📌 Deadlock

📖 Deadlock의 개념

• Blocked / Asleep state
  - 프로세스가 특정 이벤트를 기다리는 상태
  - ㅍ로세스가 필요한 자원을 기다리는 상태

• Deadlock state
  - 프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
  -> 프로세스가 deadlock 상태에 있음

  - 시스템 내에 deadlock에 빠진 프로세스가 있는 경우
  -> 시스템이 deadlock 상태에 있음
  

- Deadlock vs Starvation

Deadlock은 모든 프로세스가 리소스를 보유하고 다른 프로세스가 보유한 리소스를 얻기 위해 대기할 때 발생
반대로 프로세스가 필요한 리소스를 무한정 기다릴 때 Starvation이 발생

---

📖 자원의 분류

• 일반적 분류
  - HW resources vs SW resources

• 다른 분류법
  - 선점 가능 여부에 따른 분류
  - 할당 단위에 따른 분류
  - 동시 사용 가능 여부에 따른 분류
  - 재사용 가능 여부에 따른 분류

1. 선점 가능 여부에 따른 분류

• Preemptible resources
  - 선점 당한 후, 돌아와도 문제가 발생하지 않는 자원
  - Processor, memory 등

• Non-preemptible resources
  - 선점 당하면, 이후 진행에 문제가 발생하는 자원
  (Rollback, restart 등) 특별한 동작이 필요
  - E.g., disk drive 등

2. 할당 단위에 따른 분류

• Total allocation resources
  - 자원 전체를 프로세스에게 할당
  - E.g., Processor, disk drive 등

• Partitioned allocation resources
  - 하나의 자원을 여러 조각으로 나누어, 여러 프로세스들에게 할당
  - E.g., memory 등

3. 동시 사용 가능 여부에 따른 분류

• Exclusive allocation resources
  - 한 순간에 한 프로세스만 사용 가능한 자원
  - E.g., Processor, memory, disk drive 등

• Shared allocation resource
  - 여러 프로세스가 동시에 사용 가능한 자원
  - E.g., Program(SW) 또는 일종의 Source Code, shared date 등

4. 재사용 가능 여부에 따른 분류

• SR (Serially-reusable Resources)
  - 시스템 내에 항상 존재하는 자원
  - 사용이 끝나면 다른 프로세스가 사용 가능
  - E.g., Processor, memory, disk drive, program 등

• CR (Consumalbe Resources)
  - 한 프로세스가 사용한 후에 사라지는 자원
  - E.g., signal, message 등
  

---

📖 Deadlock과 자원의 종류

• Deadlock을 발생시킬 수 있는 자원의 형태
  - Non-preemptible resources
  - Exclusive allocation resources
  - SR (Serially reusable resources)
  - 할당 단위는 영향을 미치지 않음
  - CR을 대상으로하는 Deadlock model도 존재하지만 너무 복잡함

📖 Deadlock 발생의 예

• 2개의 프로세스 (P1, P2)
• 2개의 자원 (R1, R2)
  

---

📖 Deadlock Model (표현법)

1. Graph Model

• Node
  - 프로세스 노드 (P1, P2), 자원 노드(R1, R2)

• Edge
  - Rj -> Pi : 자원(Rj)이 프로세스(Pi)에 할당 됨
  - Pi -> Rj : 프로세스(Pi)가 자원(Rj)응 요청 (대기 중)
  - 아래의 그림과 같이 사이클이 형성될 경우, 데드락 상태라고 함
  

2. State Transition Model

• 예제
  - 2개의 프로세스와 A type의 자원 2개(unit) 존재
  - 프로세스는 한번에 자원 하나만 요청/반납 가능

• State

  

  • #of R units allocated : 현재 자원 수, Request : 요청
    state 0 : 자원이 없고, 요청이 없는 상태
    state 1 : 자원이 없고, 요청이 있는 상태
    state 2 : 자원이 1개, 요청이 없는 상태
    state 3 : 자원이 1개, 요청이 있는 상태
    state 4 : 자원이 2개, 요청이 없는 상태
    
    
  • State Trasnsition Model로 표현하면 다음과 같다.
    
  • S33 : 두 프로세스 모두 하나를 가지고, 하나를 요청하는 경우 (Deadlock)

---

📖 Deadlock 발생 필요 조건

• Exclusibe use of resources (자원의 특성)
• Non-preemptible resources (자원의 특성)
• Hold and wait (Partial allocation) (프로세스의 특성)
  - 자원을 하나 hold하고 다른 자원 요청
• Circular wait (프로세스의 특성)

---

📌 Deadlock 해결 방법

1. Deadlock prevention : 교착상태 예방

• 4개의 deadlock 발생 필요 조건 중 하나를 제거하는 방법
  - Exclusive use of resources
  - Non-preemptible resources
  - Hold and wait (Partial allocation)
  - Circular wait

• Deadlock이 절대 발생하지 않음

• 심각한 자원 낭비 발생
  - Low device utilization
  - Reduced system throughput

• 비현실적

1.1. Deadlock Prevention Case

1. 모든 자원을 공유 허용할 경우
   • Exclusive use of resources 조건 제거
   • 현실적으로 불가능

2. 모든 자원에 대해 선점을 허용할 경우
   - Non-preemptible resources 조건 제거
   - 현실적으로 불가능
   - 유사한 방법

   • 프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소
   • 이후 처음 또는 check-point부터 다시 시작
   • 심각한 자원 낭비 발생 -> 비현실적

3. 필요 자원을 한번에 모두 할당할 경우(Total allocation)

   • Hold and wait 조건 제거
   • 자원 낭비 발생 -> 필요하지 않은 순간에도 가지고 있음
   • 무한 대기 현상 발생 가능

4. Circular wait 조건을 제거할 경우
   • Totally allocation을 일반화한 방법
   • 자원들에게 순서를 부여
   • 프로세스는 순서의 증가 방향으로만 자원 요청 가능
   • 자원 낭비 발생

---

2. Deadlock Avoidence : 교착상태 회피

• 시스템의 상태를 계속 감시
• 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state로 유지

2.1. Deadklock Avoidance States

• Safe state
  - 모든 프로세스가 정상적으로 종료 가능한 상태
  - Safe sequence가 존재
  • Deadlock 상태가 되지 않을 수 있음을 보장

• Unsafe state
  - Deadlock 상태가 될 가능성이 있음
  - 반드시 발생한다는 의미는 아님

---

3. Deadlock detenction & recovery methods : 교착상태 탐지 및 복구