[OS] 데드락 - Deadlock

데드락 하면 교통체증을 떠올린다. 서로의 차들은 먼저 가고 싶어하고, 그럴수록 차로는 지체돼, 아무것도 할 수 없게 되는 것이다. 정확히 말하면, 그림과 같이 4거리에서 각자의 교통체증이 해결될 때까지 기다리기만 하는 상태이다.

더 자세한 정의를 보면,

두 개 이상의 작업이 서로 상대방의 작업이 끝나기 만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.

결국 작업은 자동차고, 도로는 리소스, 그리고 이러한 교통 체증이 교착 상태, 즉 데드락(Deadlock)이 되는 것이다.

작업을 수행해야 하는 프로세스가 계속 대기 상태에만 머무는 것이다.

이러한 데드락 문제는 다중 프로세스 환경에서 발생하며 최대한 예방을 하더라도 교착 상태는 발생하게 된다.

교착 상태에 운영체제가 포함 되어 있을경우, 컴퓨터 자체가 먹통이 되는 문제도 생기게 된다.

데드락, 즉 교착 상태가 발생할 수 있는 4가지 조건이 있다.

이 중 하나라도 예방하지 못한다면 데드락은 발생할 수 있다.

이러한 조건들을 예방하는 방법은,

발생 조건	해결 방법
상호배제(Mutual exclusion)	상호 배제 조건을 제거한다. -> 자원 공유
점유대기(Hold and wait)	점유와 대기 조건을 제거한다. -> 한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구
비선점(No preemption)	비선점 조건 제거 -> 비선점 프로세스에 대해 선점 가능한 프로토콜 생성
순환대기(Circular wait)	순환 대기 조건 제거 -> 자원 유형에 따라 순서를 매긴다.

이런 것들이 있고, 데드락을 아예 회피하거나, 교착 상태로 걸렸을 경우, 회복하는 방법도 있다.

교착 상태를 회피 하는 방법에는

자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)

은행원 알고리즘 (Banker's algorithm)

등이 있고, 교착 상태를 회복(Recovery) 하는 방법은 데드락을 발생 원인의 프로세스를 종료시키거나, 모두 종료시키는 방법 등이 있다.

점프 점프