[OS] Deadlock I (Definition, Resource Allocation Graph, Resource Condition, Deadlock Handling)

Deadlock

 Deadlock을 직역하면 교착상태라는 의미이다. 정확히 이게 어떤 뜻일까. OS에서의 Deadlock이란 Process들의 set이 System Resource 혹은 IPC를 위해 Competing 하다가 시스템이 영구적으로 Blocking되는 상태가 되는 것을 의미한다. 예를 들자면 어떤 Process의 set이 blocked되어 있는데 해당 Process set을 깨워줄 수 있는 Process의 set 역시 block 상태에 있다면 어떠한 Process도 진행할 수 없을 것이다. 이러한 상황을 우리는 Deadlock, 즉 교착상태라고 정의한다. 어떤 Process들도 Trigger될 수 없다면 어떤 Process도 진행할 수 없게 된다. 

 

 Deadlock은 Programmer Level에서는 파악하기 매우 어렵다. 왜냐하면 Deadlock은 어떤 자원에 대한 여러 Process들이 동시에 접근하여 사용하고 싶을 때 발생하기 때문이다. 예를 들어서 어떤 교차로가 있다고 하자. 근데 이 교차로에는 신호등이 없다. 운전자들이 모두 이기적이기 때문에 서로 먼저 교차로를 통과하고 싶다. 그래서 모든 운전자가 교차로에 진입하면 더이상 아무도 직진할 수 없는 상황에 닥친다. 이러한 상태를 교착상태라고도 칭한다. 교차로를 자원이라고 한다면 어떠한 특정 순서에 의해서 서로 교차로를 통과해야 교통상황은 정상이지만, 만약 모두 동시에 통과하려고 한다면 해당 구간에서는 분명 정체가 일어날 것이다. 

교착상태 예시.

Resource

 당연한 소리지이만 Deadlock이 발생하기 위해서 Resource의 특성을 알 필요가 있다. 첫 번째로 Resouece는 Non-Preemptable이어야 한다. 비선점 자원은 어떤 Process가 해당 자원을 사용한다면 다른 Process는 그 자원을 사용을 하지 못한다. 만약 다른 Process가 자원을 뺏어 가서 Code를 수행한다면 사실 Deadlock이 일어나지 않을 것이다. 

 Resource는 또 두 가지의 Category로 나눌 수 있다. 하나는 Re-Useable Resource이다. 이는 한 번에 하나의 Process만 사용이 가능하며 고갈되지 않는 자원들을 의미한다. 즉 우리가 앞에서 배웠던 동기화 문제에서 사용되는 자원들을 의미한다. 그렇기 때문에 Resource Request -> Lock(Allocate) -> Use -> Unlock(Release) 의 과정을 거친다. 예를 들자면 Processors, Memory, Device, HW Resources, files, database, semaphores 등이 있다. 다른 하나는 Consumable Resource이다. Consumeable Resource는 Create 되고 Destroy될 수 있는 Resource들을 의미한다. 예를 들어서 Interrupts, Signal, Message, I/O Buffer의 Information 등이 예시이다. 어째뜬 모든 자원을 사용할 때 Deadlock은 발생할 수 있다. 

Resource Allocation Graph

 Deadlock을 파악하는 방법 중 하나는 Resource Allocation Graph를 그려보는 것이다. 이는 Process와 Allocation에 대한 특성을 보기 위한 그래프이다. 이를 통해서 System의 State가 Safe한지, Unsafe한지 파악한다. Safe는 Deadlock이 발생하지 않는 상황이고 Unsage는 Deadlock이 발생할 수 있는 상태를 의미한다. 그래프는 Directed Graph로 그리는데 Vertex에는 두 가지 종류, Edge도 두 가지의 종류가 있다. Process를 나타낼 때 Vertex는 동그라미로, Resource를 나타는데는 사각형으로 표시한다. Edge는 Process에서 나가는 outgoing edge라면 이는 Request이고, Resouece에서 나가는 outgoing edge는 Hold이다. 또한 Resource의 Vertex에서 점들이 있는데 이는 instance의 개수이다. instance가 한개라면 Deadlock이 발생할 가능성이 높아지고 instance가 여러개라면 어떤 instance가 사용중이더라도 다른 instance를 사용하면 되기 때문에 Deadlock의 발생 가능성이 낮아진다. 

 설명대로 그래프를 그려보았다. 왼쪽의 그래프는 Cyclic하다. 이렇게 Resource Allocation Graph를 그려보았을 때 Cyclic하다면 Circular Wait이 발생할 수 있기 때문에 Deadlock이 일어날 가능성이 높다고 할 수 있다. 왼쪽 그래프의 Resource의 Instance는 1개라는 거에 주목을 하자. 그러나 반대로 오른쪽 그래프의 Instance는 3개이다. 따라서 이 그래프는 얼핏 보면 Cyclic처럼 보일 수도 있지만 각각의 Resource Graph의 Instance들이 단일 Instance가 아니기 때문에 완벽한 Cycle이 만들어 진다고는 할 수 없다. 따라서 정리를 해보자면 만약 이 그래프에서 Cycle이 만들어지지 않는다면, 즉 DAG가 만들어 지면 Deadlock은 발생하지 않는다. 하지만 Cycle이 있고 Resource의 Instance가 1개라면 이는 Deadlock이다. 또 Resource의 Instance가 여러개라면 또 Deadlock은 만들어지지 않는다. 

 맨 위에서 살펴보았던 교차로 예제이다. 이를 Resource Allocation Graph로 그려본다면 이러한 그래프가 만들어 지고 각각의 교차로의 Instance는 1차로 이기 때문에 Instance가 하나만 있는 상태일 것이다. 그리고 그래프는 Cycle이 명백히 만들어진다. 따라서 이 상황에서는 Deadlock이 발생한다고 볼 수 있다. 

The Conditions for Deadlock

 그렇다면 조금 더 자세하게 Deadlock이 발생하는 조건에 대해서 살펴보자. 

1. Mutual Exclusion(상호배제): 오직 하나의 Process만 Resource를 사용할 수 있다. 

2. No Preemption(비선점): 어떤 Process가 Resource를 사용하고 있다면 다른 Process는 그 Resource가 Release될 때 까지 사용할 수 없다.

3. Hold and Wait(점유대기): 어떤 Process가 어떤 Reousrce를 holding하고 있다면 그 Process는 다른 Process가 가지고 있는 Resource를 사용하기 위해 대기중이어야한다. 

4. Circular Wait(순환대기): 순환적으로 P0 -> P1 -> P2 -> ... -> Pn -> P0로 순환적으로 대기하는 상황이 발생한다.

 이렇게 4가지의 Condition들이 존재하는데, 1, 2, 3번은 Necessary한 필요조건들이다. 생각해보면 당연한데 1, 2번은 Resource의 특성이고, 3번은 자원의 사용에 대한 특성이다. 4번은 단순히 충분조건이라고 생각하면 되겠다. 

How to handle Deadlock

 그렇다면 우리는 Deadlock이 발생하지 않도록 어떻게 해야할까. Deadlock을 해결하는데는 크게 4가지가 있다. 누군가는 3가지라고 하는데 4번째 방식은 너무나 당연하지만, Deadlock이 추후에 발생했을 때 처리를 제대로 하지 못한다는 단점이 있기 때문이다. 

1. Deadlock Prevention(예방): Deadlock의 Condition을 제약하는 방법이다. 위에서 언급한 Deadlock의 세가지 필요조건들 중 하나만 제거하더라도 혹은, 순환대기를 예방함으로서 Deadlock을 유발시키지 않을 수 있다. 그러나 이 방식은 Concurrency와 Utilization 측면에서 효율적이지 못하다. 또한 이렇게 되면 Resource를 사용하는데 어려움이 있을 수 있다. 
2. Deadlock Avoidance(회피): 회피와 예방이 어떤 차이가 있냐고 묻는다면 회피는 System의 State에 따라 Resource Request를 거절 혹은 승인 하는 방식이다. Request를 아예 받지 않음으로서 Deadlock을 만드는 상황 자체를 회피해버리는 것이다. 그러나 이 방식은 결국 미래에 대한 예측을 해야하는 것이기 때문에 구현의 어려움이 있다. 
3. Deadlock Detection and Recovery: 주기적으로 Deadlock이 발생했는지 체크를 하고 만약 발생한다면 Deadlock을 유발시킨 Process를 kill 시켜버리거나 Resource를 강제적으로 Release해주는 방식이다.
4. Just ignore the Problem: 언급했지만 가장 단순하다. 그냥 OS를 재부팅 시켜버리는 방법이다. 

Deadlock Prevention

 대부분 이 방식을 많이 채택해서 Deadlock에 대한 문제를 해결한다. 그러나 Resource의 특성에 따라 Mutual Exclusioin과 No-Preemption 은 우리가 어떻게 해결할 수 없는 부분이다. 그렇기 때문에 Hold and Wait과 Circular Wait을 적절히 활용하여 문제를 해결한다. Hold and Wait은 필요한 모든 Request를 넣고 Lock을 걸어버려 해결할 수 있다. 그러나 이 역시 Concurrency문제가 발생하게 된다. Circular Wait은 Resource를 Ordering 함으로서 문제를 해결할 수 있다. Resource type에 Linear한 번호를 매긴다. Resource를 사용할 때 순서대로 사용한다면 Backward Edge가 발생하지 않는다. 따라서 Deadlock은 발생하지 않는다. 그러나 이 방식은 Kernel Level에서 구현하는 것이 어렵고, 점진적인 자원 요청에 대한 희생이다. 만약 자원이 추가되고 삭제되며 Process들이 늘어난다면 어떻게 Ordering을 다시 새롭게 해야하는지에 대한 문제이다. 

 

다음 파트에서는 Deadlock의 대표적인 예시인 Dininig Philosopher Problem을 통해서 Deadlock 문제를 같이 해결해볼 것이다. 또한 다룰 수 있다면 Banker's Algorithm까지 다뤄볼 예정이다. 

Reference

이미지 출처:

http://15418.courses.cs.cmu.edu/spring2013/article/27