[OS] Deadlock은 무엇인가? 해결 방법은? - Prevention, Avoidance

Deadlock이란 ??

Deadlock은 두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 말한다.

Deadlock은 왜 일어날까 ❔❔

Deadlock은 critical section의 기본조건인 progress를 보장하지 못해 발생하는 문제이다.

Critical section의 기본 조건

1. Mutual Exclusion

어떤 프로세스가 Critical section을 실행 중이라면, 다른 프로세스는 Critical section을 실행할 수 없다!

2. Progress

어떠한 프로세스도 critical section을 실행하지 않고, critical section을 실행하려는 프로세스가 있다면, 다음 critical section을 실행하는 프로세스가 무기한 연기되어선 안 된다!

👉 deadlock 방지

3. Bounded Waiting

각 프로세스는 유한한 횟수의 시도 후에 critical section에 들어갈 수 있어야 한다.

👉 starvation 방지

Deadlock이 발생하는 예시 - Semaphores

interrupt로 인해 A1 → B1 → A2 → B2 순서로 실행되게 된다면,
P1은 R1를 점유하면서 R2를 점유하길 원하고
P2는 R2를 점유하면서 R2를 점유하길 원한다.

👉 이를 deadlock(교착상태)라고 말한다.

deadlock이 발생하는 조건은 무엇이 있을까 ❔❔

deadlock이 발생하기 위해서는 4가지 조건이 반드시 동시에 충족해야 한다.

1. Mutual Exclusion

한 번에 오직 한 프로세스만이 리소스 인스턴스를 사용한다.

2. Hold and Wait

하나 이상의 리소스를 점유하고 있는 프로세스가 다른 프로세스가 점유하고 있는 리소스를 획득하기 위해 기다린다.

3. No Preemption

리소스는 해당 리소스를 점유하는 프로세스가 사용을 완료한 뒤 자발적으로 반납할 때만 릴리즈될 수 있다.

다른 프로세스가 점유하고 있는 리소스를 강제로 빼앗을 수 없다.

4. Circular Wait

각 프로세스가 순환적으로 다음 프로세스가 요구하는 리소스를 가지고 있는 것

deadlock을 해결하기 위한 방법이 무엇이 있을까 ❔❔

Deadlock Prevention(예방)

deadlock 발생 조건 4가지 중 하나 이상의 조건이 충족되지 않도록 하는 방법

 

Deadlock Avoidance(회피)

deadlock의 발생 가능성을 인정하고 deadlock의 발생 가능성을 피해 가는 방법 (Resource Allocation Graph algorithm, Banker's algorithm)

 

Deadlock Recovery(복구)

deadlock이 발생하면 이를 해결하는 방법

 

Deadlock Ignorance(무시)

deadlock을 해결하기 위해서는 그만큼의 overhead가 발생하기 때문에 deadlock으로 인한 성능 저하보다 deadlock 해결로 인한 성능 저하가 클 경우 deadlock을 무시하는 방법

 

Deadlock Prevention

deadlock 발생 조건 4가지 중 하나 이상의 조건이 충족되지 않도록 한다.

1. Mutual Exclusion ❌

모든 리소스가 동시에 공유 가능하도록 만든다.

👉 read-only 파일처럼 동시 접근 가능한 리소스는 상관없지만 mutex lock이나 printer와 같이 동시 접근이 불가능한 리소스를 동시에 공유 가능하도록 만들 순 없다. why? race condition이 발생하기 때문!!

2. Hold and Wait ❌

프로세스가 리소스를 요청할 때, 어떠한 리소스를 점유하지 않도록 보장한다.

Total Allocation

프로세스가 실행하기 이전에 요청할 모든 리소스를 할당 받고 실행한다.

예를 들어, 어떤 프로세스가 USB에 담긴 파일을 디스크에 있는 파일로 복사하고 이를 프린터로 복사하는 task를 가지고 있다고 가정해보자. 이 프로세스는 USB, 디스크, 프린터 이 3개의 리소스를 실행하기 전에 점유하고 task가 끝날 때 이 리소스들을 반납할 수 있다.

👉 Resource Utilization (자원 활용도)가 너무 낮아진다.

3. Preemption ⭕️

리소스를 점유하고 있는 프로세스로부터 리소스를 강제로 빼앗는 것을 허락한다.

👉 state(상태)를 쉽게 저장하고 불러올 수 있는 리소스의 경우 가능하다. 예를 들어, CPU의 경우 context switch를 통해 프로세스의 상태를 쉽게 저장하고 불러올 수 있기 때문에 Preemtion 가능하다.

👉 하지만 대부분의 리소스의 경우 상태를 저장하는 것이 불가능하다. 리소스가 Preemtion될 경우 race condition이 발생할 수 있다.

4. Circular Wait ❌

모든 리소스에 고유한 번호를 할당하고 각 프로세스는 오름차순으로 리소스를 요청한다.

👉 항상 고유한 순서로 리소스를 요청할 수 없는 문제가 발생한다.

요약하면 대부분의 경우에서 현실적으로 불가능하고, 가능하다 할지라도 자원 활용도가 낮아지는 문제가 발생한다.

 

Deadlock Avoidance

deadlock 발생가능성을 계속 검사하고, 발생가능성이 있다면 회피하는 방법을 사용한다.Safe, Unsafe 개념을 사용함.

Safe: deadlock이 발생하지 않는 상태

Unsafe: deadlock 발생 가능성이 있는 상태 (100% 발생하는 것이 아님)

Algorithm

- 리소스가 단일 인스턴스일 경우: Resource Allocation Graph Algorithm

- 리소스가 다중 인스턴스일 경우: Banker's Algorithm

Resource Allocation Algorithm

Claim edge Pi → Rj: Pi가 미래에 Rj를 요청할 수 있다는 것을 의미함. 점선으로 표시.

Request edge Rj → Pi: Rj가 Pi에게 할당된 것을 의미함. 실선으로 표시.

Resource Allocation Algorithm은 Claim edge와 Request edge를 포함하여 cycle이 발생하는지의 여부를 파악한다.

👉 cycle이 발생할 경우: Unsafe state!!!

R2가 P1에게 할당된다면 ❔❔ Safe state!!!

R2가 P2에게 할당된다면 ❔❔ Unsafe state!!!

👉 R2는 P1에게 먼저 할당된 후 P1이 R2를 반납한 뒤 P2에게 할당되면 시스템은 안전한 상태를 보장할 수 있다.

Banker's Algorithm

가정

1. 각 프로세스는 리소스의 최대 사용량을 사전에 주장한다.

2. 프로세스가 리소스를 요청할 때, 기다려야 할 수 있다.

3. 프로세스가 모든 리소스를 얻으면 유한한 시간 내에 리소스를 반납해야 한다.

 

알고리즘

- Safety Algorithm: 현재 상태가 safe한지 판단하는 알고리즘

- Resource-Request Algorithm: 리소스 요청 이후 상태가 safe한지 판단하는 알고리즘

 

자료구조

N: 프로세스 수, M: 리소스 타입 수

Available: 길이 M의 벡터

Available[j] = k // 리소스 Rj의 인스턴스 중 k개 이용가능하다.

Max: N×M 행렬

Max[i, j] = k // 프로세스 Pi가 리소스 Rj를 최대 k개까지 요청할 수 있다.

Allocation: N×M 행렬

Allocation[i, j] = k // 프로세스 Pi가 현재 리소스 Rj의 인스턴스 중 k개를 할당받았다.

Need: N×M 행렬

Need[i, j] = k // 프로세스 Pi가 리소스 Rj를 k개 더 필요로 한다.
Need[i, j] = Max[i, j] - Allocation[i, j]

Safety Algorithm

Safety Algorithm은 현재 상태가 safe한지 판단하는 알고리즘이다.

 

Pseudocode

// 1. Work와 Finish는 각각 m, n 길이의 vector이다.
Work = Available
Finish[i] = false for i = 0, 1, 2, ..., n-1

// 2. 아래 조건을 충족하는 i(0 ~ n-1)를 찾는다.
Finish[i] == false && Need[i, j] <= Work[j] for j = 0, 1, 2, ..., m-1
// 조건에 충족하지 않다면 4번으로 넘어간다.

// 3. 아래와 같이 값을 할당하고 다시 2번으로 돌아간다.
Work[j] = Work[j] + Allocation[i, j] for j = 0, 1, 2, ..., m-1

// 4. 모든 i에 대해 아래 조건이 충족한다면, 이 시스템은 safe state를 가진다.
Finish[i] == true for i = 0, 1, 2, ..., n-1

예시

아래와 같은 상황을 가정해보자.

P0는 현재 Available(3, 3, 2)보다 더 많은 리소스(7, 4, 3)을 요구하기 때문에 2번 조건에 부합하지 않는다.
P1은 Finish가 false가 아니고, Need가 Available보다 작기 때문에 2번 조건에 부합하여 3번 로직을 수행한다.

P2는 현재 Available(5, 3, 2)보다 더 많은 리소스(6, 0, 0)을 요구하기 때문에 2번 조건에 부합하지 않는다.

P3가 2번 조건에 해당하므로, task를 완료하고 3번 로직을 수행한다.

위와 같이 <P1, P3, P4, P0, P2> safe sequence를 찾을 수 있다. (safe sequence는 여러 조합이 나올 수 있다.)

Resource-Request Algorithm

Resource-Request Algorithm은 특정 프로세스가 리소스를 요청한 이후에도 safe state를 가지는지 확인하는 알고리즘이다.

 

자료구조

Request: 길이 M의 벡터

Request[i, j] = k // 프로세스 Pi가 리소스 Rj를 k개 인스턴스만큼 요청한다.

 

Pseudocode

// 1. 아래 조건에 부합하다면 계속 진행한다.
// 조건에 부합하지 않으면, 해당 프로세스가 초기 주장한 최대 사용량을 초과하기 때문에 에러를 발생한다. (가정 1)
Request[i, j] <= Need[i, j] for j = 0, 1, 2, ..., m-1

// 2. 아래 조건이 부합하다면 계속 진행한다.
// 조건에 부합하지 않으면, 해당 프로세스는 요청한 리소스가 이용가능하지 않기 때문에 기다려야 한다.(가정 2)
Request[i, j] <= Available[j] for j = 0, 1, 2, ..., m-1

// 3. 해당 프로세스가 요청한 리소스를 할당한다고 가정하고 아래와 같이 상태를 변경한다.
Available[j] = Available[j] - Request[i, j] for j = 0, 1, 2, ..., m-1
Allocation[i, j] = Allocation[i, j] + Requset[i, j] for j = 0, 1, 2, ..., m-1
Need[i, j] = Need[i, j] - Request[i, j] for j = 0, 1, 2, ..., m-1

// safe -> 프로세스 Pi에게 리소스를 할당한다.
// unsafe -> 프로세스 Pi는 기다려야 한다.

예시

다음과 같은 상황에서 P1이 리소스 (1, 0, 2)를 요청한다고 가정해보자.

이와 같이 상태가 바뀌고, Safety Algorithm을 수행하여 이 상태가 safe하다면 리소스를 할당한다.

 

Deadlock Avoidance는 request할 때마다 safety algorithm을 돌려야 한다.

deadlock이 자주 발생하는 것이 아니기 때문에 비효율적이다.