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

[YuDeokRin]

6️⃣ CAS 연산 1

✅ 락 기반 방식의 문제점

• SyncInteger 와 같은 클래스는 데이터를 보호하기 위해 락(synchronized,Lock(ReentrantLock)을 사용한다.

• 락은 특정 자원을 보호하기 위해 스레드가 해당 자원에 대한 접근하는 것을 제한한다.

• 락이 걸려 있는 동안 다른 스레드 들은 해당 자원에 접근할 수 없고, 락이 해제될 때까지 대기해야 한다.
  또한 락 기반 접근에서는 락을 획득하고 해제하는 데 시간이 소요된다.

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

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

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

✅ 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); //내부에 있는 기본 숫자 값을 `0`
으로 설정한다.
        System.out.println("start value = " + atomicInteger.get());

        boolean result1 = atomicInteger.compareAndSet(0, 1);// 메서드를 통해 CAS 연산을 지원한다.
        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(0, 1)

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

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

• 여기서 중요한 것은 이 메서드는 원자적으로 실행된다는 점이다.

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

➡️ 실행 순서 분석

• 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

• CASE 연산으로 값을 성공적으로 변경 후 → true 반환

• CAS - 실패 케이스

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

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

• 여기까지 듣고 보면 CAS 연산을 사용하면,

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

7️⃣ CAS 연산 2

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

i = i + 1;

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

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

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

• 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도 이 메서드를 제공하지만, 여기서는 이해를 위해 직접 구현해보자.

start value = 0
09:18:12.303 [     main] getValue: 0
09:18:12.304 [     main] result: true
resultValue1 = 1
09:18:12.305 [     main] getValue: 1
09:18:12.305 [     main] result: true
resultValue2 = 2

✅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 연산이 실패하는 경우에 어떻게 작동하는지 알아보자.

8️⃣ 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;

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();
            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
09:24:09.902 [ Thread-1] getValue: 0
09:24:09.904 [ Thread-1] result: true
09:24:09.902 [ Thread-0] getValue: 0
09:24:09.905 [ Thread-0] result: false
09:24:09.905 [ Thread-0] getValue: 1
09:24:09.905 [ Thread-0] result: true
AtomicInteger resultValue: 2

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

• Thread-1 실행

09:24:09.902 [ Thread-1] getValue: 0
09:24:09.904 [ 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 첫 번째 시도
09:24:09.902 [ Thread-0] getValue: 0
09:24:09.905 [ Thread-0] result: false

//[Thread-0] do~while 두 번째 시도
09:24:09.905 [ Thread-0] getValue: 1
09:24:09.905 [ 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 값을 읽는다. getVal는 1이다.
• compareAndSet(1,2) 을 수행한다.
  • compareAndSet(getValue, getValue + 1)
• CAS 연산이 성공했으므로 value 값은 1에서 2로 증가하고 true를 반환한다.
• do~while 문을 빠져나간다.

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

• 락(Lock) 방식

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

• CAS(Compare-And-Swap) 방식

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

• 락 방식

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

• CAS 방식

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