Изменения
убрала лишнюю переменную, которая, вероятно, осталась после копипасты
'''Очередь Майкла и Скотта''' (англ. ''(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> содержит ссылку на хранимые в нём данные и атомарный указатель на следующий элемент списка.
'''case class''' Node('''val''' data: '''Int''', '''val''' next: AtomicReference<Node>)
Если узел <tex>node</tex> является последним в списке, то <tex>node.next</tex> указывает на <tex>null</tex>.
Сама очередь состоит из двух атомарных указателей: <tex>H</tex> на голову и<tex>T</tex> на хвост. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.
Голова списка является фиктивным элементом ''(dummy)''. Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>.
[[Файл:Структура_msqueue.PNG|500px|thumb|center|Структура очереди Майкла и Скотта]]
'''class''' Queue
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>
