Compare and Swap

parkhr·2022년 4월 18일
0

Compare and Swap(CAS) 은 동시 알고리즘을 설계할 때 사용되는 기술입니다.

멀티 쓰레드 환경, 멀티 코어 환경에서 각 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을 수행합니다.


자바 5부터는 atomic 클래스를 통해 CPU 수준에서 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)) {
            // 성공할때까지 무한루프
        }
    }
}


출처

profile
기록만이 살길이다.

0개의 댓글