이론 5) 교착 상태 2

 

 

 

 

 

 

 

 

 

1. 은행가 알고리즘 (Banker's Algorithm)

: 교착상태 회피 알고리즘 + 자원의 종류가 여러 개 일 때

 

 

 

1) 안전성 알고리즘

: 안정상태인지 불안정상태인지 검사

 

ex) 3개 종류의 자원(A, B, C)

 

 

 

 

 

현재사용량 : Allocation
시작잔여량 : Available

p1, p3 종료가능, 아무거나 선택
p1 종료 후 잔여 : 3 3 2 + 2 0 0 = 5 3 2
p3 종료 후 잔여 : 5 3 2 + 2 1 1 = 7 4 3

안정 순열 < p1, p3, p4, p0, p1 > 등 

 

 

 

 

 

2) 자원 요청 알고리즘

 

① Request1 <= Available ((1, 0, 2) <= (3, 3, 2)) 확인

② 새로운 시스템 상태가 안정한지 판별하기 위해 안정성 알고리즘 실행

③ <P1, P3, P4, P2, P0> 순서의 안정 순열 존재

④ 프로세스 P1의 요청을 허락

 

ex)

이 상태에서 Request1 = (1, 0, 2)이면? (P1이 A자원 +1과 C자원 +2를 더 요구한다면?)

 

 

 

 

주의 !

Need 에서 요청한만큼 빼줘야함

 

 

 

 

 

 

 

 

3) 은행원 알고리즘의 단점

 

- 할당할 수 있는 자원의 일정량을 요구한다.

- 사용자 프로세스 수가 일정해야 한다.

- 사용자가 최대 필요량을 미리 알려주도록 요구된다.

- 교착상태 회피 알고리즘을 사용하면 계속해서 상태를 파악하고 그에 따라 대응해야 하기 때문에 시스템 과부하가 증가한다.

- 항상 불안정 상태를 방지해야 하므로 자원 이용도가 낮다.

 

 

 

 

 

 

 

 

 

 

2. 교착 상태 탐지

 

: 교착 상태가 발생하도록 허용한다.

: 교착 상태가 발생했는지 탐지 알고리즘

: 교착 상태로부터 회복하는 알고리즘 제공한다.

 

-> 은행가 알고리즘에서 조금 변형한 것이다.

 

 

1) 은행가 알고리즘과의 차이

: 은행가 알고리즘에서는 Request를 받아줄지 말지를 고민하는 상태였다면

교착 상태 탐지 알고리즘에서는 이미 Request 가 요구를 하고있다. 모든 프로세스가 대기하는 상태이므로 Available은 남아있지 않다. 

 

 

<P0, P2, P3, P1, P4> 로 안정 순열이 존재한다.

 

 

만약 P2가 C자원 하나를 더 요구한다면?

 

P0 다음에 할당할 수 있는 프로세스가 없으므로 교착 상태에 놓이게 된다.

 

 

 

 

2) 교착 상태 탐지 알고리즘의 특징

- 교착 상태가 자주 발생하면 탐지 알고리즘도 자주 호출된다.

- 요청할 때마다 연산 시간 부담이 크다.

- 경제적인 방법은 호출 빈도를 줄이는 것으로, 한 시간마다 또는 CPU 이용률이 40% 이하로 저하될 때마다 호출하는 방법이 있다.

( CPU 이용률이 낮다는 것은 교착 상태로 인해 문제가 생겼을 가능성이 높기 때문이다. )

 

 

 

3) 교착 상태 회복

- 모든 교착 상태 프로세스들을 중지시키거나, 

교착 상태 사이클이 제거될 때까지 하나씩 프로세스를 중지시키는 방법이 있다.

 

 

 

 

 

 

3. 교착 상태를 다루는 결합된 방법

: 3가지 방법(예방, 회피, 탐지)를 결합하여 시스템 자원 종류에 따라 최적의 방법을 고안한다.

 

 

 

4. 정보처리기사 문제 풀어보기

 

1) 은행가 알고리즘은 교착 상태 회피 알고리즘이다

2) 교착상태 4가지 조건 중 어느 하나를 제거하는 방법은 교착 상태 예방 알고리즘이다.

3) 교착 상태 회피 알고리즘은 

사전에 시스템을 제어하여 교착 상태를 회피하는 알고리즘이다.

대표적인 예로 은행가 알고리즘이 있다.

교착상태가 발생할 확률을 완전히 배제한다.