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

[seyeop03]

0x02. CAS 연산

2.1. CAS 연산1

참고: CAS 연산은 심화 내용이다. 이해가 어렵다면 가볍게 듣고 넘어가도 괜찮다. 왜냐하면 우리가 직접 CAS 연산을 사용하는 경우는 거의 없기 때문이다. 대부분 복잡한 동시성 라이브러리들이 CAS 연산을 사용한다. 우리는 AtomicInteger와 같은 CAS 연산을 사용하는 라이브러리들을 잘 사용하는 정도면 충분하다.

(1) 락 기반 방식의 문제점

SyncInteger 와 같은 클래스는 데이터를 보호하기 위해 락을 사용한다.
여기서 말하는 락은 synchronized , Lock(ReentrantLock) 등을 사용하는 것을 말한다.
락은 특정 자원을 보호하기 위해 스레드가 해당 자원에 대한 접근하는 것을 제한한다. 락이 걸려 있는 동안 다른 스레드들은 해당 자원에 접근할 수 없고, 락이 해제될 때까지 대기해야 한다.
또한 락 기반 접근에서는 락을 획득하고 해제하는 데 시간이 소요된다.

예를 들어서 락을 사용하는 연산이 있다고 가정하자. 락을 사용하는 방식은 다음과 같이 작동한다.

1. 락이 있는지 확인한다.
2. 락을 획득하고 임계 영역에 들어간다.
3. 작업을 수행한다.
4. 락을 반납한다.

여기서 락을 획득하고 반납하는 과정이 계속 반복된다. 10000번의 연산이 있다면 10000번의 연산 모두 같은 과정을 반복한다.

이렇듯 락을 사용하는 방식은 직관적이지만 상대적으로 무거운 방식이다.

(2) CAS

이런 문제를 해결하기 위해 락을 걸지 않고 원자적인 연산을 수행할 수 있는 방법이 있는데, 이것을 CAS(Compare-And-Swap, Compare-And-Set) 연산이라 한다. 이 방법은 락을 사용하지 않기 때문에 락 프리(lock-free) 기법이라 한다. 참고로 CAS 연산은 락을 완전히 대체하는 것은 아니고, 작은 단위의 일부 영역에 적용할 수 있다. 기본은 락을 사용하고, 특별한 경우에 CAS를 적용할 수 있다고 생각하면 된다.

지금부터 코드를 통해 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());
    }
}

• new AtomicInteger(0) : 내부에 있는 기본 숫자 값을 0 으로 설정한다.
• 자바는 AtomicXxx 의 compareAndSet() 메서드를 통해 CAS 연산을 지원한다.

실행 결과

compareAndSet(0, 1)

atomicInteger가 가지고 있는 값이 현재 0이면 이 값을 1로 변경하라는 매우 단순한 메서드이다.

• 만약 atomicInteger의 값이 현재 0이라면 atomicInteger의 값은 1로 변경된다. 이 경우 true를 반환한다.
• 만약 atomicInteger의 값이 현재 0이 아니라면 atomicInteger의 값은 변경되지 않는다. 이 경우 false를 반환한다.

여기서 가장 중요한 내용이 있는데, 이 메서드는 원자적으로 실행된다는 점이다.

그리고 이 메서드가 제공하는 기능이 바로 CAS(compareAndSet) 연산이다.

(3) 실행 순서 분석

CAS - 성공 케이스

• 여기서는 AtomicInteger 내부에 있는 value 값이 0이라면 1로 변경하고 싶다.
• compareAndSet(0, 1)을 호출한다. 매개변수의 왼쪽이 기대하는 값, 오른쪽이 변경하는 값이다.
• CAS 연산은 메모리에 있는 값이 기대하는 값이라면 원하는 값으로 변경한다.
• 메모리에 있는 value의 값이 0이므로 1로 변경할 수 있다.
• 그런데 생각해보면 이 명령어는 2개로 나누어진 명령어이다. 따라서 원자적이지 않은 연산처럼 보인다.
  1. 먼저 메인 메모리에 있는 값을 확인한다.
  2. 해당 값이 기대하는 값(0)이라면 원하는 값(1)으로 변경한다.

CPU 하드웨어의 지원

CAS 연산은 이렇게 원자적이지 않은 두 개의 연산을 CPU 하드웨어 차원에서 특별하게 하나의 원자적인 연산으로 묶어서 제공하는 기능이다. 이것은 소프트웨어가 제공하는 기능이 아니라 하드웨어가 제공하는 기능이다. 대부분의 현대 CPU들은 CAS 연산을 위한 명령어를 제공한다.

CPU는 다음 두 과정을 묶어서 하나의 원자적인 명령으로 만들어버린다. 따라서 중간에 다른 스레드가 개입할 수 없다.

1. x001의 값을 확인한다.
2. 읽은 값이 0이면 1로 변경한다.

CPU는 두 과정을 하나의 원자적인 명령으로 만들기 위해 1번과 2번 사이에 다른 스레드가 x001의 값을 변경하지 못하게 막는다. 참고로 1번과 2번 사이의 시간은 CPU 입장에서 보면 아주 잠깐 찰나의 순간이다. 그래서 성능에 큰 영향을 끼치지 않는다. CPU가 1초에 얼마나 많은 연산을 수행하는지 생각해보면 이해가 될 것이다.

• value의 값이 0 → 1이 되었다.
• CAS 연산으로 값을 성공적으로 변경하고 나면 true를 반환한다.

CAS - 실패 케이스

• CAS 연산은 메모리에 있는 값이 기대하는 값이라면 원하는 값으로 변경한다.
• 여기서는 AtomicInteger 내부에 있는 value 값이 0이라면 1로 변경하고 싶다.
• 현재 value 의 값이 기대하는 0이 아니라 1이므로 아무것도 변경하지 않는다.

• CAS 연산으로 값 변경에 실패하면 false를 반환하고, 값도 변경하지 않는다.

여기까지 듣고 보면 CAS 연산을 사용하면, 1. 기대하는 값을 확인하고 2. 값을 변경하는 두 연산을 하나로 묶어서 원자적으로 제공한다는 것은 이해했을 것이다. 그런데 이 기능이 어떻게 락을 일부 대체할 수 있다는 것일까?

2.2. CAS 연산2

어떤 값을 하나 증가하는 value++ 연산은 원자적 연산이 아니다. 이 연산은 다음 연산과 같다.

i = i + 1;

이 연산은 다음 순서로 나누어 실행된다. i의 초기 값은 0으로 가정하겠다.

1. 오른쪽에 있는 i의 값을 읽는다. i의 값은 0이다.
2. 읽은 0에 1을 더해서 1을 만든다.
3. 더한 1을 왼쪽의 i변수에 대입한다.

1번과 3번 연산 사이에 다른 스레드가 i의 값을 변경할 수 있기 때문에, 문제가 될 수 있다. 따라서 value++ 연산을 여러 스레드에서 사용한다면, 락을 건 다음에 값을 증가해야 한다.

CAS 연산을 활용해서 락 없이 값을 증가하는 기능을 만들어보자.
AtomicInteger가 제공하는 incrementAndGet() 메서드가 어떻게 CAS 연산을 활용해서 락 없이 만들어졌는지 직접 구현해보자.

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());

        // incrementAndGet 구현
        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;
    }
}

여기서 만든 incrementAndGet()은 atomicInteger 내부의 value 값을 하나 증가하는 메서드이다. 사실 atomicInteger도 이 메서드를 제공하지만, 여기서는 이해를 위해 직접 구현해보자.

CAS 연산을 사용하면 여러 스레드가 같은 값을 사용하는 상황에서도 락을 걸지 않고, 안전하게 값을 증가할 수 있다. 여기서는 락을 걸지 않고 CAS 연산을 사용해서 값을 증가했다.

• getValue = atomicInteger.get()을 사용해서 value 값을 읽는다.
• compareAndSet(getValue, getValue + 1)을 사용해서, 방금 읽은 value 값이 메모리의 value 값과 같다면 value 값을 하나 증가한다. 여기서 CAS 연산을 사용한다.
• 만약 CAS 연산이 성공한다면 true를 반환하고 do~while문을 빠져나온다.
• 만약 CAS 연산이 실패한다면 false를 반환하고 do~while문을 다시 시작한다.

실행 결과

지금은 순서대로 실행되기 때문에, 결과는 다음과 같다.

incrementAndGet 첫 번째 실행

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

incrementAndGet 두 번째 실행

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

지금은 main 스레드 하나로 순서대로 실행되기 때문에 CAS 연산이 실패하는 상황을 볼 수 없다. 우리가 기대하는 실패하는 상황은 연산의 중간에 다른 스레드가 값을 변경해버리는 것이다. 멀티스레드로 실행해서 CAS 연산이 실패하는 경우에 어떻게 작동하는지 알아보자.

2.3. 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() 코드를 추가했다.

실행 결과

실행 결과를 보면 마지막에 AtomicInteger가 정상적으로 2 증가된 것을 확인할 수 있다.

두 스레드의 실행 결과를 분석해보자. 보기 쉽게 스레드 별로 로그를 나누었다.

Thread-1 실행

• 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 첫 번째 시도

• 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를 반환한다.
• 실패했으므로 do~while문을 빠져나가지 못한다. do~while문을 다시 시작한다.
  • 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의 예를 보자.

실행 결과

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

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

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

락 방식

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

CAS 방식

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

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

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