5
我正在學習邁克爾& Scott的無鎖隊列算法並試圖用C++實現它。解釋邁克爾和斯科特無鎖隊列算法
但是我在我的代碼中產生了一場比賽，並認爲可能會出現算法競賽。
我這裏看報紙： Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms 和原始出隊的僞代碼如下：
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前進到D3然後停下來。
- 線程2提前至D3，讀同樣的頭，螺紋1
- 線程2幸運的是先進的一路D20，D19在其釋放head.ptr
- 線程1繼續和先進D4，試圖閱讀
head.ptr->next，但由於head.ptr已被線程1釋放，發生崩潰。
而我的C++代碼真的總是在D4崩潰線程1
任何人都可以請您指出我的錯誤，並給予一定的解釋？