운영체제 7. 교착 상태 Deadlock (5) - Deadlock detection and Recovery

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

 

 

 

• Deadlock prevention method는 비현실적이거나 비효율적이라는 문제가 있다.
• Deadlock avoidance method는 오버헤드가 너무 크고 자원 효용성이 떨어진다는 문제가 있다.

 

 

Deadlock Detection (데드락 검출 : Deadlock을 찾아내는 방법)

 

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

 

 

• Resource Allocation Graph (RAG)
  • Deadlock 검출을 위해 사용
  • Directed(방향성이 있음), bipartite(2개(프로세스와 리소스)의 파트로 나눔) Graph

 

 

• Resource Allocation Graph (RAG)
  • Directed graph G = (N, E)
    • N = {Np, Nr} 노드 N은 Np와 Nr의 집합이다.
      • Np는 프로세스들의 집합 = {P1, P2, ..., Pn}
      • Nr은 리소스들의 집합 = {R1, R2, ..., Rm}

 

 

• Edge는 Np와 Nr 사이에만 존재한다. bipartite graph이기 때문에 한쪽에서 다른쪽으로 (다른 그룹으로만) 엣지가 연결될 수 있다.
  • e = (Pi, Rj) : 프로세스 Pi가 자원 Rj를 요청
  • e = (Rj, Pi) : 자원 Rj가 프로세스 Pi에게 할당

 

 

• Rk : k type의 자원
• tk : Rk의 단위 자원 수, 자원 Rk가 몇 개 있는가
• |(a, b)| : (a, b) edge의 수

 

RAG example

 

프로세스는 P1, P2가 있고, 자원은 R1이 3개, R2가 2개 있다. 이중 R1 2개는 P1에게 할당되어있고, 1개는 P2에게 할당되어있다. 그리고 R2 1개는 P2에게 할당되어있는 상황이다. 여기서 P1은 R2를 요청하고 있고, P2는 R1과 R2를 요청하고 있다. 이 상황은 deadlock 상황일까?

 

Deadlock을 쉽게 판단하기 위한 알고리즘으로 graph reduction 방법이다.

• Graph reduction : 그래프를 줄인다.
  • 주어진 RAG에서 edge를 하나씩 지워가는 방법
  • completely reduced
    • 모든 edge가 제거 됨
    • Deadlock에 빠진 프로세스가 없음
  • Irreducible
    • 지울 수 없는 edge가 존재
    • 하나 이상의 프로세스가 deadlock 상태

 

그렇다면 어떤 엣지를 지워야 할까?

• Unblocked process에 연결된 엣지를 전부 지운다.
  • 필요한 자원을 모두 할당 받을 수 있는 프로세스
  • 프로세스가 요청한 리소스의 수보다 남은 리소스의 수가 더 많을 때. 즉, 필요로 하는 자원을 다 할당받을 수 있는 프로세스를  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)

 

(a) 번의 상황에서 unblocked process가 존재할까? P1에게 R2자원을 먼저 할당해주면 P1은 unblocked process가 된다. 그러면 (b) 번처럼 P1에게 연결된 edge를 모두 지워준다. 그 뒤, P2가 요청하는 자원들을 모두 할당해줄 수 있고 (c) 번처럼 P2에게 연결된 edge를 모두 지운다.

 

모든 edge가 제거되었으므로(Completely reduced) deadlock이 아니다.

 

 

Graph Reduction (example 2)

 

초기 상태 (a)에서 P3가 unblocked process가 될 수 있다. P3에게 연결된 edge를 제거하면 (b)가 된다.

(b)에서 P1과 P2 둘다 unblocked process 가 될 수 없으므로 edge가 남아있는 상태(irreducible)로 종료가 된다.

 

그러므로 example 2는 deadlock 상태이다.

 

 

Deadlock Detection Method

 

• 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는 크게 2가지로 나뉜다.
  • Process termination
    • Deadlock 상태에 있는 프로세스를 종료시킴
    • 강제 종료 된 프로세스는 이후 재시작 됨
  • Resource preemption
    • Deadlock 상태 해결을 위해 선점할 자원을 선택
    • 선정된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
      • 자원을 빼았긴 프로세스는 강제 종료 됨

 

 

• Process termination
  • Deadlock 상태인 프로세스 중 일부 종료 (deadlock인 프로세스 Pa, Pb, Pc가 있을 때, 이중 일부를 종료시켜서 나머지 프로세스의 deadlock을 해결)
  • Termination cost model
    • 종료시킬 deadlock 상태의 프로세스 선택
    • Termination cost
      • 우선순위
      • 종류
      • 총 수행 시간
      • 남은 수행 시간
      • 종료 비용

 

 

• Process termination
  • 종료 프로세스 선택
    • Lowest-termination cost process first (종료비용이 제일 적은애를 먼저 종료시키기)
      • 장점 
        • Simple (쉽게 찾을 수 있음)
        • Low overhead. O(N) 한 바퀴만 돌면 됨
      • 단점
        • 불필요한 프로세스들이 종료될 가능성이 높음
    • Minimum cost recovery
      • 모든 경우의 수를 고려해서 최소 비용으로 deadlock 상태를 해소할 수 있는 process 선택
        • 모든 경우의 수를 고려해야 함
      • Complex
      • High overhead. 프로세스가 k개 있다고 가정했을 시 O(2^k)

 

 

• Resource preemption
  • Deadlock 상태 해결을 위해 선점할 자원 선택. P1이 R1, R2, R3가 필요한데 자원들이 모두 다른 프로세스들에게 할당되어있다. 이때, 어느 프로세스의 자원을 뺐어올지를 선택하는 것이다.
  • 해당 자원을 가지고 있는 프로세스를 종료 시킴
    • Deadlock 상태가 아닌 프로세스가 종료 될 수도 있음
    • 해당 프로세스는 이후 재시작 됨
  • 선점할 자원 선택
    • Preemption cost model(기준)이 필요
    • Minimum cost recovery method 사용. 리소스가 r개 있다고 가정했을 시 O(r)

 

 

Deadlock Recovery는 결국 어떤 프로세스 Pi가 종료되고, 재시작할 시 처음지점부터 다시 시작하게 된다. 이런 비효율성을 해결하기 위해 checkpoint-restart method가 있다.

• Checkpoint-restart method
  • 프로세스의 수행 중 특정 지점 (check point) 마다 context를 저장
  • Rollback을 위해 사용
    • 프로세스 강제 종료 후, 가장 최근의 checkpoint에서 재시작