[Concurrency] Compare And Swap (CAS)

#동시성

compare and swap은 멀티스레드 쓰기 작업에 사용되는 주요 개념 중 하나다.

lock 없이 효율적으로 병렬 작업을 동기화할수 있어서 lock-free operation이라고도 부른다.

문제

멀티스레드 환경에서는 거의 모든 것이 일반적인 환경과 다르게 동작한다.
integer 변수 하나를 두고 동시에 +1를 하는 간단한 로직을 수행하는 것만으로도 data race로 인한 쓰기 충돌 문제가 발생하기 때문이다.
단순 쓰기가 아니라 읽기-쓰기가 종합적으로 이뤄지는 경우라면 문제는 당연히 더 커질 것이다.

Compare And Swap

Compare And Swap, 이하 CAS는 이를 해결하기 위한 Atomic Operation이다.
하드웨어 지원이기 때문에 완전한 원자성을 보장한다.

방법론은 간단하다. 특정 변수를 내가 들어있을거라 예상한 값과 대조해서, 같으면 쓰기 작업을 수행하고, 다르면 쓰기 실패로 처리를 하는 것이다.
말 그대로 비교해서(compare) & 바꿔치는(swap) 것이다.

예시를 들어보겠다. 언어는 Rust다.

이건 기존 값에 1을 더하는 정말 단순한 코드다.
하지만 이것도 동시성 환경에 맞춰진 연산이라 진짜 단순하진 않다. 부가적인 논리가 들어가게 된다.

저 코드는 current 값이 4인 상태였다면 (4=>5)로 CAS를 날리게 된다.
여기서 CAS가 실행되는 시점이 진짜 4가 맞았다면, CAS 연산은 성공한다.
하지만 CAS가 실행되는 시점에, 다른 스레드가 저 값을 100으로 변경했다면, (4!=100)이므로 CAS 연산이 실패한다.

이런 실패 가능성이 있기 때문에, 대부분의 CAS 기반 코드는 실패-재시도를 반복하는 spin loop 로직이 들어가게 된다.

CAS 연산 각각은 단일 인스트럭션이라 리소스가 그다지 크진 않지만, 오랫동안 돌다보면 CPU 리소스를 많이 갉아먹게 된다. 그래서 쓰더라도 잘 써야한다.

CPU 인스트럭션

CAS는 라이브러리에서 구현하거나 하는게 아니라, 실제로 CPU 인스트럭션 수준에서 지원되는 명령이다. 이런 진정한 원자성은 하드웨어 지원 없이는 애당초 달성이 불가능하다.
그래서 일반적인 컴퓨팅 환경이 아니라면, CAS를 사용하는 것 자체가 불가능할 수 있다.

인텔 계열 프로세서에서는 이 작업 자체가 하나의 인스트럭션으로 제공이 된다. 이름은 cmpxchg이다.
예를 들어, 아래 코드는 rust의 표준 함수를 컴파일한 어셈블리 코드다.

l이 붙어서 피연산자 순서가 반대긴 한데,
cmpxchgl [새 값] [저장위치]
cmpxchg [저장위치] [새 값]
의 형태를 가진다.

비교할 기존 값은 rax, eax, 또는 ax, al 레지스터에서 가져온다.
레지스터의 값과 저장위치의 기존값이 같다면 새 값을 넣는 것이다.

ARM의 경우에도 인스트럭션을 바로 지원한다. 이름도 매우 직관적인 CAS다.

Strong CAS vs Week CAS

근데 잘 보면, cas는 한가지만 있는게 아니라 2가지가 존재한다. week라는 버전이 또 존재하는데

이건 Rust에만 있는건 아니고, C++ 등에도 있다.

week는 보장 수준이 낮은 CAS 버전이다.
Strong CAS가 전용 인스트럭션을 사용해서 완전한 동작을 보장한다면, week CAS는 원자성과 관련이 없는 인스트럭션 2개를 조합해서 느슨한 처리를 한다.

strong CAS는 쓰기에 성공했다면 성공했다고 하고, 실패했다면 실패했다고 한다.
반면 week CAS는 쓰기에 성공했더라도 실패했다고 알려줄 수 있다. 다만 성공했다고 하는 것은 정말 성공한 것이다.

week CAS가 이런 느슨한 보장으로 얻을 수 있는 것은 성능이다. week CAS는 strong CAS에 비해 근소하게 실행 성능이 좋다. 그래서 마이크로한 최적화를 할때, 거짓-실패가 허용되는 경우라면 사용하곤 한다.
week/strong 간의 성능 차이는 CPU 플랫폼마다 다르다.

arm의 예를 들면 strong CAS 인스트럭션은 단일 인스트럭션이긴 하지만, 사실 하드웨어 내부에서 retry loop를 돌린다. 그래서 다른 연산에 비해서는 매우 느린 편이다.
그리고 arm의 week CAS는 LDAXR/STLXR 2개의 조합으로 구현되는데, 이건 실패하면 retry loop 없이 그대로 반환한다. 그래서 race가 심할수록 성능이 좋을 수 있다.