개막 공연

원자적 연산

명령어 하나가 마치 더 나눌 수 없는 하나의 동작처럼 보이지만, 실제로는 전혀 그렇지 않은 경우가 많아요. 메모리에 있는 값에 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

이것은 **읽기-수정-쓰기(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 접두사

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 같은 몇 가지 전용 명령어.

교환 후 더하기

그냥 lock add는 메모리를 갱신하지만 예전 값은 버려요. 예전 값이 바로 필요한 경우가 많아요. 예를 들어 각 스레드에 서로 다른 티켓 번호를 나눠 줄 때요.

xadd 명령어(x는 교환을 뜻해요)는 더하는 동시에 이전 값을 반환해요. 합은 목적지에 쓰고, 원래 목적지에 있던 값은 소스 레지스터에 남겨 둬요.

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

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

lock add와 마찬가지로, 카운터는 정확히 호출 횟수만큼 증가한 값에서 끝나요. 그런데 lock add와 달리, 중간 값들도 모두 반환돼요. 호출한 쪽마다 하나씩요.

비교 후 교환

xadd는 더하고 xchg는 덮어쓰지만, 둘 다 새 값을 현재 값에 의존하게 만들거나, 그 사이에 아무것도 바뀌지 않았을 때만 반영하게 할 수는 없어요. 그런 조건부 갱신을 제공하는 것이 바로 cmpxchg, 즉 비교 후 교환이고, 이 원시 연산들 가운데 가장 범용적이에요.

cmpxchg dest, src는 rax를 암묵적인 누산기로 사용해서 dest와 비교해요:

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

dest는 앞서 rax에 로드해 둔 기대값과 같을 때만 갱신된다는 점에 주목해요. 이 동등성 덕분에 dest가 아직 새 값을 계산할 때의 그 값 그대로임이 보장돼요. 그래서 오래된 읽기에 기반한 갱신은 절대 반영되지 않아요. 그래서 cmpxchg는 **비교 후 교환(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

이 재시도 루프가 락 없는 갱신의 핵심이에요. 읽기와 비교 후 교환 사이의 틈이 바로 다른 스레드가 끼어들 수 있는 순간인데, cmpxchg는 오래된 읽기로 계산한 값을 저장하지 않음으로써 그걸 잡아내요.

메모리 순서

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

분기 없는 코드 개념에서 현대적인 코어는 명령어를 한 번에 하나씩 느릿느릿 처리하지 않는다는 이야기를 했어요. 코어는 여러 명령어를 동시에 처리 중인 상태로 두고, 가능한 곳에서는 앞질러 나아가요. 그래서 어떤 쓰기가 프로그램이 암시하는 시점보다 늦게 다른 코어에 보일 수 있고, 그 뒤의 명령어는 이미 앞서 나가 있을 수 있어요.

x86-64는 일반적인 로드와 스토어 사이에 강한 메모리 순서를 유지해요. 그래서 각 코어에서:

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

가능한 재배치는 하나뿐인데, 다른 주소를 나중에 로드한 뒤에 스토어가 완료된 것처럼 보이는 경우예요.

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

스핀 대기와 pause

플래그를 설정하면서 그 이전 상태도 함께 반환하는 명령어를 테스트 앤드 세트라고 해요. 이런 명령어는 스핀락의 기반으로 쓰일 수 있어요. 스핀락은 어떤 코어가 코드의 일부를 독점적으로 사용하도록 보장해요.

이진 플래그와 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 없는 스핀 루프도 여전히 올바르지만, 낭비일 뿐이에요.

스레드가 작업을 마치면, mov로 평범하게 0을 스토어해서 잠금을 풀 수 있어요. mov 이상의 것은 필요 없어요. x86-64에서는 로드와 스토어가 뒤의 스토어보다 뒤로 재배치되지 않기 때문이에요. 앞선 접근들을 앞지르지 않는 스토어는 릴리스 순서를 가진다고 해요. 그리고 x86에서는 모든 평범한 스토어가 이 순서를 지녀요.