데드락 예방과 회피

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

크게 예방(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이라는 도구로 런타임에 락 획득 순서를 추적합니다.

lockdep은 락 클래스 사이의 의존 관계와 사용 규칙을 검사합니다. 모든 락에 고정 번호를 부여하는 구현과는 구분합니다.

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

import threading

class OrderedLock:
    """오름차순 락 획득을 검사하는 예제"""
    _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()

이 예제는 각 락에 서로 다른 순서를 주고, 획득한 스레드가 반드시 역순으로 해제한다는 전제입니다. release()는 락의 정체성이나 해제 순서를 검사하지 않으므로 잘못된 사용까지 막는 완성된 락 라이브러리는 아닙니다.

데드락 회피

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

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

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

안전 상태와 불안전 상태

안전 상태(Safe State): 각 프로세스의 선언된 최대 요구량을 고려했을 때, 모두 완료할 수 있는 순서가 하나 이상 존재하는 상태입니다.

이 완료 순서를 안전 순서(Safe Sequence)라고 부릅니다.

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

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

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

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

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

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

은행원 알고리즘

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

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

가용 자원이 0이어도 추가 자원 없이 완료할 프로세스가 있으면 자원을 돌려받을 수 있습니다. 잔고가 0이라는 사실만으로 데드락을 판정하지 않습니다.

필요한 자료 구조

• 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]

동작 과정 추적

다음 표는 코드의 입력을 손으로 추적한 결과입니다. 각 벡터는 A, B, C 순서이고 초기 Work는 [3, 3, 2]입니다.

자원 요청 알고리즘

프로세스 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 <stdio.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_unlock(&lock1);
            return NULL;
        }
        /* lock2 획득 실패 → lock1 반납하고 재시도 */
        pthread_mutex_unlock(&lock1);
        usleep(100 * (1 << retries));  /* 지수 백오프 */
        retries++;
    }
    printf("락 획득 실패, 대체 로직 실행\n");
    return NULL;
}

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

이 코드에서 재시도 상한은 lock2 획득 실패를 다섯 번까지 세는 것입니다. 첫 pthread_mutex_lock(&lock1)에는 시간 제한이 없으므로 함수 전체의 종료 시각은 보장하지 않습니다.

자원을 반납하고 간격을 늘리면 충돌 반복을 줄일 수 있지만, 고정된 백오프만으로 공정성이나 성공을 보장하지는 않습니다. 마지막 줄은 실패 안내만 출력하며 실제 대체 작업은 구현하지 않았습니다.

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