Изменения

{{В разработке}}'''Очередь Майкла и Скотта''' (англ. ''(Michael-Scott Queue)'' ) - алгоритм построения lock-free очереди. Впервые был предложен Maged M. Michael и Michael L. Scot в статье 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>, которые можно менять атомарнона хвост. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.

Узел Голова списка, на который указывает <tex>H</tex>, является фиктивным (элементом ''(dummy)''). Данные, хранимые в этом узле, не имеют значения. Изначально очередь состоит из одного ''dummy''-элемента, на который указывают <tex>T</tex> и <tex>H</tex>. [[Файл:Структура_msqueue.PNG|500px|thumb|center|Структура очереди Майкла и Скотта]]

Будем поддерживать следующий инвариант: в нашей очереди <tex>H</tex> указывает на узел, находящийся не правее узла, на который указывает <tex>T</ TODO; картинкаtex>.

Будем поддерживать следующий инвариант: в нашей очереди <tex>H</tex> указывает на узел, находящийся не правее узла, на который указывает <tex>T</tex> ==Идея реализацииОднопоточная реализация==

== Многопоточная Не lock-free многопоточная реализация ==

Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>) использовать <tex>CAS</tex>.

=== Описание проблемы ===

'''if ''' ('''CAS'''(tail.next, '''null''', newTail)): <font color=green> /* Если T указывает на последний добавленный элемент и получилось добавить ещё один элемент в хвост,

если Если получилось - то мы сами передвинули T, завершаем работу */ </font>

else: <font color=green>/* Если T - не последний добавленный элемент элемент, то передвигаем T на последний элемент Если этого сделать не получилось, значит, это сделал другой поток. Если получилось - значит, наш поток передвинул T на текущий последний элемент. В любом случае, возвращаемся в начало CAS-цикла, чтобы завершить добавление в очередь новой вершины. */</font> '''CAS'''(T, tail, tail.next.get())

val newTail = Node(x, AtomicReference(null))== Проблема с <tex>pop</tex> ===

Если мы попытаемся воспользоваться написанной выше реализацией метода <tex>pop</tex>, инвариант очереди не будет соблюдён. В силу особенностей реализации метода <tex>push</tex>, в некоторые моменты <tex>T</tex> может указывать не на добавленный последним элемент, а на добавленный предпоследним. В таком случае, с помощью последовательности удалений можно добиться того, что <tex>H</tex> будет указывать на последний добавленный элемент, а <tex>T</tex> - на предпоследний. Таким образом, <tex>H</tex> будет указывать на вершину правее чем та, на которую указывает <tex>T</tex>, то есть инвариант очереди будет нарушен === Корректная реализация === Основная проблема предыдущей реализации состоит в том, что в методе <tex>pop</tex> при перемещении <tex>H</tex>, мы никак не следили за положением <tex>T</tex>. Эту проблему можно исправить следующим образом: пусть в методе <tex>pop</tex> рабочий поток будет помогать переместить указатель <tex>T</tex> на последний добавленный элемент (аналогично действиям рабочего потока в методе <tex>push</tex>). Для определения того, указывает ли <tex>T</tex> на последний добавленный элемент, воспользуемся следующим соображением: если <tex>T</tex> указывает на последний добавленный элемент, то <tex>T.get().next == '''null'''</tex>, так как за последним добавленным элементом нет других элементов. В противном случае <tex>T</tex> указывает на предпоследний добавленный элемент, и его надо передвинуть на последний добавленный.  '''def''' pop(): '''Int''' '''while ''' ('''true''') {: <font color=green>//CAS-цикл</font> head = H.get() <font color=green>//Сохраняем в локальные переменные текущие голову и хвост, а так же следующий за головным элемент</font> val tail = T.get() if (tail nextHead = head.next.compareAndSetget(null, newTail) '''if''' (head == tail) {: <font color=green>/* Если T - последний добавленный элементhead и tail совпадают, добавляем это ещё один элемент в хвост ине означает, что очередь пуста. пробуем передвинуть T Возможно, что мы просто не успели подвинуть tail. Если tail.next не получилось передвинуть Tnull, то мы просто не успели подвинуть tail при добавлении. */</font> '''if''' (nextHead == '''null'''): <font color=green>// Следующего элемента нет,очередь пуста</font> '''throw''' '''new''' EmptyException() '''else''': <font color=green>/* значит push не успел подвинуть T, другой наш поток сделал это за нас, завершаем работудолжен помочь tail == head => tail.next == head.next */</font> '''else''': <font color=green>// Очередь гарантированно не пуста, следующий элемент существует</font> T result = nextHead.compareAndSetdata '''if''' (tail'''CAS'''(H, head, newTailnextHead)): return } else { <font color=green>/* Если T - не последний элементполучилось переставить голову, то передвигаем T на последний элементфиктивным элементом стал H.next, результат - данные, которые в нём лежали. Если этого сделать не получилось, значит, это сделал другой поток- В любом случае, возвращаемся в начало CAS-цикла, чтобы завершить добавление в очередьметода и пробуем ещё раз */</font> T.compareAndSet(tail, tail.next.get()) } }'''return''' result