[OS] 현대 OS의 Deadlock 처리

데드락이 발생하기 위한 조건

1. Mutual Exclusion : 한 resource에 대해 한 번에 하나의 task만 사용할 수 있다.

2. Hold and Wait : 어떤 task가 multiple resource를 필요로 하는데, 하나의 resource를 잡는 데는 성공했지만, 또 다른 resource를 잡는 데에는 실패했을 때, "첫 번째로 잡은 resource를 잡고 있는 채로, 두 번째 resource를 기다리는 상태"

3. No preemption : resource를 잡고 있는 task를 강제로 resource를 빼앗을 수 없음.

4. Circular wait : taskA는 taskB가 잡고 있는 resource를 기다리고, taskB는 taskC가 잡고 있는 resource를 기다리며 taskC는 taskA가 잡고 있는 resource를 기다리고 있는 순환 관계

 

cf. 위 네 가지 조건을 모두 만족해야 데드락이 발생한다. 

 

데드락 해결

1. 데드락이 절대 발생하지 않도록 하기 : 1) deadlock prevention, 2) deadlock avoidance

2. 데드락이 발생하면 그때 해결하기 : 1) deadlock detection and recovery, 2) just ignore

 

[deadlock prevention]

위 데드락이 발생하기 위한 조건 중 하나 이상의 조건을 만족시키지 않도록 함으로써 데드락을 사전에 예방한다. 하지만 1, 2, 3 방식을 만족하지 않도록 하는 것은 거의 불가능하다. Mutual Exclusion과 No preemption은 OS의 내재된 특성이라 막는다는 것 자체가 성립할 수 없으며, Hold and Wait를 방지하는 경우는 거의 적용하기 어렵다. 보통의 경우 필요한 resource들을 모두 한 번에 잡아 서로 간의 연관관계를 고려해 resource들을 사용하는데, Hold and Wait를 만족하지 않도록 한다면 적절한 데이터 처리가 불가능하기 때문이다.

 

따라서 보통의 경우 4번(Circular wait)을 발생하지 않도록 하는 방식으로 데드락을 예방한다. 전체 resource들에 우선순위를 부여하고 ordering 한 순서대로만 resource를 사용할 수 있도록 함으로써 Circular wait가 만족하지 않도록 한다. 하지만 이 방식에는 모든 resource들에게 우선순위를 부여하고 ordering을 계산하는 등의 오버헤드가 존재한다.

 

[deadlock avoidance]

이와 관련된 기술로 Banker algorithm, resource allocation graph 등이 있지만 거의 사용하지 않는 방식이다.(완전 이론적) 어떤 task가 어떤 resource를 잡을지 미리 예측하는 방식인데, 미래를 예측하는 것 자체가 말이 안 된다.

 

[deadlock detection and recovery]

데드락 발생하면 해당 task를 중지시키고 해당 task가 잡고 있던 모든 resource를 회수하는 방식이다. 하지만 task가 진행 중에 있는 resource를 도중에 회수한다는 것은 매우 위험한 방식이다. resource들끼리 서로 엮겨있기 때문에 다른 task에게 부작용을 끼칠 수 있다. 따라서 거의 사용하지 않으며 사용해서도 안된다.

 

[just ignore]

놀랍게도 거의 대부분의 현대 OS들이 사용하는 방식으로, 데드락 발생 자체를 그냥 무시한다. 발생한 문제를 무시하는 알고리즘을 'ostrich algorithm'이라고 한다. 사실 데드락은 거의 발생하지 않으며 deadlock prevention 방식은 cost가 매우 크다. 따라서 OS입장에서는 데드락에 대해 책임 지는 것  자체가 투자 대비 이익(ROI)이 비효율적이다. 

 

 

 

 

결론 : 대부분의 OS는 데드락에 대해 무시하는 방식을 취하며 데드락에 대해 책임을 지지 않는다.

 

 

 

 

Reference

- https://en.wikipedia.org/wiki/Ostrich_algorithm