Giải thích Michael & Scott hàng đợi không bị khóa alorigthm

Question

Tôi đang nghiên cứu Michael & Thuật toán xếp hàng không có khóa của Scott và cố triển khai nó trong C++.

Nhưng tôi đã tạo ra một cuộc đua trong mã của mình và nghĩ rằng có thể có một cuộc đua trong thuật toán.

Tôi đọc báo ở đây: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms và Dequeue pseudo-code ban đầu là như sau:

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 

Theo quan điểm của tôi, cuộc đua là như thế này:

1. Chủ đề 1 tiên tiến đến D3 rồi dừng lại.
2. Chủ đề 2 tiến đến D3, đọc phần đầu giống như Chủ đề 1.
3. Chủ đề 2 may mắn tiến tất cả các cách để D20, D19 tại nó giải phóng head.ptr
4. Chủ đề 1 tiếp tục và tiên tiến để D4, cố gắng đọc head.ptr->next, nhưng như head.ptr đã được giải phóng bởi Chủ đề 1, sự cố xảy ra.

Và C++ mã của tôi thực sự luôn luôn treo ở D4 cho Chủ đề 1.

bất cứ ai có thể vui lòng chỉ ra sai lầm của tôi và đưa ra một số lời giải thích?

Answer 1

Cảm ơn bạn, chủ đề rất thú vị! Nó chắc chắn trông giống như một con bọ, nhưng một trong những tác giả của bài báo khẳng định rằng chúng miễn phí() không miễn phí() tất cả chúng ta sống, nhưng một số phép thuật tự do(), vì vậy không có lỗi. Tuyệt diệu.

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

Hy vọng không ai đưa điều này vào sản xuất mà không phân tích kỹ lưỡng.