Объяснение Майкла и Скотта, не зависящего от очереди, alorigthm

Question

Я изучаю Майкл & Скоттовский алгоритм блокировки очереди и пытается реализовать его на C++.

Но я произвел гонку в своем коде и думаю, что в алгоритме может быть гонка.

Я прочитал статью здесь: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms и оригинальный Dequeue псевдо-код выглядит следующим образом:

dequeue(Q: pointer to queue_t, pvalue: pointer to data type): boolean 
D1: loop       // Keep trying until Dequeue is done 
D2:  head = Q->Head    // Read Head 
D3:  tail = Q->Tail    // Read Tail 
D4:  next = head.ptr->next  // Read Head.ptr->next 
D5:  if head == Q->Head   // Are head, tail, and next consistent? 
D6:   if head.ptr == tail.ptr // Is queue empty or Tail falling behind? 
D7:   if next.ptr == NULL // Is queue empty? 
D8:    return FALSE  // Queue is empty, couldn't dequeue 
D9:   endif 
       // Tail is falling behind. Try to advance it 
D10:   CAS(&Q->Tail, tail, <next.ptr, tail.count+1>) 
D11:   else     // No need to deal with Tail 
       // Read value before CAS 
       // Otherwise, another dequeue might free the next node 
D12:   *pvalue = next.ptr->value 
       // Try to swing Head to the next node 
D13:   if CAS(&Q->Head, head, <next.ptr, head.count+1>) 
D14:    break    // Dequeue is done. Exit loop 
D15:   endif 
D16:   endif 
D17:  endif 
D18: endloop 
D19: free(head.ptr)    // It is safe now to free the old node 
D20: return TRUE     // Queue was not empty, dequeue succeeded 

На мой взгляд, гонка, как это:

1. Тема 1 расширенный на D3, а затем остановится.
2. Тема 2 вышла в D3, читать же голова, как Тема 1.
3. тему 2, к счастью, выдвинутых весь путь до D20, D19 на это освободило head.ptr
4. Thread 1 продолжает и передовые Д4, пытаясь прочитайте head.ptr->next, но как head.ptr уже освобожден Thread 1, происходит сбой.

И мой C++ код действительно всегда падает на Д4 для Тема 1.

Может кто-нибудь, пожалуйста, указать на мою ошибку и дать какое-то объяснение?

Answer 1

Спасибо, очень интересный предмет! Это определенно похоже на ошибку, но один из авторов статьи утверждает, что их free() не является нормальным свободным(), с которым мы все живем, но некоторые magic free(), поэтому нет ошибки. Фантастика.

См http://blog.shealevy.com/2015/04/23/use-after-free-bug-in-maged-m-michael-and-michael-l-scotts-non-blocking-concurrent-queue-algorithm/

Надежда никто не положил это в производство без тщательного анализа.