데드락 Detection
: Deadlcok 을 허용하지만 알고리즘으로 찾아내서 Recover
1. 한개의 R 에 1개의 Instance : wait for graph
: pi -> pj
: pj의 리소스를 사용하고자함
> 주기적 알고리즘이 사이클탐지 // n^2 (Task 개수)
그림1) 전에 배운
Resource-Allocation Graph
그림2) 지금배운
Corresponding wait-for graph
2. 한개의 R 에 Multi Instance :
Banker's Algorithm 과 유사
1. P0 할당 > Avail) 010
2. P2 할당 > " 313
> 나머지 다가능
>>
sequence<p0,p2,p3,p1,p4>
-> Finsish[i]=true
>>> safe
if) P2 가 Request Resource C : 1
1. P0할당 > Avail 010 // 전과동일
2. P2할당하지 못함!
> 기존과 달리 P2의 Allocation을 받지 못하므로
> Finish[i] = false
> P3,P1,P2,P4 : Deadlcok
>> 이렇게 Deadlock 을 찾아낼 수 있음
근데 이걸 언제/얼만큼/자주 알고리즘을 돌릴건지??
고려1) 얼마나 데드락이 자주 생기는가?
고려2) 몇개의 P 를 Rolled back(원상복구) 시킬것인가?
>
이걸 상관없이 임의로 알고리즘을 돌리면..
많은 resource graph 가 생기고
> 어디서 Deadlock이 발생되었는지 파악하기 어려워짐..
발견한 데드락을 회복하려면?
1. 프로세스 종료
2. Resource Preemption
1-1) 모든 데드락 process 종료
1-2) 하나씩 종료 시켜봄
> 어떤순서? : 우선순위, 리소스를 얼마나 쓰는지 등등 고려..
2) 한명씩 종료 당해야함.. > victim(피해자)
a) Victim 선택 : 위의 순서를 고려하여 시간이 젤 적게드는순
b) Rollback : 시스템이 safe state 였던 상태로 가서 -> victim을 재실행 시켜봄
단점) Starvation : 어떤 process가 계속 victim 당하면.. > starve 발생
>> 여기까지가 중간범위