Объясните Майкл и Скотт замок-бесплатные alorigthm очереди


Я изучаю алгоритм Майкла и Скотта lock-free queue и пытаюсь реализовать его в C++.

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

Я читаю эту статью здесь: простой, быстрый и практичный неблокирующий и блокирующий Алгоритмы Параллельной Очереди и исходный псевдокод 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 он освободил голову.ptr
  4. поток 1 продолжает и продвигается к D4, пытаясь прочитать head.ptr->next, но поскольку head.ptr уже освобожден потоком 1, происходит сбой.

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

Может ли кто-нибудь указать на мою ошибку и дать какое-то объяснение ?
1   7   2016-11-26 15:47:54

1 ответ:

Спасибо, очень интересная тема! Это определенно похоже на ошибку, но один из авторов статьи утверждает, что их free () - это не обычный free (), с которым мы все живем, а какой-то волшебный 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/

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