15. Deadlocks 2

운영체제

홍비 2022. 3. 12. 15:07

이화여자대학교 반효경 교수님의 운영체제 강의 17강을 듣고 정리한 내용이다.

✏️ Deadlock Detection and Recovery

Resource type에 따라

✓ Single instance인 경우, 자원 할당 그래프에서 사이클이 곧 deadlock을 의미

✓ Multiple instance인 경우, Banker's algorithm과 유사한 방법 활용

✓ Resource type당 single instance인 경우

✓ Wait-for graph

• 자원할당 그래프의 변형

• 프로세스만으로 node 구성

• $P_j$가 가지고 있는 자원을 $P_k$가 기다리는 경우 $P_k → P_j$

✓ Algorithm

• Wait-for graph에 사이클이 존재하는지를 주기적으로 조사

• $O(n^2)$

✓ Process termination

• Abort all deadlocked processes

• Abort one process at a time until the deadlock cycle is eliminated

✓ Resource Preemption

• 비용을 최소화할 victim 선정

• 안정상태로 rollback하여 프로세스를 재시작

• Starvation 문제 - 동일한 프로세스가 계속해서 victim으로 선정되는 경우, cost factor에 rollback 횟수도 같이 고려

• 교착상태가 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음

• Deadlock이 매우 드물게 발생하므로 교착상태에 대한 조치 자체가 더 큰 오버헤드일 수 있음

• 만약, 시스템에 교착상태가 발생한 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처

• UNIX, Windows 등 대부분의 범용 OS가 채택