[운영체제] 7. Deadlocks

Deadlock Problem

1) Deadlock : 일련의 프로세스들이 서로가 가진 SW/HW 자원을 기다리며 block된 상태

2) Resource : HW, SW 등을 포함하는 개념

- I/O device, CPU cycle, memory space, semaphore 등

- 자원 사용 절차 : Request(요청) > Allocate(할당) > Use(사용) > Release(반납)

 

Deadlock이 발생하는 4가지 조건🔥

1) Mutual Exclusion(상호 배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있음

2) No preemption(비선점) : 프로세스는 자원을 스스로 내어놓을 뿐, 강제로 빼앗기지 않음

3) Hold and wait(보유대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때, 보유 자원을 놓지 않고 계속 가지고 있을 수 있음

4) Circular wait(순환대기) : 자원을 기다리는 프로세스 간에 사이클이 형성되어야 함

 

Resource-Allocation graph(자원할당그래프)

프로세스->자원 : 프로세스가 자원을 요청하였고, 아직 자원 얻지 못함

자원->프로세스 : 자원이 해당 프로세스에게 할당됨

 

* 그래프에 cycle이 없으면 deadlock이 아니다!

* 그래프에 cycle이 있으면 

1) 자원 당 인스턴스가 하나밖에 없으면, 무조건 deadlock

2) 자원 당 인스턴스가 여러 개 있으면, deadlock일 수 있음!

(좌) deadlock, (우) cycle이 있지만 not deadlock

 

Deadlock의 처리 방법

1) 사전 방지

(1) Deadlock Prevention : 자원 할당 시 deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것

(2) Deadlock Avoidance : deadlock의 가능성이 없는 경우에만 자원을 할당(시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당)

 

2) Deadlock Detection & Recovery

3) Deadlock Ignorance : deadlock을 시스템이 책임지지 않음, 대부분의 OS가 채택

* deadlock은 자주 일어나는 이벤트가 아니기 때문에 대비하는 것 자체가 large overhead

 

1. Deadlock Prevention

사전에 모든 deadlock을 방지하기 때문에 utilization 저하, throughput 감소, starvation 문제 발생 가능

1) Mutual Exclusion(상호 배제) : 공유해서는 안되는 자원의 경우 반드시 성립해야 함 (그러나 실제로는 성립하기 어려움)

2) Hold and wait(보유대기)  : 프로세스는 자원을 요청할 때 다른 자원도 가지고 있지 않아야 한다

- 프로세스 시작 시 필요한 모든 자원을 할당받는 방법 - 자원이 낭비될 수 있음

- 자원이 필요할 경우 보유한 자원을 모두 놓어두고 다시 요청(자진반납)

3) No preemption(비선점) : process가 대기상태인 경우 보유한 자원 뺏길 수 있음(강제)

- 사용 상태를 쉽게 save & restore할 수 있는 자원에서 주로 사용(CPU, memory)

4) Circular wait(순환대기) : 모든 자원 유형에 할당 순서를 정하여 순서대로 자원 할당

 

2. Deadlock Avoidance

항상 safe state를 유지

프로세스가 시작될 때, 필요로 하는 각 자원의 최대 사용량을 미리 선언하도록 함

 

* safe state : 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

* safe sequence : 프로세스의 자원 요청이 <가용 자원 + 모든 프로세스의 보유 자원>에 의해 충족되어야 함

항상 safe state를 유지함

 

1) 자원 당 인스턴스가 하나인 경우 : Resource Allocation Graph 사용

2) 자원 당 인스턴스가 여러 개인 경우 : Banker's Algorithm 사용

 

(1) Resource Allocation Graph Algorithm

최악의 상황을 가정 - 가능한 자원이 있다고 해서 다 내어주지 않는다

실선 : 프로세스가 해당 자원을 요청했다.

점선 : 프로세스가 해당 자원을 요청할 일이 있다

Process 2번이 Resource 2번을 요청한 경우 -> 점선을 포함한 사이클이 발생한다(not deadlock)

 

(2) Banker's Algorithm

Need가 Available로 충족이 되는 경우 자원을 할당

- Allocation : 프로세스에게 할당된 자원량

- Max : 프로세스가 필요로 하는 자원의 최대 사용량

- Available : 가용 자원량

- Need : 추가 요청 가능량

 

P1이 need 만족 -> P1 종료하면서 allocation + need 반환 (available 증가)

-> P3이 need 만족 -> P3 종료하면서 allocation + need 반환 (available 증가) ...

 

3. Deadlock Detection & Recovery

[ Deadlock Detection ]

1) 자원 당 인스턴스가 하나인 경우 : Resource Allocation Graph / Wait-for graph 사용

- wait-for graph : 프로세스만으로 node를 구성한다

- 프로세스가 n개 있는 경우, 각 프로세스에 대한 화살표는 최대 (n-1)개 존재할 수 있다 - 탐색 시간 O(n^2)

자원을 제거하고 프로세스끼리의 관계만 그림

 

2) 자원 당 인스턴스가 여러 개인 경우 : Banker's Algorithm 사용

- Allocation : 프로세스에게 할당된 자원량

- Request : 현재 프로세스가 요청한 자원량

- Available : 가용 자원량

 

* 낙관적 가정 : 현재 Request가 0인 경우, Allocation을 반납할 것이라고 가정

 

1) 현재 Request가 0인 경우 가용 자원에 해당 프로세스의 자원 포함

2) 가용 자원으로 Request 처리할 수 있는 경우가 있는지 확인 

- 모든 Request를 처리할 수 없다면 deadlock 발생

deadlock 발생

 

[ Deadlock Recovery ]

1) Process Termination(프로세스 종료)

- deadlock에 연루된 모든 프로세스를 abort

- deadlock이 없어질 때까지 deadlock에 연루된 모든 프로세스를 하나씩 abort해봄

 

2) Resource Preemption(자원 뺏기)

- 비용을 최소화할 victim을 선정 - safe state로 rollback하여 프로세스 restart

- starvation 문제 : 동일한 프로세스가 계속해서 victim으로 선정되는 경우 - rollback 횟수도 함께 고려해야 한다

 

4. Deadlock Ignorance

Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않는 방법

Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음