CH7. Deadlock

목차 정리

• Deadlock Problem의 정의

• Deadlock 발생의 조건 4가지

  • (1) Mutual exclusion
  • (2) No preemption
  • (3) Hold and wait
  • (4) Circular wait

• Resource-Allocation Graph를 통해 deadlock 확인하기
  

• Deadlock의 처리 방법

  1. Deadlock Prevention
  2. Deadlock Avoidance
     • Resource-Allocation Graph Algorithm
     • Banker's Algorithm
  3. Deadlock Detection and recovery
     • Detection:
       - Wait-For Graph Algorithm
       - Banker's Algorithm과 유사한 방법
     • Recovery:
       - Process termination
       - Resource Preemption
  4. Deadlock Ignorance

---

Deadlock Problem

일련의 프로세스들이 서로가 가진 자원(하드웨어, 소프트웨어)을 기다리며 block된 상태로, 교착상태라고도 한다.

프로세스가 자원을 사용하는 절차는 크게 4개의 단계로 나눠진다.
: Request, Allocate, Use, Release

Deadlock 발생의 조건 4가지

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

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

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

(4) Circular wait (순환대기)
자원을 기다리는 프로세스 간에 cycle이 형성되어야 한다.
프로세서 $P_0, P_1, ..., P_n$이 있을 때, $P_0$는 $P_1$이 가진 자원을 기다리고, $P_1$은 $P_2$가 가진 자원을 기다리고, ..., $P_n$은 $P_0$가 가진 자원을 기다리는 상황이다.

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

Resource-Allocation Graph(자원할당 그래프)를 통해서 deadlock 여부를 좀 더 빠르게 판별해볼 수 있다.

• 그래프에 cycle이 없으면 ⇒ deadlock이 아니다.
• 그래프에 cycle이 있으면
  • if only one instance per resource type, then deadlock
  • if several instances per resource type, then possibility of deadlock

위의 판별 기준을 가지고 아래의 두 가지 예시에 대해서 deadlock 여부를 판별해보자.

(좌) cycle이 존재하지만 $R_2$의 자원 개수가 2개 이상이다. 하지만 $R_2$를 사용하는 cycle의 개수가 2개이기 때문에 사실상 cycle 당 $R_2$의 자원 개수는 1개라고 볼 수 있다. 띠라서 deadlock이다.

(우) cycle이 존재하지만 cycle에 사용되는 자원($R_1, R_2$)의 개수가 2개 이상이다. 하지만 $R_1, R_2$를 사용하는 $P_2, P_4$는 cycle을 형성하지 않기 때문에 deadlock이 아니다.

Deadlock의 처리방법

1) Deadlock Prevention

자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 방법이다.

(1) Mutual Exclusion: 공유해서는 안되는 자원의 경우 반드시 성립해야 한다.

(2) No Preemption:
process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점된다.
모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
state를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용한다. (CPU, memory)

(3) Hold and wait:
프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 한다.

• 방법 1. 프로세스 시작 시 모든 필요한 자원을 할당 받게 하는 방법
• 방법 2. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청하는 방법
  

(4) Circular wait:
모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다.

예를 들어 순서가 3인 자원 $R_i$를 보유 중인 프로세스가 순서 1인 자원 $R_j$를 할당받기 위해서는 우선 $R_i$를 release해야 한다.

⇒ Utilization 저하, Throughput 감소, Starvation 문제가 발생할 수 있다.

2) Deadlock Avoidance

자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당하는 방법이다. 최악의 경우를 상정하고, 최악의 경우에 deadlock이 발생할 수 있다면 자원을 할당해주지 않는다.

가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다.

• Resoure type 당 single instance인 경우
  ⇒ 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
  ⇒ Resource-Allocation Graph Algorithm을 사용하여 state를 확인한다.

• Resource type 당 multiple instance인 경우
  ⇒ Banker's Algorithm 사용한다.

📍 [용어 정의]

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

safe sequence: 프로세스의 sequence $<P_1, P_2, ..., P_n>$이 safe하려면 $P_i (1 ≤ i ≤ n)$의 자원 요청이 "가용자원 + 모든 $P_j (j < i)$의 보유 자원"에 의해 충족되어야 한다.
조건을 만족하려면 다음 방법으로 모든 프로세스의 수행을 보장한다.

• $P_i$의 자원 요청이 즉시 충족될 수 없으면 모든 $P_j (j < i)$가 종료될 때까지 기다린다.
• $P_{i-1}$이 종료되면 Pi의 자원요청을 만족시켜 수행한다.

Resource-Allocation Graph Algorithm

request edge의 assignment edge 변경시 claim edge를 포함하여 cycle이 생기지 않은 경우에만 요청 자원을 할당한다.

위 그림의 경우 첫번째 그림에서는 claim edge였던 것이 request edge로 변하였고, 이후 자원이 할당되어 assignment edge로 바뀌었다. 이때 $P_1$에서 $R_2$로 향하는 claim edge로 인해 cycle이 형성되기 때문에 unsafe한 상태이므로 자원을 할당하지 않는다.

프로세스가 n개일 때 Resource-Allocation Graph Algorithm에서 cycle 생성 여부를 조사하는데 걸리는 시간은 $O(n^2)$이다.
(n개의 process에서 생성될 수 있는 edge의 개수는 n(n-2)개이기 때문이다)

Banker's Algorithm

• 가정
  • 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
  • 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
• 방법
  • 기본 개념: 자원 요청 시 safe 상태를 유지할 경우에만 할당한다.
  • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택한다. (그런 프로세스가 없으면 unsafe 상태)
  • 그런 프로세스가 있으면 그 프로세스에게 자원을 할당한다.
  • 모든 프로세스가 종료될 때까지 이러한 과정을 반복한다.

다음 그림은 Banker's Algorithm의 한 예시이다.

위에서 설명한 방법에 따라 보면, 먼저 총 요청 자원 수가 가용 자원의 수보다 적은 프로세스가 실행된다. Need에 총 요청 자원 수 - 할당된 자원 수가 계산되어있기 때문에 Need를 현재의 Available로 충족시킬 수 있는 프로세스를 선택한다.
⇒ $P_1, P_3$ 선택

$P_1$이 실행되면 $P_1$ 프로세스에 할당되었던 자원이 반납될 것이다. 그러면 Available이 5,3,2가 되고, 또 다시 Need를 새로운 Available로 충족시킬 수 있는 프로세스를 선택한다.
⇒ $P_4$ 선택

$P_3$가 실행된 후 할당되었던 자원이 반납되면, 새로운 Available은 7,4,3이 된다.
⇒ $P_2$ 선택

$P_4$가 실행된 후 할당되었던 자원이 반납되면, 새로운 Available은 7,4,5가 된다.
⇒ $P_0$ 선택

결과적으로 sequence $<P_1, P_3, P_4, P_2, P_0>$가 존재하므로 시스템은 safe state이다.

3) Deadlock Detection and recovery

Deadlock 발생은 허용하되 그에 대한 detection routine을 두어 deadlock 발견 시 recover하는 방법이다.

[ Deadlock Detection ]

먼저 Deadlock을 detect하는 방법으로는 2가지 방법이 있다.

• Resoure type 당 single instance인 경우
  ⇒ 자원 할당 그래프에서의 cycle이 곧 deadlock을 의미한다.
  ⇒ Wait-For Graph Algorithm을 이용하여 cycle을 확인한다.

• Resource type 당 multiple instance인 경우
  ⇒ Banker's Algorithm과 유사한 방법 활용한다.

Wait-For Graph Algorithm

Resource 당 single instance인 경우에 사용한다. Wait-For Graph에 사이클 존재 여부를 주기적으로 조사하고 이때 시간복잡도는 $O(n^2)$이다.

📍 Wait-For Graph
Resource-Allocation Graph (자원할당 그래프)를 변형한 것 프로세스만으로 node를 구성한다. 따라서 $P_j$가 가지고 있는 자원을 $P_k$가 기다리는 경우를 $P_k → P_j$로 표현한다.

아래 그림은 같은 상황을 각각 Resource-Allocation Graph와 Wait-For Graph로 나타낸 것이다. Resource-Allocation Graph에서 Resource를 제거하면 Wait-For Graph가 됨을 알 수 있다.

Banker's Algorithm과 유사한 방법

Resource type 당 multiple instance인 경우에 사용하는 방법이다.

위의 그림과 같은 상황을 Banker's Algorithm과 유사한 방법으로 살펴보며 state가 safe/unsafe인지 알아보자.

프로세스의 자원 최대 사용량을 기준으로 프로세스를 선택한 Banker's Algorithm과 달리, 여기서는 프로세스의 자원 최대 사용량을 알 필요가 없다.

현재 실제로 요청한 자원량인 Request를 현재 이용가능한 자원 (Available)로 할당할 수 있으면 프로세스를 선택한다.

현재 Available은 0,0,0이기 때문에 Request가 0,0,0인 프로세스만 선택할 수 있다
⇒ $P_0, P_2$ 선택

$P_0$가 실행된 후 할당되었던 자원이 반납되면, 새로운 Available은 0,1,0이 된다.
⇒ 아무것도 선택 못함

$P_2$가 실행된 후 할당되었던 자원이 반납되면, 새로운 Available은 3,1,3이 된다.
⇒ $P_1, P_3, P_4$ 선택

결과적으로 sequence $<P_0, P_2, P_1, P_3, P_4>$가 존재하므로 시스템은 safe state이다.

safe sequence가 존재하지 않는 unsafe state인 경우도 살펴보자.

현재 Available은 0,0,0이기 때문에 Request가 0,0,0인 프로세스만 선택할 수 있다
⇒ $P_0$ 선택

$P_0$가 실행된 후 할당되었던 자원이 반납되면, 새로운 Available은 0,1,0이 된다.
⇒ 아무것도 선택 못함

이 상태에서 더 이상 프로세스를 선택하지 못하기 때문에 safe sequence가 존재하지 않는다. 따라서 unsafe state이고 deadlock이 발생한다.

이처럼 deadllock이 발생하면 다음 2가지 방법을 사용하여 recovery를 진행한다.

[ Deadlock Recovery ]

• Process termination

  • 모든 deadlock 프로세스를 종료한다.
  • deadlock cycle이 없어질 때까지 프로세스를 하나씩 종료한다.

• Resource Preemption

  • 비용을 최소화할 victim을 선정한다.
  • safe state로 rollback하여 process를 재시작한다.
  • starvation 문제가 발생할 수 있다.
    • 동일한 프로세스가 계속해서 victim으로 선정되는 경우에 발생할 수 있다.
    • cost factor에 rollback 횟수도 같이 고려하여 starvation 문제를 해결할 수 있다.

4) Deadlock Ignorance

Deadlock을 시스템이 책임지지 않는 방식으로, UNIX, Windows를 포함한 대부분의 OS가 채택하는 방법이다.

Deadlock이 매우 드물게 발생하므로 deadlock에 대한 예방/조치가 더 큰 overhead일 수 있다.

시스템에 deadlock이 발생한 경우, 사용자가 직접 process를 죽이는 등의 방법으로 대처한다.