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

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

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

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

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

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

Если узел [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
    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]

Идея реализации

Удаление элемента

Для удаления элемента необходимо переместить указатель [math]H[/math] на следующую в списке вершину.

def pop(): Int
    if (H.next == null):
        throw new EmptyException()
    H = H.next
    return H.data //H - новый фиктивный элемент

Добавление элемента

Создадим новый узел списка, и добавим его в конец очереди.

def push(x: Int):
    newTail = new Node(x, new AtomicReference<Node>(null))
    T.next = newTail //Добавление новой вершины в очередь
    T = T.next //Изменение хвоста списка

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

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