[Chapter 7. 교착상태] 교착상태 처리 방법 - 회피, Banker's 알고리즘과 Safety 알고리즘

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

 

교착 상태 처리 방법

1. 교착상태가 되지 않도록 사전에 조치하는 방법 (예방, 회피)

2. 교착상태 방치 후 탐지하여 복구하는 방법 (탐지, 복구)

 

 

앞서 설명한 교착상태 예방 대책은

교착상태 발생 조건이 성립 것 자체를 부정하는 방법을 미리 마련하여 각 프로세스가 이를 지키도록 강제하는 방법이었다.

 

그 대책들은 자원의 활용도를 낮게 하고 시스템의 처리량을 감소시키거나, 기아 상태도 발생 가능한 등 여러 부수적인 문제들이 있다.

 

교착상태 회피(avoidance)

---

교착상태 회피는 프로세스 일생 동안 자원 요청에 대한 더 많은 정보를 미리 제공할 것을 요구하는 것이다.

 

현재 사용 가능한 자원, 현재 각 프로세스에 할당된 자원, 각 프로세스가 앞으로 요청하거나 방출할 자원 정보들을 활용하여

프로세스의 현재 요청이 만족될 수 있는지, 그리고 미래의 가능한 교착 상태를 회피하기 위해 프로세스가 대기해야 하는지의 여부를 결정할 수 있다.

 

교착상태 회피 알고리즘은 시스템에 순환(환형) 대기 상황이 발생하지 않도록 자원 할당 상태를 검사한다.

자원 할당 상태는 가용 자원의 수, 할당 자원의 수, 그리고 프로세스들의 최대 요구 수에 의해 정의된다.

 

안정 상태 (Safe State)

'시스템의 상태가 안정하다/안전하다'는 것은

시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을 (최대 요구수를 요구하더라도)

교착 상태를 야기하지 않고 차례로 모두 할당해줄 수 있는 상태를 말한다.

 

즉, n개의 프로세스들에 대해 자원을 할당해주는 n!개의 순열 중

안정 순열이 단 하나라도 존재하면 안정(safe) 상태이며, 그렇지 않다면 불안정(unsafe) 상태이다.

 

시스템이 불안전 상태에 있다고 해서 반드시 교착상태로 간다는 것은 아니다. (교착상태가 발생할 가능성이 존재한다는 것)

 

 

이때 안정 순열(safe sequence)이라는 것은

프로세스의 순열 <P1, P2, ... , Pn>의 각 Pi에 대해서 그 Pi가 요청하는 자원을

현재 시스템에 남아있는 자원과 앞에서 수행을 마칠 모든 프로세스 Pj(j < i)들이 반납하는 자원들로 만족시켜줄 수 있음을 뜻한다.

 

풀어서 말하면,

① 앞으로 Pi가 요청할 수 있는 최대의 자원량(= 최대 요구량 - 현재 보유량)이

② 현재 시스템에 남아있는 자원의 개수와

③ j < i인 모든 프로세스 Pj들이 보유하고 있는 자원들로 충족되면

이 프로세스 순열은 안정순열이다. (자원의 개수가 ② + ③ >= ①을 충족하면 안정순열)

 

 

(안정 상태, 불안정 상태 예시)

12개의 테이프 장치와 3개의 프로세스가 있다.

시간 T0의 자원 할당 상황은 아래와 같으며, 현재 시스템은 안정 상태에 있다. (12 >= 5+2+2)

 

	최대 소요량	현재 사용량	남은 자원량
P0	10	5	3
P1	4	2
P2	9	2

 

프로세스 순열 <P1, P0, P2>는 안정순열이다.

T0 이후, 각 프로세스들이 최대 소요량 만큼의 자원을 요구한다고 하자.

 

	T0의 할당 상황 및 이후 안정 상태 예상
P0	5 → 10 → 0
P1	2 → 4 → 0
P2	2 → 9 → 0

 

P1 → P0 → P2 순으로 프로세스들이 실행되었을 때 남은 테이프 수들을 확인하는 것으로 이것이 안정 순열인지를 확인할 수 있다.

 

1. P1 수행 시 남은 테이프 수 : 3개 → 1개 → 5개

2. 그 다음, P2 수행 시 남은 테이프 수 : 5개 → 0개 → 10개

3. 마지막 P3 수행 시 남은 테이프 수 : 10개 → 3개 → 12개

 

이 순서대로라면 프로세들의 요구하는 만큼 자원들을 전부 바로바로 할당해줄 수 있기 때문에

프로세스 순열 <P1, P0, P2>는 안정 순열이라는 것이며, 시스템은 안정 상태에 있다.

 

 

하지만 만약 시간 T1에서 P2가 한 개의 테이프를 추가 요청하여 남은 테이프가 2개가 되었다면 시스템은 불안정 상태가 된다.

 

	최대 소요량	T1 이후 상황 전개 예상	남은 자원량
P0	10	5	2
P1	4	2
P2	9	3

 

남은 테이프 2개로 종료시킬 수 있는 프로세스는 P1이 유일하기 때문에 먼저 P1을 수행시킬 수 밖에 없다.

P1 수행 후 남은 테이프 수 : 2 → 0 → 4

 

P1 수행 후 남은 테이프 수는 4개이다.

이것으로는 P0과 P2 누구나 먼저 실행되어 최대 소요량을 요구할 경우, 모두 요청을 완료시켜 줄 수 없다.

1. P0의 최대 소요량은 10개로, 앞으로 최대 5개를 요청할 수 있으나 남은 자원이 4개로 1개가 모자르다.

2. P2의 최대 소요량은 9개로, 앞으로 최대 6개를 요청할 수 있으나 남은 자원이 4개로 2개가 모자르다.

 

따라서 P0와 P2 사이에 교착 상태가 발생할 수 있기 때문에 시스템은 불안정 상태가 된다는 것이며,

시간 T1에 P2에게 테이프 하나를 더 할당하지 말아야 한다.

 

---

이처럼 교착상태 회피의 기본 방법은

자원 할당 시 시스템이 항상 안정 상태에 있도록 유지하는 것이다.

 

즉, 시스템이 안정 상태에서 안정상태로 옮겨갈 수 있을 때에만 자원을 할당해주는 것이다.

만약 안정 상태가 유지된다는 보장이 되지 않는다면 프로세스가 자원을 기다리도록 한다. 

 

이 방식에서는 유휴 자원이 있더라도 프로세스가 대기해야하는 상황이 발생하기 때문에

시스템의 이용도는 낮아질 수 밖에 없다.

 

Banker's 알고리즘

프로세스가 자원을 요청하면 시스템은 해당 요청 수락 시, 그 다음의 상태가 안정 상태로 유지될 것인가 여부를 미리 검토한다.

1. 만약 계속 안정 상태에 머무르게 된다면 그 요청을 수락

2. 그렇지 않다면 그 요청은 허락이 안 된 채 다른 프로세스가 끝나기까지 기다려야 한다.

 

프로세스가 시작할 때 프로세스가 가지고 있어야 할 자원의 최대 개수를 자원 종류마다 미리 알려야 한다.

 

 

이 알고리즘을 구현하려면 아래의 자료구조들이 필요하다.

n : 프로세스의 수 / m : 자원의 종류 수

 

1. Available (길이 m의 벡터)

각 자원별 사용 가능 개수

Available[j] = k : 자원 유형 Rj는 현재 k개 사용 가능

 

2. Max (n×m 행렬)

각 자원별 최대 요청 가능 개수

Max[i, j] = k : 프로세스 Pi가 최대 k개의 자원 유형 Rj를 요청할 수 있음

 

3. Allocation (n×m 행렬)

현재 프로세스가 각 자원별 할당받고 있는 자원의 개수

Allocation[i, j] = k : 현재 프로세스 Pi가 자원 유형 Rj를 k개 할당 받고 있음

 

4. Need (n×m 행렬)

각 자원별 유휴 자원의 개수

Need = Max - Allocation

 

5. Request

임의 시점에 프로세스의 자원 요청 개수

Request[i, j] = k : 프로세스 Pi가 자원 유형 Rj 중 k개 할당을 요청하고 있음

 

 

// 아래 첨자를 쓸 수 없어서 벡터.i로 표기함

1. If Request.i <= Need.i : Goto Step 2.
	Or Error(illegal request)

2. If Request[i] <= Available : Goto Step 3.
	Or Pi must WAIT(resources not available)

3. Calculate the result of allocation:
	Available := Available - Request.i;
    Allocation.i := Allocation.i + Request.i
    Need.i := Need.i - Request.i;
    

// Pi에게 자원을 할당한 것처럼 하고,
// 이후 Safety 알고리즘으로 안정 여부를 판단한다.
// 만약 안정하지 않다고 판명되면 값들을 원상복구하고 대기하게 된다!

 

Safety 알고리즘

안정 순열이 존재하는지 판별하는 알고리즘이다.

 

// Work와 Finish는 크기가 m과 n인 벡터
Work = Available;
Finish[i] = false;

for (j = 0; j < n; j++) {
    for (i = 0; i < n; i++) {
        // 앞으로 자원 부족이 생기지 않는지 체크, 발견된 순서가 곧 안정 순열이 된다.
        if (Finish[i] == false && Need.i <= Work) // 최대 요청 가능량 <= 유효 자원량
            break;
    }
    Work = Work + Allocation.i; // 프로세스 i 수행 완료 후 현재 갖고 있는 자원을 반납
    Finish[i] = true;
}

// 모든 i에 대하여 Finish[i] = true라면 이 시스템은 안정 상태에 있다!

 

(예시 1)

다섯 개의 프로세스 {P0, P1, ... , P4}와 자원 {A, B, C}를 가진 시스템이 있으며, 자원 유형 A는 10개, B는 5개, C는 7개가 있다.

시간 T0에서 시스템은 아래와 같은 상태에 있다.

 

	Allocation			Max			Work = Available
	A (총합 7)	B (총합 2)	C (총합 5)	A	B	C	A	B	C
P0	0	1	0	7	5	3	10-7 = 3	5-2 = 3	7-5  = 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

* Allocation은 가정치로, 이렇게 할당한다고 가정할 경우 안정 순열이 존재하는지를 알아보겠다는 뜻이다.

 

Need 행렬 값은 Max - Allocation으로 얻어진다.

 

	Need (Max - Allocation)
	A	B	C
P0	7	4	3
P1	1	2	2
P2	6	0	0
P3	0	1	1
P4	4	3	1

 

Need 행렬을 위에서부터 슥 훑어봤을 때 Need <= Work를 만족하는 첫 프로세스는 P1이다.

P1 실행 후 Work = Work + Allocation = (3+2, 3+0, 2+0) = (5, 3, 2)

 

그 다음, 자원 (5, 3, 2)로 Need <= Work를 만족하는 프로세스는 P3이다.

P3 실행 후 Work = Work + Allocation = (5+2, 3+1, 2+1) = (7, 5, 3)

 

...

 

이렇게 해서 프로세스 순열 <P1, P3, P4, P2, P0>는 안정 순열임이 확인되며,

그대로 자원을 할당해도 교착상태가 발생하지 않는 것이 확인되었기 때문에 그대로 진행해도 된다.

 

 

(예시 2)

예시 1에서, 만약 프로세스 P1이 자원 유형 A의 자원 1개와 자원 유형 C의 자원 2개를 요구했을 경우를 보자. (Request.i = (1, 0, 2))

 

Banker's 알고리즘에서 Request.i <= Available 즉, (1, 0, 2) <= (3, 3, 2)이기 때문에 새로운 상태에 도달할 것임을 가정할 수 있다.

안정 순열이 존재하는지 보자.

 

	Allocation			Max			Work = Available
	A (총합 8)	B (총합 2)	C (총합 7)	A	B	C	A	B	C
P0	0	1	0	7	5	3	10-8 = 2	5-2 = 3	7-7  = 0
P1	3	0	2	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 (Max - Allocation)
	A	B	C
P0	7	4	3
P1	0	2	0
P2	6	0	0
P3	0	1	1
P4	4	3	1

 

예시 1의 방법과 똑같이 수행해보면, 프로세스 순열 <P1, P3, P0, P2, P4>는 안정 순열임이 확인된다.

 

 

(예시 3)

만약 예시 2에 이어서 프로세스 P0도 자원 유형 B를 2개 요청했다면 어떻게 되는가? (Request.0 = (0, 2, 0))

 

Banker's 알고리즘에서 Request.0 <= Available 즉, (0, 2, 0) <= (2, 3, 0)이므로 새로운 상태에 도달할 것을 알 수 있다.

이 경우 안정 순열은 존재할까?

 

	Allocation			Max			Work = Available
	A (총합 8)	B (총합 4)	C (총합 7)	A	B	C	A	B	C
P0	0	3	0	7	5	3	10-8 = 2	5-4 = 1	7-7  = 0
P1	3	0	2	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 (Max - Allocation)
	A	B	C
P0	7	2	3
P1	0	2	0
P2	6	0	0
P3	0	1	1
P4	4	3	1

 

어떤 프로세스의 Need도 Need <= Work (2, 1, 0)을 만족하지 않는다.

 

안정 순열이 존재하지 않으므로 이 시스템은 안정 상태가 아니며,

따라서 Request.0 = (0, 2, 0)은 할당이 불가, P0은 바로 실행되지 못하며 자원을 대기해야 하는 것이다.

 

이때 Banker's 알고리즘에서 갱신된 값들은 원상복구되어야 한다.