원자적 연산 에서

원자적 연산 소개

하나의 명령어는 겉보기에는 더 이상 나눌 수 없는 하나의 동작처럼 보일 수 있지만, 실제로는 전혀 그렇지 않아요. 메모리에 있는 값에 5를 더하는 경우를 봐요:

add qword [rel counter], 5

내부적으로 프로세서는 메모리에 직접 값을 더하는 방법이 없어요. 그래서 이 명령어 하나를 마이크로 연산이라고 부르는 세 개의 작은 단계로 나눠요:

1. 메모리에서 현재 값을 읽고;
2. 레지스터에서 이 값에 5를 더해 수정하고;
3. 결과를 다시 써요.

mov rax, qword [rel counter] ; 1. load the current value
add rax, 5                   ; 2. add five
mov qword [rel counter], rax ; 3. store the result back

이것은 read-modify-write (RMW) 라고 부르는 흔한 패턴이에요.

읽기(또는 로드)와 쓰기(또는 스토어)는 서로 별개의 사건이라서, 그 사이에 시간적인 틈이 있어요. 단일 코어에서는 각 명령어가 다음 명령어로 넘어가기 전에 그 효과를 완전히 만들어 내는 것이 보장되기 때문에, 우리는 보통 이 틈을 알아차리지 못해요. 따라서 그 틈은 보이지 않고, add는 하나의 단위처럼 동작해요.

하지만 요즘 CPU는 단일 코어인 경우가 드물고, 애플리케이션은 흔히 여러 코어에서 동시에 실행되는데, 코어들 사이에는 순서가 정해져 있지 않아요. 여러 코어가 바로 그 같은 순간에 실행되면, 다른 코어가 이 코어의 로드 이후이자 스토어 이전인 그 틈 안에서 counter를 읽거나 쓸 수 있어요. 두 스레드가 각각 같은 예전 값을 로드하고, 각각 5를 더하고, 각각 자신의 결과를 저장해요. 덧셈은 두 번 일어났지만, 값은 5만큼만 움직였어요. 업데이트 하나가 조용히 사라진 거예요.

이것이 바로 데이터 레이스이고, 멀티스레드 코드에서 흔히 생기는 문제예요.

모든 값이 이런 식으로 노출되는 것은 아니에요. 각 스레드는 자신만의 레지스터와 자신만의 스택을 가지고 있어서, 레지스터에 담긴 값이나 스레드 스택 위의 지역 변수는 그 스레드만의 것이고 경쟁할 수 없어요. 위의 counter처럼 스레드가 공유하는 메모리만 보호가 필요해요.

x86-64는 명령어를 나눌 수 없는 단위로 만들어서 이 문제를 해결하는 명령어 집합을 제공해요. 이 명령어는 자신을 처리하는 코어뿐만 아니라 다른 모든 코어에게도 하나의 단위로 동작해요. 다른 코어가 쪼갤 수 없이 하나로 유지되는 연산을 원자적이라고 해요.

원자적 교환

xchg 명령어는 두 개의 피연산자를 맞바꿔요. 목적지 피연산자는 소스 피연산자의 이전 값과 같아지고, 소스 피연산자는 목적지 피연산자의 이전 값과 같아져요. 개념적으로는 두 개의 mov 명령어가 동시에 일어나는 것으로 생각할 수 있어요.

여느 때처럼, 두 개의 레지스터 피연산자와 함께 쓸 수도 있고, 하나의 메모리 피연산자와 하나의 레지스터 피연산자와 함께 쓸 수도 있어요:

mov  eax, 1
xchg dword [rdi], eax ; [rdi] = 1, eax = the old value of [rdi]
mov ecx, 2
mov edx, 3
xchg edx, ecx         ; edx = 2, ecx = 3

메모리 피연산자와 함께 쓰이면, xchg는 항상 원자적이에요. 프로세서는 그동안 그 위치에 락을 걸어요. 이는 다음에 설명할, lock 접두사가 다른 명령어들에 사용하는 것과 같은 메커니즘이에요.

lock 접두사

x86-64에서 명령어를 원자적으로 만드는 가장 흔한 방법은 lock 접두사를 붙이는 거예요. 이 접두사는 읽기, 수정, 쓰기를 하나의 나눌 수 없는 단계로 융합해요. 즉, 코어가 전 과정 동안 그 메모리를 독점하므로, 그 사이에 다른 코어가 그 위치를 읽거나 쓸 수 없어요.

lock add qword [rel counter], 5 ; the read, the modify, and the write are one step

lock은 목적지가 메모리일 때만, 그리고 그 메모리를 읽고-수정하고-쓰는 명령어에만 동작해요:

1. add, sub, inc, dec, neg 같은 산술 연산;
2. and, or, xor, not 같은 비트 연산;
3. bts, btr, btc 비트 명령어;
4. 아래에서 설명할 xadd, cmpxchg 같은 몇 가지 전용 명령어.

일반 mov처럼 그 밖의 명령어에서는 이 접두사가 유효하지 않고, 프로세서가 잘못된 opcode 폴트를 발생시켜요. 단독 로드나 단독 스토어에는 접두사가 필요 없어요. 자연스럽게 정렬된 접근은 그 자체로 이미 원자적이거든요.

원자적 비트 연산

락을 걸 수 있는 명령어들 가운데, 비트 테스트는 이 문서 끝에 나오는 스핀락과 자연스럽게 짝을 이뤄요. bts, btr, btc는 각각 선택한 비트 하나를 캐리 플래그로 복사한 다음, 그 비트를 세트하거나 클리어하거나 뒤집어요. lock 접두사를 붙이면 이것이 1비트 read-modify-write가 돼요. 비트가 원자적으로 바뀌고, CF가 이전 값을 알려줘요.

    lock bts qword [rdi], 0 ; set bit 0; CF = the bit's previous value
    setc al                 ; al = 1 when the bit was already set

세트하려는데 비트가 이미 세트되어 있다면, 다른 스레드가 먼저 차지한 거예요. 이는 xchg가 워드 전체에 대해 하는 플래그 선점을 1비트 버전으로 한 것이에요.

교환 및 덧셈

일반 lock add는 메모리를 갱신하지만 예전 값을 버려요. 흔히 예전 값이 바로 필요한 값일 때가 있어요. 예를 들어 각 스레드에 서로 다른 티켓 번호를 나눠줄 때요.

xadd 명령어는 (x는 exchange를 뜻해요) 덧셈을 하면서 이전 값을 반환해요. 합을 목적지에 쓰고, 원래 목적지 값을 소스 레지스터에 남겨둬요.

mov  rax, 1
lock xadd qword [rdi], rax ; [rdi] = [rdi] + rax = [rdi] + 1
                           ; rax = the old value of [rdi]

lock 접두사와 함께 쓰면 이것은 원자적 fetch-and-add예요. 여러 스레드가 같은 카운터에 대해 실행하면, 각 호출이 서로 다른 예전 값을 반환해요.

lock add와 마찬가지로, 카운터는 정확히 호출 횟수만큼에서 끝나요. 하지만 lock add와 달리, 모든 중간 값도 각 호출자에게 하나씩 반환돼요.

소스는 어떤 범용 레지스터든 될 수 있고, 피연산자 폭은 바이트부터 쿼드워드까지예요. 음수를 더하면 같은 명령어가 fetch-and-subtract가 돼요.

비교 및 교환

xadd는 더하고 xchg는 덮어쓰지만, 둘 다 새 값을 현재 값에 의존하게 만들고 그 사이에 아무것도 바뀌지 않았을 때만 적용하는 것은 못 해요. 그런 조건부 갱신을 제공하는 것이 바로 cmpxchg, 즉 compare-and-exchange이고, 이것이 이 원시 연산들 가운데 가장 일반적이에요.

cmpxchg dest, src는 rax를 암묵적 누산기로 사용하고, 그것을 dest와 비교해요:

• dest == rax이면 dest = src이고 ZF = 1이에요.
• dest != rax이면 rax = dest이고 ZF = 0이에요.

누산기는 피연산자 크기를 따라가요. 바이트에는 al, 더 넓은 형태에는 ax, eax, rax를 써요.

dest는 이전에 rax에 로드한 기대값과 같을 때만 갱신된다는 점에 유의해요. 이 동등성 덕분에 dest가 새 값을 계산해 낸 그 값 그대로임이 보장되므로, 오래된 읽기에 기반한 갱신은 절대 적용되지 않아요. 그래서 cmpxchg는 compare-and-swap (CAS)라고도 하는 원자적 갱신의 구성 요소가 돼요:

    mov rax, qword [rdi]          ; rax = the value we expect to find
.retry:
    lea rcx, [rax + 10]           ; rcx = the new value we want to install
    lock cmpxchg qword [rdi], rcx ; if [rdi] still equals rax, store rcx and set ZF
                                  ; otherwise reload rax with the current value, clear ZF
    jnz  .retry                   ; ZF is cleared, so another thread won the race. Recompute and retry

이 재시도 루프가 락 프리 갱신의 핵심이에요. 읽기와 compare-and-exchange 사이의 틈이 바로 다른 스레드가 끼어들 수 있는 순간이고, cmpxchg는 오래된 읽기로 계산한 값을 저장하기를 거부함으로써 그것을 잡아내요.

알아 둘 만한 미묘한 점이 하나 있어요. cmpxchg는 그 값이 읽었던 값과 같은지를 확인할 뿐, 그 위치가 한 번도 건드려지지 않았는지를 확인하지는 않아요. 다른 스레드가 그 틈 안에서 값을 A에서 B로 바꿨다가 다시 A로 되돌려 놓았다면, 그 아래에서 세상이 바뀌었는데도 교환은 _여전히 성공_해요.

일반 카운터라면 이건 무해해요. 같은 횟수는 똑같이 좋은 횟수니까요. 하지만 락 프리 리스트의 머리에 있는 메모리 주소라면 이야기가 달라요. 같은 주소가 이제는 다른 곳을 가리킬 수 있기 때문이에요. 이것이 바로 ABA 문제예요.

이 문제의 일반적인 해법은 값에 어떤 "스탬프"를 짝지어 붙이는 거예요. 예를 들어 계속 커지기만 하는 카운터 같은 것이요. 스탬프는 오직 앞으로만 나아가기 때문에, 스탬프가 일치한다는 것은 그 위치가 중간에 건드려지지 않았다는 증거이고, 단지 안 바뀐 것처럼 보인다는 것과는 달라요.

하지만 멀티스레드 환경에서 이게 통하려면, 메모리 주소와 그 스탬프가 함께 갱신되어야 해요. x86-64에서 메모리 주소는 쿼드워드 하나를 차지하므로, cmpxchg만으로는 그것과 또 다른 값을 동시에 갱신하기에 충분하지 않아요.

cmpxchg16b라고 하는 두 배 폭 명령어가 있는데, 의미상 cmpxchg와 같지만 16바이트를 한 번에 다루며 그런 상황에서 쓸 수 있어요. 이 명령어는 소스 피연산자가 없고, 대신 rcx:rbx를 대체 값으로 사용해요. 유일한 피연산자는 16바이트로 정렬된 메모리 위치예요. 또한 이 명령어는 rax만이 아니라 rdx:rax를 누산기로 사용해요.

메모리 오더링

지금까지의 모든 연산은 단일 위치만 건드렸어요. 스레드가 둘 이상의 위치를 통해 협력하면 새로운 질문이 생겨요. 한 스레드의 쓰기가 다른 스레드에 어떤 순서로 보이게 되는 걸까요. 이 질문에 답하는 규칙이 바로 프로세서의 메모리 오더링이에요.

branchless-code 개념에서 현대적인 코어가 명령어를 한 번에 하나씩 터벅터벅 처리하지 않는다는 이야기를 했어요. 코어는 여러 명령어를 동시에 진행 중인 상태로 두고, 가능한 곳에서는 앞서 나가요. 즉, 어떤 쓰기가 프로그램이 시사하는 시점보다 늦게 다른 코어에 보일 수 있는데, 그 뒤의 명령어들은 이미 앞서 나가 있을 수 있어요.

x86-64는 일반적인 로드와 스토어 사이에서 강한 메모리 오더링을 유지하기 때문에, 각 코어에서:

1. 로드는 뒤의 로드 뒤로 재배치되지 않아요;
2. 스토어는 뒤의 스토어 뒤로 재배치되지 않아요;
3. 로드는 뒤의 스토어 뒤로 재배치되지 않아요.

가능한 유일한 재배치는 어떤 스토어가 다른 주소에 대한 뒤의 로드 이후에 완료된 것처럼 보이는 경우뿐이에요.

lock 접두사가 붙은 명령어나 메모리 피연산자를 가진 xchg는 완전한 배리어예요. 그 경계를 넘어 어느 방향으로도 움직이는 것처럼 보이는 것이 없어요. 그래서 대부분의 상황에서 완전한 순서를 보장하기에 이들로 충분해요.

살아남은 그 하나의 재배치 뒤에 있는 메커니즘이 바로 스토어 버퍼예요. 앞서 나가기 위해, 코어는 각 스토어를 그 버퍼에 세워 두고, 그 스토어가 다른 코어가 볼 수 있는 메모리에 도달하기 전에 뒤의 명령어들이 진행되게 해요. 따라서 쓰기 뒤에 다른 위치를 읽는 경우 순서가 뒤바뀐 것처럼 보일 수 있어요. 뒤의 읽기가 앞서 나가는 동안 쓰기는 아직 버퍼에 남아 있을 수 있거든요. 쓰기 후 읽기의 그 틈만 빼고 모든 것이 순서대로 되는 이 모델을 total store order라고 해요.

그 틈 하나만으로도 스토어 후 확인 방식의 핸드셰이크를 깨뜨리기에 충분해요. 두 스레드가 각자 자신의 플래그를 쓰고 나서 상대방의 플래그를 읽으면, 양쪽 읽기 모두 세트되지 않은 값으로 돌아올 수 있어요. 어느 스토어도 아직 스토어 버퍼를 떠나지 않았기 때문이에요. mfence 명령어는 스토어 버퍼를 비워서 그 틈을 닫아요. 그 앞의 모든 쓰기는 그 뒤의 어떤 읽기보다 먼저 보이게 돼요.

    mov dword [rdi], 1    ; publish: this thread is ready
    mfence                ; the store above must land before the load below
    mov eax, dword [rsi]  ; observe whether the other thread is ready

더 좁은 범위의 배리어도 두 가지 있어요:

• sfence는 쓰기들 사이의 순서를 정하고, 주로 스트리밍 방식의 non-temporal 스토어와 관련이 있어요;
• lfence는 읽기들의 순서를 정해요.

위의 일반적인 원자적 패턴들에서는 lock 접두사가 붙은 명령어가 이미 완전한 순서를 담고 있어서, 명시적인 배리어는 위처럼 일반 스토어와 로드로 만든 핸드셰이크에만 필요해요.

이 보장들에는 x86을 넘어서 통용되는 이름이 있어요. 어떤 연산 뒤의 접근이 그 앞으로 움직이는 것처럼 보일 수 없을 때 그 연산은 acquire 순서를 가진다고 하고, 어떤 연산 앞의 접근이 그 뒤로 움직이는 것처럼 보일 수 없을 때 release 순서를 가진다고 해요. x86에서 모든 로드는 acquire이고, 모든 스토어는 release이며, lock 접두사가 붙은 명령어나 메모리를 대상으로 하는 xchg는 둘 다 한 번에예요.

스핀과 pause

플래그를 세트하면서 그 이전 상태도 함께 반환하는 명령어를 test-and-set이라고 해요. 이들은 스핀락의 토대로 쓸 수 있고, 어떤 코어가 코드의 일부에 배타적으로 접근하도록 보장해요.

이것이 이진 플래그와 함께 xchg 명령어를 사용하는 전체 알고리즘이에요:

1. 플래그는 0으로 시작해요.
2. 락을 획득하기 위해, 코어는 플래그의 값을 1과 맞바꿔요.
3. 반환된 값이 1이면, 다른 코어가 락을 _쥐고 있다_는 뜻이에요. 그러면 현재 코어는 기다렸다가 다시 락 획득을 시도해요.
4. 반환된 값이 0이면, 락이 비어 있었다는 뜻이에요. 이제 xchg가 그것을 1로 설정했고, 다른 코어들은 이 코어가 락을 풀 때까지 기다릴 거예요.
5. 현재 코어가 작업을 마치면, 플래그를 0으로 갱신해서 락을 풀어요.

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock; eax = its old value
    test eax, eax
    jnz  .held            ; old value was 1: someone else holds it
    ret                   ; old value was 0: the lock is ours
.held:
    pause                 ; wait before trying again
    jmp  acquire

대기 루프에 있는 pause 명령어는 코드가 계산하는 결과를 바꾸지 않아요. 이것은 프로세서에게 이것이 스핀 대기라는 것을 알려주는 힌트예요. 그러면 CPU는 기다리는 스레드의 전력 사용을 줄이고, 같은 코어를 공유하는 형제 스레드에게 양보할 수 있어요. pause 없는 스핀 루프도 여전히 올바르지만, 낭비일 뿐이에요.

test-and-set에서 xchg 같은 명령어는 플래그가 이미 세트되어 있었더라도 항상 세트한다는 점에 유의해요. 즉, 락이 아직 쥐어져 있을 가능성이 높은 경우에도 매번 스핀할 때마다 그 메모리에 대한 배타적 접근을 얻어요.

이 알고리즘에는 test-and-test-and-set이라고 하는 변형이 있는데, 먼저 플래그를 테스트(읽기)해서 이미 세트되어 있는지 확인해요. 그런 다음 락이 비어 보일 때만 test-and-set(여기서는 xchg)을 시도해요:

acquire:
    mov  eax, 1
    xchg dword [rdi], eax ; try to take the lock
    test eax, eax
    jz   .taken           ; got it
.held:
    pause                 ; wait before trying again
    cmp  dword [rdi], 0   ; watch the lock without writing to it
    jne  .held            ; still held
    jmp  acquire          ; looks free: retry
.taken:
    ret

스레드가 작업을 마치면, mov를 사용해 0을 일반 스토어 하는 것으로 락을 풀 수 있어요. mov 이상은 필요 없어요. x86-64에서는 로드와 스토어가 뒤의 스토어 뒤로 재배치되지 않기 때문이에요. 앞의 접근들을 절대 추월하지 않는 스토어는 release 순서를 가진다고 하고, x86에서는 모든 일반 스토어가 그것을 지녀요.