자바 비 차단 알고리즘 Lock-free 의 실현 분석

막 히 지 않 는 창고
우 리 는 먼저 CAS 를 사용 하여 몇 개의 막 히 지 않 는 스 택 을 구축 합 니 다.스 택 은 가장 간단 한 체인 구조 로 그 본질은 링크 이 고 링크 의 뿌리 부분 은 바로 스 택 지붕 이다.
우 리 는 먼저 노드 데이터 구 조 를 구축 합 니 다.

public class Node<E> {
    public final E item;
    public Node<E> next;

    public Node(E item){
        this.item=item;
    }
}

이 노드 는 메모리 item 과 다음 노드 next 를 저장 합 니 다.
그 다음 에 저 희 는 차단 되 지 않 은 스 택 을 구축 합 니 다.이 스 택 에서 pop 과 push 방법 을 실현 해 야 합 니 다.저 희 는 Atomic 류 를 사용 하여 top 노드 의 인용 을 저장 하고 pop 과 push 전에 copare Andset 명령 을 호출 하여 명령 의 원자 성 을 확보 해 야 합 니 다.또한,우 리 는 라인 이 충돌 할 때 업 데 이 트 를 다시 시도 할 수 있 도록 끊 임 없 는 순환 이 필요 하 다.

public class ConcurrentStack<E> {

    AtomicReference<Node<E>> top= new AtomicReference<>();

    public void push(E item){
        Node<E> newNode= new Node<>(item);
        Node<E> oldNode;
        do{
            oldNode=top.get();
            newNode.next= oldNode;
        }while(!top.compareAndSet(oldNode, newNode));
    }

    public E pop(){
        Node<E> oldNode;
        Node<E> newNode;
        do {
            oldNode = top.get();
            if(oldNode == null){
                return null;
            }
            newNode=oldNode.next;
        }while(!top.compareAndSet(oldNode, newNode));
        return oldNode.item;
    }

}

비 차단 링크
체인 테이블 을 구축 하 는 것 은 창 고 를 구축 하 는 것 보다 복잡 하 다.우 리 는 머리 와 꼬리 두 개의 지침 을 유지 해 야 하기 때문이다.put 방법 으로 볼 때,우 리 는 두 단계 의 조작 을 실행 해 야 한다.1.끝 에 새로운 노드 를 삽입 해 야 한다.2.꼬리 포인 터 를 최신 노드 로 가 리 킵 니 다.
우리 가 CAS 를 사용 하 는 것 은 그 중의 한 단계 만 원자 집행 이 라 고 보장 할 수 있다.그렇다면 1 과 2 의 조합 절 차 는 어떻게 처리 해 야 할 까?
우 리 는 다시 자세히 고려 해 보 자.사실은 1 과 2 는 반드시 같은 라인 에서 실행 해 야 하 는 것 이 아니다.다른 라인 은 라인 이 노드 에 삽 입 된 것 을 검 측 했 지만 테 일 을 마지막 노드 로 가리 키 지 않 았 을 때 이 조작 을 완전히 도와 주 었 다.
우 리 는 구체 적 인 코드 실현 을 살 펴 보 자.

public class LinkedNode<E> {
    public final E item;
    public final AtomicReference<LinkedNode<E>> next;

    public LinkedNode(E item, LinkedNode<E> next){
        this.item=item;
        this.next=new AtomicReference<>(next);
    }
}

먼저 링크 드 노드 클래스 를 구축 합 니 다.

public class LinkedQueue<E> {
    private final LinkedNode<E> nullNode= new LinkedNode<>(null, null);
    private final AtomicReference<LinkedNode<E>> head= new AtomicReference<>(nullNode);
    private final AtomicReference<LinkedNode<E>> tail= new AtomicReference<>(nullNode);

    public boolean put(E item){
    LinkedNode<E> newNode = new LinkedNode<>(item, null);
    while (true){
        LinkedNode<E> currentTail= tail.get();
        LinkedNode<E> tailNext= currentTail.next.get();
        if(currentTail == tail.get()){
            if (tailNext != null) {
                //               ，      tail       
                tail.compareAndSet(currentTail, tailNext);
            }else{
                //           ，       ：1.      ，2. tail       
                if(currentTail.next.compareAndSet(null, newNode)){
                    tail.compareAndSet(currentTail, newNode);
                }
            }
        }
    }
    }
}

이상 은 자바 비 차단 알고리즘 Lock-free 의 실현 에 대한 상세 한 내용 을 분석 하 는 것 입 니 다.자바 비 차단 알고리즘 Lock-free 의 실현 에 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 십시오!