DeadLock(교착상태)

목표

1.데드락의 개념에 대해서 이해한다.

2.데드락의 발생 조건에 대해서 이해한다. 

3.데드락을 예방할 수 있는 방법에 대해서 이해한다.

4.데드락이 회피 할 수 있는 방법에 대해서 이해한다.

5.데드락을 탐지 및 치료(?) 할 수  있는 방법에 대해서 이해한다. 

DeadLock(교착상태)

데드락이란 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있는 상태이기 때문에 결과적으로 아무것도 완료되지 못하는 상태이다. 예를 들어 사다리가 있고 두 사람이 각각 위 아래쪽에 위치해있다고 가정해보자. 각자 반대방향으로 움직이려고 한다면, 두 사람은 서로 상대방이 사다리를 비켜줄 때 까지 하염없이 사다리에서 기다리는것 처럼 다중 프로그래밍에서 교착상태는 흔히 발생할 수 있으며 데드락에 대한 해결방법은 아직 없는 상태이다. 

데드락의 발생하기 위한 필요조건

다음과 같은 네 가지의 조건을 모두 충족시킬 때 교착상태가 발생할 수 있다.

1.Mutual Exclusion(상호배제) : 프로세스들이 서로 필요로 하는 자원에 대해 배타적으로 통제권을 갖는다. 즉, 서로 하나의 자원에 대해서 요구한다는 것이다. 

2.Hold and Wait(점유대기) : 프로세스가 자원을 할당한 채로, 다른 자원을 기다린다. 

3.No Preemption(비선점) : 프로세스가 어떤 자원의 사용이 끝나기 전 까진, 그 자원을 반환할 수 없다.

4.Circular Wait(순환대기) : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다. 

*순환대기 조건은 점유대기와 비선점 조건을 충족해야 발생할 수 있기 때문에 4개의 조건들이 독립적인건 아니다.

데드락을 예방할 수 있는 방법(Deadlock Prevention)

현재의 대부분 OS는 교착상태를 피할 수 없다. 데드락 발생조건의 4가지 중 하나를 막음으로써 예방하게 된다. 각 조건들을 다시 살펴보자

1.Mutual Exclustion(상호배제) : 여러 프로세스가 공유 자원을 사용토록 허용하는것이다.

2.Hold and Wait(점유대기) : 프로세스가 실행되기 전에 필요한 자원들을 모두 미리 할당하는 것이다. 프로세스가 스케쥴러에서 벗어나면 다른 프로세스가 자원을 요구하게 된다. 따라서 어떤 자원이 필요한지 파악해야 되고 자원에 대한 내용을 저장하고 복원해야 하고 기아상태 및 무한대기의 문제점이 있다.

3.No Preemption(비선점) : 비 선점 프로세스에 대해서 선점 가능한 프로토콜을 만들어 준다.

4.Circular Wait(순환대기) : 자원 유형에 따라 순서를 매겨서 순서대로 할당받게 한다.

*Prevention은 대부분 자원의 소모가 크고 시스템 부하가 큰 방법들이다.

데드락을 회피하는 방법(Deadlock Avoidance)

자원이 어떻게 요청될지에 대한 추가정보를 제공하도록 요구하는 것으로, 시스템에 Circular Wait가 발생하지 않도록 시스템을 검사한다.

시스템이 safe하다는 뜻은 프로세스가 자원을 요청하면 즉시 자원을 할당해 줄 수 있는 상태를 말한다. unsafe한 상태를 만들지 않으려는게 핵심이다.

리소스가 single instance일 경우 Resource Allocation Graph를 활용하여 싸이클이 발생할 request를 미리 블록할 수 있다.-> Resource Allocation Graph Algorithm

만약 리소스가 multiple instance일 경우 프로세스별로 리소스 사용 형태를 미리 정의하여 unsafe가능성 여부를 검사한다. -> Banker's Algorithm

데드락의 탐지 및 회복(Deadlock Detection and Recovery)

시스템을 감시하는 알고리즘을 통하여 교착상태를 감지한다. 시스템의 자원할당 그래프(Resource Allocation Graph)로 교착상태를 검출한다.

<자원 할당 그래프>

Pi -> Rj의 간선은 프로세스가 자원을 요청한 상태이며, Rj->Pi의 간선은 프로세스에게 할당된 자원을 뜻한다. 

당연히 자원을 요청할 때 마다 데드락 탐지 알고리즘을 실행하면 상당한 오버헤드가 발생한다.

그래서 때로는 데드락의 발생 확률이 비교적 낮을 경우 무시하기도 한다.

Recovery(회복)

데드락을 발생시킨 프로세스를 강제 종료시키거나, 할당된 자원을 해제하여 교착상태로부터 회복한다.

교착상태가 풀릴때 까지 한개씩 프로세스를 종료시키거나, 데드락과 관련된 모든 프로세스를 종료시키는 방법이 있다. 

참고

http://includestdio.tistory.com/12

http://jwprogramming.tistory.com/12

http://raisonde.tistory.com/entry/Deadlock%EC%9D%98-%EB%B0%9C%EC%83%9D-%EC%A1%B0%EA%B1%B4%EA%B3%BC-%ED%95%B4%EA%B2%B0%EB%B2%95

https://ko.wikipedia.org/wiki/%EA%B5%90%EC%B0%A9_%EC%83%81%ED%83%9C