[F-Lab 모각코 챌린지 31일차] CAS 알고리즘

TIL

1. Compare And Swap
2. CAS 알고리즘은 check하고 act한다.
3. check then Act 연산은 Atomic이 보장 되어야 한다.
4. Blocking Threads는 비용이 비싸다.
5. CPU가 Atomic한 CAS 연산을 제공한다.
6. 자바에서의 CAS 알고리즘

 

---

 

Compare And Swap

• 동시성 알고리즘을 설계할 때, 사용되는 기술
• 현재 스레드가 갖고 있는 expected value와 메모리가 가지고 있는 variable을 비교하여 두 값이 동일하면 메모리의 variable 값을 new value로 교체한다. 그리고 true를 반환한다.
• 두 값이 다르면 new value가 반영되지 않고 false를 반환한 다음 재시도 한다.
• visibility 문제와 atomic 문제를 해결할 수 있다.

 

 

 

 

CAS 알고리즘은 check하고 act한다.

public class ProblematicLock {

    private volatile boolean locked = false;

    public void lock() {

        while(this.locked) {
            // busy wait - until this.locked == false
        }

        this.locked = true;
    }

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

}

lock() 메소드는 먼저 while 루프 내에서 locked 멤버변수의 값이 false인지 확인한다.

만약 locked 변수가 false라면, while 루프를 빠져나가고 locked 변수의 값을 true로 변경한다.

 

즉, lock() 메소드는 먼저 locked 변수의 값을 확인하고(check), 그 확인 결과에 따라서 동작한다.(act)
이를 Check, then act(확인 후 동작)라고 부른다.

 

만약 여러 스레드가 이 객체에 접근한다면 lock() 메소드는 제대로 동작하지 않을 수 있다.
스레드1이 locked 변수 값이 false라는 것을 확인하고 그 결과에 따라 while 루프를 빠져나가 남은 작업을 수행한다.
스레드1이 locked 값을 true로 변경하기 전, 스레드2가 locked 값을 확인하면 그 값이 false이기 때문에 스레드2 역시 while 루프를 빠져나가 남은 동작을 수행한다. 이러한 현상은 전형적인 race condition이다.

 

 

 

 

Check Then Act 연산은 Atomic이 보장 되어야 한다.

멀티 스레드 환경에서 race condition을 피하려면 check then act 연산은 atomic하게 실행되어야 한다.
여기서 atomic이란 변수의 값을 확인하고 확인 결과에 따라 동작하는 단계가 원자성 코드 블록으로 실행되는 것을 의미한다. 해당 코드 블록을 시작한 스레드는 다른 스레드의 간섭 없이 블록을 실행할 수 있다.
자바에서 코드 블록을 atomic하게 만드는 방법은 synchronized 키워드를 해당 블록에 선언해주는 것이다.

 

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;
    }

}

이제 lock() 메소드는 synchronized 키워드로 선언되어 있으므로 한 객체에서 한 번에 하나의 스레드만 실행할 수 있다.

 

 

 

 

Blocking Threads는 비용이 비싸다.

2개의 스레드가 동시에 synchronized 블록에 진입하려고 할 때, 두 스레드 중 하나는 block 되고 다른 스레드는 synchronized 블록에 진입할 수 있다. synchronized 블록에 진입한 스레드가 블록을 빠져나오면, 대기 중인 스레드가 블록에 진입할 수 있다.

 

그런데 block 됐던 스레드가 언제 unblock 되는지에 대한 보장이 없다. OS가 block 된 스레드의 unblock을 조정하는 역할을 하기 때문이다. 이로 인해 block 된 스레드는 공유 데이터 구조에 접근할 수 있는 시간이 낭비될 수 있다.

 

위 그림을 보면 스레드2가 먼저 synchronized 블록에 진입했고 스레드1은 차단 되어있다.
스레드2가 작업을 마치고 나왔음에도 불구하고 스레드1은 계속 차단 된 상태로 시간을 낭비하다 블록에 진입한다.

 

 

 

 

CPU가 Atomic한 CAS 연산을 제공한다.

• 요즘 CPU는 atomic compare and swap 연산을 내장해서 제공한다.
• compare and swap 작업은 synchronized 블록을 대체하는 데 사용할 수 있다.
• CPU는 CPU 코어 간에도 한 번에 하나의 스레드만 compare and swap 작업을 실행할 수 있도록 보장한다.
• OS가 스레드의 차단이나 차단 해제를 처리할 필요가 없다.
• 따라서 스레드가 compare and swap 작업을 실행하기 위해 대기하는 시간이 짧아져 정체가 줄어들고 처리량이 높아진다.

 

위 그림을 보면 공유 데이터에 접근하려는 스레드1은 완전히 block 되지 않는다. 스레드1은 계속 compare and swap 연산을 시도하면서 성공할 때까지 기다리고 스레드2가 작업을 완전히 끝냈을 때, 공유 데이터에 접근할 수 있는 허락을 얻는다. 전에 살펴봤던 그림과 비교해보면 스레드1이 공유 데이터에 접근하는 지연 시간이 줄어든게 보인다.

 

 

 

 

자바에서의 CAS 알고리즘

일부 atomic 클래스를 통해 CPU 수준에서 compard and swap 작업을 할 수 있다.

• AtomicBoolean
• AtomicInteger

compare and swap 연산을 사용해 중요한 섹션을 보호할 수 있다.
즉, 여러 스레드가 중요한 섹션을 동시에 실행하는 것을 방지할 수 있다.

 

 

public class Main {

    private static int count;
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger atomicCount = new AtomicInteger(0);

        // 스레드1
        new Thread(() -> {
            for (int i = 0; i < 100_000; i++) {
                count++;
                atomicCount.incrementAndGet();
            }
        }).start();

        // 스레드2
        new Thread(() -> {
            for (int i = 0; i < 100_000; i++) {
                count++;
                atomicCount.incrementAndGet();
            }
        }).start();

        Thread.sleep(5000);
        System.out.println("AtomicInteger 결과: " + atomicCount);
        System.out.println("int 결과: " + count);
    }
}

AtomicInteger 결과: 200000
int 결과: 180505

atomicCount는 예상했던대로 200_000이 출력되는 것을 볼 수 있고
int 타입인 count는 동기화가 지켜지지 않아 잘못된 값을 출력하는 것을 볼 수 있다.

 

 

public final int incrementAndGet() {
    return U.getAndAddInt(this, VALUE, 1) + 1;
}

@IntrinsicCandidate
public final int getAndAddInt(Object o, long offset, int delta) {
    int v;
    do {
        v = getIntVolatile(o, offset);
    } while (!weakCompareAndSetInt(o, offset, v, v + delta));
    return v;
}

AtomicInteger 클래스의 weakCompareAndSetInt() 메소드 내부를 살펴보면 CAS 알고리즘 로직을 구현한다.
weakCompareAndSetInt() 메소드는 '메모리에 저장된 변수 값'과 'expected value'를 비교해서 동일하면 'new value'를 메모리에 저장한다. 그리고 true를 리턴하며 while문을 빠져나온다.

 

 

 

 

📚 참고
https://jenkov.com/tutorials/java-concurrency/compare-and-swap.html#compare-and-swap-for-check-then-act-cases
https://velog.io/@eunsiver/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%94#cas-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%82%AC%EC%9A%A9-%EC%98%88