문서의 각 단락이 어느 리비전에서 마지막으로 수정되었는지 확인할 수 있습니다. 왼쪽의 정보 칩을 통해 작성자와 수정 시점을 파악하세요.

교착 상태 발생 | |
정의 | |
영문 용어 | Deadlock |
발생 조건 | 상호 배제, 점유와 대기, 비선점, 순환 대기 (4가지 조건이 동시에 성립) |
주요 발생 영역 | |
해결 방법 분류 | 예방, 회피, 탐지 및 복구, 무시 |
상세 정보 | |
상호 배제 | 한 번에 한 프로세스만 자원을 사용할 수 있음 |
점유와 대기 | 자원을 보유한 상태에서 다른 프로세스가 점유한 자원을 대기 |
비선점 | 다른 프로세스가 강제로 자원을 빼앗을 수 없음 |
순환 대기 | 대기 중인 프로세스들이 순환 형태로 서로를 기다리는 상태 |
예방 방법 | 4가지 조건 중 하나를 부정 (예: 자원을 모두 할당하거나, 선점 가능하게 설계) |
회피 방법 | 은행원 알고리즘 등을 사용해 안전한 상태에서만 자원 할당 |
탐지 방법 | 자원 할당 그래프 등을 이용해 교착 상태 발생 여부를 주기적으로 확인 |
복구 방법 | 프로세스 종료 또는 자원 선점을 통해 상태를 해결 |
관련 개념 | |
주요 예시 | |

교착 상태는 둘 이상의 프로세스나 스레드가 서로가 가진 자원을 기다리며 무한정 대기하는 상태를 말한다. 이는 운영체제나 분산 시스템에서 자원을 관리할 때 발생할 수 있는 심각한 문제이다.
교착 상태가 발생하면 관련된 모든 프로세스의 실행이 중단되고, 시스템의 성능이 저하되거나 특정 기능이 완전히 마비될 수 있다. 이 상태는 일단 발생하면 외부의 개입 없이는 해결되지 않는다는 특징을 가진다.
이 문제는 에츠허르 데이크스트라와 같은 학자들에 의해 1960년대부터 본격적으로 연구되기 시작했다. 이후 자원 할당 그래프나 은행원 알고리즘과 같은 다양한 탐지, 예방, 회피 기법이 개발되었다.

교착 상태가 발생하기 위해서는 네 가지 조건이 동시에 성립해야 한다. 이 조건들은 에즈거 데이크스트라를 비롯한 초기 컴퓨터 과학자들에 의해 정립되었다. 하나라도 만족되지 않으면 교착 상태는 발생하지 않는다.
첫째, 상호 배제 조건이다. 이는 최소한 하나의 자원이 비공유 모드로 점유되어야 함을 의미한다. 즉, 한 번에 하나의 프로세스만이 그 자원을 사용할 수 있고, 다른 프로세스들은 그 자원이 해제되기를 기다려야 한다. 공유 가능한 자원만 존재하는 경우에는 이 조건이 성립하지 않아 교착 상태가 발생하지 않는다.
둘째, 점유와 대기 조건이다. 프로세스가 현재 일부 자원을 보유한 상태에서, 다른 프로세스가 보유한 추가 자원을 얻기 위해 대기해야 한다. 프로세스가 필요한 모든 자원을 한꺼번에 요청하고 할당받는 방식(예: 모든 자원을 미리 할당)을 사용하면 이 조건을 깰 수 있다.
셋째, 비선점 조건이다. 프로세스에 할당된 자원은 그 프로세스가 사용을 끝내고 자발적으로 해제하기 전에는 강제로 빼앗을 수 없다. 만약 선점이 가능하다면, 대기 중인 프로세스의 자원을 다른 프로세스로부터 빼앗아 할당할 수 있으므로 순환 대기 상태가 깨질 수 있다.
넷째, 순환 대기 조건이다. 대기 중인 프로세스들의 집합 {P1, P2, ..., Pn}에서 P1은 P2가 보유한 자원을, P2는 P3가 보유한 자원을, ..., Pn은 P1이 보유한 자원을 기다리는 폐쇄된 순환 체인이 형성되어야 한다. 자원에 순서를 부여하여 모든 프로세스가 그 순서대로만 자원을 요청하도록 하면 이 순환 고리를 예방할 수 있다.
이 네 가지 조건은 다음과 같이 정리할 수 있다.
조건 | 설명 | 예방/회피 방법 예시 |
|---|---|---|
상호 배제 | 자원이 비공유 모드로만 사용 가능함. | 자원을 공유 가능하게 설계[1]. |
점유와 대기 | 자원을 보유한 채 다른 자원을 대기함. | 프로세스 시작 시 필요한 모든 자원을 한꺼번에 할당. |
비선점 | 할당된 자원을 강제로 빼앗을 수 없음. | 필요한 자원이 즉시 할당되지 않으면 기존 자원을 모두 해제. |
순환 대기 | 프로세스 간에 자원을 기다리는 순환 고리가 형성됨. | 모든 자원에 번호를 부여하고, 오름차순으로만 자원 요청. |
상호 배제는 교착 상태가 발생하기 위한 네 가지 필요조건 중 첫 번째 조건이다. 이 조건은 한 번에 하나의 프로세스만이 특정 자원을 사용할 수 있어야 함을 의미한다. 즉, 해당 자원은 공유될 수 없고, 이미 사용 중인 자원은 다른 프로세스가 접근하거나 사용하는 것이 허용되지 않는다.
상호 배제 조건이 필요한 자원의 대표적인 예는 프린터, 테이프 드라이브, 또는 공유 데이터베이스의 특정 레코드와 같은 비공유 자원이다. 예를 들어, 프린터는 한 순간에 하나의 인쇄 작업만을 처리할 수 있으므로, 한 프로세스가 프린터를 점유하고 있으면 다른 프로세스는 그 작업이 끝날 때까지 기다려야 한다.
만약 모든 자원이 공유 가능하다면, 교착 상태는 발생하지 않는다. 여러 프로세스가 동시에 같은 자원을 사용할 수 있기 때문에, 한 프로세스가 자원을 점유해 다른 프로세스가 무한정 기다리는 상황이 생기지 않기 때문이다. 따라서 상호 배제 조건은 교착 상태를 가능하게 하는 근본적인 토대 중 하나로 작용한다.
점유와 대기는 교착 상태가 발생하기 위한 네 가지 필요조건 중 하나이다. 이 조건은 하나 이상의 프로세스가 현재 일부 자원을 보유(점유)한 상태에서, 다른 프로세스가 보유하고 있는 추가 자원을 얻기 위해 대기해야 하는 상황을 의미한다.
구체적으로, 프로세스 A가 프린터와 같은 자원 X를 할당받아 사용 중인 상태에서, 스캐너인 자원 Y도 필요하게 되었다고 가정하자. 만약 자원 Y가 이미 프로세스 B에 의해 점유되어 있다면, 프로세스 A는 자원 Y가 해제되기를 기다리면서 대기 상태에 들어간다. 이때 프로세스 A는 자신이 이미 보유한 자원 X를 해제하지 않은 채로 대기한다. 이러한 "자원을 잡은 채로 다른 자원을 기다리는" 상황이 점유와 대기의 전형적인 예이다.
이 조건이 없으면 교착 상태는 발생하지 않는다. 예를 들어, 프로세스가 필요한 모든 자원을 사전에 한꺼번에 요청하고 할당받아야만 실행을 시작하도록 강제하거나, 프로세스가 새로운 자원을 요청하기 전에 현재 보유 중인 모든 자원을 먼저 반납하도록 하는 정책을 적용하면 점유와 대기 조건을 제거할 수 있다. 그러나 이러한 방법은 자원 활용도를 저하시키거나 프로세스의 실행을 지연시킬 수 있는 단점이 있다[2].
비선점은 교착 상태가 발생하기 위한 네 가지 필요조건 중 하나이다. 이 조건은 이미 할당된 자원을 다른 프로세스가 강제로 빼앗을 수 없음을 의미한다. 즉, 자원을 점유하고 있는 프로세스가 자발적으로 그 자원을 반환하기 전까지는, 다른 프로세스나 운영체제가 그 자원을 강제로 회수하여 다른 프로세스에 할당할 수 없다.
대부분의 상호 배제가 필요한 자원은 비선점 자원의 특성을 가진다. 예를 들어, 프린터나 테이프 드라이브와 같은 물리적 장치, 또는 공유 메모리의 특정 임계 구역에 대한 접근 권한은 일반적으로 비선점적이다. 한 프로세스가 프린터를 사용하여 문서를 출력하는 중이라면, 그 출력 작업이 완료되기 전에는 운영체제가 프린터 사용권을 강제로 중단시켜 다른 프로세스에 넘겨줄 수 없다. 만약 자원이 선점 가능했다면, 교착 상태에 빠진 프로세스로부터 자원을 강제로 회수하여 다른 대기 중인 프로세스에 할당함으로써 순환 대기 고리를 끊고 교착 상태를 해결할 수 있었을 것이다.
비선점 조건을 제거하여 교착 상태를 예방하는 것은 시스템 설계에 제약을 가져온다. 모든 자원을 선점 가능하게 만드는 것은 현실적으로 불가능하거나 매우 비효율적이다. 예를 들어, 데이터베이스 트랜잭션이 특정 레코드를 갱신하는 도중에 그 자원을 선점당하면 데이터의 일관성이 깨질 수 있다. 따라서, 이 조건을 완화하기 위해서는 자원의 상태를 안전하게 저장하고 복원할 수 있는 메커니즘(예: 체크포인트와 롤백)이 필요하며, 이는 주로 메모리나 중앙 처리 장치와 같은 특정 유형의 자원에 한정되어 적용된다.
순환 대기는 교착 상태가 발생하기 위한 네 가지 필요조건 중 하나이다. 이 조건은 두 개 이상의 프로세스나 스레드가 서로 다른 자원을 점유한 채, 상대방이 점유한 자원을 기다리는 순환 고리가 형성되는 상황을 의미한다.
예를 들어, 프로세스 P1이 자원 R1을 점유하고 자원 R2를 기다리는 동안, 프로세스 P2는 자원 R2를 점유하고 자원 R1을 기다린다면 두 프로세스는 서로 상대방이 자원을 해제하기를 무한정 기다리게 된다. 이러한 순환 구조는 두 개 이상의 프로세스로 확장되어 더 복잡한 고리를 형성할 수도 있다. 이 조건은 다른 세 조건(상호 배제, 점유와 대기, 비선점)이 모두 충족된 상태에서 발생하면 교착 상태를 필연적으로 초래한다.
순환 대기 조건을 제거하는 일반적인 방법은 모든 자원에 전역적인 순서를 부여하고, 각 프로세스가 항상 낮은 번호의 자원부터 높은 번호의 자원 순서로만 자원을 요청하도록 강제하는 것이다. 이 방식을 자원 계층화 또는 자원 순서화라고 한다. 이 정책을 따르면 프로세스들이 자원을 기다리는 방향이 한쪽으로만 흐르게 되어 순환 고리가 생기는 것을 근본적으로 방지할 수 있다.

교착 상태는 주로 자원에 대한 경쟁과 프로세스의 실행 순서가 복잡하게 얽힐 때 발생한다. 시스템의 자원 수가 제한되어 있고, 여러 프로세스가 동시에 그 자원들을 필요로 하며, 운영체제의 자원 할당 정책이 특정 조건을 만족시키면 교착 상태에 빠질 가능성이 생긴다.
구체적인 원인으로는 첫째, 유한한 자원에 대한 경쟁이다. 프린터, 테이프 드라이브, 세마포어, 데이터베이스의 락과 같은 자원의 수가 프로세스의 요구보다 적을 때, 프로세스들이 서로 상대방이 점유한 자원을 기다리며 블록되는 상황이 벌어진다. 둘째, 프로세스들의 실행 순서와 자원 사용 패턴이다. 프로세스가 자원을 요청하고 해제하는 순서가 적절하지 않으면, 예를 들어 프로세스 A가 자원 1을 점유한 채 자원 2를 요구하고, 동시에 프로세스 B가 자원 2를 점유한 채 자원 1을 요구하는 순환 대기 조건이 만들어질 수 있다.
마지막으로, 운영체제의 자원 관리 정책과 시스템의 설계 자체가 원인이 될 수 있다. 비선점 정책을 사용하거나, 프로세스가 작업 중 필요한 모든 자원을 한꺼번에 요청하고 점유한 채 대기하도록 허용하는 정책은 교착 상태의 필요 조건을 형성하는 데 기여한다[3]. 따라서 교착 상태는 단일 원인보다는 시스템의 자원 종류, 수, 프로세스의 특성, 그리고 운영체제의 스케줄링 정책이 복합적으로 작용하여 발생하는 현상이다.
교착 상태의 주요 원인 중 하나는 프로세스나 스레드가 유한한 시스템 자원을 두고 경쟁하는 상황이다. 시스템의 자원은 프로세서, 메모리, 파일, 프린터, 데이터베이스 레코드 등 다양한 형태를 띠지만, 그 수는 제한되어 있다. 여러 프로세스가 동시에 같은 자원을 필요로 할 때, 그 자원이 한 번에 하나의 프로세스만 사용할 수 있는 상호 배제 조건을 가진다면 경쟁이 발생한다.
예를 들어, 두 개의 프로세스 A와 B가 각각 프린터와 스캐너를 사용하여 작업을 완료해야 한다고 가정해 보자. 프로세스 A가 먼저 프린터를 점유하고, 프로세스 B가 스캐너를 점유했다. 이후 A는 스캐너를, B는 프린터를 추가로 요청하면, 각자 필요한 자원이 상대방에게 점유된 상태이므로 두 프로세스 모두 무한정 대기하게 된다. 이는 단순히 자원이 부족해서가 아니라, 자원을 점유한 상태에서 다른 자원을 요청하는 특정한 순서에 의해 발생한다.
자원 경쟁이 교착 상태로 이어지기 위해서는 일반적으로 네 가지 필요조건이 모두 만족되어야 한다[4]. 자원 경쟁 자체는 병행 시스템에서 흔히 발생하는 현상이지만, 이러한 조건들이 결합되면 시스템이 더 이상 진행되지 못하는 순환 대기에 빠질 수 있다. 따라서 교착 상태를 이해하고 관리하는 것은 이러한 경쟁을 어떻게 조정하느냐에 달려 있다.
교착 상태는 프로세스들이 특정 순서로 자원을 요청하고 획득할 때 발생할 수 있다. 각 프로세스가 실행되는 순서와 자원을 요청하는 시점이 서로 맞물리면, 순환 대기 조건이 성립되어 교착 상태에 빠질 수 있다.
예를 들어, 프로세스 A가 자원 1을 먼저 획득한 후 자원 2를 요청하고, 프로세스 B는 자원 2를 먼저 획득한 후 자원 1을 요청하는 상황을 가정해 보자. 두 프로세스의 실행 순서가 다음과 같다면 교착 상태는 피할 수 있다.
프로세스 | 실행 순서 1 | 실행 순서 2 |
|---|---|---|
A | 자원 1 획득 | 자원 2 획득 |
B | 자원 2 획득 | 자원 1 획득 |
그러나 두 프로세스가 아래와 같은 순서로 동시에 실행되면 교착 상태가 발생한다.
1. 프로세스 A가 자원 1을 획득한다.
2. 프로세스 B가 자원 2를 획득한다.
3. 프로세스 A는 자원 2를 요청하지만, 프로세스 B가 점유 중이므로 대기한다.
4. 프로세스 B는 자원 1을 요청하지만, 프로세스 A가 점유 중이므로 대기한다.
따라서, 운영체제나 응용 프로그램 설계 시 프로세스들의 자원 요청 순서를 일관되게 정의하는 것이 중요하다. 모든 프로세스가 동일한 순서(예: 항상 자원 1을 먼저 요청한 후 자원 2를 요청)로 자원을 요청하도록 강제하면, 순환 대기가 형성되지 않아 교착 상태를 예방할 수 있다. 이는 교착 상태 예방 기법 중 하나이다.
시스템의 물리적 또는 논리적 자원이 제한되어 있을 때, 교착 상태가 발생할 가능성이 높아진다. 운영체제는 프로세스들에게 CPU, 메모리, 입출력 장치와 같은 자원을 할당하여 실행을 지원한다. 그러나 이러한 자원의 총량이 고정되어 있고, 여러 프로세스가 동시에 제한된 자원을 요구하면, 모든 요청을 즉시 만족시킬 수 없는 상황이 발생한다. 이는 자원에 대한 경쟁을 심화시키고, 결국 순환 대기 조건을 형성하는 원인이 된다.
예를 들어, 시스템에 프린터가 단 한 대만 설치되어 있다고 가정해 보자. 두 개의 프로세스가 각각 파일 A와 B를 출력하기 위해 이 프린터를 필요로 한다면, 한 프로세스가 프린터를 점유하는 동안 다른 프로세스는 대기해야 한다. 만약 각 프로세스가 추가로 다른 자원(예: 특정 데이터베이스 레코드에 대한 락)을 보유한 채 상대방이 점유한 프린터를 무한정 기다린다면, 이는 전형적인 교착 상태에 빠지게 된다. 자원의 수가 적을수록 이러한 충돌 가능성은 기하급수적으로 증가한다.
자원 유형 | 제한된 자원의 예시 | 교착 상태 발생 가능성 |
|---|---|---|
하드웨어 자원 | 프린터, 스캐너, 테이프 드라이브 | 자원 인스턴스 수가 적을수록 높음 |
소프트웨어 자원 | 데이터베이스의 잠금, 메시지 버퍼 슬롯 | 동시 사용자 수나 버퍼 크기가 작을수록 높음 |
추상적 자원 | 프로세스 테이블 항목, 열린 파일 핸들 | 시스템 전체 할당량이 부족할 경우 높음 |
자원의 한계는 단순히 개수뿐만 아니라 풀(pool)의 크기에서도 기인한다. 시스템은 종종 성능이나 안정성을 위해 특정 자원의 최대 사용량을 제한한다. 예를 들어, 동시에 생성될 수 있는 최대 프로세스 수나 열 수 있는 최대 파일 수가 정해져 있다. 여러 프로세스가 이 제한에 도달하여 서로가 해제할 자원을 기다리는 상황이 연쇄적으로 발생하면, 시스템 전체가 마비될 수 있다. 따라서 시스템 설계 시 예상되는 작업 부하를 고려하여 자원 풀을 적절히 확보하거나, 자원 할당 그래프 등을 이용한 사전 모니터링이 필요하다.

교착 상태 탐지는 시스템이 현재 교착 상태에 빠져 있는지 확인하는 과정이다. 탐지 기법은 주로 자원 할당 그래프나 대기 그래프와 같은 그래프 모델을 사용하여 시스템 상태를 분석한다.
자원 할당 그래프는 프로세스와 자원 간의 관계를 시각적으로 표현한다. 그래프에서 프로세스 노드에서 자원 노드로 향하는 간선은 해당 자원을 요청(대기) 중임을 나타내고, 자원 노드에서 프로세스 노드로 향하는 간선은 자원이 프로세스에 할당(점유)되었음을 나타낸다. 이 그래프에서 사이클이 발견되면 교착 상태가 존재할 가능성이 있다. 단일 유형의 자원이 여러 개 존재하는 경우, 그래프를 단순화하여 사이클을 탐지할 수 있다. 시스템은 주기적으로 이 그래프를 검사하거나 자원 요청이 지연될 때마다 검사를 수행하여 교착 상태를 발견한다.
다른 주요 방법으로는 대기 그래프를 사용하는 것이다. 이는 자원 할당 그래프에서 자원 노드를 제거하고 프로세스 노드 간의 대기 관계만을 나타낸 그래프이다. 프로세스 P_i가 프로세스 P_j가 점유한 자원을 기다리고 있다면, P_i에서 P_j로 향하는 간선이 존재한다. 이 대기 그래프에서 사이클이 존재하는 것은 교착 상태가 발생했음을 직접적으로 의미한다. 탐지 알고리즘은 이러한 사이클을 찾기 위해 주기적으로 그래프를 순회한다.
탐지 빈도는 성능과 교착 상태 지속 시간 사이의 절충안이다. 탐지를 너무 자주 수행하면 시스템 오버헤드가 커지고, 너무 드물게 수행하면 교착 상태가 오랫동안 방치될 수 있다. 따라서 시스템 설계자는 교착 상태로 인한 손실과 탐지 비용을 고려하여 적절한 탐지 주기를 결정해야 한다.
자원 할당 그래프는 시스템 내 프로세스와 자원 간의 관계를 시각적으로 표현하는 방향 그래프이다. 이 그래프는 교착 상태를 탐지하는 데 사용되는 주요 도구 중 하나이다.
그래프는 정점과 간선으로 구성된다. 정점은 두 가지 유형으로 나뉜다. 프로세스 정점(P)과 자원 정점(R)이다. 자원 정점 내부에는 해당 자원의 이용 가능한 인스턴스 수를 나타내는 점이 표시된다. 간선은 두 종류가 있다. 프로세스에서 자원을 향하는 요청 간선과 자원에서 프로세스를 향하는 할당 간선이다. 요청 간선은 프로세스가 해당 자원을 요청했지만 아직 획득하지 못한 상태를, 할당 간선은 자원 인스턴스가 특정 프로세스에 이미 할당된 상태를 나타낸다.
교착 상태의 존재 여부는 이 그래프에서 사이클을 찾아냄으로써 판단할 수 있다. 만약 그래프에 사이클이 존재하지 않으면, 시스템은 교착 상태에 있지 않다. 반면, 그래프에 사이클이 존재하면, 시스템이 교착 상태일 가능성이 있다. 특히, 각 자원 유형이 정확히 하나의 인스턴스만을 갖는 경우, 그래프 내의 사이클은 교착 상태가 발생했음을 의미하는 필요충분조건이 된다. 그러나 자원 유형이 여러 개의 인스턴스를 가질 수 있는 경우, 사이클의 존재는 교착 상태의 필요조건이지만 충분조건은 아니다. 이 경우 더 정밀한 알고리즘이 추가로 필요하다.
그래프 요소 | 설명 | 표기법 예시 |
|---|---|---|
프로세스 정점 | 시스템 내의 프로세스를 나타냄 | 원 또는 사각형 안에 P₁, P₂ 등 |
자원 정점 | 자원 유형을 나타냄. 내부 점은 인스턴스 수 | 원 안에 R₁, R₁ 내부에 점 2개는 인스턴스 2개 |
요청 간선 | 프로세스 → 자원. 자원을 요청 중인 상태 | P₁ → R₁ |
할당 간선 | 자원 → 프로세스. 자원이 프로세스에 할당된 상태 | R₁ → P₂ |
대기 그래프는 시스템 내 프로세스 간의 대기 관계를 방향 그래프로 표현한 것이다. 이 그래프는 교착 상태 탐지를 위한 주요 도구 중 하나로 활용된다.
대기 그래프의 노드는 프로세스를 나타내며, 방향성 간선은 대기 관계를 표현한다. 예를 들어, 프로세스 P1이 프로세스 P2가 보유한 자원을 기다리고 있다면, P1에서 P2로 향하는 간선이 그려진다. 이는 P1 → P2의 관계를 의미한다. 시스템의 자원 할당 상태를 나타내는 자원 할당 그래프와 달리, 대기 그래프는 프로세스 간의 직접적인 대기 종속성에만 초점을 맞춘다.
교착 상태는 대기 그래프에서 사이클이 존재할 때 발생한다고 판단할 수 있다. 그래프에 사이클이 존재한다는 것은 프로세스들이 순환적으로 서로를 기다리고 있는 상태, 즉 교착 상태에 빠져 있음을 의미한다. 탐지 알고리즘은 주기적으로 이 그래프를 생성하고 사이클 검사를 수행한다. 대기 그래프는 자원 유형을 노드로 표시하지 않기 때문에, 특히 동일 유형의 자원이 여러 개 존재하는 경우 자원 할당 그래프보다 간결한 표현이 가능할 수 있다.
그래프 유형 | 노드 | 간선 의미 | 교착 상태 판단 기준 |
|---|---|---|---|
자원 할당 그래프 | 프로세스와 자원 | 할당 또는 요청 | 자원 유형에 따른 사이클 존재 |
대기 그래프 | 프로세스 | 프로세스 간 대기 관계 | 프로세스 노드로만 구성된 사이클 존재 |
그러나 대기 그래프는 모든 대기 관계가 프로세스 간 직접적인 관계로 환원될 수 있을 때 효과적이다. 일부 복잡한 자원 경쟁 시나리오에서는 자원 할당 그래프를 대기 그래프로 변환하는 과정이 필요하며, 이 변환 과정 자체가 계산 비용을 수반할 수 있다.

교착 상태 예방은 교착 상태 발생의 네 가지 필요조건 중 적어도 하나를 시스템이 허용하지 않음으로써 교착 상태가 절대 발생하지 않도록 보장하는 접근법이다. 각 조건을 제거하는 대표적인 기법은 다음과 같다.
상호 배제 조건 제거: 모든 자원을 공유 가능하게 만드는 것은 현실적으로 불가능하다. 프린터나 테이프 드라이브와 같은 물리적 자원은 본질적으로 상호 배타적이기 때문이다. 따라서 이 조건을 완전히 제거하기보다는, 소프트웨어적 자원(예: 읽기 전용 파일)에 대해서만 적용될 수 있다.
점유와 대기 조건 제거: 프로세스가 실행되기 전에 필요한 모든 자원을 한꺼번에 요청하고 할당받도록 하는 방법이다. 이는 자원 이용률을 심각하게 저하시키고, 프로세스가 필요한 모든 자원을 미리 알지 못하는 경우 적용하기 어렵다는 단점이 있다. 다른 방법으로는, 프로세스가 자원을 전혀 보유하지 않은 상태에서만 새로운 자원을 요청하도록 강제하는 방식이 있다. 이 경우 프로세스는 기존에 점유하던 자원을 모두 반납한 후 새로운 집합을 요청해야 하므로, 실용성이 낮다.
비선점 조건 제거: 이미 할당된 자원을 강제로 빼앗을 수 있도록 한다. 예를 들어, 높은 우선순위의 프로세스가 필요한 경우, 낮은 우선순위 프로세스가 점유한 자원을 선점할 수 있다. 이 방법은 CPU나 메모리와 같은 자원에는 적용 가능하지만, 프린터 작업 중간에 선점하는 것은 불가능하거나 매우 비효율적이다. 주로 상태를 쉽게 저장하고 복원할 수 있는 자원에 한정되어 사용된다.
순환 대기 조건 제거: 모든 자원에 전역적인 순서(예: 자원 유형 번호)를 부여하고, 프로세스가 자원을 오름차순 순서로만 요청하도록 강제하는 방법이다. 이는 가장 실용적이고 널리 사용되는 예방 기법 중 하나이다. 프로세스가 높은 번호의 자원을 점유한 상태에서 낮은 번호의 자원을 요청하는 것을 금지함으로써, 자원 할당 그래프에서 순환이 발생하는 것을 근본적으로 차단한다.
예방 조건 | 주요 기법 | 장점 | 단점 |
|---|---|---|---|
상호 배제 제거 | 자원을 공유 가능하게 설계 | 교착 상태 방지 | 대부분의 물리적 자원에 적용 불가 |
점유와 대기 제거 | 모든 자원 사전 할당 또는 자원 반납 후 요청 | 단순함 | 자원 이용률 저하, 기아 상태 가능성 |
비선점 제거 | 자원 선점 허용 | 특정 자원에 효과적 | 적용 가능한 자원 유형이 제한적 |
순환 대기 제거 | 자원에 순서 부여 및 순차적 요청 강제 | 실용적, 오버헤드 낮음 | 자원 요청 순서 제약으로 유연성 감소 |
이러한 예방 기법들은 교착 상태를 근본적으로 막지만, 시스템 성능 저하나 자원 이용률 감소, 적용의 제한성 등의 트레이드오프를 동반한다. 따라서 시스템의 특성과 요구사항에 맞는 조건을 선택적으로 제거하는 전략이 필요하다.
교착 상태 예방을 위한 필요조건 제거 기법은 교착 상태가 발생하기 위한 네 가지 필요 조건 중 하나 이상을 시스템이 허용하지 않도록 함으로써, 교착 상태가 절대 발생하지 않도록 보장하는 방법이다.
네 가지 조건 중 하나를 제거하는 대표적인 접근법은 다음과 같다. 첫째, 상호 배제 조건을 제거하는 것은, 모든 자원을 공유 가능하게 만드는 것이다. 그러나 프린터나 테이프 드라이브와 같은 물리적 자원은 본질적으로 상호 배제가 필요하므로, 이 조건을 완전히 제거하는 것은 현실적으로 불가능한 경우가 많다. 둘째, 점유와 대기 조건을 제거하기 위해 프로세스가 실행을 시작하기 전에 필요한 모든 자원을 한꺼번에 요청하고 할당받도록 하는 방법이 있다. 이는 자원의 한계로 인해 자원 활용도가 떨어지고 기아 상태가 발생할 가능성을 높인다는 단점이 있다. 셋째, 비선점 조건을 제거하는 방법으로, 이미 할당된 자원을 강제로 빼앗을 수 있도록 하는 것이다. 그러나 이 방법은 자원의 상태를 저장하고 복원하는 비용이 크며, 프린터와 같은 자원에는 적용하기 어렵다.
마지막으로, 순환 대기 조건을 제거하는 가장 일반적인 방법은 모든 자원에 고유한 번호(전체 순서)를 부여하고, 프로세스가 자원을 요청할 때는 이 번호가 항상 오름차순(또는 내림차순)으로만 요청하도록 강제하는 것이다. 이 정책을 따르면 자원 할당 그래프에 사이클이 형성될 수 없어 순환 대기 조건이 제거된다. 이 기법은 구현이 비교적 간단하고 오버헤드가 적지만, 자원 요청 순서를 애플리케이션 개발자가 미리 알고 있어야 하며, 필요에 따른 유연한 자원 사용을 제한할 수 있다는 한계가 있다.
은행원 알고리즘은 교착 상태를 회피하기 위해 에츠허르 데이크스트라가 제안한 알고리즘이다. 이 알고리즘은 은행이 대출을 승인할 때 고객의 최대 대출 요구량과 현재 가용한 자금을 고려하여 안전한지 판단하는 방식에서 착안하여 이름이 붙었다.
알고리즘은 시스템이 항상 안전 상태에 머물도록 보장한다. 각 프로세스는 자신이 필요로 할 최대 자원의 수를 사전에 선언해야 한다. 시스템은 프로세스가 자원을 요청할 때마다, 그 요청을 허용했을 때 시스템이 여전히 안전 상태를 유지할 수 있는지 시뮬레이션을 통해 검사한다. 검사 결과 안전 상태가 유지될 수 있다고 판단되면 자원을 할당하고, 그렇지 않으면 프로세스는 자원을 할당받기 전까지 대기 상태가 된다.
이 알고리즘을 적용하기 위해서는 몇 가지 전제 조건이 필요하다. 시스템 내의 프로세스 수와 자원의 종류 및 수가 고정되어 있어야 하며, 프로세스는 자신이 필요로 하는 최대 자원량을 미리 명시해야 한다. 또한, 프로세스는 작업을 완료한 후 반드시 할당받은 모든 자원을 시스템에 반환한다는 가정을 한다.
장점 | 단점 |
|---|---|
교착 상태를 완전히 회피할 수 있음 | 프로세스 수와 자원 수가 고정되어야 함 |
사전에 안전성을 보장함 | 프로세스의 최대 자원 요구량을 미리 알아야 함 |
자원 할당 시 오버헤드가 발생함[5] |
이 알고리즘은 이론적으로는 완벽하지만, 실제 시스템에 적용하기에는 제약이 많다. 프로세스가 필요로 하는 최대 자원 수를 정확히 예측하기 어렵고, 시스템의 자원 수가 동적으로 변하는 환경에서는 사용하기 힘들다. 따라서 주로 학문적 모델에서 설명되며, 실제 시스템에서는 보다 실용적인 다른 교착 상태 처리 방법이 더 많이 사용된다.

교착 상태 회피는 시스템이 안전 상태에 있는 동안에만 자원을 할당함으로써 교착 상태가 발생하지 않도록 보장하는 사전적 접근 방식이다. 이 방법은 교착 상태의 필요조건을 제거하거나 부정하지 않고, 자원 할당 요청이 발생할 때마다 그 요청을 허용했을 때 시스템이 여전히 안전 상태를 유지할지 동적으로 검사하여 결정한다.
안전 상태란 시스템이 특정 순서로 모든 프로세스가 자원을 요청하고 반납하는 과정을 마칠 수 있는 안전 순서가 존재하는 상태를 말한다. 만약 시스템이 불안전 상태에 들어갈 가능성이 있는 자원 할당 요청이 들어오면, 해당 요청은 즉시 허용되지 않고 프로세스는 자원을 얻기 위해 대기해야 한다. 가장 대표적인 교착 상태 회피 알고리즘은 은행원 알고리즘이다.
교착 상태 회피를 구현하기 위해서는 시스템이 미리 각 프로세스가 필요로 할 최대 자원의 양을 알고 있어야 한다. 또한, 현재 사용 가능한 자원의 수, 각 프로세스에 현재 할당된 자원의 수, 각 프로세스의 추가 요청 가능량을 지속적으로 관리해야 한다. 이 정보를 바탕으로 각 자원 요청에 대해 '가상 할당'을 시뮬레이션하고, 그 결과 시스템이 안전 상태로 남아 있는지 확인하는 과정을 거친다.
이 방식의 주요 단점은 사전 정보(최대 필요 자원량)의 필요성과 알고리즘 수행에 따른 오버헤드이다. 프로세스 수와 자원 종류가 많아질수록 안전 상태 검사에 드는 계산 비용이 증가하며, 실제로 프로세스가 선언한 최대 자원 사용량보다 훨씬 적게 사용하는 경우 자원 이용률이 낮아질 수 있다. 따라서 이 방법은 주로 자원 종류가 비교적 단일하고 프로세스의 행동을 예측하기 쉬운 환경에서 적용된다.
안전 상태는 시스템이 교착 상태에 빠지지 않고 모든 프로세스가 필요한 자원을 할당받아 정상적으로 종료될 수 있는 가능성이 있는 상태를 말한다. 반대로, 불안전 상태는 현재의 자원 할당 상태와 프로세스의 최대 요구량을 고려했을 때, 어떤 순서로 자원을 할당하더라도 교착 상태가 발생할 가능성이 있는 상태를 의미한다. 불안전 상태는 반드시 교착 상태가 발생한다는 것을 보장하지는 않지만, 교착 상태가 발생할 수 있는 위험한 조건을 가지고 있다[6].
시스템이 안전 상태를 유지한다는 것은 은행원 알고리즘과 같은 교착 상태 회피 알고리즘이 적용될 수 있는 전제 조건이 된다. 안전 상태를 판별하기 위해 시스템은 각 프로세스의 현재 할당량, 최대 요구량, 그리고 사용 가능한 자원의 수를 고려하여 '안전 순서열'이 존재하는지 검사한다. 안전 순서열이란, 프로세스들이 그 순서대로 자원을 요청하고 반납할 경우, 각 프로세스가 필요한 최대 자원을 얻고 작업을 완료할 수 있는 프로세스들의 진행 순서를 말한다.
상태 | 정의 | 교착 상태 발생 가능성 | 시스템의 대응 |
|---|---|---|---|
안전 상태 | 안전 순서열이 존재하는 상태 | 없음 | 자원 요청을 즉시 승인할 수 있음 |
불안전 상태 | 안전 순서열이 존재하지 않는 상태 | 있음 | 자원 요청을 지연시켜 회피해야 함 |
따라서 교착 상태 회피의 핵심은 시스템이 불안전 상태로 진입하는 것을 허용하지 않고, 항상 안전 상태 내에 머물도록 자원 할당을 통제하는 것이다. 만약 프로세스의 자원 요청이 시스템을 안전 상태에서 불안전 상태로 만들 것이라고 판단되면, 해당 요청은 즉시 허용되지 않고 프로세스는 자원을 얻기 위해 대기하게 된다. 이 방식은 자원 활용도를 희생시키는 대신 교착 상태를 사전에 방지한다.
자원 할당 정책은 시스템이 프로세스의 자원 요청을 허용할지 말지를 결정하는 규칙으로, 교착 상태를 회피하는 핵심 메커니즘이다. 이 정책은 은행원 알고리즘과 같은 교착 상태 회피 알고리즘을 구현하는 기반이 된다. 시스템은 프로세스가 자원을 요청할 때마다, 해당 요청을 허용한 후의 시스템 상태가 안전 상태에 머물러 있는지 시뮬레이션을 통해 검사한다. 만약 요청을 수락했을 때 시스템이 불안전 상태로 빠질 가능성이 있다면, 해당 요청은 즉시 거부되고 프로세스는 자원을 할당받지 못한 채 대기하게 된다.
주요 자원 할당 정책으로는 다음과 같은 것들이 있다.
정책 | 설명 | 목적 |
|---|---|---|
안전 상태 유지 정책 | 모든 자원 요청에 대해 안전 상태 검사를 수행하여, 안전 순서가 존재할 때만 할당한다. | 교착 상태 발생을 사전에 차단한다. |
자원 요청 거부 정책 | 안전 상태 검사 실패 시, 프로세스의 자원 요청을 즉시 거부하고 대기시킨다. | 불안전 상태로의 진입을 방지한다. |
사전 선언 정책 | 프로세스가 시작 시 필요한 최대 자원 수를 미리 선언하게 하여, 알고리즘이 안전성을 판단할 수 있는 정보를 제공한다. | 은행원 알고리즘의 전제 조건을 만족시킨다. |
이러한 정책을 적용할 때의 주요 고려사항은 성능과 자원 활용도이다. 지나치게 보수적인 정책은 교착 상태는 방지할 수 있지만, 자원 이용률을 낮추고 프로세스의 대기 시간을 증가시켜 시스템 전체 처리량을 떨어뜨릴 수 있다. 반대로 너무 관대한 정책은 교착 상태 위험을 높인다. 따라서 시스템 설계자는 응용 프로그램의 특성과 자원의 종류, 수를 고려하여 적절한 정책을 선택하거나 조합해야 한다. 예를 들어, 프린터나 테이프 드라이브와 같이 교착 상태 발생 시 복구 비용이 큰 자원에는 보수적인 정책을, 주기억장치와 같이 선점이 비교적 쉬운 자원에는 덜 제한적인 정책을 적용하는 경우가 많다.

교착 상태가 이미 발생한 시스템에서는 복구 기법을 적용하여 정상 상태로 되돌려야 한다. 복구 방법은 크게 프로세스를 종료시키는 방법과 자원을 선점하는 방법으로 나눈다.
프로세스 종료 방식은 교착 상태에 연루된 하나 이상의 프로세스를 강제로 종료하여 점유한 자원을 해제하는 방법이다. 여기에는 두 가지 전략이 있다. 첫째는 교착 상태에 있는 모든 프로세스를 한꺼번에 종료하는 것이다. 이는 구현이 간단하지만 진행 중이던 작업이 모두 손실되는 단점이 있다. 둘째는 교착 상태가 제거될 때까지 프로세스를 하나씩 순차적으로 종료하는 것이다. 이 방법은 시스템 오버헤드는 크지만 작업 손실을 최소화할 수 있다. 종료 대상 프로세스를 선택할 때는 프로세스의 우선순위, 실행 시간, 사용한 자원의 종류와 양, 다시 시작하는 데 필요한 비용 등을 고려한다.
자원 선점 방식은 교착 상태에 있는 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당하는 방법이다. 선점을 위한 프로세스 선택 기준은 프로세스 종료 방식과 유사하다. 자원을 선점당한 프로세스는 해당 자원을 잃게 되므로, 이후 특별한 처리가 필요하다. 일반적으로 해당 프로세스는 중단된 지점에서 계속 실행할 수 없으므로, 완전히 재시작하거나 안전한 체크포인트[7]까지 롤백하여 다시 실행해야 한다. 이 과정에서 기아 상태가 발생하지 않도록 주의해야 한다.
교착 상태를 복구하기 위한 프로세스 종료 기법은 하나 이상의 프로세스를 강제로 종료하여 점유된 자원을 시스템에 반환하고, 순환 대기 조건을 깨는 방법이다. 이 기법은 크게 두 가지 방식으로 나뉜다.
첫 번째 방식은 모든 프로세스를 종료하는 것이다. 이는 가장 간단한 방법이지만, 이미 상당량의 작업을 수행한 프로세스들까지 모두 중단시켜야 하므로 시스템 전체의 처리 효율이 크게 떨어질 수 있다. 두 번째 방식은 교착 상태에 연루된 프로세스 중 하나씩 순차적으로 종료해보며 순환 대기가 사라질 때까지 반복하는 것이다. 이 경우 어떤 프로세스를 먼저 종료할지 선택하는 기준이 중요해진다.
프로세스 선택 기준은 일반적으로 시스템의 손실을 최소화하는 방향으로 설정된다. 주요 고려 사항은 다음과 같다.
선택 기준 | 설명 |
|---|---|
프로세스의 우선순위 | 낮은 우선순위의 프로세스를 먼저 종료한다. |
실행 시간과 남은 시간 | 지금까지 실행된 시간이 짧거나, 완료까지 예상되는 시간이 긴 프로세스를 종료한다. |
점유한 자원의 양 | 많은 자원을 점유하고 있는 프로세스를 종료하면 더 많은 자원이 한꺼번에 해제된다. |
프로세스 유형 | 대화형 프로세스보다 일괄 처리 프로세스를 먼저 종료하는 등 유형에 따라 결정한다. |
프로세스가 종료된 후, 특정 시점(예: 교착 상태가 발생하기 직전의 상태)으로 시스템을 되돌리는 롤백 작업이 필요할 수 있다. 이는 데이터베이스 트랜잭션과 같이 원자성이 중요한 작업에서 특히 중요하다. 프로세스 종료는 확실한 복구 방법이지만, 작업 손실과 재시작에 따른 오버헤드라는 비용을 수반한다.
자원 선점은 교착 상태에 빠진 하나 이상의 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당함으로써 교착 상태를 해소하는 방법이다. 이 기법은 시스템이 교착 상태를 탐지한 후에 수행되는 복구 조치에 해당한다.
자원을 선점할 프로세스를 선택하는 기준에는 여러 가지가 있다. 일반적으로는 최소 비용의 복구를 목표로, 이미 많은 자원을 점유한 프로세스, 낮은 우선순위를 가진 프로세스, 또는 재시작하기까지 남은 예상 실행 시간이 짧은 프로세스 등을 선점 대상으로 선정한다. 선점된 프로세스는 이후 특정 지점(예: 체크포인트)부터 재시작되거나, 완전히 종료될 수 있다.
자원 선점 과정은 세 단계로 이루어진다.
1. 선점: 선택된 프로세스로부터 하나 이상의 필요한 자원을 강제로 회수한다.
2. 롤백: 선점된 프로세스를 안전한 상태(일반적으로 선점 이전의 특정 체크포인트)로 되돌린다.
3. 재시작: 회수된 자원을 대기 중인 프로세스에 할당한 후, 롤백된 프로세스의 실행을 재개한다.
이 방법은 프로세스를 강제 종료하는 것보다 자원 활용도 측면에서 유리할 수 있지만, 선점과 롤백에 따른 시스템 오버헤드가 발생하며, 모든 프로세스와 자원이 선점에 적합한 것은 아니라는 한계가 있다. 특히 프린터나 테이프 드라이브와 같은 비선점 자원에서의 선점은 구현이 매우 복잡하거나 불가능할 수 있다.

교착 상태는 이론적인 개념에 그치지 않고, 데이터베이스 시스템, 운영체제, 분산 시스템 등 다양한 실제 컴퓨팅 환경에서 빈번히 발생하는 문제이다. 각 시스템은 고유한 자원 관리 메커니즘을 가지고 있어 교착 상태의 양상과 해결 접근법이 다르게 나타난다.
데이터베이스 시스템에서는 주로 트랜잭션이 락을 획득하는 순서에 따라 교착 상태가 발생한다. 예를 들어, 트랜잭션 A가 레코드 X에 대한 락을 획득한 후 레코드 Y의 락을 요구하는 동안, 트랜잭션 B는 이미 레코드 Y의 락을 획득하고 레코드 X의 락을 요구하면 순환 대기가 형성된다. 대부분의 현대 관계형 데이터베이스 관리 시스템은 교착 상태 탐지기(Deadlock Detector)를 주기적으로 실행하여 자원 할당 그래프를 분석하고, 희생자(Victim) 트랜잭션을 선정해 롤백함으로써 교착 상태를 복구한다.
운영체제에서는 프로세스들이 프린터, 테이프 드라이브, 메모리 세그먼트와 같은 물리적 또는 소프트웨어 자원을 경쟁하며 교착 상태에 빠질 수 있다. 예를 들어, 두 프로세스가 각각 스캐너와 프린터를 점유한 채 상대 프로세스가 가진 자원을 대기하는 경우가 전형적이다. 유닉스나 리눅스 같은 운영체제는 교착 상태 예방을 위해 자원 할당 정책을 엄격히 정의하거나, 은행원 알고리즘과 같은 회피 기법을 구현하기도 한다. 그러나 성능 오버헤드로 인해 실제로는 교착 상태가 발생하지 않도록 응용 프로그램을 설계하는 데 더 중점을 둔다.
분산 시스템은 교착 상태를 탐지하고 해결하는 것이 가장 복잡한 환경이다. 여러 독립적인 사이트에 자원과 프로세스가 분산되어 있어 전역 상태 정보를 수집하기 어렵기 때문이다. 분산 교착 상태 탐지는 중앙 집중식, 계층적, 분산 알고리즘 등 다양한 방식으로 이루어진다. 이러한 시스템에서는 통신 지연과 부분적 실패로 인해 교착 상태 탐지 자체가 불확실할 수 있어, 타임아웃 메커니즘을 활용한 복구나 교착 상태를 허용하지 않는 프로토콜(예: 모든 자원을 한 번에 요청하는 방식)을 사용하기도 한다.
데이터베이스 시스템에서 교착 상태는 주로 여러 트랜잭션이 동일한 데이터 항목에 대해 잠금을 설정하고 서로가 점유한 잠금을 기다릴 때 발생한다. 예를 들어, 트랜잭션 A가 레코드 X에 대한 배타적 잠금을 획득하고 레코드 Y의 잠금을 요청하는 동안, 트랜잭션 B는 이미 레코드 Y에 대한 배타적 잠금을 보유한 상태에서 레코드 X의 잠금을 요청하면 순환 대기 조건이 성립되어 교착 상태에 빠진다.
대부분의 현대 관계형 데이터베이스 관리 시스템은 교착 상태를 탐지하고 처리하기 위한 내장 메커니즘을 갖추고 있다. 일반적으로 시스템은 주기적으로 잠금 대기 그래프를 분석하여 순환 의존성을 탐지한다. 교착 상태가 탐지되면, 시스템은 희생자를 선택하여 해당 트랜잭션을 롤백함으로써 교착 상태를 해결한다. 희생자 선택 기준은 일반적으로 롤백 비용이 가장 낮은 트랜잭션(예: 가장 적은 수의 연산을 수행한 트랜잭션)이다.
교착 상태를 완전히 방지하기보다는 탐지 후 복구하는 전략이 데이터베이스 시스템에서 더 일반적으로 사용된다. 이는 교착 상태 예방 기법이 트랜잭션의 동시성을 과도하게 제한하여 시스템 성능을 저하시킬 수 있기 때문이다. 개발자는 애플리케이션 수준에서 교착 상태 발생 가능성을 줄이기 위해 모든 트랜잭션이 일관된 순서로 데이터 항목에 접근하도록 설계하거나, 잠금 유지 시간을 최소화하는 등의 방법을 사용할 수 있다.
교착 상태 처리 단계 | 데이터베이스 시스템의 일반적 접근법 |
|---|---|
탐지 | 주기적으로 잠금 대기 그래프를 검사하여 순환을 찾음 |
복구 | 희생자 트랜잭션을 롤백하고 모든 잠금을 해제 |
선택 기준 | 롤백 비용(수행된 작업량, 트랜잭션 우선순위 등) |
운영체제는 프로세스와 시스템 자원을 관리하는 핵심 소프트웨어로, 교착 상태가 발생할 수 있는 전형적인 환경을 제공한다. 특히 멀티태스킹과 멀티프로그래밍을 지원하는 운영체제에서는 여러 프로세스가 한정된 자원을 동시에 요구하며 경쟁하기 때문에 교착 상태의 네 가지 필요조건[8]이 쉽게 충족된다. 운영체제 커널 내부에서도 교착 상태는 발생할 수 있으며, 이 경우 시스템 전체가 멈출 수 있는 치명적인 상황으로 이어질 수 있다.
운영체제에서 교착 상태는 주로 프린터, 테이프 드라이브, 메모리 블록과 같은 물리적 자원이나, 세마포어, 뮤텍스, 잠금과 같은 소프트웨어적 자원을 할당하는 과정에서 발생한다. 예를 들어, 프로세스 A가 프린터를 점유한 채 스캐너를 기다리고, 프로세스 B는 스캐너를 점유한 채 프린터를 기다리는 고전적인 순환 대기 상황은 운영체제가 자원을 관리하는 과정에서 흔히 나타나는 문제이다.
다양한 운영체제는 교착 상태를 다루기 위해 각기 다른 정책을 채택한다. 유닉스 계열 운영체제와 같은 많은 현대 시스템은 교착 상태를 탐지하거나 회피하기보다는, 발생 가능성을 낮추는 설계와 발생 시 수동으로 복구하는 방식을 선호한다. 반면, 실시간 시스템이나 고신뢰성이 요구되는 시스템에서는 은행원 알고리즘과 같은 회피 알고리즘이나, 필요조건 중 하나를 제거하는 예방 기법이 더 적극적으로 적용될 수 있다.
자원 유형 | 교착 상태 발생 예시 | 일반적 대처 방식 |
|---|---|---|
물리적 자원 (프린터, 메모리) | 두 프로세스가 프린터와 스캐너를 서로 점유하며 대기 | 대부분 예방 또는 무시(복구 위주) |
소프트웨어 자원 (세마포어, 잠금) | 커널 내부의 여러 스레드가 잠금을 순환적으로 대기 | 주의 깊은 설계로 예방, 탐지 후 복구 |
파일 시스템 메타데이터 | 두 프로세스가 서로 다른 파일에 대한 잠금을 점유한 상태에서 상대방 파일 접근 시도 | 타임아웃 기반 잠금 또는 계층적 잠금 정책 사용 |
분산 시스템에서의 교착 상태는 네트워크로 연결된 여러 컴퓨터 노드가 서로 다른 자원을 보유하면서 상대방이 가진 자원을 기다릴 때 발생한다. 각 노드는 로컬 자원 관리 정보만을 가지고 있어 전역 상태를 파악하기 어렵기 때문에, 교착 상태 탐지와 해결이 중앙 집중식 시스템보다 복잡해진다. 통신 지연, 메시지 손실, 부분적 장애와 같은 네트워크 특유의 문제들이 교착 상태 관리에 추가적인 변수를 만든다.
분산 교착 상태 탐지 알고리즘은 크게 중앙 집중식, 계층적, 분산식으로 나눌 수 있다. 중앙 집중식 방식은 하나의 코디네이터 노드가 다른 노드들로부터 자원 할당 그래프 정보를 수집하여 분석하지만, 단일 장애점이 될 수 있다는 문제가 있다. 분산식 방식은 모든 노드가 탐지 과정에 참여하여, 확산 기법이나 경로 추적 기법을 사용해 교착 상태 가능성을 협력적으로 판단한다. 이 과정에서 타임스탬프나 고유 식별자를 사용해 탐지 메시지의 중복과 무한 순환을 방지한다.
분산 환경에서의 교착 상태 예방과 회피는 실용적으로 구현하기 어려운 경우가 많다. 대신, 타임아웃 메커니즘을 기반으로 한 교착 상태 복구가 널리 사용된다. 프로세스가 특정 시간 동안 응답이 없으면 해당 작업을 롤백하거나 연결을 재설정하는 방식이다. 분산 트랜잭션을 관리하는 2단계 커밋 프로토콜 같은 경우, 참여자들이 준비 상태에서 영구적으로 대기하는 교착 상태를 방지하기 위해 코디네이터의 장애 시 타임아웃 후 중단하는 절차를 포함한다.
탐지 방식 | 주요 특징 | 단점 |
|---|---|---|
중앙 집중식 | 하나의 노드가 전역 그래프를 구성하고 분석함. 구현이 비교적 단순함. | 코디네이터 노드에 과부하 집중, 단일 장애점 문제 발생. |
분산식 | 모든 노드가 협력하여 탐지함. 내고장성이 높음. | 메시지 오버헤드가 크고, 알고리즘이 복잡함. |
계층적 | 노드들을 트리 구조로 조직하여 탐지 책임을 분산함. | 토폴로지 관리가 필요하며, 부분적 장애 시 복잡도 증가. |

기아 상태는 하나 이상의 프로세스가 필요한 자원을 계속해서 할당받지 못하고 무한정 대기하는 상태를 말한다. 교착 상태와 달리, 기아 상태에서는 프로세스가 진행은 가능하지만 특정 자원에 대한 접근이 지연되거나 거부될 수 있다. 이는 주로 자원 할당 정책이 불공평하거나 우선순위 기반 스케줄링에서 낮은 우선순위 프로세스가 계속해서 밀려날 때 발생한다. 기아 상태를 해결하기 위해 노화 기법을 사용하여 오래 대기한 프로세스의 우선순위를 점진적으로 높이는 방법이 자주 적용된다.
라이브락은 두 개 이상의 프로세스가 서로의 상태 변화에 반응하며 실제 작업은 전혀 진척되지 않으면서 계속해서 자원을 점유하고 CPU 시간을 소비하는 상태를 의미한다. 이는 교착 상태와 유사하게 시스템이 멈춘 것처럼 보이지만, 프로세스들은 여전히 활성 상태이며 실행 중이라는 점에서 차이가 있다. 대표적인 예로, 복도에서 마주친 두 사람이 서로 같은 방향으로 비켜주려다 계속해서 길을 막는 상황을 비유할 수 있다. 네트워크 프로토콜이나 동시성 제어 알고리즘에서 설계 결함으로 인해 발생할 수 있다.
개념 | 주요 특징 | 상태 | 해결 방안 예시 |
|---|---|---|---|
상호 배타적인 자원을 점유한 채 서로가 가진 자원을 요구하며 무한 대기 | 프로세스가 블록됨 (진행 불가) | 필요조건 제거, 탐지 및 복구 | |
특정 프로세스가 자원 할당에서 계속 배제되어 지연됨 | 프로세스는 실행 가능하지만 특정 작업이 지연됨 | 공정한 스케줄링, 노화 기법 적용 | |
프로세스는 실행 중이지만, 서로의 반응으로 인해 유용한 작업 진전이 없음 | 프로세스가 활성 상태이며 실행 중 (진행 없음) | 알고리즘 설계 변경, 무작위성 도입 |
이러한 세 상태는 모두 시스템의 효율성을 저해하지만, 그 원인과 메커니즘, 그리고 해결 접근법이 서로 다르다. 올바른 동시성 제어와 자원 관리 정책은 이들 문제를 완화하거나 방지하는 데 핵심적인 역할을 한다.
기아 상태는 시스템에서 하나 이상의 프로세스가 필요한 자원을 계속해서 할당받지 못하고 무기한 대기하게 되는 상황을 가리킨다. 교착 상태와 유사하게 프로세스의 정상적인 실행을 방해하지만, 발생 메커니즘은 근본적으로 다르다. 교착 상태가 상호 대기하는 순환 구조로 인해 발생하는 반면, 기아 상태는 특정 프로세스가 자원 할당 정책에서 계속해서 배제되어 발생한다.
기아 상태는 주로 자원 관리나 스케줄링 알고리즘이 공정하지 않을 때 나타난다. 예를 들어, 우선순위 스케줄링에서 높은 우선순위의 프로세스가 지속적으로 유입되면 낮은 우선순위의 프로세스는 실행 기회를 얻지 못할 수 있다. 또한 은행원 알고리즘과 같은 보수적인 자원 할당 정책이 특정 프로세스의 요청을 지연시키는 원인이 되기도 한다.
기아 상태를 완화하거나 방지하기 위한 일반적인 기법은 다음과 같다.
기법 | 설명 |
|---|---|
프로세스가 대기하는 시간이 길어질수록 우선순위를 점진적으로 높이는 방법이다. | |
공정한 스케줄링 | 라운드 로빈이나 공정 큐와 같이 모든 프로세스에 균등한 기회를 제공하는 알고리즘을 사용한다. |
자원 할당 정책 개선 | 자원을 요청한 순서대로 할당하는 FIFO 큐 등을 도입하여 특정 프로세스가 배제되지 않도록 한다. |
기아 상태는 시스템이 기능적으로 정지된 교착 상태와 달리, 시스템은 정상 동작하지만 일부 프로세스만 영향을 받는다는 점에서 차이가 있다. 그러나 장기간 지속될 경우 시스템의 전체적인 효율성을 저하시키고, 특정 작업이 완료되지 않는 결과를 초래할 수 있다.
라이브락은 하나 이상의 프로세스가 실행 상태에 있지만, 실제로는 진전을 이루지 못하고 동일한 상태를 반복하는 현상을 말한다. 교착 상태와 달리 프로세스들은 CPU를 점유하고 있으며, 실행은 하지만 유용한 작업을 수행하지는 못한다. 이는 주로 프로세스들이 서로의 진행을 방해하는 일련의 상태 변화를 계속 반복할 때 발생한다.
전형적인 예로, 두 개의 프로세스가 각각 하나의 자원을 점유한 채 상대방이 가진 다른 자원을 얻기 위해 대기하는 교착 상태와는 다르다. 라이브락에서는 프로세스들이 자원을 얻으려고 지속적으로 시도하지만, 그 시도의 타이밍이나 조건이 맞지 않아 서로 계속 양보하거나 상태를 변경하기만 할 뿐 실제 자원을 할당받지 못한다. 예를 들어, 복도에서 마주친 두 사람이 서로를 피하려고 같은 방향으로 계속 움직여 길을 비켜주지 못하는 상황에 비유할 수 있다.
라이브락은 교착 상태의 특별한 경우로 간주되기도 하지만, 주요 차이점은 프로세스의 상태에 있다. 교착 상태의 프로세스는 대기 상태에 머무는 반면, 라이브락의 프로세스는 실행 상태를 유지한다는 점이다. 이로 인해 시스템은 멈춘 것처럼 보이지 않을 수 있어 탐지가 더 어려울 수 있다. 해결 방법에는 프로세스들이 행동을 취하는 타이밍을 무작위화하거나, 시도 횟수를 제한하는 메커니즘을 도입하는 것이 포함된다.
