(44) Deadlock Detection

### Deadlock Detection ###

: 시스템이 Deadlock에 들어가도록 한다.

 

: Deadlock detection algorithm

 

: Deadlock recovery algorithm

 

(Deadlock prevention, avoidance가 비용이나 효율성 측면에서 봤을 때는 무조건 좋다고 볼 수 없다

(deadlock이 항상 발생하지 않기 때문)

다시 말하면 Deadlock prevention이나 avoidance는 리소스를 좀더 효율적으로 사용, 시스템의 utilization을 높일 수 있음에도 불구하고 어쩌다 발생할 수 있는 deadlock을 막기 위해 리소스 할당을 제한하거나 delay를 시킨다

=> 비효율적

 

그래서 시스템의 utilization을 높이고 시스템 성능을 끌어올리기 위해 deadlock 방지기법(Deadlock prevention, avoidance)를 사용 대신에 사후 대책을 생각하는 것이 Deadlock detection 방법, Deadlock recovery 방법 이다.

- Deadlock detection은 deadlock이 발생을 했을 때 이 deadlock이 실질적으로 발생했는지를 시스템이 인지 하게 하는 방법

- Deadlock recovery은 발생한 deadlock에 대해서 deadlock을 인지한 이후 system을 어떻게 복구 시킬 것이냐에 대한 메커니즘

그러나 deadlock 발생 빈도 수가 많고 deadlock이 시스템에 끼치는 영향이 크면 Deadlock detection, recovery방법 보다 사전에 예방하는 Deadlock prevention,avoidance를 사용하는 것이 더 좋다.)

​

​

​

< Single Instance of a Resource Type >

: 사이클 존재 유무를 보고 deadlock 위험성 판단

​

:< Wait-for graph >

: 각 자원 유형의 단일 instance가 있는 시스템의 deadlock을 감지한다.

​

: graph에서 주기를 검색하는 알고리즘을 주기적으로 호출한다.

​

: 기존 Resource allocation graph에서 resouce node만 제거 하여 thread사이를 다시 연결하는 것

​

: dfs 알고리즘을 사용할 수 있다

=> 시간 복잡도 = (node개수 + edge 개수)* node 개수 = node개수^2

 

출처: Operating System Concepts 10th Ed (John Wiley & Sons, Inc. 2018)

 

 

< Multiple Instance of a Resource Type >

: 각 자원 유형의 단일/복수 instance가 있는 시스템의 deadlock을 감지한다.

​

- Available

: 길이가 m인 vector는 각 유형의 사용 가능한 리소스 수를 나타낸다.

​

- Allocation

: n*m 행렬은 각 thread에 현재 할당 된 각 유형의 리소스 수를 정의한다.

​

- Request

: n*m 행렬은 각 thread의 현재 요청을 나타낸다.

(Requesst[i][j] = k인 경우 thread TTii는 k개 이상의 자원 유형 instance request를 요청한다.)

​

: Deadlock이 발생이 확실 할 때 알려주는 알고리즘

(safety 알고리즘은 deadlock의 가능성 까지 알려주는 알고리즘)

 

: work - 사용가능한 instance의 개수(임시 누적 변수)

 

: finish - thread가 완료가 되는지의 여부 파악해주는 변수

 

​

​

​