교착상태를 회피하는방법

교착상태는 예방(prevention)하는 방법과 회피(avoidance)하는 방법이 있다.

예방은 교착상태가 발생할 수 있는 4가지 조건을 없애는 방법이다.

4가지 조건이란..

1. Mutex Exclusion : 각 리소스는 한번에 한 프로세스에게만 할당될 수 있거나 사용이 가능하다.

2. Hold and Wait : 프로세스는 현재 필요한 자원을 붙잡고, 필요한 새로운 자원을 요청할 수 있다.

3. No Preemption : 이미 할당받은 자원은 다른 프로세스에의해 강제적으로 빼앗기지 않는다.

4. Circular Wait : 이 상황은 원형의 모양으로 서로 맞물려 있다.

이 4가지 조건을 예방하는 방법은 아래와 같다.

Mutual exclusion

모든 자원을 한 프로세스에게 독점적으로 할당하지 않는다. 그러나 예를 들면 프린터같이 동시에 여러 프로세스들에게 할당할 수 없는 자원도 있으므로 이 조건은 충족될 수 없다.

Hold and wait

실행전에 프로세스는 모든 자원을 요청한다. 그러나 자원 사용에 비효율적이다. 예를 들면, tape를 읽어서 처리한 결과를 다시 tape에 써야한다고 할 때, 이 프로세스는 읽기위한 자원과 쓰기위한 자원을 실행전에 미리 요청을 한다. 읽는 동작이 한시간정도 걸린다고 할 때, 쓰기위한 자원은 이 읽기 동작이 끝날 동안 비효율적으로 기다리고 있어야 한다.

No preemption

필요할 때 자원을 강제로 빼앗는다. 이미 다른 프로세스에서 사용중인 자원을 강제로 빼앗는 방법은 좋은 방법이 아니다.

Circular wait

모든 자원에 전역적인 번호를 지정하고 자신이 이미 갖고 있는 자원의 숫자보다 낮은 번호를 가진 자원만 요청을 할 수 있는 규칙을 정하는 것이다. 원형으로 앉았을 경우 A옆에는 1, 2번 젓가락, B옆에는 2, 3, C옆에는 3, 4, D옆에는 4, 1이 있을 것이다. 이때 A는 1, B는 2, C는 3, D는 4를 각각 잡고 있을 경우 D는 1을 어차피 1을 요청할 수 없으므로 4를 놓아야 한다. 그러면 A나 C가 먼저 사용을 하고 놓게 되는 것이다. 그러나 이 방법의 단점은 모든 자원을 사용 순서대로 번호를 매기기 힘들다는 것이다. 예를 들어, 프린터, CD Rom, 스캐너라는 자원이 있을 때 이 자원들을 어느 순서로 사용할지는 아무도 모른다. 각 순서대로 1, 2, 3으로 매겨 놓았을 경우, 프로세스가 스캐너를 사용한 다음에는 프린터나 CD Rom을 사용할 수 없다.

4가지 예방하는 방법이 있지만 각 조건들은 모두 만족되기 힘들다. 이제 회피하는 방법을 알아보자.

전체     필요한 돈     이미 대출받은 돈     추가로 필요한 돈(need)

A        9천만원      2천만원                    7천만원

B        4천만원     천만원                        3천만원

C        3천만원     2천만원                       천만원

D        7천만원     3천만원                       4천만원

은행에 7천+3천+1천+4천=1억5천만원이 있으면 4명에게 동시에 빌려주면 좋겠지만 "작은 마을"의 은행은 빌려줄 수 있는 돈이 천만원밖에 없었다. 그래서 이 은행원은 방법을 생각했다. 

"천만원을 C에게 먼저 빌려주면 다 쓰고 이전에 빌려갔던 돈까지 3천만원을 갚겠구나! 그러면 3천만원을 빌려줄 수 있으니까 B에게 빌려주고, 그러면 B는 4천만원을 갚을 것이다. 이 4천만원을 D에게 빌려주고 7천만원을 받으면 A에게 빌려준 후에 모든 돈을 회수할 수 있겠구나!"

이 이론을 바탕으로 만들어진 알고리즘이다. (이 예는 단일 자원에 대한 것이다.)

여기서 한가지 용어가 나오는데 "Safe state"라는 것이다. 위 예에서 은행에 천만원이 있었기 때문에 저 "교착상태"를 풀 수 있었다. 만약에 은행에 천만원보다 작은 돈이 있었거나, 4명이 요구하는 돈이 천만원보다 더 컸으면 계속 교착상태에 빠져있어야 했을 것이다.

여기서 대출을 받은 순서 C -> B -> D -> A가 "안전 순서"이다. 이런 안전한 순서가 있는 상태가 "안전상태(Safe State)"이다.