자바 비 차단 알고리즘 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 의 실현 에 관 한 자 료 는 우리 의 다른 관련 글 을 주목 하 십시오!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.