Chapter 8. Deadlocks

Outline

---

① The Deadlock Problem

② System Model

③ Deadlock Characterization

④ Resource Allocation Graph

⑤ Methods for Handling Deadlocks

⑥ Deadlock Prevention

⑦ Deadlock Avoidance

⑧ Deadlock Detection

⑨ Recovery from Deadlock

 

① The Deadlock Problem

---

● Bridge Crossing Example

1. 자동차를 강에 던지기

  -> kill the process

 

2. 차를 후진하기

  -> preempt the resource and rollback

 

3. 1차선 도로에 이미 자동차가 존재할 경우 데드락 발생이 예상되므로 safe state까지 진입하지 않고 대기

  -> deadlock avoidance

 

4. 1차선 도로에 자동차 두대가 진입했을 경우 데드락이 탐지됨

  -> deadlock detection

 

 

● 방지 및 대처

1. Deadlock detection

2. Deadlock avoidance

3. Deadlock recovery

4. Deadlock prevention

② System Model

---

③ Deadlock Characterization

---

● 데드락의 필요 조건

1. Mutual exclusion

  -> 한 번에 하나의 프로세스만 리소스 사용 가능.

  -> 리소스를 여러 프로세스가 동시에 접근 가능하면 데드락 발생하지 않음.

 

2. Hold and wait

  -> 리소스를 가지고 있는 프로세스가 리소스 추가 요청

 

3. No preemption 

  -> 리소스가 사용 중일 때 다른 프로세스가 리소스를 가로채서 사용하는 것(preemption)을 허용 안함.

  -> Preemption이 된다면 두 개의 프로세스가 리소스를 번갈아가면서 사용할 수 있으므로 데드락 발생하지 않음.

 

4. Circular wait

  -> p1 → p2

  -> p2 → p3

  -> ...

  -> pn → p1

 

※ 4가지 필요조건이 모두 만족하더라도 데드락이 무조건 발생하는 것은 아님.

④ Resource Allocation Graph

---

리소스가 프로세스에게 어떻게 할당되는지를 그래프 형태로 나타냄

Deadlock Detection

 

1. request edge

  -> 프로세스 → 리소스

  -> Pi → Rj

 

2. assignment edge

  -> 리소스 → 프로세스

  -> Ri → Pj

 

● 예시

 

● 데드락 발생하는경우

1. 사이클 (x)

  -> 발생 (x)

 

2. 사이클 (o)

  1) resource의 instance 1개: 발생 (o)

  2) resource의 instance 여러 개: 발생 가능성 있음

 

● 사이클 (O) 데드락 (O)

● 사이클 (O) 데드락 (X)

012

 

⑤ Methods for Handling Deadlocks

---

● 교착상태 처리방법

1. 시스템이 deadlock 되지 않도록 보장하기

  -> prevention, avoidance

 

2. 시스템이 deadlock 상태가 되는 것을 허용하되 원상복구하기

  -> detection, recovery

 

3. deadlock이 발생하지 않은 것처럼 무시하기

  -> 대부분 OS에서 이 방식 사용 (UNIX 포함)

 

⑥ Deadlock Prevention

---

● 발생조건 4가지 중 하나 제거

-> infeasible 또는 side effect

 

1. Mutual exclusion -> "infeasible"

근본적으로 공유 불가능한 resource 존재 (ex. 프린터, mutex 등)

 

2. Hold and wait -> "side effect"

프로세스가 자원을 요청할 때 다른 자원을 가지고 있으면 안됨

  1) 실행하기 전에 모든 자원을 할당 받을 경우

    -> Low resource utilization, starvation

  2) 리소스를 소유하지 않았을 때만 request를 허용: resource 효율이 저하됨 

    -> Low resource utilization

 

3. No preemption -> "almost infeasible"

CPU는 preemption 가능하지만 printer 같은 대부분의 resource은 preemption 불가

 

4. Circular wait -> "side effect"

모든 resource type에 Total ordering 설정

  -> 리소스 효율이 저하됨 (동시에 리소스를 활용할 수 없음)

⑦ Deadlock Avoidance

---

1. single instance

-> resource allocation graph

 

2. multiple instance

-> 그래프 만으로는 확인 불가

-> banker's algorithm

 

● Single instance

01

● Multiple instance

목표

시스템이 절대 unsafe state가 되지 않도록 보장

 

sate state = allocated + demand ≤ available

● Banker's Algorithm

각 프로세스는 최대 자원 요구량을 선언해야 함

 

1. Available   : 길이 m인 vector  (사용 가능한 instance 수)

2. Max         :  n x m 행렬        (최대 요구 instance 수)

3. Allocation :  n x m 행렬        (최대 요구 instance 수)

4. Need       :  n x m 행렬        (최대 요구 instance 수)

 

⑧ Deadlock Detection

---

Deadlock avoidance와 유사

1. single instance

-> corresponding wait-for graph

-> 리소스 제거, 프로세스만 표시

 

2. multiple instance

-> banker's algorithm 변형

-> need를 current real request로 바꿈

⑨ Recovery from Deadlock

---

deadlock 발생 시 후속조치

 

1. Process Termination (kill processes)

  1) deadlock 된 프로세스 모두 종료

  2) cycle 제거될 때까지 한 번에 하나씩 종료

 

2. Check point & Roll back 

  1) selecting a victim

  2) Roll back

    -> 가장 근접한 check point로 이동

    -> safe state로 돌아가서 재시작 (Process Control Block의 Program Counter 정보 이용)

 

 

요약

1. prevention

4개 중 하나 제거

  - mutual exclusion

  - no preemption

  - hold & wait

  - circular wait

 

2. avoidance

  - single: Resource Allocation graph

  - multiple: Banker's Algorithm

 

3. detection

  - single: corresponding wait-for graph

  - multiple: Banker's Algorithm 변형

 

4. recovery

  - kill processes

  - roll back