설명 Michael & Scott lock-free 큐 alorigthm

Question

Michael의 공부하고 있습니다. & Scott의 lock-free 큐 알고리즘을 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. 스레드 1은 전진 D3으로 이동 한 다음 중지합니다.
2. 스레드 2 스레드로 2 다행히 D20에있는 모든 방법을 고급 1.
3. 스레드 같은 머리를 읽고, D3에 진출 D19에서 그것을하려고,
4. 스레드 1이 계속되고 고급 D4에 head.ptr을 해제 head.ptr->next을 읽으십시오. 그러나 head.ptr이 이미 스레드 1에 의해 해제되었으므로 충돌이 발생합니다.

그리고 내 C++ 코드는 정말 항상 누군가가 내 실수를 지적하고 약간의 설명을 적어주세요 수 스레드 1

위해 D4에 충돌?

Answer 1

감사합니다. 매우 흥미로운 제목입니다. 그것은 분명히 버그처럼 보입니다. 그러나이 논문의 저자 중 한 명은 무료()가 보통 자유롭지는 않지만() 우리 모두가 살고 있지만 일부 마법은 무료()이므로 버그가 없다고 주장합니다. 환상적.

는

http://blog.shealevy.com/2015/04/23/use-after-free-bug-in-maged-m-michael-and-michael-l-scotts-non-blocking-concurrent-queue-algorithm/ 아무도 철저한 분석없이 생산에이를 넣지 희망을 참조하십시오.