원자적 연산
원자적 연산(Atomic operation)은 공유 자원의 원자적 접근과 변경을 보장하는 연산을 뜻한다. 원자적이라는 것은 불가분한(더 이상 쪼갤 수 없는) 처리 단위를 말한다.
어떤 연산이 원자적이라는 것은 해당 연산 도중 상태는 시스템적으로 관측할 수 없고, 연산이 실패하면 연산 전 상태로 복원된다는 것을 의미한다. 엄밀히는 프로세서의 덧셈, 곱셈 명령도 원자적 연산이지만, 일반적으로는 여러 번의 메모리 접근이 필요한 작업을 원자적으로 처리하는 연산을 말한다.
Compare and Swap (CAS)
CAS 연산은 메모리 위치의 값(*p)과 주어진 값(val)을 비교해 두 값이 같은 경우에만 메모리 위치의 값을 변경하는 원자적 연산이다.
bool compare_and_swap(uint64_t *p, uint64_t val, uint64_t newval) {
if (*p != val) {
return false;
}
*p = newval;
return true;
}
그런데 사실 위 코드는 원자적이지 않다. L2(if (*p != val))는 L5(*p = newval)와 별도로 실행될 수 있다. x86 어셈블리 코드로 컴파일하면 아래와 같이 된다.
cmpq %rsi, (%rdi) ; rsi 레지스터의 값과 rdi 레지스터가 가리키는 값을 비교한다.
jne LBB0_1 ; 비교 결과가 같지 않으면 LBB0_1 라벨로 점프한다.
movq %rdx, (%rdi)
movl $1, %eax
retq ; 1을 반환한다.
LBB0_1:
xorl %eax, %eax ; eax 레지스터 값을 0으로 설정한다.
retq ; 0을 반환한다.
gcc, clang 같은 컴파일러는 원자적 연산을 위한 내장 함수 __sync_bool_compare_and_swap을 제공한다. 이 내장 함수는 하드웨어 수준에서 원자적 연산을 보장한다.
bool compare_and_swap(uint64_t *p, uint64_t val, uint64_t newval) {
return __sync_bool_compare_and_swap(p, val, newval);
}
앞서 정의한 compare_and_swap과 의미는 똑같지만, 어셈블리 코드로는 다르게 컴파일된다.
movq %rsi, %rax ; rsi 레지스터 값을 rax 레지스터로 복사한다.
xorl %ecx, %ecx ; ecx 레지스터 값을 0으로 초기화한다.
lock cmpxchgq %rdx, (%rdi) ; lock 접두사를 이용해 아토믹하게 값을 비교, 교환한다.
sete %cl
movl %ecx, %eax
retq
Test and Set (TAS)
TAS 연산은 메모리 위치의 값(*p)이 true인 경우 true를 반환하고, false인 경우 true로 변경한 뒤 false를 반환하는 원자적 연산이다.
bool test_and_set(bool *p) {
if (*p) {
return true;
}
*p = true;
return false;
}
CAS와 마찬가지로 하드웨어 수준에서 원자성을 보장하는 내장 함수 __sync_lock_test_and_set이 있다.
bool test_and_set(bool *p) {
return __sync_lock_test_and_set(bool *p);
}
Load-Link/Store-Conditional (LL/SC)
x86, x86-64에서는 lock 접두사로 메모리 락을 걸었지만, ARM, RISC-V 등의 CPU에서는 LL/SC 명령으로 원자적 연산을 구현한다.
- Load-Link (LL): 메모리 읽기를 배타적으로 수행한다.
- Store-Conditional (SC): 메모리 쓰기. LL 명령으로 지정한 메모리로의 쓰기는 다른 프로세스가 침범하지 않은 경우에만 성공한다.
공유 메모리상에 있는 변수를 여러 프로세스가 증가시키는 상황을 가정해보자.
- P1이 공유 변수 v의 값 1을 LL 명령으로 읽는다.
- 직후 P2가 v의 값 1을 read 명령으로 읽는다.
- 이어서 P2가 v의 값 1에 1을 더해 write 명령으로 2를 쓴다.
- P1이 v의 값 1에 1을 더해 SC 명령으로 2를 쓰지만 실패한다. (LL 명령과 SC 명령 사이에 v로의 쓰기가 발생했기 때문.)