데드락 이란

데드락(deadlock) 이란?
프로세스가 자원을 얻지 못해 다음 처리를 하지 못하는 상태

예를 들어 컴퓨터1 과 컴퓨터2가 리소스 A,B 둘 다를 얻어야 한다고 가정한다.  컴퓨터1 이 리소스 A를 얻고 컴퓨터2가 리소스 B를 얻었다면  이제  다른 리소스를 얻기위해 컴퓨터1은 리소스 B를, 컴퓨터2는 리소스 A를 기다리게 된다. 하지만 서로 원하는 리소스가 상대방에게 할당되어 있기 때문에 이 두 프로세스는 무한정 기다리게 되는데 이러한 상태을 DeadLock상태라고 한다.

 

데드락 발생 조건
데드락은 아래 네 가지 조건이 동시에 성립 할 때 발생한다. 즉, 아래의 네 가지 조건 중 하나라도 성립하지 않도록 만든다면 데드락을 해결할 수 있다.

상호 배제 (Mutual exclusion) :  자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다
점유 대기 (Hold and wait) : 최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 한다.
비선점 (No preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없어야 한다
순환 대기 (Circular wait) :프로세스의 집합 {P0, P1, ,…Pn}에서 P0는 P1이 점유한 자원을 대기하고 P1은 P2가 점유한 자원을 대기하고 P2…Pn-1은 Pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

데드락 처리
교착 상태 예방 및 회피 : 교착 상태가 되지 않도록 보장하기 위하여 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법
교착 상태 탐지 및 회복 : 교착 상태가 되도록 허용한 다음에 회복시키는 방법
교착 상태 무시 : 대부분의 시스템은 교착 상태가 잘 발생하지 않으며, 교착 상태 예방, 회피, 탐지, 복구하는 것은 비용이 많이 든다.

예방
교착 상태 발생 조건 중 하나를 제거함으로써 해결하는 방법
자원의 낭비가 심하다.
상호 배제 (Mutual exclusion) 부정 :여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.
점유 대기 (Hold and wait) 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 할당한다.
비선점 (No preemption) 부정 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 한다.
순환 대기 (Circular wait) 부정 :  자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다.

 

회피
-교착 상태가 발생하면 피해나가는 방법
-은행원 알고리즘 (Banker’s Algorithm)
자원할당 요청 -> 자원이 안전한지 체크 -> (안전하다면) 자원할당   -> (안전하지 않으면) 할당거부

 

탐지
-자원 할당 그래프를 통해 교착 상태 탐지
-자원을 요청할때마다 자원 할당 알고리즘을 실행하면 오버헤드 발생

회복
-교착 상태를 일으킨 프로세스를 종료하거나, 할당된 자원을 해제함으로써 회복

프로세스를 종료하는 방법
-교착 상태의 프로세스를 모두 중지
-교착 상태가 제거될 때까지 한 프로세스씩 중지

자원을 선점하는 방법
-교착 상태의 프로세스가 점유하고 있는 자원을 선점하여 다른 프로세스에게 할당하며, 해당 프로세스를 일시 정지 시키는 방법
-우선 순위가 낮은 프로세스, 수행된 횟수가 적은 프로세스 등을 위주로 프로세스의 자원을 선점한다.