[운영체제] 데드락

Deadlock

---

• 모든 프로세스가 다른 프로세스의 작업이 끝나기를 기다리고있는 상태
• Deadlock(교착상태) 발생 필수 조건 4가지
  1. Mutual exclusion (상호배제)
     • 최소한 1개의 자원은 공유할 수 없어야 한다.
  2. Hold and wait (점유대기)
     • 최소한 1개의 자원을 소유한 프로세스가 다른 프로세스가 소유하고 있는 자원을 얻기를 기다려야 한다.
  3. No preemption (비선점)
     • Preemption이 없어야 한다.
  4. Circular wait (순환대기)
     • 서로 다른 프로세스가 자원을 소유하고 요청하는 사이클이 존재해야 한다.

 

Resource Allocation Graph

---

사이클이 없는 resource allocation graph

 

• Resource 종류마다 1개의 인스턴스만 있고, 사이클이 존재한다면 항상 데드락이 발생한다.
• Resuorce 종류마다 여러개의 인스턴스가 있고, 사이클이 존재한다면 항상 데드락인 것은 아니다.

사이클이 있는 resource allocation graph. 교착상태가 존재한다.

사이클이 존재하지만, P2 또는 P4가 자신의 실행을 끝내고 R1 또는 R2를 반환하면 교착상태가 풀린다.

 

Handling Deadlocks

---

1. Prevent or avoid deadlock
   • 시스템이 절대 교착상태에 빠지지 않도록 보장한다.
   • Deadlock avoidance에서는 추가적인 정보가 필요하다.
2. Detect and recover deadlock
   • 시스템이 교착상태에 빠지도록 하지만, 이를 감지하고 복구한다.
3. Ignore
   • 교착상태가 드물게 일어나기 때문에, prevention/avoidance는 오버헤드가 있다.
   • 대부분의 운영체제는 교착상태를 단순히 무시한다.

 

Deadlock Prevention

---

• 다음 4가지 조건 중 적어도 1가지를 만족하지 않도록 하겠다.
  1. Mutual exclusion (상호배제)
     • 자원을 공유 가능하도록 하겠다.
     • 자원을 공유 가능하게 만드는 것이 어려움
  2. Hold and wait (점유대기)
     • 프로세스가 자원을 요청할 때, 다른 자원을 소유하고 있지 않도록 한다.
  3. No preemption
     • 만약 프로세스가 자원을 소유하고 있고, 할당받을 수 없는 다른 자원을 요청한다면, 소유중인 모든 자원을 해제한다.
     • 만약 프로세스가 자원을 요청하고 있고, 그 자원이 추가적인 자원을 요청하고 있는 프로세스에 의해서 소유되고 있다면 preempt 한다.
  4. Circular wait
     • 모든 자원에 대해서 순서를 정하고, 프로세스가 그 순서대로 자원을 요청하도록 한다.
     • 번호가 큰(우선순위가 낮은) 자원을 할당받은 상태에서 번호가 낮은(우선순위가 큰) 자원을 요구한다면, 번호가 큰 자원을 해제한다.

 

Deadlock Avoidance

---

• 자원이 어떻게 요청되는지에 대한 추가적인 정보가 필요하다. 각 요청마다, 해당 요청이 대기해야 하는지 아닌지 결정한다.
• Safe state
  • Safe sequence가 존재한다.
    • 어떤 순서로 할당했을시 데드락은 발생하지 않고, 모든 프로세스의 요구를 처리할 수 있는 순서
  • Safe state에서 시스템은 각 프로세스에게 자원을 할당하는 모든 요청을 만족할 수 있는 safe sequence가 존재한다면 데드락을 피할 수 있다.
• Unsafe state
  • 데드락이 발생할 가능성이 있는 상태 (= Safe sequence를 찾을 수 없는 상태)
  • 모든 unsafe state가 교착상태인 것은 아니다.

Multi-dimensional state space

Safe state 예제

Unsafe state 예제

 

Banker's Algorithm

---

• Deadlock avoidance를 위한 알고리즘이다.
• 자료구조
  • Available: 각 자원유형에 따른 사용가능한 인스턴스의 갯수
  • Max: 각 프로세스가 필요로하는 최대 자원 갯수
  • Alloaction: 프로세스에게 현재 할당된 자원 갯수
  • Need: 프로세스가 필요한 자원의 갯수

Banker's 알고리즘의 예