Two-Lock Concurrent Queue Алгоритм Выпуск

Question

Так что я собирался по статье Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms по Магеда М. Майкл и Майкл Л. Скотт, и есть небольшая проблема, которую я не понимаю:

Допустим, у нас есть два параллельных потока, которые запускаются сразу после инициализации очереди. Один из потоков вызывает enqueue, а другой - dequeue. Что мешает им получить доступ к полю next фиктивного узла одновременно? не может ли поток dequeue читать поле next, в то время как поток enqueue пишет ему? Они оба используют разные замки ... поэтому я не понимаю, что синхронизирует их.

Спасибо.

Answer 1

enqueue() управляет только хвостом, а dequeue() управляет только головой, поэтому им не нужно использовать одни и те же блокировки. Существует особый случай, когда head и tail указывают на тот же узел, «фиктивный» узел, который был создан при инициализации. И вы правы, что enqueue() может писать следующий указатель этого узла, в то время как dequeue() пытается его прочитать.

Нет проблем с одновременным чтением и записью. Обратите внимание, что enqueue() создает новый узел и полностью инициализирует этот объект, прежде чем сделать его видимым, записав его в tail-> next. Поэтому ни один другой код никогда не сможет увидеть этот новый узел в состоянии с половинным инициализацией. Кроме того, чтение/запись в указатель являются атомарными, поэтому для dequeue() невозможно получить, скажем, половину указателя.

Так что в вашем сценарии, где Епдиеие() и Dequeue() оба называются сразу же, есть две возможности:

• Епдиеие() пишет tail-> следующая перед тем Dequeue() считывает из head- > следующая. В этом случае dequeue() увидит узел, который был установлен в очередь и вернет его.
• dequeue() читает с головы-> следующий перед enqueue() пишет в tail-> next. В этом случае dequeue() считает, что очередь пуста и возвращает false.