교착 상태(Deadlock)란?
교착 상태(deadlock)는 두 개 이상의 프로세스가 각자 보유한 자원을 서로 요구하면서, 어느 쪽도 자원을 내놓지 않아 실행을 영원히 완료하지 못하는 상황을 의미합니다.
위 다이어그램을 살펴보면, 프로세스 1은 자원 1을 점유한 상태에서 자원 2를 필요로 하고, 프로세스 2는 자원 2를 점유한 상태에서 자원 1을 필요로 합니다. 두 프로세스 모두 상대방이 가진 자원이 있어야 작업을 끝낼 수 있지만, 누구도 자신의 자원을 반납할 의사가 없기 때문에 프로세스 1과 프로세스 2는 교착 상태에 빠지게 됩니다.
코프먼 조건(Coffman Conditions)
교착 상태는 다음 네 가지 코프먼 조건이 모두 참일 때에만 발생합니다. 이 조건들은 반드시 상호 배타적일 필요는 없습니다.
1. 상호 배제(Mutual Exclusion)
한 번에 오직 하나의 프로세스만 점유할 수 있는 자원이 존재해야 합니다. 아래 다이어그램에서 자원 R1은 단 하나의 인스턴스만 존재하며, 프로세스 P1만이 이를 점유하고 있습니다.
2. 점유와 대기(Hold and Wait)
프로세스가 이미 여러 자원을 점유한 상태에서, 다른 프로세스가 보유 중인 추가 자원을 계속 요청할 수 있어야 합니다. 아래 예시에서 프로세스 P1은 자원 R1과 R2를 점유한 채, 프로세스 P2가 보유한 자원 R3를 요청하고 있습니다.
3. 비선점(No Preemption)
자원을 강제로 빼앗을 수 없어야 합니다. 자원은 해당 프로세스가 자발적으로 반납할 때만 해제됩니다. 아래 다이어그램에서 프로세스 P1은 프로세스 P2로부터 자원 R3를 강제로 선점할 수 없으며, P2의 실행이 끝난 후 자발적으로 반납할 때까지 기다려야 합니다.
4. 순환 대기(Circular Wait)
프로세스들이 원형 사슬 형태로 서로의 자원을 기다리는 구조가 만들어져야 합니다. 즉, 첫 번째 프로세스가 두 번째 프로세스의 자원을 기다리고, 두 번째 프로세스는 세 번째 프로세스의 자원을 기다리며, 마지막 프로세스는 다시 첫 번째 프로세스의 자원을 기다리는 순환 고리가 형성됩니다. 예를 들어 프로세스 P1은 자원 R1을 할당받은 상태에서 R2를 요청하고, 프로세스 P2는 자원 R2를 할당받은 상태에서 R1을 요청하여 순환 대기 루프가 만들어집니다.
교착 상태 탐지(Deadlock Detection)
자원 스케줄러(resource scheduler)는 각 프로세스에 할당된 모든 자원을 지속적으로 추적하기 때문에 교착 상태를 탐지할 수 있습니다. 교착 상태가 감지되면 다음 방법으로 해결할 수 있습니다.
- 교착 상태에 연루된 모든 프로세스를 강제 종료합니다. 다만 이 방법은 프로세스가 지금까지 진행한 모든 작업이 사라진다는 점에서 바람직하지 않습니다.
- 일부 프로세스로부터 자원을 선점하여 다른 프로세스에 재할당함으로써, 교착 상태가 풀릴 때까지 반복합니다.
교착 상태 예방(Deadlock Prevention)
교착 상태는 발생하기 전에 미리 막는 것이 가장 좋습니다. 따라서 시스템은 트랜잭션을 실행하기 전에 엄격하게 검사하여 교착 상태로 이어질 가능성이 있는지 확인합니다. 교착 상태를 유발할 가능성이 조금이라도 있다면 해당 트랜잭션은 실행되지 않습니다.
타임스탬프(timestamp)를 활용해 교착 상태 발생을 방지하는 대표적인 기법은 다음 두 가지입니다.
대기-사망(Wait-Die) 기법
트랜잭션 T1이 트랜잭션 T2가 보유한 자원을 요청하는 경우, 다음 두 가지 상황 중 하나가 발생합니다.
- TS(T1) < TS(T2) — T1이 T2보다 오래된 트랜잭션이라면(시스템에 먼저 진입했다면), T2의 실행이 끝나 자원이 반환될 때까지 대기하는 것이 허용됩니다.
- TS(T1) > TS(T2) — T1이 T2보다 최신 트랜잭션이라면, T1은 강제 종료(kill)되고 나중에 동일한 타임스탬프로 재시작됩니다.
부상-대기(Wound-Wait) 기법
트랜잭션 T1이 트랜잭션 T2가 보유한 자원을 요청하는 경우, 다음 두 가지 상황 중 하나가 발생합니다.
- TS(T1) < TS(T2) — T1이 T2보다 오래된 트랜잭션이라면, T2를 롤백(부상, wound)시킬 수 있습니다. 그런 다음 T1이 자원을 가져가 실행을 완료하고, T2는 나중에 동일한 타임스탬프로 재시작됩니다.
- TS(T1) > TS(T2) — T1이 T2보다 최신 트랜잭션이라면, T2의 실행이 끝날 때까지 대기하는 것이 허용됩니다.
교착 상태 회피(Deadlock Avoidance)
교착 상태가 발생한 후 조치를 취하는 것보다 애초에 발생하지 않도록 회피하는 것이 더 바람직합니다. 이때 대기 그래프(wait-for graph)를 활용할 수 있습니다. 다만 데이터베이스 규모가 커질수록 그래프가 매우 복잡해지기 때문에, 소규모 데이터베이스에서만 실용적으로 사용할 수 있습니다.
대기 그래프(Wait-for Graph)
대기 그래프는 자원과 트랜잭션 간의 관계를 시각적으로 보여주는 도구입니다. 트랜잭션이 자원을 요청하거나 이미 보유하고 있다면, 그 관계가 대기 그래프상의 간선(edge)으로 표현됩니다. 대기 그래프에 사이클(cycle)이 존재한다면 시스템에 교착 상태가 발생했을 가능성이 있고, 사이클이 없다면 교착 상태가 없다고 판단할 수 있습니다.
교착 상태 무시 — 타조 알고리즘(Ostrich Algorithm)
타조 알고리즘은 이름 그대로 교착 상태를 그냥 무시하고 "절대 발생하지 않을 것이다"라고 가정하는 전략입니다. 일부 시스템에서는 교착 상태가 매우 드물게 발생하기 때문에, 이를 처리하는 비용이 무시하는 비용보다 오히려 큽니다. 따라서 교착 상태가 발생하지 않는다고 가정하고 운영하다가, 우연히 발생하더라도 시스템을 재부팅하는 방식으로 대응합니다.