8-2강. Deadlock(Cont'd)

---

2. Deadlock Avoidance

 이 방법은 어떤 추가적인 정보를 이용하여 데드락을 막는 방법이다. 이 추가적인 정보라 함은, 프로세스마다 자기 평생에 자원을 최대로 쓰면 얼마나 쓸지(자원 사용의 최대치)에 대한 정보이다.  

 

그림 6 : Deadlock Avoidance

 

 Deadlock Avoidance Algorithm은 두 종류가 있다. 첫 번째는 자원당 instance가 하나인 경우이고, 두 번째는 자원당 instance가 여러 개인 경우이다. 먼저 instance가 하나인 경우부터 살펴보자.

 

---

* Single instance per resource types (Resource Allocation Graph Algorithm) *

 

그림 1 : Resource Allocation Graph Algorithm

 

 Deadlock Avoidance에서는 위 그래프에서 실선뿐만 아니라 점선도 둔다. 점선은 프로세스에서 자원으로 향하는 에지에 만 있으며 해당 프로세스가 그 자원을 언젠가는 요청할 수도 있음을 의미한다. 그러다가 실제로 그 자원을 요청하게 되면 점선이 실선으로 바뀐다. 그렇게 되면 선으로만 놓고 보면 Cycle이 형성은 됐지만 실제로 Deadlock은 아니다. 1번 프로세스가 2번 자원을 요청할 '수'도 있기 때문이다. 하지만 첫 번째 그림에서 두 번째 그림으로 넘어갈 때 P2에서 R2로 들어가는 점선이 실선으로 바뀌며 R2가 P2에게 가버리면, 세 번째 그림에서 보이듯 점선을 포함하여 Cycle이 형성되고 이때 운이 나쁘게도 P1이 R2에게 요청을 '실제로' 보내버린다면 Deadlock이 '발생 위험성'이 있기 때문에 R2는 현재 아무에게도 귀속되지 않았음에도 P2의 R2요청을 거부하고 P1이 R1을 반납해서 P2가 R1을 가질 수 있게 될 때까지 P2로 하여금 기다리게 하는 것이 Deadlock Avoidance이다. 

---

* Multipe instances per resource types (Banker's Algorithm) *

 

  이 방법은 자원을 테이블 형태로 만들어서 자원을 할당할지 말지 결정해주는 알고리즘이다. 

<그림 2>의 예시를 살펴보자. 

 

 먼저 프로세스는 P0, P1, P2, P3, P4 5개가 있고, 자원의 instances는 각각 A는 10개, B는 5개, C는 7개가 있다. 그리고 Allocation Table은 각 프로세스에게 자원의 instance들이 몇 개씩 할당되어 있는가를 보여준다. 

Available Table은 각 자원마다 몇 개의 instance가 가용한지를 보여준다.

Max Table은 각 프로세스가 평생에 걸쳐 최대로 쓸 자원을 보여준다.

Need Table은 Max에서 Allocation을 뺀다. 추가로 요청할 수 있는 자원의 개수를 보여준다.  

 

 이 Banker's Algorithm도 Single instance인 경우와 크게 다르지 않다. <그림 2>의 예시에서 현재 C자원은 가용하다. 그래서 P0이 C자원 1개를 요청한다면 주어야 할지 결정할 때, 주지 않는다. 왜? 현재 가용자원은 A B C 각각 3 3 2이다. 그런데 P0이 지금 이 순간(~) 요청할 수 있는 자원의 최대는 7 4 3이다. 가용자원으로 충족 불가능하다. 물론 지금 이 자원들을 모두 한꺼번에 요청할지 아닐지는 모르나 그럴 위험이 분명 존재한다. 따라서 unsafe state로 갈 수 있기 때문에 주지 않는다. 즉, 현재 가용자원으로 어떤 프로세스의 현재 최대 요청 자원을 커버하지 못하면 자원을 주지 않는 것이 핵심이다. 반면 P1은 Need가 1 2 2인데 가용자원은 3 3 2 이므로 어떤 자원을 요청하든 준다. 왜냐하면 남은 Need를 한 번에 모두 요청해서 주게 되면 더 이상 자원을 요청할 일이 없기 때문이다. 나머지. P2는 안 주고, P3은 주고, P4는 안 준다.

 

그림 2 : Banker's Algorithm

 정리하자면 Deadlock Avoidance는 항상 safe한 상태를 유지하고 unsafe 한 상태를 들어가지 않게 된다. 특히 Banker's의 예시에서는 항상, 가용자원으로 어떤 프로세스의 최대 요청량을 처리할 수 있을 때만 자원을 주기 때문에 언제나 Safe state를 만족하도록 처리하고 언젠가는 P0과 같이 많은 자원을 요구하는 프로세스도 처리해 줄 수 있게 되는 것이다. 이 조건을 만족시키는 sequence는 <P1, P3, P4, P2, P0>이 존재하므로 이 시스템은 Safe state에 있다.

 

그림 3 : Banker's Algorithm Example

---

3. Deadlock Detection and Recovery

 두 번째 방법까지는 아예 Deadlock이 발생하지 않도록 막는 것이었고, 세 번째 방법 부터는 Deadlock이 발생하도록 놔두는 것이다. 잘 발생하지도 않는 Deadlock을 막겠다고 여유 있는 자원을 안 주고 기다리게 하는 건 시스템을 너무 비효율적으로 만들기 때문이다. 그러다가 실제로 Deadlock이 일어나면 Detection을 하고, 발생했으면 Recovery하는 방법이 세 번째 방법이다. 이것도 이전 방법과 마찬가지로 자원당 instance가 하나인지 여러 개인지에 따라 처리 루틴을 다르게 한다. 

 

그림 4 : Deadlock Detection and Recovery

---

* Single instance per resource types (Wait-for Graph Algorithm) *

 

 이 방법은 두 번째 방법에서 Resource Allocation Graph 방법과 완전히 동일하다. 왼쪽 그래프가 그러하다. 그런데 이것을 Corresponding Wait-for Graph로 바꿀 수 있다. 자원을 빼버리고 프로세스만 가지고 그래프를 만들 수 있다.

그림 5 : Single instance per resource

 

 

그럼 자원당 instances가 여러 개인 경우는 어떻게 되느냐? 두 번째와 비슷하게 Table을 그려 처리한다.

프로세스는 P0, P1, P2, P3, P4로 5개가 있다.

그리고 자원은 A, B, C로 각각 7, 2, 6개의 instance가 있다.

여기서는 각 프로세스가 평생 몇 개의 자원을 쓸지는 관심 대상이 아니다. 

Allocation Table은 현재 할당된 자원을 보여준다.

Request Table은 실제로(가능한 최대 요청량이 아님) 현재 요청한 자원을 보여준다.

Available Table은 가용자원을 보여준다.

 

여기서는 Avoidance와는 조금 다르게 프로세스에 대해 조금 낙관적으로 생각한다. 현재 요청하지 않은 프로세스는 자원을 반납할 것이라고 생각한다. 물론 자원을 꼭 내어 놓는다는 보장은 없다. 어차피 당장 데드락이 걸리는지 안 걸리는지만 관심이 있기 때문이다.

---

* Multipe instances per resource types  *

 

그림 6 : Multiple instances per resource

 

 그러나 <그림 6>과는 달리 <그림 7>과 같이 P2가 C 1개를 요청하면 어떻게 될까? P0이 자원을 반납하더라도 Available은 0 1 0이 될 것이고 이 자원으로는 아무것도 처리할 수 없기 때문에 Deadlock이 된다.

그림 7 : Deadlock이 된 경우

 그럼 <그림 7>처럼 Deadlock이 생겼으면 어떡할 것이냐? Deadlock Recovery를 해야 한다. 

 

1. Process Termination

• 데드락에 연루된 모든 프로세스를 모두 죽이는 방법이 있다.

• 혹은 데드락에 연루된 프로세스를 하나씩 죽여서 데드락이 사라지는지 보는 방법이 있다.

 

2. Resource Preemption

 프로세스를 죽이지 않고 데드락에 연루된 프로세스가 가진 자원을 빼앗는 방법이 있다. 이때 비용이 최소화 되는 프로세스 하나를 골라서 자원을 빼앗아 safe state로 roll back 시킨다. 그러나 동일한 프로세스가 계속해서 그 대상자로 지목되는 경우 Starvation Problem이 발생할 수 있다. 따라서 프로세스 선정 시에 roll back 횟수도 함께 고려해야 한다.

 

그림 8 : Deadlock Recovery

---

4. Deadlock Ignorance

 이 방법은 아무것도 아니다. 데드락은 굉장히 드물게 발생하는 일이기 때문에, 이 데드락을 방지하거나 처리하기 위해 일을 하는 것이 대단히 낭비라는 것이다. 데드락에 대해 아무일도 하지 않는다. 현대 범용 OS들은 전부 이 방식을 채택하기 때문에 사실은 Deadlock은 중요하지 않다. 옛날 문제라는 뜻이다.

 

본 글들은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성됩니다.

링크 : http://www.kocw.net/home/search/kemView.do?kemId=1046323