섹션 10. CAS - 동기화와 원자적 연산 (2)

[YONGHYNG]

CAS (Compare-And-Set) 연산 정리

1. 배경
   synchronized, ReentrantLock 같은 락 기반 동기화 방식은 직관적이지만 무겁다.

공유 변수 접근 시

1. 락 획득
2. 임계 영역 실행
3. 락 해제

이 과정이 반복되므로 연산이 많아질수록 비용이 커진다.

이를 개선하기 위해 락 없이 동기화를 수행하는 방법이 CAS 연산이다.
CAS는 원자적(atomic)으로 값을 비교하고 변경하는 기능이며, Java에서는 AtomicInteger 등이 이를 내부적으로 사용한다.

2. CAS 연산 예시

package thread.cas;

import java.util.concurrent.atomic.AtomicInteger;

public class CasMainV1 {

    public static void main(String[] args) {

        AtomicInteger atomicInteger = new AtomicInteger(0);
        System.out.println("start value = " + atomicInteger.get());

        boolean result1 = atomicInteger.compareAndSet(0, 1);
        System.out.println("result1 = " + result1 + ", value = " + atomicInteger.get());

        boolean result2 = atomicInteger.compareAndSet(0, 1);
        System.out.println("result2 = " + result2 + ", value = " + atomicInteger.get());
    }
}

실행결과

start value = 0
result1 = true, value = 1
result2 = false, value = 1

compareAndSet(expected, update)의 의미

• 현재 값이 expected와 동일하면 update 값으로 변경하고 true 반환
• 값이 일치하지 않으면 변경하지 않고 false 반환
• 이 연산 전체가 CPU 단위에서 원자적으로 실행됨

CAS가 빠른 이유

• 락처럼 대기 스레드를 블로킹하지 않는다
• CPU가 읽기 + 비교 + 변경을 하나의 명령어로 처리
• 업데이트 실패 시 락처럼 대기하지 않고 다시 시도하는 방식(스핀)

CAS 기반 incrementAndGet 직접 구현

AtomicInteger의 incrementAndGet() 내부 원리를 직접 구현해본 코드

package thread.cas;

import java.util.concurrent.atomic.AtomicInteger;
import static util.MyLogger.log;

public class CasMainV2 {

    public static void main(String[] args) {

        AtomicInteger atomicInteger = new AtomicInteger(0);
        System.out.println("start value = " + atomicInteger.get());

        int resultValue1 = incrementAndGet(atomicInteger);
        System.out.println("resultValue1 = " + resultValue1);

        int resultValue2 = incrementAndGet(atomicInteger);
        System.out.println("resultValue2 = " + resultValue2);
    }

    private static int incrementAndGet(AtomicInteger atomicInteger) {

        int getValue;
        boolean result;

        do {
            getValue = atomicInteger.get();
            log("getValue: " + getValue);

            result = atomicInteger.compareAndSet(getValue, getValue + 1);
            log("result: " + result);

        } while (!result);

        return getValue + 1;
    }
}

동작 설명

1. 현재 값 get
2. compareAndSet(현재값, 현재값+1) 시도
3. 성공하면 증가 완료
4. 실패하면 반복(do-while)하며 다시 시도

실행 결과 예시

start value = 0
getValue: 0
result: true
resultValue1 = 1
getValue: 1
result: true
resultValue2 = 2

핵심 정리

결론

• CAS는 락 없이 원자적 연산을 수행하는 기법
• CPU 명령 레벨에서 compare+swap을 원자적 연산으로 처리
• 실패 시 다시 반복하여 동시성 문제 해결
• Java에서는 AtomicInteger, incrementAndGet(), compareAndSet() 등에 활용됨
• 직접 사용할 일은 많지 않지만 Atomic 계열 동시성 라이브러리의 기반 원리를 이해하게 된다.

CAS 연산3

멀티스레드를 사용해서 중간에 다른 스레드가 먼저 값을 증가시켜 버리는 경우를 알아보자. 그리고 CAS 연산이 실패하는 경우에 어떻게 되는지 알아보자. 이 경우에도 값을 정상적으로 증가시킬 수 있을까?

package thread.cas;
import java.util.ArrayList;
import java.util.List;
import java.util.concurrent.atomic.AtomicInteger;
import static util.MyLogger.log;
import static util.ThreadUtils.sleep;
public class CasMainV3 {
    private static final int THREAD_COUNT = 2;
    public static void main(String[] args) throws InterruptedException {
        AtomicInteger atomicInteger = new AtomicInteger(0);
        System.out.println("start value = " + atomicInteger.get());
        Runnable runnable = new Runnable() {
            @Override
            public void run() {
                incrementAndGet(atomicInteger);
            }
        };
        List<Thread> threads = new ArrayList<>();
        for (int i = 0; i < THREAD_COUNT; i++) {
            Thread thread = new Thread(runnable);
            threads.add(thread);
            thread.start();
        }
        for (Thread thread : threads) {
            thread.join();
        }
        int result = atomicInteger.get();
        System.out.println(atomicInteger.getClass().getSimpleName() + "resultValue: " + result);
    }
    private static int incrementAndGet(AtomicInteger atomicInteger) {
        int getValue;
        boolean result;
        do {
            getValue = atomicInteger.get();
            sleep(100); // 스레드 동시 실행을 위한 대기
            log("getValue: " + getValue);
            result = atomicInteger.compareAndSet(getValue, getValue + 1);
            log("result: " + result);
        } while (!result);
        return getValue + 1;
    }
}

• 2개의 스레드가 incrementAndGet() 를 호출해서 AtomicInteger 내부의 value 값을 동시에 하나씩 증가시킨다.
• 이때 두 스레드는 incrementAndGet() 메서드를 함께 호출한다. 여기서 스레드가 동시에 같은 값을 읽고
  CAS를 수행하는 상황을 쉽게 만들기위해 중간에 sleep() 코드를 추가했다.

실행 결과

start value = 0
18:13:37.623 [ Thread-1] getValue: 0
18:13:37.623 [ Thread-0] getValue: 0
18:13:37.625 [ Thread-1] result: true
18:13:37.625 [ Thread-0] result: false
18:13:37.731 [ Thread-0] getValue: 1
18:13:37.731 [ Thread-0] result: true
AtomicInteger resultValue: 2

Thread-1 실행

18:13:37.623 [ Thread-1] getValue: 0
18:13:37.625 [ Thread-1] result: true

• atomicInteger.get() 을 사용해서 value 값을 읽는다. getValue 는 0이다.
• compareAndSet(0,1) 을 수행한다.
  • compareAndSet(getValue, getValue + 1)
• CAS 연산이 성공했으므로 value 값은 0에서 1로 증가하고 true 를 반환한다.
• do~while 문을 빠져나간다.

Thread-0 실행

//[Thread-0] do~while 첫 번째 시도
18:13:37.623 [ Thread-0] getValue: 0
18:13:37.625 [ Thread-0] result: false

//[Thread-0] do~while 두 번째 시도
18:13:37.731 [ Thread-0] getValue: 1
18:13:37.731 [ Thread-0] result: true

[Thread-0] do~while 첫 번째 시도

• atomicInteger.get() 을 사용해서 value 값을 읽는다. getValue 는 0이다.
• compareAndSet(0,1) 을 수행한다.
  • compareAndSet(getValue, getValue + 1)
• 그런데 compareAndSet(0,1) 연산은 실패한다.
  • CAS 연산에서 현재 value 값으로 0을 기대했지만 Thread-1 이 중간에 먼저 실행되면서 value 의 값을 0 1로 변경해버렸다.
• CAS 연산이 실패했으므로 value 값은 변경하지 않고, false 를 반환한다.
• 실패했으므로 dowhile 문을 빠져나가지 못한다. dowhile 문을 다시 시작한다.
  • while (!result) while(!false) while(true) 이므로 다시 반복

[Thread-0] do~while 두 번째 시도

• do~while 문이 다시 시작된다.
• atomicInteger.get() 을 사용해서 value 값을 읽는다. getValue 는 1이다.
• compareAndSet(1,2) 을 수행한다.
  • compareAndSet(getValue, getValue + 1)
• CAS 연산이 성공했으므로 value 값은 1에서 2로 증가하고 true 를 반환한다.
• do~while 문을 빠져나간다.

정리

AtomicInteger 가 제공하는 incrementAndGet() 코드도 앞서 우리가 직접 작성한 incrementAndGet() 코드와 똑같이 CAS를 활용하도록 작성되어 있다. CAS를 사용하면 락을 사용하지 않지만, 대신에 다른 스레드가 값을 먼저 증가해서 문제가 발생하는 경우 루프를 돌며 재시도를 하는 방식을 사용한다.

이 방식은 다음과 같이 동작한다

1. 현재 변수의 값을 읽어온다.
2. 변수의 값을 1 증가시킬 때, 원래 값이 같은지 확인한다. (CAS 연산 사용)
3. 동일하다면 증가된 값을 변수에 저장하고 종료한다.
4. 동일하지 않다면 다른 스레드가 값을 중간에 변경한 것이므로, 다시 처음으로 돌아가 위 과정을 반복한다.

두 스레드가 동시에 실행되면서 문제가 발생하는 상황을 스레드가 충돌했다고 표현한다.
이 과정에서 충돌이 발생할 때마다 반복해서 다시 시도하므로, 결과적으로 락 없이 데이터를 안전하게 변경할 수 있다.

CAS를 사용하는 방식은 충돌이 드물게 발생하는 환경에서는 락을 사용하지 않으므로 높은 성능을 발휘할 수 있다. 이는 락을 사용하는 방식과 비교했을 때, 스레드가 락을 획득하기 위해 대기하지 않기 때문에 대기 시간과 오버헤드가 줄어드는 장점이 있다.

그러나 충돌이 빈번하게 발생하는 환경에서는 성능에 문제가 될 수 있다. 여러 스레드가 자주 동시에 동일한 변수의 값을 변경하려고 시도할 때, CAS는 자주 실패하고 재시도해야 하므로 성능 저하가 발생할 수 있다. 이런 상황에서는 반복문을 계속 돌기 때문에 CPU 자원을 많이 소모하게 된다.

CAS(Compare-And-Swap)와 락(Lock) 방식의 비교락(Lock) 방식

• 비관적(pessimistic) 접근법
• 데이터에 접근하기 전에 항상 락을 획득
• 다른 스레드의 접근을 막음
• "다른 스레드가 방해할 것이다"라고 가정

CAS(Compare-And-Swap) 방식

• 낙관적(optimistic) 접근법
• 락을 사용하지 않고 데이터에 바로 접근
• 충돌이 발생하면 그때 재시도
• "대부분의 경우 충돌이 없을 것이다"라고 가정

정리하면 충돌이 많이 없는 경우에 CAS 연산이 빠른 것을 확인할 수 있다. 그럼 충돌이 많이 발생하지 않는 연산은 어떤 것이 있을까? 언제 CAS 연산을 사용하면 좋을까? 사실 간단한 CPU 연산은 너무 빨리 처리되기 때문에 충돌이 자주 발생하지 않는다. 충돌이 발생하기도 전에 이미 연산을 완료하는 경우가 더 많다.

앞서 여러 스레드가 value++ 연산을 수행했던 BasicInteger , VolatileInteger 의 예를 보자.

실행 결과

BasicInteger result: 950
VolatileInteger result: 961
SyncInteger result: 1000
MyAtomicInteger result: 1000

이 경우 최대한 많이 충돌하게 만들기 위해 1000개의 스레드를 동시에 쉬게 만든 다음에 동시에 실행했다.

sleep(10); //너무 빨리 실행되기 때문에, 다른 스레드와 동시 실행을 위해 잠깐 쉬었다가 실행
incrementInteger.increment();

BasicInteger 의 실행 결과를 보면 최대한 스레드를 충돌하게 만들었는데도, 1000개 중에 약 50개의 스레드만 충돌한 사실을 확인할 수 있다.

락 방식

• 스레드 충돌을 방지하기 위해 1000개의 스레드가 모두 락을 획득하고 반환하는 과정을 거친다.
• 락을 사용하기 때문에 1000개의 스레드는 순서대로 하나씩 수행된다.
• 사실 이 중에 스레드가 충돌하는 경우는 50개의 경우 뿐이다.

CAS 방식

• 1000개의 스레드를 모두 한 번에 실행한다.
• 그리고 충돌이 나는 50개의 경우만 재시도 한다.

이 예제는 억지로 충돌을 만들기 위해서 sleep(10) 을 넣었다. 만약 이 코드를 제거한다면 충돌 가능성은 100개 중에 1개도 안될 것이다.

정리하면 간단한 CPU 연산에는 락 보다는 CAS를 사용하는 것이 효과적이다.

CAS 락 구현1

CAS는 단순한 연산 뿐만 아니라, 락을 구현하는데 사용할 수도 있다. synchronized , Lock(ReentrantLock) 없이 CAS를 활용해서 락을 구현해보자. 먼저 CAS의 필요성을 이해하기 위해 CAS 없이 직접 락을 구현해보자.

package thread.cas.spinlock;

import static util.MyLogger.log;
import static util.ThreadUtils.sleep;

public class SpinLockBad {

    private volatile boolean lock = false;

    public void lock() {
        log("락 획득 시도");
        while(true) {
            if(!lock) {
                sleep(100);
                lock = true;
                break;
            } else {
                log("락 획득 싪패 - 스핀 대기");
            }
        }

        log("락 획득 완료");
    }

    public void unlock() {
        lock = false;
        log("락 반납 완료");
    }
}

구현의 원리는 매우 단순하다.

• 스레드가 락을 획득하면 lock 의 값이 true 가 된다.
• 스레드가 락을 반납하면 lock 의 값이 false 가 된다.
• 스레드가 락을 획득하면 while문을 탈출한다.
• 스레드가 락을 획득하지 못하면 락을 획득할 때 까지 while문을 계속 반복 실행한다.

package thread.cas.spinlock;

import static util.MyLogger.log;
import static util.ThreadUtils.sleep;

public class SpinLockMain {

    public static void main(String[] args) {
        SpinLockBad spinLock = new SpinLockBad();
        //SpinLock spinLock = new SpinLock();

        Runnable task = new Runnable() {
            @Override
            public void run() {
                spinLock.lock();
                try {
                    // critical section
                    log("비즈니스 로직 실행");
                    sleep(1); // 오래 걸리는 로직에서 스핀 락 사용X
                } finally {
                    spinLock.unlock();
                }
            }
        };

        Thread t1 = new Thread(task, "Thread-1");
        Thread t2 = new Thread(task, "Thread-2");

        t1.start();
        t2.start();

    }
}

실행 결과

09:58:35.387 [ Thread-1] 락 획득 시도
09:58:35.387 [ Thread-2] 락 획득 시도
09:58:35.388 [ Thread-1] 락 획득 완료
09:58:35.389 [ Thread-2] 락 획득 완료
09:58:35.389 [ Thread-1] 비즈니스 로직 실행
09:58:35.389 [ Thread-2] 비즈니스 로직 실행
09:58:35.389 [ Thread-1] 락 반납 완료
09:58:35.389 [ Thread-2] 락 반납 완료

실행 결과를 보면 기대와는 다르게 Thread-1 , Thread-2 둘다 동시에 락을 획득하고 비즈니스 로직을 동시에 수행해버린다. 이제는 왜 이런 문제가 발생하는지 이제는 쉽게 이해할 수 있을 것이다. 스레드 둘이 동시에 수행되기 때문에 문제가 발생했다. 실행 결과를 분석해보자.

ublic void lock() {
    log("락 획득 시도");
    while(true) {
        if (!lock) { // 1. 락 사용 여부 확인
            sleep(100); // 문제 상황 확인용, 스레드 대기
            lock = true; // 2. 락의 값 변경
            break; // while 탈출
        } else {
            // 락을 획득할 때 까지 스핀 대기(바쁜 대기) 한다.
            log("락 획득 실패 - 스핀 대기");
        }
    }
    log("락 획득 완료");
}

실행 결과 분석

lock 의 초기값은 false 이다.
Thread-1 과 Thread-2 는 동시에 실행된다.

• Thread-1 : lock() 을 호출해서 락 획득을 시도한다.

• Thread-2 : lock() 을 호출해서 락 획득을 시도한다.

• Thread-1 : if (!lock) 에서 락의 사용 여부를 확인한다. lock 의 값이 false 이다.

  • if (!lock) if (!false) if (true) 이므로 if 문을 통과한다.

• Thread-2 : if (!lock) 에서 락의 사용 여부를 확인한다. lock 의 값이 false 이다.

  • if (!lock) if (!false) if (true) 이므로 if 문을 통과한다.

• Thread-1 : lock = true; 를 호출해서 락의 값을 변경한다.

  • 이 시점에 lock 은 false true 가 된다.

• Thread-2 : lock = true; 를 호출해서 락의 값을 변경한다.

  • 이 시점에 lock 은 true true 가 된다.

• Thread-1 , Thread-2 둘다 break; 를 통해 while문을 탈출한다.

• Thread-1 , Thread-2 둘다 락 획득을 완료하고, 비즈니스 로직을 수행한 다음에 락을 반납한다.

여기서 어떤 부분이 문제일까?
바로 다음 두 부분이 원자적이지 않다는 문제가 있다.

• 1. 락 사용 여부 확인
• 2. 락의 값 변경

이 둘은 한 번에 하나의 스레드만 실행해야 한다. 따라서 synchronized 또는 Lock 을 사용해서 두 코드를 동기화해서 안전한 임계 영역을 만들어야 한다.

여기서 다른 해결 방안도 있다. 바로 두 코드를 하나로 묶어서 원자적으로 처리하는 것이다. CAS 연산을 사용하면 두 연산을 하나로 묶어서 하나의 원자적인 연산으로 처리할 수 있다. 락의 사용 여부를 확인하고, 그 값이 기대하는 값과 같다면 변경하는 것이다. 이것은 CAS 연산에 딱 들어 맞는다!

참고로 락을 반납하는 다음 연산은 연산이 하나인 원자적인 연산이다. 따라서 이 부분은 여러 스레드가 함께 실행해도 문제가 발생하지 않는다.

public void unlock() {
      lock = false;
      log("락 반납 완료 ")
}

CAS 락 구현2

package thread.cas.spinlock;

import java.util.concurrent.atomic.AtomicBoolean;

import static util.MyLogger.log;
import static util.ThreadUtils.sleep;

public class SpinLock {

    private final AtomicBoolean lock = new AtomicBoolean(false);

    public void lock() {
        log("락 획득 시도");
        while(!lock.compareAndSet(false, true)) {
            log("락 획득 실패 - 스핀 대기");
        }
        log("락 획득 완료");
    }

    public void unlock() {
        lock.set(false);
        log("락 반납 완료");
    }
}

• CAS 연산을 지원하는 AtomicBoolean을 사용했다.

구현 원리는 단순하다.

• 스레드가 락을 획득하면 lock 의 값이 true 가 된다.
• 스레드가 락을 반납하면 lock 의 값이 false 가 된다.
• 스레드가 락을 획득하면 while문을 탈출한다.
• 스레드가 락을 획득하지 못하면 락을 획득할 때 까지 while문을 계속 반복 실행한다.

락을 획득할 때 매우 중요한 부분이 있다. 바로 다음 두 연산을 하나로 만들어야 한다는 점이다.

• 1. 락 사용 여부 확인
• 2. 락의 값 변경

락을 획득하기 위해 먼저 락의 사용 여부를 확인했을 때 lock 의 현재 값이 반드시 false 여야 한다. true 는 이미다른 스레드가 락을 획득했다는 뜻이다. 따라서 이 값이 false 일 때만 락의 값을 변경할 수 있다.

락의 값이 false 인 것을 확인한 시점부터 lock 의 값을 true 로 변경할 때 까지 lock 의 값은 반드시 false 를
유지해야 한다.

중간에 다른 스레드가 lock 의 값을 true 로 변경하면 안된다. 그러면 여러 스레드가 임계 영역을 통과하는 동시성 문제가 발생한다.

CAS 연산은 이 두 연산을 하나의 원자적인 연산으로 만들어준다.
lock.compareAndSet(false, true)

• 1. 락 사용 여부 확인: lock 의 값이 false 이면
• 2. 락의 값 변경: lock 의 값을 true 로 변경해라.

실행 결과 분석

lock 의 초기값은 false 이다.

• Thread-1 : lock() 을 호출해서 락 획득을 시도한다.
• Thread-2 : lock() 을 호출해서 락 획득을 시도한다.
• Thread-1 : while (!lock.compareAndSet(false, true)) 를 사용해서 락의 사용 여부를 확인하면서 변경을 시도한다.
  • lock.compareAndSet(false, true)
    • CAS 연산을 사용했다. lock 이 false 면 lock 의 값을 true 로 변경한다.
    • lock 의 값이 false 이므로 true 로 변경한다. 변경에 성공했기 때문에 true 를 반환한다.
  • while (!true) while(false) 가 되므로 while문을 빠져나온다.
  • 락 획득을 완료한다.
• Thread-2 : while (!lock.compareAndSet(false, true)) 를 사용해서 락의 사용 여부를 확인하면서 변경을 시도한다.
  • lock.compareAndSet(false, true)
    • CAS 연산을 사용했다. lock 이 false 면 lock 의 값을 true 로 변경한다.
    • lock 의 값이 true 이므로 값을 변경할 수 없다. 변경에 실패했기 때문에 false 를 반환한다.
  • while (!false) while(true) 가 되므로 while문을 시작한다.
  • 락 획득에 실패하고, 락을 획득할 때 까지 while문을 반복한다.
    • 락 획득 실패 - 스핀 대기 로그가 반복해서 남는다.
• Thread-1 : 비즈니스 로직을 수행하고 lock.set(false) 을 수행해서 락을 반납한다.
• Thread-2 : 락을 획득하고 while문을 탈출한다. 비즈니스 로직을 수행한 다음에 락을 반납한다.

CAS 방식의 단점과 스핀락 이해

CAS(compare-and-set)는 락을 사용하지 않고 값을 변경하려고 시도하는 방식이다. 하지만 변경에 실패하면 while문으로 계속 재시도하며 락을 얻을 때까지 CPU를 쉬지 않고 사용한다.

• synchronized 같은 락 기반 방식
  → 다른 스레드는 BLOCKED / WAITING 상태로 잠시 멈춤
  → CPU를 거의 쓰지 않음
  → 락이 풀리면 다시 실행

• CAS(스핀 방식)
  → 락이 없는 대신 성공할 때까지 계속 반복(check → 비교 → 실패 → 재시도)
  → 스레드는 계속 RUNNABLE 상태이며 CPU를 계속 소비

즉, CAS는 중간에 잠깐만 기다리면 될 때 효율적이며, 기다리는 시간이 긴 상황에서는 오히려 CPU 낭비가 심할 수 있다.

CAS(스핀락)을 쓰면 좋을 때

• 연산이 매우 짧게 끝날 때
  예) 숫자 증가, 자료구조 push/pop 같은 극히 작은 연산

• 오래 걸리는 작업에는 비효율적
  예) DB 조회, 네트워크 요청 처리
  → CPU가 100% 쓰이며 계속 기다리기 때문