Изменения
убрала лишнюю переменную, которая, вероятно, осталась после копипасты
== Структура очереди ==
Очередь моделируется с помощью односвязного спискапостроена на односвязном списке. Каждый элемент списка (<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>, которые можно менять атомарнона хвост. Удаление из очереди происходит со стороны головы, добавление - со стороны хвоста.
'''class''' Queue
tail = '''new''' AtomicReference<Node>(dummy)
Будем поддерживать следующий инвариант: в нашей очереди <tex>H</tex> указывает на узел, находящийся не правее узла, на который указывает <tex>T</ TODO; картинкаtex>.
=== Удаление элемента ===
T = T.next <font color=green>//Изменение хвоста списка</font>
== Многопоточная Не lock-free многопоточная реализация ==
Будем при всех изменениях указателей на вершины списка использовать <tex>CAS</tex> (то есть при изменении <tex>T</tex>, <tex>H</tex>, и <tex>T.next</tex>) использовать <tex>CAS</tex>.
=== Удаление элемента ===
При данной реализации мы сталкиваемся со следующей проблемой
=== Описание проблемы ===
Рассмотрим ситуацию, при которой два потока <tex>A</tex> и <tex>B</tex> добавляют в очередь элементы <tex>elem</tex> и <tex>elem'</tex>. Рассмотрим следующую последовательность действий:
=== Реализация <tex>push</tex> ===
'''def''' push(x: '''Int'''):
newTail = '''new''' Node(x, '''new''' AtomicReference<Node>(null))
'''while''' ('''true'''): <font color=green>//CAS-цикл</font>
tail = T.get()
'''if''' ('''CAS'''(tail.next, '''null''', newTail)):
<font color=green>/*
Если T указывает на последний добавленный элемент и
получилось добавить ещё один элемент в хвост,
пробуем передвинуть T. Если не получилось передвинуть T,
значит, другой поток сделал это за нас, завершаем работу.
Если получилось - то мы сами передвинули T, завершаем работу
*/</font>
'''CAS'''(T, tail, newTail)
'''return'''
else:
<font color=green>/*
Если T - не последний добавленный элемент элемент, то передвигаем T на последний элемент
Если этого сделать не получилось, значит, это сделал другой поток.
Если получилось - значит, наш поток передвинул T на текущий последний элемент.
В любом случае, возвращаемся в начало CAS-цикла, чтобы завершить добавление в очередь новой вершины.
*/</font>
'''CAS'''(T, tail, tail.next.get())
== Корректная реализация <tex>pop</tex> ==
=== Проблема с <tex>pop</tex> ===
==Примечания==