교착 상태 필요조건

자원 그래프를 그린다

프로세스와 자원을 노드로 두고 할당과 요청 간선을 분리하면 막힌 원인을 볼 수 있다.

조건 중 하나라도 깨지면 deadlock은 성립하지 않는다.

livelock은 계속 움직이지만 진전이 없고, starvation은 특정 작업이 오래 선택되지 않는 상태다.

Deadlock

영구 대기 각 작업이 다른 작업이 가진 자원을 기다려 모두 멈춘다.

외부 개입 없이는 풀리지 않는다.

Livelock

움직이지만 진전 없음 서로 양보하거나 상태를 바꾸지만 목표에 도달하지 못한다.

무작위 backoff가 도움될 수 있다.

Starvation

선택받지 못함 시스템은 진행하지만 특정 작업만 계속 밀린다.

aging과 공정성이 필요하다.

Resource graph

원인 시각화 요청 간선과 할당 간선을 따라 cycle을 찾는다.

단일 인스턴스에서 cycle은 강한 신호다.

네 조건 mutual exclusion, hold-and-wait, no preemption, circular wait가 모두 있는가.

구분 deadlock, livelock, starvation을 진행 가능성 기준으로 구분하는가.

그래프 대기 관계를 자원 그래프로 표현할 수 있는가.

deadlock possible only if:
ME && hold_wait && no_preemption && circular_wait