데드락 예방과 회피

데드락의 네 가지 필요조건을 알았으니, 이제 데드락이 발생하지 않도록 막는 방법을 살펴봅니다.

크게 예방(Prevention)과 회피(Avoidance) 두 가지 접근법이 있습니다.

예방은 필요조건 자체를 깨뜨리는 것이고, 회피는 조건은 허용하되 위험한 상태로 진입하지 않겠다고 런타임에서 판단하는 것입니다.

데드락 예방: 4가지 조건 깨뜨리기

예방은 네 가지 필요조건 중 최소 하나를 원천적으로 불가능하게 만드는 전략입니다.

각 조건을 어떻게 깨뜨릴 수 있는지, 그리고 왜 실무에서 쉽지 않은지를 함께 살펴봅니다.

1. 상호 배제 깨뜨리기

자원을 공유 가능하게 만들면 됩니다.

읽기 전용 파일, 불변(immutable) 데이터 구조는 동시 접근이 가능하므로 상호 배제가 필요 없습니다.

하지만 뮤텍스, 프린터, 쓰기 작업처럼 본질적으로 공유가 불가능한 자원이 있습니다.

프린터 두 작업을 동시에 출력하면 결과물이 섞입니다.

따라서 모든 경우에 적용할 수는 없습니다.

실무 대안으로 스풀링(Spooling)이 있습니다.

프린터에 직접 접근하는 대신, 인쇄 작업을 큐에 넣고 프린터 데몬이 순서대로 처리합니다.

사실상 경쟁 자원을 큐로 변환하는 것입니다.

2. 점유와 대기 깨뜨리기

방법 A — 일괄 요청: 프로세스가 실행을 시작하기 전에 필요한 모든 자원을 한꺼번에 요청합니다.

중간에 추가 자원을 요청하지 않으므로 점유+대기 상태가 되지 않습니다.

방법 B — 선반납 후 요청: 새로운 자원이 필요하면, 현재 보유한 모든 자원을 먼저 반납한 후 필요한 자원 전체를 다시 요청합니다.

두 방법 모두 심각한 단점이 있습니다.

• 자원 이용률 저하: 실행 초반에 잠깐 사용할 자원을 끝까지 잡고 있어야 합니다. 프린터는 마지막에만 필요한데 시작할 때부터 점유합니다.
• 기아 가능성: 많은 자원을 한꺼번에 요청하는 프로세스는 모든 자원이 동시에 사용 가능해질 때까지 무한 대기할 수 있습니다.
• 미래 예측 불가: 프로세스가 실행 전에 필요한 자원 전체를 알기 어렵습니다. 사용자 입력에 따라 필요한 자원이 달라질 수 있습니다.

3. 비선점 깨뜨리기

자원을 보유한 프로세스가 다른 자원을 요청했는데 즉시 할당받지 못하면, 현재 보유한 자원을 강제로 반납시킵니다.

적용 가능한 자원: CPU 레지스터, 메모리 페이지처럼 상태를 저장하고 복원할 수 있는 자원.

실제로 CPU 스케줄링에서 선점형 스케줄러가 이 원리입니다.

적용 불가능한 자원: 프린터(중간에 빼앗으면 출력이 망가짐), 뮤텍스(임계 구역 중간에 빼앗으면 데이터 일관성 파괴), 네트워크 연결(중간에 끊기면 프로토콜 상태 손실).

4. 순환 대기 깨뜨리기

가장 실용적이고 널리 사용되는 방법입니다.

모든 자원에 전역적 번호(순서)를 부여하고, 프로세스는 반드시 번호가 증가하는 순서로만 자원을 요청합니다.

/* 락에 순서를 부여: lock1 = 순서 1, lock2 = 순서 2 */
pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *thread_a(void *arg) {
    pthread_mutex_lock(&lock1);  /* 순서 1 먼저 */
    pthread_mutex_lock(&lock2);  /* 순서 2 다음 */
    /* --- 작업 --- */
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

void *thread_b(void *arg) {
    pthread_mutex_lock(&lock1);  /* 순서 1 먼저 (lock2부터 잡지 않음!) */
    pthread_mutex_lock(&lock2);  /* 순서 2 다음 */
    /* --- 작업 --- */
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

양쪽 스레드 모두 lock1 → lock2 순서로 잡기 때문에 순환이 형성될 수 없습니다.

증명: 자원 번호가 오름차순으로만 요청된다고 가정합니다.

P1이 R5를 보유하고 R8을 기다린다면, P1은 5보다 큰 번호만 요청합니다.

P2가 R8을 보유하고 있다면, P2는 8보다 큰 번호만 요청할 수 있습니다.

따라서 P2가 R5(번호 5)를 요청하는 것은 불가능하므로 순환이 형성되지 않습니다.

실무 적용: Linux 커널은 lockdep이라는 도구로 런타임에 락 획득 순서를 추적합니다.

순서 위반이 감지되면 경고를 출력합니다.

실제 데드락이 발생하기 전에 잠재적 문제를 찾는 예방적 디버깅 도구입니다.

class OrderedLock:
    """락 순서를 강제하는 Python 구현"""
    _thread_local = {}

    def __init__(self, order):
        self._lock = threading.Lock()
        self._order = order

    def acquire(self):
        tid = threading.current_thread().ident
        held = OrderedLock._thread_local.get(tid, [])
        if held and held[-1] >= self._order:
            raise RuntimeError(
                f"락 순서 위반: {held[-1]} 이후에 {self._order} 획득 시도"
            )
        self._lock.acquire()
        held.append(self._order)
        OrderedLock._thread_local[tid] = held

    def release(self):
        tid = threading.current_thread().ident
        OrderedLock._thread_local[tid].pop()
        self._lock.release()

데드락 회피

회피는 예방보다 유연합니다.

네 가지 조건 자체는 허용하지만, 자원 요청 시마다 이 요청을 수락하면 데드락이 발생할 수 있는가?를 런타임에 판단합니다.

위험하면 요청을 지연시킵니다.

안전 상태와 불안전 상태

안전 상태(Safe State): 모든 프로세스가 최대 자원을 요청하더라도 어떤 순서로든 모두 완료할 수 있는 상태입니다.

"안전 순서(Safe Sequence)"가 하나라도 존재하면 안전 상태입니다.

불안전 상태(Unsafe State): 안전 순서가 존재하지 않는 상태입니다.

불안전 상태가 반드시 데드락을 의미하지는 않지만, 데드락이 발생할 가능성이 있습니다.

데드락은 불안전 상태의 부분 집합입니다.

회피 전략은 시스템을 항상 안전 상태로 유지합니다.

자원 요청이 들어오면, 가상으로 할당해보고 결과가 안전 상태인지 확인합니다.

안전하면 할당하고, 불안전하면 대기시킵니다.

은행원 알고리즘

은행원 알고리즘(Banker's Algorithm)은 다익스트라가 1965년에 제안한 데드락 회피 알고리즘입니다.

은행이 고객에게 대출을 해줄 때, 모든 고객의 최대 대출 요구를 충족할 수 있는 범위에서만 대출하는 것과 같은 원리입니다.

대출 잔고(Available)가 바닥나면 모든 고객의 대출금 회수가 불가능해지는 것이 데드락에 해당합니다.

필요한 자료 구조

• Available[m]: 현재 사용 가능한 각 자원 유형의 인스턴스 수 (벡터, m개 자원 유형)
• Max[n][m]: 각 프로세스의 최대 자원 요구량 (n개 프로세스 × m개 자원 유형)
• Allocation[n][m]: 현재 각 프로세스에 할당된 자원
• Need[n][m]: 각 프로세스가 앞으로 필요한 자원 ($Need[i][j] = Max[i][j] - Allocation[i][j]$)

안전성 검사 알고리즘

def is_safe(available, max_need, allocation, n_proc, n_res):
    """은행원 알고리즘: 안전 상태 여부 판정"""
    need = [[max_need[i][j] - allocation[i][j]
             for j in range(n_res)] for i in range(n_proc)]

    work = available[:]       # 현재 가용 자원 복사
    finish = [False] * n_proc  # 완료 여부
    safe_seq = []

    while len(safe_seq) < n_proc:
        found = False
        for i in range(n_proc):
            if not finish[i]:
                # Need[i] <= Work 인지 확인
                if all(need[i][j] <= work[j] for j in range(n_res)):
                    # 프로세스 i가 완료 가능 → 자원 반환
                    for j in range(n_res):
                        work[j] += allocation[i][j]
                    finish[i] = True
                    safe_seq.append(i)
                    found = True
        if not found:
            return False, []  # 안전 순서 없음 → 불안전
    return True, safe_seq

# 예제: 5개 프로세스, 3종류 자원 (A, B, C)
available = [3, 3, 2]
max_need = [
    [7, 5, 3],  # P0
    [3, 2, 2],  # P1
    [9, 0, 2],  # P2
    [2, 2, 2],  # P3
    [4, 3, 3],  # P4
]
allocation = [
    [0, 1, 0],  # P0
    [2, 0, 0],  # P1
    [3, 0, 2],  # P2
    [2, 1, 1],  # P3
    [0, 0, 2],  # P4
]

safe, seq = is_safe(available, max_need, allocation, 5, 3)
print(f"Safe: {safe}")        # True
print(f"Sequence: {seq}")     # [1, 3, 4, 0, 2]

동작 과정 추적

초기 Available = [3, 3, 2].

Need를 계산합니다.

1단계: P1의 Need [1,2,2] ≤ Work [3,3,2] → P1 완료.

Work = [3+2, 3+0, 2+0] = [5,3,2]

2단계: P3의 Need [0,1,1] ≤ Work [5,3,2] → P3 완료.

Work = [5+2, 3+1, 2+1] = [7,4,3]

3단계: P4의 Need [4,3,1] ≤ Work [7,4,3] → P4 완료.

Work = [7+0, 4+0, 3+2] = [7,4,5]

4단계: P0의 Need [7,4,3] ≤ Work [7,4,5] → P0 완료.

Work = [7+0, 4+1, 5+0] = [7,5,5]

5단계: P2의 Need [6,0,0] ≤ Work [7,5,5] → P2 완료.

안전 순서 <P1, P3, P4, P0, P2>가 존재하므로 안전 상태입니다.

자원 요청 알고리즘

프로세스 Pi가 Request[i]를 요청하면:

1. Request[i] ≤ Need[i] 인지 확인 (최대 요구량 초과 여부)
2. Request[i] ≤ Available 인지 확인 (현재 가용 여부)
3. 가상으로 할당한 후 안전성 검사 실행
4. 안전하면 실제 할당, 불안전하면 요청 대기

은행원 알고리즘은 매 요청마다 복잡한 표를 다시 보는 것처럼 느껴지지만, 판단 질문은 세 단계로 줄일 수 있습니다.

요청이 선언한 최대 필요량 안에 있는지, 지금 가진 자원으로 줄 수 있는지, 가상 할당 후에도 안전 순서가 남는지를 차례로 확인합니다.

아래 다이어그램은 승인과 대기, 오류를 나누는 런타임 의사결정 경로를 한 화면에 묶었습니다.

실무에서의 적용

은행원 알고리즘은 이론적으로 완벽하지만 실무에서는 거의 사용되지 않습니다.

• 최대 요구량 예측 불가: 프로세스가 최대 자원 요구량을 미리 알려야 하는데, 사용자 입력이나 런타임 조건에 따라 달라집니다.
• 프로세스 수 가변: 웹 서버처럼 프로세스가 동적으로 생성/소멸되는 환경에는 적합하지 않습니다.
• 계산 오버헤드: 매 요청마다 $O(n^2 \times m)$ 검사가 필요합니다.

실무에서는 랙 순서 규칙 + 타임아웃 + try-lock 조합을 사용합니다.

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

pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *safe_worker(void *arg) {
    int retries = 0;
    while (retries < 5) {
        pthread_mutex_lock(&lock1);
        if (pthread_mutex_trylock(&lock2) == 0) {
            /* 두 락 모두 획득 성공 */
            printf("작업 수행\n");
            pthread_mutex_unlock(&lock2);
            pthread_mutex_lock(&lock1);
            return NULL;
        }
        /* lock2 획득 실패 → lock1 반납하고 재시도 */
        pthread_mutex_unlock(&lock1);
        usleep(100 * (1 << retries));  /* 지수 백오프 */
        retries++;
    }
    printf("락 획득 실패, 대체 로직 실행\n");
    return NULL;
}

pthread_mutex_trylock은 락 획득에 실패하면 블로킹하지 않고 즉시 반환합니다.

실패 시 보유한 자원을 반납하고 지수 백오프로 재시도하면 데드락과 라이브락을 모두 방지할 수 있습니다.

실무 코드는 이론적인 안전성 검사보다 락 순서, 비블로킹 시도, 시간 제한, 재시도 간격, 대체 경로를 조합하는 경우가 많습니다.

아래 다이어그램은 요청을 무작정 기다리지 않고 실패를 제어 가능한 흐름으로 바꾸는 패턴을 정리합니다.

다음 절에서는 데드락이 발생한 후 이를 탐지하고 복구하는 방법을 알아보겠습니다.