나무 숲
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가 됨을 알 수 있다. 따라서 요청은 받아들여진다
'Career' 카테고리의 다른 글
Paging (0) | 2016.06.08 |
---|---|
Deadlock Detection Algorithm (0) | 2016.06.08 |
RISC vs CISC (0) | 2016.06.07 |
File System (0) | 2016.06.06 |
Demand Paging (0) | 2016.06.05 |