데드락 탐지와 복구

대기 그래프를 축약한다

자원 노드를 빼고 프로세스가 어떤 프로세스를 기다리는지 wait-for graph로 표현한다.

단일 인스턴스 자원에서는 wait-for graph cycle이 deadlock 탐지의 핵심이다.

종료 비용, 우선순위, 수행 시간, 보유 자원 수를 기준으로 복구 대상을 선택한다.

Detection interval

검사 주기 자주 검사하면 overhead가 크고, 늦게 검사하면 멈춘 시간이 길다.

시스템 성격에 따라 다르다.

Victim

복구 대상 가장 비용이 작은 프로세스를 종료하거나 rollback한다.

기아를 막기 위해 반복 희생을 피한다.

Rollback

이전 상태 복귀 checkpoint가 있어야 안전하게 되돌릴 수 있다.

DB와 batch 시스템에서 중요하다.

Resource preemption

강제 회수 일부 자원은 빼앗아도 되지만 printer, lock, 파일 작업은 어렵다.

자원 종류별 정책이 필요하다.

그래프 대기 관계를 wait-for graph로 줄여 cycle을 찾을 수 있는가.

주기 탐지를 얼마나 자주 실행할지 overhead와 멈춤 시간을 비교하는가.

복구 프로세스 종료와 자원 선점의 데이터 손실 비용을 고려하는가.

build wait-for graph
if cycle exists:
  choose victim
  abort or rollback
  release resources