Compare And Exchange(CAS) 명령어

Compare And Exchange (CAS)

Compare And Exchange (CAE)  명령어는 락을 사용하지 않는 기본 원자함수이며(CPU 레벨에서 지원한다.), 

비교와 교환을 원자성을 가지고 수행한다.

Compare And Swap (CAS)  라는 이름으로도 불린다.

행동 정보

• 서로다른 두 값을 비교하고,

• 두 값이 같다면 새로운 값으로 덮어쓴다.

인자 정보

• current : 현재 값

• old      : 현재 값 이라고 예상되는 값. (다른 쓰레드에 의해 다른 값으로 갱신 되었을 수 있다.)

• newVal : current  == old  이면 새롭게 current 에 대입될 값.

반환 정보

• true    :  current  == old  일 때,  ( current = newVal  명령도 동시에 일어남. )

• false   :  current  !=  old  일 때, 

기본적인 구현은 다음과 같으며,

매커니즘을 설명하기 위한 것 뿐이지 실제로 적용가능한 함수는 아니다.

current 의 자료형이 포인터인 것에 주목하자.

포인터가 아니였다면 이 시점에서의 현재 값을 얻어올 수 없을 것 이다.

포인터를 사용하지 않았을 때 다른 쓰레드가 current 를 변경했다면, 

값으로만 비교하는 그 함수는 current 가 바뀐 것을 눈치채지 못한다.

아래는 간략한 진행도이다.

Usage

이 함수는 current 와 old 가 같을 때, current 의 값을 갱신하는 함수이다.

즉, current == old 이어야 할 필요성이 있는 자료구조에 사용된다.

예를 들자면 다음과 같은 자료구조에 사용될 수 있다.

• 카운터

• 노드를 사용하는 자료구조 (스택, 큐, ..)

• ...

카운터와 스택의 실제 예제는 Concurrent Examples 절에서 설명한다.

C++11 Standard

compare_exchange  함수는 C++11에서 추가되었으며,

원자계 프리미티브 타입인 atomic<T> 에서 멤버 메소드로 구현되었다.

이 함수에는 weak와 strong 2가지 버전이 있다.

각각 compare_exchange_weak  와 compare_exchange.strong  이다.

weak 버전의 함수는 current == old  이지만 false 를 반환할 수 있다.

위의 특징 덕분에 일부 플랫폼에서는 strong 버전보다 좀 더 빠르게 동작한다.

하나 주의할 점이 있는데, 

T가 다음의 특징을 가지고 있다면 weak 버전을 사용해야 한다.

아래와 같은 경우에서는 strong 버전은 항상 fail  를 반환한다.

• T는 패딩비트를 가질 수 있다.  (C++20에서 수정된다.)
• T는 트랩비트를 가질 수 있다.
• 하나의 상태에 여러 표기법이 있을 수 있다. (예를들면 float-point NaN)

weak 버전은 T를 굉장히 단순하게 비교하며,

strong 버전은 비트열까지 엄격하게 비교하기 때문이다.

그리고 current != old  일 경우, current  를 old  로 업데이트한다.

* Concurrent Example(1)에서 위 사항을 적용한 예제가 있다.

C++20 standard

C++20 부터 값에 관여하지 않는 패딩비트는 무시되도록 strong 버전이 개선되었다.

Concurrent Example(1) : Thread-Safe Counter

먼저 쓰레드에 안전하지 않은 버전부터 살펴보자.

10000  개의 쓰레드가 하나의 카운터에 대하여 개별적으로 10000  번씩 증가시킬 것 이다.  

그러므로 카운터의 최종값은 10000*10000  이 되어야 한다.

원하지 않은 값이 나온 이유는 명백하고 단순하다.

같은 값에 대해 v+=1  을 수행한 쓰레드 쌍이 존재하기 때문이다.

예를 들어 v = 100  인 상태에서,

이미 다른 쓰레드에 의해 v = 101  으로 갱신되었음에도 불구하고,

이것을 눈치채지 못하고 v = 101  로 갱신하려는 다른 쓰레드가 있었기에 발생한 것 이다.

이 문제를 해결할 수 있는 키 포인트는 간단하다.

값을 증가시키기 전에 누군가가 이미 값을 변경했나 확인하는 것 이다.

다음은 위의 키 포인트를 적용하여 작성한 쓰레드에 안전한 버전이다.

19행:  current == old  조건이 맞지 않았다면 다른 쓰레드가 이미 1을 증가시켰다는 것 이다.

21행:  old 를 명시적으로 갱신시키는 과정은 필요하지 않다. 실패했을 경우에 compare_change  내에서 old = current   로 업데이트된다.

19행에서 SpinLock의 개념이 쓰인것의 유의하자.

Compare_And_Exchange  또는 Test_And_Set  같이 LOCK-FREE한 원자함수를 사용할 때, 

SpinLock 처럼 원하는 상황이 나올때까지 while() 에서 무한 대기하는 것을 기본 매커니즘으로 하는데.

while() 문에서 무한대기 한다는 것은 자원을 엄청나게 많이 잡아먹는다는 것에 주의하자.

실제로 위의 소스코드를 실행했을 때 CPU 사용량이 급증했다.

Concurrent Example(2) : Thread-Safe Stack

아래 예제의 출처는 cppReference이며 약간 수정했다.

위의 Atomic Counter를 이해했다면 다음의 Stack도 쉽게 이해할 수 있을 것 이다.