DeadLock

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

DeadLock의 4가지 발생 조건

1971년 E.G.코프만 교수는 교착 상태가 일어나려면 다음과 같은 4가지 필요 조건이 충족해야 함을 보였다.

1. 상호 배제 (Mutual Exclusion)

• 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
• ex) 하나의 차량은 그 순간에 하나의 구간만 차지할 수 있다.

2. 점유 대기 (Hold and Wait)

• 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
• ex) 각각의 차량들이 도로에서 하나의 구간을 차지하면서 나아가기를 기다리고만 있다.

3. 비선점 (No preemption)

• 프로세스가 어떤 자원의 사용을 끝날 때까지 그 자원을 뺏을 수 없다.
• ex) 하나의 구간이 양보될 수 없는 상황, 즉 차량을 뺄 수 없는 상황이다.

4. 순환 대기 (Circular Wait)

• 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
• ex) 차량들이 서로를 기다리고 있다.

이 조건 중에서 한가지라도 만족하지 않으면 교착 상태는 발생하지 않는다. 위의 4가지 조건은 서로 완전히 독립적인 것은 아니다.

DeadLock 해결 방법

교착 상태의 관리

현재의 대부분의 운영 체제들은 교착 상태를 막는 것이 불가능하다. 교착 상태가 발생하면 여러 운영 체제들은 각각의 다른 비표준 방식들로 교착 상태에 대응하는데 대부분의 접근들은 4가지 코프만 조건들 중 하나를 막으며 동작한다. 코프만 조건 중 순환대기를 주로 막는다.

교착 상태의 예방

상호 배제 조건의 제거

• 교착 상태는 두 개 이상의 프로세스가 공유 불가능한 자원을 사용하기 때문에 발생하는 것이므로 공유 불가능이라는 조건을 제거하면 상호 배제 조건을 제거할 수 있다.

점유 대기 조건의 제거

• 한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법이다. 자원 과다 사용으로 인한 효율성, 프로세스가 요구하는 자원을 파악하기 위한 비용, 자원에 대한 내용을 저장/복원 하기 위한 비용, 기아상태, 무한 대기 등의 문제를 야기한다.

비선점 조건의 제거

• 비선점 프로세스에 대해 선점 가능한 프로토콜을 만든다.

순환 대기 조건의 제거

• 자원의 유형에 따라 우선순위를 부여한다.

이러한 해결 방법들은 자원 사용 효율성을 떨어트리고, 비용이 많이 든다.

교착 상태의 회피

자원이 어떻게 요청될지에 대한 추가 정보를 제공하도록 요구하는 것으로 시스템에 순환 대기가 발생하지 않도록 자원 할당 상태를 검사한다.

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

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