Java JUC 학습 - ConcurrentLinkedDeque 상세 설명

Java JUC 학습 - ConcurrentLinkedDeque 상세 설명
선언

병발 프로그램 을 어떻게 실현 하 는 지 는 자바 와 다른 고급 언어 에 있어 쉽 지 않 은 일이 다.대학 1 학년 지난 학기 에 우 리 는 체인 시 계 를 배 웠 다.링크 는 자주 사용 하 는 데이터 구조 라 고 할 수 있 습 니 다. 체인 식 대기 행렬 과 스 택 을 실현 하 든 트 리 를 실현 하 든 모두 이런 데이터 구조 가 필요 합 니 다.그러나 처음에 우 리 는 링크 의 병발 문 제 를 고려 한 적 이 없다. 예 를 들 어 다음은 전형 적 인 링크 삽입 과정 이다.

//C Source Code
//    
LinkNode *SearchNode(LinkList *list, int i);
//    
void LinkListInsert(LinkList *list, LinkNode *node, int i) {
//              
    LinkNode *previous = SearchNode(list, i-1);
//        
    node->next = previous->next;
    previous->next = node;
}

만약 에 하나의 스 레 드 조작 링크 만 있다 면 문제 가 없 을 것 입 니 다. 그러나 링크 의 삽입 작업 은 실제 적 으로 비 원자 (nonatomic) 접근 이기 때문에 다 중 스 레 드 가 같은 링크 를 조작 하면 문제 가 발생 할 수 있 습 니 다.이런 문 제 를 해결 하 는 방법 은 스 레 드 동기 화 를 사용 하여 방문 할 때 자 물 쇠 를 채 우 는 것 이다.하지만 이렇게 되면 프로 그래 밍 이 번 거 롭 고 예측 할 수 없 는 문제 도 많다.자바 에 서 는 다 중 스 레 드 접근 을 위 한 JUC 라 이브 러 리 를 제공 합 니 다.오늘 소개 한 것 이 바로 그 중의 ConcurrentLinkedDeque 유형 이다.

0x 01 ConcurrentLinkedDeque 개요

ConcurrentLinkedDeque 는 자바 SE 7 / JDK 7 부터 제공 하 는 Non - blocking Thread - safe List (비 차단 식 스 레 드 보안 링크) 로 java.util.concurrent 가방 에 속 합 니 다.그 유형의 원형 은 다음 과 같다.

public class ConcurrentLinkedDeque
extends AbstractCollection
implements Deque, Serializable

API 프로필 에서 ConcurrentLinkedDeque 에 대한 표현 은 다음 과 같다.

An unbounded concurrent deque based on linked nodes. Concurrent insertion, removal, and access operations execute safely across multiple threads. A ConcurrentLinkedDeque is an appropriate choice when many threads will share access to a common collection. Like most other concurrent collection implementations, this class does not permit the use of null elements.

대충 말 하면 ConcurrentLinkedDeque 은 링크 노드 를 바탕 으로 하 는 무한 병발 링크 이다.삽입, 삭제, 접근 작업 을 안전하게 병행 할 수 있 습 니 다.많은 스 레 드 가 공공 집합 을 동시에 방문 할 때 ConcurrentLinkedDeque 는 적당 한 선택 이다.대부분의 다른 병렬 집합 유형 과 마찬가지 로 이 종 류 는 빈 요 소 를 사용 할 수 없습니다.

아름 답 게 들 리 지만 사용 과정 에서 요소 의 수량 에 대한 문 제 를 주의해 야 합 니 다. API 문서 에서 이렇게 표현 합 니 다.

Beware that, unlike in most collections, the size method is NOT a constant-time operation. Because of the asynchronous nature of these deques, determining the current number of elements requires a traversal of the elements, and so may report inaccurate results if this collection is modified during traversal.

대부분의 집합 유형 과 달리 그 size 방법 은 상수 적 인 조작 이 아니다.링크 의 비동기 성 때문에 현재 요소 의 수량 을 확인 하려 면 모든 요 소 를 옮 겨 다 녀 야 하기 때문에 옮 겨 다 니 는 동안 다른 스 레 드 가 이 집합 을 수정 하면 size 방법 은 정확 하지 않 은 결 과 를 보고 할 수 있 습 니 다.

이 동시에 링크 에 대한 대량 작업 도 원자 조작 이 아니 므 로 사용 할 때 API 문서 에서 이렇게 표현 해 야 합 니 다.

Bulk operations that add, remove, or examine multiple elements, such as addAll(java.util.Collection extends E>) , removeIf(java.util.function.Predicate super E>) or forEach(java.util.function.Consumer super E>) , are not guaranteed to be performed atomically.

대량의 조작 은 여러 요 소 를 추가, 삭제 또는 검사 하 는 것 을 포함한다. 예 를 들 어 addAll(java.util.Collection extends E>), removeIf(java.util.function.Predicate super E>) 또는 removeIf(java.util.function.Predicate super E>) 또는 forEach(java.util.function.Consumer super E>) 방법 을 포함 하 는데 이 유형 은 원자 방식 으로 집행 하 는 것 을 보장 하지 않 는 다.원자 접근 을 보장 하려 면 대량 조작 방법 을 사용 해 서 는 안 된다 는 것 을 알 수 있다.

API 의 소 개 를 조회 하여 우 리 는 이 유형 에 대해 대체적으로 알 게 되 었 다.실제 ConcurrentLinkedDeque 는 본질 적 으로 도 하나의 링크 이다. 이 유형 에 대한 기본 적 인 조작 도 기본 적 인 링크 와 마찬가지 로 대체적으로 '생 성, 삽입, 삭제, 옮 겨 다 니 기, 비우 기' 등 이다. 다음은 구체 적 인 예 를 통 해 설명 한다.

0x 02 ConcurrentLinkedDeque 소스 코드 분석

이 절 에서 저 는 일반 링크 의 실현 측면 에서 이 막 히 지 않 는 스 레 드 안전 링크 의 실현 을 분석 할 것 입 니 다.먼저 링크 에 있어 반드시 결점 으로 구성 되 고 정 의 는 다음 과 같다.

static final class Node {
//               ，Java    ，             。
        volatile Node prev;
//               。
        volatile E item;
//               
        volatile Node next;
    }

그 다음은 이런 공유 방법의 실현 이다. 이런 방법 은 대부분이 실 현 된 java.util.Deque 중의 인터페이스 방법 이다.

링크 에 주어진 요소 가 포함 되 어 있 는 지 확인 합 니 다

/**
     * Returns {@code true} if this deque contains the specified element.
     * More formally, returns {@code true} if and only if this deque contains
     * at least one element {@code e} such that {@code o.equals(e)}.
     *
     * @param o element whose presence in this deque is to be tested
     * @return {@code true} if this deque contains the specified element
     */
    public boolean contains(Object o) {
    //          ，          
        if (o != null) {
        //     for     ，           。
            for (Node p = first(); p != null; p = succ(p)) {
                final E item;
        //                   ，   true
                if ((item = p.item) != null && o.equals(item))
                    return true;
            }
        }
        return false;
    }

링크 가 비어 있 는 지 확인

/**
     * Returns {@code true} if this collection contains no elements.
     *
     * @return {@code true} if this collection contains no elements
     */
    public boolean isEmpty() {
    //             ，     peekFirst()     
        return peekFirst() == null;
    }

링크 에 포 함 된 요소 개 수 를 되 돌려 줍 니 다

/**
     * Returns the number of elements in this deque.  If this deque
     * contains more than {@code Integer.MAX_VALUE} elements, it
     * returns {@code Integer.MAX_VALUE}.
     *
     * 
Beware that, unlike in most collections, this method is
     * NOT a constant-time operation. Because of the
     * asynchronous nature of these deques, determining the current
     * number of elements requires traversing them all to count them.
     * Additionally, it is possible for the size to change during
     * execution of this method, in which case the returned result
     * will be inaccurate. Thus, this method is typically not very
     * useful in concurrent applications.
     *
     * @return the number of elements in this deque
     */
    public int size() {
        //     Java    （label）     ，           
        restartFromHead: for (;;) {
            //count   
            int count = 0;
            //    
            for (Node p = first(); p != null;) {
                //       
                if (p.item != null)
                    //  count 1             
                    if (++count == Integer.MAX_VALUE)
                        break;  // @see Collection.size()
                //  p         p，     
                if (p == (p = p.next))
                    continue restartFromHead;
            }
            return count;
        }
    }

링크 의 첫 번 째 결산 점 획득

public E peekFirst() {
    //          ，          
        for (Node p = first(); p != null; p = succ(p)) {
            final E item;
            if ((item = p.item) != null)
                return item;
        }
        return null;
    }

링크 끝 점 획득

public E peekLast() {
    //         ，          
        for (Node p = last(); p != null; p = pred(p)) {
            final E item;
            if ((item = p.item) != null)
                return item;
        }
        return null;
    }

다음은 protected 방법 과 private 방법 을 소개 한다.여기 서 첫 번 째 결점 에 삽입 하 는 방법 과 끝 점 에 삽입 하 는 방법 만 설명 하고 다른 방법 은 생각 이 대체적으로 같 으 므 로 여 기 는 더 이상 소개 하지 않 겠 습 니 다.

    /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
    //       ，         。
        final Node newNode = newNode(Objects.requireNonNull(e));

        restartFromHead:
        for (;;)
        //          
            for (Node h = head, p = h, q;;) {
            //  p                 
                if ((q = p.prev) != null &&
                    (q = (p = q).prev) != null)
                    // Check for head updates every other hop.
                    // If p == q, we are sure to follow head instead.
                    p = (h != (h = head)) ? h : q;
                else if (p.next == p) // PREV_TERMINATOR
                    continue restartFromHead;
                else {
                    // p is first node
                    //           p
                    NEXT.set(newNode, p); // CAS piggyback
                    //          
                    if (PREV.compareAndSet(p, null, newNode)) {
                        // Successful CAS is the linearization point
                        // for e to become an element of this deque,
                        // and for newNode to become "live".
                        if (p != h) // hop two nodes at a time; failure is OK
                        //     
                            HEAD.weakCompareAndSet(this, h, newNode);
                        return;
                    }
                    // Lost CAS race to another thread; re-read prev
                }
            }
    }

    /**
     * Links e as last element.
     */
    private void linkLast(E e) {
    //       ，         。
        final Node newNode = newNode(Objects.requireNonNull(e));

        restartFromTail:
        for (;;)
            for (Node t = tail, p = t, q;;) {
            //  p                   
                if ((q = p.next) != null &&
                    (q = (p = q).next) != null)
                    // Check for tail updates every other hop.
                    // If p == q, we are sure to follow tail instead.
                    p = (t != (t = tail)) ? t : q;
                else if (p.prev == p) // NEXT_TERMINATOR
                    continue restartFromTail;
                else {
                    // p is last node
                    //           p
                    PREV.set(newNode, p); // CAS piggyback
                    if (NEXT.compareAndSet(p, null, newNode)) {
                        // Successful CAS is the linearization point
                        // for e to become an element of this deque,
                        // and for newNode to become "live".
                        if (p != t) // hop two nodes at a time; failure is OK
                        //     
                            TAIL.weakCompareAndSet(this, t, newNode);
                        return;
                    }
                    // Lost CAS race to another thread; re-read next
                }
            }
    }

역시 자바 라 이브 러 리 의 코드 실현 은 비교적 복잡 하 다. 이번 에는 대충 알 고 있 을 뿐이다.어떤 부분 은 여전히 잘 이해 하지 못 하기 때문에 좀 더 공부 해 야 한다.

0x 03 Concurrent LinkedDeque 의 실제 응용

설명 을 많이 하지 않 고 직접 응용 했다.

package cn.xiaolus.cld;

import java.util.concurrent.ConcurrentLinkedDeque;

public class CLDMain {
    private static ConcurrentLinkedDeque cld = new ConcurrentLinkedDeque<>();
    
    public static void main(String[] args) {
        int numThread = Runtime.getRuntime().availableProcessors();
        Thread[] threads = new Thread[numThread];
        for (int i = 0; i < threads.length; i++) {
            (threads[i] = new Thread(addTask(), "Thread "+i)).start();
        }
    }
    
    public static Runnable addTask() {
        return new Runnable() {
            
            @Override
            public void run() {
                int num = Runtime.getRuntime().availableProcessors();
                for (int i = 0; i < num; i++) {
                    StringBuilder item = new StringBuilder("Item ").append(i);
                    cld.addFirst(item.toString());
                    callbackAdd(Thread.currentThread().getName(), item);
                }
                callbackFinish(Thread.currentThread().getName());
            }
        };
    }
    
    public static void callbackAdd(String threadName, StringBuilder item) {
        StringBuilder builder = new StringBuilder(threadName).append(" added :").append(item);
        System.out.println(builder);
    }
    
    public static void callbackFinish(String threadName) {
        StringBuilder builder = new StringBuilder(threadName).append(" has Finished");
        System.out.println(builder);
        System.out.println(new StringBuilder("CurrentSize ").append(cld.size()));
    }
}

프로그램의 출력 은 다음 과 같 습 니 다.

Thread 0 added :Item 0
Thread 0 added :Item 1
Thread 0 added :Item 2
Thread 0 added :Item 3
Thread 0 has Finished
CurrentSize 6
Thread 1 added :Item 0
Thread 2 added :Item 0
Thread 2 added :Item 1
Thread 2 added :Item 2
Thread 2 added :Item 3
Thread 1 added :Item 1
Thread 1 added :Item 2
Thread 2 has Finished
Thread 1 added :Item 3
Thread 1 has Finished
CurrentSize 13
CurrentSize 13
Thread 3 added :Item 0
Thread 3 added :Item 1
Thread 3 added :Item 2
Thread 3 added :Item 3
Thread 3 has Finished
CurrentSize 16

이 프로그램 은 다 중 스 레 드 와 대량의 요 소 를 공공 링크 에 추가 하 는 것 을 실현 했다. 바로 ConcurrentLinkedDeque 의 전형 적 인 사용 장면 이다.또한 위의 설 도 검증 했다. 즉 size() 방법 은 링크 를 옮 겨 다 니 며 잘못된 결 과 를 되 돌 릴 수 있다.

소스 코드 링크: Github - xiaolulwr (로 웨 이 용) / JUC - Demo.