데드락 예방과 회피

앞 글에서 교착 상태가 생기려면 상호 배제, 점유와 대기, 비선점, 순환 대기의 네 조건이 모두 성립해야 한다는 것을 보았습니다. 그렇다면 교착 상태를 막는 방법도 두 갈래로 생각할 수 있습니다. 하나는 네 조건 가운데 하나를 아예 성립할 수 없게 만드는 예방(prevention)입니다. 다른 하나는 조건이 성립할 수 있는 것은 그대로 두되, 자원을 내줄 때마다 이 요청을 들어주어도 위험하지 않은지 따져 보고 위험하면 미루는 회피(avoidance)입니다. 이 글에서는 두 방법을 차례로 살펴보고, 각각이 실무에서 어디까지 쓰이는지 정리합니다.

예방: 네 조건 가운데 하나를 깨뜨린다

예방은 교착 상태에 필요한 조건 하나를 원천적으로 막는 방법입니다. 조건마다 깨뜨리는 방법이 있지만, 그 대가도 저마다 다릅니다.

상호 배제를 없앨 수 있을까

자원을 여럿이 함께 쓸 수 있다면 기다릴 일이 없으므로 교착 상태도 생기지 않습니다. 읽기 전용 파일이나 바뀌지 않는(immutable) 자료구조는 여러 작업이 동시에 읽어도 되므로 상호 배제가 필요 없습니다. 하지만 쓰기나 프린터처럼 본래 함께 쓸 수 없는 자원이 있으므로, 이 방법을 모든 자원에 쓸 수는 없습니다.

함께 쓸 수 없는 자원을 우회하는 방법으로 스풀링(spooling)이 있습니다. 여러 프로그램이 프린터를 직접 잡는 대신 인쇄할 내용을 큐에 넣으면, 프린터 데몬 하나만 프린터를 쥐고 큐의 작업을 차례로 인쇄합니다. 프로그램들은 프린터를 기다리는 대신 큐에 넣고 바로 다음 일을 할 수 있으므로, 프린터를 둘러싼 대기 관계가 사라집니다.

점유와 대기를 없애기

쥔 채로 기다리는 일을 없애는 방법은 둘입니다. 첫째는 필요한 자원을 실행을 시작하기 전에 한꺼번에 요청하는 것입니다. 중간에 더 요청하지 않으므로 무언가를 쥔 채 기다리는 상태가 생기지 않습니다. 둘째는 새 자원이 필요할 때마다 지금 쥔 자원을 모두 돌려준 뒤, 필요한 자원 전체를 다시 요청하는 것입니다.

두 방법 모두 대가가 큽니다. 첫째 방법에서는 마지막에 잠깐 쓸 자원도 처음부터 끝까지 쥐고 있어야 하므로 자원을 놀리게 됩니다. 많은 자원을 한꺼번에 원하는 작업은 그 자원이 동시에 모두 비는 순간을 기다려야 하므로 기아에 빠질 수 있습니다. 무엇보다 실행해 보기 전에는 어떤 자원이 필요할지 모르는 경우가 많습니다. 사용자의 입력에 따라 열어야 할 파일이 달라지는 프로그램이 그렇습니다.

비선점을 없애기

자원을 쥔 작업이 다른 자원을 요청했는데 바로 얻지 못하면, 쥔 자원을 강제로 돌려주게 하는 방법입니다. 이 방법은 상태를 저장했다가 되살릴 수 있는 자원에만 쓸 수 있습니다. CPU가 그 예로, 5장의 선점형 스케줄러는 실행 중인 작업의 레지스터를 저장하고 CPU를 빼앗습니다. 메모리 페이지도 디스크로 내보냈다가 다시 들여올 수 있습니다. 반면 프린터는 인쇄 도중 빼앗으면 출력물이 망가지고, 뮤텍스는 임계 영역 도중 빼앗으면 데이터가 반쯤 고쳐진 채로 남으므로 이 방법을 쓸 수 없습니다. 데이터베이스는 트랜잭션을 되돌릴 수 있으므로, 교착 상태가 생기면 트랜잭션 하나를 취소해 그 잠금을 빼앗는 방식으로 이 조건을 깨뜨리기도 합니다.

순환 대기를 없애기: 잠금에 순서를 정한다

실무에서 가장 많이 쓰는 방법입니다. 모든 자원에 번호를 매기고, 모든 작업이 번호가 커지는 순서로만 자원을 요청하게 합니다. 앞 글의 예에서 두 스레드가 모두 lock1을 먼저, lock2를 나중에 잠그게 하면 교착 상태가 생기지 않았던 것이 이 방법입니다.

/* 잠금 순서: lock1(1번) 다음 lock2(2번) */
static pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

static void *thread_a(void *arg)
{
    (void) arg;
    pthread_mutex_lock(&lock1);
    pthread_mutex_lock(&lock2);
    /* 작업 */
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

static void *thread_b(void *arg)
{
    (void) arg;
    pthread_mutex_lock(&lock1);     /* lock2부터 잠그지 않는다. */
    pthread_mutex_lock(&lock2);
    /* 작업 */
    pthread_mutex_unlock(&lock2);
    pthread_mutex_unlock(&lock1);
    return NULL;
}

번호 순서를 지키면 왜 원이 생기지 않을까요? 순환 대기가 있다고 가정해 보겠습니다. 원 위의 각 작업은 자기가 쥔 자원보다 번호가 큰 자원을 기다리고, 그 자원은 원의 다음 작업이 쥐고 있습니다. 원을 따라 한 바퀴 돌면 기다리는 자원의 번호가 계속 커져야 하는데, 출발한 작업으로 돌아오면 처음 자원보다 번호가 커진 자원이 처음 자원 자신이어야 하므로 모순입니다. 그러므로 모든 작업이 순서를 지키는 한 원은 생길 수 없습니다.

어려운 점은 모든 코드가 이 순서를 지키게 하는 것입니다. 잠금이 수십 개이고 코드가 여러 사람의 손을 거치면 누군가 순서를 어기기 쉽습니다. 그래서 순서를 실행 중에 검사하는 도구를 씁니다. Linux 커널의 lockdep은 잠금의 종류별로 어떤 순서로 잡혔는지를 기록해 두었다가, 반대 순서로 잡는 코드가 실행되면 실제로 교착 상태가 일어나기 전이라도 경고합니다. 다음 Python 코드는 같은 생각을 작게 구현한 것으로, 스레드마다 지금 쥔 잠금의 번호를 기억해 두고 더 작은 번호의 잠금을 잡으려 하면 오류를 냅니다.

import threading

_held = threading.local()                 # 스레드마다 지금 쥔 잠금의 순서 번호 목록

class OrderedLock:
    """번호가 커지는 순서로만 잠그도록 검사하는 잠금(푸는 순서는 with 문에 맡긴다)"""
    def __init__(self, order):
        self.order = order
        self._lock = threading.Lock()

    def __enter__(self):
        stack = _held.__dict__.setdefault("stack", [])
        if stack and stack[-1] >= self.order:
            raise RuntimeError(f"순서 위반: {stack[-1]}번을 쥔 채 {self.order}번을 잠그려 함")
        self._lock.acquire()
        stack.append(self.order)
        return self

    def __exit__(self, *exc):
        _held.stack.pop()
        self._lock.release()

accounts = OrderedLock(10)
orders = OrderedLock(20)

with accounts:
    with orders:
        print("10번, 20번 순서로 잠금: 성공")

try:
    with orders:
        with accounts:
            print("이 줄은 실행되지 않는다")
except RuntimeError as error:
    print(error)

10번, 20번 순서로 잠금: 성공
순서 위반: 20번을 쥔 채 10번을 잠그려 함

순서를 지킨 첫 블록은 정상적으로 실행되고, 20번을 쥔 채 10번을 잠그려는 둘째 블록은 실제로 잠금을 얻기 전에 오류가 납니다. 이렇게 하면 두 스레드가 정말로 엇갈려 멈추는 운 나쁜 순간을 기다리지 않고, 순서를 어기는 코드가 한 번이라도 실행되면 바로 알 수 있습니다. with 문을 쓰므로 잠금은 늘 잠근 역순으로 풀리고, 기록도 그에 맞추어 줄어듭니다. 실제 라이브러리라면 같은 번호의 잠금을 여러 개 다루는 규칙이나, 잠금 객체마다 기록을 맞추는 검사도 필요합니다.

회피: 위험한 상태로 들어가지 않는다

예방은 조건 하나를 늘 막으므로 단순하지만, 그만큼 자원을 쓰는 방식이 제한됩니다. 회피는 네 조건을 모두 허락하되, 자원을 요청받을 때마다 "이 요청을 들어주어도 모든 작업이 끝까지 실행될 수 있는가"를 따져 보고, 그렇지 않으면 요청을 미룹니다. 이를 위해 각 작업이 앞으로 최대 얼마만큼의 자원을 요청할지 미리 알려 주어야 합니다.

안전 상태와 불안전 상태

지금 자원을 나누어 준 상태에서, 모든 작업이 선언한 최대량까지 요청하더라도 어떤 순서로 실행하면 모두 끝낼 수 있다면 그 상태를 안전 상태(safe state)라고 하고, 그 순서를 안전 순서(safe sequence)라고 합니다. 남은 자원으로 최대 요구를 채워 줄 수 있는 작업을 먼저 끝내면 그 작업이 쥐었던 자원이 돌아오고, 늘어난 자원으로 다음 작업을 끝내는 식으로 모두를 끝낼 수 있다는 뜻입니다.

그런 순서가 하나도 없으면 불안전 상태(unsafe state)입니다. 불안전 상태가 곧 교착 상태는 아닙니다. 작업들이 실제로는 최대량까지 요청하지 않을 수도 있기 때문입니다. 하지만 최대량까지 요청하는 순간 교착 상태에 빠질 수 있으므로, 회피는 처음부터 불안전 상태에 들어가지 않습니다. 교착 상태는 불안전 상태의 일부이고, 안전 상태에서는 교착 상태가 생기지 않습니다.

은행원 알고리즘

은행원 알고리즘(banker's algorithm)은 데이크스트라가 1965년 무렵 제안한 회피 방법입니다. 은행이 고객들에게 대출 한도를 약속해 두고, 남은 현금으로 언제든 누군가의 한도를 끝까지 채워 줄 수 있는 범위에서만 돈을 내주는 것과 같은 원리입니다. 그 고객이 사업을 마치고 돈을 갚으면, 그 돈으로 다른 고객의 한도를 채워 줄 수 있습니다. 그래서 금고의 현금이 지금 0이라도, 추가로 돈이 필요 없는 고객이 있다면 위험한 것이 아닙니다.

필요한 자료

자원 유형이 $m$가지, 작업이 $n$개라면 다음 자료를 씁니다.

자원 A, B, C 세 가지와 작업 P0부터 P4까지 다섯이 있는 예를 보겠습니다. 지금 남은 자원은 A 3개, B 3개, C 2개이고, 각 작업의 최대 요구량과 지금 쥔 양, 그 차이인 남은 요구량은 다음과 같습니다.

안전한지 검사하기

안전성 검사는 남은 자원을 Work로 놓고 시작합니다. 아직 끝나지 않은 작업 가운데 Need가 Work 이하인 작업, 곧 최대 요구까지 채워 줄 수 있는 작업을 찾아, 그 작업이 끝나고 쥔 자원을 돌려준다고 보고 Work에 그 작업의 Allocation을 더합니다. 이를 되풀이해 모든 작업을 끝낼 수 있으면 안전하고, 중간에 끝낼 수 있는 작업이 없으면 불안전합니다.

처음에 Work는 [3, 3, 2]입니다. P1의 Need [1, 2, 2]는 세 자원 모두 Work 이하이므로 P1을 끝낼 수 있습니다. P1에게 남은 요구 [1, 2, 2]를 마저 주면 Work는 잠시 [2, 1, 0]이 되지만, P1이 끝나면서 원래 쥐었던 [2, 0, 0]과 방금 받은 [1, 2, 2]를 모두 돌려주므로 Work는 [5, 3, 2]가 됩니다. 결국 원래 Work에 P1의 Allocation만 더한 것과 같으므로, 계산에서는 Allocation만 더하면 됩니다. 이어서 P3의 [0, 1, 1]을 채워 [7, 4, 3]이 되고, P4의 [4, 3, 1]을 채워 [7, 4, 5]가 되며, P0의 [7, 4, 3]과 P2의 [6, 0, 0]도 차례로 채울 수 있어 마지막에 [10, 5, 7]이 됩니다. 모든 작업을 끝낼 수 있으므로 이 상태는 안전하고, P1, P3, P4, P0, P2는 안전 순서 가운데 하나입니다.

요청을 들어줄지 판단하기

작업 Pi가 자원을 요청하면 은행원 알고리즘은 다음 순서로 판단합니다.

1. 요청이 그 작업의 Need를 넘으면 선언한 최대량을 어긴 것이므로 오류입니다.
2. 요청이 Available을 넘으면 지금 자원이 모자라므로 기다리게 합니다.
3. 자료의 복사본에서 요청을 들어주었다고 가정하고, 그 상태가 안전한지 검사합니다.
4. 안전하면 실제로 내주고, 불안전하면 복사본을 버리고 기다리게 합니다.

다음 코드는 안전성 검사와 요청 판단을 구현하고, 앞의 상태에서 네 가지 요청을 판단합니다.

def need_of(max_need, allocation):
    return [[m - a for m, a in zip(mr, ar)] for mr, ar in zip(max_need, allocation)]

def is_safe(available, max_need, allocation):
    """안전 순서가 있으면 그 순서를, 없으면 None을 돌려준다."""
    need = need_of(max_need, allocation)
    work, finish, order = available[:], [False] * len(allocation), []
    progress = True
    while progress:
        progress = False
        for i in range(len(allocation)):
            if not finish[i] and all(n <= w for n, w in zip(need[i], work)):
                work = [w + a for w, a in zip(work, allocation[i])]   # 끝나면 쥔 것을 돌려준다
                finish[i] = True
                order.append(f"P{i}")
                progress = True
    return order if all(finish) else None

def request(i, req, available, max_need, allocation):
    need = need_of(max_need, allocation)
    if any(r > n for r, n in zip(req, need[i])):
        return "오류: 선언한 최대 요구량을 넘음"
    if any(r > a for r, a in zip(req, available)):
        return "대기: 지금 남은 자원이 부족함"
    trial_avail = [a - r for a, r in zip(available, req)]             # 복사본에서 시험한다
    trial_alloc = [row[:] for row in allocation]
    trial_alloc[i] = [a + r for a, r in zip(trial_alloc[i], req)]
    order = is_safe(trial_avail, max_need, trial_alloc)
    return f"허락: 안전 순서 {order}" if order else "대기: 들어주면 불안전 상태가 됨"

available = [3, 3, 2]                     # 자원 A, B, C의 남은 수
max_need = [[7, 5, 3], [3, 2, 2], [9, 0, 2], [2, 2, 2], [4, 3, 3]]
allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 2], [2, 1, 1], [0, 0, 2]]

print("현재 상태의 안전 순서:", is_safe(available, max_need, allocation))
print("P1이 [1, 0, 2] 요청:", request(1, [1, 0, 2], available, max_need, allocation))
print("P4가 [3, 3, 0] 요청:", request(4, [3, 3, 0], available, max_need, allocation))
print("P0가 [0, 2, 0] 요청:", request(0, [0, 2, 0], available, max_need, allocation))
print("P2가 [4, 0, 0] 요청:", request(2, [4, 0, 0], available, max_need, allocation))

현재 상태의 안전 순서: ['P1', 'P3', 'P4', 'P0', 'P2']
P1이 [1, 0, 2] 요청: 허락: 안전 순서 ['P1', 'P3', 'P4', 'P0', 'P2']
P4가 [3, 3, 0] 요청: 대기: 들어주면 불안전 상태가 됨
P0가 [0, 2, 0] 요청: 허락: 안전 순서 ['P3', 'P1', 'P2', 'P0', 'P4']
P2가 [4, 0, 0] 요청: 대기: 지금 남은 자원이 부족함

P1의 요청 [1, 0, 2]는 P1의 Need [1, 2, 2]와 남은 자원 [3, 3, 2] 안에 들어갑니다. 들어준다고 가정하면 남은 자원은 [2, 3, 0], P1의 Need는 [0, 2, 0]이 되는데, 이 상태에서도 P1을 먼저 끝내 [5, 3, 2]를 만들 수 있고 나머지도 차례로 끝낼 수 있으므로 허락합니다.

P4의 요청 [3, 3, 0]도 P4의 Need [4, 3, 1]과 남은 자원 안에 들어갑니다. 그런데 들어준다고 가정하면 남은 자원이 [0, 0, 2]가 되고, P0은 A, B, C가, P1은 A와 B가, P2는 A가, P3은 B가, 요청 뒤 Need가 [1, 0, 1]이 된 P4는 A가 모자라 아무도 먼저 끝낼 수 없습니다. 그래서 남은 자원이 충분한데도 기다리게 합니다. 지금 당장 교착 상태가 되는 것은 아니지만, 모두가 최대량까지 요청하면 빠져나올 길이 없는 상태로 들어가지 않으려는 것입니다. P2의 요청 [4, 0, 0]은 Need [6, 0, 0] 안에는 들어가지만 남은 A가 3개뿐이어서 안전성을 따지기 전에 기다리게 됩니다.

시험은 반드시 복사본에서 해야 합니다. 원래 자료를 고친 채로 검사했다가 불안전으로 판정되면 원래대로 되돌려야 하는데, 되돌리는 과정에서 실수하면 이후의 모든 판단이 틀어집니다.

은행원 알고리즘을 실제로 쓰기 어려운 이유

은행원 알고리즘은 우아하지만 범용 운영체제에서는 거의 쓰이지 않습니다. 첫째, 각 작업이 실행하기 전에 최대 요구량을 알려야 하는데, 사용자 입력이나 실행 중의 조건에 따라 필요한 자원이 달라지는 프로그램이 대부분입니다. 둘째, 작업이 생기고 사라질 때마다 최대 요구량과 할당 상태를 정확히 맞추어 관리해야 합니다. 셋째, 요청할 때마다 안전성 검사에 $O(n^2 \times m)$의 시간이 들어, 작업과 자원이 많으면 부담이 큽니다. 그래서 이 방법은 자원의 종류와 최대 요구량이 미리 정해진 일부 시스템에서나 쓰이고, 일반적인 프로그램은 잠금 순서 같은 예방 방법과 다음 글의 탐지와 복구에 기댑니다.

시도 잠금과 물러나기

실무에서는 잠금 순서를 정하는 것을 기본으로 하고, 순서를 지키기 어려운 곳에는 기다리지 않는 잠금 시도를 섞어 씁니다. 다음 C 코드는 두 번째 잠금을 pthread_mutex_trylock으로 시도하고, 얻지 못하면 첫 잠금까지 돌려준 뒤 잠시 기다렸다 다시 시도합니다.

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

static pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
static pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

static void *careful_worker(void *arg)
{
    (void) arg;
    for (int retries = 0; retries < 5; retries++) {
        pthread_mutex_lock(&lock1);
        if (pthread_mutex_trylock(&lock2) == 0) {   /* 얻지 못하면 기다리지 않고 바로 돌아온다. */
            printf("작업 수행\n");
            pthread_mutex_unlock(&lock2);
            pthread_mutex_unlock(&lock1);
            return NULL;
        }
        pthread_mutex_unlock(&lock1);               /* 쥔 것까지 돌려주고 물러난다. */
        usleep(100u << retries);                    /* 100, 200, 400 ... 마이크로초 */
    }
    printf("잠금을 얻지 못해 다른 방법으로 처리\n");
    return NULL;
}

두 번째 잠금을 얻지 못하면 첫 잠금까지 돌려주므로, 무언가를 쥔 채 기다리는 일이 없어 점유와 대기 조건이 깨집니다. 물러나는 간격을 두 배씩 늘리는 지수 물러나기(exponential backoff)는 같은 시간 동안 다시 시도하는 횟수를 줄여 경쟁을 덜어 줍니다. 하지만 이 코드처럼 모든 스레드가 같은 간격을 따르면, 같은 순간에 실패한 스레드들은 앞 글의 라이브락처럼 계속 같은 박자로 부딪힐 수 있으므로, 실제로는 간격을 무작위로 흩뜨려(jitter) 박자를 어긋나게 합니다. 다만 이것만으로 언젠가 성공한다고 보장할 수는 없으므로, 재시도 횟수에 상한을 두고 끝내 실패하면 다른 방법으로 처리하는 경로를 마련해야 합니다. 이 코드에서 상한은 두 번째 잠금 시도에만 걸려 있고 첫 pthread_mutex_lock에는 시간 제한이 없으므로, 함수 전체가 언제 끝날지까지 보장하지는 않는다는 점도 알아 두어야 합니다.

더 깊이: 순서를 정할 수 없는 잠금 묶음과 나이 순 양보

잠그는 순서를 아예 정할 수 없는 경우도 있습니다. Linux의 wound/wait 뮤텍스 설계 문서가 드는 예는 GPU 작업으로, 작업 하나가 버퍼 여러 개를 함께 잠가야 하는데 버퍼가 작업마다 어떤 순서로 나올지 미리 정할 수 없습니다. 이런 곳에 쓰는 ww_mutex는 잠금 묶음을 얻기 시작하는 작업마다 전역 계수기에서 번호표(ticket)를 하나 나누어 주고, 번호가 작은 작업을 더 오래된 작업으로 봅니다. 두 작업이 부딪히면 언제나 더 오래된 작업이 이깁니다. 두 방식의 이름은 데이터베이스 문헌에서 트랜잭션의 교착 상태를 다루던 방법에서 왔습니다.

부딪혔을 때 누가 물러날지는 두 방식 가운데 하나로 정합니다. Wait-Die에서는 잠금을 쥔 쪽이 더 젊으면 요청한 쪽이 기다리고, 더 오래되었으면 요청한 쪽이 물러납니다. Wound-Wait에서는 잠금을 쥔 쪽이 더 젊으면 요청한 쪽이 그 작업에게 물러나라고 요구하고, 더 오래되었으면 요청한 쪽이 기다립니다. 진 작업은 -EDEADLK를 받고, 이미 쥔 잠금을 모두 놓은 뒤 부딪혔던 잠금부터 다시 얻기 시작합니다. 문서는 Wound-Wait가 물러나는 횟수는 적지만 물러난 뒤 복구할 일이 더 많다고 보고, 동시에 경쟁하는 작업이 대개 적을 때 Wound-Wait를 쓰라고 권합니다.

앞의 시도 잠금과 달리 이 방식에서는 지금 가장 오래된 작업이 물러나는 일이 없습니다. 그래서 문서는 물러난 작업이 다시 시도할 때 새 번호표를 받지 말고 처음 받은 번호표를 그대로 써야 결국 진척이 있다고 강조합니다. 새 번호표를 받으면 다시 가장 젊은 작업이 되어 계속 질 수 있지만, 처음 번호표를 지키면 시간이 지나 그 작업이 가장 오래된 작업이 되기 때문입니다.

정리

• 예방은 교착 상태의 네 조건 가운데 하나를 원천적으로 막습니다. 상호 배제는 스풀링으로 우회하고, 점유와 대기는 한꺼번에 요청하거나 다 돌려준 뒤 다시 요청해 깨고, 비선점은 상태를 저장할 수 있는 자원에서만 깰 수 있습니다.
• 실무에서 가장 많이 쓰는 예방은 모든 잠금에 순서를 정하고 그 순서대로만 잠그는 것이며, lockdep 같은 도구로 순서 위반을 미리 찾습니다.
• 회피는 자원을 내줄 때마다 들어주어도 안전 상태가 유지되는지 따져, 불안전 상태로 들어가는 요청을 미룹니다. 불안전 상태가 곧 교착 상태는 아니지만, 그 안에서는 교착 상태가 생길 수 있습니다.
• 은행원 알고리즘은 Need가 Work 이하인 작업을 차례로 끝내며 안전 순서를 찾고, 요청을 복사본에서 시험한 뒤 안전할 때만 들어줍니다.
• 최대 요구량을 미리 알아야 하고 검사 비용이 크기 때문에, 범용 시스템은 은행원 알고리즘보다 잠금 순서와 시도 잠금, 탐지와 복구를 주로 씁니다.

연습 문제

1. P0의 요청을 손으로 판단하기

본문의 처음 상태에서 P0이 [0, 2, 0]을 요청합니다. Need와 남은 자원과 비교한 뒤, 들어준다고 가정한 남은 자원, P0의 Allocation과 Need를 구하세요. 그리고 P0부터 P4까지 차례로 살피는 방식으로 안전 순서를 찾아, 요청을 들어줄 수 있는지 판단하세요.

2. 계좌 번호로 잠금 순서 정하기

계좌 이체 함수 transfer(src, dst, amount)가 src의 잠금을 먼저, dst의 잠금을 나중에 얻습니다. X에서 Y로, Y에서 X로의 이체가 동시에 실행되면 교착 상태가 생길 수 있습니다. 잠금 순서 정하기로 이 함수를 고치는 방법을 설명하고, 고친 뒤에는 왜 원이 생기지 않는지 설명하세요. 같은 계좌로 이체하는 경우도 따져 보세요.

3. 안전 상태와 교착 상태

동료가 "불안전 상태라는 판정이 나왔으니 지금 시스템이 교착 상태에 빠졌다"고 말했습니다. 이 말이 맞는지 설명하고, 은행원 알고리즘이 불안전 상태를 피하는 이유를 말하세요.

다음 글 데드락 탐지와 복구에서는 교착 상태가 생기는 것을 허락하되, 주기적으로 찾아내고 작업을 끝내거나 자원을 빼앗아 풀어내는 방법을 살펴봅니다.