잠금 해제 대기열에 버그가 어디 있습니까?

Question

Java lock free queue 구현을 작성했습니다. 동시성 버그가 있습니다. 못 찾겠 어. 이 코드는 중요하지 않습니다. 휘발성 변수와 관련된 관찰 된 동작을 설명 할 수 없다는 것에 대해 걱정할뿐입니다.

버그는 예외 ("null head")로 볼 수 있습니다. 현재 큐 크기를 유지하는 원자 적 정수가 있기 때문에 불가능한 상태입니다. 큐에는 스텁 요소가 있습니다. 독자 스레드는 테일 포인터를 변경하지 않고 작성자 스레드는 헤드 포인터를 변경하지 않습니다.

대기열 길이 변수는 링크 된 목록이 절대로 비어 있지 않음을 보장합니다. 그것은 세마포어입니다.

take 메소드는 길이 값을 도난당한 것처럼 동작합니다.

class Node<T> { 
    final AtomicReference<Node<T>> next = new AtomicReference<Node<T>>(); 
    final T ref; 
    Node(T ref) { 
     this.ref = ref; 
    } 
} 
public class LockFreeQueue<T> { 
    private final AtomicInteger length = new AtomicInteger(1); 
    private final Node stub = new Node(null); 
    private final AtomicReference<Node<T>> head = new AtomicReference<Node<T>>(stub); 
    private final AtomicReference<Node<T>> tail = new AtomicReference<Node<T>>(stub); 

    public void add(T x) { 
     addNode(new Node<T>(x)); 
     length.incrementAndGet(); 
    } 

    public T takeOrNull() { 
     while (true) { 
      int l = length.get(); 
      if (l == 1) { 
       return null; 
      } 
      if (length.compareAndSet(l, l - 1)) { 
       break; 
      } 
     } 
     while (true) { 
      Node<T> r = head.get(); 
      if (r == null) { 
       throw new IllegalStateException("null head"); 
      } 
      if (head.compareAndSet(r, r.next.get())) { 
       if (r == stub) { 
        stub.next.set(null); 
        addNode(stub); 
       } else { 
        return r.ref; 
       } 
      } 
     } 
    } 

    private void addNode(Node<T> n) { 
     Node<T> t; 
     while (true) { 
      t = tail.get(); 
      if (tail.compareAndSet(t, n)) { 
       break;  
      } 
     } 
     if (t.next.compareAndSet(null, n)) { 
      return; 
     } 
     throw new IllegalStateException("bad tail next"); 
    } 
} 

Answer 1

난 당신이 takeOrNull()에서 카운터를 사용하면 스텁을 제거 할 때, 당신은 1 길이를 감소하는 방법에 오류가 있다고 생각하지만, 다시 스텁을 추가 할 때이를 다시 증가하지 않는다 add() 대신 addNode()를 사용하기 때문에 끝입니다. 지금은 하나 개의 스레드가, 길이가 1, 헤드 FIRST_NODE로 이동,이 때문에 스텁 노드 감소 takeOrNull을() 일을 시작 그래서

Length is 2 
STUB -> FIRST_NODE -> NULL 
^  ^
|   | 
Head  Tail 

: 의 당신의 큐는 다음과 같습니다 있도록 성공적 요소를 추가한다고 가정 해 봅시다 끝까지 다시 추가되므로 지금 가지고 있습니다.

Length is 1 
FIRST_NODE -> STUB -> NULL 
^   ^
|    | 
Head   Tail 

표시 되나요? 길이는 1입니다! 다음 takeOrNull()에서 FIRST_NODE가 여전히 대기열에 있고 반환 된 적이 없더라도 NULL이 반환됩니다. 데이터가 손실되었습니다. 또한이 광고를 무한 반복하고 노드 누적을 시작할 수 있습니다. 3 개의 노드를 추가하면 Length는 4이고 FIRST, STUB, NEW1, NEW2, NEW3이 있습니다. 그런 다음 세 개의 takeOrNull()을 수행하면 NEW2, NEW3, STUB 및 길이 1로 끝납니다. 이렇게하면 끝나는 요소가 줄어들지 만 이것이 예외를 트리거하는 방법에 대해 완전히 확신하지 못한다는 것을 인정합니다. 좀 더 먹고 생각해 봅시다. ;-)

EDIT : Ok food가 나에게 좋았는데, 머리 null 예외를 유발하는 시퀀스가 ​​떠올랐다. 의 이전처럼 하나 개의 요소로 유효한 큐 시작하자 :

Length is 2 
STUB -> FIRST_NODE -> NULL 
^  ^
|   | 
Head  Tail 

이제 우리는 네 takeOrNull하려고 스레드,이()와 동시에 추가 두()를 가지고있다. 두 스레드를 모두 추가하면 테일 포인터가 올바르게 이동합니다. 첫 번째 스레드는 FIRST에서 SECOND로 테일을 이동 한 다음 일시 중지되었습니다. 두 번째 추가 스레드는 SECOND에서 THIRD로 테일을 이동 한 다음 이전 테일 (SECOND)의 다음 포인터를 업데이트 한 다음 카운터를 증가시키고 종료합니다. 길이가 3이기 때문에, 모두 요소를 얻을 수있을 것입니다,

Length is 3 
STUB -> FIRST_NODE -> NULL   SECOND_NODE -> THIRD_NODE -> NULL 
^             ^
|              | 
Head             Tail 

지금 두 takeOrNull 스레드가 깨어나 실행합니다 우리는 왼쪽있어! 첫 번째는 Head를 STUB에서 FIRST로 이동시키고, 두 번째는 Head를 FIRST에서 NULL로 이동시킵니다. 이제 HEAD가 null이고 takeOrNull()이 다음에 호출 될 때마다 EXCEPTION!