[운영체제] Deadlock

들어가며

Deadlock 현상은 Synchronization으로 인해 발생한다. Race Condition을 해결하기 위해 Synchronization이 필요하기 때문에, 우리는 Deadlock을 방지하고 해결할 수 있는 방법을 찾아야 한다.

 

Deadlock

서로가 서로에 의해 어느 프로세스도 실행되지 못하는 상황을 의미하며 한국어로는 교착 상태라고 한다. Dining Philosphier Problem을 떠올리면 된다.

 

Deadlock의 성립 조건

1. Mutual Exclusion : 공유 자원에 대해 한번에 하나의 프로세스만 접근한다.
2. Hold and Wait : 자원을 쥐고있더라도 필요한 모든 자원을 얻은 후에 실행한다.
3. No preemption : 스케쥴러에 의해 실행 권한을 빼앗기지 않는다.
4. Circular Wait : 자원을 얻고자하는 프로세스들이 서로 Cycle을 형성한다. (Dinining Philosophier problem)

deadlock이 발생하기 위해선 위 4가지 조건을 모두 만족해야 한다. 이 조건들 중 하나라도 성립되지 않으면 Deadlock은 발생하지 않는다.

 

Resource Allocation Graph

Circular Wait 상태를 표현하기 위해 Resource Allocation graph를 사용한다. 그래프의 구성요소에 대해 알아보자.

 

구성요소

Node

한 instance는 하나의 자원을 의미한다.

 

Edge

Request edge : process -> resource type 방향의 간선이다.

Assignment edge : resource type -> process 방향의 간선이다.

 

Cycle이 없는 그래프

No Cycle graph

 

Cycle이 있는 그래프

Cycle Graph

Safe와 Unsafe

Safe : Cycle이 형성되지 않는 상태를 의미하며 Deadlock이 절대 발생하지 않는 상황이다.

Unsafe : Cycle이 형성된 상태를 의미하며 Deadlock이 발생할 수도 있는 상황이다.

 

Cycle이 있다고 해서 무조건 Deadlock이 발생하는 것은 아니다.

 

Deadlock Prevention

Deadlock은 4가지 조건을 만족하는 상황에서만 발생한다고 했다. Deadlock Prevention은 조건을 성립하지 않도록 하여 Deadlock을 사전에 방지하는 방법이다.

 

1. No Mutual Exclusion

공유된 메모리에 대해 여러개의 프로세스게 동시에 작업하는 것을 허용함으로써 Deadlock이 발생하지 않도록 막는 방법이다. 이 방법은 Race Condition이 발생하지 않는 상황에서는 유효하지만, Critical Section 문제를 해결할 수 없기 때문에 불가능한 방법이다.

 

2. No Hold and Wait

쥐고있는 자원이 없을 때만 자원을 요청할 수 있도록 만드는 방법이다. 이를 구현하는 방식은 두 가지로 나뉜다.

 

첫번째는, Total Allocation이라고 불리며, 필요한 모든 자원이 모두 사용 가능할 때만 자원을 요청 가능하게 만드는 방식이다. 두번째는,  hold하고 있는 모든 자원을 놓아주고나서 필요한 모든 자원을 요청할 수 있도록 하는 방식이다.

 

하지만, 이 두 가지 방식 모두 실효성이 없는데, 자원을 할당받기까지 오랜 시간이 소요되기 때문이다.

 

3. Preemption

Preemption을 허용하는 방법이다. 하지만 이 방법 또한 Mutual Exclusion와 같은 맥락에서 불가능하다. Preemption을 허용하면 Atomic Instruction의 사용이 불가능해지기 때문에, Race Condition을 방지할 방법이 사라진다.

 

4. No Circular Wait

Total Ordering이라는 방식을 이용하여 그 방법을 구현할 수 있다. 우선순위에 의해 자원을 할당받도록 만드는 방법이다. 하지만, 이 방법 역시 불가능하다. 우선 순위가 낮은 프로세스를 먼저 실행시킬 수 없기 때문이다.

 

Deadlock Avoidance

아까 Safe와 Unsafe 상황에 대해 이야기 했었다. Deadlock Avoidance는 그래프를 검토하여 프로세스가 Unsafe 상태에 놓이지 않게 막는 방법이다.

 

Resource Allocation Graph Algorithm

Single instance of resource type일 때, 사용할 수 있는 알고리즘이다.

Request edge와 Assignment edge 외에 Claim edge라는 가상의 Request edge를 이용하여, Cycle의 형성 여부를 검사하여 Deadlock을 회피한다. Multiple instance인 경우에 사용할 수 없다는 한계가 있다.

 

Banker's Algorithm

Multiple instance of resource type에도 사용할 수 있는 알고리즘이다.

Resource Request Algorithm을 수행하여 가상으로 자원을 요청한 후, Safety Algorithm을 통해 safe 상태라 판별되면 실제로 자원을 요청한다.

 

가정

각 프로세스는 얼마나 자원을 사용할 것인지 정의되어 있다.

프로세스는 자원을 요청하는 동안 기다린다.

프로세스가 필요한 자원을 모두 얻으면 유한한 시간 내에 다시 돌려준다.

 

자료 구조

int n = number of processes
int m = number of resources types

Available[j] = k : k개의 instance를 가지는 resource type j

Max[i, j] = k : process i가 resource type j에게 얻을 수 있는 k개의 instance

Allocation[i, j] = k : i가 j에 대해 k개의 instance를 할당받고 있음

Need[i, j] = k : i가 작업을 완수하기 위해 k개의 instance가 더 필요함
// Need[i, j] = Max[i, j] - Allocation[i, j]

 

Resource Request Algorithm

가상으로 자원을 요청하는 알고리즘이다. 이 알고리즘을 수행한 후 Safety Algorithm을 통해 safe 상태임라고 판별되면 실제로 자원을 할당한다.

Request[i, j] = k : resource type j에서 k개의 인스턴스를 요구하는 프로세스 i

1.
if Request_i <= Need_i : 다음 단계로
else : 필요로 하는 자원의 양보다 요청하는 양이 많으므로, error 발생

2.
if Reqeust_i <= Available : 다음 단계로
else : 할당이 가능할 때까지 기다린다.

3.
Available = Available - Request[i] // Available에서 Request 만큼 차감
Allocation[i] += Request[i] // Allocation에 Request만큼 추가
Need[i] -= Request[i] // Need에 Request 한 만큼 차감

 

Safety Algorithm

safe/unsafe 상태를 판별하는 알고리즘이다.

1. 
int Work[m] = Available
bool Finish[n] = {false, false, ...}

2.
실행되지 않은 프로세스들 중 Need <= Work 인 프로세스를 찾는다.
만약에 없다면, 4번으로 넘어가 safe state인지 검사한다.

3. 
Need <= Work인 프로세스에 대해 
Work = Work + Allocation 하고 프로세스를 끝낸다.
다시 2번으로 돌아간다.

4.
모든 프로세스가 종료된 상태라면 safe 상태를 반환하고,
아니라면 unsafe 상태를 반환한다.

 

예시

다음은 P1 (1, 0, 2)를 Request하는 과정이다.

Request 전 상황

 

Safety algorithm까지 수행한 상황

 

Deadlock Ignorance

Deadlock Prevention, Avoidance와 같이 Deadlock의 발생을 원천 차단하는 방법도 있지만, Deadlock은 흔히 발생하지 않고 막기 위해 많은 자원이 사용되기 때문에 Ostrich Algorithm과 같이 Deadlock의 발생 가능성을 배제시키는 방법이 있다.

추가로 Deadlock Detection, Deadlock Recovery와 같이 Deadlock이 발생되었을 때 해결하는 방법 또한 있으니 알아보면 좋을 것 같다.