- 교착 상태(deadlock)란?
교착 상태란 둘 이상의 프로세스가 서로 가진 한정된 자원을 요청하는 상태이다.
즉 두 개 이상의 작업이 서로의 작업이 끝나기를 기다리고 있어 결과적으로 아무것도 완료하지 못하는 상태를 말한다. 때문에 프로세스가 진전되지 못하고 모든 프로세스가 대기 상태가 된다.
교착 상태가 일어나려면 아래의 네 가지 필요 조건을 충족시켜야 한다.
1. 상호배제 : 프로세스들이 필요로 하는 자원에 대해 배타적인 통제권을 요구한다.
2. 점유대기 : 프로세스가 할당된 자원을 가진 상태에서 다른 자원을 기다린다.
3. 비선점 : 프로세스가 어떤 자원의 사용을 끝낼 때까지 그 자원을 뺏을 수 없다.
4. 순환대기 : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있다.
이 4가지 조건 중 하나라도 만족하지 않으면 교착 상태는 발생하지 않는다.
순환대기 조건은 점유대기 조건과 비선점 조건을 만족해야 성립하는 조건으로 이 4가지 조건이 완전히 독립적이진 않다.
교착 상태를 처리하는 방법에는 3가지가 있다.
1. 교착 상태 예방 및 회피 : 교착 상태가 되지 않도록 하기 위해 교착 상태를 예방하거나 회피하는 프로토콜을 이용하는 방법이다.
➡ 교착 상태 예방
교착 상태 예방 방법에는 상호배제 조건의 제거, 점유돠 대기 조건의 제거, 비선점 조건의 제거, 환형 대기 조건의 제거 방법이 있다.
상호배제 조건의 제거 : 공유 불가능한, 상호 배제 조건을 제거하여 교착 상태를 해결한다.
점유와 대기 조건의 제거 : 한 프로세스에 수행되기 전에 모든 자원을 할당시키고 나서 점유하지 않을 때에는 다른 프로세스가 자원을 요구하도록 하는 방법으로 효율성 문제와 비용 문제, 기아 상태, 무한 대기 등의 문제점이 있다.
비선점 조건의 제거 : 자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 점유하고 있는 자원을 반납하고 비선점 프로세스에 대해 선점 가능한 프로토콜을 만들어 준다.
환형 대기 조건의 제거 : 자원을 선형 순서로 분류하고 자원 유형에 따라 고유 번호를 할당하여 순서를 매긴다. 각 프로세스는 현재 점유한 자원의 고유 번호보다 앞이나 뒤 어느 방향으로만 자원을 요구하도록 한다.
➡ 교착 상태 회피
교착 상태 회피 방법에는 자원 할당 그래프 알고리즘과 은행원 알고리즘이 있는데 주로 은행원 알고리즘(Banker's Algorithm)이 사용된다.
은행원 알고리즘 : 은행에서 모든 고객의 요구가 충족되도록 현금을 할당하는 데서 유래한 기법으로 병렬 수행 프로세스 간의 교착 상태를 방지하기 위한 방법이다. 프로세스가 자원을 요구할 때 시스템이 자원을 할당한 후에도 안정한 상태인지 사전에 검사하여 교착 상태를 회피하는 기법이다.
은행원 알고리즘은 프로세스의 모든 요구를 유한한 시간 안에 할당하는 것을 보장한다.
2. 교착 상태 탐지(발견) 및 회복 : 교착 상태가 발생했는지 점검하고 교착 상태에 있는 프로세스와 자원을 발견하고 교착 상태를 일으킨 프로세스를 종료하거나 프로세스에 할당된 자원을 선점하여 프로세스나 자원을 회복한다.
교착 상태 탐지(발견)에는 교착 상태 발견 알고리즘과 자원 할당 그래프 등을 사용할 수 있다.
➡ 교착 상태 회복
교착 상태 회복 기법에는 프로세스 종료, 자원 선점 방법이 있다.
프로세스 종료 : 교착 상태에 있는 프로세스를 종료하는 방법으로 교착 상태에 있는 모든 프로세스를 종료하는 방법과 프로세스들을 하나씩 종료하면서 교착 상태를 해결하는 방법이 있다.
자원 선점 : 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에 할당하여 해당 프로세스를 일시적으로 멈추는 방법이다. 우선순위가 낮은 프로세스, 수행된 정도가 적은 프로세스, 사용되는 자원이 적은 프로세스 등을 위주로 해당 프로세스의 자원을 선점한다.
3. 교착 상태 무시 : 대부분 교착 상태가 잘 발생하지 않기에 교착 상태 예방, 회피, 탐지, 복구는 비용이 많이 든다. 또 예방 또는 회피를 프로그래밍해서 넣으면 성능이 큰 영향을 미칠 수 있다. 때문에 교착 상태의 발생 확률이 비교적 낮으면 별 다른 조치를 취하지 않는다.
