ConcurrentLinkedQueue 비 차단 대기 열

스 레 드 안전 을 실현 하려 면 두 가지 방식 이 있 습 니 다.차단 과 비 차단 입 니 다.차단 대기 열 은 잠 금 응용 이 아니 라 차단 이 아 닌 CAS 알고리즘 응용 입 니 다.다음은 비 차단 알고리즘 에 대한 연 구 를 시작 하 겠 습 니 다.Coucurrent LinkedQueue.
ConcurrentLinkedQueue 는 링크 노드 를 기반 으로 하 는 경계 없 는 스 레 드 보안 대기 열 로 FIFO 원칙 으로 요 소 를 정렬 합 니 다."wait-free"알고리즘(즉 CAS 알고리즘)을 사용 하여 이 루어 졌 습 니 다.
Coucurrent LinkedQueue 는 다음 과 같은 몇 가지 불변성 을 규정 했다.

입단 의 마지막 요소 인 next 는 null

이다.

대기 열 에서 삭제 되 지 않 은 노드 의 item 은 null 일 수 없 으 며 head 노드 에서

까지 옮 겨 다 닐 수 있 습 니 다.

삭제 할 노드 에 대해 서 는 null 로 직접 설정 하 는 것 이 아니 라 item 도 메 인 을 null 로 설정 합 니 다.

헤드 와 tail 업데이트 지연 허용.이게 무슨 뜻 이 죠?헤드,테 일 은 항상 첫 번 째 요소 와 마지막 요 소 를 가리 키 지 않 는 다 는 뜻 이다.

head 의 불변성 과 가 변성:

불변성

삭제 되 지 않 은 모든 노드 는 head 노드 를 통 해

까지 옮 겨 다 닐 수 있 습 니 다.

head 는 null

이 될 수 없습니다.

head 노드 의 next 는 자신 을 가리 키 지 못 합 니 다

가 변성

head 의 item 은 null 일 수도 있 고 null 2 가 아 닐 수도 있 습 니 다.tail 지연 head 를 허용 합 니 다.즉,succc()방법 을 호출 하면 head 에서 tail

에 도달 할 수 없습니다.

tail 의 불변성 과 가 변성

불변성

tail 은 null

이 될 수 없습니다.

가 변성

tail 의 item 은 null 일 수도 있 고 null

이 아 닐 수도 있 습 니 다.

tail 노드 의 next 도 메 인 은 자신 을 가리 킬 수 있 습 니 다.tail 정체 head 를 허용 합 니 다.즉,succc()방법 을 호출 하면 head 에서 tail

에 도달 할 수 없습니다.

이런 특성 들 은 이미 어 지 럽 지 않 습 니까?괜찮아,우 리 는 아래 의 소스 코드 분석 을 보면 이러한 특성 을 이해 할 수 있어.
ConcurrentLinkedQueue 소스 코드 분석
Coucurrent LinkedQueue 의 구 조 는 head 노드 와 tail 노드 로 구성 되 고 모든 노드 는 노드 요소 item 과 다음 노드 를 가리 키 는 next 참조 로 구성 되 며 노드 와 노드 간 의 관 계 는 이 next 를 통 해 연 결 된 것 으로 링크 의 대기 열 을 구성 합 니 다.노드 노드 는 ConcurrentLinkedQueue 의 내부 클래스 로 다음 과 같이 정의 합 니 다.

private static class Node {
      /**       */
      volatile E item;
      volatile Node next;

      //   ,  item   next     ,    CAS   

      Node(E item) {
          UNSAFE.putObject(this, itemOffset, item);
      }

      boolean casItem(E cmp, E val) {
          return UNSAFE.compareAndSwapObject(this, itemOffset, cmp, val);
      }

      void lazySetNext(Node val) {
          UNSAFE.putOrderedObject(this, nextOffset, val);
      }

      boolean casNext(Node cmp, Node val) {
          return UNSAFE.compareAndSwapObject(this, nextOffset, cmp, val);
      }

      // Unsafe mechanics

      private static final sun.misc.Unsafe UNSAFE;
      /**     */
      private static final long itemOffset;
      /**           */

     private static final long nextOffset;

      static {
          try {
              UNSAFE = sun.misc.Unsafe.getUnsafe();
              Class> k = Node.class;
              itemOffset = UNSAFE.objectFieldOffset
                      (k.getDeclaredField("item"));
              nextOffset = UNSAFE.objectFieldOffset
                      (k.getDeclaredField("next"));
          } catch (Exception e) {
              throw new Error(e);
          }
      }
  }

열거 하 다
열 에 들 어가 면 우 리 는 매우 간단 한 과정 이 라 고 생각한다.tail 노드 의 next 는 새로운 노드 를 실행 한 다음 에 tail 을 새로운 노드 로 업데이트 하면 된다.단일 스 레 드 각도 에서 우리 가 이렇게 이해 하 는 것 은 문제 가 없 을 것 이다.그러나 다 중 스 레 드 는?만약 에 하나의 스 레 드 가 삽입 동작 을 하고 있다 면 먼저 꼬리 노드 를 가 져 온 다음 에 꼬리 노드 의 다음 노드 를 현재 노드 로 설정 해 야 합 니 다.그러나 하나의 스 레 드 가 삽입 을 완 료 했 으 면 꼬리 노드 에 변화 가 생 겼 습 니까?이 경우 Concurrent LinkedQueue 는 어떻게 처리 하나 요?우 리 는 먼저 소스 코드 를 본다.
offer(E e):지정 한 요 소 를 도 큐 끝 에 삽입 합 니 다.

public boolean offer(E e) {
        //       null
        checkNotNull(e);
        //      
        final Node newNode = new Node(e);

        //          
        for (Node t = tail, p = t;;) {
            Node q = p.next;
            // q == null    p          ，        
            //       ，            p   
            if (q == null) {                                // --- 1
                // casNext：t   next      
                // casTail：  tail    
                if (p.casNext(null, newNode)) {             // --- 2
                    // node         tail              ，    tail
                    if (p != t)                             // --- 3
                        casTail(t, newNode);                    // --- 4
                    return true;
                }
            }
            // p == q     
            else if (p == q)                                // --- 5
                // p == q             
                //         ，  offer()     poll()，  offer()          poll() 
                //    poll()    updateHead()    head     q，  p.next    ， ：p.next == p
                //       tail    head（tail  head   ），       p
                p = (t != (t = tail)) ? t : head;           // --- 6
            // tail        
            else
                // tail          ， p        
                p = (p != t && t != (t = tail)) ? t : q;    // --- 7
        }
    }

소스 코드 만 봐 도 헷 갈 려 서 노드 를 삽입 하면 한 번 분석 하면 밝 아 집 니 다.
초기 화
ConcurrentLinkedQueue 초기 화 시 head,tail 에 저 장 된 요 소 는 모두 null 이 고 head 는 tail 과 같 습 니 다.
원소 추가 A
프로그램 분석 에 따 르 면 첫 번 째 요소 A,head=tail=dummy Node,모든 q=p.next=null,직접 2:p.casNext(null,new Node)를 삽입 합 니 다.p==t 가 성립 되 기 때문에 절차 3:casTail(t,new Node)을 실행 하지 않 고 직접 return 합 니 다.A 노드 를 삽입 하면 다음 과 같 습 니 다.
원소 추가 B
q=p.next=A,p=tail=dummy Node,그래서 바로 7:p=(p!=t && t != (t = tail)) ? t : q;。이때 p=q,그리고 두 번 째 순환 q=p.next=null,절차 2:p==null 이 성립 되 고 이 노드 를 삽입 합 니 다.p=q,t=tail 이기 때문에 절차 3:p!=t 성립,집행 절차 4:casTail(t,newNode),그리고 return.다음 과 같다.
노드 C 추가
이때 t=tail,p=t,q=p.next=null 은 요소 A 를 삽입 하 는 것 과 다 름 이 없습니다.다음 과 같 습 니 다.
여기 서 전체 offer()과정 은 이미 분석 이 끝 났 습 니 다.아마도 p==q 는 이해 하기 어 려 울 것 입 니 다.p 는 q.next 와 같 지 않 습 니까?어떻게 p==q 가 있 습 니까?이 의문 은 우리 가 열 거 된 poll()에서 분석 합 니 다.
열거 하 다
Concurrent LinkedQueue 는 poll()방법 을 제공 하여 열 을 표시 합 니 다.입 열 은 주로 tail 과 관련 되 고,출 열 은 head 와 관련된다.우 리 는 먼저 소스 코드 를 본다.

public E poll() {
        //     p         head    
        restartFromHead:        //       ？      
        for (;;) {
            for (Node h = head, p = h, q;;) {

                //    item
                E item = p.item;

                // item   null，  item    null
                if (item != null && p.casItem(item, null)) {                    // --- 1
                    // p != head    head
                    if (p != h)                                                 // --- 2
                        // p.next != null，  head   p.next ,     p
                        updateHead(h, ((q = p.next) != null) ? q : p);          // --- 3
                    return item;
                }
                // p.next == null     
                else if ((q = p.next) == null) {                                // --- 4
                    updateHead(h, p);
                    return null;
                }
                //       poll   ，           p      —— p.next = p，p         ，      
                else if (p == q)                                                // --- 5
                    continue restartFromHead;
                else
                    p = q;                                                      // --- 6
            }
        }
    }

이것 은 offer()방법 에 비해 간단 할 것 입 니 다.그 안에 중요 한 방법 이 있 습 니 다.updateHead().이 방법 은 CAS 에서 head 노드 를 업데이트 하 는 데 사 용 됩 니 다.다음 과 같 습 니 다.

final void updateHead(Node h, Node p) {
    if (h != p && casHead(h, p))
        h.lazySetNext(h);
}

우 리 는 먼저 위의 offer()의 링크 poll()을 떨 어 뜨리 고 A,B,C 노드 구 조 를 다음 과 같이 추가 합 니 다.
poll A
head=dumy,p=head,item=p.item=null,절차 1 이 성립 되 지 않 습 니 다.절차 4:(q=p.next)==null 이 성립 되 지 않 습 니 다.p.next=A,단계 6,다음 순환 으로 넘 어 갑 니 다.이때 p=A,그래서 절차 1 item!=null,p.casItem(item,null)진행 성공,이때 p==A!=h,그래서 실행 절차 3:updateHead(h,(q=p.next)!=null) ? q : p)，q = p.next = B != null,head CAS 를 B 로 업데이트 합 니 다.다음 과 같 습 니 다.
poll B
head=B,p=head=B,item=p.item=B,절차 성립,절차 2:p!=h.성립 되 지 않 고 직접 return,다음 과 같 습 니 다.
poll C
head=dumy,p=head=dumy,tiem=p.item=null,절차 1 이 성립 되 지 않 습 니 다.절차 4:(q=p.next)==null,성립 되 지 않 습 니 다.그리고 절차 6 으로 넘 어 갑 니 다.이때 p=q=C,item=C(item),절차 1 이 성립 되 기 때문에 C(item)는 null,절차 2:p 로 설정 합 니 다!=h 성립,실행 절차 3:updateHead(h,(q=p.next)!=null) ? q:p),다음 과 같다.
여기 서 한눈 에 알 수 있 는 지,여기 서 우 리 는 offer()의 절차 5 를 분석 합 니 다.

else if(p == q){
	p = (t != (t = tail))? t : head;
}

Concurrent LinkedQueue 에 따 르 면 p==q 는 이 노드 가 삭제 되 었 음 을 나타 낸다.즉,tail 은 head 보다 뒤 처 져 있 고 head 는 succ()방법 으로 tail 에 옮 겨 다 닐 수 없다.어떻게 합 니까?t != (t = tail))? t : head;（이 코드 의 가 독성 이 너무 떨 어 집 니 다.정말 이해 하기 어렵 습 니 다.t 로 이해 할 수 있 을 지 모 르 겠 습 니 다!=tail ? tail:head)이 코드 는 주로 tail 노드 가 바 뀌 었 는 지 확인 하 는 것 입 니 다.만약 에 변화 가 발생 하면 tail 이 다시 위 치 를 정 했 음 을 설명 합 니 다.tail 을 다시 찾 으 면 됩 니 다.그렇지 않 으 면 head 만 가리 킬 수 있 습 니 다.
위 에 있 는 그 요소 D 를 다시 삽입 합 니 다.p=head,q=p.next=null,실행 절차 1:q=null 및 p!=t,그래서 실행 절차 4:다음 과 같 습 니 다.
원소 E,q=p.next=null,p==t 를 삽입 하기 때문에 E 를 삽입 하면 다음 과 같 습 니 다.
여기까지 Concurrent LinkedQueue 의 전체 입 열,출 열 을 분 석 했 습 니 다.Concurrent LinkedQueue LZ 에 대해 진심으로 알 아 보기 어렵 고 알 아 본 후에 도 디자인 이 너무 정교 하 다 고 감탄 합 니 다.CAS 를 이용 하여 데이터 조작 을 완성 하 는 동시에 대열 의 불일치 성 을 허용 합 니 다.이런 약 한 일치 성 은 정말 강하 습 니 다.Doug Lea 의 천재 에 다시 한 번 감 탄 드 립 니 다.