교착 상태 Deadlocks

6장의 락은 레이스 컨디션(race condition)을 막기 위한 도구였다. 그런데 그 도구를 잘못 쓰면 정반대의 병이 생긴다 — 아무도 레이스를 일으키지 않지만, 아무도 진행(progress)하지도 못한다. 모두가 서로를 기다리며 영원히 멈춘 상태, 이것이 교착 상태(deadlock)다. 7장의 식사하는 철학자들이 동시에 왼쪽 젓가락을 집는 순간이 바로 그 그림이다.

0학습 지도

1시스템 모델 — 자원과 요청 사이클 📘 OSC 8.1

시스템은 경쟁하는 여러 스레드에게 분배할 유한한 자원(resource)의 집합으로 이루어진다. 자원은 여러 유형(type, class)으로 나뉘고, 각 유형은 동일한 인스턴스(instance) 여러 개로 구성된다. 예를 들어 CPU가 4개면 자원 유형 “CPU”는 인스턴스가 4개다. 네트워크 인터페이스가 2개면 유형 “network”의 인스턴스가 2개다.

핵심 가정: 같은 유형의 인스턴스는 완전히 같다. 스레드가 어떤 유형의 인스턴스를 하나 요청하면, 그 유형의 어느 인스턴스를 줘도 요청이 충족돼야 한다. 만약 특정 인스턴스만 받아들여진다면, 그것은 인스턴스가 동일하지 않다는 뜻이고 자원 유형을 잘못 나눈 것이다.

스레드가 커널 자원을 쓸 때는 반드시 다음 세 단계 사이클을 따른다. (다른 프로세스의 자원을 IPC로 쓰다 생기는 데드락도 있지만, 이는 커널의 관심사가 아니므로 이 장에서 다루지 않는다.)

커널은 시스템 테이블에 각 자원이 free인지 allocated인지, 할당됐다면 어느 스레드에게 줬는지를 기록한다. 이미 다른 스레드가 쥔 자원을 요청하면, 요청한 스레드는 그 자원의 대기 큐에 들어간다.

2멀티스레드 앱에서의 데드락 · 라이브락 📘 OSC 8.2

이론으로 들어가기 전에, 두 개의 뮤텍스만으로 데드락이 어떻게 태어나는지 코드로 보자. POSIX에서 pthread_mutex_init()은 잠기지 않은 뮤텍스를 만들고, pthread_mutex_lock()은 획득(잠겨 있으면 소유자가 풀 때까지 블록), pthread_mutex_unlock()은 해제다.

pthread_mutex_t first_mutex;
pthread_mutex_t second_mutex;

pthread_mutex_init(&first_mutex,  NULL);
pthread_mutex_init(&second_mutex, NULL);

/* thread_one 이 실행하는 함수 */
void *do_work_one(void *param) {
    pthread_mutex_lock(&first_mutex);     /* (1) first  */
    pthread_mutex_lock(&second_mutex);    /* (2) second */
    /* ... 작업 ... */
    pthread_mutex_unlock(&second_mutex);
    pthread_mutex_unlock(&first_mutex);
    pthread_exit(0);
}

/* thread_two 가 실행하는 함수 — 순서가 거꾸로다 */
void *do_work_two(void *param) {
    pthread_mutex_lock(&second_mutex);    /* (1) second */
    pthread_mutex_lock(&first_mutex);     /* (2) first  */
    /* ... 작업 ... */
    pthread_mutex_unlock(&first_mutex);
    pthread_mutex_unlock(&second_mutex);
    pthread_exit(0);
}

thread_one은 first → second 순으로, thread_two는 second → first 순으로 잡는다. 데드락은 가능하다: thread_one이 first_mutex를 쥔 바로 그 순간 thread_two가 second_mutex를 쥐면, 각자 상대가 쥔 나머지 하나를 영원히 기다린다.

2.1 라이브락(livelock) — 멈추지 않지만 진행도 없다

데드락과 사촌인 또 하나의 liveness 실패가 있다. 데드락은 “집합 내 모두가 블록되어” 멈추지만, 라이브락(livelock)은 스레드들이 블록되지 않고 계속 무언가를 시도하지만 그 시도가 매번 실패해서 진행이 없는 상태다. 복도에서 마주친 두 사람이 서로 같은 방향으로 비키기를 반복하며 길을 못 가는 상황과 같다.

/* thread_one */
void *do_work_one(void *param) {
    int done = 0;
    while (!done) {
        pthread_mutex_lock(&first_mutex);
        if (pthread_mutex_trylock(&second_mutex)) {   /* 논블로킹 시도 */
            /* 둘 다 잡음 → 작업 */
            pthread_mutex_unlock(&second_mutex);
            pthread_mutex_unlock(&first_mutex);
            done = 1;
        } else {
            pthread_mutex_unlock(&first_mutex);       /* 실패 → 가진 것도 놓고 재시도 */
        }
    }
    pthread_exit(0);
}
/* thread_two 는 second → first 순서로 대칭 */

pthread_mutex_trylock()은 잠긴 락을 만나면 블록하지 않고 즉시 실패를 반환한다. 그래서 블록되지는 않는다. 그러나 thread_one이 first를, thread_two가 second를 잡은 뒤, 둘 다 나머지 하나에 trylock으로 실패하고, 가진 것을 놓고, 동시에 다시 시도하면 — 이 춤이 무한히 반복된다. 데드락처럼 진행이 없지만, CPU는 바쁘게 돌고 있다(그래서 더 음흉하다).

3데드락 특징 — 네 가지 필요조건 · 자원 할당 그래프 📘 OSC 8.3

3.1 데드락의 네 가지 필요조건

데드락은 다음 네 조건이 동시에 성립할 때만 발생할 수 있다(필요조건). 하나라도 깨면 데드락은 불가능하다 — 5절의 예방이 바로 이 사실을 이용한다.

1. 상호 배제(mutual exclusion): 적어도 하나의 자원이 비공유(nonsharable) 모드로 점유된다 — 한 번에 한 스레드만 그 인스턴스를 쓸 수 있다. 다른 스레드가 요청하면 해제될 때까지 지연된다.
2. 점유와 대기(hold and wait): 어떤 스레드가 최소 하나의 자원을 쥔 채, 다른 스레드가 쥐고 있는 추가 자원을 기다린다.
3. 비선점(no preemption): 자원은 선점(preemption — 강제로 빼앗음)될 수 없다. 점유한 스레드가 작업을 마치고 자발적으로만 해제한다.
4. 순환 대기(circular wait): 대기 스레드 집합 {T₀, T₁, …, T_n}이 존재해서 T₀은 T₁이 쥔 자원을, T₁은 T₂가 쥔 자원을, …, T_n은 T₀이 쥔 자원을 기다린다 — 고리가 닫힌다.

네 조건은 완전히 독립이 아니다: 순환 대기(④)는 점유와 대기(②)를 함의한다(고리 안의 각 스레드는 무언가를 쥔 채 기다리므로). 그럼에도 예방에서는 각 조건을 따로 공략하는 것이 유용하다(5절).

3.2 자원 할당 그래프(resource-allocation graph)

데드락은 방향 그래프로 정밀하게 그릴 수 있다. 정점은 두 종류다: 활성 스레드 T = {T₁, …, T_n}(원으로 그림)와 자원 유형 R = {R₁, …, R_m}(사각형으로 그림). 유형 R_j의 인스턴스 개수는 사각형 안의 점(dot) 개수로 표시한다. 간선은 두 종류다.

• 요청 간선(request edge) T_i → R_j: 스레드 T_i가 유형 R_j의 인스턴스를 요청해 기다리는 중. 사각형을 가리킨다.
• 할당 간선(assignment edge) R_j → T_i: R_j의 한 인스턴스가 T_i에게 할당됨. 사각형 안의 특정 점에서 출발한다.

요청이 충족되면 요청 간선은 즉시 할당 간선으로 바뀌고, 자원을 해제하면 할당 간선이 삭제된다.

4데드락을 다루는 세 가지 방법 📘 OSC 8.4

데드락 문제를 다루는 길은 크게 셋이다.

예방과 회피는 모두 “데드락에 들지 않게 보장”하지만 방식이 다르다. 예방(prevention)은 네 필요조건 중 적어도 하나가 성립할 수 없게 요청 방식을 제약한다(5절). 회피(avoidance)는 각 스레드가 장차 어떤 자원을 얼마나 쓸지에 대한 추가 정보를 미리 받아, 매 요청마다 “지금 줘도 안전한가”를 동적으로 판단한다(6절). 한 시스템에서 자원 종류별로 서로 다른 전략을 조합하는 것이 최적일 때가 많다 — 어느 한 방법도 모든 자원 문제에 만능은 아니다.

5데드락 예방 — 네 조건을 각각 깨기 📘 OSC 8.5

데드락은 네 조건이 동시에 성립해야 가능하므로, 하나만 성립 못 하게 만들면 예방된다. 네 조건을 하나씩 공략해 보자.

5.1 상호 배제 깨기 — 대개 불가능

공유 가능(sharable) 자원은 상호 배제가 필요 없어 데드락에 끼지 않는다. 읽기 전용 파일이 좋은 예다 — 여러 스레드가 동시에 열어도 된다. 그러나 일반적으로 이 조건은 깰 수 없다. 어떤 자원은 본질적으로 비공유이기 때문이다 — 뮤텍스 락은 여러 스레드가 동시에 가질 수 없다.

5.2 점유와 대기 깨기

스레드가 자원을 요청할 때 다른 자원을 전혀 쥐고 있지 않도록 보장하면 된다. 두 프로토콜이 있다.

• 전부 미리 요청: 실행 시작 전에 필요한 모든 자원을 한꺼번에 요청·할당받는다. 자원 요청이 동적인 대부분의 앱에선 비현실적이다.
• 쥔 게 없을 때만 요청: 추가 자원을 요청하기 전에, 현재 쥔 것을 모두 해제한다.

두 방법의 두 단점: ① 자원 활용률 저하 — 오래 쥐었는데 잠깐만 쓸 수 있다(뮤텍스를 전 실행 동안 쥐지만 실제론 잠깐만 필요). ② 기아(starvation) — 인기 있는 자원 여러 개가 필요한 스레드는 그중 하나가 늘 남에게 가 있어 무한정 못 받을 수 있다.

5.3 비선점 깨기

쥔 채로 다른 자원을 요청했는데 즉시 못 받으면, 현재 쥔 자원을 전부 (암묵) 해제한다 — 그 자원들은 “대기 목록”에 올라가고, 스레드는 옛 자원 + 새 자원을 모두 다시 얻을 수 있을 때 재시작된다. 또는, 요청한 자원이 대기 중인 다른 스레드에게 가 있으면 그것을 선점해 요청자에게 준다.

이 프로토콜은 상태를 쉽게 저장·복원할 수 있는 자원(CPU 레지스터, 데이터베이스 트랜잭션)에 잘 맞는다. 그러나 뮤텍스·세마포어처럼 — 정확히 데드락이 가장 흔히 나는 그 자원 — 에는 일반적으로 적용할 수 없다(임계 구역 중간에 락을 강제로 뺏으면 보호 대상 데이터의 일관성이 깨진다).

5.4 순환 대기 깨기 — 자원 순서화(유일하게 실용적)

앞의 셋은 대개 비현실적이다. 그러나 순환 대기를 깨는 것은 실용적이다. 모든 자원 유형에 전순서(total ordering)를 매기고, 각 스레드가 번호가 증가하는 순서로만 요청하게 하면 된다.

형식적으로, 자원 유형 집합 R = {R₁, …, R_m}에 대해 일대일 함수 F: R → ℕ(자연수)을 정의한다. 예를 들어 Figure 8.1의 두 락에 F(first_mutex)=1, F(second_mutex)=5를 매긴다. 그러면 규칙은: R_i를 쥔 뒤에는 F(R_j) > F(R_i)인 R_j만 요청 가능. 두 락을 동시에 쓰려면 반드시 first 먼저, 그다음 second. (또는: R_j를 요청하려면 F(R_i) ≥ F(R_j)인 R_i는 모두 해제한 상태여야 한다.)

void transaction(Account from, Account to, double amount) {
    mutex lock1, lock2;
    lock1 = get_lock(from);     /* 인자에 따라 어느 락인지 런타임에 결정 */
    lock2 = get_lock(to);
    acquire(lock1);
        acquire(lock2);
            withdraw(from, amount);
            deposit(to, amount);
        release(lock2);
    release(lock1);
}

6데드락 회피 — 안전 상태와 은행원 알고리즘 📘 OSC 8.6

예방은 요청을 제약해 부작용(낮은 장치 활용·처리량 감소)을 낳는다. 회피(avoidance)는 다른 길이다: 각 스레드가 장차 필요할 각 자원 유형의 최대 개수를 미리 선언하면, 시스템은 매 요청마다 “지금 줘도 미래에 데드락이 없는가”를 동적으로 검사해 결정한다. 판단에는 ① 현재 가용 자원, ② 각 스레드에 현재 할당된 자원, ③ 각 스레드의 최대 수요가 쓰인다.

6.1 안전 상태(safe state)와 안전 순서

상태가 안전(safe)하다는 것은: 시스템이 각 스레드에게 (최대 수요까지) 자원을 어떤 순서로 할당해도 데드락을 피할 수 있다는 뜻이다. 더 정확히, 안전 순서(safe sequence) ⟨T₁, …, T_n⟩이 존재하면 안전하다 — 각 T_i가 아직 요청할 수 있는 자원이, 현재 가용 자원 + 자기보다 앞선 모든 T_j(j<i)가 쥔 자원으로 충족될 수 있어야 한다. 그러면 T_i는 (필요하면) 앞 스레드들이 끝나길 기다렸다가 자원을 얻어 끝내고 반납하고, 그다음 T_i+1이… 이렇게 줄줄이 완료된다.

6.2 안전/불안전 — 12개 자원 worked example

자원 12개, 스레드 셋(T₀·T₁·T₂). 최대 수요와 현재 점유가 다음과 같다(t₀ 시점). 가용 = 12 − (5+2+2) = 3.

t₀은 안전하다 — 안전 순서 ⟨T1, T0, T2⟩이 있다: 가용 3 ≥ T1의 Need 2 → T1에게 주고 끝내면 반납해 가용 5 → T0의 Need 5 충족 → 끝내면 가용 10 → T2의 Need 7 충족. 모두 완료.

이제 t₁에 T2가 1개를 더 요청해 받았다고 하자(가용 3→2, T2 점유 2→3, Need 7→6). 시스템은 더 이상 안전하지 않다: 가용 2로는 오직 T1(Need 2)만 채울 수 있고, T1이 끝나면 가용 4. 그런데 T0는 Need 5, T2는 Need 6이라 둘 다 못 채운다 → 둘이 영원히 대기 → 데드락. 실수는 T2의 1개 추가 요청을 승인한 것이었다. 그 요청을 (가용했음에도) 대기시켰다면 데드락을 피했을 것이다.

6.3 자원 할당 그래프 알고리즘 — 단일 인스턴스용

모든 자원 유형이 인스턴스 1개면, 자원 할당 그래프의 변형으로 회피할 수 있다. 새 간선 요구 간선(claim edge) T_i → R_j(점선)를 도입한다 — “T_i가 장차 R_j를 요청할 수도 있다”. 스레드 시작 전 모든 claim 간선이 미리 그려져야 한다. T_i가 실제로 R_j를 요청하면 claim → request로, 할당되면 request → assignment로 바뀌고, 해제하면 다시 claim으로 돌아간다.

규칙: 요청 간선 T_i → R_j를 할당 간선 R_j → T_i로 바꿨을 때 그래프에 사이클(claim 간선 포함)이 생기지 않을 때만 승인한다. 사이클 검사는 n²(n=스레드 수) 연산이 든다. 사이클이 없으면 할당 후에도 안전, 있으면 불안전이므로 T_i는 대기한다.

6.4 은행원 알고리즘(Banker's Algorithm) — 다중 인스턴스용

그래프 알고리즘은 인스턴스 1개일 때만 쓴다. 유형마다 인스턴스가 여럿이면 은행원 알고리즘을 쓴다(이름의 유래: 은행이 모든 고객의 수요를 못 채울 만큼 현금을 내주지 않게 하는 것과 같다). 새 스레드는 진입 시 각 유형의 최대 필요 인스턴스 수를 선언한다. 요청이 오면 시스템은 “주면 안전한가”를 검사해, 안전하면 주고 아니면 기다리게 한다. n=스레드 수, m=유형 수일 때 네 자료구조를 유지한다.

표기: 길이 n 벡터 X, Y에 대해 X ≤ Y ⇔ 모든 i에서 X[i] ≤ Y[i]. 행렬의 한 행을 벡터로 보고 Allocation_i, Need_i로 쓴다.

// 1. 초기화
Work    = Available             // 길이 m
Finish[i] = false   for i = 0..n-1

// 2. 아직 못 끝났고 Need가 Work로 충족되는 스레드 찾기
loop:
  find i such that  Finish[i] == false  AND  Need[i] <= Work
  if none:  goto step4

// 3. 그 스레드가 끝났다 치고 자원을 회수(낙관적)
  Work    = Work + Allocation[i]
  Finish[i] = true
  goto loop

// 4. 판정
step4:
  if Finish[i] == true for ALL i:   상태는 SAFE (찾은 순서가 안전 순서)
  else:                             UNSAFE

// Ti 가 Request_i 를 요청
// 1. 최대 선언 초과 검사
if Request_i > Need_i:    error("최대 수요 초과")     // 규칙 위반

// 2. 가용 검사
if Request_i > Available: Ti must wait                // 지금은 자원 부족

// 3. "줬다 치고" 상태를 가상으로 갱신
Available     = Available     - Request_i
Allocation_i  = Allocation_i  + Request_i
Need_i        = Need_i        - Request_i

// 4. 안전성 알고리즘 실행
if 결과 상태가 SAFE:   요청 승인 (실제로 할당)
else:                  롤백(원상복구) 하고 Ti must wait

6.5 은행원 알고리즘 — 행렬 손계산 worked example ⊕ 확장

스레드 5개(T₀~T₄), 유형 셋 A(총 10)·B(총 5)·C(총 7). 현재 스냅샷:

현재 상태는 안전하다. 안전성 알고리즘을 Work=(3 3 2)로 돌려보자(각 단계: Need ≤ Work인 스레드를 골라 Allocation을 회수).

모든 Finish[i]=true → 안전. 안전 순서 ⟨T1, T3, T4, T2, T0⟩.

7데드락 탐지 — wait-for graph · 다중 인스턴스 📘 OSC 8.7

예방·회피를 안 쓰면 데드락이 일어날 수 있다. 이때 시스템은 ① 상태를 검사해 데드락 발생 여부를 판정하는 알고리즘과 ② 회복 알고리즘을 제공할 수 있다. 탐지·회복에는 오버헤드가 따른다 — 정보 유지·탐지 실행의 런타임 비용 + 회복에 따르는 손실.

7.1 단일 인스턴스 — wait-for graph

모든 자원이 인스턴스 1개면 wait-for graph(대기 그래프)를 쓴다. 자원 할당 그래프에서 자원 노드를 제거하고 간선을 합쳐 얻는다: wait-for 그래프에 T_i → T_j가 있다 ⇔ 원래 그래프에 어떤 자원 R_q에 대해 T_i → R_q → T_j가 있다(“T_i가 T_j가 쥔 자원을 기다린다”). 데드락 ⇔ wait-for 그래프에 사이클. 시스템은 이 그래프를 유지하며 주기적으로 사이클을 찾는다(O(n²), n=정점 수).

7.2 다중 인스턴스 — 탐지 알고리즘

인스턴스가 여럿이면 wait-for 그래프를 못 쓴다. 은행원 알고리즘과 닮은 시변 자료구조(Available·Allocation·Request)를 쓴다. Request는 “지금 더 요청 중인 양”이다(Max·Need가 아니라 현재 요청). 알고리즘은 본질적으로 “완료될 수 있는 스레드를 낙관적으로 회수해 가며, 끝내 못 끝나는 스레드가 있으면 그것들이 데드락”임을 찾는다.

// 1. 초기화 — Allocation이 0이 아닌 스레드만 의심
Work = Available
for i = 0..n-1:
    Finish[i] = (Allocation[i] == 0)   // 아무것도 안 쥔 스레드는 데드락 아님

// 2. 끝낼 수 있는 스레드 찾기 (Need가 아니라 Request 사용!)
loop:
  find i such that  Finish[i] == false  AND  Request[i] <= Work
  if none:  goto step4

// 3. 낙관적 회수: Ti가 더 안 요청하고 곧 반납한다고 가정
  Work = Work + Allocation[i]
  Finish[i] = true
  goto loop

// 4. 판정
step4:
  if Finish[i] == false for some i:
        시스템은 DEADLOCK,  그런 Ti 들이 교착된 집합

7.3 탐지를 얼마나 자주 돌릴까

탐지 빈도는 두 요인에 달렸다: ① 데드락이 얼마나 자주 나는가, ② 났을 때 몇 스레드가 엮이는가. 양극단을 보자.

• 매 요청마다 탐지(가장 잦음): 데드락은 “즉시 못 채우는 요청”에서만 생기므로, 그런 요청마다 돌리면 어느 스레드가 데드락을 “유발”했는지까지 식별할 수 있다(엄밀히는 고리 전체가 공범이지만). 단, 계산 오버헤드가 막대하다.
• 주기적(덜 잦음): 한 시간마다, 혹은 CPU 활용률이 40% 아래로 떨어질 때(데드락은 결국 처리량을 떨어뜨려 CPU 유휴를 키운다) 돌린다. 임의 시점에 돌리면 그래프에 사이클이 여럿일 수 있어 “누가 유발했는지”는 못 가린다.

8데드락 회복 — 종료 · 선점 · 기아 📘 OSC 8.8

탐지가 데드락을 발견하면, 운영자에게 알려 수동 처리하게 하거나 시스템이 자동 회복한다. 고리를 깨는 길은 둘이다: 스레드(프로세스)를 종료하거나, 자원을 선점한다.

8.1 프로세스·스레드 종료

두 방식 모두 종료된 프로세스의 자원을 전부 회수한다.

• 교착된 프로세스 전부 종료: 확실히 고리를 깨지만 비용이 크다 — 오래 계산한 부분 결과를 다 버려 재계산해야 한다.
• 한 번에 하나씩 종료: 하나 죽일 때마다 탐지를 다시 돌려 아직 교착인지 확인한다. 종료가 적은 대신 탐지 반복 오버헤드가 크다.

종료는 간단하지 않다. 파일을 갱신 중이던 프로세스를 죽이면 파일이 부정합 상태로 남고, 뮤텍스로 공유 데이터를 갱신 중이었다면 시스템이 락 상태를 “가용”으로 되돌려도 데이터 무결성은 보장할 수 없다.

8.2 자원 선점

교착 고리가 깨질 때까지 일부 자원을 프로세스에서 차례로 선점해 다른 프로세스에 준다. 세 이슈를 다뤄야 한다.

1. 희생자 선택(selecting a victim): 어느 자원·프로세스를 선점할지. 종료와 마찬가지로 비용을 최소화하는 순서로(쥔 자원 수, 소비한 시간 등).
2. 롤백(rollback): 자원을 뺏긴 프로세스는 정상 진행이 불가하므로 어떤 안전 상태로 되돌려 재시작해야 한다. 안전 상태를 알기 어려워 보통은 전체 롤백(abort 후 재시작)이 가장 단순하다. 고리를 깰 만큼만 부분 롤백하는 것이 효율적이지만, 그러려면 모든 실행 상태 정보를 더 많이 보관해야 한다.
3. 기아(starvation): 비용 위주로만 희생자를 고르면 같은 프로세스가 늘 희생자가 되어 영영 못 끝날 수 있다. 실용 시스템은 이를 막아야 한다 — 한 프로세스가 희생자로 뽑히는 횟수에 유한한 상한을 둔다. 가장 흔한 해법은 롤백 횟수를 비용 함수에 포함해, 자주 당한 프로세스는 점점 덜 뽑히게 하는 것이다.

9실무와 연결 — 락 순서화 · 타임아웃 · 분산 데드락 ⊕ 교재 외 확장

교재는 알고리즘에 집중하지만, 실무 동시성 코드에서 데드락을 다루는 무기고는 더 구체적이다. 이 절은 앞 절들을 현장 기법·다른 장과 잇는다.

9.1 현장의 3대 무기 — 순서화 · tryLock · 타임아웃 ⊕ 확장

void transfer(Account& a, Account& b, long amount) {
    // 두 락을 "주소가 작은 것 먼저" 고정 순서로 잡아 순환 대기 차단
    std::mutex& lo = (&a.m < &b.m) ? a.m : b.m;
    std::mutex& hi = (&a.m < &b.m) ? b.m : a.m;
    std::lock_guard<std::mutex> g1(lo);
    std::lock_guard<std::mutex> g2(hi);
    a.balance -= amount;
    b.balance += amount;
}

// 또는 표준 라이브러리가 데드락 없이 여러 락을 한꺼번에:
void transfer2(Account& a, Account& b, long amount) {
    std::scoped_lock lk(a.m, b.m);   // C++17: 내부적으로 deadlock-avoiding 알고리즘
    a.balance -= amount;
    b.balance += amount;
}

boolean transferWithTimeout(Account from, Account to, long amount)
        throws InterruptedException {
    long stop = System.nanoTime() + TimeUnit.SECONDS.toNanos(1);
    while (System.nanoTime() < stop) {
        if (from.lock.tryLock()) {
            try {
                if (to.lock.tryLock()) {          // 둘째 락도 논블로킹 시도
                    try {
                        from.balance -= amount;
                        to.balance   += amount;
                        return true;              // 성공
                    } finally { to.lock.unlock(); }
                }
            } finally { from.lock.unlock(); }     // 둘째 실패 → 첫째도 즉시 반납
        }
        Thread.sleep(ThreadLocalRandom.current().nextInt(1, 50)); // 무작위 백오프 — 라이브락 회피
    }
    return false;   // 타임아웃 → 포기(상위에서 재시도/보고)
}

9.2 6장·4장과의 연결 — 우선순위 역전, fork+락 ⊕ 확장

9.3 분산 시스템의 데드락 ⊕ 확장

한 줄로: 자원과 프로세스가 여러 노드에 흩어진 분산 데드락에서는 어느 노드도 전역 wait-for 그래프를 못 본다 — 그래서 중앙 코디네이터가 부분 그래프를 모으거나(중앙집중식), 엣지 추적(edge-chasing) 같은 분산 탐지로 “probe 메시지”를 고리를 따라 돌려 자기에게 돌아오면 데드락으로 판정한다. 이는 운영체제를 넘어 분산 트랜잭션·마이크로서비스의 핵심 문제다.

10오해 정리 · 한 장 요약 · 복습 📘 OSC 8.9

10.1 흔한 오해 바로잡기

• ❌ “자원 할당 그래프에 사이클이 있으면 무조건 데드락이다.” → 인스턴스가 1개일 때만 사이클 ⇔ 데드락. 다중 인스턴스면 사이클은 필요조건일 뿐, 고리 밖에서 해제돼 풀릴 수 있다.
• ❌ “불안전 상태 = 데드락 상태.” → 데드락은 반드시 불안전하지만, 모든 불안전이 데드락은 아니다. 불안전은 “데드락으로 갈 수도 있는” 위험 지대.
• ❌ “네 조건 중 점유와 대기, 순환 대기는 별개다.” → 순환 대기는 점유와 대기를 함의한다(완전 독립 아님). 그래도 예방에선 따로 공략한다.
• ❌ “라이브락은 블록되니 데드락의 일종이다.” → 라이브락은 블록되지 않는다. 계속 시도하나 매번 실패해 진행이 없는 것. CPU는 바쁘다.
• ❌ “은행원 알고리즘은 가용하면 무조건 준다.” → 가용해도 결과가 불안전하면 거절한다. 활용률을 희생해 안전을 산다.
• ❌ “OS가 데드락을 알아서 막아준다.” → Linux·Windows는 대부분 무시(타조 알고리즘)한다. 데드락 회피는 앱·커널 개발자의 책임(주로 락 순서화).
• ❌ “비선점을 깨면 어떤 락에도 적용된다.” → CPU 레지스터·DB 트랜잭션처럼 상태 저장·복원이 쉬운 자원에만 맞고, 뮤텍스·세마포어엔 일반적으로 부적합.

10.2 한 장 정리

10.3 복습 — 답을 가리고

Q1. 데드락의 네 필요조건을 말하고, 왜 “필요”조건이라 부르는지 설명하라.

① 상호 배제 ② 점유와 대기 ③ 비선점 ④ 순환 대기. 데드락이 일어나려면 넷이 동시에 성립해야 하므로 각각이 필요조건이다 — 뒤집으면 하나만 깨도 데드락은 불가능하다(예방의 원리).

Q2. 자원 할당 그래프에 사이클이 있다. 데드락이라고 단정할 수 있는가?

아니다. 모든 관련 자원 유형이 인스턴스 1개일 때만 사이클 ⇔ 데드락이다. 다중 인스턴스면 사이클은 필요조건일 뿐 — 고리 밖의 스레드가 인스턴스를 해제해 고리를 끊을 수 있다. 단, 사이클이 없으면 데드락은 확실히 없다.

Q3. 순환 대기를 자원 전순서로 깨면 왜 데드락이 불가능한가?

모든 스레드가 번호 증가 순으로만 잡으면, 고리가 있다고 가정 시 F(R₀)<F(R₁)<…<F(Rₙ)<F(R₀)이 되어 추이성으로 F(R₀)<F(R₀) — 모순. 따라서 순환이 닫힐 수 없다. 단, 개발자가 그 순서를 지켜 짜야 하고, 락을 동적으로 얻으면(계좌 이체) 식별값 정렬이 추가로 필요하다.

Q4. “자원이 가용한데도 요청을 거절”하는 회피 알고리즘. 이게 합리적인 이유는?

지금 주면 불안전 상태가 되어 미래에 데드락이 강제될 수 있기 때문이다. 회피는 “승인 결과가 안전 상태일 때만 승인”한다. 자원 활용률 저하를 대가로 데드락을 원천 차단한다(6.2의 12자원 예: T2의 추가 1개를 승인한 게 실수였다).

Q5. 은행원 알고리즘. Available=(3 3 2), Need가 T1=(1 2 2)·T3=(0 1 1)·T4=(4 3 1)·T2=(6 0 0)·T0=(7 4 3)일 때 안전 순서를 하나 제시하라.

Work=(3 3 2)에서 시작. T1 충족(≤Work)→회수 (5 3 2); T3→(7 4 3); T4→(7 4 5); T2→(10 4 7); T0→(10 5 7). 모두 완료 → 안전 순서 ⟨T1, T3, T4, T2, T0⟩.

Q6. wait-for graph는 자원 할당 그래프와 어떻게 다르며, 언제만 쓸 수 있나?

자원 노드를 지우고 “Tᵢ→Rq→Tⱼ”를 “Tᵢ→Tⱼ”로 축약한 것이다(Tᵢ가 Tⱼ가 쥔 자원을 기다림). 모든 자원이 인스턴스 1개일 때만 쓰며, 이때 사이클 ⇔ 데드락이다. 다중 인스턴스면 Request 기반 탐지 알고리즘을 써야 한다.

Q7. 선점으로 회복할 때 “기아”가 왜 생기며 어떻게 막나?

비용 위주로만 희생자를 고르면 같은 프로세스가 늘 희생자가 되어 영영 못 끝난다. 막는 법: 한 프로세스가 희생되는 횟수에 유한 상한을 두기 — 가장 흔한 구현은 롤백 횟수를 비용 함수에 포함해, 자주 당한 프로세스일수록 덜 뽑히게 한다.

Q8. 왜 대부분의 OS(Linux·Windows)는 데드락을 “무시”하나? 그 대가는?

예방·탐지의 상시 오버헤드보다, 드물게(예: 월 1회) 나는 데드락을 무시하는 게 더 싸기 때문이다(타조 알고리즘). 대가: 탐지되지 않은 데드락은 자원을 쥔 채 못 도는 스레드를 늘려 처리량을 갉아먹다 결국 멈춰, 수동 재시작이 필요해진다. 회피는 앱·커널 개발자 몫(락 순서화).

10.4 연관 자료 · 더 깊이