[Operating System] DeadLock

DeadLock

DeadLock이란 각 process가 각자가 원하는 자원을 갖고 있어 더 이상 작업이 진행되지 않는 상태를 의미한다.

 

이러한 deadlock은 다음 4가지 조건이 모두 동시에 만족되는 경우에 발생하게 된다.

• Mutual exclusion : 하나의 자원을 오직 하나의 process만 접근이 가능한 경우
• No preemption : resource의 release가 오직 현재 resource를 점유하고 있는 process에 의해서만 가능한 경우
• Hold and Wait : process가 자신이 원하는 자원을 요청할 때 다른 자원을 hold한 상태로 요청하는 경우
• Circular wait : process가 순환적으로 자원을 요청하는 경우

Resource-Allocation Graph

resource와 process의 allocation 관계를 graph로 나타내는 것

vertex는 2종류로 이루어져 있다.

• P_i : i번째 process
• R_j : j번째 resource

edge도 2종류로 이루어져 있다.

• P_i  -> R_j : i번째 process가 j번째 resource를 요청
• R_j -> P_i : j번째 resource가 i번째 process에 할당됨

예시

• 현재 $R_2$ resource가 $P_1,P_2$에
• $R_1$가 $P_2$에
• $R_3$가 $P_3$에 할당되어 있는 상태에서
• $P_1$가 $R_1$을 기다리고, $P_2$가 $R_3$를 기다리고 있는 상태이다.

Basic Facts

1. graph에 cycle이 없다면 deadlock이 발생하지 않은 상태
2. graph에 cycle이 있다면 deadlock이 발생할 수 있는 상태

cycle이 있고 deadlock이 발생한 경우

cycle이 있지만 deadlock이 발생하지 않은 상태

tip) resource $R$의 모든 instance가 cycle이 존재한다면 deadlock

• 1번 예시에서 $R_2$의 모든 instance가 cycle로 구성되어 있다.
• 2번 예시에서 $R_1$의 1개의 instance에는 cycle이 있지만 다른 한 개는 cycle이 없기 때문에 deadlock이 아니다.

이러한 사실로부터 알 수 있는 것은 모든 resource가 single instance라면 cycle이 존재하면 반드시 deadlock 상태임을 알 수 있다.

Methods for Handling Deadlocks

deadlock을 막기 위한 방법론은 크게 3종류로 나뉜다.

1. deadlock state 자체가 발생하지 않도록 하는 방식
   • prevent : deadlock 발생 요건 중 한 가지를 제거
   • avoid : deadlock이 발생할 것인지를 검사하면서 resource를 할당
2. deadlock이 발생하면 그 때 처리하는 방식
   • detection : deadlock이 발생했는지 detection한 뒤 발생했다면 recover하는 방식
3. deadlock 상태를 무시하는 방식
   • 최근 HW의 발전으로 처리속도가 빨라지고, resource instance의 수가 증가하고 resource 자체도 증가하면서 deadlock이 잘 발생하지 않기 때문
   • deadlock을 처리하는 algorithm의 시간복잡도가 높고 resource utilization을 감소시키기 때문

Deadlock Prevention

deadlock 발생 요건 중 한 가지를 제거

1. mutual exclusion
   • 공유 데이터 특성 상 mutual exclusion을 제거할 수 있는 방법이 없다.
2. Hold and wait
   • process가 하나를 잡은 상태로 다른 하나를 요청하는 것을 방지
   • 즉, process가 자신이 필요한 자원을 한번에 요청하는 방식을 사용(all or nothing)
3. No Preemption
   • process가 모든 자원을 요청할 수 없는 상태라면 현재 잡은 자원도 모두 release하는 방식
   • hold and wait와 다른 방식으로 deadlock을 방지하는 것
   • process가 동시에 필요한 자원을 모두 사용하는 것이 아님에도 불구하고 모두 잡지 못하면 어떠한 작업도 진행하지 못 하기 때문에 resource utilization이 감소한다.
4. Circular wait
   • 전체 resource에 순서를 부여한 뒤, process들이 resource를 순서에 맞춰 자원을 요청하는 방식

• 위에서 circular wait가 발생하는 이유는 $P_1$이 $R_1$보다 $R_3$를 먼저 요청해 할당받은 상태이기 때문이다.
• 만약 순서대로 요청을 했다면, 아래와 같이 되어 cycle이 발생하지 않는다.

💡 [순서]
P1 → R1 요청 (assign)
P2 → R1 요청 (wait)
P3 → R2 요청 (assign)
P3 → R3 요청 or P1 → R3 요청 (assign)

⇒ P1이나 P3는 무조건 자신이 필요한 자원을 할당받을 수 있으므로 cycle 발생 X

Deadlock Avoidance

deadlock이 발생할 것인지를 검사하면서 resource를 할당

deadlock이 발생할 것인지를 알기 위해 각 process의 사전 지식이 필요

가장 간단한 방식으로는 각 process가 자신이 요청할 resource의 최대치를 사전 지식으로 전달하는 것이다.

safe state

process가 요청한 resource를 할당할 수 있을 때, 할당하기 전에 반드시 할당하고 난 뒤의 상태가 safe state인지를 확인해야 한다.

 

safe state란 남은 resoure를 이용해 현재 실행 중인 process를 모두 종료할 수 있는 sequence가 존재하는 경우가 있을 때를 의미한다.

 

basic facts

• 만약 system이 safe state라면, deadlock이 발생하지 않는다.
• 만약 system이 safe state가 아니라면, deadlock이 발생할 수 있다.
  ⇒ 반드시 deadlock이 발생하는 것은 아니고, 모든 process가 자신이 필요한 자원을 동시에 요청하면 deadlock이 발생하게 된다는 것을 의미

avoidance algorithm : single instance resource

claim edge를 추가한 resource-allocation graph를 이용

claim edge $P_i -> R_j$ : $P_i$가 $R_j$를 요청하게 될 것이라는 것을 의미(점선으로 표시)

request edge $P_i -> R_j$ : 현재 $P_i$가 $R_j$를 요청해 대기하고 있는 것을 의미

assignment edge $R_j -> P_i$ : 현재 $R_j$가 $P_i$에 할당되어 있다는 것을 의미

1. 위 상태에서 $P_2$가 $R_2$를 요청하게 된다면 algorithm은 만약 $P_2$에게 $R_2$를 할당한다면 어떻게 되는지를 확인한다.

2. $P_2$에게 $R_2$를 할당하게 된다면 다음과 같은 resource-allocation graph가 생성되게 되고, cycle이 발생하기 때문에 algorithn은 $P_2$에게 $R_2$를 할당하지 않게 된다.
⇒ 해당 상태 자체는 cycle이 아니지만 cycle이 발생할 여지($P_1$가 $R_2$에게 요청을 보내는 상황)이 존재하기 때문에 unsafe하다고 하는 것!!

avoidance algorithm : multiple instance resource

Banker’s algorithm

single instance와 다르게 $P_i$가 몇 개의 $R_j$를 사용할 것인지도 알아야 한다.

• $Available[j] = k$ : $R_j$의 자원이 k개 남아있는 상태
• $Max[i,j]=k$ : $P_i$가 $R_j$을 최대 $k$개 할당한다는 의미
• $Allocation[i,j]=k$ : 현재 $P_i$가 $R_j$를 k개 할당받았다는 의미
• $Need[i,j]=k$ : $P_i$가 앞으로 작업을 완료하기 위해 더 할당받아야 할 $R_j$가 k개라는 의미
• ⇒ $Need[i,j]=Max[i,j]-Allocation[i,j]$

safety algorithm

1. 현재 실행 중인 process를 unfinish 상태로 initialization
2. process를 순회하면서 unfinish 상태의 process를 찾는다.
3. unfinish process 중 작업을 끝내기 위해 필요한 자원이 현재 이용 가능한 자원 내에서 해결이 가능한 경우를 찾는다.
4. 3번을 만족하는 process가 존재하면, 모든 자원을 해당 process에게 할당해서 작업을 끝낼 수 있다는 의미이므로 해당 process의 상태를 finish로 바꾸고 해당 process가 갖고있던 원래 resource를 반환한다.
5. 위 작업을 반복해 모든 process가 finish 상태가 될 수 있다면 safety, 그렇지 않다면 unsafety

 

banker’s algorithm

1. 요청하는 resource가 자신이 원래 필요로 했던 자원보다 작은지 확인
   ⇒ 더 많다면 에러 또는 이상 행동이므로 종료
2. 요청하는 resource가 현재 할당 가능한지 확인
   ⇒ 할당 가능하지 않다면 wait
3. safety algorithm을 통해 해당 resource를 할당한다면 safe한지 확인
   ⇒ safe하다면 그때서야 할당

example

Q. 현재 상태는 safe 상태인가?

 

Q. 만약 $P_1$이 $<1,0,2>$를 요청한다면 할당이 가능?

 

Q. 만약 $P_4$이 $<3,3,0>$를 요청한다면 할당이 가능?

Q. 만약 $P_0$이 $<0,2,0>$를 요청한다면 할당이 가능?

Deadlock Detection

deadlock이 발생했는지 detection한 뒤 발생했다면 recover하는 방식

deadlock detection algorithm과 recovery scheme이 필요

single instance deadlock detection

single instance resource인 경우는 단순히 wait-for graph의 cycle 여부를 체크함으로써 알 수 있다.

• wait-for graph : resoure-allocation graph에서 resource node를 제거한 graph

• cycle detection algorithm의 시간 복잡도 : $O(N^2), N:\# node$
• ⇒ 따라서 wait-for graph로 축약해 표현함으로써 시간 복잡도를 줄일 수 있다.

multiple instance deadlock detection

safety algorithm과 유사한 동작 방식이다.

• $Available[j] = k$ : $R_j$의 자원이 k개 남아있는 상태
• $Allocation[i,j]=k$ : 현재 $P_i$가 $R_j$를 k개 할당받았다는 의미
• $Request[i,j]=k$ : $P_i$가 $R_j$ k개를 요청한 상태라는 의미

safety algorithm과 다르게 $Max,Need$ 등의 변수가 사라짐

⇒ process가 현재 요청한 정보만 가지고 판단하기 때문

 

detection algorithm

1. 현재 실행 중인 process를 unfinish 상태로 initialization
2. process를 순회하면서 unfinish 상태의 process를 찾는다.
3. unfinish process 중 해당 프로세스가 요청한 자원이 현재 이용 가능한 자원 내에서 해결이 가능한 경우를 찾는다.
4. 3번을 만족하는 process가 존재하면, 모든 자원을 해당 process에게 할당해서 작업을 끝낼 수 있다는 의미이므로 해당 process의 상태를 finish로 바꾸고 해당 process가 갖고있던 원래 resource를 반환한다.
5. 위 작업을 반복해 모든 process가 finish 상태가 될 수 있다면 deadlock 상태가 아니고, 그렇지 않다면 deadlock 상태임을 의미

💡 safety algorithm과 다른 점은 4번에서 현재 process가 요청한 자원을 비교하느냐, 현재 process가 앞으로 필요한 모든 자원을 비교하느냐이다.

 

example

 

Q. 현재 상태가 deadlock 상태인가?

problem

multiple instance detection algorithm의 경우 시간 복잡도가 $O(N^3)$이다.

얼마나 자주 detection algorithm을 수행할 것인지도 선택

• 모든 resource request마다 : overhead가 커진다.
• 자원을 할당할 수 없는 request마다
• 특정 시간마다 주기적으로

Recovery

여러 recovery 방식이 존재 ⇒ 답은 없다.

 

Termination

1. deadlock 발생 시 모든 process 종료
2. deadlock 발생 시 deadlock cycle이 제거될 때까지 process를 1개씩 종료
   ⇒ “어떤 process를 먼저 제거할 것인가”도 문제가 된다.

Rollback

특정 state를 deadlock 상태 이전으로 돌린다.

⇒ 변수가 많아 rollback시켜도 deadlock과 동일한 상황이 연출되기 어렵다.

• starvation 현상이 발생하기도..
  ⇒ 동일한 state를 계속 rollback시키는데 계속 deadlock이 발생하게 되는 경우..

Avoidance vs Detection

Avoidance

• 최악의 상황을 가정 : 모든 process가 자신의 최대 resource를 요청하는 것을 가정
• 따라서 확률적으로 deadlock이 발생하기 어려움에도 불구하고 자원을 할당하지 않기 때문에 resource utilization이 낮아진다.
  ⇒ Prevention과 동일한 단점

Detection

• 최선의 상황을 가정 : 현재 process가 요청한 자원에 대해서만 가정
• deadlock detection algorithm의 overhead가 크다.

 

그래서 위 최신 OS에서는 deadlock에 대해 처리하지 않는다.

 

참고

- Operating System Concepts

- 운영체제, 한양대학교 강수용 교수님