앞 글에서는 두 스레드가 counter++ 를 동시에 실행하면 증가가 유실되는 예제로 시작했습니다. counter++ 는 CPU 에서 읽기, 더하기, 쓰기 세 단계로 실행될 수 있습니다. 두 스레드가 같은 값을 읽은 뒤 각자 1을 더해 쓰면 두 번의 증가 중 한 번만 남습니다. 이 세 단계를 한 스레드씩 실행하게 만드는 도구가 lock 입니다.

pthread_mutex_lock(&lock);
counter++;
pthread_mutex_unlock(&lock);

lock 을 획득한 스레드만 임계 영역(critical section)에 들어가고 다른 스레드는 lock 이 풀릴 때까지 기다립니다. 상호 배제(mutual exclusion)는 한 번에 한 스레드만 임계 영역을 실행하게 하는 성질입니다. 그런데 lock 자체도 여러 스레드가 동시에 건드리는 공유 변수로 만들어야 합니다. 기다리는 스레드는 그동안 무언가를 하며 시간을 보내야 합니다. 그리고 lock 을 제대로 걸었는데도 프로그램이 느려질 수 있습니다.

lock 은 하드웨어와 운영체제의 도움을 받아 어떻게 만들어질까요? lock 을 기다리는 스레드는 CPU 를 쓰면서 기다려야 할까요? 자료구조에서 lock 을 잘게 나누면 더 빨라질까요?

OSTEP 28장 Locks와 29장 Lock-based Concurrent Data Structures, Linux 의 futex(2) man page, JDK 21 의 LongAdder 문서를 읽고 정리했습니다. 예제를 직접 실행하거나 측정한 결과는 없고 성능 수치는 OSTEP 29장에 실린 실험 결과입니다.

1. flag 변수 하나로 lock 을 만들 수 있을까요?

가장 먼저 떠오르는 방법은 변수 하나로 lock 의 상태를 나타내는 것입니다. flag 가 0이면 비어 있으니 1로 바꾸고 들어갑니다. 1이면 0이 될 때까지 기다립니다.

void lock() {
    while (flag == 1)
        ;           // 다른 스레드가 풀 때까지 반복해서 확인합니다
    flag = 1;
}

void unlock() {
    flag = 0;
}

이 코드는 두 스레드를 동시에 임계 영역에 들여보낼 수 있습니다.

  1. Thread A 가 flag 를 읽고 0인 것을 확인합니다.
  2. A 가 flag = 1 을 실행하기 전에 context switch 가 일어납니다.
  3. Thread B 도 flag 를 0으로 읽고 flag = 1 을 실행한 뒤 임계 영역에 들어갑니다.
  4. 다시 실행된 A 도 flag = 1 을 실행하고 임계 영역에 들어갑니다.

flag 를 확인하는 읽기와 1로 바꾸는 쓰기 사이에 다른 스레드가 실행될 수 있어서 생긴 문제입니다. counter++ 와 같은 문제가 lock 안에서 다시 생겼습니다. 확인과 변경을 나뉘지 않는 하나의 연산으로 실행하려면 하드웨어의 도움이 필요합니다.

2. 하드웨어는 lock 을 어떻게 도울까요?

test-and-set

test-and-set 은 메모리의 예전 값을 돌려주면서 새 값을 쓰는 명령입니다. C 로 쓰면 다음과 같지만 하드웨어는 이 읽기와 쓰기를 하나의 원자적 연산으로 실행합니다.

int TestAndSet(int *ptr, int new) {
    int old = *ptr;   // 예전 값을 읽고
    *ptr = new;       // 새 값을 씁니다
    return old;
}

1절의 lock() 에서 확인과 변경을 이 명령 하나로 바꿉니다.

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        ;
}

void unlock() {
    flag = 0;
}

flag 가 0일 때 TestAndSet() 을 부른 스레드는 0을 돌려받고 lock 을 획득합니다. 그와 동시에 flag 는 1이 됩니다. 여러 스레드가 동시에 불러도 0을 돌려받는 스레드는 하나뿐이고 나머지는 1을 돌려받아 반복문을 계속 돕니다. spin lock 은 이렇게 lock 이 풀릴 때까지 반복해서 확인하며 기다리는 lock 입니다.

compare-and-swap

compare-and-swap(CAS)은 메모리의 현재 값이 기대한 값과 같을 때만 새 값을 씁니다. 이것도 하드웨어가 원자적으로 실행합니다.

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

CompareAndSwap(&flag, 0, 1) 은 flag 가 0일 때만 1로 바꾸므로 test-and-set 자리에 넣어도 같은 spin lock 이 됩니다. CAS 는 lock 없이 동작하는 lock-free 자료구조를 만들 때도 씁니다. 앞 글의 AtomicInteger 도 이런 원자 명령으로 증가를 처리합니다.

load-linked/store-conditional

load-linked 와 store-conditional 은 짝으로 쓰는 명령입니다. load-linked 로 값을 읽은 뒤 그 주소에 다른 쓰기가 없었을 때만 store-conditional 이 쓰기에 성공합니다. flag 를 load-linked 로 읽어 0이면 store-conditional 로 1을 쓰고, 쓰기에 실패하면 처음부터 다시 시도하면 같은 spin lock 이 됩니다.

공정성과 ticket lock

test-and-set spin lock 은 공정성을 보장하지 않습니다. 다른 스레드들이 lock 을 계속 획득하고 해제하는 동안 한 스레드가 영원히 돌기만 할 수 있습니다. 이렇게 한 스레드가 계속 기회를 얻지 못하는 상태를 starvation 이라고 합니다.

fetch-and-add 는 값을 원자적으로 1 늘리면서 예전 값을 돌려주는 명령입니다. 이 명령으로 번호표를 나눠 주는 ticket lock 을 만들 수 있습니다. lock 을 획득하려는 스레드는 ticket 에 fetch-and-add 를 실행해 자기 번호를 받고 공유 변수 turn 이 자기 번호가 될 때까지 기다립니다. lock 을 풀 때는 turn 을 1 늘려 다음 번호를 부릅니다. 번호를 받은 스레드는 앞 번호의 스레드들이 지나간 뒤 반드시 차례를 얻습니다.

lock 은 순서도 지켜야 합니다

임계 영역 안의 읽기와 쓰기가 컴파일러나 CPU 에 의해 lock 밖으로 옮겨지면 lock 이 임계 영역을 보호하지 못합니다. 실제 lock 구현은 획득과 해제에서 이 순서도 보장합니다. Java 에서는 같은 lock 의 해제와 획득 사이에 happens-before 관계가 생깁니다. 이 부분은 앞 글의 3절에서 다뤘습니다.

3. spin lock 은 언제 CPU 를 낭비할까요?

spin lock 은 lock 을 기다리는 동안 반복문을 돌며 CPU 를 씁니다. CPU 가 하나인 시스템에서 두 스레드가 이렇게 실행된다고 하겠습니다.

  1. Thread A 가 lock 을 획득하고 임계 영역을 실행합니다.
  2. A 의 time slice 가 끝나 context switch 가 일어납니다.
  3. Thread B 가 실행되어 lock 을 획득하려 하지만 A 가 들고 있습니다.
  4. B 는 자기 time slice 가 끝날 때까지 TestAndSet() 을 반복합니다.

CPU 가 하나이므로 B 가 도는 동안 A 는 실행되지 않고 A 가 실행되지 않으니 lock 도 풀리지 않습니다. B 의 time slice 는 통째로 낭비됩니다. 스레드가 모두 N 개이고 그중 N - 1 개가 lock 을 기다린다면 A 가 다시 실행되기 전까지 time slice N - 1 개를 이렇게 낭비할 수 있습니다.

CPU 가 여러 개면 B 가 한 CPU 에서 도는 동안 A 는 다른 CPU 에서 임계 영역을 끝내고 lock 을 풀 수 있습니다. OSTEP 에 따르면 스레드 수가 CPU 수와 비슷할 때 spin lock 은 꽤 잘 동작합니다. 임계 영역이 짧다면 잠깐 도는 비용이 스레드를 재우고 깨우는 비용보다 작을 수 있습니다.

그래서 spin lock 은 CPU 가 충분하고, 임계 영역이 짧고, 경쟁하는 스레드가 적고, lock 을 들고 있는 스레드가 다른 CPU 에서 실행 중일 때 낭비가 적습니다.

돌지 않고 CPU 를 양보하면 어떨까요?

다른 스레드가 lock 을 들고 있으면 반복문을 도는 대신 yield() 로 CPU 를 다른 스레드에 넘길 수 있습니다.

void lock() {
    while (TestAndSet(&flag, 1) == 1)
        yield();    // CPU 를 양보합니다
}

CPU 하나에 스레드 두 개라면 잘 동작합니다. B 가 바로 양보하므로 A 가 실행되어 임계 영역을 끝냅니다. CPU 가 하나이고 스레드 100개가 lock 하나를 두고 경쟁한다고 하겠습니다. lock 을 든 스레드가 임계 영역 중간에 CPU 를 빼앗기면 나머지 99개가 차례로 실행되어 lock 을 확인하고 바로 양보합니다. time slice 99개를 통째로 도는 것보다는 낫지만 그만큼 context switch 가 일어나고 그 비용도 작지 않습니다. 그리고 yield() 는 starvation 을 막지 못합니다. 다른 스레드들이 임계 영역을 드나드는 동안 한 스레드가 계속 양보만 할 수 있습니다.

4. 기다리는 스레드를 재우려면 무엇이 필요할까요?

spin 과 yield() 모두 다음에 어느 스레드가 실행될지를 스케줄러에 맡깁니다. 스케줄러가 lock 을 들고 있지 않은 스레드를 고르면 그 스레드는 돌거나 양보할 수밖에 없습니다. OSTEP 은 기다리는 스레드를 큐에 넣고 재운 뒤, lock 이 풀리면 큐 맨 앞의 스레드를 깨우는 방법을 보여 줍니다. 이 예제는 Solaris 의 시스템 호출을 씁니다.

  • park(): 호출한 스레드를 재웁니다.
  • unpark(threadID): 지정한 스레드를 깨웁니다.

lock_t 에는 lock 이 걸려 있는지를 나타내는 flag, 기다리는 스레드를 넣는 큐 q, 그리고 flag 와 큐를 고치는 동안만 획득하는 작은 spin lock guard 가 있습니다.

void lock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ;                           // 큐를 보호하는 guard 를 spin 으로 획득합니다
    if (m->flag == 0) {
        m->flag = 1;                // lock 을 획득했습니다
        m->guard = 0;
    } else {
        queue_add(m->q, gettid());  // 대기 큐에 자신을 넣고
        m->guard = 0;
        park();                     // 잠듭니다
    }
}

void unlock(lock_t *m) {
    while (TestAndSet(&m->guard, 1) == 1)
        ;
    if (queue_empty(m->q))
        m->flag = 0;                // 기다리는 스레드가 없으면 lock 을 풉니다
    else
        unpark(queue_remove(m->q)); // 있으면 lock 을 다음 스레드에 바로 넘깁니다
    m->guard = 0;
}

이 코드에도 spin 이 남아 있지만 guard 를 들고 있는 시간은 flag 를 확인하고 큐를 고치는 몇 줄뿐입니다. 사용자 코드의 임계 영역이 길어도 기다리는 스레드는 잠들어 있습니다. 깨어난 스레드는 flag 를 다시 1로 바꾸지 않습니다. unlock() 이 flag 를 0으로 돌리지 않고 lock 을 큐 맨 앞에서 깨우는 스레드에 그대로 넘기기 때문입니다. 큐에 들어온 순서대로 깨우므로 starvation 도 막습니다.

잠들기 직전에 깨우는 신호가 오면 어떻게 될까요?

lock() 에서 guard 를 0으로 돌린 뒤 park() 를 부르기 전에 context switch 가 일어날 수 있습니다. 그 사이 lock 을 들고 있던 스레드가 unlock() 에서 이 스레드를 unpark() 하면 깨우는 신호가 잠들기 전에 도착합니다. 뒤늦게 park() 를 부른 스레드는 깨워 줄 스레드가 없는 채로 계속 잠들 수 있습니다. 이 스레드는 unlock() 이 넘겨준 lock 을 받은 상태라 flag 가 1로 남고 뒤에 오는 스레드도 모두 큐에 들어가 잠듭니다. 이 문제를 wakeup/waiting race 라고 합니다.

Solaris 는 setpark() 라는 세 번째 호출로 이 문제를 해결합니다. 스레드가 guard 를 풀기 전에 setpark() 로 곧 잠들 것이라고 알려 두면, park() 전에 unpark() 가 먼저 와도 뒤의 park() 가 잠들지 않고 바로 돌아옵니다.

queue_add(m->q, gettid());
setpark();      // 곧 park() 할 것이라고 알립니다
m->guard = 0;
park();

Linux 는 futex 로 비슷한 일을 합니다

futex 하나는 메모리의 정수 하나와 커널 안의 대기 큐 하나로 이루어집니다. 아래 두 이름은 OSTEP 이 단순화해 쓴 이름이고 실제로는 futex() 시스템 호출에 연산 종류를 인자로 넘깁니다.

  • futex_wait(address, expected): address 의 값이 expected 와 같으면 호출한 스레드를 재웁니다. 다르면 바로 돌아옵니다.
  • futex_wake(address): 그 큐에서 기다리는 스레드 하나를 깨웁니다.

futex(2) man page 에 따르면 커널은 값을 읽고 expected 와 비교하고 스레드를 재우는 과정을 원자적으로 실행합니다. 잠들기 직전에 다른 스레드가 lock 을 풀어 값이 바뀌었다면 futex_wait() 는 재우지 않고 돌아오므로 wakeup/waiting race 가 생기지 않습니다. 참고: futex(2).

OSTEP 이 보여 주는 glibc 의 mutex 코드는 정수 하나의 최상위 비트로 lock 이 걸려 있는지를, 나머지 비트로 기다리는 스레드 수를 나타냅니다. 경쟁이 없으면 lock 은 원자적 비트 test-and-set 한 번, unlock 은 원자적 덧셈 한 번으로 끝나고 커널에 들어가지 않습니다. 다른 스레드가 lock 을 들고 있을 때만 futex_wait() 로 커널에서 잠듭니다.

잠깐 돌다가 잠드는 two-phase lock

spin 은 CPU 를 쓰지만 lock 이 금방 풀리면 빠릅니다. sleep 은 재우고 깨울 때 시스템 호출과 context switch 비용이 드는 대신 CPU 를 쓰지 않습니다. two-phase lock 은 두 방식을 이어 붙입니다. 첫 단계에서는 lock 이 곧 풀리기를 기대하며 잠깐 돌고 그동안 획득하지 못하면 두 번째 단계에서 잠듭니다. OSTEP 에 따르면 이 방식은 1960년대 초의 Dahm Locks 까지 거슬러 올라가고 앞의 Linux mutex 도 한 번만 시도하고 잠드는 two-phase lock 입니다.

two-phase lock 이 더 나은지는 하드웨어, 스레드 수, 워크로드에 따라 달라서 모든 경우에 좋은 범용 lock 을 하나 만들기는 어렵습니다.

5. 올바른 lock 을 걸면 자료구조도 빨라질까요?

29장은 28장에서 만든 lock 을 자료구조에 거는 방법을 다룹니다. 가장 단순한 방법은 자료구조 전체에 lock 하나를 거는 것입니다.

typedef struct __counter_t {
    int value;
    pthread_mutex_t lock;
} counter_t;

void increment(counter_t *c) {
    pthread_mutex_lock(&c->lock);
    c->value++;
    pthread_mutex_unlock(&c->lock);
}

이 카운터는 thread-safe 합니다. 여러 스레드가 동시에 increment() 를 불러도 증가가 유실되지 않습니다. 하지만 모든 스레드가 lock 하나를 두고 경쟁하므로 한 번에 하나의 증가만 실행됩니다.

OSTEP 은 Intel 2.7GHz i5 CPU 4개가 달린 iMac 에서 스레드마다 카운터를 100만 번 늘리는 실험을 했습니다. 스레드 하나로는 약 0.03초가 걸렸고 스레드 두 개가 각자 100만 번씩 늘리자 5초 넘게 걸렸습니다. 스레드를 더 늘리면 더 나빠졌습니다. 작업이 lock 하나에서 순서대로 처리되면 병렬로 실행한 이점은 없어지지만 그것만으로는 두 스레드의 200만 번에 약 0.06초가 걸려야 합니다. 책은 이보다 80배 넘게 느려진 원인을 따로 설명하지 않습니다. 경쟁 중인 lock 을 기다리며 잠들고 깨는 비용과, lock 변수가 담긴 캐시 라인이 코어 사이를 오가는 비용이 더해졌을 것으로 추정합니다.

perfect scaling 은 스레드마다 CPU 가 따로 있을 때 스레드가 늘어도 각 스레드의 작업이 스레드 하나일 때만큼 빨리 끝나는 것을 말합니다. 총 작업량은 늘지만 병렬로 처리되므로 걸리는 시간은 늘지 않습니다. 이 카운터는 올바르게 동작해도 확장되지는 않습니다.

6. 카운터 하나를 여러 개로 나누면 어떻게 될까요?

OSTEP 이 소개하는 approximate counter(sloppy counter 라고도 부릅니다)는 논리적인 카운터 하나를 CPU 마다 하나씩 있는 local counter 와 global counter 하나로 나눕니다. local counter 마다 lock 이 있고 global counter 에도 lock 이 있습니다.

스레드는 자기가 실행 중인 CPU 의 local counter 를 그 CPU 의 local lock 으로 보호하며 늘립니다. 한 CPU 에서 여러 스레드가 번갈아 실행될 수 있어서 local lock 이 필요합니다. CPU 마다 local counter 가 따로 있으니 서로 다른 CPU 의 스레드는 경쟁하지 않습니다. local counter 의 값이 threshold S 에 도달하면 global lock 을 획득해 그 값을 global counter 에 더하고 local counter 를 0으로 되돌립니다. global lock 은 S 번의 증가마다 한 번만 획득하면 됩니다.

S 를 키우면 무엇을 얻고 무엇을 잃을까요?

CPU 4개가 같은 카운터를 CPU 마다 10번씩 늘립니다. local 값이 S 에 도달하면 global lock 을 획득해 global counter 에 더합니다. S 를 바꿔 같은 증가를 다시 실행해 보세요.

실제 값 0 global 값 0 가장 컸던 차이 0 상한 4 global lock 획득 0번 lock 대기 0번 끝날 때까지 0단계

approximate counter 를 단순화한 설명용 모형입니다. CPU 마다 스레드 하나가 한 단계에 한 번씩 카운터를 늘리고, CPU 1, 2, 3 은 각각 1, 2, 3단계 늦게 시작합니다. global lock 은 한 단계 동안 들고 있다고 가정했고, 기다리는 순서는 도착한 순서로 단순화했습니다. CPU 마다 스레드가 하나뿐이면 local counter 에는 경쟁이 없으므로 local lock 은 그리지 않았습니다. 단계 수와 대기 횟수는 이 모형에서 나온 값이며 측정값이 아닙니다. OSTEP 의 실험은 S 를 1024 로 두었고, 이 모형은 숫자를 작게 줄였습니다.

OSTEP 의 실험에서 S 를 1024 로 두었을 때, CPU 4개에서 카운터를 400만 번 늘리는 시간이 CPU 1개에서 100만 번 늘리는 시간과 거의 같았습니다.

global counter 는 아직 옮겨지지 않은 local 값만큼 실제 값보다 작을 수 있습니다. 그 차이는 최대 CPU 수 곱하기 S 입니다. deadlock 을 피하도록 local lock 과 global lock 을 모두 정해진 순서로 획득하면 정확한 값을 읽을 수 있지만 읽을 때마다 모든 lock 을 획득해야 하므로 확장되지 않습니다.

threshold Sglobal lock 경쟁global counter 와 실제 값의 차이
작게 둘 때많아서 lock 하나짜리 카운터에 가까워집니다작습니다
크게 둘 때적어서 잘 확장됩니다최대 CPU 수 곱하기 S 까지 커집니다

Java 의 LongAdder 도 같은 방법일까요?

Java 의 LongAdder 도 합계 하나를 여러 변수에 나눠 늘립니다. JDK 21 문서에 따르면 여러 스레드가 동시에 add() 를 불러 경쟁이 생기면 변수 집합이 늘어날 수 있고 sum() 은 그 변수들을 모두 더해 현재 합계를 돌려줍니다. 경쟁이 적을 때는 AtomicLong 과 특성이 비슷합니다. 경쟁이 심하면 공간을 더 쓰는 대신 AtomicLong 보다 기대 처리량이 크게 높습니다.

approximate counter 와 다른 점도 있습니다. LongAdder 에는 threshold 가 없고 값을 한 곳으로 모으지 않습니다. 읽을 때마다 모든 변수를 더하므로 global counter 처럼 아직 옮기지 않은 값 때문에 뒤처지지는 않습니다. 다만 sum() 은 원자적인 스냅숏이 아니어서 합계를 계산하는 동안 들어온 증가는 반영되지 않을 수 있습니다. JDK 문서에 따르면 LongAdder 는 통계 수집처럼 여러 스레드가 함께 갱신하는 합계에 알맞고, 정밀한 동기화 제어에는 알맞지 않습니다. 참고: LongAdder (JDK 21).

7. 연결 리스트의 노드마다 lock 을 걸면 더 빨라질까요?

lock 하나가 자료구조의 어디까지를 보호하는지를 lock granularity 라고 합니다. 자료구조 전체를 lock 하나로 보호하면 coarse-grained lock, 일부분마다 따로 lock 을 두면 fine-grained lock 이라고 부릅니다.

연결 리스트 전체에 lock 하나를 걸면 구현이 단순하고 맞는지 확인하기도 쉽습니다. 그러나 리스트의 서로 다른 부분을 다루는 스레드도 같은 lock 을 기다립니다.

노드마다 lock 을 두는 방법으로 hand-over-hand locking(lock coupling)이 있습니다. 리스트를 따라갈 때 다음 노드의 lock 을 먼저 획득한 뒤 현재 노드의 lock 을 풉니다. 여러 스레드가 리스트의 서로 다른 구간을 동시에 지나갈 수 있습니다.

OSTEP 에 따르면 실제로는 이 리스트를 lock 하나짜리 리스트보다 빠르게 만들기 어렵습니다. 노드를 하나 지날 때마다 lock 을 획득하고 해제하는 비용이 너무 크기 때문입니다. 리스트가 매우 길고 스레드가 많아도 마찬가지입니다. 몇 노드마다 lock 을 새로 획득하는 절충안은 OSTEP 이 조사해 볼 만한 방향으로 남겨 둡니다.

8. 큐와 해시 테이블은 lock 을 어디에서 나눌까요?

큐는 head 와 tail 에 lock 을 따로 둡니다

큐에서 enqueue 는 tail 에 노드를 붙이고 dequeue 는 head 에서 노드를 뗍니다. Michael 과 Scott 이 설계한 큐는 head 와 tail 에 lock 을 하나씩 둡니다.

typedef struct __queue_t {
    node_t *head;
    node_t *tail;
    pthread_mutex_t head_lock, tail_lock;
} queue_t;

enqueue 는 보통 tail_lock 만, dequeue 는 head_lock 만 획득하므로 두 연산이 동시에 실행될 수 있습니다. 큐를 초기화할 때 dummy node 를 하나 넣어 두는데, OSTEP 에 따르면 head 쪽 연산과 tail 쪽 연산을 나누려고 둡니다. 큐에 값이 하나도 없어도 dummy 가 남아 있으므로 enqueue 는 head 를, dequeue 는 tail 을 바꿀 일이 없습니다.

이 큐는 비어 있을 때 dequeue 하는 스레드를 기다리게 하지 못합니다. 큐가 비거나 가득 찼을 때 스레드를 기다리게 하는 bounded queue 는 OSTEP 다음 장의 condition variable 에서 다룹니다.

해시 테이블은 bucket 마다 lock 을 둡니다

OSTEP 의 해시 테이블은 bucket 마다 앞에서 만든 lock 하나짜리 연결 리스트를 둡니다. 리스트마다 lock 이 있으니 bucket 마다 lock 이 하나씩 생기고 서로 다른 bucket 을 다루는 연산은 동시에 실행됩니다.

  • Thread A 가 1번 bucket 에 삽입합니다.
  • Thread B 가 2번 bucket 에서 삭제합니다.
  • Thread C 가 3번 bucket 을 조회합니다.

세 스레드는 서로를 기다리지 않습니다. 같은 bucket 에 접근하는 스레드끼리만 경쟁합니다.

같은 iMac 에서 스레드 4개가 각각 1만 번에서 5만 번까지 삽입하는 실험에서, 삽입 횟수가 늘어도 이 해시 테이블의 실행 시간은 거의 늘지 않았고 lock 하나짜리 연결 리스트의 실행 시간은 크게 늘었습니다. 해시 테이블은 lock 을 나눈 위치가 데이터가 실제로 나뉘는 위치와 일치합니다. 키가 여러 bucket 에 고르게 퍼지면 경쟁도 함께 퍼집니다. 7절의 hand-over-hand 리스트는 lock 이 늘어난 만큼 모든 탐색이 더 많은 lock 을 거쳐야 했습니다.

이 효과는 bucket 이 충분하고 키가 고르게 퍼질 때 나옵니다. 특정 bucket 에 키가 몰리면 그 bucket 의 lock 에서 다시 경쟁이 생깁니다. OSTEP 의 예제는 크기를 바꾸지 않는 해시 테이블이고 resizing 을 처리하려면 동기화를 더 해야 합니다.

9. 처음 질문으로 돌아가면

lock 은 하드웨어와 운영체제의 도움을 받아 어떻게 만들어질까요? lock 을 기다리는 스레드는 CPU 를 쓰면서 기다려야 할까요? 자료구조에서 lock 을 잘게 나누면 더 빨라질까요?

구분방법대가
상호 배제test-and-set, CAS 같은 원자 명령으로 lock 상태를 확인하고 바꿉니다test-and-set spin lock 은 공정성을 보장하지 않습니다
공정성fetch-and-add 로 만든 ticket lock, 대기 큐번호나 큐를 관리해야 합니다
기다리는 비용spin, yield(), park() 와 futex 로 재우기, two-phase lockspin 은 CPU 를, sleep 은 시스템 호출과 context switch 를 씁니다
자료구조의 확장성approximate counter, head 와 tail lock 분리, bucket 별 lock읽는 값의 정확도가 떨어지거나 구현이 복잡해집니다

lock 은 하드웨어의 원자 명령으로 상호 배제를 얻습니다. 운영체제의 sleep 과 wakeup 지원이 있으면 기다리는 스레드는 대부분의 시간 동안 CPU 를 쓰지 않습니다. Linux 의 futex 기반 mutex 는 경쟁이 없을 때 커널에 들어가지 않고 경쟁이 있을 때만 잠듭니다.

lock 을 올바르게 걸어도 모든 스레드가 lock 하나를 두고 경쟁하면 OSTEP 의 카운터처럼 스레드를 늘릴수록 느려질 수 있습니다. 반대로 hand-over-hand 리스트처럼 lock 을 많이 나눠도 lock 을 다루는 비용 때문에 빨라지지 않을 수 있습니다. 카운터와 해시 테이블은 경쟁이 몰리는 지점을 나눠 OSTEP 의 실험에서 효과가 드러났습니다. 큐는 서로 독립적인 두 연산이 서로 다른 lock 을 쓰도록 나눴습니다.

28장은 lock 을 정확성, 공정성, 성능으로 평가했습니다. 자료구조에 lock 을 걸 때는 정확성(correctness), 동시에 실행할 수 있는 정도(concurrency), 성능(performance)을 따로 따져야 합니다. lock 하나로도 정확성은 얻을 수 있고 lock 을 나누면 concurrency 가 늘어납니다. 하지만 lock 이 늘수록 획득하고 해제하는 횟수가 늘고, 여러 lock 을 함께 획득하는 코드는 스레드마다 획득 순서가 다르면 deadlock 에 빠지기도 합니다. 코드도 그만큼 복잡해집니다.

OSTEP 은 29장을 마치며 Knuth 의 말(“Premature optimization is the root of all evil.”)을 인용해 처음에는 lock 하나로 올바른 자료구조를 만들고 성능 문제가 실제로 드러났을 때 나누라고 권합니다. Linux 도 멀티프로세서를 처음 지원할 때 커널 전체에 big kernel lock(BKL) 하나를 썼습니다. 멀티 CPU 시스템이 흔해져 이 lock 이 병목이 되자 여러 lock 으로 나눴습니다. lock 을 나눌지는 측정으로 병목을 확인한 뒤 정하고, 나눈 뒤에도 실제로 빨라졌는지 다시 측정해야 합니다.


학습 자료: Remzi H. Arpaci-Dusseau, Andrea C. Arpaci-Dusseau, Operating Systems: Three Easy Pieces, Chapter 28 Locks, Chapter 29 Lock-based Concurrent Data Structures. Linux man-pages, futex(2). Oracle, LongAdder (JDK 21).