교착상태(Deadlock)

작성자

교착상태(Deadlock)?

두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로 아무것도 완료되지 못하는 상태를 가리킨다.¹⁾
시스템은 절대로 교착 상태가 되지 않아야 한다.
시스템이 교착 상태가 되면 복구할 수 있어야 한다.
대부분의 운영 체제에선 교착상태를 무시하고 교착상태가 시스템에서 발생하지 않는 것처럼 가장한다.

교착상태 발생 조건

교착상태는 아래 4가지 조건이 동시에 충족될 때 발생한다.

1) 상호 배제(Mutual exclusion)

자원은 한 번에 한 프로세스만이 사용할 수 있어야 한다.

2) 점유 대기(Hold and wait)

프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.

3) 비선점(No preemption)

프로세스가 어떤 자원의 사용을 끝낼 때까지 프로세스의 자원을 뺏을 수 없다.

4) 순환 대기(Circular wait)

각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.

교착상태의 관리

1. 교착 상태의 예방

교착상태의 4가지 조건 중 한 가지를 제거하여 예방하는 방법이다.
자원 사용의 효율성이 떨어지고 비용이 많이 드는 문제점이 있다.
다른 문제를 발생시킬 가능성 또한 존재한다.

1) 상호 배제 조건의 제거

교착 상태는 두 개 이상의 프로세스가 공유 가능한 자원을 사용할 때 발생하는 것이므로 자원을 공유가 불가능하도록, 즉 상호 배제 조건을 제거하면 교착 상태를 예방할 수 있다.

2) 점유와 대기 조건의 제거

한 프로세스가 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법이다.
자원 과다 사용으로 인한 효율성이 저하된다.
프로세스가 요구하는 자원을 파악하는 데에 대한 비용, 자원에 대한 내용을 저장 및 복원하기 위한 비용이 든다.
기아 상태²⁾, 무한 대기가 발생할 수 있다.

3) 비선점(No preemption) 조건의 제거

비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.

4) 순환 대기(circular wait) 조건의 제거

자원 유형에 따라 순서를 매긴다.

2. 교착 상태의 회피

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

교착 상태 회피 알고리즘

자원 할당 그래프 알고리즘 (Resource Allocation Graph Algorithm)
- 자원 유형이 단일 일때 사용하는 알고리즘
은행원 알고리즘 (Banker's algorithm)
- 자원 유형이 여러 개 일때 사용하는 알고리즘
- 프로세스가 자원을 요구할 때 시스템은 자원을 할당한 후에도 안정 상태로 남아있게 되는지를 사전에 검사한다.
- 안정 상태에 있으면 자원을 할당하고, 그렇지 않으면 다른 프로세스들이 자원을 해지할 때까지 대기한다.

3. 교착 상태의 무시

예방 혹은 회피 기법을 프로그래밍해서 넣으면 성능에 큰 영향을 미칠 수 있게 된다.
교착상태 발생 확률이 낮은 경우 별다른 조치를 취하지 않는다.

4. 교착 상태의 발견

감시/발견을 하는 탐지 알고리즘으로 교착상태 발생을 체크하는 방식.
성능에 큰 영향을 미칠 수 있다.

참조

Operating System Concepts. Abraham Silberschatz, Peter B. Galvin, Greg Gagne 공저

각주

위키백과
프로세스의 우선순위가 낮아서 원하는 자원을 결코 할당받지 못하는 상태.