Michael-Scott Queue 원본 논문의 오류

[codingskynet]

원본 논문에는 다음과 같이 알고리즘이 작성되어 있다.

dequeue(Q: pointer to queue t, pvalue: pointer to data type): boolean
D01:     loop # Keep trying until Dequeue is done
D02:         head = Q–>Head # Read Head
D03:         tail = Q–>Tail # Read Tail
D04:         next = head–>next # Read Head.ptr–>next
D05:         if head == Q–>Head # Are head, tail, and next consistent?
D06:             if head.ptr == tail.ptr # Is queue empty or Tail falling behind?
D07:                 if next.ptr == NULL # Is queue empty?
D08:                     return FALSE # Queue is empty, couldn’t dequeue
D09:                 endif
D10:                 CAS(&Q–>Tail, tail, <next.ptr, tail.count+1>) # Tail is falling behind. Try to advance it
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
D13:                 if CAS(&Q–>Head, head, <next.ptr, head.count+1>) # Try to swing Head to the next node
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 dummy node
D20:     return TRUE # Queue was not empty, dequeue succeeded

근데 이거 if next.ptr == NULL이 D06보다 먼저 test되어야 에러가 안 난다. 이와 같게 작성하면 D13에서 next.ptr이 NULL일 수도 있다는 것이 관찰되었다. 왜징

[codingskynet]

아니 근데 진짜 생각 열심히 해봤는데, head != tail && head.next == NULL이 어떻게 가능한건지 이해가 안 감...