교착상태 #3 - Deadlock detection and deadlock recovery methods

Deadlock 해결 방법

Deadlock prevention methods

• 교착상태 예방

Deadlock avoidance method

• 교착상태 회피

Deadlock detection and deadlock recovery methods

• 교착상태 탐지 및 복구

---

Deadlock Detection

• Deadlock 방지를 위한 사전 작업을 하지 않음
  • Deadlock이 발생 가능
• 주기적으로 deadlock 발생 확인
  • 시스템이 deadlock 상태인가?
  • 어떤 프로세스가 deadlock 상태인가?
• Resource Allocation Graph (RAG) 사용

 

Resource Allocation Graph (RAG)

• Deadlock 검출을 위해 사용
• Directed, bipartite Graph (프로세서와 자원으로 나눈 그래프)

• Directed graph G = (N,E)
  • N = { Np , Nr } where
    • Np is the set of processes = {P1, P2, ..., Pn}
    • Nr is the set of resources = {R1, R2, ..., Rm}

• N : 노드 ( Np : 프로세서 노드 집합, Nr : 리소스 노드 집합 
• Edge는 Np 와 Nr 사이에만 존재
  • e = (Pi , Rj ) : 자원 요청
  • e = (Rj , Pi ) : 자원 할당

• Rk : k type의 자원
• tk : Rk의 단위 자원 수
  • For each Rk ∈ Nr, ∃ tk which is the number of units of Rk
• |(a,b)| : (a,b) edge의 수

 

RAG example

• 현재 상태가 deadlock인지 확인 하는 방법으로 Graph reduction이 있다.

Graph reduction

• 주어진 RAG에서 edge를 하나씩 지워가는 방법
• Completely reduced
  • 모든 edge가 제거 됨
  • Deadlock에 빠진 프로세스가 없음
• Irreducible
  • 지울 수 없는 edge가 존재
  • 하나 이상의 프로세스가 deadlock 상태

Unblocked process ( edge를 지운다 )

• 필요한 자원을 모두 할당 받을 수 있는 프로세스

• |(Pi, Rj)| : 프로세스 Pi가 요청하는 Rj 자원 수
• tj : Rj의 모든 자원수 
• ∑ |(Rj, Pk)| : 프로세스 Pk에 할당된 Rj의 자원 수들의 합 ( Rj의 모든 자원 중 할당 된 자원 )

=> 모든 자원에 대해서 요청 자원 수 ≤ 남은 자원 수이면 unblocked process 이다.

 

Graph reduction procedure

1. Unblocked process에 연결 된 모든 edge를 제거
2. 더 이상 unblocked process가 없을 때까지 1 반복
   • 최종 Graph에서
   • 모든 edge가 제거 됨 (Completely reduced)
     • 현재 상태에서 deadlock이 없음
   • 일부 edge가 남음 (irreducible)
     • 현재 자원을 할당 받을수 없는 프로세스가 존재 
     • 현재 deadlock이 존재

 

Graph Reduction (example 1)

• 모든 edge가 지워졌으므로 deadlock이 아니다.

Graph Reduction (example 2)

• P1, P2의 edge를 모두 지울 수 없으므로 deadlock이다.

 

 

Graph Reduction 특징

• High overhead
  • 검사 주기에 영향을 받음
  • Node의 수가 많은 경우
• Low overhead deadlock detection methods (Special case)
  • Case-1) Single-unit resources
    • Cycle detection
  • Case-2) Single-unit request in expedient state
    • Knot detection

---

Deadlock Avoidance vs Detection

Deadlock avoidance

• 최악의 경우를 생각
• 앞으로 일어날 일을 고려
• Deadlock이 발생 하지 않음

Deadlock detection

• 최선의 경우를 생각
• 현재 상태만 고려
• Deadlock 발생 시 Recovery 과정이 필요

---

Deadlock Recovery

• Deadlock을 검출 한 후 해결 하는 과정
• Deadlock recovery methods
  • Process termination
    • Deadlock 상태에 있는 프로세스를 종료 시킴
    • 강제 종료 된 프로세스는 이후 재시작 됨
  • Resource preemption
    • Deadlock 상태 해결 위해 선점할 자원 선택
    • 선정 된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
    • 자원을 빼앗긴 프로세스는 강제 종료 됨

 

Process termination

• Deadlock 상태인 프로세스 중 일부 종료
• Termination cost model
  • 어떤 프로세스를 종료 할지에 대한 기준
  • 종료 시킬 deadlock 상태의 프로세스 선택
  • Termination cost
    • 우선순위 / Process priority
    • 종류 / Process type
    • 총 수행 시간 / Accumulated execution time of the process
    • 남은 수행 시간 / Remaining time of the process
    • 종료 비용 / Accounting cost
    • Etc.

종료 프로세스 선택 예

• Lowest-termination cost process first
  • Simple
  • 종료 비용이 가장 적은 프로세스를 종료
  • Low overhead ( 대상 프로세스가 n개일 경우 n번만 검색 ) 
  • 불필요한 프로세스들이 종료 될 가능성이 높음
• Minimum cost recovery
  • 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택
    • 모든 경우의 수를 고려 해야 함
  • Complex
  • High overhead ( 대상 프로세스가 n개일 경우 2의 n제곱 )

 

Resource preemption

• Deadlock 상태 해결을 위해 선점할 자원 선택
• 해당 자원을 가지고 있는 프로세스를 종료 시킴
  • Deadlock 상태가 아닌 프로세스가 종료 될 수도 있음
  • 해당 프로세스는 이후 재시작 됨
• 선점할 자원 선택
  • Preemption cost model 이 필요
  • Minimum cost recovery method 사용
    • O(r)

 

Checkpoint-restart method

• Deadlock Recovery 방법은 어떤 프로세스는 종료되므로 재시작 해야한다. (비효율 발생)
• 프로세스의 수행 중 특정 지점(checkpoint) 마다 context를 저장 
• Rollback을 위해 사용
  • 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작

---

강의

www.youtube.com/watch?v=8XbSgZ2JPQ8&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=23