[C#] Interlocked.Exchange와 CAS algorithm, ABA problem

· Interlocked.Exchange()

C#의 Interlocked는 멀티쓰레딩 환경에서의 유저 모드 동기화 요소 개념인 정적 클래스이다. 유저 모드 동기화 요소는 여러 쓰레드를 조율하기 위해 특별한 CPU 명령을 사용하여 커널 모드 동기화 요소보다 훨씬 빠르게 수행된다는 특징이 있다.

멀티쓰레드 프로그래밍에선 동기화가 필수적으로 이루어져야 하는데, Interlocked.Exchange() 메서드는 Atomic하게 값을 변경하는 작업을 수행할 때 사용할 수 있다. Interlocked.Exchange() 메서드는 다음과 같은 형태로 정의되어 있다.

public static extern int Exchange(ref int location1, int value);

이는 int 타입용으로 오버로딩된 형태이고, 같은 형태로 object 타입 또는 제네릭 타입으로 오버로딩된 메서드도 제공된다.

해당 함수를 호출하면 location1 인자에 value를 저장함과 동시에 반환 값으로 value를 저장하기 이전 즉, 원래의 location 값을 반환한다. 위 Interlocked.Exchange() 메서드를 호출하면 아래의 코드를 Atomic하게 수행함을 보장하는 것과 똑같다.

int val1 = 5;

int val2 = Interlocked.Exchange(ref val1, 10);
Console.WriteLine(val2);

==============================================

// 위 코드와 똑같다.
int val1 = 5;

int val2 = val1;
val1 = 10;
Console.WriteLine(val2);

해당 함수를 활용할 수 있는 한 가지 예시가 Swap 작업이다.

int val1 = 5;
int val2 = 10;
val2 = Interlocked.Exchange(ref val1, val2);

val2를 val1 저장하면서, 변경되기 전의 val1을 val2에 저장하여 Swap과 같은 효과를 낼 수 있다. 하지만 이때 주의해야 할 것이 있다. 아래 Interlocked.Exchange() 메서드를 사용한 코드와 그를 분석한 ildasm 유틸리티의 결과를 먼저 살펴보자.

IL_0006에서 Interlocked.Exchange() 메서드를 호출하였고, 그 다음 IL_000b 라인에서 stloc.1이라는 명령을 확인할 수 있다. stloc 명령은 스택에 있는 값을 지역변수로 가져오는 명령이다. Interlocked.Exchange()로 반환된 값이 우선 스택에 저장되었고, 이후 별개의 명령으로 스택 값을 num2에 저장했다는 것이다.

이것이 뜻하는 것은 Interlocked.Exchange()와 그 반환값을 저장하는 작업은 Atomic하지 않다는 것을 의미한다. 즉, 앞서 설명한 Interlocked.Exchange() 메서드로 Swap 기능 등을 구현할 때 모든 과정의 원자성이 보장되지 않는다.

val2 = Interlocked.Exchange(ref val1, val2);

위 코드는 OOP의 결합성(Composability) 덕분에 편리한 식을 작성할 수 있었을 뿐, 같은 라인에 작성하였다고 해서 val2에 Interlocked.Exchange()의 반환값을 저장하는 것이 Interlocked.Exchange()가 포함하는 기능은 아니라는 것을 기억해야 한다. 단지 두 연산이 하나인 것처럼 표현이 된 것이고, 원자적으로 수행될 것이라고 오해해선 안 된다.

int num1 = 5;
int num2 = 10;
int temp = 0;

// SWAP
temp = num1;
num2 = temp;	// Interlocked.Exchange() 메서드는 해당 부분까지만 원자성을 보장한다.
num1 = num2;

즉 교환 과정에서 Data race가 발생할 여지가 여전히 존재하는 것이다. 이를 위해 CAS 알고리즘을 활용할 수 있다.

· CAS(Compare And Swap) Algorithm

CAS 알고리즘은 프로그래밍에서 Lock 기능을 구현하기 위해 만든 비교와 교환 연산이 합쳐진 형태의 연산 알고리즘이다. Compare는 '어떤 값과 특정 값을 비교한다.', Swap은 '두 값이 동일하면 어떤 값을 다른 것으로 교체한다.' 라는 뜻을 가지고 있다.

CAS를 구현하면 다음과 같다.

int CompareAndSwap(int* var, int new, int expected){
	int curVar = *var;
    if (*var == old){
    	*var = new;
    }
    return curVar;
}

이때 핵심은 값을 변경하는 시점에 값을 변경할 변수 var이 기대하는 값 expected와 같으면 new로 변경하는 조건문이 존재한다는 것이다. CompareAndSwap() 호출 시점에 다른 쓰레드가 var에 접근해 다른 값으로 변경하였을 때 불일치를 확인하고 추가적인 조치를 할 수 있다는 것이다.

이때 중요한 것은 Blocking이 없다는 것이다. 이를 활용하면 다른 쓰레드를 Block 시키지 않고 값싸게 Lock을 구현할 수 있다.

- C#의 CAS, Interlocked.CompareExchange()

C#은 Interlocked 클래스에 CAS를 구현한 메서드 CompareExchange()를 제공하고 있다. 이는 내부적으로 위의 CAS 구현 예시와 같은 코드를 구현하고 있다.

public static Int32 CompareExchange(ref Int32 location, Int32 value, Int32 comparand);
    // Int32 old = location;
    // if (location == comparand) location = value;
    // return old;

이러한 CompareExchange() 메서드를 이용하여 다음과 같이 Lock을 구현할 수 있다.

using System;
using System.Threading;

class Test
{
    volatile static internal int _lock = -1;

    static void Main()
    {
        for (int i = 0; i < 100; i++)
        {
            new Thread(tryLock).Start();
        }
    }

    internal static int CASLock()
    {
        return -Interlocked.CompareExchange(ref _lock, 1, -1);
    }

    internal static void tryLock()
    {
        while (CASLock() != -1)
        {
            Thread.Sleep(1);
        }

        Console.WriteLine("Get Lock");
        Thread.Sleep(500);
        _lock *= -1;
    }
}

· ABA Problem

추가적으로 알아 놓으면 좋을, CAS를 사용하는 Lock-free 알고리즘이 가지고 있는 고질적인 문제이다.

일반적인 큐에선 Dequeue를 할 때 단순히 head를 head->next로 변경하고, 기존의 head를 delete하는 작업을 할 것이다. 이때 CAS 알고리즘이 적용되어 있다면? 현재 head가 올바른지 확인 후, 올바르다면 head->next로, 아니라면 다시 작업을 시도할 것이다.

예를 들어 { D, C, B, A } 순서로 네 개의 원소를 삽입한 스택 있다고 하자. 이때 CAS pop을 한다면

// `top`이 `A`라면 `B`로 변경하고, 아니라면 취소 후 다시 수행한다.
Node curTop = top;
Node nextTop = top.next;
Interlocked.CompareExchange(ref top, nextTop, curTop); 

라는 실행을 준비할 것이다. 이때, 해당 작업이 실행되기 직전에 Thread B에 의해 두 개의 원소가 Pop 되었다고 하자.

그리고 마침, 아직 Thread A의 작업이 이루어지기 전에 Thread C에 의해 A가 다시 Push 되는 상황이 생길 수 있다.

이때 발생하는 문제가 ABA 문제이다. Thread C에 의한 수행까지 끝난 후에서야 Thread A가 CAS pop을 하면 현재 top이 A이므로 아무런 문제가 없는 것처럼 보인다. 따라서 B를 그대로 top으로 만드는데, B는 이미 제거된 객체이므로 대상이 되어선 안 된다.

해당 문제를 해결하기 위해 다양한 해결법이 있지만, 매우 간단하게 C#에선 ConcurrentStack, ConcurrentQueue, ConcurrentDictionary, ConcurrentBag과 같은 Concurrent 계열 자료구조를 사용함으로써 ABA 문제를 해결한 CAS 알고리즘이 적용된 효과를 낼 수 있다.

---

· 참고

▶ [MS Document] Interlocked.Exchange
▶ 멀티 쓰레딩 기본 - 스택과 CAS 연산
▶ ABA Problem