[OS] Deadlocks

Deadlock Problem

• 두개 이상의 task들이 한개 이상의 resource type이나 instance를 요청해야할 때 발생
• 어떤 task가 어떤 resource를 잡고 있고 또 다른 task가 그 resource를 필요로하여 기다리고 있을 때 발생

Conditions for Deadlock

1. Mutual exclusion
   어떤 resource가 있는데 서로 두개 이상의 task가 share해서 쓸 수 없는 resource여야 한다.
2. Hold and wait
   어떤 resource를 여러개가 필요한데 allocate하여 require하는 도중에
3. No preemption
   내가 어떤 resource를 줬으면 반환하기 전까지는 뺏어가지 않겠다.
4. Circular wait
   Task들이 wait하고 있는데 결국 circular로 서로 기다리고 있는 상황이라고 한다.

Strategies for Handling Deadlocks

Deadlocks never happen

• Deadlock prevention
• Deadlock avoidance

Deadlocks may happen

• Deadlock detection and recovery
• ignore

Deadlock Prevention

• deadlock이 발생하는 조건 4가지 중 한 개 이상이 발생하지 않게 한다.
  • Mutual exclusion
    여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
  • Hold and wait
    프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
  • No preemption
    자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
  • Circular wait
    resource잡는 순서를 정해놓고(total ordering) 순서가 작은것부터 큰 순으로 한방향으로만 lock을 잡게 한다.
• 시스템이 resource를 allocate하는 순서와 time을 보고 deadlock이 발생할 것인지 판단할 수 있게 하는 시스템 : witness

Deadlock Avoidance

• safe state에서 unsafe state로 가지 않게 한다.
• safe state : resource를 acquire하고 release하는 과정을 다 안다고 했을 때 모든 프로세스가 모든 요청을 다 완수했을 때, safe sequence가 하나라도 있을 때
• safe sequence : 현재 resource상황이 있고 각 프로세스들이 필요로 하는 resource allocation schedule이 있는데 이것에 맞춰 resource를 잘 나눠줬더니 모두가 잘 도는 순서
• 예시
  운영체제는 12개의 자기 테이프 드라이브 공유자원을 가진다. 어느 시점 t0에서 P0, P1, P2의 요구대로 공유자원을 주면 현재 운영체제는 3개의 테이프가 사용가능한 자원으로 남아있다. t0 시점에 시스템은 safe state이다. <P1, P0,P2>로 safe sequence를 만족한다.
  하지만 시스템은 safe state에서 unsafe state로 변할 수 있다. t1에 P2가 자원하나를 더 요청하였다. 그러면 P2는 3개를 가지고 운영체제는 2개를 가지게 된다. P0은 5개가 필요하기 때문에 불가능하다. P1은 2개가 필요하므로 남은 2개를 주면 P1을 끝낼 수 있을 거라고 생각하지만 P1이 사용되고 반환하더라고 총 테이프는 4개가 되어 P0이나 P2를 해결해줄 수 없다. 따라서 t1에서는 시스템이 unsafe state가 된다. deadlock에 빠질 가능성이 있는 t1에서 P2에게 자원을 빌려주지 않고 P1이 끝나도록 하는(safe state를 유지하는) 것이 이 알고리즘이다.
  
• Banker's Algorithm
  • 프로세스가 자원을 요구할 때 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사하여 교착 상태를 회피하는 기법
  • 안정 상태에 있으면 자원 할당, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기
  • 예시
    
    Allocation에서 각각 A, B, C끼리 더하면 7, 2, 5이다. Total resources - 7, 2, 5 = Available resources. Max - Allocation = Need

Deadlock Recovery

• Deadlock이 발생한 상황을 알아내고(detection) process를 termination을 한다.
• Resource preemption

Ignore

• Ostrch algorithm : 타조가 위험에 처하면 머리를 땅에 박고 자신은 보이지 않으므로 안전하다고 생각한다.