CAS (Compaer And Swap)

1. CAS란?

CAS는 Compare And Swap의 약자로 위키의 설명에 따르면,
'멀티 스레딩에서 동기화 달성을 위해 사용되는 원자적 명령어(atomic instruction)'이다.
이 문장을 이해하기 위해서는 몇가지 배경 지식이 필요하다.

2. Atomic, Thread

일반 과학에서, 원자(atom)는 물질을 구성하는 가장 작은 단위를 뜻한다. 컴퓨터과학 역시 비슷한 의미로 사용된다. 수행 도중 중단될 수 없는 하나의 명령을 의미한다 좀 더 풀어서 말하자면 한번에 실행되어 중간 상태가 관찰되지 않는다고 할 수 있겠다. 이를 설명하기 위해 유명한 예시를 하나 들자면

int count = 0;

void Add(int number)
{
	for (int i=0; i < 1000000; i++)
		count++;
}
int main 
{
	thread t1(Add);
	thread t2(Add);

	t1.join();
	t2.join();

	cout << count << endl;
}

위의 코드를 실행하면 의도한 결과인 2000000이 출력되지 않는다. 바로 count++가 원자적이지 않기 때문이다. 어셈블리를 통해 자세히 알아보자

00007FF7C2BD2545  mov         eax,dword ptr [count (07FF7C2C165DCh)]  
00007FF7C2BD254B  inc         eax  
00007FF7C2BD254D  mov         dword ptr [count (07FF7C2C165DCh)],eax  

1. count의 값을 eax에 이동시킴 
2. eax의 값을 증가시킴
3. eax의 값을 count에 이동시킴

코드상에서 한번의 연산이지만 디스어셈블리에서는 3번의 연산을 진행한다. 즉 중간상태가 발견되기 때문에 멀티스레드 환경에서 문제가 발생한다.

간단한 예시로 t1이 3번을 시작하기 직전에 t2가 1번을 시작하면 t2는 증가되지 않은 값에 대해서 inc 명령어를 실행하기 때문에 의도한 값이 나오지 않는다.

atomic<int> count = 0;

c++11부터 추가된 atomic을 통해서 해결 할 수 있다.

00007FF636572705  xor         edx,edx  
00007FF636572707  lea         rcx,[count (07FF6365B65DCh)]  
00007FF63657270E  call        std::_Atomic_integral<int,4>::operator++ (07FF63656BAE0h)  

1. edx의 값을 0으로 만든다
2. rcx에 count의 '주소'를 가져온다
3. 내부 함수를 호출한다.

2번에서 값이 아니라 주소를 가져오는 것이 인상적이다.
3번에 대해서 좀 찾아보니 CPU에 따라서 지원하는 명령어를 호출하여 한번에 처리한다.
(x86 아키텍쳐에서는 LOCK prefix를 통해서 이를 지원하는 듯)

따라서 여기서의 count++는 '원자적으로' 동작한다.

3. CAS 탐구

다시 CAS의 의미를 살펴보면 Compare-And-Swap을 원자적으로 수행하는 것 인데. 어떤 경우에 사용할까?

멀티스레드 환경에서는 c++에서 제공되는 mutex와 lock_guard를 사용하는 예제가 많았다. 하지만 이 경우 스레드간의 문맥전환이 많아지고 성능저하의 원인이 되는 상황이 있다고 한다.
물론 스레드간의 문맥전환은 프로세스간의 문맥전환 보다는 가벼운 작업일 것이다. (CPU와 컴파일러가 계속 발전해가는데 아직도 눈에 띄는 성능저하가 있는지는 개인적인 의문이다.)

그래서 lock을 사용하지 않고 CAS를 사용해 동기화를 보장해준다.

//In window
bool compare_exchange_strong(_TVal& _Expected, const _TVal _Desired,
    const memory_order _Order = memory_order_seq_cst)

위의 함수는 visual studio에서 제공하는 C++ CAS의 기본 함수이다.

• _Expected : atomic 오브젝트가 가지길 기대하는 값
• _Desired : 기대하는 값을 가졌을 때 대체하길 원하는 값
• _Order : CAS를 실패 하거나 성공했을 때 적용할 memory_order
  • 성공/실패 시 적용할 memory_order를 따로 정할 수 있다.

의사 코드로 만들어 보자면 다음과 같다

if (objValue == expected)
{
	objValue = desired;
	return true;
}
else
{
	expected = objValue;
	return false;
}

• compare_exchange_strong : 도중에 다른 스레드에 의해 인터럽트가 나면 끝까지 시도
• compare_exchange_weak : 도중에 다른 스레드에 의해 인터럽트가 나면 실패 (spurious fake) (loop와 함께 사용)

이를 기반으로 Lock-free 자료구조를 만들 수 있다.

4. CAS의 문제 (ABA Problem)

간단히 말하면, 객체의 변경을 감지하지 못하는 문제이다.
(메모리 주소의 재사용에 관한 문제)

• Stack
  • A-> B -> C
  • head : A

이 상황에서 아래의 과정을 진행.

• expected = &A
• desired = B
• head.CAS(expected, desired)
• pop

하지만 멀티 스레드 환경에서 2번과 3번을 실행하기 전에 stack 이 다음과 같은 과정을 겪는다고 가정해보자

• Stack
  • A-> B -> C
  • head : A
• Stack
  • B -> C
  • head : B
• Stack
  • C
  • head : C
• Stack
  • A-> C
  • head : A

다시 원래의 스레드로 돌아오면 여전이 head == desied == A 이므로 head = desired를 실행하지만, B는 해제 되었을 수 있고, 다른 변수가 사용중일 수 있다.

해결 방법

Double compare-and-swap 말그대로 2개를 비교한다.
기존 시스템의 2배의 길이로 비교하며, count 값과 포인터를 비교한다.
포인터를 사용하면 count값을 증가 시킨다. 향후에 CAS를 할 때 포인터는 물론 count값 까지 동일하면 온전한 상태!

Visual Studo에서는 _InterlockedCompareExchange128를 지원하므로 이를 사용해보자

5. 여담

학부시절 운영체제 강의에서 배웠던 내용인데 오랜만에 다시 살펴 보았는데, 의외로 살펴볼 내용이 많아서 놀랐다. Lock-Free 자료구조를 만드는 것은 물론이고 신경 쓸 부분이 너무 많다. 정말로 Lock-Free하게 동작하는지도 검증하는 것이 어려운 점인 듯하다.
듣기로는 이 분야에 특허도 많다고 하는데 왜 그런지 알 것 같다.