[OS] DeadLock

DeadLock이란, 

이전의 Dinner-Philosipher 문제와 같이,

두 개 이상의 Task가 각각 Shared Resource를 점유하고 있고, 

각 Task는 서로가 점유하고 있는 Shared Resource를 필요로 하여,

상대방의 Task가 끝나기를 기다리고 있기에 결과적으론 아무것도 못하는 상태이다.

 

각 Task는 다음과 같은 순서로 Resource를 이용한다. 

• Request : Resource를 요청한다. (만약, 다른 Task가 먼저 점유하고 있다면 대기한다)
• Use : Task가 Resource를 할당받아, 작업을 수행한다.
• Release : Task가 Resource의 점유를 해제한다.

 

 

DeadLock Characterization

DeadLock 발생 조건

DeadLock이 발생하기 위해선 4가지 필요조건을 "모두" 충족시켜야 한다.

즉, 이 중 하나라도 만족시키지 못한다면, 교착상태는 발생하지 않는다.

• Mutual Exclusion (상호배제) : 하나의 Resource에 대해 하나의 Task만 점유가 가능하다.
• Hold and Wait (점유대기) : Task가 다른 Resource를 대기할 때, 자신이 가진 Resource를 소유한 채로 대기한다.
• No Preemption (비선점) : Task가 Resouce의 사용을 끝내고 스스로 반환하지 않는 이상, 중간에 점유권을 뺏을 수 없다.
• Circular Wait (순환대기) : 각 Task는 순환적으로 다음 Task가 요구하는 Resource를 가지고 있다. 

$T_1$, $T_2$, $T_3$의 Task와, $R_1$, $R_2$,  $R_3$의 Resouce가 있고,

각 숫자에 맞는 Resource를 점유하고 있다고 가정하자. 

$T_1$은 $R_2$를 요구하고, 

$T_2$은 $R_3$를 요구하고, 

$T_3$은 $R_1$를 요구하는 상황이 Circular Wait이다. 

Circular Wait의 경우,

Hold and Wait와 No Preemption이 만족해야 성립되기 때문에, 

위 4가지 조건은 서로 독립적인 조건들은 아니다.

 

Resource-Allocation Graphs

Resouce-Allocation Graphs는 Resouce와 Process간의 관계를 설명하는 그래프로, 

위 그래프는 DeadLock이 발생할지 예상할 수 있다.

 

해당 그래프의 노드는 2가지 타입이 있다. 

• P = {$P_1$, $P_2$, ..., $P_n$} 각각 Process를 의미한다.
• R = {$R_1$, $R_2$, ... , $R_n$} 각각 Resource의 타입을 의미한다. 

간선 역시 2가지 타입으로 나뉜다.

• $P_i$ 에서 $R_j$ : $P_i$가 $R_j$의 인스턴스를 request한다.
• $R_j$ 에서 $P_i$ : $R_j$의 인스턴스를 $P_i$에 Assignment한다.

$R_j$노드 내부의 점은 인스턴스를 의미하고,

점의 갯수는 $R_j$타입의 Resource의 갯수를 의미한다.

만약, graph에서 Cycle이 존재하지 않는다면, DeadLock은 발생하지 않는다. 

반면 Cycle이 존재하고,

"각 Resource Type에 하나의 인스턴스만 존재"하는 경우 DeadLock이 발생한다.

 

마지막으로 Cycle이 존재하고,

"각 Resource Type에 여러 개의 인스턴스가 존재"하는 경우 DeadLock의 가능성이 있다.

 

 

Methods for Handling DeadLocks

DeadLock을 제어하는 방법으로는 크게 2가지로 나눌 수 있다. 

• DeadLock이 발생하지 않도록 하는 방법 : Prevention & Avoidance
• DeadLock이 발생한 후에 처리하는 방법 : Detection & Recovery

 

Prevention

앞서 말했듯, DeadLock이 발생하기 위해선 4가지의 필요조건을 모두 충족시켜야 한다. 

이는 이 중 하나의 조건이라도 제거한다면 DeadLock을 사전에 방지할 수 있다.

 

Mutual Exclusion

Critical Section의 경우, 해당 조건을 만족하지 않으면 여러 Concurrency Problem이 발생한다. 

따라서, 공유자원이 있는 경우 해당 조건을 위반할 수 없다. 

 

Hold and Wait

한 Task가 수행되기 전에 모든 Resource를 할당하고 수행하면 Hold and Wait 조건을 제거할 수 있다.

 

No Preemption

어떤 Task가 요청하는 Resource가 바로 점유할 수 없는 Resource라면, 

해당 Task는 점유하고 있는 Resource들이 선점되게 할 수 있다. 

이를 통해, No Preemption을 위반할 수 있다.

 

Circular Wait

Resource를 순환 형태로 대기하지 않도록,

한쪽 방향으로만 Resource를 Request할 수 있어야 한다.

이는 모든 Resource Type을 정렬하여,

정렬된 순서로만 Resource를 Request하는 방식을 통해 Circular Wait 조건을 제거할 수 있다.

 

Prevention 단점

Prevention 해결 방법들은 Resource 사용의 효율성이 떨어지고, 비용이 많이 드는 단점이 있다.

 

Hold and Wait 조건의 제거를 예를 들면 다음과 같다. 

Task가 요구하는 Resource를 한 번에 파악하고, Resource에 대한 내용을 저장 및 복원하는 비용이 든다.

또한, Starvation 현상이 발생할 수 있다.

 

Avoidance

Avoidance는 데드락이 발생하지 않고 Resource를 할당할 수 있을 때 Resource를 할당하는 방식이다.

여기서, "데드락이 발생하지 않고 Resource를 할당할 수 있을 때"

시스템은 Safe State(안전 상태)에 있다고 말한다.

Safe State인지 아닌지는 추가적인 정보를 통해검사하게 된다.

 

반면, unsafe state에서는 데드락이 발생 가능성이 있는 거지, 필수로 발생하는 것은 아니다.

 

safe state를 판별하는 알고리즘은 Resource Type의 Instance가 하나인지 여러 개인지에 따라 나뉜다.

 

Single Instance Per Resrouce Type 

Resource Type마다 하나의 Instance가 있는 경우는

Resource Allocation Graph의 Cycle 존재 여부를 통해 판별한다. 

그래프에는 3가지 타입의 edge가 존재한다. 

• Claim Edge : 점선으로 표시되며, 미래에 Resource에 Request할 가능성이 있다는 것을 의미한다.
• Request Edge : Task가 해당 자원을 요청할 때
• Assignment Edge : Resource가 Task에 할당될 때

Claim Edge에서 요청이 들어오면 Reqeust Edge로 변경되며, 

Resource가 Release되면 Assignement Edge에서 Claim Edge로 변경되게 된다.

위의 그림에서 $P_2$ 가 $R_2$에 Request를 보내고, 

자원이 할당된다면(Assignment Edge),

Cycle이 형성된다. 

 

Single Instance Per Resource Type에서 

Cycle 형성은 DeadLock을 의미하기 때문에, 

unsafe state이다. 

따라서, Task의 Resouce 할당 요청은 거부된다.

 

 

반면, Resource Type에 여러 개의 Instance가 있다면, Banker's 알고리즘을 사용한다.

 

Detection and Recovery

Avoidance와 Prevention은 DeadLock이 발생하지 않도록 사전에 처리하는 방식이었다면, 

Detection과 Recovery는 DeadLock의 발생한 후에 이를 감지하고 처리하는 방식이다. 

 

Detection

Detection기법 역시 Resource Type마다 Single Instance냐 Multiple Instance냐에 따라 나뉜다.

single Instance Per Resource Type일 경우에는

Resource Alloction Graph를 활용하여, Cycle 존재여부를 통해 DeadLock을 판별한다.

 

Multiple Instance Per Resource Type일 경우에는 다른 알고리즘을 통해 DeadLock을 판별한다. 

 

Recovery

DeadLock을 Detection했다면, DeadLock 상태에서 벗어나기 위한 Recovery 기법을 사용한다.

Recovery는 크게 "Task Termination"과 "Resouce Preemption"으로 나뉠 수 있다. 

 

"Task Termination"은 말 그대로 DeadLock 상태에 있는 Process를 강제종료 시키는 방법이다. 

이는, DeadLock Task를 모두 종료시킬 수도 있고,

DeadLock이 Detection되지 않을 때까지 Task를 하나씩 종료시킬 수도 있다. 

(Single Instance Per Resource Type이라면 Cycle이 없어질 때까지 강제종료시킨다)

 

"Resource Preemption" 방법은

Task에 할당된 자원을 DeadLock이 Detection되지 않을 때까지

다른 Task에 할당해 주는 방식이다.

 

 

Referecne

위키피디아

• 교착상태

Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 9th』