Deadlock Detection Algorithm

* Allow systems to enter the deadlock state

Single instance of a resource type - Use a wait-for graph

Multiple instance of a resource type - Variant of the banker's algorithm

* Recovery scheme

1 Wait-for graph

a) resource allocation graph

b) wait-for graph

위 그림처름 Pi가 Pj가 끝나기를 기다리고 있을 때! ->화살표로 표시한다

(b에서 모든 자원이 single instance이므로 cycle이 발생하여 데드락 발생가능성이 생긴다..는 걸 탐지함)

2 Variant of the banker's algorithm

- Available : 각 타입의 가능한 자원들을 길이 m의 벡터로 표현

- Allocation : n*m 행렬은 현재 각 프로세스에 할당된 자원의 수를 나타냄

- Request : n*m 행렬은 각 프로세스의 요청을 나타냄. Request[i][j]=k라면 Pi는 Rj에게서 k개의 instance를 추가로 요청중인 상태

- Algorithm

1) Work와 Finish 가 각각 길이 m, n인 벡터가 되도록 하고, Work=Available, 그리고 Allocation이 0이 아닐 때 Finish[i]=false로 초기화한다. (0이면 할당 가능한 것이 없어 할당이 안되므로 Finish[i]=true)

2) Finish[i]==False이고 Requesti <=Work 인 i를 찾는다. 그러한 i가 없으면 4번으로 ㄱㄱ

3) Work+=Allocation; Finish[i]=true; 2번으로 ㄱㄱ

4) 만약 몇몇 i에 대해 Finish[i]==false 이면 시스템은 데드락(교착) 상태에 빠진 것이다. 나아가 만약 모든 i에 대해 Finish[i]==false이면 프로세스 Pi는 deadlocked process이다!

예)

5 process, 3 resource types (A 7, B 2, C 6)

	Allocation			Request			Available			Work
	A	B	C	A	B	C	A	B	C	A	B	C
P0	0	1	0	0	0	0	0	0	0	0	1	0
P1	2	0	0	2	0	2				7	2	4
P2	3	0	3	0	0	0				3	1	3
P3	2	1	1	1	0	0				5	2	4
P4	0	0	2	0	0	2				7	2	6

위 알고리즘대로 실행하면 맨 처음 Work는 available 0,0,0으로 초기화된 상태. 

P0에서 시작! request<=work이므로 P0의 allo를 할당하고 work+=allo가 되어 0,1,0

내려가서 P1을 보니 안되네.. 한칸 더내려감. P2를 보니 가능하다! work+=allo가 되어 3,1,3

같은 방식으로 돌고돌고 하니 Sequence P0 P2 P3 P1 P4가 나오고 Finish[i]=true for all i이다!

예2)

P2가 type C의 additional instance를 요청할 때

일단 기본적으로 위 표와 같다. 단, P2의 Request가 0 0 1이 된 상태.

이 때에는 위에서 나온 것처럼 P0 이후의 Sequence가 나올 수 없으므로 deadlock이 P1 P2 P3 P4 모두에 존재한다는 것을 알 수 있다.

3 Recovery Scheme

- Process termination

* Abort all deadlocked processes

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