Изменения
→Корректная lock-free реализация
=== Основная идея ===
Нельзя выполнить добавление элемента в очередь и перемещение <tex>T</tex> атомарно. В таком случае, пусть остальные потоки помогают перенести указатель на хвост очереди. Если поток видит непустой <tex>T.next</tex> (то есть если он провалил <tex>CAS(tail.next, null, newTail)</tex>), то он должен помочь перенести <tex>T</tex>, то есть выполнить <tex>CAS(T, tail, tail.next.get())</tex> однократно. Если <texttex>CAS</texttex> выполнен успешно, то хвост перемещён успешно (а значит, наш поток должен вернуться к добавлению нового элемента). Если же он выполнен неудачно, то это значит, что <tex>T</tex> уже не указывает на <tex>tail</tex>, а значит, другой поток уже успешно переместил хвост (а значит, наш поток должен вернуться к добавлению нового элемента).
=== Реализация <tex>push</tex> ===
val newTail = Node(x, AtomicReference(null))
while (true) {
val tail = T.get()
if (tail.next.compareAndSet(null, newTail)) {
/*
Если T - последний добавленный элемент, добавляем ещё один элемент в хвост и
пробуем передвинуть T. Если не получилось передвинуть T,
значит, другой поток сделал это за нас, завершаем работу
*/
T.compareAndSet(tail, newTail)
return
} else {
/*
Если T - не последний элемент, то передвигаем T на последний элемент
Если этого сделать не получилось, значит, это сделал другой поток
В любом случае, возвращаемся в начало CAS-цикла, чтобы завершить добавление в очередь
*/
T.compareAndSet(tail, tail.next.get())
}
}
==Примечания==
