[Operating System] Deadlock

Deadlock

---

Deadlock

• deadlock의 정의
  • 각 프로세스가 다른 프로세스에서 무언가를 기다리고 있는 상황
  • 모두가 wait 상태이기 때문에, 아무도 기다리는 것을 제공해 줄 수 없다.

• deadlock example with semaphores
  

Deadlock Characterization

• Deadlock은 4가지 조건이 동시에 만족해야 deadlock이라고 할 수 있다.
  1. Mutual exclusion: 한 자원은 하나의 프로세스만 사용할 수 있다.
  2. No preemption: 일이 끝날 때까지 양보하지 않는다.
  3. Hold and wait: 적어도 하나의 자원을 가지고 있는 상태에서 다른 자원을 기다린다.
  4. Circular wait: 대기 순환

Deadlock: Resource-Allocation Graph

Deadlock Handling

• Deadlock을 해결하기 위한 방법은 두 가지로 나뉜다.
  1. Deadlock prevention/avoidance: deadlock 상황 자체를 막는다. -> 보수적인 자원 배분이 일어나 자원 사용성이 떨어질 수 있다.
  2. Deadlock detection and recovery: deadlock이 발생하면 복구한다. -> 사용성은 증가하지만 deadlock 발생에 따른 다른 피해가 생긴다.

Deadlock Prevention

---

Deadlock Prevention

• deadlock의 4가지 조건 중 하나라도 피하는 방법

  1. No mutual exclusion: 자원의 특성상 실현 불가능하다.
  2. Preemption: 실행 중인 자원을 억지로 끌어내리면 문제가 발생할 수 있다.
  3. No hold and wait: 확실히 가능할 때 hold 하는 방법이다. 그러나 확실히 가능한 상황을 예측하는 것은 어려우며, 예측에 자원이 낭비된다. -> Utilization 감소와 starvation 발생
  4. No circular wait: 줄줄이 wait 하는 상황을 끊는 방법이다. 획득하는 것에 순서를 지정하거나 계층구조로 설정하고, 모든 프로세스는 그 순서에 따른다.

• deadlock prevention을 완벽하게 하는 것은 어렵다.

Deadlock Avoidance

• 시스템에 몇 가지 추가 사전 정보가 있어야 한다.
  • available한 자원의 개수
  • 할당된 자원의 개수
  • 프로세스가 얼마나 요청할지

• deadlock-avoidance algorithm은 리소스 할당 상태를 동적으로 검사하여 cycle이 발생하지 않도록 한다.
  • 리소스 할당 상태는 available 자원 및 할당된 자원 수나 프로세스의 수요에 의해 결정된다.

Banker's Algorithm

• Terms
  • P = { P1, P2, ..., Pn } -> n개의 프로세스
  • R = { R1, R2, ..., Rm } -> m개의 resource 종류
• Safe state: deadlock이 발생하지 않는 상태
• Unsafe state: deadlock이 발생할 가능성이 있는 상태
  

• 각 프로세스는 사전에 얼마나 사용할지 결정하고 요구해야 한다.
• 프로세스가 바로 자원을 얻지 못해도 wait할 수 있는 환경이어야 한다.
• 프로세스가 모든 자원을 얻으면, 한정된 시간 내에 자원을 반환해야 한다

• Notation
  • n = 프로세스의 개수, m = 자원 타입의 개수
  • Available[1:m] : resource가 얼마나 남아 있는지
  • Max[1:n, 1:m] 프로세스가 최대 얼마를 요구했는지
  • Allocation[1:n, 1:m]: 현재 얼마나 할당되어 있는지
  • Need[1:n, 1:m]: 얼마나 남았는지
    • Max = Allocation + Need

• Safety Algorithm: 현재 state가 safe인지 판별하는 알고리즘
• Resource-Request Algorithm: 어떤 request가 들어왔을 때, 이것을 처리해도 safe가 유지되는지 확인

Banker's Algorithm - Safety Algorithm

• Example
  • 5개의 processes P0-P4
  • 3개의 자원: A (10 instance), B (5 instance), C (7 instance)

T0

• Safe sequence: <P1,
• P1이 현재 Available로 처리할 수 있음

T1

• Safe sequence: <P1, P3,
• P1은 finish가 되어 P1이 가지고 있던 자원들도 available로 들어간다.

...

T4

• Safe sequence: <P1, P3, P4, P2, P0>

• Safety Algorithm

1. Initialize Work[1:m] and Finish[1:n]
   Work = Available
   Finish[i] = false for i = 1, 2, …, n

2. Find an i such that both
   (a) Finish[i] = false
   (b) Needi <= Work
   If no such i exists, go to step 4

3. Work = Work + Allocationi
   Finish[i] = true
   Go to step 2

4. If Finish[i] = true for all i, then the system is in a safe state

Banker's Algorithm - Resource-Request Algorithm

• Example
  • 5개의 processes P0-P4
  • 3개의 자원: A (10 instance), B (5 instance), C (7 instance)

T1

• 여기에서 P0에 새로운 자원 (0, 2, 0) 할당
  
• Allocation에 (0, 2, 0)을 더하고, Need와 Available에는 (0, 2, 0)을 뺀다.
• 남은 Available로도 (0, 1, 1)해결할 수 있으므로, 여저니 safe state임을 알 수 있다.

• Resource-Request Algorithm for process Pi

Requesti = request for process Pi

    1. If Requesti <= Needi, go to step 2
    Otherwise, raise error condition (exceed maximum claim)
    
    2. If Requesti <= Available, go to step 3
    Otherwise, Pi must wait for the resource
    
    3. Pretend to allocate requested resources to Pi by modifying the state as follows
         Available = Available - Requesti
         Allocationi = Allocationi + Requesti
         Needi = Needi - Requesti
       If safe → the resources are allocated to Pi
       If unsafe → Pi must wait, and the old resource-allocation state is restored

Deadlock Detection

---

Deadlock Detection

• Deadlock Detection mechanisms의 한계
  • deadlock 상태를 방지하는 것은 비용이 많이 들거나 비효율적이다.
  • detection 또한 비용이 많이 들고, 복구가 거의 불가능하다.
  • 주어진 시간 내에 처리해야 하는 일에는 detection이 적합하지 않다.

• Single instance of each resource type (각각의 자원의 수가 1개인 경우) -> cycle이 존재한다는 것 자체가 deadlock 상태이다.
• Multiple instances of a resource type (각 자원의 수가 여러 개인 경우) -> Banker's algorithm과 비슷한 algorithm을 수행한다.

Deadlock Detection - Single Instance

• 주기적으로 사이클이 있는지 판단한다.
  • 만약 사이클이 존재한다면 -> deadlock으로 판단
• 알고리즘 수행 시간: $O(n^2)$
• single instance는 wait-for graph로 간단하게 나타낼 수 있다.
  

Deadlock Detection - Multiple Instance

• Banker's algorithm과의 차이점
  • Max값은 고려하지 않는다.

1. Initialize Work[1:m] and Finish[1:n]
   Work = Available
   Finish[i] = false, if Allocationi ≠ 0 // 점유한 자원이 없으면 finish로 간주한다.
               true, otherwise
               
2. Find an i such that both
   Finish[i] = false
   Requesti <= Work // Requesti = 요청했지만 할당받지 못한 자원의 수
   If no such i exists, go to step 4
   
3. Work = Work + Allocationi
   Finish[i] = true
   Go to step 2
   
4. If Finish[i] == false for some i, the system is in deadlock state and Pi is deadlocked 
// Finish[i[ == false가 존재하면, deadlock state이다.

• Example
  • 5개의 processes: P0~P4
  • 3개의 자원들: A (10 instance), B (2 instance), C (6 instance)

T0

• Request가 (0, 0, 0)인 게 있어야 한다.
  

• P0 처리 → Available: 0,1,0
• P2 처리 → Available: 3,1,3
• P3 처리 → Available: 5,2,4
• P1 처리 → Available: 7,2,4
• P4 처리 → Available: 7,2,6
• Sequence <P0, P2, P3, P1. P4>, FInish[i] = true (모든 i)

Deadlock Recovery

• Process Termination

  1. deadlock 상태인 모든 프로세스 중단
  2. deadlock 상태가 해소될 때까지 한 프로세스씩 중단한다.

     선택 기준

     • 프로세스의 우선순위
     • 프로세스가 계산한 시간 및 완료까지 남은 시간
     • 프로세스가 사용한 리소스
     • 프로세스가 완료하는 데 필요한 리소스
     • 종료해야 하는 프로세스 수
     • 다른 프로세스와 상호작용을 하는가?

• Resource preemption

  • 고려해야 할 사항

    • 희생 프로세스 선택 - 비용을 최소화하는 방향으로
    • rollback - safe state로 돌아가서 해당 상태의 프로세스를 다시 시작한다.
    • starvation - 항상 동일한 프로세스를 희생 프로세스로 선택할 수 있다.
    • 비용 요소에 rollback 횟수를 포함할 수 있다.