교착상태 해결방법

<예방 기법>

1. 자원의 배타적 사용 조건을 배제

모든 자원을 공유 가능 자원으로 하여 교착 상태의 발생을 차단하겠다는 의도이다. 불행하게도 시스템이 보유한 자원 중에는 배타적으로 사용할 수 밖에 없는 자원들도 존재 (ex. 프린터나 테이프 장치)

결론적으로, 이 조건을 배제하여 교착 상태를 예방하기는 불가능하다.

2. 자원의 부분 할당을 배제

프로세스들은 각자 자신이 필요한 모든 자원을 미리 할당 받아 실행을 시작하도록 하는 방법이다. 일부 자원만 확보되면 시작할 수 있음에도 불구하고 모든 것을 할당 받을 때까지 기다려야 하고, 할당이 가능했던 일부 자원들은 사용되지 못해 낭비되는 현상 발생한다. (심각한 자원의 낭비가 초래되는 방법이 됨)

3. 자원의 선점 불가능을 배제

모든 자원이 선점 가능하도록 할 경우 교착 상태는 발생하지 않을 것이라는 점을 고려한 해결책이다.

일부 자원을 가지고 실행하던 프로세스가 현재 할당이 불가능한 자원을 요청할 경우 자신이 보유하고 있던 자원을 내 놓게 함으로써 비선점 조건을 없앤다는 것이다.

실행 도중 보유한 자원을 내어놓게 되는 프로세스는 비정상적인 종료와 함께 심할 경우 처음부터 다시 시작해야 하는 불이익을 받게 되는 것이며, 반납되어진 자원들을 사용하여 지금까지 해 왔던 일들이 모두 무효가 된다.

결과적으로 그 동안 가동되었던 모든 자원들은 사실상 낭비된 결과가 되는 것

4. 자원의 환형 대기 상황을 배제

모든 화살표가 한 방향으로만 생성되도록 하여 사이클이 발생될 소지를 없애 교착 상태를 없앤 방법이다. 자원의 낭비와 프로세스의 무한 연기 존재.

<회피 기법>

Dijkstra의 은행가 알고리즘(Banker's Algorithm)이 대표적이다.

[안전 상태(Safe State)]

시스템에 있는 모든 프로세스가 유한 시간 내에 정상적으로 종료될 수 있는 상태를 말하며 그렇지 못할 경우를 불안전 상태라 한다.

안전 상태란 교착 상태가 발생할 수 없는 상태를 말하며, 불안전 상태라고 해서 교착 상태임을 의미하는 것은 아니지만 불안전상태는 교착 상태로 갈 가능성이 있으며 그럴 경우의 방지책이 없음을 뜻한다.

회피 기법은 시스템의 상태가 안전 상태로만 가도록 지속적으로 제어해 나가는 것이며, 각 프로세스의 자원에 대한 요청을 해당 자원이 사용 가능하다고 해서 할당하는 것이 아니라 할당의 결과 시스템이 계속 안전 상태가 되느냐에 의해 결정함을 뜻한다.

은행가 알고리즘이 제대로 작동하기 위해서는 시스템에 대한 몇 가지 가정이 요구 됨

① 시스템 내의 프로세스 수가 고정되어 있어야 한다.

② 자원의 수 역시 고정되어 있어야 한다.

③ 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다.

④ 각 프로세스는 할당 받은 자원을 사용 후 반드시 반납하여야 한다.

 

<Dijkstra의 은행가 알고리즘>

P2가 더 요구할 최대량이 2개이며 이것은 시스템이 현재 가지고 있는 여유량을 넘지 않는다. P2의 성공적인 종료를 유도하고, 반납되는 6개의 자원을 여유량으로 확보하면 P1과 P3의 어떤 요청도 할당 가능하기 때문이다.

 

 

현재의 여유량인 1개의 자원으로는 어떤 프로세스도 향후 자신의 최대 요구량에 이르지 못하는 상태가 되어 불안전 상태가 된다.

<탐지 기법>

교착 상태를 찾아 낸다는 말이고, 교착 상태의 탐지를 위해 현 시스템의 상황을 그래프로 많이 표현하는데, 이것을 자원 할당 그래프(Resource Allocation Graph, RAG)라 한다.

RAG에 대한 그래프 제거(Graph Reduction)법으로 교착 상태를 탐지한다.

[RAG 그래프 설명]

❶ RAG는 방향성(Directed) 이분(Bipartite) 그래프이며 노드(Node)와 에지(Edge)들로 이루어 짐

노드들은 프로세스와 자원들을 표현하며 에지들은 프로세스와 자원들 간의 요청과 대기 상황을 나타냄

프로세스로부터 자원으로 향하는 에지는 보통 두 개의 의미를 가지는데 하나는 요청 중이라는 것과 또 하나는 대기 상태가 되었다는 것이다.

에지 하나가 경우에 따라 다르게 해석될 수 있다는 의미이고, 이럴 경우 RAG로 교착 상태를 탐지하는 작업이 훨씬 어려워지므로 요청 중이라는 상황이 생기지 않게 시스템이 바로 대처하면 에지들의 방향이 나타내는 상황이 할당 아니면 대기와 같이 두가지로 분명해져 탐지 작업이 용이하다.(즉시 할당 상태)

❷ RAG에서 자원 노드는 그 자원의 형(Type)을 나타내고 그 안의 작은 동그라미가 자원의 개수를 나타 낸다. 한 자원 형에 여러 개의 자원이 있을 수 있다.

❸ 한 자원 형에는 자원의 개수를 나타내는 정수(ti)가 있으며, 임의의 노드 a로부터 다른 노드 b로 향하는 에지의 개수는 |(a,b)|로 표현한다.

즉시 할당 상태를 가정하면 자원으로 향하는 에지가 없는 프로세스란 활동이 가능한 프로세스이며 이를 unblocked process 또는 sink라 부른다

[순서]

1. RAG에서 싱크 프로세스들을 찾는다.

2. 싱크에게 할당된 자원들로부터 이 싱크 방향으로 표시된 모든 에지들을 제거한다. -> 싱크는 반납을 할 수 있으므로 "싱크가 갖고 있는 자원들을 모두 반납한다면 그 결과 RAG는 어떻게 될까?"를 적용 시키는 것이다.

3. 반납된 자원들로부터 대기하고 있던 프로세스들은 자원을 할당받을 수 있을 것이다. 싱크 역시 대열에 합류할 것이다.

[RAG의 그래프 제거 과정(교착 상태가 없는 예)]

 

R1형과 R2형은 각각 2개와 1개의 자원을 가지고 있고 현재 싱크는 P3밖에 없으므로 P3로 향하는 에지를 제거한다.

그 결과 반납되는 자원을 P2에게 할당해 준다면 P2가 싱크가 되어 다시 에지들이 제거될 수 있을 것이다.

 

최종적인 결과에서 보듯이 모든 에지가 제거 되므로 제거 전의 원래 RAG에 교착상태는 없다고 밟혀진다.

[RAG의 그래프 제거 과정(교착 상태가 있는 예)]

P2에서 R1로 향하는 에지가 2개가 있는데 이것은 R1형의 자원 2개가 한꺼번에 필요하다는 요청을 나타낸다.

P3으로부터 제거를 시작한 후 그 다음 상황에서 반납된 자원이 P2를 싱크로 만들어 주지 못함을 알 수 있다. 아직 한 개가 더 필요하고 이것은 P1이 가지고 있기 때문이다. 더 이상 에지를 제거해 줄 싱크가 없으며 따라서 애초의 RAG에 교착상태가 있다는 것을 탐지하게 된다.

[그래프 탐색 방법]

 

 

P2가 R1을 요청하게 되면 대기하게 될 것이며 이때 경로를 따라(점선) 탐색해보면 ①의 경우 바로 싱크인 P3을 만나게 되고 교착상태가 아님을 판단한다. 만약 ②의 경로로 먼저 탐색했다면 P2 자신을 되돌아오는 사이클리 있음을 알게 되는데 아직 ①의 경로 탐색이 남아있고 이 경로의 탐색 결과 싱크를 발견하게 되므로 역시 교착상태가 없음을 확인하게 되어 P2의 R1에 대한 요청은 단순히 대기 상태를 만들뿐이라는 사실을 알게된다.

<복구 기법>

교착 상태로부터 벗어나기 위한 방법이다. 교착 상태에 포함되어 있는 한 개 이상의 프로세스를 강제로 종료시켜 이들로부터 반납되는 자원들을 나머지 프로세스들에게 줌으로써 해결하거나, 아니면 교착 상태를 벗어나기 위해 필요한 추가의 자원을 어디서든 갖고와 할당해 줌으로써 해결한다.

프로세스 종료 방식과 자원의 선점에 의한 방식으로 나뉜다.

1. 프로세스의 종료 (Process Termination) 방식

교착 상태를 형성한 프로세스들 중 몇 개를 강제로 종료시켜 이들로부터 반납된 자원으로 복구한다.

어떤 프로세스들을 종료시킬 것인가가 문제인데, 강제로 종료된 프로세스들은 지금까지 해 왔던 일을 포기하게 되고 기회가 왔을 때 다시 자원들을 할당받아 일을 새로 시작해야 하는 희생이 요구되므로, 이러한 희생을 최소화할 수 있기 위해 종료 비용(TerminationCost)이라는 것을 따져 교착 상태로부터 복구될 때까지 종료 비용이 최소인 프로세스부터(Lowest-termination-cost Process First) 종료시킨다. 비교적 간단하나 프로세스 하나를 종료시킬 때마다 교착 상태가 제거되었는지 알아보아야 한다.

교착 상태에 있는 프로세스들의 집합에서 가능한 모든 부분집합을 만들어 이 집합들에 속하는 프로세스들을 종료시켰을 경우의 비용을 따져 역시 최소의 비용이 드는 부분집합에 속하는 프로세스들을 한꺼번에 종료시키는 방식을 취하기도 함

[종료 비용 산정 방법]

- 프로세스의 우선순위(Priority)나 종류, 실행된 시간의 크기, 남은 시간 등

- 우선순위가 낮은 것, 실시간이 아닌 것, 실행된 시간이 적은 것, 남은 시간이 큰 것에 해당될수록 종료 비용이 싸다고 보는 것

최소 비용의 프로세스들을 고를 수는 있으나 모든 부분 집합에 대해 비용을 계산하기가 복잡하고 힘들다.

2. 자원의 선점에 의한 방식

필요한 자원을 가지고 있는 프로세스로부터 강제로 뺏어 교착 상태에 있는 프로세스들에게 줌으로써 해결한다. 자원을 선점 당하는 프로세스는 교착 상태와는 전혀 상관이 없지만, 단지 해당 자원을 가지고 있다는 이유 때문에 선택될 수 있다는 것이다.

(물론 이 방식에서도 선점 시의 최소 비용은 따져야 함)

프로세스의 강제 종료는 그 동안의 일을 없던 것으로 하고 처음부터 다시 해야 하기 때문에 복구 비용을 키우는 주요인이 되며 시스템의 입장에서는 큰 낭비 요인이다.

강제 종료 시의 낭비를 줄이기 위한 방법으로 검사점 지정(Checkpointing) 과 재시작(Restart)을 들 수 있다.

1. 검사점(Checkpoint) : 프로세스들은 실행의 중간 중간에 그 시점까지의 실행 결과를 보존하고 표시를 해 두는 것

강제로 종료될 때는 아예 처음으로 돌아가는 것이 아니라 가장 최근의 검사점부터 차례로 하나씩 되돌리는 것

이 과정에서 교착 상태를 벗어날수 있다면 종료된 프로세스는 처음부터가 아니라 최종적으로 되돌려졌던 검사점에서 보존된 내용으로 재시작을 할 수 있어 잃게 되는 일의 양을 최소화할 수 있음

Copyrightⓒ2014 By 휴먼사이언스