[OS] 교착 상태 : 교착 상태 해결 방법!

교착 상태 해결 방법

 

해결 방법은 4가지로 분류할 수 있다. 예방(Prevention) 기법, 회피(Avoidance) 기법, 탐지(Detection) 기법, 복구(Recovery) 기법이 있으며 탐지와 복구 기법을 묶어 하나로 보기도 한다.

 

 

1. 예방 기법

 이전에 살펴본 4가지 원인 조건 중 하나를 없애 교착 상태 발생 자체를 막는 방법이다.

 

 

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

• 모든 자원을 공유 가능 자원으로 만들어 교착 상태의 발생을 차단하는 방법
• 그러나 프린터, 테이프 장치 등 프로세스가 차례대로 사용해야하는 자원들은 공유가 불가능

=> 결론적으로 조건 배제가 불가능하다.

 

 

1-2. 자원의 부분 할당 배제

• 프로세스가 각자 필요한 모든 자원을 미리 할당받아 실행을 시작하는 방법
• 그러나 일부 자원만 확보되면 시작할 수 있음에도 불구하고 모든 걸 할당받을 때까지 기다려야 함
• 할당이 가능했던 일부 자원들은 사용되지 못해 낭비되기도 함

=> 심각한 자원 낭비 초래, 무한 대기 현상 발생

 

 

1-3. 자원의 선점 불가능성 배제

• 모든 자원을 선점 가능하도록 만들어 교착 상태 발생을 방지하는 방법
• 다른 프로세스가 현재 사용 중인 자원을 요청하면 그 자원을 내놓도록 함

=> 자원을 내놓은 프로세스가 비정상적인 종료와 함께 심각한 불이익을 얻게 됨(낭비)

 

 

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

• 자원들의 순서를 정하고 프로세스가 이 순서대로 요청하도록 만들어 사이클이 발생될 소지를 없애는 방법

=> 순서를 지켜야 하기 때문에 자원의 낭비, 프로세스의 무한 대기가 발생함.

 

 

 

---

2. 회피 기법

예방 기법처럼 교착 상태를 방지하지만, 배제하는 방식을 사용한 예방 기법과 다르게 알고리즘을 사용한다. 회피 기법에서는 자원의 낭비가 덜 발생한다.

 

 

2-1. 안전 상태란?

 시스템에 있는 모든 프로세스가 유한(Finite) 시간 내에 정상적으로 종료될 수 있는 상태를 말한다. (<-> 불안전 상태) 곧 안전 상태는 교착 상태가 발생할 수 없는 상태이며, 불안전 상태는 교착 상태로 갈 가능성이 있는 상태를 의미한다.

 회피 기법은 시스템의 상태가 지속적으로 안전 상태이도록 제어하는 방법으로, Dijkstra의 은행가 알고리즘이 대표적이다. 은행가 알고리즘이 작동하기 위해서는 4가지의 가정이 요구된다.

 

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

2) 자원의 수가 고정되어 있어야 한다.

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

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

 

(한계가 존재한다는 뜻..)

 

 

2-2. Dijkstra의 은행가 알고리즘

OS? Oh Yes! - 김 주균 지음

 위의 시스템 상태는 안전할까? 정답은 안전하다.

 이미 4개의 자원을 보유한 프로세스 P2에게 여유량 2를 할당하면 P2는 성공적으로 작업을 종료하고 다시 6개의 자원을 반환한다. 프로세스 P1과 P3에게 반환받은 6개의 자원에서 각각 3개의 자원을 나눠주면 시스템은 결론적으로 모든 프로세스를 정상 종료할 수 있다.

 

 

 

---

3. 탐지 기법

 탐지 기법은 앞의 두가지 방법과 달리 교착 상태의 발생을 허용하며 이를 어떻게든 찾아내 적절한 대응을 하는 방법이다. 교착 상태를 탐지하기 위해서 현재 시스템의 상황을 그래프로 많이 표현하는데, 이를 자원 할당 그래프(RAG)라고 부른다.

 

RAG가 뭐야 ?

1) RAG는 방향성 이분 그래프로 Node와 Edge로 이루어져 있다.

• Node: 프로세스와 자원
• Edge: 할당 상태와 대기 상태

2) RAG에서 Node는 그 자원의 형태(Type)를 나타내고 그 안의 작은 동그라미가 자원의 개수를 나타낸다.

3) 한 자원 노드에는 개수를 나타내는 정수가 있으며, node a -> node b로 향하는 edge 개수는 | (a,b) | 로 표현한다.

 

 

 교착 상태 탐지 기법은 RAG에 대한 그래프 제거법으로 수행된다. 예를 들어 자원으로 향하는 edge가 없는 프로세스는 활동이 가능한 프로세스로 unblocked process 또는 sink라고 부른다.

 

 

탐지 기법의 순서

 그렇다면 탐지 기법은 RAG와 sink를 어떻게 이용해서 교착 상태를 탐지하는 걸까? OS? Oh Yes! 교재에 있는 이미지와 함께 그 과정을 살펴보도록 하자.

 

1. 현재 자원으로 향하는 edge가 없는 sink는 P3 하나 뿐이다. 그렇다면 P3 프로세스가 사용 중인 모든 자원을 반납했다고 가정하여 P3으로 향하는 edge들을 모두 지워본다.

 

2. P3이 반납한 자원을 P2가 요청하고 있다. 그러므로 반납된 자원을 다시 P2에게 할당하면 P2는 sink가 된다. 다시 P2 프로세스가 사용 중인 모든 자원을 반납했다고 생각하고 P2로 향하는 모든 edge를 지운다.

 

 

 

3. P2 프로세스가 반납한 R2 자원을 자시 P1에게 할당하면 마지막으로 남은 P1 프로세스도 sink가 된다. 결과적으로 모든 edge가 지워지기 때문에 이 RAG에 교착 상태는 존재하지 않는다. 교착 상태가 있는 RAG는 이 과정을 반복했을 때 여전히 edge가 남아있게 된다.

 

 

 

 

 

그래프 탐색 방법

 그래프 탐색 방법은 또다른 탐지 기법 중 하나이다. 교착 상태는 프로세스가 자원을 요청한 다음 대기 중인 상태에서 형성될 가능성이 높다. 그러므로 대기 중인 프로세스의 edge를 따라 그래프를 탐색하며 sink가 있는지 탐지하는 기법이다. sink가 발견되면 교착 상태가 없고, 반대로 자기 자신에게 되돌아오는 사이클이 존재하면 교착 상태가 있다고 판단한다. 

 

 

 

+ 그 외 노트(Knot)에 대한 부가적인 설명이 존재하지만 시간 상 생략.

 

 

4. 복구 기법 (Reduction)

 복구 기법은 교착 상태로부터 벗어나기 위한 방법이다. 벗어나기 위해서는 교착 상태에 포함된 한 개 이상의 프로세스를 강제로 종료시키거나, 교착 상태 해결에 필요한 자원을 추가적으로 갖고와 할당해줘야 한다.

 

1) 자원 선점에 의한 방식

 프로세스를 강제 종료해 갖고 있는 자원을 강제로 뺏어 교착 상태에 빠진 프로세스들에게 주는 방식으로 문제를 해결한다. 물론, 이 때에도 선점 시 최소 비용을 따져야 한다. --> 복구 비용을 키우는 주요인이며 큰 낭비 요인이기 때문

 

 낭비를 줄이기 위한 방법으로 '검사점 지정(Checkpointing)', '재시작(Restart)'이 있다.