synchronized, CAS, ABA

멀티 스레드 환경에서는 공유 자원을 신경 써줘야 한다.

왜 그럴까? 아래를 보자.

public class Tests {

    private static int count;
    @Test
    void nonMutualExclusion() throws InterruptedException {
        new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                count++;
            }
        }).start();

        new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                count++;
            }
        }).start();

        Thread.sleep(10000);
        System.out.println("count : " + count);
    }

}

- Result -
count : 14699

분명 2개의 스레드에서 10000씩 count를 증가시켰는데, 

결과값이 20000이 아닌 14699이다.

왜 이런걸까?

 

count++ 연산이 원자성을 보장하지 않기 때문이다.

이는 무슨 뜻이냐면, count++연산이 사실은 하나의 연산이 아니라는 뜻이다.

count++는 아래로 나눌 수 있다.

 

1. count 변수의 값 불러옴

2. 불러온 값 + 1

3. count 변수에 결과값 저장

 

3번의 연산을 수행하게 되며, 두개 이상의 경우 아래와 같은 문제가 생길 수 있다.

 

Thread 1. count 변수의 값(0) 불러옴

Thread 2. count 변수의 값(0) 불러옴

Thread 1. 0 + 1

Thread 1. count 변수에 1 저장

Thread 2. 0 + 1

Thread 2. count 변수에 1 저장

결과 : count = 1 예상값 : count = 2

 

여기서 count 변수를 여러개의 스레드가 공유해서 쓴다고 해서 공유자원이라고 한다.

위의 결과와 같이 원자성이 보장되지 않은 경우. 공유자원을 두고 스레드가 경쟁한다고 해서 이런 경우를 경쟁 상태(Race Condition) 라고 한다.
경쟁 상태를 방지하기 위해선 공유 자원을 한 스레드에서만 사용하게 해야한다.

이것을 상호배제 라고 한다.

 

synchronized

상호배제를 적용하기 위한 다양한 방법이 있지만 먼저 많이 사용하는 Java의 synchronized(동기화) 방식을 보자.

public class Tests {

    private static int count;

    synchronized void addCount() {
        count++;
    }

    @Test
    void nonMutualExclusion() throws InterruptedException {
        new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                addCount();
            }
        }).start();

        new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                addCount();
            }
        }).start();

        Thread.sleep(10000);
        System.out.println("count : " + count);
    }

}

- Result -
count : 20000

synchronized는 메서드 앞에 선언하는 것만으로 간단하게 사용할 수 있다.

메서드 블록 자체를 lock의 단위로 쓰며, 이 메서드는 동시간대에 하나의 스레드만 사용할 수 있다.

 

CAS(Compare and Swap)

다만, synchronized는 공유 변수를 쓰는 곳 마다 계속 lock처리를 해야하며, 블록 단위라서 느리다!

그래서 CAS 개념이 등장한다.

 

CAS는 이름대로 내가 알고있는 값과 비교해서 같다면 값을 입력하는 방법이다.

내가 알고있는 값과 다르다면 이미 다른 곳에서 변수의 값을 변경한 것이다.

함수로 설명해보자면 아래와 같다.

void compareAndSwap(int oldValue, int newValue) {
	if (count == oldValue) {
    	count = newValue;
    }
}

하지만 이렇게 소프트웨어로 구현하면 원자성이 보장되지 않기 때문에 Race Condition이 나타나게 된다.

그래서 오늘날 대부분의 CPU에선 CAS를 단일 명령어로 지원한다.

덕분에 쉽게 쓸 수 있는 것이다.

 

Java에선 CAS를 Atomic~~라는 객체로 쓸 수 있다.

이번엔 count 변수를 Java의 AtomicInteger로 구현해 보자.

public class Tests {

    private static AtomicInteger count = new AtomicInteger(0);

    @Test
    void nonMutualExclusion() throws InterruptedException {
        new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                count.getAndAdd(1);
            }
        }).start();

        new Thread(() -> {
            for (int i = 0; i < 10000; i++) {
                count.getAndAdd(1);
            }
        }).start();

        Thread.sleep(10000);
        System.out.println("count : " + count);
    }

}

- Result -
count : 20000

 

 

 

잘 작동한다.

 

ABA 문제

추가로 CAS를 사용할때 생길 수 있는 문제인 ABA문제를 다뤄보려한다.

ABA문제는 아래와 같은 경우를 의미한다.

스택에는 A, B, C가 차례대로 있다.

그리고 스레드1과 스레드2가 있는데, 스레드 2가 훨씬 더 빠르다고 하자.

 

스레드 1에셔 POP A를 실행하고

스레드 2에서 POP A, POP B, PUSH A를 실행한다.

 

이때 POP A, POP B 부분에서 A와 B의 할당 메모리를 해제한다.

 

그런데, A와 B는 해제 되었으니 재사용 할 수도 있다.

바로 뒤의 PUSH A 가 실행되고 처음 사용했던 A공간을 재활용 한다

스레드 1은 그것도 모르고, top값이 원래 알고있던 값과 같으니 CAS를 통과해 버린다.

 

그리고 next인 B를 top으로 설정한다.

이미 B공간은 free가 된 상태라서 이후 스택을 쓴다면 오류가 발생할 것이다. (free 공간을 참조하면 OS에서 memory validation error를 일으킨다)

 

이런 오류를 해결하려면 DCAS(Double compare-and-swap)이나 Hazzard Pointer방법을 쓰면된다.

 

Java와 같이 Garbage Collector를 쓰는 언어는 이런문제에서 자유롭다.

A, B, C를 노드 객체로 만들어 버리면 pop이 된 상태여도 pointing되어있기 때문에 메모리 해제가 일어나지 않고,

새로 들어온 A노드 객체와 pop된 A노드 각체가 다르기 때문에 CAS를 통과하지 못한다.