[OS] 7. Deadlock - Detection and Recovery

Deadlock 해결 방법

• Deadlock prevention methods (교착상태 예방)
• Deadlock avoidance method (교착상태 회피)
• Deadlock detection and deadlock recovery methods (교착상태 탐지 및 복구)

 

Deadlock Detection

• Deadlock을 허용하기 때문에 주기적으로 deadlock 발생 확인
• 확인하는 방법중 많이 사용하는 것이 Resource Allocation Graph (RAG)

 

Resource Allocation Graph (RAG)

지난 포스트에서 Deadlock model인 State Transition Model을 알아보았는데 그 모델을 확장한 것이다.

• Deadlock 검출을 위해 사용
• Directed(방향성이 있는), bipartite Graph (2개의 파트로 나눈 그래프 (프로세스, 자원으로 나눔))

자세히 설명하면 다음처럼 표현할 수 있다.

Directed graph G = (N,E)

N = { N p , N r } where (노드 = 프로세스노드 + 자원노드 의 집합)

N p is the set of processes = {P1, P2, ..., Pn}

and N r is the set of resources = {R1, R2, ..., Rm}

(N: 노드, Np: 프로세스노드, Nr: 자원노드)

Edge 는 N p 와 N r 사이에만 존재

bipartite graph 이기 때문에 edge는 한쪽으로 한쪽으로만 연결될 수 있다. 

(프로세스에서 리소스로, 리소스에서 프로세스로)

• e = (Pi, Rj): 자원 요청 (프로세스에서 리소스로 요청)
• e = (Rj, Pi): 자원 할당 (리소스에서 프로세스로 할당)

Rotation

• 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 인가? 바로 확인하기 애매하다

Deadlock을 판단하기 위한 알고리즘을 소개한다.

 

Deadlock Detection Method

Graph reduction

• 주어진 RAG 에서 edge 를 하나씩 지워가는 방법
• Completely reduced (모든 Edge제거) => Deadlock에 빠진 프로세스 없음
• Irreducible (지울 수 없는 Edge 존재) => 하나 이상의 프로세스가 Deadlock 상태
• Unblocked Process: 필요한 자원을 모두 할당 받을 수 있는 프로세스

 

모든 자원 j에 대해서 프로세스i가(Pi) 요청하는 모든 자원에 대한 요청수(Pi에서 Rj로 가는 갯수)가

tj(Rj의 전체 수)의 수에서 Rj에서 Pk에 할당된 자원(R)개수(남은수=전체개수-사용중) 를 뺀 것보다 작거나 같으면

즉, 요청한 만큼 원하는 자원을 받을 수 있으면 프로세스 Pi는 Unblocked Process이다.

 

Edge를 어떻게 지우는가?

Graph reduction procedure

1. Unblocked process 에 연결 된 모든 edge 를 제거
2. 더 이상 unblocked process 가 없을 때까지 1. 반복

최종 결과 그래프에서..

• 모든 edge 가 제거 됨 (Completely
  
  • 현재 상태에서 deadlock 이 없음
• 일부 edge 가 남음 (irreducible) (자원할당 받을 수 없는 프로세스가 존재)
  
  • 현재 deadlock이 존재

 

Graph Reduction (example 1)

unblocked process를 찾아보자

P1에게 먼저 준다고 가정하면 P1이 원하는 자원을 다 가져갔다고 하자. P1은 Unblocked

P1의 Edge를 지우면.. P2도 Unblocked(R1을 할당 받을 수 있으니까..)

위의 상태가 된다. 

즉, 모든 Edge가 지워지고, Deadlock이 아님을 알 수 있다. 

 

Graph Reduction (example 2)

예제1에서와 마찬가지로 unblocked process를 찾아보자

R3를 P3에 줄 수 있으므로 R3 는 Unblocked이다. 

P3의 Edge를 지워보자..

Unblocked프로세스를 찾으려고 하면 unblocked가 없으므로 위는 Deadlock상태이다. 

앞의 예제를 통해 Graph Reduction 방법을 통해 Deadlock을 찾을 수 있다.

 

Graph Reduction 정리

• High overhead
  • Deadlock 허용을 계속 하지만 계속 검사하기 때문에 검사 주기에 영향을 많이 받음
  • 노드가 크면 오버헤드가 크다는 단점이 있음
• 오버헤드가 적은 Deadlock감지 방법들(특별한 케이스)
  • 케이스1) 자원이 한개일 때 (Cycle detection)
  • 케이스2) Single unit request in expedient state (knot detection)

 

Deadlock Avoidance vs Detection

Deadlock avoidance

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

 

Deadlock detection

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

 

Deadlock Recovery

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
• 불필요한 프로세스들이 종료 될 가능성이 높음 (종료했는데 해결되지 않는 경우 발생)

Minimum cost recovery (최고의 선택을 수행) 

• 최소 비용으로 deadlock 상태를 해소 할 수 있는 process 선택
• 모든 경우의 수를 고려 해야 함 (P1~Pn 까지 종료하는 것을 가정함)
• Complex (모든 경우의 수를 고려하여 복잡함)
• High overhead ( 비교할 때 2^k 코스트 사용, O(2^k): 프로세스 실행, 종료... )

 

Resource preemption

• Deadlock 상태 해결 위해 선점할 자원 선택
• 선정 된 자원을 가지고 있는 프로세스에서 자원을 빼앗음
• 자원을 빼앗긴 프로세스는 강제 종료 된 후 이후 재시작 됨
• Deadlock 상태가 아닌 프로세스가 종료 될 수 있음

선점할 자원 선택

• Preemption cost model 이 필요
• Minimum cost recovery method 사용
• O(r) (비교에 r만큼 코스트 사용)

 

Deadlock Recovery 과정을 보면 Pi는 일을 하다가 종료된 후 일을 다시 시작한다.

프로세스는 다시 일을 시작할 때 처음부터 수행해야 한다.

이 때 게임의 savepoint처럼 프로세스도 수행 중 특정 지점마다 checkpoint를 저장한다..

Checkpoint restart method

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

종료되면 마지막 checkpoint 에서 다시 시작하면 된다.

 

7단원에서 배운내용

Deadlock 의 개념
Deadlock model (표현법)
Deadlock 해결 방법들

• Deadlock prevention
• Deadlock avoidance
• Deadlock detection and recovery

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---