교착 상태(Deadlock)이란 프로세스나 스레드가 결코 일어날 수 없는 특정 이벤트를 기다리는 상태이다.
둘 이상의 프로세스나 스레드가 서로 점유하고 있는 자원을 기다릴 때, 무한 대기 상태에 빠지는 것을 말한다.
시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.
프로세스A와 프로세스B가 디스크와 프린터 자원을 얻어야 한다고 가정하자.
현재 프로세스A는 프린터를, 프로세스B는 디스크를 점유하고 있다.
그렇다면, 서로 원하는 자원이 상대방에서 할당되어 서로 놓지 않고 무한정 대기 상태에 빠지게 되는 것이다.
교착 상태 발생의 4가지 조건
교착 상태가 발생하는 4가지 조건은 다음과 같다. 4가지를 모두 성립해야 교착 상태가 발생한다.
- 상호 배제
자원은 한 번에 하나의 프로세스만 사용할 수 있다. - 점유와 대기
최소한 하나의 자원을 점유하고 있으면서, 다른 프로세스에 할당되어 사용하고 있는 자원을 점유하기 위해 대기한다. - 비선점
다른 프로세스에 할당되어 사용되고 있는 자원은 끝날 때까지 강제로 뺏을 수 없다. - 순환 대기
대기 프로세스들이 순환 형태로 자원을 대기하고 있다.
교착 상태 해결 방법
교착 상태를 해결하는 방법에는 무시, 예방, 회피, 회복 및 탐지가 있다.
교착 상태 무시
교착 상태가 드물게 발생하는 곳에서 자주 사용된다. 교착 상태가 드물게 발생하는 곳에서 해결하기 위해 비용을 지불한다면 더 효율성이 떨어지기 때문이다. 만약 교착 상태가 발생한다면, 사용자가 프로세스를 죽이거나 시스템 자체를 재부팅해야 한다. Window와 Unix에서 이러한 방법을 사용한다.
교착 상태 예방
위의 교착 상태 발생 조건 중 하나라도 발생하지 않게 예방하는 방법이다.
하지만, 자원 낭비가 심하기 때문에 사용하지 않는다.
- 상호 배제 부정
한 번에 여러 프로세스가 공유 자원을 사용할 수 있게 한다. - 점유와 대기 부정
프로세스가 작업 수행 전에 필요한 자원을 모두 요청하고 획득한다.
하지만, 이렇게 되면 자원의 효율성이 떨어지게 된다. - 비선점 부정
자원을 점유하고 있는 프로세스가 다른 자원을 요구할 때 가진 자원을 반납한다. - 순환 대기 부정
모든 자원에 순서를 부여해서 오름차순으로 자원을 요청할 수 있게 한다.
하지만, 이 조건을 사용하면 필요한 자원은 훨씬 오래전부터 할당받은 상태가 되어야 하므로 자원 낭비가 일어난다.
교착 상태 회피
교착 상태 예방 방법은 비효율적이다. 이를 보충하기 위해 나온 것이 교착 상태 회피 방법이다.
교착 상태 회피에는 중요한 2가지 개념이 있다. 안전 상태(Safe State)와 안전 순서(Safe Sequence)이다.
안전 상태
시스템의 프로세스들이 요청하는 모든 자원을 교착 상태를 발생시키지 않고 모두에게 할당해 줄 수 있다면 안전 상태라고 한다.
안전 순서
특정한 순서로 프로세스에 자원 할당, 실행, 종료들의 작업을 할 때 교착 상태가 발생하지 않는 순서를 안전 순서라고 한다.
회피 알고리즘은 자원 할당 후에도 시스템이 항상 안전 상태에 있을 수 있도록 할당하는 것이다.
대표적으로는 은행원 알고리즘이 있다. 은행원 알고리즘이란, 미리 설정된 모든 자원들의 할당량을 가지고 시뮬레이션해서 안전 상태에 들 수 있는지 검사한다. 즉, 대기 중인 프로세스들의 활동에 대해서 교착 상태의 가능성을 미리 조사한다.
하지만, 프로세스의 자원 할당량을 미리 알아야 한다는 단점이 있다.
교착 상태 회복 및 탐지
교착 상태 예방이나 회피를 사용하지 않으면, 교착 상태가 발생할 수 있다.
이때, 교착 상태를 탐지 및 회복하는 방법이다.
탐지 기법
자원 할당 그래프를 통해 교착 상태를 탐지한다.
교착 상태가 제거될 때까지 하나씩 프로세스를 중지한다.
회복 기법
교착 상태를 탐지 기법을 통해 발견 시에 교착 상태로부터 회복하기 위한 방법이다.
- 프로세스 종료 방법
- 교착 상태의 프로세스를 모두 중지한다.
- 교착 상태가 제거될 때까지 하나씩 프로세스를 중지한다.
- 자원 선점 방법
- 교착 상태의 프로세스가 점유하고 있는 자원을 선점해 다른 프로세스에게 할당한다. 해당 프로세스는 일시정지 된다.
- 우선순위가 낮은 프로세스나 수행 횟수가 적은 프로세스 위주로 프로세스 자원을 선점한다.
