동기화 문제의 본질

여러 스레드를 쓰는 프로그램이 열 번 가운데 아홉 번은 맞는 결과를 내다가 한 번만 틀린 값을 낸다면, 가장 먼저 의심할 것은 동기화 문제입니다. 물론 입력이나 외부 상태가 달라서일 수도 있으므로 실행 순서와 공유 상태를 함께 살펴야 하지만, 동기화 문제는 특히 고약합니다. 개발하는 동안에는 거의 드러나지 않다가 운영 환경에서 부하가 높아질 때 나타나고, 디버거로 멈춰 보면 실행 순서가 바뀌어 다시 일어나지 않기도 합니다.

4장에서 스레드가 메모리를 함께 쓴다는 것이 장점이라고 했습니다. IPC 없이 전역 변수 하나로 데이터를 주고받을 수 있으니까요. 그런데 바로 이 공유가 동기화 문제의 원인입니다. 이 글에서는 여러 스레드가 같은 데이터를 고칠 때 무엇이 잘못되는지, 그것을 막으려면 어떤 조건을 지켜야 하는지 살펴봅니다.

두 번 더했는데 1이 되는 이유

두 스레드가 공유 변수 counter를 0에서 시작해 각자 1씩 더한다고 합시다. 결과는 당연히 2여야 할 것 같습니다. 그런데 counter++는 소스 코드에서는 한 줄이지만, CPU에서는 세 단계로 실행됩니다.

1. 메모리에서 counter의 값을 레지스터로 읽습니다(LOAD).
2. 레지스터의 값에 1을 더합니다(ADD).
3. 결과를 메모리에 씁니다(STORE).

스레드는 이 세 단계 사이 어디에서든 다른 스레드와 순서가 섞일 수 있습니다. 다음 단계 개념도는 두 스레드가 모두 0을 읽은 뒤 차례로 쓰는 순서를 보여 줍니다.

A가 0을 읽어 1을 계산하고 아직 쓰지 않았을 때 B도 0을 읽어 1을 계산합니다. A가 1을 쓰고, B도 자기가 계산한 1을 씁니다. 두 스레드가 모두 더했지만, B가 A의 결과를 보지 못한 채 낡은 값으로 덮어써 한 번의 증가가 사라졌습니다. 이를 갱신 손실(lost update)이라고 합니다.

어떤 순서에서 이런 일이 생기는지 직접 세어 볼 수 있습니다. 다음 Python 코드는 각 스레드의 세 단계를 제너레이터로 나누고, 정해 준 순서대로 한 단계씩 실행합니다. 실제 스레드를 쓰지 않고 순서를 직접 정하므로, 언제 실행해도 같은 결과가 나옵니다.

from itertools import permutations

def increment(state, name, log):
    local = state["counter"]           # 1. 읽기(LOAD)
    log.append(f"{name} 읽기 {local}")
    yield
    local += 1                         # 2. 더하기(ADD)
    yield
    state["counter"] = local           # 3. 쓰기(STORE)
    log.append(f"{name} 쓰기 {local}")
    yield

def run(order):
    """order의 글자 순서대로 A와 B를 한 단계씩 실행한다."""
    state, log = {"counter": 0}, []
    threads = {"A": increment(state, "A", log), "B": increment(state, "B", log)}
    for name in order:
        next(threads[name])
    return state["counter"], log

for order in ("AAABBB", "ABABAB"):
    result, log = run(order)
    print(order, "->", result, "|", ", ".join(log))

orders = sorted(set(permutations("AAABBB")))
lost = sum(1 for order in orders if run(order)[0] == 1)
print(f"가능한 순서 {len(orders)}가지 가운데 증가가 사라지는 순서: {lost}가지")

AAABBB -> 2 | A 읽기 0, A 쓰기 1, B 읽기 1, B 쓰기 2
ABABAB -> 1 | A 읽기 0, B 읽기 0, A 쓰기 1, B 쓰기 1
가능한 순서 20가지 가운데 증가가 사라지는 순서: 18가지

A가 세 단계를 모두 마친 뒤 B가 시작하면 B는 1을 읽어 2를 쓰므로 결과가 맞습니다. 하지만 두 스레드의 세 단계를 섞는 20가지 순서 가운데, 한 스레드가 끝난 뒤 다른 스레드가 시작하는 두 가지를 빼면 나머지 18가지에서 모두 증가가 사라집니다. 한 스레드의 읽기와 쓰기 사이에 다른 스레드의 읽기가 끼어들기만 하면 되기 때문입니다. 실제 프로그램에서는 세 단계가 몇 나노초 만에 지나가므로 그 사이에 전환될 확률이 낮고, 그래서 버그가 가끔만 나타납니다. 이 모델은 순서의 가짓수를 센 것이지 확률을 잰 것은 아니지만, 겹치기만 하면 거의 언제나 틀린다는 점을 보여 줍니다.

이처럼 실행 순서에 따라 결과가 달라지는 상황을 경쟁 조건(race condition)이라고 합니다. 여러 실행 흐름이 공유 자원에 먼저 닿으려고 경주하는 모습에서 붙은 이름입니다. 그 가운데 메모리 수준의 경쟁, 곧 여러 스레드가 같은 메모리 위치에 접근하고, 적어도 하나가 쓰며, 그 접근들이 동기화되지 않은 경우를 특히 데이터 경쟁(data race)이라고 부릅니다. 읽기만 하는 접근끼리는 데이터 경쟁이 생기지 않으며, 위험한 것은 읽기와 쓰기, 또는 쓰기와 쓰기가 겹칠 때입니다. C와 C++에서 데이터 경쟁은 정의되지 않은 동작이므로, 위 모델처럼 증가 하나가 사라지는 정도로 끝난다고 기대할 수도 없습니다.

실무에서 만나는 경쟁 패턴

경쟁 조건은 교과서의 counter++에만 있는 것이 아닙니다. 실무 코드에서 자주 보이는 모양은 크게 세 가지입니다.

첫째는 확인 후 행동(check-then-act)입니다. "사용자가 없으면 만든다"처럼 조건을 확인하는 단계와 그에 따라 행동하는 단계가 따로 일어나는 경우입니다. 두 요청이 거의 동시에 들어와 둘 다 "아직 없다"고 확인하면, 둘 다 사용자를 만듭니다. 사용자 정보를 딕셔너리에 담는다면 같은 키에 두 번 대입해 하나만 남을 수 있지만, 그사이 환영 메일을 보내는 것 같은 부수 효과는 두 번 일어납니다. 데이터베이스라면 같은 사용자 레코드가 두 개 생길 수도 있는데, 이는 유일성 제약이 있는지에 달려 있습니다.

둘째는 읽고 고치고 쓰기(read-modify-write)로, 앞의 counter++가 바로 이 모양입니다. 잔액을 읽고, 충분한지 확인하고, 줄인 잔액을 쓰는 출금도 같습니다. 다음 코드는 잔액 1,000원인 계좌에서 두 요청이 각각 800원을 출금할 때, 순서에 따라 무엇이 달라지는지 보여 줍니다.

def withdraw(account, amount, paid):
    balance = account["balance"]               # 잔액 읽기
    yield
    if balance >= amount:                      # 검사
        account["balance"] = balance - amount  # 차감한 잔액 쓰기
        paid.append(amount)                    # 돈을 내준다
    yield

for order in ("AABB", "ABAB"):
    account, paid = {"balance": 1000}, []
    requests = {"A": withdraw(account, 800, paid), "B": withdraw(account, 800, paid)}
    for name in order:
        next(requests[name])
    print(f"{order}: 남은 잔액 {account['balance']}원, 내준 돈 {sum(paid)}원")

AABB: 남은 잔액 200원, 내준 돈 800원
ABAB: 남은 잔액 200원, 내준 돈 1600원

A가 끝난 뒤 B가 시작하면 B는 200원을 읽어 출금을 거절하므로 정상입니다. 두 요청이 모두 1,000원을 읽은 뒤 진행하면, 둘 다 검사를 통과해 800원씩 1,600원을 내주고, 각자 200원을 써서 잔액은 200원이 됩니다. 남은 잔액만 보면 한 번 출금한 것처럼 보여 문제를 알아채기 어렵다는 점이 무섭습니다. 이 경우 보호해야 할 범위는 잔액을 쓰는 한 줄이 아니라 잔액을 읽고, 검사하고, 쓰고, 돈을 내주는 과정 전체입니다. 실제 데이터베이스에서는 트랜잭션이나 "잔액이 충분할 때만 줄인다"는 조건부 갱신으로 이 과정을 한 덩어리로 묶으며, 그 방법은 데이터베이스 교재의 격리 수준과 잠금에서 다룹니다.

셋째는 확인 시점과 사용 시점의 차이(time-of-check to time-of-use, TOCTOU)로, 파일 시스템에서 흔합니다. 파일이 있는지 확인한 뒤 그 파일을 여는 사이에 다른 프로세스가 파일을 지우거나 다른 파일로 바꿔치기할 수 있습니다. 보안 문제로 이어지는 경우도 많아서, 확인과 사용을 따로 하지 말고 open()에 O_CREAT | O_EXCL을 주어 "없을 때만 만든다"를 한 번의 시스템 콜로 하는 식으로 피합니다.

임계 영역과 세 가지 조건

공유 데이터에 접근하는 코드 가운데, 여러 스레드가 동시에 실행하면 경쟁 조건이 생기는 부분을 임계 영역(critical section)이라고 합니다. 앞의 예에서는 counter++가, 출금에서는 잔액을 읽고 검사하고 쓰는 부분 전체가 임계 영역입니다. 임계 영역 문제를 제대로 풀었다고 하려면 다음 세 조건을 모두 만족해야 합니다.

첫째, 상호 배제(mutual exclusion)입니다. 한 스레드가 임계 영역 안에 있으면 다른 스레드는 들어갈 수 없어야 합니다. 가장 기본적인 요구로, 이것이 깨지면 앞에서 본 갱신 손실이 생깁니다.

둘째, 진행(progress)입니다. 임계 영역에 아무도 없고 들어가려는 스레드가 있다면, 그 가운데 하나는 유한한 시간 안에 들어갈 수 있어야 합니다. 아무도 안에 없는데 서로 양보만 하다가 아무도 들어가지 못한다면, 상호 배제는 지켰어도 쓸모가 없습니다. 이렇게 스레드들이 계속 움직이는데도 진척이 없는 상태를 라이브락(livelock)이라고 합니다.

셋째, 한정 대기(bounded waiting)입니다. 어떤 스레드가 들어가겠다고 요청한 뒤, 다른 스레드들이 먼저 들어가는 횟수에 한도가 있어야 합니다. 그렇지 않으면 특정 스레드가 운 나쁘게 계속 밀려 영원히 들어가지 못하는 기아가 생길 수 있습니다.

첫째 조건은 나쁜 일이 일어나지 않는다는 안전성(safety)에 대한 것이고, 둘째와 셋째는 좋은 일이 결국 일어난다는 생존성(liveness)에 대한 것입니다. 두 성질은 따로 따져야 합니다. 예를 들어 일반적인 뮤텍스 라이브러리는 상호 배제는 지켜 주지만, 기다린 순서대로 들어가게 하거나 대기 횟수에 한도를 두는 것까지 약속하지는 않는 경우가 많습니다. 동기화 버그를 만났을 때 이 세 조건 가운데 무엇이 깨졌는지부터 나누어 보면, 원인과 해결책을 빨리 좁힐 수 있습니다.

소프트웨어만으로 상호 배제 만들기: 피터슨 알고리즘

하드웨어의 도움 없이 소프트웨어만으로 상호 배제를 만들려는 시도도 있었습니다. 그 가운데 두 스레드를 위한 간결한 해법이 1981년에 발표된 피터슨 알고리즘(Peterson's algorithm)입니다.

int flag[2] = {0, 0};   /* flag[i]가 1이면 스레드 i가 들어가고 싶다는 뜻 */
int turn;               /* 둘 다 원할 때 누구에게 양보할지 */

void enter_section(int i)
{
    int j = 1 - i;      /* 상대 스레드 */
    flag[i] = 1;        /* 나도 들어가고 싶다. */
    turn = j;           /* 하지만 너에게 먼저 양보한다. */
    while (flag[j] && turn == j)
        ;               /* 상대도 원하고 상대 차례라면 기다린다. */
}

void leave_section(int i)
{
    flag[i] = 0;
}

각 스레드는 들어가고 싶다는 표시를 한 뒤 상대에게 차례를 양보합니다. 둘이 동시에 들어가려 하면 turn에는 나중에 쓴 값이 남으므로, 나중에 양보한 쪽이 기다리고 먼저 양보한 쪽이 들어갑니다. 상대가 들어갈 생각이 없으면 flag[j]가 0이어서 바로 들어갑니다. 명령어가 쓰인 순서대로 실행되고 메모리에 쓴 값이 모든 스레드에 같은 순서로 보인다는 순차 일관성(sequential consistency)을 가정하면, 이 알고리즘은 세 조건을 모두 만족합니다.

더 깊이: 순서 하나가 바뀌면 깨진다

문제는 오늘날의 컴퓨터가 순차 일관성을 그대로 지켜 주지 않는다는 것입니다. 컴파일러는 최적화를 위해 서로 관계없어 보이는 메모리 접근의 순서를 바꾸고, CPU도 쓰기를 버퍼에 모았다가 나중에 내보내는 등 순서를 바꾸어 실행합니다. 저장 버퍼가 순차 일관성에서는 나올 수 없는 결과를 만드는 과정은 컴퓨터구조 교재의 두 변수로 메모리 순서 비교하기에서 따라가 볼 수 있습니다. 피터슨 알고리즘에서 flag[i] = 1과 turn = j의 순서가 바뀌면 어떻게 될까요? 다음 코드는 두 스레드의 모든 실행 순서를 하나씩 탐색해, 두 스레드가 동시에 임계 영역에 들어가는 순서가 있는지 찾습니다.

from collections import deque

def program(i, swapped):
    """스레드 i가 실행하는 명령. 'cs'에 도착한 스레드는 임계 영역 안에 있다."""
    j = 1 - i
    set_flag, set_turn = ("flag", i, 1), ("turn", j)
    first, second = (set_turn, set_flag) if swapped else (set_flag, set_turn)
    return [first, second, ("wait", j), ("cs",), ("flag", i, 0)]

def describe(i, op):
    if op[0] == "flag":
        return f"T{i}: flag[{op[1]}] = {op[2]}"
    if op[0] == "turn":
        return f"T{i}: turn = {op[1]}"
    return f"T{i}: 대기 검사 통과"

def find_violation(swapped):
    """두 스레드가 동시에 임계 영역에 있는 실행 순서를 모두 찾아본다."""
    progs = [program(0, swapped), program(1, swapped)]
    start = ((0, 0), (0, 0), 0)
    queue, seen = deque([(start, ())]), {start}
    while queue:
        (pcs, flag, turn), trace = queue.popleft()
        if pcs == (3, 3):
            return trace
        for i in (0, 1):
            if pcs[i] >= len(progs[i]):
                continue
            op = progs[i][pcs[i]]
            new_flag, new_turn, advance = list(flag), turn, True
            if op[0] == "flag":
                new_flag[op[1]] = op[2]
            elif op[0] == "turn":
                new_turn = op[1]
            elif op[0] == "wait":
                advance = not (flag[op[1]] and turn == op[1])   # 조건이 참이면 제자리에서 기다린다
            new_pcs = list(pcs)
            new_pcs[i] += advance
            state = (tuple(new_pcs), tuple(new_flag), new_turn)
            if state not in seen:
                seen.add(state)
                step = describe(i, op) if advance or op[0] != "wait" else None
                queue.append((state, trace + ((step,) if step else ())))
    return None

for swapped in (False, True):
    trace = find_violation(swapped)
    label = "turn 먼저 쓰기" if swapped else "원래 순서"
    print(f"{label}: " + ("두 스레드가 함께 들어가는 순서 없음" if trace is None else " -> ".join(trace)))

원래 순서: 두 스레드가 함께 들어가는 순서 없음
turn 먼저 쓰기: T0: turn = 1 -> T1: turn = 0 -> T1: flag[1] = 1 -> T1: 대기 검사 통과 -> T0: flag[0] = 1 -> T0: 대기 검사 통과

원래 순서에서는 가능한 모든 실행 순서를 다 살펴도 두 스레드가 함께 들어가는 경우가 없습니다. 하지만 두 쓰기의 순서를 바꾸면 깨지는 순서가 나옵니다. T0이 turn = 1을 쓰고, T1이 turn = 0을 쓴 뒤 flag[1] = 1을 씁니다. T1이 대기 조건을 검사할 때 T0은 아직 flag[0]을 쓰지 않았으므로 바로 들어갑니다. 그 뒤 T0이 flag[0] = 1을 쓰고 검사하면, turn이 0이어서 자기 차례이므로 역시 들어갑니다. 쓰기 순서 하나가 바뀌었을 뿐인데 상호 배제가 깨진 것입니다.

그래서 위의 C 코드를 그대로 여러 스레드에서 실행하면 안 됩니다. 일반 int 변수를 동기화 없이 함께 읽고 쓰는 것은 데이터 경쟁이어서 정의되지 않은 동작이고, 컴파일러와 CPU의 순서 바꾸기를 막지도 못합니다. C11의 원자 변수를 쓰면 이 문제를 고칠 수 있습니다. atomic_load와 atomic_store는 따로 지정하지 않으면 가장 강한 순서인 순차 일관성을 지키므로, 피터슨 알고리즘이 가정한 순서가 보장됩니다.

#include <stdatomic.h>

static atomic_int flag[2];
static atomic_int turn;

void enter_section(int i)
{
    int j = 1 - i;
    atomic_store(&flag[i], 1);
    atomic_store(&turn, j);
    while (atomic_load(&flag[j]) && atomic_load(&turn) == j)
        ;   /* 바쁜 대기 */
}

void leave_section(int i)
{
    atomic_store(&flag[i], 0);
}

그래도 실무에서 피터슨 알고리즘을 쓸 일은 거의 없습니다. 두 스레드에만 쓸 수 있고, 기다리는 동안 CPU를 계속 쓰며, 오늘날의 CPU에는 다음 글에서 볼 원자적 명령어와 이를 바탕으로 잘 검증된 잠금 라이브러리가 있기 때문입니다. 피터슨 알고리즘의 가치는 상호 배제를 만드는 원리와, 메모리 순서가 얼마나 중요한지를 보여 준다는 데 있습니다.

경쟁을 찾는 도구

경쟁 조건은 특정 실행 순서에서만 드러나므로 일반 디버거로는 찾기 어렵습니다. 대신 프로그램의 메모리 접근을 지켜보며 경쟁을 찾아 주는 도구를 씁니다. 대표적인 것이 GCC와 Clang에 들어 있는 ThreadSanitizer(TSan)입니다.

gcc -fsanitize=thread -g -o program program.c -pthread
./program                                  # 데이터 경쟁을 발견하면 보고서를 출력한다
valgrind --tool=helgrind ./program         # Valgrind의 Helgrind로 검사

TSan으로 빌드한 프로그램은 실행 중에 각 메모리 접근이 어떤 동기화로 순서가 정해졌는지 추적하다가, 동기화 없이 겹친 접근을 찾으면 두 접근의 스택 추적과 함께 보고합니다. Valgrind의 Helgrind도 비슷한 일을 합니다. 다만 이런 도구는 그 실행에서 실제로 지나간 경로만 검사하므로, 보고가 없다고 모든 경로가 안전하다는 뜻은 아닙니다. 또 확인 후 행동처럼 개별 접근은 잠금으로 보호되어 있지만 두 단계 사이가 비어 있는 논리적 경쟁은 데이터 경쟁이 아니어서 찾지 못합니다. 이런 경쟁은 어떤 조건이 함께 지켜져야 하는지를 따져 보는 설계 검토로 찾아야 합니다.

상호 배제와 실행 순서는 다른 문제다

지금까지는 여러 스레드가 같은 데이터를 동시에 고치지 못하게 하는 상호 배제를 다루었습니다. 동기화에는 또 다른 종류가 있는데, 어떤 일이 끝나야 다음 일을 시작할 수 있다는 실행 순서의 조건입니다. 입력을 읽는 작업 A가 끝나면 서로 관계없는 변환 B와 C를 함께 실행하고, 두 결과를 합치는 D는 B와 C가 모두 끝난 뒤에 실행해야 한다고 합시다. 이 의존 관계는 A에서 B와 C로, B와 C에서 D로 가는 화살표로 그릴 수 있습니다. B와 C는 서로 순서가 없으므로 함께 실행할 수 있지만, D는 둘이 끝났다는 것을 확인해야 합니다.

이런 흐름을 설명할 때 작업이 갈라지는 것을 fork, 다시 합쳐지는 것을 join이라고 부르기도 합니다. 이것을 3장의 fork() 시스템 콜과 혼동하지 않아야 합니다. fork()는 메모리를 복사한 프로세스를 만들 뿐이고, 자식의 결과를 받으려면 wait()와 IPC를 따로 써야 합니다. 스레드의 join도 스레드가 끝나기를 기다려 줄 뿐, 결과를 합치는 일은 프로그램이 해야 합니다. 실행 순서의 조건을 만드는 도구는 6장의 세마포어와 조건 변수에서 다룹니다.

정리

• 실행 순서에 따라 결과가 달라지는 상황을 경쟁 조건이라고 합니다. counter++처럼 읽고 고치고 쓰는 연산은 단계 사이에 다른 스레드가 끼어들면 갱신이 사라질 수 있습니다.
• 여러 스레드가 같은 메모리에 접근하고, 하나라도 쓰며, 동기화되지 않으면 데이터 경쟁이며, C와 C++에서는 정의되지 않은 동작입니다.
• 실무의 경쟁은 확인 후 행동, 읽고 고치고 쓰기, 확인 시점과 사용 시점의 차이 같은 모양으로 나타나며, 보호해야 할 범위는 함께 지켜져야 하는 조건 전체입니다.
• 임계 영역 문제의 해법은 상호 배제, 진행, 한정 대기를 모두 만족해야 합니다. 상호 배제는 안전성, 나머지 둘은 생존성에 대한 조건입니다.
• 피터슨 알고리즘은 순차 일관성을 가정하면 올바르지만, 컴파일러와 CPU가 메모리 접근의 순서를 바꾸면 깨지므로 원자 변수 같은 순서 보장 장치가 필요합니다.
• 데이터 경쟁은 TSan 같은 도구로 찾을 수 있지만, 논리적 경쟁은 설계 검토가 필요합니다. 상호 배제와 실행 순서의 조건은 서로 다른 동기화 문제입니다.

연습 문제

1. 7에서 시작한 두 덧셈

공유 값이 7이고, 스레드 A는 2를, B는 3을 더합니다. 두 스레드가 모두 7을 읽은 뒤 A가 먼저 쓰고 B가 나중에 쓴다면 최종 값은 얼마인가요? 두 덧셈이 모두 반영되었다면 얼마여야 하나요?

2. 사용자 생성의 경쟁

다음 코드는 여러 스레드에서 동시에 불립니다. 두 요청이 같은 username으로 거의 동시에 들어오면 어떤 일이 생길 수 있는지 설명하고, 고치는 방법을 두 가지 제시하세요.

users = {}

def register(username, send_welcome_mail):
    if username not in users:
        users[username] = {"name": username}
        send_welcome_mail(username)

3. 결과를 기다리는 데 잠금이 충분할까

변환 작업 B와 C를 함께 실행하고, 합치는 작업 D는 두 결과 파일을 읽어 합칩니다. B만 끝났을 때 D가 시작되어 아직 완성되지 않은 C의 결과 파일을 읽는 문제가 생겼습니다. 동료가 "파일에 접근할 때 잠금을 걸면 된다"고 했습니다. 이 제안으로 문제가 해결될까요?

다음 글 하드웨어 동기화와 뮤텍스에서는 CPU가 제공하는 원자적 명령어와, 이를 바탕으로 만든 스핀락과 뮤텍스를 살펴봅니다.