[OS 공룡책] Ch08. Deadlocks

Chapter 8: Deadlocks

System Model

Dining Philosophers Problem

• 멍청한 철학자 5명의 synchronization, deadlock 문제
• 모든 사람들이 동시에 왼쪽 포크를 든 후 오른쪽 포크를 들려고 할 때 → Deadlock(모든 철학자의 무한 대기) 발생
  
• System Model
  • request : 획득할 때까지 대기
  • use : 자원 이용
  • release : 자원 놓아줌

Deadlock Characterization

4가지가 동시에 발생할 때 deadlock 발생

1. Mutual exclusion
   • 적어도 한 개의 resource가 non-sharable mode일 때 (양보 X)
   • read-only는 상호 배제 필요 X
2. Hold and wait
   • 나머지 리소스 가질 때까지 점유하고 대기
3. No preemption
   • 상대방 자원 못 뺏음
4. Circular wait
   • 일렬 대기였으면 문제 X

Deadlock in Multithreaded Applications

Resource-Allocation Graph (RAG)

• Deadlock 쉽게 이해하기 위한 directed graph
• V : vertices
  • P : active thread
  • R : resource type
• E : edges

  1. request edge

     P → R : thread가 resource instance 요청

  2. assignment edge

     R → P : resource instance가 thread에 할당

Graphs with a Cycle

• Deadlock
• No Deadlock
• Cycle 존재 (X) → Deadlock (X)
• Cycle 존재 (O) → Deadlock (?)
  • resource type 당 오직 하나의 instance → deadlock
  • resource type 당 여러 개의 instance → ?

Deadlock Prevention

Methods for Handling Deadlocks

1. 안전한 상태 유지
   • prevention
     • deadlock이 아예 발생하지 않도록 4가지 조건 중 하나 없애기 → deadlock 없애는 데에는 가장 효율적
       
     • resource utilization, system throughput 저하
   • avoidance
     • 발생할 것 같으면 회피
2. deadlock state에 들어가고 recover
3. ignore
   • OStrich algorithm (타조 알고리즘)

Deadlock Prevention

• Mutual Exclusion 방지
  • 공유 자원들의 배타적 접근 적용 X ex. read-only 파일
    
  • 비공유 자원 : 배타적 접근 보장 필요 (ex. 프린트)
• Hold and Wait 방지

  1. 프로세스 시작부터 Maximum으로 요구하는 자원 모두 hold

     → system utilization 저하

  2. 프로세스가 아무것도 hold하지 않을 때만 resource 요청

     (wait 상태가 오래되면 hold하는 것 release)

     → starvation 발생

• No Preemption 방지
  • preemption : 리소스의 주인이 계속 바뀜
  • CPU 레지스터, 메모리 : 쉽게 저장, 복원 가능 ↔ 프린터 : 적용 어려움, 성능 손해
    
• Circular Wait 방지
  • 가장 쉬운 방법
  • pid에 order 부여 : 오름차순으로만 자원 요청 가능 → starvation 발생 → 오름차순 요청 : 자원 활용의 큰 제약, utilization 저하
    
  • 사이클 X → 교착상태 발생 X

Deadlock Avoidance

Deadlock Avoidance

• 각 프로세스가 사용할 resource의 최대치 미리 선언
• 할당 해놓은 resource, 할당 가능한 resource, 앞으로 요구할 resource 비교 → 남아있는 게 maximum보다 작으면 safety
  
• 다음 상태가 safe일 때만 resource 할당 → future deadlock 피하기
  

Safe , Unsafe, Deadlock State

• Safe
  • deadlock이 발생하지 않는 상태
  • 끝날 수 있는 방법이 하나라도 존재 O
  • safe sequence를 찾을 수 있다면 safe state!
• Unsafe
  • deadlock이 발생할 가능성이 있는 상태
  • 끝날 수 있는 방법이 하나도 존재 X

Avoidance Algorithms

• resource type의 Single instance
  • resource-allocation graph 사용
• resource type의 Multiple instance
  • banker’s algorithm 사용
  • safety 체크하는 알고리즘 계속 적용

Resource-Allocation Graph

• Claim edge 고려

  

  • P2, P1 → NO (Cycle 만들어짐) P1, P2 → YES
    
  • claim edge → assignment edge 변환 후에도 safe state일 때만 할당

• cycle 존재 X

  • claim edge 바로 granted
  • claim edge → request edge

• cycle 존재 O

  • unsafe state (grant 안 함)

Banker’s Algorithm

• Banker’s Algorithm
  1. Safety 파악하는 알고리즘
  2. resource request 받을 지 결정하는 알고리즘
• 사용할 리소스의 최대치 사전 정의
• Available[j] : 남아있는 자원 개수 Allocation[i][j] : Pi가 가지고 있는 Rj 개수 Request[i][j] = k : Pi가 Rj를 k개 요청
  

Safety Algorithm

1. Work = Available

   Finish[i] = false for i = 0, 1, …, n-1

2. Finish[i] = false & Need[i] ≤ Work

   (i가 없으면 go to step4)

3. Work = Work + Allocation[i]

   Finish[i] = true

   (go to step2)

4. 모든 i에 대해 Finish[i] == true

   → safe state

• Example>

  

  • Work = [3, 3, 2]
  • Need[i] ≤ Work
    • Need[i] = Max[i] - Allocaiton[i]
    • i = 0; [7, 4, 3] ≤ [3, 3, 2] → False
    • i = 1; [1, 2, 2] ≤ [3, 3, 2] → True
  • Work = Work + Allocation[i], Finish[i] = True
    • Work = [3, 3, 2] + [2, 0, 0] = [5, 3, 2]
    • Finish[1] = true
  • Need[i] ≤ Work
    • i = 2; [6, 0, 0] ≤ [5, 3, 2] → False
    • i = 3; [0, 1, 1] ≤ [5, 3, 2] → True → Work = [5, 3, 2] + [2, 1, 1] = [7, 4, 3] Finish[3] = true
      
    • i = 4; [4, 3, 1] ≤ [7, 4, 3] → True → Work = [7, 4, 3] + [0, 0, 2] = [7, 4, 5] Finish[4] = true
      
    • i = 0; [7, 4, 3] ≤ [7, 4, 5] → True → Work = [7, 4, 5] + [0, 1, 0] = [7, 5, 5] Finish[0] = true
      
    • i = 2; [1, 2, 2] ≤ [7, 5, 5] → True → Work = [7, 5, 5] + [3, 0, 2] = [10, 5, 7] Finish[2] = true
      
  • grant 순서 : <P1, P3, P4, P0, P2>, <P1, P3, P4, P2, P0> → 순서 상관없이 sequence가 존재하기만 하면 됨!
    

Resource-Request Algorithm

1. Request[i] ≤ Need[i] → go to step2

   최대 요구치보다 작거나 같아야한다.

2. Request[i] ≤ Available → go to step3

   아니면, wait (자원이 available 상태가 아니기 때문)

3. Available = Available - Request[i]

   Allocation[i] = Allocation[i] + Request[i]

   Need[i] = Need[i] - Request[i]

   • 업데이트된 자료를 기준으로 다시 safety algorithm 진행 → safe면 자원 할당 → unsafe면 wait, allocation state 갱신
     

• Example> P1 Request (1, 0, 2)

  

  • Request[i] ≤ Need[i]
    • (1, 0, 2) ≤ (1, 2, 2)
  • Request[i] ≤ Available
    • (1, 0, 2) ≤ (3, 3, 2) → True
  • Available = Available - Request[i]
    • Available = (3, 3, 2) - (1, 0, 2) = (2, 3, 0)
  • Allocation[i] = Allocation[i] + Request[i]
    • Allocation[1] = (2, 0, 0) + (1, 0, 2) = (3, 0, 2)
  • Need[i] = Need[i] - Request[i]
    • Need[1] = (1, 2, 2) - (1, 0, 2) = (0, 2, 0)

Deadlock Detection

Deadlock Detection (교착상태 탐지)

• prevention, avoidance보다 적은 overhead
• Deadlock Detection
  1. Deadlock 탐지하는 알고리즘
     • resource type의 single instance
       • resource allocation graph 사용
       • cycle 있으면 deadlock, 없으면 deadlock-free
     • resource type의 several instance →
       
  2. Deadlock 회복하는 알고리즘
     • check point : 시스템 상태 중간중간 체크, 백업
     • rollback : 가장 최근 check point로 rollback

Single Instance of Resource Type

• Wait-for Graph

  

  • Resource-Allocation Graph 변형 → 기다리는 상태만 표현 (resource 제외)
    
  • detection하는 복잡도 감소 → O(N^2) : N은 vertex 개수
    
  • 정확도 증가 X

• 주기적으로 cycle 여부 탐지

  → deadlock 발생 → rollback
  

Several Instances of Resource Type

• Detection Algorithm

  1. Work = Available

     Finish[i] = false

     Allocation[i] == 0 → Finish[i] = true

  2. Finish[i] == false && Request[i] ≤ Work

     → 만족 못 하면 go to step4

  3. Work = Work + Allocation[i]

     Finish[i] = true

     (go to step2)

  4. Finish[i] == false for some i

     → P[i] 는 deadlock

• Example>

  

  • A (7 instances), B (2 instances), C (6 instances)
  • Work = [0, 0, 0]
  • Request[i] ≤ Work
    • i = 0; [0, 0, 0] ≤ [0, 0, 0] → True
  • Work = Work + Allocation[i]
    • Work = [0, 0, 0] + [0, 1, 0] = [0, 1, 0]
    • Finish[0] = true

• 사용

  • 얼마나 자주 호출할 것인가?
  • 탐지 알고리즘이 제멋대로 호출된다면? → 어떤 프로세스가 deadlock인지 알 수 X
    
  • 바람직한 시점은?
    • 자원 요청할 때마다 호출 → 오버헤드 큼
    • 자원 요청 시 즉시 만족되지 못 하는 시점 → good
    • 지정된 시간 간격으로 호출 → CPU Utilization이 40% 이하로 떨어질 때
      
  • deadlock : 프로세스가 아무것도 못 하고 기다리는 교착상태 livelock : 의미없는 작업 열심히 하고 있는 교착상태 → CPU Utilization으로 판단하기 어려움
    

Recovery from Deadlock

Recovery from Deadlock

• 운영자에 의한 해결
  • 운영자가 수작업으로 처리
  • 비현실적인 방법
• process termination
  • circular wait을 깨기 위해 하나 이상의 프로세스 종료
• resource preemption
  • 하나 이상의 교착상태인 프로세스들로부터 자원 뺏음

Process Termination

1. 교착상태 프로세스들 모두 중지
   • 확실한 교착상태 제거
   • 높은 비용 : 다시 모두 재개
2. 교착상태 제거될 때까지 하나씩 중지
   • 중지되는 프로세스 수 감소
   • 중지 후 문제 해결 여부 확인을 위해 교착상태 탐지 알고리즘 계속 호출 → 오버헤드
     
   • 고려사항
     • 프로세스 우선순위, 작업 진행도, 사용한 자원, 필요한 자원
     • 대화형보단 일괄(batch)처리형 종료

Resource Preemption

• 교착상태 깨질 때까지 프로세스로부터 자원 선점해 다른 프로세스에게 전달
• 자원 선점 요소
  1. 희생자 선택
     • 비용 최소화
     • 프로세스가 점유한 자원의 수, 지금까지 소요한 시간 등 고려
  2. Rollback
     • 안전한 상태로 되돌려 재시작
     • 안전한 상태 파악 어려움 → 가장 단순하게 프로세스 abort후 재시작
       
  3. Starvation
     • 같은 프로세스가 항상 희생자로 선택
     • 해결책> 희생자 선택 시 rollback 횟수 고려