[OS-08] 교착상태

1. 교착 상태(Deadlock)의 개념

• 교착상태는 상호 배제에 의해 나타나는 문제점으로, 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 현상을 의미
• 교착상태는 하나 또는 둘 이상의 프로세스가 더 이상 계속할 수 없는 자원의 할당과 해제를 기다리고 있는 상태를 말함

2. 교착 상태 발생 조건

• 상호 배제(Mutual Exclusion) : 한 번에 한 개의 프로세스만이 공유 자원을 사용할 수 있어야 함
• 점유 및 대기(Hold and Wait) : 프로세스가 이미 자원을 갖고 있으면서 다른 자원의 할당을 요구
• 비선점(Non-Preemption) : 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없음 
• 환형 대기(Circular Wait) : 프로세스는 자신이 가지고 있는 자원을 점유하면서 앞이나 뒤에 있는 프로세스의 자원을 요구

3. 교착상태 해결 방법 - 예방 기법(Prevention)

• 교착 상태가 발생하지 않도록 사전에 시스템을 제어하는 방법으로, 교착 상태 발생의 4가지 조건 중에서 어느 하나를 제거함으로써 수행(자원낭비가 가장 심함)

- 상호 배제 조건의 부정

• 한 번에 여러 개의 프로세스가 공유 자원을 사용할 수 있게 함
• 공유 자원은 어느 한 시점에서 하나의 프로세서만이 사용할 수 있어야 하므로, 상호 배제 조건의 부정을 수행하는 것은 사용하기에 적절하지 않으며 실제로도 구현하지 않음

- 점유와 대기 조건의 부정

• 프로세스가 실행되기 전에 필요한 모든 자원을 할당하여 프로세스 대기를 없애거나 자원이 점유되지 않은 상태에서만 자원 요구 가능하게 함

- 비선점 조건의 부정

• 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고, 요구한 자원을 사용하기 위해 기다리게 함

- 환형 대기 조건의 부정

• 교착 상태의 예방을 위하여 각 자원 유형에 일련의 순서 번호를 부여함

4. 교착상태 해결 방법 - 회피 기법(Avoidance)

• 교착 상태가 발생할 가능성을 배제하지 않고 교착 상태가 발생하면 적절히 피해나가는 방법

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

• 은행원 알고리즘은 E.J. Dijkstra가 제안
• 각 프로세스에게 자원을 할당하여 교착 상태가 발생하지 않으며 모든 프로세스가 완료될 수 있는 상태를 안전 상태, 교착 상태가 발생할 수 있는 상태를 불안전 상태라 함
• 은행원 알고리즘을 적용하기 위해서는 자원의 양과 사용자(프로세스) 수가 일정
• 은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장

- 은행원 알고리즘 예

• 자원이 총 12개이고 현재 10개가 할당된 상태일 때 시스템이 안전상태가 되기 위해서
• B가 0 이면 A는 4
• B가 1 이면 A는 5
• B가 2 이면 A는 6
• 왜냐하면 남은 자원이 2(12-10)이기 때문에 추가 요구량은 2 이하여야 함

프로세스	현재 할당량	최대 요구량	추가 요구량
P1	2	5	3
P2	4	A	B
P3	4	8	4

5. 교착상태 해결 방법 - 발견 기법(Detection) 

• 시스템에 교착 상태가 발생했는지 점검하여 교착 상태에 있는 프로세스와 자원을 발견

6. 교착상태 해결 방법 - 회복 기법(Recovery)

• 교착 상태를 일으킨 프로세스를 종료하고 교착 상태의 프로세스에 할당된 자원을 회수하여 프로세스나 자원을 회복

※ 교착 상태에 빠진 프로세스들의 자원을 선점해야 되는 경우 고려해야 할 직접적 사항

• 자원을 선점할 희생자 프로세스를 선택하는 문제
• 복귀 문제
• 기아 현상 문제