▶ 교착상태 회피(Deadlock Avoidance) - 은행원 알고리즘 (banker's algorithm)
- Multiple instances
- Each process must a priori claim maximum use
- When a process requests a resource it may have to wait
- When a process gets all its resources it must return them in a finite amount of time
- Data Structures for the Banker’s Algorithm (n: 프로세서의 수, m : 자원의 종류수)
- Available : 사용가능한 각 자원의 수 , Available[j] = k : 자원종류 Rj중 k개 사용가능
- Max : 각 프로세스의 최대 요구 ( n x m 행렬 ), Max[i,j] = k : Pi는 자원종류 Rj중 최대 k개 요청- Allocation : 각 프로세스에 할당된 자원의 수 ( n x m 행렬 ), Allocation[i,j] = k : Pi는 현재 자원종류 Rj를 k개 할당 받고 있음Note : X[i] <= Y[i] for all i=1,2,..n 이면 X<=Y- Need : 각 프로세스의 남은 요구 ( n x m 행렬 ), Need[i,j] = Max[i,j] - Allocation[i,j] = k : Pi는 자원종류 Rj를 k개 더 요구함
+ Safety Algorithm
1. Let Work and Finish be vectors of length m and n, respectively. Initialize : Work := Available
Finish [i] := false for i = 1,2, …, n
2. Find an i such that both : (a) Finish [i] = false
(b) Needi ≤ Work
If no such i exists, go to step 4
3. Work := Work + Allocation(i)
Finish[i] := true
go to step 2
4. If Finish [i] = true for all i, then the system is in a safe state.※ Exercise ( A, B, C, D 는 시스템에 존재하는 자원을, P0, P1, P2, P3, P4는 프로세스를 표시한다.)
Allocation
Max
Available
A
B
C
D
A
B
C
D
A
B
C
D
P0
0
0
1
2
0
0
1
2
1
5
2
0
P1
1
0
0
0
1
7
5
0
P2
1
3
5
4
2
3
5
6
P3
0
6
3
2
0
6
5
2
P4
0
0
1
4
0
6
5
6
1) Need 행렬의 내용 ( 각 프로세스의 자원요구 필요량)
ㅁNeed 행렬의 값은 ( Max - Allocation)으로부터 얻어진다. (아래의 표 참고)
2) 안전 상태(safe state)의 정의와 위 시스템의 안전 상태 여부
ㅁ 안전 상태(safe state)
- 일련의 순서대로 자원할당해도 교착상태 없는 상태
- safe sequence가 있는 상태- 시스템 상태가 'safe' 하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을 (설사 최대치를 요구하더라도)deadlock을 야기시키지 않고 차례로 모두 할당해 줄 수 있다는 것을 뜻한다.즉, 시스템이 safe sequence를 찾을 수 있다며 시스템은 safe 하다고 말한다.
ㅁ 시스템이 안전 상태에 있는 지 알아보기 위해 safety algorithm 을 적용해본다.1) 초기상태 (n = 5, m = 4)Work := Available = (1, 5, 2, 0)
Finish [i] := false for i = 1,2, …,5
Allocation
Max
Need
Available
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
P0
0
0
1
2
0
0
1
2
0
0
0
0
1
5
2
0
P1
1
0
0
0
1
7
5
0
0
7
5
0
P2
1
3
5
4
2
3
5
6
1
0
0
2
P3
0
6
3
2
0
6
5
2
0
0
2
0
P4
0
0
1
4
0
6
5
6
0
6
4
2
2) - Finish[i] = false and Needi ≤ Work, If no such i exists, go to step 4i = 1 ; Finish[1] = false & Need1(0, 0, 0, 0) ≤ Work (1, 5, 2, 0) → 성립- Work := Work + Allocation(i), Finish[i] := true, go to step 2Work := Work (1, 5, 2, 0) + Allocation1(0, 0, 1, 2) = (1, 5, 3, 2)Finish[1] := true, go to step 2
Allocation
Max
Need
Available
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
P0
0
0
0
0
0
0
0
0
0
0
0
0
1
5
3
2
P1
1
0
0
0
1
7
5
0
0
7
5
0
P2
1
3
5
4
2
3
5
6
1
0
0
2
P3
0
6
3
2
0
6
5
2
0
0
2
0
P4
0
0
1
4
0
6
5
6
0
6
4
2
3) 이렇게 적용해보면, 결과는 <P0, P2, P1, P3, P4>순서로 진행되어 safety requirement가 된다.
Allocation
Max
Need
Available
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
P0
0
0
0
0
0
0
0
0
0
0
0
0
P1
0
0
0
0
0
0
0
0
0
0
0
0
P2
0
0
0
0
0
0
0
0
0
0
0
0
P3
0
0
0
0
0
0
0
0
0
0
0
0
P4
0
0
0
0
0
0
0
0
0
0
0
0
3
14
12
12
3) 프로세스 P1이 (0, 4, 2, 0)의 자원 요청시, 그 요청의 수용여부
ㅁ Request1 ≤ Available ; Request1(0, 4, 2, 0) ≤ Available(1, 5, 2, 0) → 성립
Allocation
Max
Need
Available
A
B
C
D
A
B
C
D
A
B
C
D
A
B
C
D
P0
0
0
1
2
0
0
1
2
0
0
0
0
1
1
0
0
P1
1
4
2
0
1
7
5
0
0
3
3
0
P2
1
3
5
4
2
3
5
6
1
0
0
2
P3
0
6
3
2
0
6
5
2
0
0
2
0
P4
0
0
1
4
0
6
5
6
0
6
4
2
ㅁ 요청시 P1의 Allocation := P1의 Allocation + Request1(0, 4, 2, 0) = (1, 4, 2, 0)
ㅁ 요청시 P1의 Need := P1의 Need - 요청시 P1의 Allocation = (0, 3, 3, 0)
ㅁ 요청시 Available := Available - Request1(0, 4, 2, 0) = (1, 1, 0, 0)
ㅁ safety algorithm 을 적용해보면, <P0, P2, P1, P3, P4>순서로 진행되어 safety requirement가 된다.
P1의 자원 요청은 그 즉시 수용하지는 못하나, 중간 정도에 수용요청을 들어줄 수 있다.
4) 은행원 알고리즘과 교착상태 방지(prevention)
ㅁ 은행원 알고리즘은 교착상태 회피(avoidance) 알고리즘이다. 교착상태를 회피하는 것은 사용자(프로세스)가 자원이 어떻게 요청될 지에 대한 추가 정보를 제공하도록 요청하는 것이다. 은행원 알고리즘은 프로세스가 시작할 때 프로세스가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 신고하여야 한다. 또한, 교착상태 회피 알고리즘은 시스템에 순환 대기 상황이 발생하지 않도록 자원 할당 상태(가용 자원의 수, 할당된 자원의 수, 프로세스들의 최대 요구 수)를 검사한다. 이에 반해 교착상태 방지(prevention)는 요청방법을 제약하여 교착상태를 예방하는 것인데, 교착상태가 발생할 때 필요한 네 가지의 필요 조건 중 최소한 하나가 성립하지 않도록 보장함으로써 교착상태의 발생을 예방한다.
하지만, 교착 상태 방지(prevention)는 지나치게 제한적이며, 교착상태 회피(avoidance)도 흔하게 유효하지 않는 정보를 요구할 수 있다.
5) 은행원 알고리즘을 분산시스템에서 사용하는 방법 및 문제점
ㅁ 교착 상태 방지와 회피 알고리즘들을 약간 수정하면 분산 시스템에서도 사용될 수 있다. 예를 들면, 시스템 내의 스로세스 중 하나를 은행원 알고리즘을 수행하는 데 필요한 정보를 유지하는 프로세스(은행원)로 지정함으로써 은행원 알고리즘을 분산 시스템에 사용할 수 있다.
다만, 은행원 알고리즘은 쉽게 구현될 수 있지만, 추가 비용이 너무 크다. 은행원에게 오고 가는 메시지가 너무 많기 때문에 은행원이 병목(bottleneck)이 될 수 있다.
'Algorithm' 카테고리의 다른 글
| deadlock 4가지 (0) | 2008.08.01 |
|---|---|
| B-, B+ Tree (0) | 2008.08.01 |
| CPU scheduling (0) | 2008.08.01 |
| 스케쥴링 기법 (0) | 2008.08.01 |
| deadlock (0) | 2008.08.01 |
