[OS] Deadlock

OS에서 deadlock이란 용어는 하나 또는 여러 개의 프로세스가 일어날 수 없는 event를 기다리며 영원한 대기하는 상태를 말한다.

실제로 위 그림을 보면, process 1 (P1)은 resource 1 (R1)을 요구하지만, R1은 이미 process 2 (P2)에 의해 allocation된 상태다. 그리고 P2는 resource 2 (R2)를 요구하지만 P1에 의해 allocation 된 상태라서 이도 저도 하지 못한다. 이런 경우를 deadlock이라고 부른다. 그리고 위 그래프를 Resource Allocation Graph (RAG) 라고 부르는데, 해석하는 방법은 process에서 나오는 화살표는 request, resource에서 나오는 화살표는 allocation의 의미다.

Deadlock을 처리하는 방법은 크게 세 가지로 나눌 수 있다.

1. 시스템이 결코 deadlock에 되지 않도록 보장하기 위하여 deadlock을 예방하거나 회피하는 방법을 사용
2. 시스템이 deadlock이 되도록 허용한 다음에 회복시키는 방법
3. 문제를 무시하고 deadlock이 시스템에서 결코 발생하지 않은 척 무시

1. Deadlock의 조건

System에서 deadlock이 걸리는 조건인지 아닌지를 판단하는 조건은 다음과 같이 네 가지를 모두 만족시켰을 경우다. 반대로 말하면 하나라도 만족되지 않으면 deadlock이 발생되지 않는다.

1. Mutual exclusion: 하나의 resource는 한 process만이 allocation 가능해야 한다.
2. Hold-and-wait: resource를 점유하는 process가 이미 다른 process에 의해 점유 된 resource를 요구해야 한다.
3. No preemption: 다른 process에 의해 할당된 resource는 중간에 선점이 불가능해야 한다.
4. Circular wait: 원을 그리는 형태로 process 집합이 원하는 resource를 서로 원하는 구조가 만들어져야 한다.

위 RAG는 cycle이 2개가 있는 예시다.

2. Deadlock Prevention

Deadlock을 예방하는 방법은 위 deadlock 조건 중 하나라도 지켜지지 않도록 하는 것이다.

1. Eliminate mutual exclusion: 여러 process가 shared resource를 사용하도록 한다. 그러나 몇 resource는 본질적으로 공유가 불가능한 경우가 있기 때문에 mutual exclusion을 제거하는건 쉽지 않다.
2. Eliminate hold-and-wait: process가 실행되기 전 필요한 모든 resource allocation을 한다. 또는 resource가 de-allocation 될 때만 request 할 수 있도록 해도 되는데, 이런 경우엔 starvation이 발생될 수 있다.
3. Eliminate no preemption: higher priority를 가지는 process에 의해 할당된 resource는 중간에 선점이 가능하도록, 즉 preemption 되도록 허용한다.
4. Eliminate circular wait: resource에 unique number를 할당해 resource allocation을 순서에 맞게 끔 해준다.

3. Deadlock Avoidance

기본적으로 deadlock prevention condition이 deadlock avoidance condition보다 엄격하다. 대표적인 deadlock avoidance 방법으로 Banker’s Algorithm이 있다.

3.1 Banker’s algorithm

Dijkstra에 의해 만들어진 이 알고리즘은, 우선 다음과 같은 input 정보가 필요하다.

1. Max need of resources by each process 
2. Currently, allocated resources by each process
3. Max free available resources in the system

그리고 resource request는 다음과 같은 조건에서 수행된다.

1. Request가 max need보다 작거나 같아야 한다.
2. Request가 free resource보다 작거나 같아야 한다.

총 4개의 resource와 4개의 process로 구성된 example로 설명을 해보자면 다음과 같다.

// Total resources in system:
A B C D
6 5 7 6

// Available system resources are:
A B C D
3 1 1 2

// Processes (currently allocated resources):
    A B C D
P1  1 2 2 1
P2  1 0 3 3
P3  1 2 1 0

Processes (maximum required resources):
    A B C D
P1  3 3 2 2
P2  1 2 3 4
P3  1 3 5 0

// Need = maximum resources - currently allocated resources.
// Processes (need resources):
    A B C D
P1  2 1 0 1
P2  0 2 0 1
P3  0 1 4 0

최종적으로 need를 보고 현재 available resource로 우선적으로 해결 할 수 있는 process에 allocation을 해주면서 하나씩 coupling을 푸는 방식이다.
만약 B resource에 한정해서 보자면, P2에게 resource allocation을 할 경우 need가 available resource보다 크기 때문에 deadlock이 발생 될 수 있다. 따라서 다른 process를 우선적으로 처리해줘야 한다.

Reference

1. https://www.geeksforgeeks.org/deadlock-prevention/?ref=lbp