Deadlock (교착 상태)

교착상태란, 이미 점유하고 있는 공유 자원에 사용 요청을 하게 됐을 때, SJF나 Priority 등에 의해 무한 대기하게 됐을 때 교착상태가 됐다고 부릅니다. 교착상태는 다음 4가지의 필요 조건을 가집니다.

1. Mutual Exclusion (상호 배제)
2. Hold & Wait (점유와 대기)
3. Non - Preemption (비선점)
4. Circular Wait (순환 대기)

교착 상태를 처리하는 방법에는 다음 4가지가 있습니다.

1. Prevention (예방, 필요 조건 중 1가지 제거)
2. Avoidance (회피, Banker's Algorithm)
3. Detection & Recovery (탐지 및 회복)
4. X

1,2는 교착 상태가 발생하기 전에 하는 방법이고, 3, 4는 교착 상태 이후 하는 방법입니다.

먼저 Prevention입니다. Prevention의 경우는 다음으로 정리할 수 있습니다.

필요 조건	설명	해결책	문제점
Mutual Exclusion	혼자만 사용, 같이 사용 X	실제 pointer 대신 Spool과 같은 Virtual Pointer에 출력	모든 자원이 공유 가능하지는 않다.
Hold & Wait	한번에 하나의 자원 사용	자원 점유와 요청을 둘다 하거나, 점유와 요청 둘다 하지 않거나.	Starvation의 발생으로 자원 사용의 효율이 떨어짐.
Non - Preemption	비선점	Preemption	모든 자원이 Preemption 하지는 않음.
Circular Wait	자원할당 그래프에서 사이클을 이룸.	사이클이 없도록 설계 EX) 자원에 Unique Value를 부여.	Process들의 자원 사용 순서를 미리 알 수 없음.

 

다음으로 Avoidance 입니다. Avoidance는 요약하여 자원을 할당할 때, 돌려받을 수 있는 자원이라고 판단됐을 때 할당해주는 방법입니다.

 

EX)

Resource : 12

	Max	Allocate	Need
P1	10	5	5
P2	4	2	2
P3	9	2	7

 

할당한 자원은 총 9이므로, 현재 남은 자원(Available)은 3입니다.

이때, Available ≥ Need 라면, 자원을 할당하고 해당 프로세스가 종료되면 자원을 되돌려받습니다. 즉, Available += Allocate가 됩니다.

 

따라서 조건은 다음과 같습니다.

(Available ≥ Need) == false 라면, Reject.

(Available ≥ Need) == true 라면, Accept.

 

만일 P3에서 Need로 2를 했을 때, Accept로 가정하면, 돌려받는 자원이 없습니다. (프로세스가 종료되지 않으므로) 따라서 해당 상태는 unsafe state라고 합니다. (반대의 경우 safe state[안정 상태])

unsafe state가 됐다고 해서 꼭 deadlock에 빠지는 것은 아닙니다.

 

위처럼 safe state인지 판별하기 위해 banker's algorithm을 사용합니다.

banker's algorithm은 다음으로 정의됩니다.

1. work = available; Finish = (f, f, f, ... , f) // Finish의 길이는 프로세스의 수
2. Finish(i) = false; Need(i) ≤ work
3. work = work + allocate; Finish(i) = true;
4. 모든 i에 대해서 Finish(i) = true라면, safe state.

banker's algorithm은 최악의 경우일 때 자원을 받을 수 있는 순서가 있는지 판단하기에 중간에 프로세스가 자원할당을 해제하는 경우는 고려하지 않습니다. (Pessimistic Approach, 비관적 접근)

 

반대로 3번째 처리 방법인 detection algorithm은 다음으로 정의되는데 이 알고리즘은 요청이 0인 프로세스는 자원할당을 해제한다고 가정합니다. (Optimistic Approach, 낙관적 접근)

 

1. work = available
2. Finish[i] = false; Request[i] ≤ work
3. work = work + allocate[i]; Finish[i] = true;
4. Finish[i]가 false인 프로세스는 교착상태.

해당 알고리즘은 주기적으로 실행하거나, CPU의 활용률이 떨어질 때 실행됩니다.

 

Recovery의 경우는 교착상태일때, Victim이 될 프로세스를 선정하는 알고리즘에 의해 선택된 프로세스를 죽입니다.

 

마지막 방법인 X의 경우, 정말로 아무것도 하지않습니다.