공유 자원 동기화는 운영체제가 아니라 CPU 원자적 명령어가 보장한다

스레드 네 개가 같은 변수를 각각 100만 번씩 1 증가시키면 400만이 나와야 한다. 실제로 돌려 보면 300만이 나오고, 다시 돌리면 220만이 나온다. 같은 코드인데 실행할 때마다 답이 다르다

이 문제를 잠금으로 막는다는 것까지는 알려져 있는데, 잠금이 실제로 어디서 일어나는지는 덜 알려져 있다. 스레드 네 개가 400만 번 잠그고 푸는 동안 커널에 들어간 횟수를 세어 보면 1,597번이다. 0.04%다. 나머지 99.96%는 CPU 명령어 하나로 사용자 공간에서 끝난다

공유 자원 동기화를 임계구역과 경쟁 조건에서 시작해 세마포어와 모니터, 교착상태의 네 조건과 은행원 알고리즘까지 따라간다. 잠금이 깨지는 장면과 교착상태에 빠지는 장면은 실제로 만들어 붙였다

이 글에서 자주 나오는 용어

• 공유 자원(Shared Resource): 둘 이상의 실행 흐름이 함께 쓰는 변수·파일·장치
• 임계구역(Critical Section): 한 번에 하나만 들어가야 하는 코드 구간
• 경쟁 조건(Race Condition): 접근 순서에 따라 결과가 달라지는 상태
• 세마포어(Semaphore): 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제어하기 위해 사용하는 정수 변수 기반의 동기화 기법
• 상호배제(Mutual Exclusion): 임계구역에 하나만 들어가도록 막는 것
• 원자적 연산(Atomic Operation): 중간에 끼어들 수 없는 하나의 CPU 명령어로 처리되는 연산
• futex: 리눅스의 잠금 지원 기능. 경쟁이 없으면 커널에 가지 않고 사용자 공간에서 끝난다
• 교착상태(Deadlock): 서로가 쥔 자원을 기다리다 아무도 진행하지 못하는 상태
• 안전 상태(Safe State): 모든 프로세스를 끝까지 실행시킬 수 있는 순서가 하나라도 존재하는 상태

공유 자원을 동시에 건드리면 결과가 매번 달라진다

counter = counter + 1은 한 줄이지만 CPU가 보기에는 세 단계다. 메모리에서 읽고, 레지스터에서 더하고, 메모리에 쓴다. 두 스레드가 이 세 단계를 겹쳐서 실행하면 한쪽의 증가가 사라진다

스레드 A                   스레드 B                  counter
읽기 → 10                                            10
                          읽기 → 10                  10
더하기 → 11                                          10
                          더하기 → 11                10
쓰기                                                 11
                          쓰기                       11   ← 두 번 더했는데 1만 늘었다

이 그림이 실제로 얼마나 자주 일어나는지 재 봤다. 스레드 네 개가 같은 long 변수를 각각 100만 번 증가시키고, 아무 보호 없이 실행했다

보호 없음 | 기대값 4000000 | 실제값  3013330 | 잃어버린 증가   986670 (24.67%)
보호 없음 | 기대값 4000000 | 실제값  3015076 | 잃어버린 증가   984924 (24.62%)
보호 없음 | 기대값 4000000 | 실제값  2206429 | 잃어버린 증가  1793571 (44.84%)
보호 없음 | 기대값 4000000 | 실제값  2233349 | 잃어버린 증가  1766651 (44.17%)
보호 없음 | 기대값 4000000 | 실제값  2953257 | 잃어버린 증가  1046743 (26.17%)

다섯 번 실행해서 다섯 번 다 다른 값이 나왔고, 증가의 4분의 1에서 절반 가까이가 사라졌다. 여러 프로세스나 스레드가 동시에 쓰면 안 되는 이 구간이 임계구역이고, 서로 먼저 들어가려고 다투는 상황이 경쟁 조건이다

여기서 눈여겨볼 것은 손실률이 아니라 값이 매번 다르다는 점이다. 같은 입력에 같은 코드인데 출력이 달라지면 테스트로 잡기가 어렵다. 이 성질 때문에 동기화 버그는 운영 환경에서 처음 드러나는 경우가 많다

프로세스끼리 데이터를 주고받는 방법은 두 갈래다

경쟁 조건은 데이터를 함께 쓰기 때문에 생긴다. 그러면 함께 쓰는 방법부터 정리해야 한다. 프로세스 간 통신(IPC)은 크게 둘로 나뉜다

방식	종류	성질
메시지 전달	파이프, 메시지 큐, 소켓	메모리를 공유하지 않고 데이터를 복사해 넘긴다
공유 메모리	shmget, mmap(MAP_SHARED)	같은 물리 메모리를 두 프로세스의 주소 공간에 붙인다

메시지 전달 쪽을 조금 더 나누면 이렇다. 파이프는 운영체제가 만든 단방향 통로로, 익명 파이프는 송신과 수신 프로세스가 동시에 살아 있어야 한다. 메시지 큐는 보낸 데이터를 큐에 보관하므로 받는 쪽이 나중에 가져가도 되고 양방향이 가능하다. 소켓은 클라이언트·서버 구조라 더 복잡하지만 다른 컴퓨터의 프로세스와도 통신할 수 있다

두 방식의 갈림길은 복사를 하느냐다. 메시지 전달은 커널을 거쳐 데이터를 복사하므로 느린 대신 서로의 메모리를 건드릴 수 없다. 공유 메모리는 복사가 없어 가장 빠른 대신 같은 번지를 두 프로세스가 동시에 건드릴 수 있다

그래서 순서를 지키는 장치가 따로 필요해진다. 세마포어, 뮤텍스, 모니터가 그 장치다. 이들은 데이터를 옮기는 통신 수단과 역할이 다르다. 이미 공유된 메모리 위에서 접근 순서만 강제하므로 공유 메모리와 한 세트로 쓰인다. 스레드는 애초에 같은 주소 공간을 쓰므로 통신 수단 없이 동기화 장치만 필요하다

세마포어는 개수를 세는 정수 하나다

임계구역 문제를 풀려면 상호배제 메커니즘이 있어야 하고, 그 메커니즘이 갖춰야 할 조건은 셋이다

조건	내용
상호배제	한 번에 하나만 임계구역에 들어간다
진행	임계구역이 비어 있는데 아무도 못 들어가는 상황이 없어야 한다
한정 대기	들어가려는 요청이 무한정 밀리지 않아야 한다

셋째 조건을 “임계구역에서 빨리 나와야 한다”로 기억하기 쉬운데, 그것은 프로그래머에게 주는 권고이고 메커니즘이 보장해야 할 성질은 아니다. 메커니즘이 책임질 것은 기다리는 쪽이 언젠가는 반드시 들어간다는 보장이다

세마포어는 이 셋을 정수 하나로 구현한다. POSIX 문서의 정의가 짧다

A semaphore is an integer whose value is never allowed to fall below zero.

값을 1 줄이는 연산이 sem_wait, 1 늘리는 연산이 sem_post다. 값이 0이면 sem_wait은 값이 0보다 커질 때까지 멈춘다(sem_overview(7)). 초기값이 곧 동시에 들어갈 수 있는 인원이다. 1로 두면 한 명만, 3으로 두면 세 명까지 들어간다. 프린터가 한 대면 1, 세 대면 3이다

뮤텍스는 값이 0과 1만 되는 세마포어와 비슷해 보이지만 성질이 하나 다르다. 소유자가 있다. 잠근 스레드만 풀 수 있고, 다른 스레드가 풀려고 하면 오류가 난다. POSIX는 PTHREAD_MUTEX_ERRORCHECK와 PTHREAD_MUTEX_RECURSIVE 타입에서 소유자가 아닌 스레드의 해제를 EPERM으로 규정한다(pthread_mutex_lock(3p)). 세마포어는 소유자가 없으므로 A가 내린 값을 B가 올릴 수 있다. 생산자·소비자처럼 신호를 주고받는 용도에는 이 성질이 필요하고, 임계구역을 지키는 용도에는 소유권이 있는 뮤텍스가 안전하다

잠금의 99.96%는 커널에 도달하지 않는다

앞의 경쟁 조건 실험에 뮤텍스와 원자적 연산을 각각 붙여 다시 돌렸다

보호 없음   | 기대값 4000000 | 실제값  2953257 | 잃어버린 증가  1046743 (26.17%) |    7 ms
뮤텍스      | 기대값 4000000 | 실제값  4000000 | 잃어버린 증가        0 ( 0.00%) |  141 ms
원자적 연산  | 기대값 4000000 | 실제값  4000000 | 잃어버린 증가        0 ( 0.00%) |   63 ms

둘 다 정확히 400만을 만든다. 잃는 것은 시간이다. 보호 없이 7밀리초면 끝나던 작업이 뮤텍스로는 141밀리초, 원자적 연산으로는 63밀리초가 걸렸다

여기서 뮤텍스가 무슨 일을 하는지 보려고 시스템콜을 세어 봤다. 400만 번의 lock/unlock 쌍이 커널을 몇 번 부르는지다

$ strace -c -f ./race 1          # 뮤텍스
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
 99.95    0.021251          13      1597       576 futex

$ strace -c -f ./race 2          # 원자적 연산
% time     seconds  usecs/call     calls    errors syscall
------ ----------- ----------- --------- --------- ----------------
  0.00    0.000000           0         3           futex

400만 번 잠그는 동안 futex 시스템콜은 1,597번 불렸다. 0.04%다. 나머지 99.96%의 잠금은 커널에 들어가지 않고 사용자 공간에서 끝났다. 원자적 연산 쪽은 세 번뿐인데, 그마저 카운터와 무관한 스레드 생성·종료에서 나온 것이다

futex(2) 문서가 이 구조를 설명한다. 경쟁이 없으면 “원자적 비교·교환 명령어로 잠금 상태를 획득하지 않음에서 획득함으로 바꾸는” 것으로 끝나고, “프로그램이 조건이 만족될 때까지 오래 멈춰야 할 가능성이 높을 때에만” futex()를 부른다(futex(2)). 이름 자체가 fast userspace mutex의 줄임말이다

잠금을 시도한다
   │
   ├─ 비어 있다 → CPU의 원자적 비교·교환 명령어로 획득   (커널에 가지 않는다)
   │
   └─ 이미 잠겨 있다 → futex 시스템콜로 커널에 재워 달라고 요청
                        → 다른 스레드가 풀면서 깨워 준다

그래서 잠금 비용은 두 개의 다른 숫자를 갖는다. 경쟁이 없을 때와 있을 때다. 스레드 하나로 1,000만 번씩 돌려 경쟁 없는 비용을 쟀다

  보호 없음     2.3 ns/회
  뮤텍스        5.6 ns/회  (보호 없음 대비 2.5배)
  원자적 연산   5.8 ns/회  (보호 없음 대비 2.6배)

경쟁이 없으면 뮤텍스 한 쌍이 5.6나노초다. 시스템콜 한 번이 보통 수백 나노초에서 마이크로초 단위인 것을 생각하면, 이 숫자는 커널에 가지 않았다는 증거이기도 하다

경쟁이 있으면 순서가 바뀐다. 앞의 4스레드 실험에서 뮤텍스는 141밀리초, 원자적 연산은 63밀리초였다. 경쟁이 없을 때 더 쌌던 뮤텍스가 경쟁이 붙으면 두 배 넘게 비싸진다. 기다리는 스레드를 재우고 깨우는 데 futex 호출 1,597번이 들어가기 때문이다. 이 실험은 2코어 가상 머신에서 한 것이고, 코어 수와 스레드 수의 비율이 바뀌면 두 값의 대소가 뒤집힐 수 있다

바닥에 깔려 있는 것은 CPU의 원자적 명령어다. x86-64의 lock 접두사가 붙은 명령어나 비교·교환 명령어가 “읽고 더하고 쓰기”를 하나로 묶어 준다. 운영체제는 그 위에서 잠금을 못 얻은 스레드를 재우는 일을 맡는다. 자원을 지키는 것은 운영체제가 아니라 명령어이고, 운영체제는 기다리는 쪽을 관리한다

자바 synchronized가 잠그는 것은 메서드가 아니라 객체다

언어 차원에서 상호배제를 지원하는 것이 모니터다. 자바의 synchronized가 대표적이고, 임계구역을 wait과 signal로 직접 감싸지 않아도 되므로 순서를 잘못 쓸 여지가 없다

다만 무엇이 잠기는지를 정확히 알아야 한다. 자바 언어 명세가 규정한다

If the method is an instance method, it locks the monitor associated with
the instance for which it was invoked (that is, the object that will be
known as this during execution of the body of the method). If the method
is static, it locks the monitor associated with the Class object that
represents the class in which the method is defined.

출처는 Java Language Specification SE 21, 17.1 Synchronization이다. 잠기는 대상은 메서드가 아니라 객체다. 인스턴스 메서드는 this를, static 메서드는 그 클래스의 Class 객체를 잠근다. 두 스레드가 같은 이름의 synchronized 메서드를 호출해도 서로 다른 인스턴스에 대고 호출하면 잠그는 객체가 달라 상호배제가 성립하지 않는다

확인해 봤다. static 변수 하나를 두고, 그것을 건드리는 synchronized 인스턴스 메서드를 만들었다

public class Counter {
    /* volatile 이라 JIT가 루프 밖으로 값을 빼돌리지 못한다.
       그래도 shared++ 는 읽기·더하기·쓰기 세 단계라 원자적이지 않다. */
    static volatile long shared = 0;

    synchronized void bump()         { for (int i = 0; i < 1_000_000; i++) shared++; }
    static synchronized void bumpS() { for (int i = 0; i < 1_000_000; i++) shared++; }
}

volatile을 붙인 이유는 두 가지다. JIT 컴파일러가 100만 번의 증가를 레지스터에서 처리하고 마지막에 한 번만 메모리에 쓰는 최적화를 막기 위해서, 그리고 volatile이 가시성만 보장하고 원자성은 보장하지 않는다는 것을 그대로 보이기 위해서다. volatile이 붙어 있어도 shared++는 여전히 세 단계다

세 가지 조합으로 두 스레드를 돌렸다

  같은 인스턴스에서 bump() 두 번        기대 2000000, 실제 2000000
  서로 다른 인스턴스에서 bump()         기대 2000000, 실제 1367617  ← 어긋났다
  static synchronized 인 bumpS()        기대 2000000, 실제 2000000

가운데 줄만 깨진다. 같은 인스턴스에 대고 부르면 두 스레드가 같은 객체를 잠그므로 상호배제가 되고, 서로 다른 인스턴스에 대고 부르면 각자 다른 객체를 잠그므로 둘 다 임계구역에 들어간다. static synchronized로 바꾸면 Class 객체 하나를 공유하므로 다시 성립한다

가운데 줄만 열 번 반복했다

     1회 1367076      6회 1600199
     2회 1390168      7회 1311804
     3회 1387891      8회 1833820
     4회 1499261      9회 1779431
     5회 1438133     10회 1465043
   → 2000000이 나온 횟수: 0 / 10

열 번 모두 어긋났다. 이 코드는 synchronized가 붙어 있고, 컴파일 경고도 없고, 리뷰에서 지적받기도 어렵다. 잠기는 대상이 객체라는 것을 모르면 “동기화했는데 왜 깨지지”로 남는다

한 가지 더, synchronized가 막는 것은 프로세스가 아니라 스레드다. 자바의 모니터는 JVM 안의 객체 헤더에 붙은 잠금이므로 다른 JVM 프로세스에는 아무 영향이 없다. 서버 두 대에 같은 애플리케이션을 띄우면 synchronized는 각 JVM 안에서만 유효하다. 여러 대에 걸친 상호배제가 필요하면 데이터베이스 잠금이나 분산 잠금처럼 바깥에 공유 자원을 하나 두어야 한다

교착상태는 네 조건이 모두 맞아떨어질 때만 생긴다

잠금으로 경쟁 조건을 막으면 다음 문제가 온다. 서로가 쥔 것을 기다리다 아무도 못 움직이는 상태다

성립 조건은 넷이고, 하나라도 빠지면 교착상태는 생기지 않는다

조건	내용
상호배제	한 자원은 한 번에 하나만 점유한다
점유와 대기	이미 쥔 채로 다른 것을 기다린다
비선점	쥔 것을 강제로 빼앗을 수 없다
원형 대기	기다리는 관계가 원을 이룬다

OSTEP은 이를 “이 네 조건 중 하나라도 충족되지 않으면 교착상태는 발생할 수 없다”로 정리한다(OSTEP, Common Concurrency Problems). 예방이란 이 중 하나를 깨는 일이고, 실무에서 깨기 가장 쉬운 것이 마지막 원형 대기다.

뮤텍스 두 개를 서로 반대 순서로 잠그는 스레드 두 개를 만들었다

static void *t1(void *p){
    pthread_mutex_lock(&A); pthread_mutex_lock(&B);      /* 항상 A → B */
    pthread_mutex_unlock(&B); pthread_mutex_unlock(&A);
}
static void *t2(void *p){
    pthread_mutex_lock(&B); pthread_mutex_lock(&A);      /* 항상 B → A */
    pthread_mutex_unlock(&A); pthread_mutex_unlock(&B);
}

각각 10만 번 반복시키고 8초를 기다렸다

--- 잠금 순서를 맞춘 경우 (둘 다 A → B) ---
  스레드 1 완료
  스레드 2 완료
  둘 다 정상 종료
  종료 코드 0

--- 잠금 순서가 엇갈린 경우 ---
  종료 코드 124 (124 = 시간 초과)

순서를 맞추면 끝나고 엇갈리면 멈춘다. 멈춘 프로세스를 들여다보면 원형 대기가 그대로 보인다

$ ps -L -o pid,tid,stat,wchan:16,comm -p 458
  PID   TID STAT WCHAN            COMMAND
  458   458 Sl   futex_do_wait    deadlock
  458   460 Sl   futex_do_wait    deadlock
  458   461 Sl   futex_do_wait    deadlock

$ gdb -p 458 -batch -ex "thread apply all bt 4"
Thread 3 (LWP 460):
#3  ___pthread_mutex_lock (mutex=0x55b196174080 <B>) at ./nptl/pthread_mutex_lock.c:93
Thread 2 (LWP 461):
#3  ___pthread_mutex_lock (mutex=0x55b196174040 <A>) at ./nptl/pthread_mutex_lock.c:93

스레드 3은 B를 기다리며 멈춰 있고 스레드 2는 A를 기다리며 멈춰 있다. 세 스레드 모두 WCHAN이 futex_do_wait인 것도 앞 절과 이어진다. 경쟁이 생겨 커널에 들어간 뒤 깨어나지 못하는 상태다

세 명이 원형 탁자에 앉아 좌우의 포크를 집어야 식사할 수 있는 식사하는 철학자 문제도 같은 구조다. 세 명이 동시에 왼쪽 포크를 집으면 모두가 오른쪽을 기다리며 멈춘다. 세 가지 방식으로 돌려 봤다

철학자 3명, 포크 3개, 각자 200번 식사. 30초 안에 못 끝내면 강제 종료한다.

  그대로 (모두 왼쪽부터)   → 30초 안에 끝나지 않았다 (교착상태)
  순서 부여 (한 명만 반대로)  식사 횟수 200/200/200 — 전원 완료
  착석 제한 (동시에 2명까지)  식사 횟수 200/200/200 — 전원 완료

두 해법이 깨는 조건이 다르다. 한 명만 반대 순서로 집게 하면 원을 끊는 것이고, 동시에 두 명만 앉게 하면 점유와 대기를 끊는 것이다. 어느 쪽이든 조건 하나만 무너뜨리면 된다

은행원 알고리즘은 자원이 남아 있어도 거절한다

조건을 미리 깨는 대신 자원을 내줄 때마다 위험한지 따져 보는 방법도 있다. 교착상태 회피다. 모든 프로세스를 끝까지 실행시킬 수 있는 순서가 하나라도 있으면 안전 상태, 없으면 불안전 상태로 본다

은행원 알고리즘은 이 판단을 자동화한다. 각 프로세스가 앞으로 최대 몇 개까지 요청할지를 미리 신고하게 하고, 요청이 올 때마다 그것을 들어줘도 안전 상태가 유지되는지 계산한다. 구현해서 돌려 봤다

[현재 상태]  총 자원 14, 사용 가능 2
   P1: 최대 요구 9, 현재 할당 5, 더 요청할 수 있는 양 4
   P2: 최대 요구 6, 현재 할당 4, 더 요청할 수 있는 양 2
   P3: 최대 요구 6, 현재 할당 3, 더 요청할 수 있는 양 3
   → 안전 순서 P2 → P1 → P3

사용 가능한 자원이 2개뿐인데 왜 안전한가를 순서가 설명한다. P2에게 2개를 주면 P2는 작업을 마치고 쥐고 있던 6개를 반납하므로 사용 가능한 자원이 6개가 된다. 그 6개로 P1의 4개를 채우면 P1이 9개를 반납하고, 남은 것으로 P3를 끝낸다. 한 줄씩 밀어내면 전부 끝난다

여기서 P3가 1개를 더 요청했다고 해 보자. 사용 가능한 자원이 2개이므로 내줄 수는 있다

[요청을 들어준다면]  총 자원 14, 사용 가능 1
   P1: 최대 요구 9, 현재 할당 5, 더 요청할 수 있는 양 4
   P2: 최대 요구 6, 현재 할당 4, 더 요청할 수 있는 양 2
   P3: 최대 요구 6, 현재 할당 4, 더 요청할 수 있는 양 2
   → 안전 순서 없음 = 불안전 상태

남은 1개로는 P1의 4개도 P2의 2개도 P3의 2개도 채울 수 없다. 누구도 끝낼 수 없으니 밀어낼 첫 칸이 없다. 은행원 알고리즘은 자원이 남아 있는데도 이 요청을 거절한다

불안전 상태가 곧 교착상태는 아니다. 모든 프로세스가 신고한 최대치까지 요청하지 않으면 무사히 끝날 수도 있다. 다만 그때는 운에 맡기는 것이므로 미리 거절한다

이 알고리즘이 범용 운영체제에 들어가지 않는 이유는 전제에 있다. 프로세스가 자기가 앞으로 쓸 자원의 최대치를 미리 알려야 하는데, 사용자가 무엇을 열고 무엇을 닫을지 모르는 일반 시스템에서는 그 값을 받아낼 방법이 없다. 요청이 올 때마다 전체 프로세스를 훑어 안전 순서를 찾는 비용도 매번 든다

실제 운영체제는 교착상태를 대부분 무시한다

예방은 제약이 크고 회피는 전제를 요구한다. 남은 선택지는 교착상태가 생기도록 두고 나중에 검출해서 푸는 것인데, 범용 운영체제는 대개 그것조차 하지 않는다. OSTEP은 이 태도를 이렇게 적는다

If an OS froze once a year, you would just reboot it and get happily
(or grumpily) on with your work. If deadlocks are rare, such a
non-solution is indeed quite pragmatic.

리눅스에는 일반 사용자 프로그램의 뮤텍스 교착상태를 감시하다가 풀어 주는 기능이 없다. 앞의 실험에서 프로세스가 8초 동안 멈춰 있어도 커널은 아무것도 하지 않았고, timeout 명령으로 내가 죽였다. 대신 교착상태를 다루는 장치는 범위를 좁혀서 존재한다

첫째는 뮤텍스 타입으로 켜는 검사다. 같은 스레드가 이미 쥔 뮤텍스를 다시 잠그는 경우를 잡아낸다

같은 스레드가 이미 쥔 뮤텍스를 한 번 더 잠글 때
  PTHREAD_MUTEX_ERRORCHECK     lock 반환 35 (Resource deadlock avoided)
  PTHREAD_MUTEX_RECURSIVE      lock 반환  0 (성공)
  PTHREAD_MUTEX_NORMAL (기본)  반환하지 않는다 (그대로 멈춘다)

35는 EDEADLK다. PTHREAD_MUTEX_ERRORCHECK로 만든 뮤텍스는 자기 자신을 다시 잠그려는 시도를 오류로 돌려주고, RECURSIVE는 허용하고, 기본 타입은 그대로 멈춘다(pthread_mutex_lock(3p)). 기본값이 멈추는 쪽이라는 점이 중요하다. 검사를 켜는 것은 프로그래머의 선택이고, 켜지 않으면 아무도 알려 주지 않는다

둘째는 커널 내부용 검사 도구인 lockdep이다. 커널 문서는 이것이 잠금 인스턴스가 아니라 잠금 클래스 단위로 순서를 추적한다고 설명한다. 두 잠금이 한 번이라도 반대 순서로 획득되면 “잠금 역전 교착상태”로 보고 경고를 낸다. 실제로 교착상태가 일어나기를 기다리지 않고 순서 위반만으로 판정하므로, CPU가 여러 개 있어야 재현되는 문제도 단일 CPU에서 잡아낼 수 있다(lockdep design, Linux Kernel documentation). 이 글을 쓴 환경의 커널에는 lockdep이 켜져 있지 않아 실제 경고를 찍어 보지는 못했다

셋째는 데이터베이스다. 교과서에서 배우는 자원 할당 그래프와 순환 검출은 운영체제보다 DBMS에서 실제로 돌아간다. 트랜잭션이 잠금을 기다리는 관계를 그래프로 유지하다가 순환이 생기면 한쪽을 골라 롤백시킨다. 롤백이라는 개념이 자연스러운 곳이 트랜잭션이기 때문이다. 백엔드 개발자가 “교착상태 발생”이라는 로그를 실제로 보게 되는 곳도 대개 여기다

그래서 현실적인 대응은 검출이 아니라 순서다. 잠금에 순서를 정해 두고 항상 그 순서로만 잠그면 원형 대기가 성립하지 않는다. 앞의 실험에서 스레드 두 개의 순서를 맞춘 것만으로 교착상태가 사라진 것이 그 증거다. 규칙 하나가 알고리즘 하나보다 싸다

마무리

경쟁 조건을 막는 일은 세 층에 걸쳐 있다. 맨 아래에는 읽고 더하고 쓰기를 하나로 묶는 CPU의 원자적 명령어가 있고, 그 위에 잠금을 못 얻은 스레드를 재우는 운영체제가 있고, 다시 그 위에 synchronized처럼 언어가 제공하는 편의가 있다. 어느 층을 쓰든 보장의 출처는 맨 아래 명령어다

교착상태 쪽은 반대다. 운영체제가 알아서 풀어 주지 않는다. 네 조건 중 하나를 개발자가 코드에서 깨 두는 것이 사실상 유일한 대책이고, 가장 싸게 깰 수 있는 것이 잠금 순서다

---

다음 편 예고

다음 편은 가상 메모리다. 프로세스가 0번지에서 시작한다고 믿을 수 있는 이유, 세그멘테이션과 페이징이 나눈 것이 무엇인지, 그리고 주소 변환에 메모리를 두 번 읽어야 하는 문제를 실제 하드웨어가 어떻게 해결하는지를 다룬다

---

출처와 범위

이 시리즈는 인프런의 그림으로 쉽게 배우는 운영체제(감자님) 강의를 따라 정리한 것이고, 강의 전체를 일곱 편으로 나눈 네 번째 편이다. 개념 구성과 예시의 출처는 강의이며, 동작과 보장 범위를 말하는 문장은 본문에 건 man 페이지·언어 명세·커널 문서로 확인했다. 코드 블록에 실은 실행 결과는 2코어 x86-64 리눅스 가상 머신(glibc 2.39, OpenJDK 21)에서 직접 돌린 것 그대로이고, 코어 수나 JVM 버전이 다르면 손실률과 소요 시간은 달라진다. 은행원 알고리즘은 직접 구현한 파이썬 스크립트로 계산했다. 측정에 쓴 C·자바·파이썬 코드는 본문에 인용한 부분 외에는 싣지 않았고 공개 저장소도 없다

참고 자료

• pthread_mutex_lock(3p) — Linux manual page
• futex(2) — Linux manual page
• sem_overview(7) — Linux manual page
• Java Language Specification SE 21 — 17.1 Synchronization
• Common Concurrency Problems — OSTEP
• Runtime locking correctness validator (lockdep) — The Linux Kernel documentation