ABA 문제 의 본질 과 해결 방법 을 분석 하 다.

간단 한 소개
CAS 의 원 리 는 매우 간단 하 다.다 중 스 레 드 환경 에서 우리 의 업데이트 가 기대 에 부합 되 거나 한 스 레 드 가 특정한 대상 을 업데이트 할 때 다른 스 레 드 가 이 대상 을 수정 하지 않 는 다.스 레 드 가 대상(또는 값)을 업데이트 하기 전에 업데이트 전의 값 을 저장 한 다음 실제 업데이트 할 때 이전에 저 장 된 값 을 입력 하여 비교 하고 일치 하면 업데이트 합 니 다.그렇지 않 으 면 실패 합 니 다.
CAS 는 자바 에서 native 방법 으로 이 루어 졌 으 며 시스템 자체 가 제공 하 는 원자 적 조작 을 이용 하 였 습 니 다.
그렇다면 CAS 는 어떤 문제 가 있 을까요?일반적으로 CAS 가 완벽 하 게 디자인 되 지 않 으 면 ABA 문제 가 발생 할 수 있 고 ABA 문 제 는 두 가지 로 나 눌 수 있 으 므 로 우 리 는 먼저 한 가지 문 제 를 살 펴 보 자.
제1 류 문제
우 리 는 다음 의 ABA 상황 을 고려한다.
1.다 중 스 레 드 환경 에서 스 레 드 a 는 공 유 된 주소 X 에서 대상 A 를 읽 습 니 다.
2.온라인 프로 세 스 a 는 주소 X 를 업데이트 하기 전에 스 레 드 b 는 주소 X 의 값 을 B 로 수정 합 니 다.
3.이 어 스 레 드 b 는 주소 X 의 값 을 A 로 다시 수정 했다.
4.최신 스 레 드 a 는 주소 X 에 CAS 를 실행 하고 X 에 저 장 된 것 이 대상 A 인지,대상 이 일치 하 는 것 을 발견 하면 CAS 가 성공 합 니 다.
위의 예 에서 CAS 는 성 공 했 지만 실제로 이 CAS 는 원자 조작 이 아니 라 CAS 에 의존 하여 원자 조작 을 실현 하려 면 숨겨 진 bug 가 나타 날 수 있 습 니 다.
첫 번 째 문제 의 관건 은 2 와 3 두 걸음 이다.이 두 단 계 는 스 레 드 b 가 메모리 주소 X 의 내용 을 직접 바 꾸 는 것 을 볼 수 있 습 니 다.
자동 GC 환경 을 가 진 프로 그래 밍 언어,예 를 들 어 자바 에 서 는 2,3 의 경우 나타 날 수 없습니다.자바 에 서 는 두 대상 의 주소 가 일치 하면 이 두 대상 이 같다 는 것 을 나타 내기 때 문 입 니 다.
2,3,2 단계 에 나타 날 수 있 는 상황 은 C++와 같이 자동 GC 환경의 프로 그래 밍 언어 가 존재 하지 않 습 니 다.대상 의 생명 주 기 를 스스로 제어 할 수 있 기 때문에 만약 에 우리 가 하나의 list 에서 대상 을 삭제 한 다음 에 또 하나의 대상 을 재배 치 하고 add back 을 list 에 넣 으 면 MRU memory allocation 알고리즘 에 따 르 면 이 새로운 대상 은 이전에 삭 제 된 대상 의 메모리 주소 와 같 을 가능성 이 높다.이렇게 하면 ABA 문제 가 생 길 수 있 습 니 다.
두 번 째 문제
만약 우리 가 자동 GC 의 프로 그래 밍 언어 를 가지 고 있다 면,CAS 문제 가 여전히 존재 합 니까?
아래 의 상황 을 고려 하여 하나의 링크 안의 데 이 터 는 A->B->C 입 니 다.우 리 는 CAS 작업 을 수행 하여 A 를 D 로 교체 하여 링크 D->B->C 를 생 성 하고 싶 습 니 다.다음 절 차 를 고려 합 니 다.
1.스 레 드 a 는 링크 의 머리 부분 노드 A 를 읽 습 니 다.
2.스 레 드 b 는 링크 의 B 노드 를 삭제 하고 링크 는 A->C 로 변 한다.
3.스 레 드 a 는 CAS 작업 을 수행 하고 A 를 D 에서 교체 합 니 다.
마지막 으로 우리 가 도착 한 체인 시 계 는 D->C 이지 D->B->C 가 아니다.
문 제 는 어디 에 있 습 니까?CAS 가 비교 한 노드 A 와 최신 머리 노드 가 같은 노드 인지 노드 A 가 절차 1 과 3 사이 에 내용 이 변화 하 는 지 에 관심 이 없다.
우 리 는 예 를 들 자.

public void useABAReference(){
    CustUser a= new CustUser();
    CustUser b= new CustUser();
    CustUser c= new CustUser();
    AtomicReference<CustUser> atomicReference= new AtomicReference<>(a);
    log.info("{}",atomicReference.compareAndSet(a,b));
    log.info("{}",atomicReference.compareAndSet(b,a));
    a.setName("change for new name");
    log.info("{}",atomicReference.compareAndSet(a,c));
}

위의 예 에서 우 리 는 AtomicReference 의 CAS 방법 을 사용 하여 대상 의 변화 여 부 를 판단 했다.CAS b 와 a 후에 우 리 는 a 의 name 을 수정 했다.우 리 는 마지막 출력 결 과 를 보 았 다.
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
[main] INFO com.flydean.aba.ABAUsage - true
세 개의 CAS 결 과 는 모두 true 이다.CAS 가 확실히 비교 한 둘 이 통일 대상 인지 아 닌 지 를 설명 하 는 것 으로,그 내용 의 변화 에는 관심 이 없다.
두 번 째 문 제 는 일부 집합 류 의 조작 이 원자 적 인 것 이 아니 라 CAS 과정 에서 다른 노드 가 변 화 를 보 내 는 지 보장 할 수 없 기 때문이다.
제1 류 문제 의 해결
첫 번 째 문 제 는 자동 GC 가 존재 하 는 프로 그래 밍 언어 에 존재 하지 않 습 니 다.우 리 는 주로 C++와 같은 언어 에서 이 문 제 를 어떻게 해결 하 는 지 보 겠 습 니 다.
공식 적 인 견해 에 따 르 면 첫 번 째 문 제 는 대략 네 가지 해법 이 있다.
1.중간 노드 를 사용 합 니 다.-데이터 가 아 닌 중간 노드 를 사용 하여 일부 노드 가 삭 제 된 것 을 표시 합 니 다.
2.자동 GC 를 사용한다.
3.hazard pointers-hazard pointers 를 사용 하여 현재 스 레 드 가 접근 하고 있 는 노드 의 주 소 를 저장 합 니 다.이 hazard pointers 의 노드 는 수정 되 거나 삭제 할 수 없습니다.
4.read-copy update(RCU)를 사용 합 니 다.-업데이트 할 때마다 복사 본 을 만 들 고 매번 업데이트 할 때마다 복사 한 새로운 구조 입 니 다.
두 번 째 문제 의 해결
두 번 째 문 제 는 사실 전체 집합 대상 의 CAS 문제 라 고 할 수 있다.간단 한 해결책 은 CAS 업 데 이 트 를 할 때마다 버 전 번 호 를 추가 하 는 것 이다.버 전 번호 가 예상 한 버 전이 아니라면 집합 중의 일부 노드 를 업데이트 한 다른 스 레 드 가 있 음 을 설명 합 니 다.이번 CAS 는 실 패 했 습 니 다.
우 리 는 Atomic Stamped Reference 의 예 를 들 었 다.

public void useABAStampReference(){
    Object a= new Object();
    Object b= new Object();
    Object c= new Object();
    AtomicStampedReference<Object> atomicStampedReference= new AtomicStampedReference(a,0);
    log.info("{}",atomicStampedReference.compareAndSet(a,b,0,1));
    log.info("{}",atomicStampedReference.compareAndSet(b,a,1,2));
    log.info("{}",atomicStampedReference.compareAndSet(a,c,0,1));
}

Atomic Stamped Reference 의 compare AndSet 방법 은 두 개의 매개 변 수 를 더 했 습 니 다.각각 expected Stamp 와 new Stamp 입 니 다.두 개의 매개 변 수 는 모두 int 형 이 므 로 수 동 으로 전송 해 야 합 니 다.
총결산
ABA 문 제 는 사실 두 가지 문제 로 이 루어 져 있 기 때문에 우리 가 분리 해서 대처 하고 해결 해 야 한다.
이상 은 바로 ABA 문제 의 본질 과 해결 방법 을 분석 하 는 상세 한 내용 입 니 다.더 많은 ABA 문제 의 본질 과 해결 방법 에 관 한 자 료 는 우리 의 다른 관련 글 에 관심 을 가 져 주 십시오!