대기 그래프 순환 탐지와 데드락 복구 선택지

대기 관계 수집

누가 어떤 자원을 보유하고 누구의 자원을 기다리는지 그래프나 행렬로 만든다.

wait relation

자원마다 인스턴스가 하나면 wait-for graph의 cycle이 deadlock을 의미한다.

cycle

여러 인스턴스는 Available, Allocation, Request 행렬로 완료 가능한 프로세스를 반복 제거한다.

행렬 기반 탐지

프로세스 종료, 자원 선점, 체크포인트 rollback 중 손실이 가장 작은 방법을 고른다.

recovery

탐지 주기

너무 자주 검사하면 비용이 크고 너무 늦으면 피해가 커진다. 자원 종류와 장애 허용 시간에 따라 주기를 정한다.

frequency

종료

가장 단순하지만 작업 손실과 사용자 영향이 크다. 우선순위, 수행 시간, 보유 자원 수를 기준으로 victim을 고른다.

victim selection

선점

자원을 강제로 빼앗을 수 있는 종류에서만 가능하다. 파일 잠금이나 장치 상태처럼 선점 불가능한 자원은 종료가 필요할 수 있다.

preemptable resource

그래프 정확도 대기 관계가 stale하면 잘못된 프로세스를 죽일 수 있다.

복구 기준 victim 선택 기준이 정책으로 문서화되어 있다.

기아 방지 같은 프로세스가 반복 victim이 되지 않도록 비용을 누적한다.

build wait-for graph
if cycle exists:
  choose victim -> terminate or preempt -> recheck