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

이번 포스팅은 이전에 다뤘던 deadlock 해결방법 포스팅에 이어 Deadlock Recovery에 대해서 알아보자~

Deadlock Detection

deadlock 방지를 위한 사전 작업을 하지 않기 때문에 deadlock이 발생할 수 있다.

주기적으로 deadlock이 발생하는지 확인해야 한다.

👉 이를 확인하기 위해 Resource Allocation Graph(RAG)를 사용한다.

Resource Allocation Graph (RAG)

deadlock detection을 위해 사용한다.

directed(방향성을 가지고), bipatite(이분) graph를 사용한다.

 

용어

그래프 G = (N,E), N = {Np, Nr} 

Np는 프로세스의 집합 = {P1, P2, ..., Pn}

Nr는 리소스의 집합 = {R1, R2, ..., Rm}

Edge는 Np 와 Nr 사이에만 존재

e = (Pi , Rj) : 자원 요청

e = (Rj , Pi) : 자원 할당

 

Rk : k type의 자원

tk : Rk의 단위 자원 수

|(a,b)| : (a,b) edge의 수

 

예시

어떻게 RAG를 사용해서 Deadlock을 Detection할 수 있을까 ❔❔

👉 Graph Reduction!!!

Graph Reduction

주어진 RAG에서 edge를 하나씩 지워감으로써 deadlock인지 아닌지 판단할 수 있다!

 

어떻게 deadlock을 판단할 수 있을까 ❔❔

Complete reduced → 모든 edge가 제거 되었다면 deadlock이 아니다!

Irreducible → 지울 수 없는 edge가 존재한다면 deadlock이다!

 

edge를 어떤 방법으로 지우나 ❔❔

Unblocked process에 연결된 edge를 다 지운다. 

→ 요청한 리소스를 모두 할당 받을 수 있는 프로세스

예시1 - deadlock free

예시1 - deadlock

결론 ❕❕❕

Graph Reduction은 높은 overhead를 가진다.

why? 주기적으로 검사를 해줘야 하기 때문에 검사 주기에 영향을 받고, Node 수가 많을 경우 overhead가 커진다.

Deadlock Avoidance vs Detection'

Deadlock Avoidance

deadlock이 일어날 경우를 고려하여 회피하기 때문에 deadlock이 발생하지 않음

Deadlock Detection

현재 상태에서 deadlock이 발생하는가를 파악하기 때문에 deadlock이 발생할 수 있음

👉 deadlock 발생 시 Recovery 과정이 필요하다~

 

Deadlock Recovery

Deadlock Detection 이후 deadlock을 해결하는 과정을 말한다.

Deadlock Recovery 방법으로는 Process Termination과 Resource Preemption이 있다.

 

Process Termination

deadlock 상태에 있는 프로세스 중 일부를 종료시킨다.

강제 종료된 프로세스는 이후 처음부터 재시작된다.

 

여러 개의 프로세스가 deadlock 상태에 있으면 누굴 종료시킬까 ❔❔

👉 Termination cost model을 사용한다.

Termination cost

- 우선순위 (Process priority)

- 종류 (Process type)

- 총 수행 시간 (Accumulated execution time of the process)

- 남은 수행 시간 (Remaining time of the process)

- 종료 비용 (Accounting cost)

- Etc..

Process Termination 방법

Lowest-termination cost process first

cost model이 정해지면 아주 간단한 방법!

O(n) 안에 찾을 수 있기 때문에 overhead가 낮다.

BUT 불필요한 프로세스가 종료될 가능성이 있음

 

Minimum cost recovery

최소 비용으로 deadlock 상태를 해결할 수 있는 process를 선택한다. → 최고의 선택

BUT 모든 경우의 수를 고려해야 하기 때문에 복잡하고 O(2^k)의 시간복잡도를 가진다.

Resource Preemption

deadlock 상태를 해결하기 위해 선점할 리소스를 선택한다.

선정된 자원을 점유하고 있는 프로세스에게 자원을 빼앗고, 빼앗긴 프로세스는 강제 종료되어 처음부터 재시작된다.

deadlock 상태가 아닌 프로세스가 종료될 수 있다.

 

어떤 리소스를 선점할까 ❔❔

👉 Preemption cost model이 필요하다.

Minimum cost recovery

를 사용함

Checkpoint-Restart

Process termination과 Resource preemention을 통해 프로세스가 강제 종료되고 재시작을 해야 한다.매번 처음부터 재시작하는 것은 비효율적이기 때문에 특정 시점(checkpoint)마다 context를 저장한다.이를 통해 프로세스가 강제 종료되었다면, 가장 최근의 checkpoint에서 재시작할 수 있다.

---

참고

https://www.youtube.com/watch?v=8XbSgZ2JPQ8&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=24