Deadlock

한정된 자원을 여러 프로세스가 동시에 사용하려고 할 때, 자원을 얻지 못하고 상대의 작업이 끝나기만을 기다리는 상태. 4가지 조건이 모두 성립해야 발생하며, 해결하려면 하나라도 성립하지 않도록 하면 해결할 수 있다.

 

<원인 4가지>

- 상호 배제(Mutual Exclusion) : 자원은 한 번에 한 프로세스만 사용 가능

- 점유 대기(Hold and Wait) : 최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용되고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 있어야 함

- 비선점 (No Preemption) : 다른 프로세스에 할당된 자원은 사용이 끝날 때 까지 강제로 빼앗을 수 없다.

- 순환 대기(Circular Wait) : 프로세스의 집합 P0...Pn에서 p(n-1)은 pn이 점유한 자원을 대기하며 Pn은 P0가 점유한 자원을 요구해야 한다.

 

<대처방법>

1. 예방 및 회피

예방 : 데드락 자체가 일어나지 않도록 예방

상호 배제 부정 : 여러 개의 프로세스가 공유 자원을 사용할 수 있도록 한다.

점유 대기 부정 : 프로세스가 실행되기 전 필요한 모든 자원을 미리 할당

비선점 부정 : 자원을 점유 중인 프로세스가 다른 자원을 요구할 때, 현재 점유 중인 자원을 반납하고 새로 요구하는 자원을 기다리게 함

순환 대기 부정: 자원에 고유한 번호를 할당하고, 번호 순서대로 자원을 요구하도록 한다. 주로 이 방법을 사용

 

회피 : 교착상태가 발생할 것 같으면 회피

은행원 알고리즘 : 자원요청 -> 안전 여부 체크 -> 안정 상태이면 할당, 아니라면 거부

 

2. 탐지 및 회복

탐지 : 자원 할당 그래프 알고리즘을 통해 데드락 탐지 후 해결

단, 자원 요청 마다 탐지 알고리즘을 수행하면 오버헤드 발생

자원 할당 그래프는 프로세스 Pi와 자원 Ri간의 자원 요청 또는 할당 상태를 나타내주는 그래프로 이를 통해 순환 대기 상태를 파악한다. 아래 그림은 P1 -> R1 -> P2 -> R5 -> P4 -> R2 -> P1 간 순환 대기 상태에 있는 그림.

회복 : 데드락 상태의 프로세스를 종료하거나 할당된 자원을 해제

1) 종료 : 데드락을 일으킨 프로세스를 모두 종료, 또는 데드락이 풀릴 때까지 한 프로세스씩 종료

2) 선점 : 데드락에 빠진 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당, 점유하던 프로세스는 일시 정지.

 

3. 무시 : 데드락은 자주 발생하지 않고, 이를 예방/회피/탐지/회복 하는 방법은 비용이 많이 드므로 무시

(Unix에서 사용)