교착상태 회피 ( 은행가 알고리즘 Ex문제풀이 )
예제)
1. 현재 시스템의 상태가 다음과 같다.
|
|
Allocation |
Max |
Available |
|||||||||
|
|
A |
B |
C |
|
A |
B |
C |
|
A |
B |
C |
|
|
P1 |
1 |
1 |
1 |
|
7 |
5 |
4 |
|
1 |
2 |
3 |
|
|
P2 |
2 |
1 |
0 |
|
4 |
1 |
2 |
|
|
|||
|
P3 |
3 |
0 |
2 |
|
7 |
1 |
6 |
|
||||
|
P4 |
2 |
1 |
0 |
|
2 |
1 |
3 |
|
||||
|
P5 |
0 |
0 |
1 |
|
5 |
3 |
2 |
|
||||
Q1 : Need 행렬의 내용은 무엇인가 ??
è Solution : Need(매트릭스) = 최대요구량(Max) – 할당(allocation)
è 할당 ,최대 요구량 , 잔여량이 주어진다
è 표로 나타내면 Need는 다음과 같다
|
Need |
|||
|
A |
B |
C |
|
|
7-1=(6) |
5-1=(4) |
4-1=(3) |
|
|
4-2=(2) |
1-1=(0) |
2-0=(2) |
|
|
7-3=(4) |
1-0=(1) |
6-2=(4) |
|
|
2-2=(0) |
1-1=(0) |
3-0=(3) |
|
|
5-0=(5) |
3-0=(3) |
2-1=(1) |
|
Q2 : 시스템은 현재 안전한 상태인가 ??
1. 안전한 상태인지 확인해야 한다 ( Need 값을 구한다 )
2. Work = 잔여량으로 두고 , Work값을 구한다
ㄱ. Work보다 작은 Need가 있다면 그 라인이 선점된다.
ㄴ. ( P4 ) à true로 바뀐다
ㄷ. 다시 반납을 해야 하니까 ( 2 , 1 , 0 )을 ( 1,2,3 ) 에 더해준다 à result : 3,3,3
ㄹ. 그 다음은 P2실행 하고 False 에서 True로 바뀐다 그리고 나서 p2의 자원을 반환해준다
ㅁ. (3,3,3)에 (2,1,0)을 더해준다 ( 5,4,3) 으로 바뀐다
ㅂ. 그 다음은 P5실행 하고 True로 바꾼다 그리고 나서 p5의 자원을 반환해준다
ㅅ. (5,4,3,)에 (0,0,1)을 더해준다 ( 5,4,4) 으로 바뀐다
ㅇ. 그 다음은 p3실행하고 True로 바꾼다 그리고 나서 p3의 자원을 반환해준다
ㅈ. (5,4,4)에 (3,0,2)을 더해준다 ( 8,4,6)으로 바뀐다
ㅊ. 그 다음은 p1실행하고 true 바꾼다 그리고 나서 p1의 자원을 반환해준다
ㅋ. (8,4,6) 에 (1,1,1)을 더해준다 ( 9,5,7)으로 바뀐다 : A ( 9 ) , B ( 5 ) , C ( 7 )
ㅌ. Work 결과값
|
Work |
|
초기 잔여량 = Work초기값을 설정 ( 1 , 2 , 3 ) 1. (1, 2, 3) +(2, 1, 0)à ( 3, 3, 3) 2. (3, 3, 3) +(2, 1, 0)à (5, 4, 3) 3. (5, 4, 3) +(0, 0, 1)à (5, 4, 4) 4. (5, 4, 4) +(3, 0, 2)à (8, 4, 6) 5. (8, 4, 6) +(1, 1, 1)à (9, 5, 7) 6. 결과값 : ( 9, 5, 7) |
è 그러므로 프로세스의 실행 순서가 나오게 된다 ( p4 , p2, p5, p3, p1 )
è 항상 그런 것은 아니지만 p1부터 실행한다. ( 조건이 없을 경우에 )
è 순서가 2개 존재할 수 있다.
Safe sequence = 프로세스 순서 ( 안전한 수행 순서 )
구할수 있으면 안전하다 , 구할 수 없으면 불안전하다
Q3 : P1에서 추가 할당량을 ( 1,0,2)을 요청했을 경우에 안전한가??
Solution : Safe sequence를 구할 수 없기 때문에 요청을 받아 줄 수가 없다.
계산 :
1. P0
2. P2
3. P1
4. P3
5. P4