데드락 탐지와 복구

앞 글의 예방은 자원을 쓰는 방식을 제한하고, 회피는 앞으로 필요한 자원의 최대량을 미리 알아야 합니다. 두 조건을 모두 받아들이기 어려운 시스템에서는 다른 방법을 씁니다. 교착 상태가 생기는 것은 일단 허락하고, 주기적으로 찾아내(detection) 풀어내는(recovery) 것입니다.

이 방법을 누가 맡는지는 자원을 관리하는 계층마다 다릅니다. 데이터베이스는 자기가 관리하는 행 잠금과 테이블 잠금 사이의 교착 상태를 스스로 찾아 트랜잭션 하나를 되돌립니다. 반면 범용 운영체제는 사용자 프로그램들이 쓰는 뮤텍스 사이의 교착 상태를 찾아 풀어 주지 않으므로, 프로그램 쪽에서 시간 제한이나 감시 도구로 대비해야 합니다. 이 글에서는 교착 상태를 찾는 알고리즘과, 찾은 뒤 풀어내는 방법을 살펴봅니다.

인스턴스가 하나인 자원: 대기 그래프

모든 자원 유형의 인스턴스가 하나뿐이라면, 7장 1편에서 본 대기 그래프(wait-for graph)로 충분합니다. 자원 할당 그래프에서 자원 노드를 지우고, 작업 Pi가 작업 Pj가 쥔 자원을 기다리면 Pi에서 Pj로 간선을 그립니다. 빼앗을 수 없고 다 쓰면 돌려주는 자원이라면, 이 그래프에 사이클이 있는 것이 곧 교착 상태입니다. 사이클은 깊이 우선 탐색으로 노드 수와 간선 수에 비례하는 시간에 찾을 수 있습니다.

그림에서 P1, P2, P3는 서로를 기다리는 원을 이루고, P4는 원 밖에서 P2를 기다립니다. P4는 원의 구성원이 아니지만, P2가 영원히 끝나지 않으므로 P4도 끝날 수 없습니다. 교착 상태를 풀 때 무엇을 건드려야 하는지와, 어떤 작업들이 영향을 받는지를 구분해야 합니다. 다음 코드는 두 가지를 따로 계산합니다.

def cycle_members(graph):
    """대기 그래프에서 사이클 위에 있는 작업을 모두 찾는다. graph: 작업 -> 기다리는 작업 목록"""
    def reaches(start, target, seen):
        for nxt in graph.get(start, []):
            if nxt == target or (nxt not in seen and reaches(nxt, target, seen | {nxt})):
                return True
        return False
    return sorted(p for p in graph if reaches(p, p, {p}))

def stuck(graph):
    """끝날 수 없는 작업: 끝날 수 없는 작업을 하나라도 기다리는 작업까지 포함한다."""
    done = {p for p in graph if not graph[p]}            # 아무도 기다리지 않는 작업은 끝낼 수 있다
    changed = True
    while changed:
        changed = False
        for p, targets in graph.items():
            if p not in done and all(t in done for t in targets):
                done.add(p)                              # 기다리는 상대가 모두 끝나면 이 작업도 끝난다
                changed = True
    return sorted(p for p in graph if p not in done)

graph = {"P1": ["P2"], "P2": ["P3"], "P3": ["P1"], "P4": ["P2"], "P5": []}
print("사이클 위의 작업:", cycle_members(graph))
print("끝날 수 없는 작업:", stuck(graph))

사이클 위의 작업: ['P1', 'P2', 'P3']
끝날 수 없는 작업: ['P1', 'P2', 'P3', 'P4']

cycle_members는 자기 자신에게 돌아오는 경로가 있는 작업, 곧 사이클 위의 작업을 찾습니다. 교착 상태를 풀려면 이 가운데 적어도 하나를 끝내거나 그 자원을 빼앗아야 합니다. stuck은 반대 방향으로 계산합니다. 아무도 기다리지 않는 P5는 끝날 수 있고, 기다리는 상대가 모두 끝날 수 있는 작업도 끝날 수 있다고 보고 넓혀 가면, 끝내 끝날 수 있다고 표시되지 못한 작업이 남습니다. P4는 사이클 위에 있지 않지만 끝날 수 없는 작업에 들어갑니다. 원을 풀면 P4도 함께 풀리므로, P4를 희생자로 고를 필요는 없습니다.

인스턴스가 여러 개인 자원: 탐지 알고리즘

자원 유형마다 인스턴스가 여러 개라면 사이클만으로는 판단할 수 없으므로, 은행원 알고리즘과 비슷한 계산을 합니다. 차이는 앞으로의 최대 요구량(Need) 대신 지금 실제로 요청하고 있는 양(Request)을 쓴다는 것입니다. 회피는 앞으로 일어날 수 있는 최악을 대비하지만, 탐지는 지금 이미 빠져나올 수 없는 상태인지를 묻기 때문입니다.

계산 방법은 앞 글의 안전성 검사와 같습니다. 남은 자원을 Work로 놓고, 지금 요청을 채워 줄 수 있는 작업을 찾아 그 작업이 끝나고 쥔 자원을 돌려준다고 봅니다. 이를 되풀이해도 끝내 요청을 채울 수 없는 작업이 남으면, 그 작업들이 교착 상태에 있습니다. 처음부터 아무 자원도 쥐지 않은 작업은 다른 작업을 막지 않으므로 교착 상태의 작업에서 뺍니다.

def detect_deadlock(available, allocation, request):
    """지금 요청(Request)으로 끝까지 진행할 수 없는, 자원을 쥔 작업의 번호를 돌려준다."""
    work = available[:]
    finish = [all(a == 0 for a in row) for row in allocation]   # 쥔 것이 없으면 남을 막지 않는다
    changed = True
    while changed:
        changed = False
        for i, row in enumerate(allocation):
            if not finish[i] and all(r <= w for r, w in zip(request[i], work)):
                work = [w + a for w, a in zip(work, row)]          # 끝나면 쥔 것을 돌려준다
                finish[i] = changed = True
    return [i for i, done in enumerate(finish) if not done]

available = [0, 0, 0]
allocation = [[0, 1, 0], [2, 0, 0], [3, 0, 3], [2, 1, 1], [0, 0, 2]]
request = [[0, 0, 0], [2, 0, 2], [0, 0, 0], [1, 0, 0], [0, 0, 2]]
print("교착 상태의 작업:", detect_deadlock(available, allocation, request))

request[2] = [1, 0, 0]                    # P2가 A를 하나 더 요청한다면
print("P2도 요청할 때:", detect_deadlock(available, allocation, request))

교착 상태의 작업: []
P2도 요청할 때: [1, 2, 3, 4]

첫째 경우는 남은 자원이 하나도 없는데도 교착 상태가 아닙니다. 아래 단계 개념도로 계산을 따라가 보겠습니다.

P0은 더 요청하는 것이 없으므로 남은 자원이 0이어도 끝낼 수 있고, 쥐었던 [0, 1, 0]을 돌려줘 Work가 [0, 1, 0]이 됩니다. P1은 [2, 0, 2]를 요청하므로 이 시점에는 채울 수 없어 건너뜁니다. P2도 더 요청하는 것이 없으므로 끝나고 [3, 0, 3]을 돌려줘 Work가 [3, 1, 3]이 됩니다. P3의 요청 [1, 0, 0]을 채워 끝내면 [5, 2, 4], P4의 요청 [0, 0, 2]를 채워 끝내면 [5, 2, 6]이 됩니다. 다음 바퀴에서 처음에 건너뛰었던 P1의 [2, 0, 2]도 채울 수 있어 모두 끝납니다. 남은 자원이 0이라는 것, 한 번 건너뛰었다는 것만으로 교착 상태라고 할 수는 없습니다. 한 바퀴를 다 돌아도 더 끝낼 수 있는 작업이 없을 때 남은 작업들이 교착 상태입니다.

P3를 끝낼 때 Work에 더하는 것도 따져 볼 만합니다. P3에게 요청한 [1, 0, 0]을 주면 Work는 잠시 [2, 1, 3]이 되지만, P3가 끝나면서 원래 쥔 [2, 1, 1]과 받은 [1, 0, 0]을 모두 돌려주므로 [5, 2, 4]가 됩니다. 결국 원래 Work에 Allocation만 더한 것과 같습니다.

둘째 경우는 P2가 A를 하나 더 요청한다고 바꾼 것입니다. 그러면 P0이 끝나 Work가 [0, 1, 0]이 된 뒤로는, P1은 A와 C가, P2와 P3는 A가, P4는 C가 모자라 아무도 끝낼 수 없습니다. 그래서 P1부터 P4까지 넷이 교착 상태에 있다고 판정됩니다.

탐지를 언제 실행할까

탐지 알고리즘은 작업 수 $n$과 자원 유형 수 $m$에 대해 $O(n^2 \times m)$의 시간이 드므로, 얼마나 자주 실행할지가 맞바꿈의 문제가 됩니다. 자원 요청이 있을 때마다 실행하면 교착 상태가 생기는 순간 찾을 수 있지만 비용이 큽니다. 몇십 초나 몇 분마다 주기적으로 실행하면 비용은 줄지만, 교착 상태가 찾아질 때까지 관련 작업들이 멈춰 있습니다. CPU 사용률이 갑자기 떨어지는 것을 계기로 실행하는 방법도 있습니다. 많은 작업이 교착 상태에 빠지면 일할 수 있는 작업이 줄어 CPU가 놀기 때문입니다. 실용적인 절충은 요청을 바로 들어줄 수 없어 작업이 기다리기 시작할 때만 실행하는 것입니다. 새로운 대기가 생길 때만 새로운 교착 상태가 생길 수 있기 때문입니다.

MySQL의 InnoDB는 이 탐지를 기본으로 켜 두고, 교착 상태를 찾으면 되돌리는 비용이 작은 트랜잭션, 곧 넣거나 고치거나 지운 행이 적은 트랜잭션을 골라 되돌립니다. 동시에 실행되는 트랜잭션이 아주 많아 탐지 자체가 부담이 되는 환경에서는 탐지를 끄고 잠금 대기 시간 제한(innodb_lock_wait_timeout)에 맡기기도 합니다. 이때 주의할 점은 시간이 초과되어도 기본적으로는 그 문장 하나만 되돌리고 트랜잭션 전체는 되돌리지 않는다는 것입니다. 트랜잭션 전체를 되돌리려면 innodb_rollback_on_timeout을 설정하거나 애플리케이션이 오류를 받아 직접 되돌려야 합니다. 자세한 내용은 InnoDB 교착 상태 탐지 문서에 있습니다.

교착 상태에서 복구하기

교착 상태를 찾았으면 원을 끊어야 합니다. 방법은 크게 작업을 끝내는 것과 자원을 빼앗는 것 두 가지이며, 어느 쪽이든 어떤 작업을 희생할지와 어디까지의 손실을 받아들일지를 함께 정해야 합니다.

작업을 끝내기

가장 직접적인 방법은 교착 상태에 걸린 작업을 끝내는 것입니다. 관련된 작업을 모두 끝내면 확실히 풀리지만 그동안 한 일을 모두 잃습니다. 하나씩 끝내며 그때마다 탐지 알고리즘을 다시 돌려 풀렸는지 확인하면 손실은 줄지만, 탐지를 여러 번 실행하는 비용이 듭니다. 하나씩 끝낼 때는 어떤 작업을 먼저 끝낼지 정해야 하며, 다음과 같은 기준을 함께 따집니다.

작업을 끝낸다고 그 작업이 한 일이 모두 사라지는 것은 아니라는 점에 주의해야 합니다. 데이터베이스 트랜잭션 안에서 바꾼 데이터는 되돌릴 수 있지만, 이미 쓴 파일이나 보낸 메시지, 외부 서비스에 보낸 요청처럼 트랜잭션 밖의 효과는 그대로 남습니다.

자원을 빼앗기

다른 방법은 교착 상태에 걸린 작업에서 자원을 빼앗아 다른 작업에 주는 것입니다. 이때는 세 가지 문제를 풀어야 합니다.

첫째는 희생자를 고르는 것입니다. 어떤 작업에서 어떤 자원을 빼앗을지는 앞의 기준처럼 비용이 가장 작은 쪽으로 정합니다.

둘째는 되돌리기(rollback)입니다. 자원을 빼앗긴 작업은 그 자원을 쓰던 중간 상태에 머물 수 없으므로, 그 자원을 얻기 전의 안전한 상태로 되돌려야 합니다. 작업 상태를 주기적으로 저장해 두는 체크포인트(checkpoint)가 있으면 그 시점까지만 되돌리면 되므로 손실이 줄어듭니다. 체크포인트가 없다면 처음부터 다시 실행해야 하는데, 그러려면 같은 입력을 다시 받을 수 있고 외부 효과를 정리할 수 있도록 처음부터 다시 시작할 수 있게 설계되어 있어야 합니다. 일반적인 뮤텍스를 빼앗거나 프로세스를 다시 시작하는 것만으로는 상태가 되돌아오지 않습니다.

셋째는 기아를 막는 것입니다. 늘 같은 작업이 희생자로 뽑히면 그 작업은 영원히 끝나지 못합니다. 그래서 희생된 횟수를 비용에 넣어, 자주 희생된 작업은 다음에 덜 뽑히도록 합니다.

외부 효과까지 생각한 복구

데이터베이스가 교착 상태를 풀려고 트랜잭션을 되돌렸다고 해 봅시다. 그 트랜잭션은 주문 기록을 바꾸는 도중에 이미 고객에게 알림 메일을 보냈습니다. 데이터베이스의 변경은 모두 원래대로 돌아왔지만, 보낸 메일은 돌아오지 않습니다. 애플리케이션이 같은 작업을 다시 시도하면 고객은 메일을 두 번 받게 됩니다.

그래서 교착 상태로 되돌려질 수 있는 작업은 다시 실행해도 결과가 같도록 설계하는 것이 좋습니다. 외부로 나가는 효과는 트랜잭션이 확정된 뒤에 보내거나, 업무 식별자를 붙여 같은 요청이 두 번 처리되지 않게 합니다. 이런 다시 시도해도 안전한 처리는 15장에서 자세히 다룹니다.

아무것도 하지 않는 선택: 타조 알고리즘

교착 상태에 대해 아무 대비도 하지 않는 것도 하나의 선택입니다. 위험이 닥치면 모래에 머리를 묻는다는 속설에서 따와 타조 알고리즘(ostrich algorithm)이라고 부릅니다. 교착 상태가 아주 드물게 생기고 생겼을 때 사람이 다시 시작하는 비용이 작다면, 예방하거나 탐지하느라 늘 치르는 비용보다 이쪽이 쌀 수 있습니다. 실제로 범용 운영체제는 사용자 프로그램의 잠금 사이의 교착 상태를 대부분 이렇게 다룹니다.

다만 이 판단은 발생 빈도만으로 내릴 수 없습니다. 예를 들어 탐지 때문에 처리량이 늘 5% 줄어드는 것과, 한 달에 한 번 5분 동안 서비스가 멈추는 것을 비교한다고 해 봅시다. 멈춘 동안 데이터가 손상될 수 있는지, 영향을 받는 사용자가 얼마나 되는지, 서비스가 멈춰도 되는 시간이 얼마인지에 따라 결론이 달라집니다.

실무에서 여러 전략을 조합하기

실무에서는 한 가지 전략만 쓰지 않고 단계마다 다른 방법을 조합합니다.

설계 단계에서는 예방에 집중합니다. 팀 전체가 잠그는 순서를 정해 문서로 남기고, 코드 검토에서 순서를 어기는 코드를 찾습니다. 잠금을 쥐는 구간은 짧게 하고, 잠금을 쥔 채 입출력을 하지 않습니다. 처음에는 큰 잠금 하나(coarse-grained locking)로 단순하게 시작하고, 성능이 문제가 될 때만 잠금을 잘게 나눕니다(fine-grained locking). 잠금이 많아질수록 순서를 지키기 어려워지기 때문입니다.

구현 단계에서는 기다림에 기한을 둡니다. 여러 잠금을 얻어야 할 때는 하나라도 시간 안에 얻지 못하면 이미 얻은 잠금을 모두 돌려주고 포기하는 방식이 안전합니다. 다음 코드는 그런 도우미 함수와, 다른 작업이 한 잠금을 오래 쥐고 있을 때의 동작을 보여 줍니다.

import threading

def acquire_all(locks, timeout):
    """잠금을 차례로 얻되, 하나라도 시간 안에 못 얻으면 얻은 것을 모두 돌려주고 False"""
    taken = []
    for lock in locks:
        if not lock.acquire(timeout=timeout):
            for held in reversed(taken):
                held.release()
            return False
        taken.append(lock)
    return True

lock1, lock2 = threading.Lock(), threading.Lock()
lock2.acquire()                            # 다른 작업이 lock2를 오래 쥐고 있다

ok = acquire_all([lock1, lock2], timeout=0.1)
print("두 잠금을 모두 얻음:", ok)
print("포기한 뒤 lock1이 다시 비어 있음:", lock1.acquire(blocking=False))

두 잠금을 모두 얻음: False
포기한 뒤 lock1이 다시 비어 있음: True

lock1은 얻었지만 lock2를 0.1초 안에 얻지 못하자, 함수는 lock1까지 돌려주고 실패를 알립니다. 그래서 포기한 뒤에 lock1을 다시 얻을 수 있습니다. 쥔 것을 모두 돌려주므로 점유와 대기 조건이 깨지고, 이 함수를 쓰는 작업끼리는 교착 상태가 생기지 않습니다. 실패했을 때 바로 다시 시도하면 7장 1편의 라이브락이 생길 수 있으므로, 무작위로 잠시 기다린 뒤 다시 시도하고 재시도 횟수에 상한을 두는 것을 함께 씁니다.

운영 단계에서는 교착 상태를 찾고 대응하는 도구를 갖춥니다. Java는 스레드 덤프와 ThreadMXBean.findDeadlockedThreads()로 모니터와 java.util.concurrent 잠금 사이의 교착 상태를 찾을 수 있지만, 가상 스레드나 외부 자원을 기다리는 경우까지 찾지는 못합니다. MySQL은 innodb_deadlock_detect가 켜져 있으면 스스로 찾아 트랜잭션을 되돌리고, SHOW ENGINE INNODB STATUS로 내용을 확인할 수 있습니다. Linux 커널 개발에서는 lockdep으로 잠금 순서 위반을 찾고, perf lock으로 잠금 경쟁을 분석합니다. 분산 시스템에서는 시간 제한과 서킷 브레이커(circuit breaker)로 기다림과 실패가 퍼지는 것을 막지만, 메시지 큐를 쓰더라도 소비자들 사이에 원형으로 기다리는 구조가 생기지 않는지는 따로 설계해야 합니다.

더 깊이: 커널은 자기 안에서 멈춘 작업을 어떻게 알아챌까

범용 운영체제는 사용자 프로그램의 교착 상태를 풀어 주지 않지만, 커널 자신이 멈춘 상황은 알아채려고 합니다. 다만 대기 그래프를 계산하는 대신, 너무 오래 진행하지 못한 상태를 시간으로 감지합니다. CONFIG_DETECT_HUNG_TASK를 켠 커널은 D 상태에 머문 채 오래 스케줄되지 못한 작업을 걸린 작업(hung task)으로 보고 경고와 스택 추적을 출력합니다. 기준 시간은 /proc/sys/kernel/hung_task_timeout_secs로 정하며, 기본값은 120초이고 0이면 검사하지 않습니다.

이 검사는 복구가 아니라 탐지입니다. 경고를 출력한 뒤에도 그 작업은 같은 상태에 그대로 남습니다. 대신 앞 글에서 본 lockdep을 함께 켜 두면 그 작업이 쥐고 있는 잠금도 모두 보고하므로, 누가 무엇을 쥔 채 멈췄는지 이어 보는 데 도움이 됩니다.

CPU가 아예 커널 모드에서 빠져나오지 못하는 경우는 락업 감지기 문서의 두 감지기가 찾습니다. 소프트 락업(soft lockup)은 커널 모드에서 다른 작업에게 차례를 주지 않고 20초 넘게 도는 것이고, 하드 락업(hard lockup)은 다른 인터럽트도 처리하지 못한 채 몇 초 동안 도는 것입니다. 기준은 watchdog_thresh(기본 10초)로 정해지며, 감지하면 스택 추적을 출력하고 기본으로는 시스템이 멈춘 채로 남지만 설정으로 커널 패닉을 일으키게 할 수 있습니다. 스핀락을 서로 기다리며 도는 커널 코드는 D 상태가 아니므로 걸린 작업 검사가 아니라 이런 락업 감지기로 드러납니다.

정리

• 탐지와 복구는 교착 상태가 생기는 것을 허락하고, 찾아내서 풀어내는 방법입니다. 데이터베이스는 이를 스스로 하지만, 범용 운영체제는 사용자 프로그램의 잠금 교착 상태를 풀어 주지 않습니다.
• 인스턴스가 하나인 자원에서는 대기 그래프의 사이클이 곧 교착 상태입니다. 사이클 위의 작업과, 그 작업들을 기다려 함께 멈춘 작업을 구분해야 합니다.
• 인스턴스가 여러 개인 자원에서는 지금의 요청량(Request)으로 끝낼 수 있는 작업을 차례로 지워 나가, 끝내 남는 작업을 교착 상태로 판정합니다.
• 탐지는 요청마다, 주기적으로, 또는 작업이 기다리기 시작할 때 실행할 수 있으며, 빈도와 비용을 맞바꿉니다.
• 복구는 작업을 끝내거나 자원을 빼앗아 되돌리는 방법으로 하며, 희생자를 고르는 기준, 체크포인트, 기아 방지, 트랜잭션 밖의 외부 효과를 함께 고려해야 합니다.
• 실무에서는 설계 단계의 잠금 순서, 구현 단계의 기한과 포기, 운영 단계의 탐지 도구를 조합합니다.

연습 문제

1. 첫 사이클만 찾는 함수의 한계

대기 그래프에 A와 B가 서로를 기다리는 원, C와 D가 서로를 기다리는 원이 따로 있습니다. 처음 찾은 사이클 하나만 돌려주고 끝나는 탐지 함수를 쓰면 어떤 문제가 생길까요? 본문의 cycle_members 함수로 계산하면 결과가 어떻게 되나요?

2. 쥔 것이 없는 작업

본문의 둘째 경우, 곧 P2가 [1, 0, 0]을 요청하는 상태에 작업 P5를 더합니다. P5는 아무 자원도 쥐지 않았고 A를 하나 요청합니다. 탐지 결과는 어떻게 되나요? P5가 결과에 들어가지 않는다는 것이 P5가 곧 실행된다는 뜻인가요?

3. 되돌린 트랜잭션과 두 번 보낸 메일

주문 처리 트랜잭션이 주문 상태를 바꾸고, 고객에게 알림 메일을 보낸 뒤, 재고 테이블을 고치려다 교착 상태의 희생자로 되돌려졌습니다. 애플리케이션은 오류를 받고 같은 작업을 처음부터 다시 실행했습니다. 데이터베이스가 원래대로 돌아왔다는 사실만으로 이 처리가 안전하다고 할 수 있을까요? 고치는 방법을 두 가지 제안하세요.

다음 장의 주소 바인딩에서는 운영체제가 관리하는 또 다른 핵심 자원인 메모리로 넘어가, 프로그램의 주소가 언제 실제 메모리 위치로 정해지는지 살펴봅니다.