DeadLock Avoidance Algorithms

Single instance of a resource type - Use resource-allocation graph

Multiple instances of a resource type - Use banker's algorithm

1 Resource-Allocation Graph Scheme

- Claim edge Pi->Rj : 프로세스 Pi가 resource Rj에게 자원을 요청하겠다, 고 점선으로 표현 (선언한 것을 나타냄)

- 프로세스가 자원을 요청하면 Claim edge는 Request edge로 변신

- 자원이 프로세스에게 할당되면 Request edge는 Assignment edge로 변신

- 자원이 프로세스로부터 방출되면 Assignment edge는 Claim edge로 변신

- 자원은 시스템에서 우선적으로 선언되어야 함

- 요청은 실행될 수 있다, 단, request edge Pi->Rj 에서 assignment edge Pi<-Rj가 resource allocation graph에서 사이클을 형성하지 않을 때!

 ->

 위 그림을 보면 P2가 R2에게 요청하고 있다. R2가 자원을 할당해도 사이클이 발생하지 않기 때문에 옆 그림으로 가면 할당이 가능하다. 하지만 이 상태에서 만약 P1이 R2에게 요청중인 것을 그대로 실행하면 사이클이 발생, 데드락이 발생할 수 있는 상태가 되므로 요청이 실행되지 않는다.

2 Banker's Algorithm

- 기본개념:

은행에 있는 돈이 1000이라고 해보자 만약 A가 500을 대출한다면 은행에 돈이 충분하므로 대출해줄 수 있다

그런데 B가 600을 더 대출받길 원한다면..? 은행 한도를 초과했으므로 A가 빌려간 돈을 갚아야 한다 = 빌려간 자원을 반납해야 한다

- Data structure

* n : number of processes

* m : number of resource types

* Available : A vector of length m. Available[k]=k이면 resource type Rj에 가능한 instance 개수는 k개

* Max : An n*m matrix. 만약 Max[i,j]=k 이면 Pi는 resource type Rj에 최대 k개의 instance 요청

* Allocation : n*m matrix. 만약 Allocation[i,j]=k이면 프로세스 Pi는 현재 resource type Rj에 k개의 instance 할당된 상태

* Need : n*m matrix. Need[i,j]=k이면 Pi는 작업을 완료하기 위해 Rj에서 k개의 instance가 더 필요함

- Safety Algorithm

1) Work : 길이 m의 vector  ;  Finish : 길이 n의 vector

    Work=Available로 초기화, Finish[i]=false로 초기화 (i=0,1,2...n-1)

*** Work는 다 쓰고 반납한 자원을 의미한다고 생각하면 된다

2) Finish[i]==false 이고 Needi<=Work인 i를 찾아라. 없으면 4번으로 ㄱㄱ

*** 다 쓰고 반납한, 존재하는 자원들이 각 프로세스가 원하는 자원 양만큼 있어야 하므로 비교하는 것

3) Work+=Allocationi

    Finish[i]=true

    2번으로 ㄱㄱ

4) 모든 i에 대해 Finish[i]==true이면 시스템은 safe state

예)

5 process = P0, P1 ... P4

3 resourcee types = A(10 instance) B(5 instance) C(7 instance)

	Allocation			Max			Available
	A	B	C	A	B	C	A	B	C
P0	0	1	0	7	5	3	3	3	2
P1	2	0	0	3	2	2
P2	3	0	2	9	0	2
P3	2	1	1	2	2	2
P4	0	0	2	4	3	3

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

위 표에서 하나씩 보면! 

우선 Need는 앞으로 필요한 것, 이므로 각 프로세스가 필요한 최대 양 Max에서 현재 할당받은 양 Allocation을 뺀 것이다. 

그럼 이제 Work를 본다! 기본적으로 위에 있는 알고리즘을 따른다.

P0부터 시작하여 Work=available=3,3,2 로 초기화, Finish[0]=false이다.

이제 Available, 즉 할당 가능한 것이 Need보다 클 수 있는 Need를 찾는다. P0에서 아래로 내려가다 보면.. P1임을 알 수 있다 그럼 P1의 work에는 +=P1의 allocation! 즉 5,3,2가 저장되고 Finish[1]=true가 된다

이제 다시 밑으로 내려와서 같은 방식으로 P2의 available과 현재 work를 비교한다. P2의 need가 더 크므로 다시 밑으로 내려와 P3과 비교한다. 가능하네...... 같은 방식으로 P4까지 하고 나면 다시 처음부터 Finish[i]=false인 P0과 기타등등을 찾아서 한바퀴 더 돈다 모든 Finish가 true 될 때까지. 순서대로 다 하고나면 Safe sequence = P1 P3 P4 P0 P2가 되는 것을 알 수 있다!

- Resource-Request Algorithm for Pi

추가)Requesti : Request vector for Pi 만약Requesti[j]=k이면 Pi는 Rj에서 k개의 instance를 원한다는 뜻

1) if Requesti<=Needi 이면 2번으로 간다. 아니면 시스템에 있는 개수보다 더 많이 요청했으므로 에러를 발생시킨다

2) Requesti<=Availablei 이면 3번으로 간다. 아니면 자원들이 available하지 않은 상태이므로 기다려야 한다

3) 요청대로 할당하는 척 한다

Availablei -=Requesti          가능한 영역에서 request를 뺀다

Allocationi +=Requesti       request만큼 할당함

Needi -=Requesti              request만큼 할당되었으므로 앞으로 필요한 양에서 뺀다

if safe->resources are allocated to Pi

if unsafe->Pi must wait and the old resource -allocation state is restored

예)

표는 위의 초록색 표와 같다!

Pi request 1,0,2

1) Check Requesti  <= Needi 

2) Check Requesti  <= Availablei 

두 가지 체크해보면 P1 기준으로 1,0,2 <= 1,2,2이며 1,0,2<=3,3,2가 성립된다

따라서 P1의 Allocation 2,0,0은 +=1,0,2 하여 3,0,2로 바뀐다. Available은 3,3,2-1,0,2 하여 2,3,0이 된다

safety algorithm을 적용시켜보면 위의 safe sequence와 같게 나와 safe state가 됨을 알 수 있다. 따라서 요청은 받아들여진다