8-1강. Deadlock

 이미 Deadlock이 무엇인지는 앞선 7강 동기화 문제에서 살펴본 바가 있다. 이것을 좀 더 가시화한 그림이 다음이다. 앞으로만 갈 수 있는 도로에서 차들이 꽉 막혀 진행될 수 없는 상태이다. 시스템 안에서 Deadlock은 자원이 있는데 각 프로세스들이 어떤 자원은 절대 내놓지 않고 갖고 있으면서 다른 자원을 얻으려고 하는 상태를 뜻한다. 

 

그림 1 : Deadlock Visualization

---

 * 자원의 사용 절차 및 Deadlock 발생의 4가지 조건*

 

즉, 데드락이 생기는 이유는 자기 것을 내놓지 않고 다른 자원을 얻으려는 일종의 욕심 때문에 발생한다. 그렇다면 프로세스가 자원을 어떤 절차로 사용하는가 먼저 살펴보자.

 

1. Request (요청)

2. Allocate (할당)

3. Use (사용)

4. Release (반납)

 

이러한 과정 속에서 데드락이 발생하는 조건을 살펴보자.

 

1. Mutual Exclusion (상호 배제) : 상호 배제적으로 사용되는 자원일 때이다. 어떤 프로세스가 다른 프로세스와 동시에 자원을 사용할 수 있다면 데드락은 발생하지 않는다.

 

2.  No preemption (비선점) : 프로세스는 자원을 스스로 내어놓을 뿐 빼앗기지 않는다.

 

3. Hold and wait (보유 대기) : 일을 하기 위해 가지고 있는 자원은 절대로 내어놓지 않고 다른 자원이 오기까지 기다린다. 

 

4. Circular wait (환형 대기) : 자원을 기다리는 프로세스들 간에 Cycle이 형성됨. 예를 들어 P0은 P1이 가진 자원이 필요하고, P1은 P2가 가진 자원이 필요하고,... Pn-1은 Pn이 가진 자원이 필요하고, Pn은 P0이 가진 자원이 필요할 때 데드락이 발생한다. 

그림 2 : Deadlock 발생 조건

---

 * 자원 할당 그래프 (Resource-Allocation Graph) *

 

 위 네 가지 조건이 모두 만족돼야 데드락이 발생하기 때문에 위 네 가지 중 하나를 깨면 데드락이 해결될 것이다. 데드락 해결 방법을 설명하기에 앞서 자원과 프로세스의 관계를 나타내는 '자원 할당 그래프'에 대해 알아보자.

 

그림 3 : 자원 할당 그래프

 

  프로세스는 원, 자원은 사각형으로 나타내며 자원 내에 조그만 동그라미는 자원의 instance 를 의미한다. 그러니까 동그라미의 개수는 해당 자원의 개수이다. 프로세스에서 자원으로 향하는 에지는 자원을 애타게 기다리는 것을 의미하고, 자원에서 프로세스로 향하는 에지는 자원이 해당 프로세스에 할당되어 있음을 의미한다. 

 

그림 4 : Deadlock 발생 예시

 이 엣지 특성을 염두에 두고 위 그래프들을 살펴보자. 만약 에지를 따라가는데 Cycle이 발생한다면 데드락이 발생할 '수' 있다. 자원이 하나씩만 있다면 100% 데드락일 것이고, 여러 개 있다면 데드락이 아닐 수 있다. 하지만 첫 번째 그림에서는 R2가 자원이 두 개 임에도 Cycle이 두 개 발생하기 때문에 데드락이다. 반면 두 번째 예시에서는 Cycle이 있기는 하지만 자원들의 instance가 두 개이며, Cycle에 기여하지 않은 자원의 instance는 Cycle을 발생시키지 않기 때문에 데드락이 아니다. Cycle이 없다면 100% 데드락이 아니다. 

---

 그렇다면 이제 Deadlock을 어떻게 처리하는지 알아보자. 처리 방법에는 네 가지가 있다.

 

1. Deadlock Prevention

2. Deadlock Avoidance

 

위 두 가지는 데드락을 방지하는 방법이고

 

3. Deadlock Detection and recovery

4. Deadlock Ignorance

 

위 두 가지는 데드락이 방지하는 것이 아니라 데드락을 recover하거나, 데드락을 무시해 버리는 것이다.

 

 

 

---

1. Deadlock Prevention

 데드락을 미연에 방지하는 Deadlock Prevention은 가장 강력한 방법이다. 위에서 소개한 데드락의 네 가지 조건 중 하나를 무산시켜 버린다. 조건을 하나씩 살펴보자.

 

1. Mutual Exclusion : 이것을 데드락 방지를 위해 미리 무산시킬 수는 없다. 그 이유는 공유해서 쓸 수 있는 자원이었다면 애초에 데드락 문제가 대두될 여지조차 없기 때문이다.

 

2. Hold and Wait : 어떤 작업을 하기 위해서 필요로 하는 자원을 획득하려고 할 때, 내가 가진 자원은 절대 내놓지 않고 다음 자원이 오기를 기다리는 것인데, 이 조건을 데드락을 무산시키는 데 어떻게 이용할 수 있을까?

 먼저 프로세스를 시작할 때 모든 필요 자원들을 미리 할당받게 하는 방법으로 치료할 수 있다. 그러나 이렇게 하면 자원이 너무 낭비가 될 것이다. 프로세스 실행 내내 모든 자원을 계속해서 쓰는 것이 아니기 때문이다. 그래서 자원을 요청할 때는 가진 자원을 모두 놓고 나서 다시 요청하는 방식으로 처리할 수 있을 것이다.

 

3. No preemption : 빼앗지 못하기 때문에 데드락이 발생할 수 있기 때문에 외부에서 빼앗으면 된다. 이러한 이유 때문에 CPU는 데드락이 발생하지 않는다. 애초에 빼앗을 수 있게 설계가 되었기 때문이다. 그런데 Preemption이 허용되지 않는 자원이 있다. CPU처럼 Backup and Restore가 되지 않는 자원에 관해서이다. 따라서 항상 이 방법을 통해 치료할 수 있는 것은 아니다. 

 

4. Circular Wait : Cycle이 생기지 않도록 방지하는 것이다. 이 치료법은 식사하는 철학자 문제에서도 나왔고, 그전에 이야기했던 동기화 문제에서 처리했던 방식과 비슷하다. 자원에 번호를 매기고 1번 자원을 얻어야만 2번 자원을 얻을 수 있게끔 해버리면 데드락이 생기지 않을 것이다. 

 

그러나 이러한 방법은 자원의 이용률을 저하시키고, throughput을 감소시키고, 어쩌면 starvation 문제도 발생시키는 문제가 발생하는 등 비효율적인 면이 있다.

 

그림 5 : Deadlock Prevention

 

---

2. Deadlock Avoidance

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

 

그림 6 : Deadlock Avoidance

 

 

그림 7 : 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을 가질 수 있게 될 때까지 기다리게 하는 것이 Deadlock Avoidance이다. 

 

---

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

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