Deadlock이란, 옴짝달짝 못하는 상태를 의미한다. 직역을 하면 lock이 죽었다는 의미인데 의역을 하면 lock을 해주는 존재가 없어서 생기는 문제를 의미한다. 위의 그림의 예시를 보면 신호등이 존재하지 않아서 차량들이 제 갈길만 가려고 하다 보니 더 이상 움직일 수 없는 상태가 되어 있다. 이 처럼 Deadlock은 걸리게 되면 해결을 할 수가 없다. 따라서 OS에서도 Deadlock에 걸렸을 때 대처할 방법들을 마련해야 하고, 이에 대해 이번 posting에서 다뤄보도록 하겠다.

Deadlock

OS에서의 Deadlock은 자원을 두고 여러 process들이 서로 맞물려있는 상태를 의미한다.

이러한 상황이 deadlock을 가장 간단하면서 잘 설명할 수 있는 경우이다.

Characterization

Deadlock은 다음 4가지 condition이 동시에 발생할 때 걸린다.

• Mutual Exclusion
  : 오직 1개의 process만 resource를 사용할 수 있다.
• No Preemption
  : resource의 경우 이것을 들고 있는 process가 실행을 끝마치고 자발적으로 놓지 않는 이상 강제로 뺴앗을 수 없다.
• Hold and Wait
  : 적어도 1개 이상의 resource를 들고 있는 process는 다른 process가 들고 있는 자원을 필요로 할 때 갖고 있던 자원을 들고 있는 상태로 기다린다.
• Circular Wait
  

이 상황을 맨 처음에 교통정체 상황의 deadlock에 대입을 해보면 다음과 같다.

지금부터 deadlock을 해결하기 위한 방법에 대해 알아보도록 하겠다.

Resource-Allocation Graph

Graph의 정의는 $G=(V,E)$로 나타낼 수 있다. 이 때 $V$는 P (Process)와 R (Resource) 둘로 나눌 수 있고, $E$는 Request edge ($P_i \rightarrow R_j$)와 Assignment edge ($R_j \rightarrow P_i$)로 분류할 수 있다.
또한 표시는 다음과 같이 한다.

Example

먼저 첫 번째 예시를 보면 $P_1\rightarrow R_1\rightarrow P_2\rightarrow P_3$로 끝나고 cycle이 존재하지 않기 때문에 이 case의 경우는 deadlock이 아니다.

Basic Facts

• Cycle이 존재하지 않으면 Deadlock은 발생하지 않는다.
• Cycle이 존재한다고 해서 무조건 Deadlock에 걸리는 것은 아니다.
  - Resource type 별로 instance가 1개씩만 존재하는 경우 Cycle이 있다면 Deadlock에 걸린다.
  • Resource type 별로 instance가 1개보다 많은 경우 Cycle이 있어도 Deadlock의 가능성만 존재할 뿐 무조건 Deadlock에 걸리지는 않는다.

2번째 예시를 보면, 분홍색 line의 cycle 1개와 파란색 line cycle 총 2개의 cycle이 존재한다. 그러나 이 때 $R_2$의 instance가 2개이기 때문에 Deadlock의 가능성만 존재하는 상태이다. 그럼 Deadlock이 존재하는지 확인하기 위해서는 어떻게 해야할까?
나같은 경우는 직접 화살표를 따라가면서 Cycle이 생기는지 확인을 해보았다. 위의 예시같은 경우 다음과 같이 표현할 수 있다.

[Pink]
$R_2\rightarrow P_1\rightarrow R_1\rightarrow P_2\rightarrow R_3\rightarrow P_3\rightarrow R_2$
[Blue]
$R_2\rightarrow P_2\rightarrow R_3\rightarrow P_3\rightarrow R_2$

$R_2$의 instance가 2개임에도 2개의 route가 모두 cycle임이 확인 되었기 때문에 이 case는 Deadlock이다. 그렇다면, (#instance) == (#cycle)일까?

3번째 예시를 보겠다. 이번에도 Cycle이 존재하지만, $R_1$과 $R_2$의 instance가 2개씩 존재하고 지하철 2호선 신도림과 성수처럼 Cycle에서 뻗어나온 지선이 존재한다.

알맞은 비유인지는 모르겠지만 지하철 2호선에 비유를 하자면, 모든 역에 지하철(Process)이 정차해있고 승객(Resource)을 태워서 다음 역으로 이동해야 하는데, 지하철 역은 한 번에 한 대의 지하철만 수용 가능하기 때문에 앞의 열차가 이동을 하지 않으면 순환선의 경우 모든 열차가 이동을 할 수 없기 때문에 Deadlock이 걸린다. 위의 예시에서 지선이 있을 때 Deadlock이 걸리지 않는 이유를 2호선의 성수, 신도림역과 matching시키면 지하철 역마다 있는 지하철이 전부 내선순환, 외선순환 열차가 아니라 중간에 성수, 신도림행이 존재해서 차량기지로 빠져나갈 수 있는 경우 차량기지로 가면서 자원을 놓고 가기 때문에 뒤에 기다리던 열차가 이동할 수 있는 공간이 생기게 되고 Deadlock이 풀리게 되는 것이다.

이런 식으로 Deadlock을 해결할 수 있는 방법에는 여러가지 방법들이 존재한다. 지금부터 그 방법들에 대해 알아보고자 한다.

Methods for Deadlock Handling

Deadlock Handling 기법에는 총 3가지 방법이 존재한다.

1. 시스템이 절대로 Deadlock 상태가 되지 않도록 하는 방법
   • Deadlock Prevention
   • Deadlock Avoidance
2. Deadlock을 허용하되, Deadlock 상태가 되었을 때 원래 상태로 복구시키는 방법
   • Deadlock Detection
3. Deadlock 자체를 일어나도 일어나지 않은 것처럼 무시하는 방법
   - Deadlock Ignorance
   (Deadlock이 발생할 확률이 매우 낮기 때문에 Deadlock을 신경쓰면서 OS가 Deadlock을 handling 하는 것이 오히려 overhead가 더 크다.)

Deadlock Prevention

: Deadlock이 성립하기 위한 4가지 조건 (Mutual Exclusion, Hold and Wait, No Preemption, Circular wait) 중 아무거나 만족시키지 못하게 하는 방법

1. Mutual Exclusion
   : 공유 가능한 자원에는 요구되지 않기 때문에 애초에 이 조건을 만족시키지 못하게 만들 수 없다.
2. Hold and Wait
   : All or Nothing, 한국말로는 "모 아니면 도" 전략으로 가면 된다. Hold and Wait에 대해 되짚어 보면, process가 다른 process가 들고 있는 자원을 요청할 때 기존에 갖고 있던 자원을 들고 있는 상태로 대기를 하는 방법이다. Deadlock이 Hold and Wait에 의해 발생하게 되는 원인은 "Hold"에서 발생한다. 그렇기 때문에 만약 전부 다 확보 가능한 상태임이 확인 되면 한꺼번에 자원을 hold하고, 하나라도 확보 가능한 상태가 아니라면 아얘 들지 않도록 하면 Deadlock을 방지할 수 있을 것이다.
   예시를 통해 설명하자면, Resource가 1~3까지 존재한다고 할 때 만약 3번 resource가 확보 불가능한 상태라면 1, 2번이 확보가 가능하다고 하더라도 잡지 않는 것이고, 반대로 1~3까지 모두 확보 가능한 상태라면 한꺼번에 잡는 방법이다. 첫 번째 case의 경우 확보가 가능한 자원이 존재함에도 불구하고 확보 불가능한 자원의 존재로 인해 잡지 않기 때문에 Resource utilization이 떨어지게 된다. 또한 3번이 언젠가 확보 가능한 상태가 되었을 때 기존에 확보가 가능했던 1~2번이 그 때도 확보 가능한 상태라는 것이 보장되지 않기 때문에 Starvation 문제도 발생할 수 있다.
3. No Preemption
   : No Preemption의 경우 Preemption을 허용하면 된다. Hold and Wait에서 1,2번이 확보 가능하고 3번이 확보 불가능한 상태일 때 3번이 확보가 불가능한 상태임이 확인이 되면 강제로 확보 중이던 1,2번을 빼앗으면 된다. 이 때 빼앗긴 자원들은 대기중인 process의 자원 list에 추가가되고 요청한 자원과 빼앗겼던 자원들을 모두 확보했을 때 process가 재시작 하게 된다.
4. Circular Wait
   : 자원의 종류마다 고유한 번호를 부여한다. 그렇게 되면 1번을 들고 있는 process가 3번 자원을 요구하고 3번 자원을 들고 있는 process가 7번 자원을 요구할 때, 7번을 들고 있는 process가 1번 자원을 요구해서 생기는 cycle이 (기다리는 자원)$1<7$ (확보한 자원)이므로 존재할 수 없게 된다. (Backedge가 생성될 수 없다) 또한 1, 3, 7번 자원이 존재할 때, 3번이 확보 불가능한 상태라면 3번이 확보 가능해질 때까지 뒤에 있는 7번은 확보하지 않는다. 그러므로 이 방법 역시 Resource utilization이 떨어지게 된다.
   

Deadlock Avoidance

: Deadlock이 미래에 발생하지 않을 route로만 이동하는 방법으로, 미리 각각의 resource type에 대해 process가 필요로 하는 최대 개수를 선언한다.

• Safe state
  : 현재 상태에서 모든 process가 끝날 수 있는 종료 sequence가 존재하는 경우

  $<P_1,P_2, ...,P_n>$ is safe if for each $P_i$, the resources that $P_i$ can still request can be satisfied by currently available resources $+$ resources held by $P_j (j<i)$

  

  Basic Facts

  • Safe state이면 Deadlock에 걸리지 않는다
  • Unsafe state라고 해서 무조건 Deadlock에 걸리는 것은 아니다. (Cycle이 존재한다고 반드시 Deadlock에 걸리는게 아닌 것 처럼)
    $\Rightarrow$ 모든 process가 동시에 모든 resource type에 대한 최대량을 요구했을 때 발생

Algorithm

Case A : One instance per resource types = Resource Allocation Graph Algorithm

Edge	설명
Claim edge	$P_i\rightarrow R_j$ : $P_i$가 j type resource를 미래에 사용할 것이라고 선언
-------------------	--------------------------------------------------------------------------------------------
Request edge	Process가 실제로 자원을 요청했을 때 claim edge가 request edge로 전환됨
-------------------	--------------------------------------------------------------------------------------------
	Resource가 Process에게 할당되었을 때 request edge가 assignment edge로 전환됨.
Assignment edge	만약 process가 resource를 놓게 된다면 assignment edge는 claim edge로 바뀌게 됨
	claim edge에서 request edge로 전환되었을 때 cycle이 존재하지 않을 때만 전환됨

위의 그림을 보면 claim edge가 $P_1\rightarrow R_2$, $P_2\rightarrow R_2$ 2개 존재하고 $P_2\rightarrow R_1$의 request edge 1개와 $R_1\rightarrow P_1$의 assignment edge 총 4개의 edge가 존재한다. 지금 상태에서는 deadlock이 아니지만, 만약 2개의 claim edge가 하나는 assignment edge, 나머지 하나는 request edge로 바껴서 그림에서 분홍색 형광펜을 칠한 것 처럼 된다면 cycle이 형성되어 deadlock이 걸리게 된다. 따라서 edge를 전환했을 때 cycle이 생기지 않도록 해야 한다.

Case B: Multiple instances per resource types = Banker's Algorithm

Banker's algorithm의 경우 4개의 자료구조가 존재하고 process마다 미리 사전에 필요로 하는 최대 자원의양을 선언해서 현재 할당되어 있는 자원과 더 필요로 하는 자원끼리의 관계를 확인한다.

• Safety Algorithm
  

• Resource-Request Algorithm
  

  Banker's Algorithm을 예시로 확인해보자.
  
  $P_0$부터 $P_4$까지 할당되어 있는 양, 최대 요구량, 더 필요로 하는 양이 존재하고 Available한 양에 대해 Need가 Available 보다 적어서 Finish[i]=true로 바꿀 수 있는지 확인을 해보면 된다. 현재 available한 3 3 2에 대해 $P_1$이 1 2 2로 가능하기 때문에 $P_1$을 실행하고 끝난 뒤 Allocation에 할당되어 있던 2 0 0을 더해서 5 3 2가 현재 Available하다고 update 해준다. 이 과정을 모든 process에 대해 반복하면서 모든 process를 끝낼 수 있는 종료 sequence가 존재한다면 Safe state 로 판단하면 된다. 여기서는 $<P_1, P_3, P_4, P_2, P_0>$ sequence가 존재하기 때문에 safe state이다.
  

Deadlock Detection

Wait-for Graph

Process K가 Process J를 기다리고 있는 경우 $P_k\rightarrow P_j$로 표현한다. Wait-for graph의 경우 자원과 상관 없이 process의 상태에 대해서만 표현을 하기 때문에 Resource Allocation graph에 비해 graph의 edge가 획기적으로 감소한다는 장점이 있다.


알고리즘을 살펴보면 Safety algorithm과 굉장히 유사해보인다. 그러나 여기서 차이점은 Allocation 여부에 따라 Finish가 true인 process도 존재한다는 점이다. Safety algorithm에서는 모든 process의 finish를 false로 초기화 했지만, 여기서는 아무 자원도 갖고 있지 않는 process의 경우 자원을 반환하지 않기 때문에 이 process를 기다리는 다른 process도 존재하지 않아서 종료된 process 취급을 해주기 위해 할당된 자원이 없는 process의 finish를 true로 setting 해준다.
그 뒤의 과정은 safety algorithm과 동일하다.

예시로 확인을 해보면, 아까와 동일하게 process가 실행 가능한 경우 실행한 뒤 allocation에 할당되어 있던 자원을 반홚사면서 available에 더해주면 되는데, 여기서는 0 0 0이라고 되어있는 부분의 의미가 자원을 요구하지 않는다는 의미이므로 종료된 process 취급을해서 $P_0, P_2$에 할당되어 있던 자원을 available에 더해서 3 1 3에서 종료 sequence가 존재하는지를 확인해보면 된다. 확인해보면 $<P_0, P_2, P_3, P_1, P_4>$ sequence가 존재하기 때문에 safe state라는 것을 알 수 있다.

Process Termination

가장 무식한? 방법은 deadlock에 걸린 process를 전부 abort 처리하면 된다. 그러나 이 것 보다는 cycle 여부가 deadlock에 큰 지분을 차지하기 때문에 cycle을 없앨때까지 process를 하나하나씩 abort 처리해주는 것이 조금 더 효율적일 것이다.
이 때 process를 하나하나씩 abort할 때도 아무거나 하면 안되기 때문에 순서가 존재한다.

• Process priority
• Process가 얼마나 오래 실행되었고, 앞으로 얼마나 더 실행할 것인지
• Process가 사용했던 자원
• Process를 끝내기 위해 필요한 자원
• 종료 sequence를 생성하기 위해 필요한 process의 개수
• process가 interactive 인지 아니면 batch 인지 여부

Resource Preemption

1. cost를 최소화하는 희생양 선택
2. Rollback
   • safe state로 돌아가기
   • 돌아간 safe state에서 재시작
3. Starvation
   • 같은 process를 희생양으로 선택하는 과정을 반복
   • cost factor에 rollback 횟수를 추가해서 starvation 방지

이렇게 Deadlock에 대해 알아보았다. 양이 좀 많다보니 두서 없이 쓴 부분도 있고 최대한 이해한 대로 작성한거라 틀린 부분도 존재할 것 같다. 틀린 부분이 있으면 지적해주시면 감사드리겠습니다.

중간고사를 폭망해서 기말고사는 무조건 잘봐야 하는 내 상황이 처량하도다...