교착 상태란?
운영체제가 다수의 프로세스나 스레드를 동시에 실행할 때, 여러 스레드가 한정된 자원을 사용하려고 경쟁할 수 있다. 이때 자원을 확보하지 못한 스레드는 대기 상태에 빠지게 된다. 이러한 대기 중인 스레드들이 서로 상대방이 가진 자원을 기다리면서, 모두가 더 이상 진행할 수 없는 상태에 빠지게 된다면 이를 교착 상태(Deadlock) 라고 한다.
교착 상태의 대표적인 비유는 “두 대의 기차가 교차로에서 서로 마주쳤을 때 둘 다 멈춰서 상대방이 움직이기를 기다리는 상황"이다.
교착 상태 발생의 네 가지 조건
교착 상태가 발생하려면 다음 네 가지 조건이 반드시 동시에 성립해야 한다.
상호 배제: 최소한 하나의 자원이 동시에 여러 스레드에 공유될 수 없어야 한다. 즉, 한번에 한 스레드만 자원을 사용할 수 있다.
점유하며 대기: 스레드가 최소한 하나의 자원을 확보한 상태에서, 추가로 다른 자원을 기다려야 한다.
비선점: 한 스레드가 자원을 점유하고 있을 때, 그 자원을 다른 스레드가 강제로 빼앗을 수 없어야 한다. 자원은 자발적으로만 반납된다.
순환 대기: 여러 스레드가 원형으로 서로 상대방이 가진 자원을 기다리는 구조가 만들어져야 한다.
이 네 가지 조건 중 하나라도 만족하지 않는다면 교착 상태는 발생할 수 없다.
자원 할당 그래프
교착 상태는 자원 할당 그래프(Resource Allocation Graph) 라는 방향 그래프로 표현할 수 있다. 여기에서 프로세스(스레드)는 원으로, 자원은 사각형으로 표현된다. 스레드가 자원을 요청하면 요청 간선이 추가되고, 자원이 할당되면 할당 간선이 추가된다.
- 사이클이 존재하지 않으면 교착 상태가 아니다.
- 자원이 하나의 인스턴스만 갖는 경우, 사이클이 존재하면 교착 상태이다.
- 자원이 여러 개의 인스턴스를 갖는 경우, 사이클이 존재하더라도 반드시 교착 상태는 아니다.
교착 상태 처리 방법
교착 상태를 다루는 방식은 크게 세 가지로 구분할 수 있다.
무시하기: 대부분의 운영체제가 사용하는 방법이다. 교착 상태가 드물게 발생하거나 관리 비용이 높을 때 채택하는 방식이다. 대표적인 예는 Windows나 Linux 운영체제다.
예방과 회피: 시스템이 교착 상태에 절대 빠지지 않도록 방지하거나 회피하는 방법이다. 예방은 앞서 언급한 4가지 조건 중 하나를 성립하지 못하도록 제한을 두는 것이고, 회피는 시스템이 교착 상태에 빠지지 않는 안전 상태를 유지하도록 자원을 할당한다.
탐지 및 복구: 교착 상태가 발생하면 이를 탐지하여 해결하는 방법이다. 자원 할당 그래프에서 사이클을 탐지하는 방식이 대표적이다. 탐지 후에는 스레드를 중지하거나, 스레드의 자원을 회수하는 방식으로 회복할 수 있다.
순환 대기 제거
현실적으로 교착 상태를 예방하는 방법 중 가장 유용한 방법은 순환 대기를 제거하는 것 이다. 이는 자원에 전체적인 순서를 부여하고, 그 순서대로 자원을 요청하도록 강제하는 것이다. 이렇게 되면 스레드들이 순환적으로 자원을 기다리는 상황을 막을 수 있다.
예를 들어, mutex 락에 대해 다음과 같은 순서를 정했다고 하자.
$$ f(\text{first\textunderscore mutex}) = 1,\quad f(\text{second\textunderscore mutex}) = 5 $$
스레드는 반드시 first_mutex를 먼저 요청하고 second_mutex를 요청해야 한다.
은행원 알고리즘
자원이 여러 개의 인스턴스를 가질 때 사용할 수 있는 대표적인 교착 상태 회피 알고리즘으로 은행원 알고리즘(Banker’s Algorithm) 이 있다. 이 알고리즘은 시스템의 상태가 안전 상태를 유지하는지 검사하여 자원 요청의 허용 여부를 결정한다.
은행원 알고리즘은 다음과 같은 자료구조를 이용한다.
- Available: 현재 사용 가능한 자원 개수
- Max: 각 스레드가 최대로 필요로 하는 자원 개수
- Allocation: 각 스레드에 현재 할당된 자원 개수
- Need: 각 스레드가 추가로 필요할 수 있는 자원 개수 (
Need = Max - Allocation)
스레드가 자원을 요청하면, 요청을 즉시 들어줬을 때 시스템이 안전 상태를 유지하는지를 확인한 후 할당을 결정한다.
교착 상태 복구 방법
교착 상태를 탐지했을 때 복구하는 방법은 다음과 같다.
- 프로세스 종료: 교착 상태에 빠진 프로세스를 중지하여 자원을 회수한다.
- 자원 선점: 프로세스로부터 자원을 회수하여 다른 프로세스에 제공하여 교착 상태를 해결한다.
어떤 프로세스를 중지하거나 어떤 자원을 회수할지는 시스템의 정책이나 비용을 고려하여 결정한다.