데드락(교착 상태)

상호 배제는 하나의 자원이 한 번에 하나의 프로세스에 의해서만 사용될 수 있음을 의미한다. 이는 공유 자원에 대한 동시 접근으로 인해 발생할 수 있는 데이터 불일치 문제를 방지하기 위한 기본적인 조건이다. 예를 들어, 프린터나 특정 데이터 레코드와 같은 자원은 동시에 여러 프로세스가 사용하려고 하면 오류가 발생할 수 있으므로, 한 프로세스가 사용을 완료할 때까지 다른 프로세스는 대기해야 한다.

이 조건은 데드락 발생의 네 가지 필요 조건 중 첫 번째에 해당한다. 상호 배제 조건 자체는 데드락을 직접적으로 유발하지 않지만, 자원에 대한 독점적 사용 권한을 보장함으로써 다른 프로세스의 대기를 유발하는 기반을 마련한다. 만약 모든 자원이 공유 가능하다면, 즉 여러 프로세스가 동시에 안전하게 사용할 수 있다면, 프로세스는 자원을 기다리며 멈출 필요가 없어 데드락 가능성이 크게 줄어든다.

따라서 상호 배제 조건을 제거하여 데드락을 예방하는 것은 실질적으로 불가능한 경우가 많다. 시스템의 많은 자원들은 본질적으로 상호 배제가 필수적이기 때문이다. 데드락 문제를 해결하기 위해서는 상호 배제 외의 다른 조건, 예를 들어 점유와 대기나 순환 대기 조건을 깨는 방향으로 접근하는 것이 일반적이다.

점유와 대기는 데드락이 발생하기 위한 네 가지 필요 조건 중 하나이다. 이 조건은 하나 이상의 프로세스가 이미 할당받은 자원을 보유한 상태에서, 다른 프로세스가 보유하고 있는 추가 자원을 얻기 위해 대기하는 상황을 의미한다. 즉, 각 프로세스는 현재 점유 중인 자원을 놓지 않으면서, 상대방이 가진 자원을 요청하고 기다린다.

이 조건이 성립하지 않도록 만드는 한 가지 방법은, 프로세스가 실행을 시작하기 전에 필요한 모든 자원을 한꺼번에 요청하고 할당받는 것이다. 이 방법을 자원 예약 또는 사전 할당이라고 한다. 프로세스는 필요한 모든 자원을 확보한 후에만 작업을 시작하며, 작업이 끝날 때까지 그 자원들을 보유한다. 따라서 작업 중간에 다른 자원을 요청하여 대기하는 상황 자체가 발생하지 않아 점유와 대기 조건이 제거된다.

그러나 이 방법은 심각한 단점을 가지고 있다. 자원의 활용도가 현저히 낮아질 수 있으며, 많은 자원을 필요로 하는 프로세스는 필요한 자원이 모두 가용 상태가 될 때까지 무기한 대기할 수 있다. 또한 프로세스가 실제로 사용할 자원을 정확히 예측하기 어려운 경우가 많아, 실용적으로 적용하기 힘든 경우가 많다. 따라서 점유와 대기 조건을 제거하는 것은 데드락 예방의 한 방법이지만, 시스템 효율성을 희생해야 하는 트레이드오프가 존재한다.

비선점(Non-preemption)은 데드락이 발생하기 위한 네 가지 필요 조건 중 하나이다. 이 조건은 이미 할당된 자원을 다른 프로세스가 강제로 빼앗을 수 없음을 의미한다. 즉, 한 프로세스가 어떤 자원을 점유하고 있다면, 그 프로세스가 작업을 완료하고 자발적으로 그 자원을 해제하기 전까지는 시스템이나 다른 프로세스가 그 자원을 회수할 수 없다.

대부분의 운영체제에서 프린터, 테이프 드라이브, 주변 장치와 같은 자원들은 본질적으로 비선점형이다. 예를 들어, 한 프로세스가 프린터를 할당받아 출력 작업을 시작했다면, 그 작업이 끝나기 전에는 다른 프로세스가 그 프린터 사용을 중단시키고 가져갈 수 없다. 만약 자원이 선점 가능했다면, 데드락이 발생하는 상황에서 시스템이 특정 프로세스로부터 자원을 강제로 회수하여 다른 프로세스에 할당함으로써 순환 대기 상태를 깨뜨릴 수 있다.

비선점 조건은 다음과 같이 두 가지 형태로 표현될 수 있다.

1. 프로세스가 보유한 자원은 그 프로세스가 작업을 끝내고 스스로 해제하기 전까지는 강제로 빼앗길 수 없다.

2. 한 프로세스가 새로운 자원을 요청했을 때, 그 자원을 즉시 사용할 수 없다면, 프로세스가 현재 보유하고 있는 모든 자원이 선점될 때까지 기다린다. 이후 필요한 모든 자원이 사용 가능해지면 프로세스가 재시작된다.

이 조건을 제거하여 데드락을 예방하는 것은 실용적이지 않은 경우가 많다. 많은 자원의 상태는 쉽게 저장하고 복원할 수 없기 때문이다. 예를 들어, 프린터나 공유 파일과 같은 자원을 작업 중간에 강제로 선점하면 데이터의 일관성이 깨지거나 출력물이 망가질 수 있다. 따라서 이 조건은 데드락의 필요 조건으로 남아 있으며, 데드락 처리 방법 중 예방 기법의 대상이 된다.

순환 대기는 데드락이 발생하기 위한 네 가지 필요 조건 중 하나이다. 이 조건은 두 개 이상의 프로세스나 스레드가 서로 다른 자원을 점유한 상태에서, 상대방이 점유하고 있는 자원을 추가로 요구하며 순환 형태의 대기 관계가 형성되는 상황을 가리킨다.

구체적으로, 프로세스 P1이 자원 R1을 보유하면서 자원 R2를 기다리고, 프로세스 P2는 자원 R2를 보유하면서 자원 R1을 기다리는 경우가 전형적인 순환 대기의 예이다. 이 관계는 두 개 이상의 프로세스로 확장되어 고리 형태를 이룰 수 있다. 예를 들어, P1 → R1 → P2 → R2 → P3 → R3 → P1과 같은 형태로 자원 요구와 점유가 순환 체인을 구성한다.

순환 대기 조건은 다른 세 조건(상호 배제, 점유와 대기, 비선점)이 모두 만족된 상태에서 발생하면 데드락을 유발하는 직접적인 계기가 된다. 이 조건을 방지하는 일반적인 방법은 모든 프로세스에게 자원을 요청할 때 일정한 순서(예: 자원에 고유 번호를 부여하고, 번호가 증가하는 방향으로만 요청)를 강제하는 것이다. 이렇게 하면 프로세스들이 자원을 요청하는 방향이 일정해져 순환 고리가 만들어질 가능성이 사라진다.

자원 할당 경쟁은 데드락 발생의 근본적인 원인 중 하나이다. 이는 시스템 내의 여러 프로세스나 스레드가 한정된 수의 동일한 자원을 동시에 요구할 때 발생하는 상황을 가리킨다. 각 프로세스는 작업을 완료하기 위해 CPU, 메모리, 파일, 프린터, 데이터베이스 레코드와 같은 자원을 필요로 한다. 이러한 자원의 수가 프로세스의 요구를 충족시키기에 부족할 경우, 프로세스들은 자원을 얻기 위해 서로 경쟁하게 된다.

경쟁의 구체적인 양상은 자원의 유형에 따라 달라진다. 예를 들어, 상호 배제 조건을 만족해야 하는 비공유 자원의 경우, 한 프로세스가 특정 자원을 점유하면 다른 프로세스는 그 자원을 사용할 수 없게 된다. 만약 프로세스 A가 프린터를 점유한 채 스캐너를 기다리고, 동시에 프로세스 B가 스캐너를 점유한 채 프린터를 기다린다면, 두 프로세스는 서로가 가진 자원을 무한정 기다리는 순환 대기 상태에 빠지게 된다. 이는 전형적인 데드락 상황이다.

자원 할당 경쟁이 데드락으로 이어지기 위해서는 일반적으로 점유와 대기, 비선점, 순환 대기 조건이 함께 충족되어야 한다. 시스템 설계나 자원 관리 정책은 이러한 경쟁의 강도를 조절하여 데드락 가능성을 높이거나 낮출 수 있다. 예를 들어, 자원의 종류와 수가 매우 제한적이거나, 프로세스들이 비슷한 순서로 자원을 요청하지 않고 무작위적으로 요청하는 환경에서는 경쟁이 심화되고 데드락 발생 확률이 높아진다.

프로세스의 실행 순서가 불완전하거나 비결정적인 경우 데드락이 발생할 수 있다. 특히 여러 프로세스가 공유 자원에 접근할 때, 특정 순서로 실행되면 안전하지만 다른 순서로 실행되면 교착 상태에 빠지는 경우가 있다. 이는 동기화 메커니즘이나 자원 할당 정책이 프로세스의 실행 순서를 제어하지 못할 때 두드러진다.

예를 들어, 두 개의 프로세스 P1과 P2가 각각 자원 A와 B를 필요로 한다고 가정하자. P1이 자원 A를 먼저 요청하고 획득한 후 자원 B를 요청하는 순서로 실행된다. P2는 자원 B를 먼저 요청하고 획득한 후 자원 A를 요청한다. 만약 두 프로세스가 거의 동시에 시작되어 P1이 A를, P2가 B를 각각 점유한 상태에서 상대방이 점유한 자원을 요청하게 되면 순환 대기 조건이 성립되어 데드락이 발생한다. 이는 각 프로세스의 실행 순서가 고정되어 있고, 운영체제가 이 순서를 조율하지 않으면 발생하는 전형적인 사례이다.

이러한 문제는 멀티스레딩 프로그래밍에서도 흔히 나타난다. 스레드들이 락을 획득하는 순서가 일관되지 않으면, 각 스레드가 서로 다른 순서로 락을 점유하려 시도함에 따라 데드락에 빠질 위험이 높아진다. 이를 방지하기 위한 일반적인 방법은 모든 프로세스나 스레드가 공유 자원을 요청할 때 동일한 순서를 따르도록 강제하는 것이다. 예를 들어, 자원에 전역적인 순서(예: A 항상 B보다 먼저)를 부여하고, 모든 프로세스가 그 순서대로만 자원을 요청하도록 하면 순환 대기가 형성되지 않아 데드락을 예방할 수 있다.

시스템 자원 부족은 데드락 발생의 근본적인 원인 중 하나이다. 프로세스들이 필요로 하는 자원의 총량이 시스템이 실제로 보유하고 있는 자원의 양을 초과할 가능성이 있을 때, 경쟁이 심화되고 데드락에 빠질 위험이 높아진다.

예를 들어, 시스템에 프린터가 1대만 설치되어 있지만, 동시에 실행되는 여러 프로세스가 각각 출력 작업을 필요로 하는 경우를 생각해 볼 수 있다. 한 프로세스가 프린터를 점유하면, 다른 프로세스들은 그 자원을 얻기 위해 대기해야 한다. 만약 이들 대기 중인 프로세스들이 추가적으로 다른 자원들(예: 스캐너, 파일 핸들)을 보유한 채 서로 순환적으로 자원을 요구하는 상황이 발생하면, 시스템 자원의 절대적 부족이 데드락을 유발하는 계기가 된다.

메모리와 같은 자원의 부족도 간접적으로 데드락을 초래할 수 있다. 가용 주기억장치가 부족하면 시스템은 페이지 교체를频繁하게 수행하게 되고, 이 과정에서 프로세스들의 실행이 지연된다. 이 지연은 프로세스들이 보유한 자원을 장시간 점유하게 만드는 결과를 낳아, 다른 프로세스들이 그 자원을 사용할 수 없는 '점유와 대기' 상태를 연장시킨다. 결국 순환 대기 조건이 성립될 가능성이 높아진다.

따라서 시스템 설계나 용량 계획 시, 예상되는 작업 부하에 비해 자원이 지나치게 제한적이지 않도록 하는 것이 중요하다. 그러나 자원을 무제한으로 확보하는 것은 비용상 현실적이지 않을 수 있으므로, 자원 부족 상황에서도 데드락을 관리할 수 있는 데드락 처리 방법이 함께 고려되어야 한다.

데드락 예방은 데드락의 네 가지 필요 조건 중 하나 이상을 시스템이 절대 허용하지 않도록 만드는 접근법이다. 이는 조건 자체를 부정함으로써 데드락 발생 가능성을 근본적으로 차단한다.

첫째, 상호 배제 조건을 부정하는 방법은 모든 자원을 공유 가능하게 만드는 것이다. 그러나 프린터나 테이프 드라이브 같은 자원은 본질적으로 한 순간에 하나의 프로세스만이 사용해야 하므로, 이 방법은 현실적으로 적용하기 어렵다. 둘째, 점유와 대기 조건을 부정하기 위해서는 프로세스가 필요한 모든 자원을 시작 시점에 한꺼번에 요청하고 할당받아야 한다. 이는 자원 활용도를 심각하게 저하시키며, 프로세스가 실제로 필요로 하기 전까지 자원을 점유하게 만드는 단점이 있다. 셋째, 비선점 조건을 부정하는 것은 이미 할당된 자원을 운영체제가 강제로 회수할 수 있도록 하는 것이다. 이 방법은 프로세스 상태를 저장하고 복원하는 오버헤드가 크며, 프린터 같은 자원에는 적용하기 힘들다.

마지막으로, 순환 대기 조건을 부정하는 가장 일반적인 방법은 모든 자원에 전역적인 순서(예: 자원 계층 구조)를 부여하고, 프로세스가 항상 그 순서의 증가 방향으로만 자원을 요청하도록 강제하는 것이다. 예를 들어, 자원 A(순서 1)와 자원 B(순서 2)가 있을 때, 프로세스가 B를 필요로 한다면 반드시 A를 먼저 요청하고 획득한 후에 B를 요청해야 한다. 이는 프로세스가 자원을 기다리는 방향이 단방향이 되도록 보장하여 순환 고리가 생기는 것을 원천적으로 방지한다.

이러한 예방 기법들은 데드락을 확실히 방지할 수 있지만, 시스템 처리량 감소나 자원 활용도 저하 같은 심각한 성능 저하를 동반하는 경우가 많다. 따라서 실용적인 시스템에서는 덜 제한적인 다른 접근법(데드락 회피나 데드락 탐지)이 더 선호된다.

데드락 회피는 시스템이 데드락이 발생할 가능성을 사전에 판단하여, 발생 가능성이 있는 경우 자원 할당을 허용하지 않음으로써 데드락을 사전에 차단하는 방법이다. 데드락 예방이 데드락의 필요 조건 자체를 제거하는 강력한 방법이라면, 회피는 시스템이 항상 안전 상태를 유지하도록 보장하는 더 유연한 접근법이다.

회피 알고리즘의 핵심은 시스템이 특정 자원 요청을 허용했을 때, 이후 모든 프로세스가 정상적으로 종료될 수 있는 안전한 순서가 존재하는지, 즉 안전 상태를 유지할 수 있는지를 미리 검사하는 것이다. 가장 대표적인 알고리즘은 은행원 알고리즘이다. 이 알고리즘은 각 프로세스가 필요로 할 최대 자원 수를 사전에 신고하게 하고, 자원 요청이 들어올 때마다 가상으로 자원을 할당해본 후 시스템이 여전히 안전 상태에 머무를 수 있는지를 시뮬레이션한다. 안전 상태가 보장되면 실제 할당을 수행하고, 그렇지 않으면 프로세스는 자원을 할당받기까지 대기해야 한다.

데드락 회피는 데드락을 완전히 방지하면서도 상호 배제나 비선점 같은 조건을 제거하지 않아 자원 활용도를 높일 수 있다는 장점이 있다. 그러나 이 방법은 프로세스 수나 자원 종류가 많아질수록 검사에 드는 오버헤드가 크며, 각 프로세스가 필요로 할 최대 자원 수를 사전에 알고 있어야 한다는 실용적인 제약이 있다. 또한 자원의 총수가 고정되어 있어야 하므로 동적으로 변하는 시스템 환경에는 적용하기 어렵다.

데드락이 이미 시스템에 발생했는지 확인하고, 발생했다면 이를 해결하여 시스템을 정상 상태로 되돌리는 접근법이다. 이 방법은 데드락이 드물게 발생하는 환경에서 주로 사용되며, 데드락 예방이나 데드락 회피 기법에 비해 자원 이용률과 시스템 처리량이 높다는 장점이 있다. 그러나 탐지와 복구 과정 자체가 시스템에 추가적인 오버헤드를 발생시킨다.

탐지 단계에서는 시스템의 현재 상태를 주기적으로 또는 특정 조건 하에 검사한다. 주요 탐지 방법으로는 자원 할당 그래프를 사용하는 방법과 은행원 알고리즘과 유사한 방법을 사용하는 것이 있다. 자원 할당 그래프에서 사이클이 존재하면 데드락이 발생했음을 나타낸다. 보다 일반적인 시스템에서는 각 프로세스의 자원 요청, 보유, 가용 자원 수 등의 정보를 활용한 알고리즘을 통해 안전 상태 여부를 판단하여 데드락을 탐지한다.

복구 단계는 탐지된 데드락을 해소하는 과정이다. 복구 기법은 크게 두 가지로 나뉜다. 첫째는 프로세스 종료 방식이다. 데드락에 연루된 모든 프로세스를 한꺼번에 종료하는 방법이 가장 간단하지만, 손실이 크다. 따라서 데드락이 제거될 때까지 한 번에 하나의 프로세스만 순차적으로 종료하는 방법을 사용하여 비용을 최소화하려고 한다. 둘째는 자원 선점 방식이다. 데드락에 연루된 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당함으로써 데드락 사이클을 깨는 방법이다. 이때 자원을 빼앗길 프로세스를 선정하는 기준(예: 최소 비용, 우선순위)과, 선점된 프로세스를 이후 어떻게 재시작할지(롤백)에 대한 정책이 필요하다.

데드락 무시는 운영체제나 시스템이 데드락의 발생 가능성을 인정하지만, 특별한 조치를 취하지 않는 접근 방식이다. 이 방법은 데드락이 매우 드물게 발생하거나, 처리 비용이 예방이나 회피, 탐지의 비용보다 클 것으로 판단될 때 선택된다.

가장 대표적인 예는 유닉스와 리눅스 커널을 포함한 많은 범용 운영체제이다. 이러한 시스템들은 데드락이 실제로 발생할 확률이 극히 낮으며, 데드락을 처리하기 위한 메커니즘을 구현하는 것이 시스템의 복잡성과 성능 오버헤드를 증가시켜 전체적인 효율성을 떨어뜨린다고 판단한다. 대신, 시스템 관리자나 개발자에게 문제 해결을 맡기고, 필요시 프로세스를 수동으로 종료하는 방식을 취한다.

이 방식의 장점은 구현이 간단하고 추가적인 오버헤드가 전혀 없다는 점이다. 그러나 명백한 단점은 데드락이 실제로 발생했을 때 시스템이 응답하지 않는 상태에 빠질 수 있으며, 사용자나 관리자가 직접 개입하여 시스템을 재시작하거나 프로세스를 강제 종료해야 한다는 것이다. 따라서 이 방법은 데드락의 영향이 제한적이고 복구가 비교적 쉬운 환경에서 주로 적용된다.

자원 할당 그래프는 시스템의 프로세스와 자원 간의 할당 및 요청 관계를 방향성 그래프로 표현한 모델이다. 이 그래프를 통해 시스템의 상태를 시각적으로 파악하고, 데드락이 발생했는지 여부를 탐지할 수 있다. 그래프는 정점과 간선으로 구성되며, 정점은 프로세스와 자원을 나타내고, 간선은 이들 간의 관계를 나타낸다.

그래프는 두 종류의 정점(P, R)과 두 종류의 간선으로 구성된다. 정점 P는 프로세스를, 정점 R은 자원을 나타낸다. 자원 정점 내부의 점(•)은 해당 자원의 이용 가능한 인스턴스 수를 의미한다. 간선은 할당 간선과 요청 간선으로 구분된다. 할당 간선은 자원(R)에서 프로세스(P)를 향하는 화살표로, 해당 자원이 프로세스에 할당되었음을 의미한다. 요청 간선은 프로세스(P)에서 자원(R)을 향하는 화살표로, 프로세스가 해당 자원을 요청하고 대기 중임을 의미한다.

데드락 탐지는 이 그래프에서 순환이 존재하는지 확인하는 과정이다. 그래프에 순환이 존재하지 않으면 시스템은 데드락 상태가 아니다. 반면, 그래프에 순환이 존재하면 시스템은 데드락 상태일 가능성이 있다. 특히, 각 자원 유형이 정확히 하나의 인스턴스만 갖는 경우, 그래프 내의 순환은 데드락이 발생했음을 의미하는 필요충분 조건이 된다. 그러나 자원 유형이 여러 개의 인스턴스를 가질 경우, 순환이 존재해도 데드락이 아닐 수 있으므로 추가적인 분석이 필요하다.

이 그래프는 개념적으로 이해하기 쉬운 탐지 방법을 제공하지만, 대규모 시스템에서 주기적으로 그래프를 구성하고 순환을 탐지하는 것은 오버헤드를 유발할 수 있다. 따라서 실제 시스템에서는 이 방법을 변형하거나, 은행원 알고리즘과 같은 다른 방법과 함께 사용된다.

은행원 알고리즘은 데드락을 회피하기 위해 에즈허르 데이크스트라가 제안한 알고리즘이다. 이 알고리즘은 은행이 고객들의 대출 요청을 안전하게 처리하는 방식에서 아이디어를 얻었다[2]. 시스템이 프로세스들에게 자원을 할당할 때, 항상 '안전 상태'를 유지할 수 있는 경우에만 자원을 할당한다. 안전 상태란 모든 프로세스가 정상적으로 자원을 할당받고 작업을 완료할 수 있는 일련의 순서, 즉 '안전 순서열'이 존재하는 상태를 의미한다.

알고리즘은 다음과 같은 데이터 구조를 필요로 한다.

• 가용 자원: 현재 시스템에서 사용 가능한 각 자원의 개수.

• 최대 요구량: 각 프로세스가 필요로 하는 각 자원의 최대 개수.

• 할당량: 현재 각 프로세스에 할당된 각 자원의 개수.

• 추가 요구량: 각 프로세스가 향후 추가로 요구할 수 있는 각 자원의 개수 (최대 요구량 - 할당량).

자원 할당 요청이 들어오면, 알고리즘은 그 요청을 가상으로 승인한 후 시스템 상태가 여전히 안전한지 검사한다. 검사는 가용 자원으로 현재 요구를 충족시킬 수 있는 프로세스를 찾아, 그 프로세스가 작업을 끝내고 자원을 모두 반납한다고 가정하는 시뮬레이션을 통해 이루어진다. 이러한 과정을 반복하여 모든 프로세스의 작업 완료 시뮬레이션이 성공하면 안전 상태로 판단하고 실제 자원을 할당한다. 만약 안전 상태가 아니면, 해당 자원 요청은 즉시 거부되고 프로세스는 대기 상태가 된다.

이 알고리즘의 장점은 데드락이 발생할 가능성을 사전에 차단한다는 점이다. 그러나 단점도 명확하다. 프로세스 수와 자원 종류가 많아질수록 필요한 정보의 양과 검사에 드는 오버헤드가 크게 증가한다. 또한 각 프로세스가 필요로 하는 최대 자원 수를 미리 알고 있어야 하며, 자원의 총 수가 고정되어 있어야 한다는 제약 조건이 있다. 이러한 이유로 은행원 알고리즘은 주로 학술적 모델이나 특정 제한된 환경에서 참고용으로 사용되며, 일반적인 운영체제에서는 다른 데드락 처리 방법이 더 널리 적용된다.

프로세스 종료는 데드락에서 복구하기 위해 하나 이상의 프로세스를 강제로 종료시키는 방법이다. 이 기법은 데드락에 연루된 프로세스를 제거함으로써 순환 대기 조건을 깨고 시스템에 할당된 자원을 회수하는 것을 목표로 한다. 프로세스 종료 방식은 주로 두 가지로 구분된다.

첫 번째 방식은 데드락에 연루된 모든 프로세스를 한꺼번에 종료하는 것이다. 이 방법은 구현이 간단하고 확실하게 데드락을 제거할 수 있지만, 많은 작업이 손실될 수 있으며 시스템의 전체 처리량에 큰 영향을 미친다. 두 번째 방식은 데드락이 해소될 때까지 한 번에 하나의 프로세스만 순차적으로 종료하는 것이다. 매번 프로세스를 종료한 후에는 데드락 탐지 알고리즘을 다시 실행하여 데드락 상태가 지속되는지 확인한다. 이 방식은 불필요한 프로세스 종료를 최소화하려는 시도이다.

어떤 프로세스를 먼저 종료할지 결정하는 기준은 복구의 효율성을 높이기 위해 중요하다. 일반적으로 고려되는 요소는 다음과 같다.

프로세스 종료 시, 해당 프로세스가 완전히 종료되거나 처음부터 다시 시작될 수 있다. 부분적으로 롤백되어 안전한 상태로 복귀한 후 재개될 수도 있다. 이 선택은 프로세스의 특성과 시스템의 요구사항에 따라 달라진다.

자원 선점은 데드락에서 복구하기 위해 한 프로세스가 점유하고 있는 자원을 강제로 빼앗아 다른 프로세스에게 할당하는 기법이다. 이 방법은 선점된 프로세스의 실행이 일시 중단되거나 롤백되어야 하므로 신중하게 적용해야 한다.

자원을 선점할 프로세스를 선택하는 기준은 여러 가지가 있다. 일반적으로 우선순위가 낮은 프로세스, 최근에 시작된 프로세스, 남은 실행 시간이 짧은 프로세스, 또는 지금까지 사용한 자원이 적은 프로세스 등을 대상으로 선정한다[4]. 선점 과정에서 프로세스의 상태를 안전하게 저장하고 이후 재시작할 수 있도록 보장하는 것이 중요하다.

선점된 자원을 다른 프로세스에 할당한 후, 시스템은 데드락 상태에서 벗어나 정상적인 자원 할당이 가능해진다. 그러나 선점으로 인한 부작용, 예를 들어 선점된 프로세스의 실패 또는 일관성 문제가 발생할 수 있으므로, 트랜잭션 시스템에서는 롤백과 재시작 메커니즘을 함께 사용하는 경우가 많다.

데이터베이스 시스템은 교착 상태가 빈번히 발생할 수 있는 전형적인 환경이다. 여러 트랜잭션이 동시에 데이터베이스의 같은 자원(예: 테이블의 특정 행 또는 페이지)에 접근하고 변경을 시도할 때 발생한다. 데이터베이스에서의 자원은 주로 데이터베이스 락의 형태로 관리되며, 트랜잭션은 데이터의 일관성을 유지하기 위해 필요한 락을 획득하고 해제한다.

교착 상태는 주로 두 개 이상의 트랜잭션이 서로가 점유한 락을 필요로 하면서 상대방이 그것을 해제하기를 무한정 기다릴 때 발생한다. 예를 들어, 트랜잭션 A가 행 R1에 대한 배타적 락을 획득하고 행 R2에 대한 락을 요청하는 동안, 트랜잭션 B는 행 R2에 대한 배타적 락을 이미 획득한 상태에서 행 R1에 대한 락을 요청하면 순환 대기 조건이 성립된다.

대부분의 현대 관계형 데이터베이스 관리 시스템은 내장된 교착 상태 탐지 및 해결 메커니즘을 갖추고 있다. 일반적으로 시스템은 주기적으로(또는 락 요청 타임아웃 시) 자원 할당 그래프를 분석하거나 대기 그래프를 검사하여 교착 상태를 탐지한다. 탐지되면, 시스템은 복구를 수행하는데, 일반적으로 롤백 비용이 가장 적게 드는 트랜잭션을 희생자로 선택하여 강제 종료하고, 해당 트랜잭션이 보유한 모든 락을 해제한다. 이로 인해 다른 트랜잭션들이 진행할 수 있게 된다.

데이터베이스 설계자와 개발자는 교착 상태의 발생 가능성을 줄이기 위해 여러 지침을 따른다. 모든 트랜잭션이 항상 같은 순서로 자원(예: 테이블 또는 행)에 락을 걸도록 하는 것이 가장 일반적인 예방 방법이다. 또한, 트랜잭션의 지속 시간을 짧게 유지하고, 불필요한 락의 점유 시간을 최소화하며, 적절한 트랜잭션 격리 수준을 선택하는 것도 중요하다.

운영체제는 프로세스와 시스템 자원을 관리하는 핵심 소프트웨어로서, 데드락이 발생할 수 있는 전형적인 환경을 제공한다. 운영체제 내부에서 데드락은 주로 메모리, CPU, I/O 장치와 같은 자원을 여러 프로세스가 경쟁적으로 요구할 때 발생한다. 예를 들어, 한 프로세스가 프린터를 점유한 채 스캐너를 요구하고, 다른 프로세스는 스캐너를 점유한 채 프린터를 요구하는 상황에서 순환 대기가 형성되면 데드락에 빠진다.

대표적인 사례로는 유닉스 계열 시스템에서 두 개의 프로세스가 서로의 출력을 파이프로 연결하려 할 때 발생할 수 있다. 한 프로세스가 파이프의 쓰기 끝을, 다른 프로세스가 읽기 끝을 독점적으로 점유하려 하면 양쪽 모두 상대방이 점유한 자원을 기다리며 무한정 대기하는 데드락 상태가 된다. 또한, 세마포어나 뮤텍스와 같은 동기화 기법을 잘못 사용할 경우, 여러 프로세스가 두 개 이상의 잠금을 서로 다른 순서로 획득하려 시도하다가 데드락에 빠지는 경우도 흔하다.

운영체제는 이러한 데드락 문제를 다루기 위해 다양한 정책을 채택한다. 많은 범용 운영체제 (예: 리눅스, 윈도우)는 데드락 예방이나 회피보다는 데드락이 실제로 발생할 가능성이 비교적 낮다고 판단하여 데드락 무시 전략을 사용하는 경우가 많다. 이는 데드락 처리에 따른 성능 오버헤드를 감수하지 않기 위한 선택이다. 반면, 실시간 시스템이나 고가용성이 요구되는 시스템에서는 은행원 알고리즘과 같은 회피 알고리즘을 적용하거나, 타임아웃 메커니즘을 통해 일정 시간 자원을 얻지 못하면 잠금을 포기하도록 설계하기도 한다.

라이브락(Livelock)은 두 개 이상의 프로세스나 스레드가 서로의 상태 변화에 반응하여 계속해서 실행되지만, 실제로는 유용한 작업을 전혀 수행하지 못하고 정체된 상태를 말한다. 데드락이 자원을 점유한 채 영원히 대기하는 정적인 상태라면, 라이브락은 프로세스들이 활발하게 상태를 변경하며 움직이지만, 그 움직임이 시스템의 진전을 이끌어내지 못하는 동적인 정체 상태이다.

라이브락은 주로 교착 상태 회피나 동기화를 위한 알고리즘에서 발생한다. 예를 들어, 두 개의 프로세스가 각각 하나의 자원을 점유한 상태에서 상대방이 필요한 다른 자원을 동시에 양보하려고 시도할 때 발생할 수 있다. 프로세스 A가 자원 1을 점유하고 자원 2를 기다리며, 프로세스 B가 자원 2를 점유하고 자원 1을 기다리는 상황에서, 둘 다 데드락을 피하기 위해 자신의 자원을 일시적으로 양보한다고 가정해보자. 만약 두 프로세스가 타이밍을 맞춰 동시에 자원을 놓고 다시 대기 상태로 들어간다면, 그들은 계속해서 자원을 놓고, 대기하고, 다시 시도하는 무한 루프에 빠지게 된다. 이들은 CPU 시간을 소비하며 실행되지만, 결코 필요한 자원을 모두 얻어 작업을 완료하지 못한다.

라이브락과 기아 상태는 모두 진전이 없는 상태이지만 구별된다. 기아 상태는 특정 프로세스가 계속해서 자원 할당 요청이 거부당해 실행 기회를 얻지 못하는 불평등한 상태인 반면, 라이브락의 프로세스들은 실행 기회는 얻지만, 그들의 상호작용 방식 때문에 전체 시스템이 정체된다. 라이브락을 해결하기 위해서는 일반적으로 프로세스들의 행동 패턴에 무작위성이나 지연을 도입하여 동기화 타이밍을 깨는 방법을 사용한다[6].

기아 상태는 특정 프로세스나 스레드가 시스템 자원을 지속적으로 할당받지 못해 실행이 지연되거나 중단되는 현상이다. 교착 상태와 달리 프로세스는 여전히 실행 가능한 상태에 있지만, 스케줄러나 자원 관리자의 정책상 반복적으로 자원 할당 요청이 거부당한다. 이는 주로 우선순위 기반 스케줄링이나 특정 자원 할당 알고리즘에서 발생할 수 있다.

기아 상태의 주요 원인은 불공정한 자원 할당 정책이다. 예를 들어, 높은 우선순위를 가진 프로세스가 계속해서 들어오거나, 선입 선출 큐에서 특정 프로세스가 계속해서 뒤로 밀리는 경우에 발생한다. 데드락이 상호 배타적인 자원 점유로 인한 순환 대기라면, 기아 상태는 특정 프로세스가 자원 경쟁에서 계속 소외되는 것이다.

기아 상태를 완화하거나 방지하기 위한 기법은 다양하다. 에이징은 대기 시간이 길어질수록 프로세스의 우선순위를 점진적으로 높여 결국 자원을 할당받도록 보장한다. 또한, 자원 할당 시 공정성을 유지하는 라운드 로빈 스케줄링이나 자원 할당 큐를 사용한 관리도 효과적이다.

기아 상태는 시스템의 전체 처리량에는 큰 영향을 주지 않을 수 있지만, 특정 프로세스의 응답 시간을 극단적으로 저하시켜 시스템의 공정성과 신뢰성을 해칠 수 있다. 따라서 운영체제나 분산 시스템 설계 시 반드시 고려해야 하는 중요한 개념이다.