데드락¶

개요¶

데드락(Deadlock)은 두 개 이상의 프로세스가 서로 상대방이 가진 자원을 기다리며 무한히 대기하는 상태입니다. 이 레슨에서는 데드락의 네 가지 필요조건, 자원 할당 그래프, 그리고 예방, 회피, 탐지, 복구 방법을 학습합니다.

목차¶

데드락이란?
데드락 필요조건
자원 할당 그래프
데드락 예방
데드락 회피
데드락 탐지와 복구
연습 문제

1. 데드락이란?¶

정의¶

┌─────────────────────────────────────────────────────────┐
│                    데드락 (Deadlock)                     │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  데드락 = 교착 상태                                     │
│         = 두 개 이상의 프로세스가 서로 상대방의 자원을   │
│           기다리며 무한히 대기하는 상태                  │
│                                                         │
│  ┌─────────────────────────────────────────────────┐    │
│  │                                                 │    │
│  │    프로세스 A                 프로세스 B         │    │
│  │    ┌───────┐                 ┌───────┐         │    │
│  │    │       │ ──R2 요청───▶  │       │         │    │
│  │    │  R1   │                │  R2   │         │    │
│  │    │ 보유  │ ◀──R1 요청─── │ 보유  │         │    │
│  │    │       │                │       │         │    │
│  │    └───────┘                └───────┘         │    │
│  │                                                 │    │
│  │    A는 R2를 기다림, B는 R1을 기다림              │    │
│  │    → 둘 다 영원히 대기 (데드락)                  │    │
│  │                                                 │    │
│  └─────────────────────────────────────────────────┘    │
│                                                         │
└─────────────────────────────────────────────────────────┘

실생활 예시¶

┌─────────────────────────────────────────────────────────┐
│                   데드락 실생활 예시                     │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  1. 교차로 데드락:                                      │
│                                                         │
│              │     │                                    │
│              │ ▲   │                                    │
│              │ │   │                                    │
│       ───────┼─────┼───────                             │
│          ◀───│     │                                    │
│       ───────┼─────┼───────                             │
│              │     │───▶                                │
│       ───────┼─────┼───────                             │
│              │   │ │                                    │
│              │   ▼ │                                    │
│                                                         │
│     네 대의 차가 모두 앞 차를 기다림                     │
│                                                         │
│  2. 다리 위 데드락:                                     │
│                                                         │
│     ┌───────────────────────────┐                       │
│     │     ◀───   ───▶          │                       │
│     │  A 차량    B 차량          │                       │
│     └───────────────────────────┘                       │
│     좁은 다리에서 양쪽에서 진입                          │
│                                                         │
└─────────────────────────────────────────────────────────┘

코드 예시¶

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

pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void* thread_A(void* arg) {
    pthread_mutex_lock(&lock1);
    printf("Thread A: lock1 획득\n");

    sleep(1);  // 데드락 발생 확률 높임

    printf("Thread A: lock2 대기\n");
    pthread_mutex_lock(&lock2);  // 데드락!

    printf("Thread A: 둘 다 획득\n");
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

void* thread_B(void* arg) {
    pthread_mutex_lock(&lock2);
    printf("Thread B: lock2 획득\n");

    sleep(1);  // 데드락 발생 확률 높임

    printf("Thread B: lock1 대기\n");
    pthread_mutex_lock(&lock1);  // 데드락!

    printf("Thread B: 둘 다 획득\n");
    pthread_mutex_unlock(&lock1);
    pthread_mutex_unlock(&lock2);
    return NULL;
}

int main() {
    pthread_t tA, tB;

    pthread_create(&tA, NULL, thread_A, NULL);
    pthread_create(&tB, NULL, thread_B, NULL);

    pthread_join(tA, NULL);
    pthread_join(tB, NULL);

    printf("완료\n");  // 데드락 시 도달 못함
    return 0;
}

/*
출력 (데드락 발생 시):
Thread A: lock1 획득
Thread B: lock2 획득
Thread A: lock2 대기
Thread B: lock1 대기
... (영원히 대기)
*/

2. 데드락 필요조건¶

네 가지 필요조건¶

┌─────────────────────────────────────────────────────────┐
│              데드락의 네 가지 필요조건                   │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  데드락이 발생하려면 다음 네 조건이 동시에 성립해야 함   │
│  (하나라도 깨지면 데드락 발생 안 함)                     │
│                                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │ 1. 상호 배제 (Mutual Exclusion)                   │  │
│  │    - 자원은 한 번에 하나의 프로세스만 사용 가능    │  │
│  │    - 다른 프로세스는 자원이 해제될 때까지 대기     │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │ 2. 점유와 대기 (Hold and Wait)                    │  │
│  │    - 프로세스가 자원을 보유한 채로 다른 자원 대기  │  │
│  │    - 이미 할당된 자원을 가지고 있으면서 추가 요청  │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │ 3. 비선점 (No Preemption)                         │  │
│  │    - 자원을 강제로 빼앗을 수 없음                  │  │
│  │    - 프로세스가 자발적으로 해제해야 함             │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │ 4. 순환 대기 (Circular Wait)                      │  │
│  │    - 프로세스 집합 {P0, P1, ..., Pn}에서          │  │
│  │    - P0→P1→P2→...→Pn→P0 순환 대기 존재          │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
└─────────────────────────────────────────────────────────┘

순환 대기 시각화¶

┌─────────────────────────────────────────────────────────┐
│                    순환 대기 예시                        │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  세 프로세스, 세 자원:                                  │
│                                                         │
│       ┌───────┐                                         │
│       │  P0   │                                         │
│       └───┬───┘                                         │
│      보유: R0                                           │
│      대기: R1 ───────────┐                              │
│           │               │                              │
│           ▼               ▼                              │
│       ┌───────┐       ┌───────┐                         │
│       │  R1   │       │  P1   │                         │
│       └───────┘       └───┬───┘                         │
│                      보유: R1                           │
│                      대기: R2 ─────┐                    │
│                           │        │                    │
│                           ▼        ▼                    │
│                       ┌───────┐┌───────┐                │
│                       │  R2   ││  P2   │                │
│                       └───────┘└───┬───┘                │
│                              보유: R2                   │
│                              대기: R0 ────▶ R0         │
│                                    │       (P0 보유)   │
│                                    └───────────────────┐│
│                                                        ││
│  P0 → R1 → P1 → R2 → P2 → R0 → P0 (순환!)            ││
│  └─────────────────────────────────────────────────────┘│
│                                                         │
└─────────────────────────────────────────────────────────┘

3. 자원 할당 그래프¶

그래프 표기법¶

┌─────────────────────────────────────────────────────────┐
│               자원 할당 그래프 (RAG)                     │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  노드:                                                  │
│  • 프로세스: ○ (원)                                    │
│  • 자원 유형: □ (사각형)                               │
│    - 내부 점(●): 자원 인스턴스 수                       │
│                                                         │
│  엣지:                                                  │
│  • 요청 엣지: Pi → Rj (Pi가 Rj를 요청)                 │
│  • 할당 엣지: Rj → Pi (Rj가 Pi에게 할당됨)              │
│                                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │        예시                                       │  │
│  │                                                   │  │
│  │    ○ P1 ────요청───▶ □ R1                        │  │
│  │                       │ ● ●                       │  │
│  │                       │                           │  │
│  │                       ▼ 할당                      │  │
│  │                       ○ P2                        │  │
│  │                                                   │  │
│  │    P1이 R1을 요청                                 │  │
│  │    R1의 한 인스턴스가 P2에게 할당됨               │  │
│  │    R1에는 2개의 인스턴스 존재                     │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
└─────────────────────────────────────────────────────────┘

데드락 상태의 그래프¶

┌─────────────────────────────────────────────────────────┐
│              데드락 상태 자원 할당 그래프                │
├─────────────────────────────────────────────────────────┤
│                                                         │
│     ┌─────────────────────────────────────────────┐     │
│     │                                             │     │
│     │         ○ P1                               │     │
│     │         │↖                                │     │
│     │    요청 │  ╲ 할당                          │     │
│     │         ▼   ╲                              │     │
│     │      ┌─────┐ ╲                             │     │
│     │      │ R1  │  ╲                            │     │
│     │      │  ●  │   ╲                           │     │
│     │      └──┬──┘    ╲                          │     │
│     │         │        ╲                         │     │
│     │    할당 │         ╲                        │     │
│     │         ▼          ╲                       │     │
│     │         ○ P2 ───요청───▶ ┌─────┐          │     │
│     │         ↖               │ R2  │          │     │
│     │          ╲ 할당         │  ●  │          │     │
│     │           ╲             └──┬──┘          │     │
│     │            ╲               │ 할당         │     │
│     │             ╲              ▼              │     │
│     │              ╲──────────○ P3             │     │
│     │                           │              │     │
│     │                           │ 요청          │     │
│     │                           ▼              │     │
│     │               ┌─────┐                    │     │
│     │               │ R3  │ ◀───────┐         │     │
│     │               │  ●  │         │ 할당     │     │
│     │               └─────┘         │         │     │
│     │                    ○ P1 ◀─────┘         │     │
│     │                                             │     │
│     └─────────────────────────────────────────────┘     │
│                                                         │
│     사이클: P1 → R1 → P2 → R3 → P3 → R2 → P1          │
│             (또는 P2 → R3 → P3 → R2 → P2)              │
│                                                         │
│     → 데드락 발생!                                      │
│                                                         │
└─────────────────────────────────────────────────────────┘

사이클과 데드락¶

┌─────────────────────────────────────────────────────────┐
│                사이클과 데드락의 관계                    │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  규칙:                                                  │
│  ┌───────────────────────────────────────────────────┐  │
│  │ • 사이클이 없으면 → 데드락 없음                    │  │
│  │ • 사이클이 있으면:                                 │  │
│  │   - 자원당 인스턴스가 1개 → 데드락 확정           │  │
│  │   - 자원당 인스턴스가 여러 개 → 데드락 가능성     │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  사이클은 있지만 데드락이 아닌 경우:                    │
│                                                         │
│     ○ P1 ─요청─▶ ┌─────┐ ◀─요청─ ○ P3               │
│     ↑           │ R1  │           ↑                   │
│     │           │ ●●  │           │                   │
│     │           └──┬──┘           │                   │
│     │              │              │                   │
│     │ 할당    할당 ▼  할당        │ 할당              │
│     │              │              │                   │
│     └────── ○ P2  ○ P4 ──────────┘                   │
│                                                         │
│     R1에 2개 인스턴스 → P2와 P4가 해제하면 P1, P3 진행 │
│     → 데드락 아님                                       │
│                                                         │
└─────────────────────────────────────────────────────────┘

4. 데드락 예방¶

네 조건 중 하나 깨기¶

┌─────────────────────────────────────────────────────────┐
│                    데드락 예방                           │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  1. 상호 배제 깨기                                      │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 가능하면 공유 가능한 자원 사용                  │  │
│  │  • 예: 읽기 전용 파일                             │  │
│  │  • 한계: 본질적으로 배타적인 자원 (프린터, 뮤텍스) │  │
│  │    → 일반적으로 깨기 어려움                       │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  2. 점유와 대기 깨기                                    │
│  ┌───────────────────────────────────────────────────┐  │
│  │  방법 1: 시작 시 모든 자원 요청                    │  │
│  │    • 필요한 모든 자원을 한 번에 요청               │  │
│  │    • 단점: 자원 이용률 저하, 기아 가능             │  │
│  │                                                   │  │
│  │  방법 2: 요청 전 모든 자원 해제                    │  │
│  │    • 새 자원 요청 전 보유 자원 반납                │  │
│  │    • 단점: 구현 어려움                            │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  3. 비선점 깨기                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 자원 요청 실패 시 보유 자원 강제 해제           │  │
│  │  • 또는 다른 프로세스의 자원 선점                  │  │
│  │  • 적용 가능: CPU 레지스터, 메모리                 │  │
│  │  • 적용 어려움: 뮤텍스, 프린터                    │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  4. 순환 대기 깨기 ★ 가장 실용적                       │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 자원에 순서 번호 부여                          │  │
│  │  • 오름차순으로만 자원 요청                        │  │
│  │  • 순환 대기 구조적 불가능                         │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
└─────────────────────────────────────────────────────────┘

순환 대기 예방 코드¶

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

// 자원에 순서 번호 부여
// lock1 = 자원 1 (순서 1)
// lock2 = 자원 2 (순서 2)
pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

// 항상 오름차순으로 획득!
void* thread_A(void* arg) {
    // lock1(1) → lock2(2) 순서로 획득
    pthread_mutex_lock(&lock1);  // 순서 1
    printf("Thread A: lock1 획득\n");

    pthread_mutex_lock(&lock2);  // 순서 2
    printf("Thread A: lock2 획득\n");

    // 임계 구역
    printf("Thread A: 작업 수행\n");

    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

void* thread_B(void* arg) {
    // 동일하게 lock1(1) → lock2(2) 순서로 획득
    pthread_mutex_lock(&lock1);  // 순서 1
    printf("Thread B: lock1 획득\n");

    pthread_mutex_lock(&lock2);  // 순서 2
    printf("Thread B: lock2 획득\n");

    // 임계 구역
    printf("Thread B: 작업 수행\n");

    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

int main() {
    pthread_t tA, tB;

    pthread_create(&tA, NULL, thread_A, NULL);
    pthread_create(&tB, NULL, thread_B, NULL);

    pthread_join(tA, NULL);
    pthread_join(tB, NULL);

    printf("완료 (데드락 없음!)\n");
    return 0;
}

5. 데드락 회피¶

안전 상태와 불안전 상태¶

┌─────────────────────────────────────────────────────────┐
│               안전 상태 vs 불안전 상태                   │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  안전 상태 (Safe State):                                │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 모든 프로세스가 데드락 없이 완료할 수 있는 상태  │  │
│  │  • 안전 순서 (Safe Sequence) 존재                  │  │
│  │                                                   │  │
│  │  안전 순서: <P1, P3, P4, P2, P0>                  │  │
│  │  = 이 순서로 자원을 할당하면 모두 완료 가능        │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  불안전 상태 (Unsafe State):                            │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 안전 순서가 존재하지 않는 상태                  │  │
│  │  • 데드락 발생 가능 (반드시 발생하는 건 아님)       │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  ┌────────────────────────────────────────────────────┐ │
│  │                                                    │ │
│  │  ┌─────────────────────────────────────────────┐  │ │
│  │  │                 안전 상태                   │  │ │
│  │  │     (데드락 발생 불가능)                    │  │ │
│  │  │                                             │  │ │
│  │  └─────────────────────────────────────────────┘  │ │
│  │                                                    │ │
│  │  ┌─────────────────────────────────────────────┐  │ │
│  │  │            불안전 상태                      │  │ │
│  │  │   ┌─────────────────────────────────────┐  │  │ │
│  │  │   │                                     │  │  │ │
│  │  │   │         데드락 상태                  │  │  │ │
│  │  │   │                                     │  │  │ │
│  │  │   └─────────────────────────────────────┘  │  │ │
│  │  └─────────────────────────────────────────────┘  │ │
│  │                                                    │ │
│  └────────────────────────────────────────────────────┘ │
│                                                         │
│  회피 전략: 항상 안전 상태만 유지                        │
│                                                         │
└─────────────────────────────────────────────────────────┘

은행원 알고리즘 (Banker's Algorithm)¶

┌─────────────────────────────────────────────────────────┐
│                 은행원 알고리즘                          │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  Dijkstra가 개발 (1965)                                │
│  은행원이 고객에게 대출할 때와 유사한 방식               │
│                                                         │
│  데이터 구조:                                           │
│  • n = 프로세스 수                                      │
│  • m = 자원 유형 수                                     │
│                                                         │
│  ┌───────────────────────────────────────────────────┐  │
│  │ Available[m]                                      │  │
│  │   각 자원 유형별 사용 가능한 인스턴스 수           │  │
│  │                                                   │  │
│  │ Max[n][m]                                         │  │
│  │   각 프로세스가 요청할 수 있는 최대 자원           │  │
│  │                                                   │  │
│  │ Allocation[n][m]                                  │  │
│  │   현재 각 프로세스에 할당된 자원                   │  │
│  │                                                   │  │
│  │ Need[n][m] = Max[n][m] - Allocation[n][m]        │  │
│  │   각 프로세스가 추가로 필요한 자원                 │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
└─────────────────────────────────────────────────────────┘

은행원 알고리즘 예제¶

┌─────────────────────────────────────────────────────────┐
│              은행원 알고리즘 예제                        │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  자원 유형: A, B, C (각각 10, 5, 7개 존재)             │
│  프로세스: P0, P1, P2, P3, P4                          │
│                                                         │
│  현재 상태:                                             │
│  ┌─────────┬────────────────┬─────────────┬────────────┐│
│  │ Process │   Allocation   │     Max     │    Need    ││
│  │         │   A   B   C    │  A   B   C  │  A   B   C ││
│  ├─────────┼────────────────┼─────────────┼────────────┤│
│  │   P0    │   0   1   0    │  7   5   3  │  7   4   3 ││
│  │   P1    │   2   0   0    │  3   2   2  │  1   2   2 ││
│  │   P2    │   3   0   2    │  9   0   2  │  6   0   0 ││
│  │   P3    │   2   1   1    │  2   2   2  │  0   1   1 ││
│  │   P4    │   0   0   2    │  4   3   3  │  4   3   1 ││
│  └─────────┴────────────────┴─────────────┴────────────┘│
│                                                         │
│  Available = [3, 3, 2]  (A:3, B:3, C:2 사용 가능)      │
│                                                         │
│  안전성 검사:                                           │
│  1. Need[P1] = [1,2,2] ≤ Available[3,3,2] → P1 실행 가능│
│     P1 완료 후 Available = [3,3,2] + [2,0,0] = [5,3,2]  │
│                                                         │
│  2. Need[P3] = [0,1,1] ≤ Available[5,3,2] → P3 실행 가능│
│     P3 완료 후 Available = [5,3,2] + [2,1,1] = [7,4,3]  │
│                                                         │
│  3. Need[P4] = [4,3,1] ≤ Available[7,4,3] → P4 실행 가능│
│     P4 완료 후 Available = [7,4,3] + [0,0,2] = [7,4,5]  │
│                                                         │
│  4. Need[P0] = [7,4,3] ≤ Available[7,4,5] → P0 실행 가능│
│     P0 완료 후 Available = [7,4,5] + [0,1,0] = [7,5,5]  │
│                                                         │
│  5. Need[P2] = [6,0,0] ≤ Available[7,5,5] → P2 실행 가능│
│                                                         │
│  안전 순서: <P1, P3, P4, P0, P2>                       │
│  → 시스템은 안전 상태                                   │
│                                                         │
└─────────────────────────────────────────────────────────┘

은행원 알고리즘 코드¶

#include <stdio.h>
#include <stdbool.h>

#define P 5  // 프로세스 수
#define R 3  // 자원 유형 수

int available[R] = {3, 3, 2};
int maximum[P][R] = {
    {7, 5, 3},
    {3, 2, 2},
    {9, 0, 2},
    {2, 2, 2},
    {4, 3, 3}
};
int allocation[P][R] = {
    {0, 1, 0},
    {2, 0, 0},
    {3, 0, 2},
    {2, 1, 1},
    {0, 0, 2}
};

// Need 계산
int need[P][R];

void calculate_need() {
    for (int i = 0; i < P; i++)
        for (int j = 0; j < R; j++)
            need[i][j] = maximum[i][j] - allocation[i][j];
}

bool is_safe() {
    int work[R];
    bool finish[P] = {false};
    int safe_sequence[P];
    int count = 0;

    // work = available 복사
    for (int i = 0; i < R; i++)
        work[i] = available[i];

    while (count < P) {
        bool found = false;
        for (int i = 0; i < P; i++) {
            if (!finish[i]) {
                // need[i] <= work 검사
                bool can_allocate = true;
                for (int j = 0; j < R; j++) {
                    if (need[i][j] > work[j]) {
                        can_allocate = false;
                        break;
                    }
                }

                if (can_allocate) {
                    // 자원 회수 시뮬레이션
                    for (int j = 0; j < R; j++)
                        work[j] += allocation[i][j];
                    finish[i] = true;
                    safe_sequence[count++] = i;
                    found = true;
                }
            }
        }
        if (!found)
            return false;  // 안전 순서 없음
    }

    printf("안전 순서: ");
    for (int i = 0; i < P; i++)
        printf("P%d ", safe_sequence[i]);
    printf("\n");
    return true;
}

int main() {
    calculate_need();

    if (is_safe())
        printf("시스템은 안전 상태입니다.\n");
    else
        printf("시스템은 불안전 상태입니다!\n");

    return 0;
}

6. 데드락 탐지와 복구¶

탐지 알고리즘¶

┌─────────────────────────────────────────────────────────┐
│                  데드락 탐지 알고리즘                    │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  단일 인스턴스 자원:                                    │
│  ┌───────────────────────────────────────────────────┐  │
│  │  대기 그래프 (Wait-for Graph) 사용                 │  │
│  │                                                   │  │
│  │  자원 할당 그래프에서 자원 노드 제거:              │  │
│  │                                                   │  │
│  │  Pi → Rq → Pj  변환→  Pi → Pj                    │  │
│  │  (Pi가 Rq를 요청, Rq가 Pj에게 할당)               │  │
│  │                                                   │  │
│  │  대기 그래프에 사이클 → 데드락                    │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  다중 인스턴스 자원:                                    │
│  ┌───────────────────────────────────────────────────┐  │
│  │  은행원 알고리즘과 유사한 방식 사용                │  │
│  │  현재 요청을 기준으로 안전성 검사                  │  │
│  │  데드락 상태인 프로세스 집합 식별                  │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  탐지 빈도:                                             │
│  • 자원 요청마다 → 오버헤드 높음                       │
│  • 주기적으로 (예: 5분마다)                            │
│  • CPU 이용률이 낮아질 때                              │
│                                                         │
└─────────────────────────────────────────────────────────┘

대기 그래프 예시¶

┌─────────────────────────────────────────────────────────┐
│                   대기 그래프 예시                       │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  자원 할당 그래프:              대기 그래프:            │
│                                                         │
│     ○P1 ─요청─▶ □R1           ○P1 ─────────┐          │
│         ↑      ↓ 할당              ↓        │          │
│    할당 │      ○P2              ○P2 ◀───────┘          │
│         │       ↓ 요청              ↓                  │
│       □R2 ◀────┘               ○P3 ────────┐          │
│         ↓ 할당                      ↓        │          │
│        ○P3 ─요청─▶ □R3 ◀할당─ ○P4      ○P4 ◀────┘   │
│                                                         │
│  R1 → P2 → R2 → P3 → R3 ← P4                          │
│                                                         │
│  대기 그래프:                                           │
│  P1 → P2 → P3 → P4 → P3 (사이클!)                     │
│                                                         │
│  → 데드락 발생 (P3, P4가 데드락 상태)                  │
│                                                         │
└─────────────────────────────────────────────────────────┘

데드락 복구 방법¶

┌─────────────────────────────────────────────────────────┐
│                  데드락 복구 방법                        │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  1. 프로세스 종료 (Process Termination)                 │
│  ┌───────────────────────────────────────────────────┐  │
│  │  방법 1: 모든 데드락 프로세스 종료                  │  │
│  │    • 확실하지만 비용이 큼                          │  │
│  │    • 오래 실행된 프로세스도 종료됨                 │  │
│  │                                                   │  │
│  │  방법 2: 한 번에 하나씩 종료                       │  │
│  │    • 종료 후 데드락 재검사                         │  │
│  │    • 선택 기준: 우선순위, 실행시간, 자원 사용량     │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  2. 자원 선점 (Resource Preemption)                     │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 프로세스의 자원을 강제로 빼앗아 다른 프로세스에  │  │
│  │    할당                                           │  │
│  │                                                   │  │
│  │  고려 사항:                                       │  │
│  │  • 희생자 선택: 어떤 프로세스의 자원을 선점할지    │  │
│  │  • 롤백: 선점된 프로세스를 안전한 상태로 복구      │  │
│  │  • 기아 방지: 같은 프로세스가 계속 희생되지 않도록 │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
│  3. 체크포인트/복구 (Checkpoint/Recovery)               │
│  ┌───────────────────────────────────────────────────┐  │
│  │  • 주기적으로 프로세스 상태 저장 (체크포인트)      │  │
│  │  • 데드락 발생 시 이전 체크포인트로 롤백           │  │
│  │  • 데이터베이스 시스템에서 주로 사용               │  │
│  └───────────────────────────────────────────────────┘  │
│                                                         │
└─────────────────────────────────────────────────────────┘

데드락 처리 방법 비교¶

┌──────────────┬──────────────┬──────────────┬───────────────┐
│     방법      │    오버헤드   │   자원 이용률 │   구현 복잡도  │
├──────────────┼──────────────┼──────────────┼───────────────┤
│ 예방         │ 높음         │ 낮음         │ 낮음          │
│ (Prevention) │              │              │               │
├──────────────┼──────────────┼──────────────┼───────────────┤
│ 회피         │ 높음         │ 중간         │ 높음          │
│ (Avoidance) │              │              │               │
├──────────────┼──────────────┼──────────────┼───────────────┤
│ 탐지/복구    │ 중간         │ 높음         │ 중간          │
│ (Detection) │              │              │               │
├──────────────┼──────────────┼──────────────┼───────────────┤
│ 무시         │ 없음         │ 최고         │ 없음          │
│ (Ostrich)   │              │              │               │
└──────────────┴──────────────┴──────────────┴───────────────┘

무시 (Ostrich Algorithm):
• 데드락이 드물게 발생한다고 가정
• 발생하면 수동으로 재부팅
• Unix, Linux, Windows 등 대부분의 OS가 채택
• 현실적인 접근법

7. 연습 문제¶

문제 1: 데드락 필요조건¶

다음 중 데드락의 네 가지 필요조건에 해당하지 않는 것은?

A. 상호 배제 B. 순환 대기 C. 우선순위 역전 D. 비선점 E. 점유와 대기

정답 보기

**정답: C. 우선순위 역전** 데드락의 네 가지 필요조건: 1. 상호 배제 (Mutual Exclusion) 2. 점유와 대기 (Hold and Wait) 3. 비선점 (No Preemption) 4. 순환 대기 (Circular Wait) 우선순위 역전은 데드락과는 다른 동시성 문제입니다.

문제 2: 자원 할당 그래프¶

다음 자원 할당 그래프가 데드락 상태인지 판별하세요.

P1 → R1, R1 → P2
P2 → R2, R2 → P3
P3 → R1

정답 보기

**분석:** - P1이 R1 요청 - R1이 P2에게 할당됨 - P2가 R2 요청 - R2가 P3에게 할당됨 - P3가 R1 요청 **대기 관계:** - P1 → P2 (R1 때문에) - P2 → P3 (R2 때문에) - P3 → P2 (R1 때문에, R1은 P2가 보유) **사이클:** P2 → P3 → P2 **결론: 데드락 상태** (단, 각 자원이 단일 인스턴스라고 가정)

문제 3: 은행원 알고리즘¶

다음 상태에서 시스템이 안전 상태인지 확인하세요.

Available = [1, 1, 2]

Process	Allocation	Max
P0	(0,1,0)	(2,2,2)
P1	(1,0,0)	(1,1,2)
P2	(0,0,1)	(1,2,3)

정답 보기

**Need 계산:** - P0: (2,2,2) - (0,1,0) = (2,1,2) - P1: (1,1,2) - (1,0,0) = (0,1,2) - P2: (1,2,3) - (0,0,1) = (1,2,2) **안전성 검사:** 1. Available = [1,1,2] 2. Need[P1] = [0,1,2] <= [1,1,2]? Yes! - P1 실행 후: Available = [1,1,2] + [1,0,0] = [2,1,2] 3. Need[P0] = [2,1,2] <= [2,1,2]? Yes! - P0 실행 후: Available = [2,1,2] + [0,1,0] = [2,2,2] 4. Need[P2] = [1,2,2] <= [2,2,2]? Yes! - P2 실행 후: 완료 **안전 순서: ** **결론: 안전 상태**

문제 4: 순환 대기 예방¶

순환 대기를 예방하기 위해 자원에 순서를 부여하는 방법을 설명하고, 왜 이 방법이 데드락을 방지하는지 증명하세요.

정답 보기

**방법:** - 모든 자원 유형에 고유한 순서 번호 부여 - 프로세스는 반드시 오름차순으로만 자원 요청 **증명:** 순환 대기가 발생하려면: P0 → R(i0) → P1 → R(i1) → ... → Pn → R(in) → P0 각 화살표는 "보유 후 요청"을 의미: - P0가 R(i0)를 보유하고 있고 P1이 R(i0)를 기다림 - P1이 R(i1)을 보유하고 P2가 R(i1)을 기다림 - ... - Pn이 R(in)을 보유하고 P0가 R(in)을 기다림 오름차순 규칙에 따르면: - P0가 R(in)을 요청하려면 i0 < in 이어야 함 - 하지만 순환이면 in < i0 < i1 < ... < in (모순!) 따라서 순환 대기 불가능 → 데드락 불가능

문제 5: 데드락 복구¶

데드락이 발생했을 때 "한 번에 하나씩 프로세스 종료" 방법을 사용할 경우, 어떤 기준으로 희생자를 선택해야 하는지 설명하세요.

정답 보기

**희생자 선택 기준:** 1. **프로세스 우선순위** - 낮은 우선순위 프로세스 먼저 종료 2. **실행 시간** - 짧게 실행된 프로세스 종료 (손실 최소화) - 또는 거의 완료된 프로세스는 보호 3. **사용 자원량** - 많은 자원을 보유한 프로세스 종료 (더 많은 자원 확보) 4. **완료까지 남은 자원** - 많은 자원이 더 필요한 프로세스 종료 5. **프로세스 유형** - 배치 작업보다 대화형 프로세스 우선 보호 6. **기아 방지** - 같은 프로세스가 반복적으로 희생되지 않도록 - 종료 횟수 카운트 및 제한 **최적 선택:** 위 기준들의 가중 합으로 비용 함수 정의 후 최소 비용 프로세스 선택

다음 단계¶

이것으로 프로세스 동기화 파트가 완료되었습니다. 다음 학습 주제: - 10_Memory_Management_Basics.md - 메모리 관리 (예정)

데드락¶

개요¶

목차¶

1. 데드락이란?¶

정의¶

실생활 예시¶

코드 예시¶

2. 데드락 필요조건¶

네 가지 필요조건¶

순환 대기 시각화¶

3. 자원 할당 그래프¶

그래프 표기법¶

데드락 상태의 그래프¶

사이클과 데드락¶

4. 데드락 예방¶

네 조건 중 하나 깨기¶

순환 대기 예방 코드¶

5. 데드락 회피¶

안전 상태와 불안전 상태¶

은행원 알고리즘 (Banker's Algorithm)¶

은행원 알고리즘 예제¶

은행원 알고리즘 코드¶

6. 데드락 탐지와 복구¶

탐지 알고리즘¶

대기 그래프 예시¶

데드락 복구 방법¶

데드락 처리 방법 비교¶

7. 연습 문제¶

문제 1: 데드락 필요조건¶

문제 2: 자원 할당 그래프¶

문제 3: 은행원 알고리즘¶

문제 4: 순환 대기 예방¶

문제 5: 데드락 복구¶

다음 단계¶

참고 자료¶