1
탐지 알고리즘: 자원 유형별 구분
탐지 알고리즘은 현재 시점에서 데드락이 존재하는가?를 판정합니다.
탐지(Detection)데드락 탐지와 복구
예방과 회피를 완벽하게 적용하기 어렵다면, 데드락이 발생하도록 두었다가 탐지(Detection)한 후 복구(Recovery)하는 전략을 쓸 수 있습니다. 예방은 제약이 많고, 회피는 미래 예측이 필요합니다.
대기 그래프, 자원 할당 상태, 복구 비용을 기준으로 데드락 탐지와 복구 시점을 정합니다.
1. 사이클 탐지wait-for graph 또는 상태 행렬에서 더 진행할 수 없는 집합을 찾는다.
2. 희생자 선택우선순위·보유 자원·잃는 작업량을 비용으로 비교한다.
3. 사이클 절단종료·rollback·자원 선점 중 가능한 방법으로 한 간선을 끊는다.
4. 해제 후 재검사풀린 자원을 대기자에게 넘기고 남은 사이클을 다시 검사한다.
2
데드락 복구
데드락을 탐지했으면 복구해야 합니다.
복구(Recovery)
3
타조 알고리즘
타조 알고리즘(Ostrich Algorithm)은 "데드락이 발생하면 무시한다"는 전략입니다.
탐지 후 복구