[운영체제] Lock | 단순 Mutual Exclusion을 위한 Test-And-Set부터 성능까지 챙긴 Futex까지

지난번 포스팅에서는 프로세스와 스레드의 기본 개념부터, 공유 자원 접근 시 발생하는 경쟁 조건(Race Condition)의 위험성까지 다루었다. counter++라는 단 한 줄의 코드도 원자적으로 실행되지 않아 데이터 부정합을 일으킬 수 있다는 사실은, 동시성 프로그래밍이 얼마나 섬세한 접근을 요구하는지 보여주었다.

Race Condition Problem

이 문제를 해결하기 위해 상호 배제(Mutual Exclusion)가 필요하며, 가장 대표적인 도구가 바로 락(Lock)이다. 이번 시간에는 이 '락'이라는 것이 어떻게 구현되는지, 그 발전 과정을 따라가며 깊이 있게 학습한 내용을 기록하고자 한다.

1. 좋은 Lock의 조건

단순히 "임계 구역을 잠근다"는 개념을 넘어, 잘 만들어진 락은 다음 세 가지 기준을 만족해야 한다.

상호 배제 (Mutual Exclusion): 가장 기본적인 요건이다. 락은 임계 구역에 오직 하나의 스레드만 진입하도록 확실히 보장해야 한다.
공정성 (Fairness): 락을 기다리는 여러 스레드에게 기회가 공평하게 주어져야 한다. 특정 스레드가 계속해서 락을 얻지 못하고 무한정 기다리는 기아(Starvation) 상태에 빠져서는 안 된다.
성능 (Performance): 락을 획득하고 해제하는 과정 자체의 오버헤드가 적어야 한다. 특히, 락을 얻기 위해 대기하는 시간 동안 CPU 자원을 낭비해서는 안 된다.

이 세 가지 기준을 염두에 두고, 가장 원시적인 락의 구현 시도부터 살펴보자.

2. Lock 구현을 향한 여정 (실패의 역사)

시도 1: 인터럽트 비활성화

가장 단순하고 강력한 방법이다. 임계 구역에 진입하기 전에 모든 인터럽트를 비활성화하고, 빠져나올 때 다시 활성화하는 것이다. 인터럽트가 없다면 문맥 교환도 일어나지 않으므로, 임계 구역의 원자성은 완벽하게 보장된다.

Disabled Interrupt

하지만 이 방법은 수많은 문제점을 안고 있다.

애플리케이션에게 인터럽트를 제어할 권한을 주는 것은 시스템 전체를 위험에 빠뜨리는 일이다.
인터럽트가 오랫동안 비활성화되면 디스크 I/O 완료와 같은 중요한 이벤트를 놓칠 수 있다.
결정적으로, 멀티코어 프로세서에서는 전혀 동작하지 않는다. 한 CPU에서 인터럽트를 비활성화해도, 다른 CPU 코어의 스레드가 같은 임계 구역에 접근하는 것을 막을 수 없다.

시도 2: 단순 플래그를 이용한 스핀 락 (Spin Lock)

인터럽트 제어가 안된다면, 소프트웨어로 해결해 보자. 락의 상태를 나타내는 flag 변수 하나를 두는 것이다.

// flag가 0이면 사용 가능, 1이면 사용 중
while (flag == 1)
    ; // flag가 0이 될 때까지 계속 확인 (spinning)
flag = 1; // 락 획득

// --- 임계 구역 ---

flag = 0; // 락 해제

직관적으로는 그럴듯해 보이지만, 이 코드는 상호 배제를 보장하지 못한다. while (flag == 1) 검사와 flag = 1 설정 사이에는 보이지 않는 틈이 존재한다. 스레드 A가 flag가 0인 것을 확인하고 막 flag를 1로 바꾸려는 찰나에 문맥 교환이 발생했다고 가정해 보자. 스레드 B가 실행되어 flag가 여전히 0인 것을 확인하고, flag를 1로 설정한 뒤 임계 구역에 진입할 것이다. 이후 스레드 A가 다시 실행되면, 자신도 flag를 1로 설정하고 임계 구역에 진입해버린다. 두 스레드가 동시에 임계 구역에 진입한 것이다.

이 실패는 우리에게 중요한 교훈을 준다. "현재 상태를 확인하고, 그에 따라 상태를 변경하는" 작업은 반드시 하나의 원자적 단위로 묶여야 한다.

3. 하드웨어의 도움: 원자적 명령어

소프트웨어만으로는 '확인'과 '변경'을 묶을 수 없다는 한계에 부딪혔다. 이를 해결하기 위해 CPU 제조사들은 하드웨어 수준에서 원자성을 보장하는 특별한 명령어들을 제공한다.

Test-And-Set (or Atomic Exchange)

이 명령어는 이름 그대로, 특정 메모리 위치의 값을 확인하고(Test) 새로운 값으로 설정하는(Set) 것을 단 하나의, 분리될 수 없는 명령으로 수행한다.

// TestAndSet의 동작 원리
int TestAndSet(int *ptr, int new) {
    int old = *ptr; // 1. ptr이 가리키는 메모리의 현재 값을 읽어 old에 저장 
    *ptr = new;     // 2. ptr이 가리키는 메모리에 새로운 값(new)를 씀
    return old;     // 3. 처음에 읽은 옛날 값(old) 반환
}

이를 이용하면 앞서 실패했던 스핀 락을 올바르게 구현할 수 있다.

// flag의 초기값은 0
while (TestAndSet(&flag, 1) == 1)
    ; // 이전 값이 1이었다면 (누군가 락을 사용 중) 계속 스핀

// --- 임계 구역 ---

flag = 0; // 락 해제

TestAndSet

TestAndSet 자체가 원자적이므로, flag를 확인하고 1로 바꾸는 도중에 문맥 교환이 일어날 걱정이 없다.

평가:

상호 배제: 드디어 보장된다. (성공)
공정성: 전혀 보장되지 않는다. 운이 나쁜 스레드는 영원히 스핀할 수 있다. (실패)
성능: 락을 가진 스레드가 선점(preemption)되면 최악의 상황이 발생한다. 다른 모든 스레드는 깨어날 스레드를 기다리며 자신의 타임 슬라이스 전체를 스피닝으로 낭비한다. (실패)

Compare-And-Swap (CAS)

Test-And-Set과 유사하지만 조금 더 강력한 원자적 명령어로 Compare-And-Swap (CAS)이 있다.

// CAS의 동작 원리
int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;          // 1. ptr이 가리키는 메모리의 실제값을 읽음 
    if (actual == expected) {   // 2. 실제 값과 예상한(expected) 값이 같은지 비교
        *ptr = new;             // 3. 같다면, 새로운(new) 값으로 교체
    }
    return actual;              // 4. 비교 결과와 상관없이, 처음 읽은 실제값 반환
}

CAS는 세 개의 인자를 받는다: 메모리 주소(ptr), 예상되는 기존 값(expected), 그리고 새로운 값(new). 이 명령어는 *ptr의 값이 expected와 일치하는지 원자적으로 확인한다. 만약 일치한다면 *ptr의 값을 new로 바꾸고, 일치하지 않는다면 아무 작업도 하지 않는다. 어떤 경우든 *ptr의 원래 값을 반환한다.

이 "조건부 업데이트" 기능 덕분에 CAS는 단순 스핀 락 구현을 넘어, 여러 스레드가 락 없이 데이터 구조를 수정하는 락-프리(lock-free) 동기화를 구현하는 데 핵심적인 역할을 한다.

Fetch-And-Add 와 티켓 락 (Ticket Lock)

공정성 문제를 해결하기 위한 더 발전된 원자적 명령어가 Fetch-And-Add이다. 이 명령어는 특정 메모리 값을 1 증가시키고, 증가하기 전의 원래 값을 원자적으로 반환한다. 마치 은행 창구에서 번호표를 뽑는 것과 같다.

이를 이용해 매우 공정한 티켓 락을 만들 수 있다.

typedef struct {
    int ticket; // 다음에 발급할 티켓 번호
    int turn;   // 현재 서비스 중인 턴 번호
} lock_t;

void lock(lock_t *lock) {
    int myturn = FetchAndAdd(&lock->ticket, 1); // 내 번호표를 뽑는다
    while (lock->turn != myturn)
        ; // 내 차례가 올 때까지 스핀
}

void unlock(lock_t *lock) {
    FetchAndAdd(&lock->turn, 1); // 다음 사람을 부른다
}

모든 스레드는 lock()을 호출할 때 FetchAndAdd를 통해 고유한 myturn 번호를 받는다(ticket +=1). 그리고 unlock()이 호출될 때마다 turn 값이 순차적으로 증가(turn +=1)하므로, 스레드들은 번호표를 받은 순서대로 정확하게 임계 구역에 진입하게 된다. 이 방식은 먼저 온 순서대로 락을 획득하는 것을 보장하므로 기아 문제가 발생하지 않는다.

평가:

상호 배제: 보장된다. (성공)
공정성: 보장된다. (성공)
성능: 여전히 스피닝으로 인한 CPU 낭비 문제는 해결되지 않았다. (실패)

4. OS의 도움: 스피닝을 잠재우다

하드웨어의 도움으로 정확성과 공정성은 확보했지만, 스피닝은 여전히 큰 비효율을 낳는다. 락을 기다리는 동안 CPU를 낭비하는 대신, 차라리 다른 유용한 일을 하는 스레드에게 CPU를 양보하는 것이 현명하다. 여기서부터는 운영체제(OS)의 스케줄러 지원이 필요하다.

시도 1: 단순 양보 (Yield)

가장 간단한 OS 지원은 스피닝 대신 yield() 시스템 콜을 호출하는 것이다. yield()는 현재 실행 중인 스레드를 잠시 멈추고 실행 가능한 다른 스레드에게 CPU를 양보하라는 요청이다.

// 스핀 대신 yield() 사용
while (TestAndSet(&flag, 1) == 1)
    yield(); // CPU를 양보한다

하지만 이 접근법은 문맥 교환(context switch) 비용이라는 함정이 있다. 만약 락을 기다리는 스레드가 N개라고 가정해 보자. 최악의 경우, N-1개의 대기 중인 스레드가 각각 한 번씩 실행되었다가 yield() 하고, 다시 다음 대기 스레드로 문맥 교환되는 과정이 반복될 수 있다. 락을 가진 스레드가 잠들어 있는 동안, 시스템은 불필요한 문맥 교환만 수없이 반복하며 오버헤드를 발생시킨다. 또한 yield()는 스케줄러에게 힌트를 줄 뿐이라, 공정성(기아 문제)도 여전히 해결되지 않는다.

시도 2: 스핀 대신 잠들기 (Sleeping Instead of Spinning)

아이디어는 간단하다. 락을 얻을 수 없다면, 스레드를 대기 큐(wait queue)에 넣고 잠재우는(sleep) 것이다. 그리고 락을 해제하는 스레드가 대기 큐에서 잠들어 있는 스레드 중 하나를 깨워주면(wakeup) 된다.

이를 위해 park()(스레드를 잠재움)와 unpark(threadID)(특정 스레드를 깨움)와 같은 OS 시스템 콜이 필요하다.

하지만 이 방식에도 미묘한 경쟁 조건이 숨어있다. 스레드 B가 락을 확인하고 "이제 잠들어야겠다"고 결심한 후 park()를 호출하기 직전에 문맥 교환이 발생했다고 하자. 그 사이 락을 해제한 스레드 A가 unpark(B)를 호출한다. 스레드 A의 입장에서는 "B를 깨웠다"고 생각하지만, B는 아직 잠들지도 않았다. 이후 B가 다시 실행되어 예정대로 park()를 호출하면, 깨워줄 스레드는 이미 지나가 버렸기 때문에 영원히 잠들게 된다. 이를 Wakeup/Waiting Race 라고 한다.

Wakeup/Waiting Race

Solaris와 같은 운영체제는 setpark()라는 세 번째 시스템 콜을 도입해 이 문제를 해결한다. 스레드는 park()를 호출하기 전에 "나 곧 잠들거야"라는 의사를 setpark()를 통해 시스템에 미리 알린다. 만약 이 표시 이후, 실제 park()가 호출되기 전에 unpark()가 먼저 도착하면, 나중에 호출되는 park()는 스레드를 재우지 않고 즉시 반환된다.

Futex: 똑똑한 하이브리드 락

이러한 문제를 해결하기 위해 현대 OS는 더 정교한 메커니즘을 제공한다. 리눅스의 Futex (Fast Userspace Mutex)가 대표적이다.

Futex는 기본적으로 유저 공간에서 동작하는 락이다.

스레드는 먼저 유저 공간의 락 변수를 원자적 명령어로 확인한다.
만약 락이 사용 가능하면(경쟁이 없으면), 커널을 전혀 호출하지 않고 락을 바로 획득한다. 이 과정은 매우 빠르다.
만약 락이 이미 사용 중이라면(경쟁이 발생하면), 그때서야 futex_wait() 시스템 콜을 호출하여 커널에게 자신을 잠재워달라고 요청한다.
락을 해제하는 스레드는 futex_wake() 시스템 콜을 통해 대기 중인 스레드를 깨운다.

Futex

이 하이브리드 방식은 경쟁이 없는 대부분의 경우 커널 개입 없이 빠르게 동작하고, 경쟁이 발생했을 때만 OS의 도움을 받아 CPU 낭비 없이 효율적으로 대기하는, 두 세계의 장점을 모두 취한 방식이다.

결론

올바른 락을 하나 만드는 과정은 생각보다 훨씬 깊고 복잡한 여정이었다.

소프트웨어적 시도는 원자성 문제로 실패했다.
하드웨어 원자적 명령어의 도움으로 정확성(TestAndSet)과 공정성(FetchAndAdd)을 확보했지만, 성능(스피닝) 문제가 남았다.
최종적으로 OS 스케줄러의 도움(잠재우기와 깨우기)을 받아 성능까지 만족하는 현대적인 락이 완성되었다.

단순히 lock()과 unlock()을 호출하는 것을 넘어, 그 내부에서 하드웨어, OS, 그리고 라이브러리가 어떻게 상호작용하는지 이해하는 것은 동시성 버그를 디버깅하고 고성능 멀티스레드 프로그램을 설계하는 데 있어 필수적인 기반 지식이 될 것이다.

[운영체제] CPU 가상화 | Logical Control Flow에서 Context Switch까지

[운영체제] 운영체제란? | Virtualization, Concurrency, Persistence 핵심 개념 이해