1632
правки
Изменения
м
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
rollbackEdits.php mass rollback
'''Очередь Майкла и Скотта''' (англ. ''(Michael-Scott Queue)'' ) - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scott <ref>[http://www.cs.rochester.edu/~scott/papers/1996_PODC_queues.pdf? Simple, Fast, and Practical Non-Blocking and BlockingConcurrent Queue Algorithms]</ref>.
== Структура очереди ==
Если узел <tex>node</tex> является последним в списке, то <tex>node.next</tex> указывает на <tex>null</tex>.
Сама очередь состоит из двух атомарных указателей: <tex>H</tex> на голову и<tex>T</tex> на хвост. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.
Голова списка является фиктивным элементом ''(dummy)''. Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.
tail = '''new''' AtomicReference<Node>(dummy)
Будем поддерживать следующий инвариант: в нашей очереди <tex>H</tex> указывает на узел, находящийся не правее узла, на который указывает <tex>T</tex>.
==Однопоточная реализация==
При данной реализации мы сталкиваемся со следующей проблемой
=== Описание проблемы ===
Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>elem</tex> и <tex>elem'</tex>. Рассмотрим следующую последовательность действий:
'''def''' pop(): '''Int'''
'''while''' ('''true'''): <font color=green>//CAS-цикл</font>
head = H.get() <font color=green>//Сохраняем в локальные переменные текущие голову и хвост, а так же следующий за головным элемент</font>
tail == head => tail.next == head.next
*/</font>
'''CAS'''(T, tail, nextHead)
'''else''':
<font color=green>// Очередь гарантированно не пуста, следующий элемент существует</font>
