<aside> 📌 Deadlock의 처리 방법, Deadlock Avoidance, Example of Banker's Algorithm, p1 request(1, 0, 2), Deadlock Detection and Recovery, Deadlock Ignorance

</aside>

Deadlock의 처리 방법

위로 갈수록 Deadlock을 처리하기 위한 강한 방법 3, 4번은 Deadlock이 생기도록 방치

1. Deadlock Prevention
   • 자원 할당 시 Deadlock의 4가지 필요 조건 중 어느 하나가 만족되지 않도록 하는 것
2. Deadlock Avoidance
   • 자원 요청에 대한 부가적인 정보를 이용해서 deadlock의 가능성이 없는 경우에만 자원을 할당
   • 시스템 state가 원래 state로 돌아올 수 있는 경우에만 자원 할당
3. Deadlock Detection and recovery
   • Deadlock 발생은 허용하되 그에 대한 detection 루틴을 두어 deadlock 발견시 recover
4. Deadlock Ignorance
   • Deadlock을 시스템이 책임지지 않음 (사람이 프로세스를 직접 죽이는 등 해결해야 함)
   • UNIX를 포함한 대부분의 OS가 채택

Deadlock Prevention

• Mutual exclusion (상호 배제)
  • 공유해서는 안되는 자원의 경우 반드시 성립해야 함
• Hold and wait (보유 대기)
  • 프로세스가 자원을 요청할 때 다른 어떤 자원도 가지고 있지 않아야 함
  • 방법 1: 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법
  • 방법 2: 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청
• No Preemption (비선점)
  • process가 어떤 자원을 기다려야 하는 경우 이미 보유한 자원이 선점됨
  • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작됨
  • State를 쉽게 save하고 restore할 수 있는 자원에서 주로 사용 (CPU, memory)
• Circular wait (순환 대기)
  • 모든 자원 유형에 할당 순서를 정하여 정해준 순서대로만 자원 할당
  • 예를 들어 순서가 3인 자원 R1를 보유중인 프로세스가 순서가 1인 자원 R2을 할당받기 위해서는 우선 R1을 release해야 함

→ Utilization 저하, throughput 감소, starvation 문제

Deadlock Avoidance

• 정의
  • 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당
  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법임
• safe state
  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태
• safe sequence
  • 프로세스의 sequence <P1, P2, …, Pn>이 safe하려면 Pi(1 ≤ i ≤ n)의 자원 요청이 가용 자원 + 모든 Pj (j < i)의 보유 자원 에 의해 충족되어야 함
  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장
    • Pi 의 자원 요청이 즉시 충족될 수 없으면 모든 Pj (j < i)가 종료될 때까지 기다린다
    • Pi-1 이 종료되면 Pi 의 자원 요청을 만족시켜 수행한다

• 항상 safe한 상태를 유지

Resource Allocation Graph algorithm (자원당 인스턴스가 하나인 경우)

Banker’s Algorithm 사용 (자원당 인스턴스가 여러 개인 경우)

• 가정

  • 모든 프로세스는 자원의 최대 사용량을 미리 명시
  • 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납

• 방법

  • 기본 개념: 자원 요청시 safe 상태를 유지할 경우에만 할당
  • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택
  • 그런 프로세스가 있다면 그 프로세스에게 자원을 할당 (그런 프로세스가 없다면 unsafe 상태)
  • 할당 받은 프로세스가 종료되면 모든 자원을 반납
  • 모든 프로세스가 종료될 때까지 이러한 과정 반복

• Example of Banker’s Algorithm

  

  

  • 요청한 자원이 가용한 자원보다 적기 때문에 처리가 가능한 것

Deadlock Detection and Recovery

• Deadlock Detection
  • Resource type 당 single instance인 경우
    • 자원할당 그래프에서의 cycle이 곧 deadlock을 의미
  • Resource type 당 multiple instance인 경우
    • Banker’s algorithm과 유사한 방법 활용
• wait-for graph 알고리즘
  • Resource type 당 single instance인 경우
  • wait-for graph
    • 자원할당 그래프의 변경 (자원을 빼버리고 표시)
    • 프로세스만으로 node 구성
    • Pj 가 가지고 있는 자원을 Pk 가 기다리는 경우는 Pk → Pj
  • Algorithm
    • wait-for graph에 사이클이 존재하는지를 주기적으로 조사
    • O(n^2) → 깊이 우선 탐색

• Recovery
  • Process termination
    • Abort all deadlocked processes
    • Abort one process at a time until the deadlock cycle is eliminated
  • Resource Preemption
    • 비용을 최소화할 victim 선정
    • safe state로 rollback하여 process를 restart
    • Starvation 문제
      • 동일한 프로세스가 계속해서 victim으로 선정되는 경우
      • cost factor에 rollback 횟수도 같이 고려

Deadlock Ignorance

• Deadlock이 일어나지 않는다고 생각하고 아무런 조치도 취하지 않음
  • Deadlock이 매우 드물게 발생하므로 deadlock에 대한 조치 자체가 더 큰 overhead일 수 있음
  • 만약, 시스템에 deadlock이 발생할 경우 시스템이 비정상적으로 작동하는 것을 사람이 느낀 후 직접 process를 죽이는 등의 방법으로 대처
  • UNIX, Windows 등 대부분의 범용 OS가 채택