잠 금 알고리즘 없 음 - CAS 원리

1. 잠 금 없 는 알고리즘
CAS (비교 와 교환, Compare and swap) 는 유명한 잠 금 없 는 알고리즘 이다.잠 금 프로 그래 밍, 즉 잠 금 을 사용 하지 않 은 상태 에서 다 중 스 레 드 간 의 변 수 를 동기 화 하 는 것 입 니 다. 즉, 스 레 드 가 막 히 지 않 은 상태 에서 변 수 를 동기 화 하 는 것 이기 때문에 비 차단 동기 화 (Non - blocking Synchronization) 라 고도 합 니 다.비 차단 동기 화 를 실현 하 는 방안 을 '잠 금 없 는 프로 그래 밍 알고리즘' (Non - blocking algorithm) 이 라 고 합 니 다.이에 대응 하여 독점 자 물 쇠 는 비관 적 인 자물쇠 이다. synchronized 는 독점 자물쇠 이다. 최 악의 상황 을 가정 하고 다른 스 레 드 가 방 해 를 받 지 않도록 하 는 상황 에서 만 실행 하면 다른 모든 자물쇠 가 필요 한 스 레 드 가 걸 리 고 자 물 쇠 를 가 진 스 레 드 가 자 물 쇠 를 풀 때 까지 기다 릴 수 있다.lock 을 사용 하여 스 레 드 동기 화 를 실현 하 는 데 많은 단점 이 있 습 니 다. * 경쟁 이 발생 할 때 스 레 드 가 막 혀 서 기다 리 고 스 레 드 가 실시 간 으로 응답 할 수 없습니다. *dead lock, 자물쇠. *live lock。 * 우선 순위 반전.부적 절 한 사용 으로 성능 이 떨 어 졌 다.물론 일부 상황 에서 현재 로 서 는 잠 금 없 는 프로 그래 밍 이 lock 을 대체 할 수 없다.
2. 실현 등급
비동기 차단 의 실현 은 세 단계 로 나 눌 수 있 습 니 다. wait - free / lock - free / obstruction - free.wait - free 는 가장 이상 적 인 모델 로 전체 작업 은 모든 스 레 드 가 유한 한 절차 에서 완성 되도록 보장 합 니 다.시스템 급 삼투 (system - wide throughput) 및 스 레 드 없 는 배 고 픔 을 보증 합 니 다.2011 년 까지 구체 적 인 실현 은 별로 없 었 다.실현 되 더 라 도 구체 적 인 CPU 에 의존 해 야 한다.lock - free 는 개별 스 레 드 의 배 고 픔 을 허용 하지만 시스템 급 의 삼투 를 보장 합 니 다.최소한 하나의 스 레 드 가 계속 실 행 될 수 있 도록 확보 하 세 요.wait - free 의 알고리즘 도 lock - free 일 것 입 니 다.obstruction - free 는 모든 시간 에 하나의 스 레 드 가 하나의 업무 로 격 리 되 어 실 행 됩 니 다 (다른 스 레 드 suspended). 그리고 제 한 된 절차 에서 완 료 됩 니 다.실행 과정 에서 데이터 가 수정 되 는 것 을 발견 하면 스크롤 백 합 니 다.낙관 자물쇠, 즉 낙관 병행 통제 (OOC) 라 고도 한다.트 랜 잭 션 의 과정 은: 1 읽 기 및 시간 스탬프 쓰기;2. 쓰기 준비, 버 전 검사;3. 검증 이 통과 되면 기록 하고 검증 이 통과 되 지 않 으 면 스크롤 백 합 니 다.lock - free 는 반드시 obstruction - free 입 니 다.
3. CAS 알고리즘
CAS (비교 와 교환, Compare and swap) 는 유명한 잠 금 없 는 알고리즘 이다.CAS, CPU 명령 은 IA 32, Space 를 포함 한 대부분의 프로세서 구조 에서 CAS 명령 을 사용 합 니 다. CAS 의 의 미 는 "V 의 값 이 A 여야 한다 고 생각 합 니 다. 만약 그렇다면 V 의 값 을 B 로 업데이트 해 야 합 니 다. 그렇지 않 으 면 V 의 값 이 실제 얼마 인지 수정 하지 않 고 알려 주지 않 습 니 다" 입 니 다. CAS 는 낙관적 인 잠 금 기술 로 여러 스 레 드 가 CAS 를 사용 하여 같은 변 수 를 동시에 업데이트 하려 고 시도 할 때그 중의 한 스 레 드 만 변수의 값 을 업데이트 할 수 있 고 다른 스 레 드 는 모두 실 패 했 습 니 다. 실패 한 스 레 드 는 걸 리 지 않 고 이번 경쟁 에서 실 패 했 음 을 알 리 고 다시 시도 할 수 있 습 니 다.CAS 는 3 개의 조작 수, 메모리 값 V, 오래된 예상 치 A, 수정 할 새 값 B 가 있 습 니 다.예상 치 A 와 메모리 V 만 동시에 메모리 V 를 B 로 변경 하지 않 으 면 아무것도 하지 않 습 니 다.java. util. concurrent. atomic 의 AtomicXXX 는 모두 이러한 밑바닥 의 JVM 을 사용 하여 디지털 유형의 인용 유형 에 효율 적 인 CAS 조작 을 지원 합 니 다. java. util. concurrent 의 대부분 종 류 는 실현 할 때 직접적 이거 나 간접 적 으로 이러한 원자 변 수 를 사 용 했 습 니 다. 이러한 원자 변 수 는 sun. misc. Unsafe 라 이브 러 리 의 CAS 알고리즘 을 호출 했 습 니 다.CPU 명령 으로 잠 금 없 는 자동 증 가 를 실현 합 니 다. JDK 소스 코드:

public final int getAndIncrement() {  
        for (;;) {  
            int current = get();  
            int next = current + 1;  
            if (compareAndSet(current, next))  
                return current;  
        }  
}  

public final boolean compareAndSet(int expect, int update) {  
    return unsafe.compareAndSwapInt(this, valueOffset, expect, update);  
}

따라서 대부분의 경우 자바 에 서 는 Atomic 패키지 의 increment AndGet 을 사용 하 는 성능 이 synchronized 를 사용 하 는 것 보다 몇 배 높다.
질문
thread 1 은 val = 1 을 2, cas (val, 1, 2) 로 조작 하려 고 합 니 다.thread 1 먼저 val = 1 읽 기;thread 1 이 선점 (preempted) 되 어 thread 2 를 실행 합 니 다.thread 2 수정 val = 3, 다시 1.thread 1 을 계속 실행 하면 기대 치 는 '원래 값' (사실은 수정 되 었 습 니 다) 과 같 고 CAS 작업 을 완성 할 수 있 습 니 다.CAS 를 사용 하면 ABA 문제 가 발생 할 수 있 으 며, 특히 포인터 로 일부 병렬 데이터 구 조 를 조작 할 때.솔 루 션 ABAʹ：수정 여 부 를 표시 하기 위해 추가 표 시 를 추가 합 니 다.자바 1.5 부터 JDK 의 atomic 패키지 에는 Atomic Stamped Reference 가 제공 되 어 ABA 문 제 를 해결 합 니 다.이 클래스 의 compare Andset 방법 은 현재 인용 이 예상 인용 과 같 는 지, 현재 로고 가 예상 표지 와 같 는 지, 모두 같 으 면 원자 방식 으로 이 인용 과 이 로고 의 값 을 주어진 업데이트 값 으로 설정 하 는 것 입 니 다.