Очередь Майкла и Скотта

Эта статья находится в разработке!

Очередь Майкла и Скотта (Michael-Scott Queue) - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье .

Структура очереди

Очередь моделируется с помощью односвязного списка. Каждый элемент списка ([math]Node[/math]) содержит ссылку на хранимые в нём данные и указатель на следующий элемент списка (который можно менять атомарно).

case class Node<T>(val data: T, val next: AtomicReference<Node<T>>)

Если узел [math]node[/math] является последним в списке, то его [math]next[/math] указывает на [math]null[/math].

Сама очередь состоит из двух указателей: на голову [math]H[/math] и на хвост [math]T[/math], которые можно менять атомарно. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел списка, на который указывает [math]H[/math], является фиктивным (dummy). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного dummy-элемента, на который указывают [math]T[/math] и [math]H[/math].

class Queue<T>
    dummy = new Node(null, new AtomicReference<Node>(null))
    head = new AtomicReference<Node>(dummy)
    tail = new AtomicReference<Node>(dummy)

// TODO; картинка

Будем поддерживать следующий инвариант: в нашей очереди [math]H[/math] указывает на узел, находящийся не правее узла, на который указывает [math]T[/math]

Источники информации

• Maurice Herliny & Nir Shavit - The Art of Multiprocessor programming, стр 230