CAS, 낙관적 락, Atomic VS LongAdder(Accumulator)

이 글은 Lock-Free 방식 중 하나를 설명한다.

1. CAS 기법이란

<CAS 기법>

=> 가정1: CompareAndSwap함수는 원자적으로 실행된다고 가정한다.

=> 가정2: ptr은 모든 프로세서가 공유할 수 있는 Volatile 메모리이다.

 

1. 일단, 공유 메모리에 접근해 ptr의 값을 가져온다.

2. (기대하는 값)expected와 비교해 같다면, 값을 new로 갱신(새로운 값)

3. 실제 ptr의 값을 반환한다.

 

이를 while문으로 actual값과 expected값이 같을 때 까지 돌려준다.

<while문으로 돌림>

즉, CompareAndSwap(CAS)와 SPIN(while문)으로 락을 구현할 수 있다.

 

이게 무슨 소리인가 싶다.

그렇다면, 예제를 통해 살펴보자.

2. CAS 기법을 이용한 락 방식 예

2-1. 상황

=> Counter을 갱신하는 상황이다.

=> 모든 쓰레드가 공유할 수 있는 Counter라는 메모리가 있다.

=> 모든 쓰레드는 count에 +1을 하는 count()라는 메서드를 실행한다.

 

2-2. 동시성 문제가 나타나는 상황

public class Counter {
    private static int cnt = 0;

    public void count(){
        for(int i = 0; i < 1000; i++){
            cnt++;
        }
    }

    public int getCnt(){
        return cnt;
    }
}

<간단한 Counter 클래스>

import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

public class Main {
    public static void main(String[] args) {
        Counter counter = new Counter();
        try (ExecutorService executorService = Executors.newFixedThreadPool(10)) {
            for(int i = 0; i < 10; i++){
                executorService.submit(counter::count);
            }
        }catch (Exception e){}

        System.out.println(counter.getCnt());
    }
}

<10개의 쓰레드에서 실행>

<동시성 문제 발생>

 

2-3. 동시성 문제를 CAS로 해결

import java.util.concurrent.atomic.AtomicInteger;

public class Counter {
    private static AtomicInteger cnt = new AtomicInteger(0);

    public void count(){
        for(int i = 0; i < 1000; i++){
            while(true){
                int currCnt = getCnt();
                if(compareAndSwap(currCnt, currCnt+1)){
                    break;
                }
            }
        }
    }

    private boolean compareAndSwap(int expected, int update){
        return cnt.compareAndSet(expected, update);
    }

    public int getCnt(){
        return cnt.get();
    }
}

=> Main 메서드는 그대로 가져간다.

<동시성 문제 해결>

 

3. 낙관적 락과 CAS

=> 생각해보면 CAS와 낙관적 락은 락을 얻지 않고 업데이트 전에 검사하여 Spin을 돌리는 방식으로 꽤나 비슷하다.

=> 꽤나 비슷한 것이 아니라, 동작하는 방법은 같다.

=> 낙관적 충돌 감지 + 조건부 업데이트이기 때문이다.

 

=> 때문에, 쓰레드 간 경합이 심한 로직에 넣으면, CPU 소모가 크겠다.(SPIN 기반 Non-Blocking이기 때문)

=> 하지만, Lock보다는 성능이 어느정도 보장될 것이다.

 

4. LongAccumulator(LongAdder)의 등장

=> Atomic은 스핀을 통해 경합 상황 시 재시도를 한다.

=> 이는 CPU의 불필요한 사용량을 증가시킬 수 있다.

=> 때문에, 경합 상황 시 CPU 사용량을 낮출 수 있는 방식이 필요하다.

=> LongAccumulator는 Dynamic Striping을 사용하여, CAS(낙관적 락)의 경합 상황 시 재시도를 최대한 방지한다.

 

4-1. False Sharing(병렬 연산 시 고려해야 하는 것)

<출처 https://m.blog.naver.com/PostView.naver?blogId=palanmanzang&logNo=221161924103&proxyReferer=&noTrackingCode=true>

=> 위는 Mesi 프로토콜이다.

=> E는 유일한 복사본(메인 메모리의 데이터를 가져옴을 뜻함)

=> S는 공유됨(하나의 캐시에서 데이터를 E했을 때, 다른 Core에 그 데이터를 공유)

=> M는 수정됨

=> I는 무효(다른 코어의 캐시에서 수정되었을 시 해당 캐시의 데이터는 무효하다.)

=> 캐시는 64 바이트 단위로 읽고 씀

=> 즉, {A = 1, B = 1}이라는 데이터가 한 번에 캐시로 올라옴(모든 캐시 라인은 E나 S상태)

=> Thread 1(Core1)이 A = 2로 바꾸고, Thread 2(Core2)가 B = 2로 바꾸고자 함.

=> Thread1(Core1)이 A = 2로 바꿈.

=> Core1의 {A = 2, B = 1}이 M상태, 나머지 코어에서는 {A = 1, B = 1}이 I상태

=> 즉, Core2가 B = 2로 바꾸고자 할 때, {A = 1, B = 1}은 I 상태이기 때문에, 메모리에서 다시 읽어와야 함

=> 낙관적 락과 비슷한 구조이다.

=> 때문에, 공간 지역성이 비슷한 메모리들의 참조 시 병렬 연산 시 병목 현상이 발생할 수 있다.

=> 이를 고려해서, LongAccumulator(LongAdder) Padding을 임의로 둠으로 공간 지역성을 다르게 해, 다른 캐시로 한다.

 

5. CAS가 적용된 다양한 자바 클래스들

https://icanchangeworld.tistory.com/160

CAS가 적용된 다양한 자바 클래스들