하드웨어 동기화와 뮤텍스

임계 영역 문제를 해결하려면, 한 번에 하나의 스레드만 진입할 수 있도록 보장하는 메커니즘이 필요합니다.

Peterson 알고리즘의 순차 일관성 같은 가정을 실제 언어와 하드웨어에서 충족해야 합니다. 일반 변수의 읽기·쓰기만으로 그 보장을 대신할 수는 없습니다.

그래서 CPU가 원자적(atomic) 명령어를 하드웨어 수준에서 제공하고, 이를 기반으로 뮤텍스, 세마포어 등의 동기화 도구가 구축됩니다.

인터럽트 비활성화

가장 원시적인 방법입니다.

임계 영역에 진입하기 전에 인터럽트를 비활성화하면, 타이머 인터럽트가 발생하지 않아 선점되지 않습니다.

disable_interrupts();
// 임계 영역
enable_interrupts();

이 방법은 커널 내부의 짧은 임계 영역에서만 사용됩니다.

문제가 많기 때문입니다.

해당 CPU의 마스킹 가능한 인터럽트 처리가 지연됩니다. 다른 CPU나 마스킹 불가능한 인터럽트까지 모두 막는 것은 아닙니다.

멀티코어의 상호 배제를 이것만으로 해결할 수 없습니다. 다른 코어의 접근은 별도의 락 등으로 보호해야 합니다. 실제 커널 코드는 진입 전 인터럽트 상태도 올바르게 복원해야 합니다.

그리고 사용자 프로세스에게 인터럽트 비활성화 권한을 주면, 악의적인 프로세스가 CPU를 영원히 독점할 수 있습니다.

하드웨어 원자적 명령어

CPU는 읽기·수정·쓰기를 다른 접근에 대해 하나의 원자적 효과로 보이게 하는 연산을 제공합니다. 한 명령이나 재시도하는 명령 쌍으로 구현할 수 있으며, 다른 코어 전체를 멈추거나 주변의 모든 메모리 접근 순서까지 자동으로 보장한다는 뜻은 아닙니다.

Test-and-Set (TAS)

값을 읽고, 새 값을 쓰는 두 동작을 쪼갤 수 없는 하나의 연산으로 수행합니다.

/* 하드웨어가 원자적으로 수행 */
bool test_and_set(bool *target) {
    bool old = *target;
    *target = true;
    return old;
}

반환값이 false이면 이전에 잠겨 있지 않았고, 지금 잠겼다 → 락 획득 성공.

반환값이 true이면 이미 잠겨 있었다 → 락 획득 실패.

x86에서는 XCHG 명령어가 이 역할을 합니다.

ARM에서는 아키텍처 버전에 따라 exclusive load/store 쌍이나 LSE 원자 명령 등을 사용할 수 있습니다.

Compare-and-Swap (CAS)

기대되는 값과 현재 값이 같으면 새 값으로 교체하는 원자적 연산입니다.

TAS보다 범용적입니다.

/* 하드웨어가 원자적으로 수행 */
bool compare_and_swap(int *value, int expected, int new_value) {
    if (*value == expected) {
        *value = new_value;
        return true;   /* 성공 */
    }
    return false;      /* 실패: 비교 시점의 값이 expected와 다름 */
}

이 의사코드의 CAS 실패는 비교 시점에 현재 값이 기대값과 달랐다는 뜻입니다. 기대값 자체가 처음부터 틀릴 수도 있으므로 실패만으로 다른 스레드의 변경 이력을 증명할 수는 없습니다.

보통 루프를 돌면서 재시도합니다.

이것이 CAS 루프(또는 compare-and-swap loop) 패턴입니다.

void atomic_increment(int *counter) {
    int old_val, new_val;
    do {
        old_val = *counter;
        new_val = old_val + 1;
    } while (!compare_and_swap(counter, old_val, new_val));
}

x86에서는 CMPXCHG 명령어가 CAS를 수행합니다.

Java의 AtomicInteger.compareAndSet()이나 C++의 std::atomic::compare_exchange_weak()는 이와 같은 원자적 비교·교체를 제공합니다. 특정 CPU 명령으로의 대응은 구현에 달려 있으며, weak 비교·교체는 값이 같아도 허위 실패할 수 있어 재시도 규칙을 확인해야 합니다.

증가 루프에서 counter가 100일 때 A가 old_val=100, new_val=101을 계산했다고 합시다. 비교 전에 B가 원자적으로 101로 바꾸면 A의 CAS(기대 100, 새 값 101)는 실패하여 현재 101을 바꾸지 않습니다. A가 루프를 다시 돌면 이번에는 101을 새로 읽어 102를 계산하고, 그 사이 추가 변경이 없다면 CAS가 성공합니다. 실패 때 이전 new_val=101만 그대로 재사용하면 새로 읽은 상태의 증가를 놓칩니다. 이 의사코드는 루프의 재읽기로 기대값을 갱신하며, 실제 언어 API가 실패 시 기대값을 갱신하는 방식과는 구별합니다.

독립 확인: A가 8을 읽어 9를 계산한 뒤, 문제 조건상 B가 먼저 현재 값을 9로 바꿨습니다. A의 첫 CAS와, 다른 변경이 없는 재시도 뒤 최종 값은 어떻게 되나요?

CAS와 Lock-Free 프로그래밍

CAS의 강력함은 락 없이도 스레드 안전한 연산이 가능하다는 것입니다.

위 코드는 원자적 읽기와 CAS, 올바른 메모리 순서, 정수 범위 내 계산을 가정합니다. 일반 int와 위의 보통 C 함수 구현을 그대로 합쳐 실행하면 안전한 원자 연산이 되지 않습니다.

이것이 Lock-Free 프로그래밍의 기반입니다.

Lock-Free가 중요한 이유: 뮤텍스를 사용하면, 락을 잡은 스레드가 선점되거나 지연되면 다른 모든 스레드가 블로킹됩니다.

Lock-Free는 개별 스레드의 완료 상한이 아니라, 실행이 계속되는 동안 시스템 전체에서 연산의 진척을 보장하는 성질입니다. CAS를 사용했다는 사실만으로 전체 알고리즘이 lock-free가 되는 것은 아닙니다.

Java·C++·Rust의 atomic API는 원자적 읽기·쓰기와 RMW 등을 제공합니다. 지원 연산과 lock-free 여부는 언어·타입·대상 하드웨어의 계약을 확인합니다.

ABA 문제

CAS의 알려진 함정입니다.

값이 A → B → A로 변하면, CAS는 값이 여전히 A이므로 변경이 없었다고 판단합니다.

하지만 실제로는 변경이 있었습니다.

연결 리스트에서 이것이 문제가 될 수 있습니다.

해결책: 버전 번호를 함께 비교합니다.

Java의 AtomicStampedReference가 이 방법을 사용합니다.

CAS 루프는 성공과 실패만 보는 코드처럼 보이지만, 실제로는 읽은 값이 언제까지 유효한가를 계속 확인하는 낙관적 동시성 패턴입니다.

버전 표식은 ABA 탐지에 도움이 되지만 표식 순환과 노드 수명·메모리 회수 문제까지 자동으로 해결하지는 않습니다.

독립 확인: T1의 예상 쌍은 (A, 7)입니다. T2가 (B, 8), 이어 (A, 9)로 바꾸고 중간 표식 순환은 없다고 합시다. 값만 비교한 CAS와 값·버전 쌍을 원자적으로 비교한 CAS는 무엇을 다르게 판별하나요?

스핀락

스핀락(Spinlock)은 TAS로 구현하는 가장 단순한 동기화 방법입니다.

typedef struct {
    int locked;
} spinlock_t;

void spin_lock(spinlock_t *lock) {
    while (test_and_set(&lock->locked)) {
        /* 락이 풀릴 때까지 CPU를 태우며 반복 (busy waiting) */
    }
}

void spin_unlock(spinlock_t *lock) {
    lock->locked = 0;
}

락을 얻을 때까지 while 루프를 돌며 기다립니다.

이것을 바쁜 대기(Busy Waiting) 또는 스피닝(Spinning)이라고 합니다.

CPU가 아무 유용한 일을 하지 않으면서 계속 명령어를 실행합니다.

TAS의 반환값을 소유권과 연결하면 처음 잠금 값 false에서 A의 호출은 false를 반환하며 값을 true로 바꾸어 A가 획득합니다. 그 뒤 B가 호출하면 이전 값 true를 반환하므로 B는 진입하지 않습니다. A가 올바른 원자 해제로 false를 게시한 뒤 B의 다음 TAS가 false를 반환해야 B가 획득합니다. B의 반복 호출 횟수는 진입 횟수가 아니며, 해제와 획득의 메모리 순서도 실제 구현 계약에 포함됩니다.

스핀락이 효율적인 경우

스핀락은 무조건 나쁘지 않습니다.

멀티코어에서 락 소유자가 실행 중이고 대기가 매우 짧다면 재우고 깨우는 것보다 스핀이 유리할 수 있습니다. 성능 우위는 실제 경합과 측정에 달려 있습니다.

뮤텍스는 락 획득 실패 시 스레드를 슬립시키고, 나중에 깨웁니다.

이 과정에 커널 진입(시스템 콜) + 컨텍스트 스위칭이 필요합니다.

임계 영역이 수십 나노초만 지속된다면, 스레드를 재우고 깨우는 비용이 그냥 스피닝하는 비용보다 큽니다.

Linux 커널 내부의 짧은 임계 영역에서 스핀락이 광범위하게 사용됩니다.

사용자 공간에서는 뮤텍스가 일반적입니다.

스핀락이 위험한 경우

싱글코어 사용자 공간에서 소유자가 선점된 락을 스핀하면 CPU를 낭비할 수 있습니다. 커널의 선점·인터럽트 제어와 결합한 스핀락까지 모두 무의미하다는 뜻은 아닙니다.

락을 잡고 있는 스레드가 같은 코어에서 실행되고 있으므로, 스피닝하는 스레드가 CPU를 계속 점유하면 락을 잡고 있는 스레드가 실행되지 못합니다.

결국 타이머 인터럽트로 선점될 때까지 스피닝이 계속됩니다.

뮤텍스 (Mutex)

뮤텍스(Mutex, Mutual Exclusion Lock)는 스핀락의 바쁜 대기 문제를 해결합니다.

락을 얻지 못하면, 스레드를 슬립(Sleep) 상태로 전환하여 CPU를 양보합니다.

락이 풀리면 대기 중인 스레드를 깨웁니다.

이것을 Sleep-and-Wake 방식이라고 합니다.

C — pthread_mutex

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>

int counter = 0;
pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

void *increment(void *arg) {
    for (int i = 0; i < 1000000; i++) {
        pthread_mutex_lock(&lock);    /* 락 획득 (대기 가능) */
        counter++;                     /* 임계 영역 */
        pthread_mutex_unlock(&lock);   /* 락 해제 */
    }
    return NULL;
}

int main() {
    pthread_t t1, t2;
    pthread_create(&t1, NULL, increment, NULL);
    pthread_create(&t2, NULL, increment, NULL);
    pthread_join(t1, NULL);
    pthread_join(t2, NULL);
    printf("Counter: %d\n", counter);  /* 생성·잠금·join 성공 시 2000000 */
    return 0;
}

C 예제는 스레드 생성·잠금·join의 성공을 전제로 합니다. 반환 오류를 처리하지 않으므로 자원 실패 경로까지 보장하는 프로그램은 아닙니다.

두 작업의 루프는 각각 1,000,000번이고 같은 lock으로 모든 counter 증가를 보호합니다. 스레드 생성·잠금·두 join이 모두 정상 완료된 조건에서 합은 1,000,000+1,000,000=2,000,000입니다. 어느 스레드가 먼저 끝나는지나 번갈아 잠금을 얻는지는 이 값의 계산 조건이 아닙니다. main의 최종 읽기는 두 join 뒤이며, 한 작업만 기다리거나 보호 밖의 다른 쓰기를 추가하면 같은 근거를 그대로 적용할 수 없습니다.

pthread_mutex_lock()은 락을 획득합니다.

다른 스레드가 보유하면 획득 가능해질 때까지 대기합니다. 짧게 스핀할지 커널에서 잠들지는 구현에 달려 있습니다.

pthread_mutex_unlock()은 락을 해제하여 대기자가 획득할 수 있게 합니다. 바로 실행되거나 FIFO 순서로 획득한다는 보장은 아닙니다.

Python — threading.Lock

import threading

counter = 0
lock = threading.Lock()

def increment():
    global counter
    for _ in range(1_000_000):
        with lock:        # acquire() + 자동 release()
            counter += 1

t1 = threading.Thread(target=increment)
t2 = threading.Thread(target=increment)
t1.start(); t2.start()
t1.join(); t2.join()
print(f"Counter: {counter}")  # 두 작업이 정상 완료하면 2000000

with lock: 구문은 lock.acquire()를 호출하고 블록이 끝나면(예외가 발생해도) lock.release()를 호출합니다.

C에서는 조기 반환·오류 처리 경로에서 unlock을 빠뜨리지 않도록 관리해야 합니다. Python의 with는 해당 블록을 벗어날 때 해제를 구조화합니다.

뮤텍스 사용 주의 사항

잠금 타입 확인: POSIX의 NORMAL 뮤텍스 재잠금은 교착, ERRORCHECK는 오류, RECURSIVE는 재귀 횟수 증가입니다. DEFAULT를 모든 환경에서 동일하다고 가정하지 않습니다. Python Lock도 재진입 락이 아닙니다.

재진입이 필요하면 재진입 뮤텍스(Recursive Mutex)를 사용합니다.

pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_RECURSIVE)로 설정합니다.

최소 범위 잠금: 임계 영역은 최대한 짧아야 합니다.

락 안에서 I/O, 네트워크 호출, 대용량 연산을 하면 다른 스레드가 오래 대기합니다.

락 순서 일관성: 여러 뮤텍스를 사용할 때, 항상 같은 순서로 잡아야 합니다.

A → B와 B → A의 획득 경로가 겹쳐 서로의 락을 기다리면 데드락이 발생할 수 있습니다.

7장에서 자세히 다룹니다.

뮤텍스 vs 스핀락 비교

Futex — 두 세계의 장점

Linux의 Futex(Fast Userspace Mutex)는 사용자 공간 잠금 구현을 지원하는 대기·깨우기 커널 기능입니다. 독립적인 세 번째 락 종류나 스핀 단계를 필수로 포함하는 API는 아닙니다.

일반적인 비경합 경로는 커널 진입 없이 사용자 공간 원자 연산으로 락을 획득합니다.

사용자 공간에서 대기할 필요가 생기면 futex를 통해 커널의 도움을 받을 수 있습니다. 기대값이 이미 바뀌었다면 대기 요청이 잠들지 않고 반환할 수도 있습니다.

Linux의 glibc pthread 뮤텍스 구현은 futex를 활용합니다. POSIX 자체가 이 내부 구현을 요구하는 것은 아닙니다.

Futex의 대기는 기대값 검사와 수면 진입을 연결하여 놓친 깨우기를 방지하도록 돕습니다. 깨우기는 락 소유권을 바로 넘기는 것이 아니므로 구현은 깨어난 뒤 다시 상태를 확인합니다. 짧은 스핀을 먼저 할지는 뮤텍스 타입과 구현의 선택입니다.

다음 절에서는 뮤텍스보다 더 유연한 동기화 도구인 세마포어를 다루겠습니다.