CAS

CAS (Compare And Swap) Algorithms

정의

컴퓨터 과학에서 CAS(Compare-and-Swap)는 동기화를 달성하기 위해 멀티스레딩에 사용되는 원자적 명령입니다. 메모리 위치의 내용을 주어진 값과 비교하고 동일한 경우에만 해당 메모리 위치의 내용을 새로운 주어진 값으로 수정합니다. 이것은 단일 원자 연산으로 수행됩니다. 원자성은 최신 정보를 기반으로 새 값이 계산되도록 보장합니다. 그 동안 다른 스레드에 의해 값이 업데이트된 경우 쓰기가 실패합니다. 연산 결과는 대체를 수행했는지 여부를 나타내야 합니다. 이것은 간단한 부울로 수행 할 수 있습니다. 응답(이 변형은 종종 비교 및 설정 이라고 함 ) 또는 메모리 위치에서 읽은 값(기록된 값이 아님)을 반환합니다.

from wiki

멀티 쓰레드 환경, 멀티 코어 환경에서 각 CPU는 메인 메모리에서 변수값을 참조하는게 아닌, 각 CPU의 캐시 영역에서 메모리를 값을 참조하게 됩니다.

이때, 메인 메모리에 저장된 값과 CPU 캐시에 저장된 값이 다른 경우가 있습니다. (이를 가시성 문제라고 합니다.)

그래서 사용되는 것이 CAS 알고리즘입니다. 현재 쓰레드에 저장된 값과 메인 메모리에 저장된 값을 비교하여 일치하는 경우 새로운 값으로 교체하고, 일치 하지 않는 다면 실패하고 재시도를 합니다.

이렇게 처리되면 CPU캐시에서 잘못된 값을 참조하는 가시성 문제가 해결됩니다.

적용

두 개의 스레드가 동시에 Java의 synchronized block에 들어가려고 하면 하나는 synchronized block에 들어갈 수 있고, 하나는 block 됩니다. 이 때, 스레드를 block 하는데 비용이 많이 듭니다.

public class ProblematicLock {
    private volatile boolean locked = false;
    public synchronized void lock() {
        while(this.locked) {
            // busy wait - until this.locked == false
        }

        this.locked = true;
    }

    public void unlock() {
        this.locked = false;
    }
}

또한 block 된 스레드가 언제 block 해제되는지 정확하게 보장하지 않습니다. 이는 block 해제를 조정하는 OS 또는 운영체제에 따라 다릅니다. 아래 그림과 같이 일정 시간 낭비될 수가 있습니다.

Compare and Swap 알고리즘을 사용하면 sychronized block을 대체하고, 비용이 많이 드는 문제를 해결할 수 있습니다. CPU가 한번에 하나의 스레드만 Compare and Swap 하도록 보증합니다. 그러므로 스레드를 차단하거나 해제하는 작업을 처리할 필요가 없습니다.

따라서 스레드가 실행 대기하는 시간이 단축됩니다. 아래 그림 처럼 접근 가능할때까지 Compare and Swap을 수행합니다.

비용이 많이 드는 Synchronized block이 아닌 Atomic 클래스를 이용하여, Compare and swap를 구현할 수 있습니다.

public class CompareAndSwapLock {
    private AtomicBoolean locked = new AtomicBoolean(false);
    
    public void unlock() {
        this.locked.set(false);
    }

    public void lock() {
        while(!this.locked.compareAndSet(false, true)) {
            // 성공할때까지 무한루프
        }
    }
}

참고 자료: kongkong2님의 velog