본문으로 건너뛰기

교착 상태

운영체제 : 교착 상태(Deadlock)의 이해와 해결

1. Executive Summary: 교착 상태 핵심 요약​

목적과 핵심 요약​

이 브리핑은 운영체제(OS) 환경에서 발생하는 핵심적인 문제 중 하나인 교착 상태(Deadlock) 의 개념을 명확히 정의하고,
발생 조건과 다양한 해결 방안을 체계적으로 설명하는 것을 목적으로 합니다. 교착 상태란 둘 이상의 프로세스가 서로 상대방이 점유한 자원을 무한정 기다리며 작업이 중단되는 현상을 의미합니다.

이러한 문제를 해결하기 위해,
교착 상태의 발생 조건 자체를 원천적으로 차단하는 예방(Prevention), 자원 할당 시 위험성을 사전에 검사하는 회피(Avoidance),
그리고 교착 상태 발생을 허용한 뒤 사후에 조치하는 검출 및 회복(Detection & Recovery) 전략이 사용됩니다.

일상 속 예시를 통한 개념 설명​

교착 상태는 '양보 없는 일방통행 다리'의 상황으로 쉽게 이해할 수 있습니다.
다리의 각 구간을 시스템 '자원'으로, 다리를 건너는 차량을 '프로세스'로 비유해 보겠습니다.

양쪽에서 동시에 진입한 차량들이 다리 한가운데서 마주치면, 어느 쪽도 앞으로 나아갈 수 없는 상태가 됩니다.
각 차량은 상대방이 길을 비켜주기(자원을 놓아주기)만을 기다리며 꼼짝도 할 수 없습니다.
이 상황이 바로 교착 상태입니다. 이 문제를 해결하기 위해서는 외부의 개입, 즉 한쪽 차량이 후진(자원 해제 및 양보)하여 길을 터주는 것 외에는 다른 방법이 없습니다.

2. 교착 상태(Deadlock)의 정의와 기본 개념​

다중 프로그래밍 환경에서 여러 프로세스가 한정된 자원을 공유하는 것은 필연적이며, 이 과정에서 교착 상태는 시스템의 성능과 안정성을 심각하게 저해하는 문제로 이어질 수 있습니다.
따라서 교착 상태의 공식적인 정의를 이해하고, 유사하지만 다른 개념인 기아 상태(Starvation) 와의 차이점을 명확히 구분하는 것은 문제 해결의 첫걸음입니다.

교착 상태의 공식 정의​

교착 상태(Deadlock)는 둘 이상의 프로세스들이 자원을 점유한 상태에서 서로 다른 프로세스가 점유하고 있는 자원을 요구하며 무한정 기다리는 상태로 정의됩니다.
이 현상은 단순히 시스템 자원(예: CPU, 메모리) 할당뿐만 아니라, 공유 데이터에 대한 동시 접근을 제어하는 잠금(lock) 메커니즘, 데이터베이스 트랜잭션과 같은 다양한 응용 프로그램 환경에서도 발생할 수 있습니다.

교착 상태와 기아 상태 비교 분석​

교착 상태는 종종 기아 상태와 혼동되지만, 두 현상은 원인과 상태 진행, 해결 방법에서 뚜렷한 차이를 보입니다.

구분교착 상태 (Deadlock)기아 상태 (Starvation)
개념 및 원인프로세스들이 서로가 점유한 리소스를 순환적으로 대기하며 발생합니다.특정 프로세스가 자원에 대한 우선순위가 낮거나 스케줄링 정책의 문제로 인해 자원에 계속 접근하지 못하고 대기하는 상황입니다.
상태 진행관련된 모든 프로세스가 아무런 진전을 보이지 못하고 시스템 전체가 멈출 수 있습니다.다른 프로세스들은 정상적으로 계속 진행될 수 있으며, 특정 프로세스만 작업을 수행하지 못합니다.
해결 방법외부의 개입을 통해 프로세스를 강제 종료하거나 자원을 강제로 해제해야 해결 가능합니다.우선순위 동적 조정(e.g., 에이징) 등 공정한 스케줄링 정책을 적용하여 모든 프로세스가 자원을 할당받을 기회를 갖도록 조정하여 해결할 수 있습니다.

3. 교착 상태의 발생 조건 분석​

교착 상태는 우연히 발생하는 현상이 아니라, 아래에 설명할 네 가지 특정 조건이 모두 동시에 충족될 때만 발생하는 필연적인 결과입니다. 따라서 이 네 가지 필요조건을 정확히 이해하는 것은 교착 상태를 예방하고, 진단하며, 해결하는 모든 전략의 근본적인 기초가 됩니다.

네 가지 필요조건 (Necessary Conditions)​

교착 상태가 발생하기 위해서는 아래의 네 가지 조건이 반드시 동시에 성립해야 합니다. 이 중 단 하나라도 충족되지 않으면 교착 상태는 발생하지 않습니다.

  • 상호 배제 (Mutual Exclusion) 자원은 한 번에 오직 하나의 프로세스만 사용할 수 있어야 합니다. 즉, 공유가 불가능한 배타적인 자원이어야 합니다.
  • 점유와 대기 (Hold and Wait) 프로세스가 최소한 하나 이상의 자원을 점유하고 있는 상태에서, 다른 프로세스에 할당된 자원을 추가로 요청하며 대기할 수 있어야 합니다.
  • 비선점 (Non-preemption) 한 프로세스에 할당된 자원은 사용이 끝날 때까지 다른 프로세스가 강제로 빼앗을 수 없어야 합니다. 자원의 반납은 오직 점유한 프로세스 자신만이 할 수 있습니다.
  • 원형 대기 (Circular Wait) 자원을 기다리는 프로세스들 간에 순환적인 사슬이 형성되어야 합니다. 즉, 프로세스 P0는 P1이 가진 자원을, P1은 P2가 가진 자원을, ..., Pn은 P0가 가진 자원을 기다리는 원형의 대기열이 존재해야 합니다.

사례 연구: 식사하는 철학자 문제​

'식사하는 철학자 문제(The Dining Philosophers Problem)'는 위 네 가지 조건이 어떻게 교착 상태를 유발하는지 보여주는 고전적인 예시입니다. 원형 식탁에 앉은 철학자들이 식사를 하기 위해서는 자신의 왼쪽과 오른쪽 포크를 모두 집어야 합니다.

이 문제에 네 가지 조건을 대입해 보면 다음과 같습니다.

  • 상호 배제: 하나의 포크는 동시에 한 명의 철학자만 사용할 수 있습니다.
  • 점유와 대기: 각 철학자는 자신의 왼쪽 포크를 집은 상태에서, 오른쪽 포크를 사용할 수 있을 때까지 기다립니다.
  • 비선점: 옆 사람이 사용 중인 포크를 강제로 빼앗을 수 없습니다.
  • 원형 대기: 만약 모든 철학자가 동시에 자신의 왼쪽 포크를 집는다면, 각 철학자는 자신의 오른쪽에 앉은 철학자가 왼쪽 포크(즉, 자신의 오른쪽 포크)를 놓기만을 기다리는 원형의 대기열이 형성되어 아무도 식사를 시작하지 못하는 교착 상태에 빠지게 됩니다.

4. 교착 상태 해결을 위한 전략적 접근​

교착 상태를 다루는 방법은 크게 세 가지 범주로 나눌 수 있습니다: 예방(Prevention), 회피(Avoidance), 그리고 검출 및 회복(Detection & Recovery).
각 전략은 문제에 대한 근본적으로 다른 철학을 반영하며, 시스템의 요구사항, 성능, 자원 효율성 측면에서 뚜렷한 장단점을 가집니다.

교착 상태 예방 (Prevention)​

  • 개념 설명 '예방'은 네 가지 필요조건 중 최소 하나를 원천적으로 성립하지 않도록 시스템을 설계하여 교착 상태 발생 가능성 자체를 없애는 가장 강력하고 근본적인 접근법입니다.
  • 각 조건의 무력화 시도와 한계 분석
    • 상호 배제 부정: 모든 자원을 공유 가능하게 만드는 것은 현실적으로 불가능합니다. 프린터와 같은 물리적 장치나 중요한 데이터 구조는 반드시 보호되어야 합니다.
    • 점유와 대기 부정: 이는 프로세스가 실행 전 필요한 모든 자원을 한꺼번에 요청하도록 강제하는 '전부 할당하거나 아니면 아예 할당하지 않는(all-or-nothing)' 방식으로, 당장 사용하지 않을 자원까지 미리 점유하게 되어 심각한 자원 낭비와 활용성 저하를 초래합니다.
    • 비선점 부정: 다른 프로세스의 자원을 강제로 빼앗는 방식은 작업의 일관성을 해칠 수 있으며, 우선순위가 낮은 프로세스가 계속해서 자원을 빼앗기는 '기아 상태'를 유발할 수 있어 신중한 설계가 필요합니다.
    • 원형 대기 부정: 모든 자원에 고유한 번호를 부여하고 오름차순으로만 자원을 요청하도록 강제하는 방식은, 프로세스의 작업 유연성을 크게 떨어뜨리며 모든 자원에 합리적인 순서를 부여하기 어렵다는 문제가 있습니다.
  • 결론 교착 상태 예방은 이론적으로는 완벽한 해결책처럼 보이지만, 대부분의 방법이 심각한 자원 낭비와 시스템 성능 저하라는 트레이드오프를 감수해야 하므로 현실적인 시스템에 적용하기는 매우 어렵습니다.

교착 상태 회피 (Avoidance)​

  • 개념 설명 '회피'는 교착 상태 발생 가능성을 인정하되, 자원을 할당할 때마다 시스템이 교착 상태에 빠질 위험이 없는 안정 상태(Safe State) 를 유지하는지 검사하여, 위험을 초래할 수 있는 할당 요청을 거부하는 방식입니다. 교착 상태는 '불안정 상태(Unsafe State)'의 한 경우로 간주됩니다.
  • 핵심 알고리즘: 은행원 알고리즘 (Banker's Algorithm)
    • 은행원 알고리즘은 교착 상태 회피를 구현하는 대표적인 방법입니다.
    • 이 알고리즘은 시스템 내 자원의 수가 한정적이고, 각 프로세스가 사전에 필요한 자원의 최대량을 선언해야 한다는 강력한 전제 조건 하에 동작합니다. 이는 시스템의 상태를 총 자원(Total), 현재 가용 자원(Available), 각 프로세스의 최대 필요량(Max) 및 현재 할당량(Allocation)과 같은 변수들을 통해 지속적으로 추적함으로써 달성됩니다.
    • '안정 상태'란, 현재 가용 자원으로 각 프로세스의 기대 자원(최대 요구량 - 현재 할당량)을 만족시킬 수 있는 안전한 실행 순서가 최소 하나 이상 존재하는 상태 로 정의됩니다. 시스템은 자원 할당 요청이 들어올 때마다, 해당 요청을 수락한 후에도 시스템이 안정 상태를 유지할 수 있는지 시뮬레이션하고 그 결과에 따라 할당 여부를 결정합니다.
  • 회피 전략의 문제점
    • 자원 이용률 저하: 안정 상태 유지를 위해 자원이 있어도 할당을 보류하는 경우가 생겨 자원 활용도가 떨어집니다.
    • 미래 자원 요구량 예측의 어려움: 프로세스가 실행 전에 자신의 최대 자원 요구량을 정확히 예측하기는 매우 어렵습니다.
    • 복잡성 및 성능 저하: 자원 할당 시마다 복잡한 알고리즘을 실행해야 하므로 시스템에 상당한 오버헤드를 유발합니다.

교착 상태 검출 및 회복 (Detection & Recovery)​

  • 개념 설명 '검출 및 회복'은 교착 상태 예방이나 회피를 위한 제약을 가하지 않고, 교착 상태가 발생하는 것을 허용하되 주기적으로 시스템을 감시하여 교착 상태를 검출하고, 발견 시 이를 회복시키는 가장 현실적인 접근법입니다.
  • 검출 기법
    • 자원 할당 그래프 분석: 자원 할당 그래프에서 순환(cycle)이 발생하는지 탐지하여 교착 상태를 검출할 수 있습니다.
    • 타임아웃(Timeout) 활용: 일정 시간 이상 응답이 없는 프로세스를 교착 상태로 간주하는 간단한 방법입니다. 특별한 알고리즘 없이 쉽게 구현할 수 있다는 장점이 있지만, 단순히 작업이 오래 걸리는 것을 교착 상태로 오진할 수 있습니다.
  • 회복 기법 교착 상태가 검출되면 다음과 같은 방법으로 시스템을 회복시킵니다.
    • 프로세스 종료: 교착 상태에 연관된 프로세스 중 하나 또는 전부를 강제로 종료하여 교착 상태의 순환 고리를 끊습니다.
    • 자원 선점 (Resource Preemption): 특정 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에 할당합니다. 이 경우, 작업을 어느 지점부터 재시작할지(롤백, rollback) 결정하는 문제가 복잡하게 얽혀 있습니다.

희생자 선택의 원칙 (Principles of Victim Selection)​

프로세스 종료와 자원 선점 방식 모두 교착 상태를 깨기 위해 특정 프로세스를 '희생'시켜야 합니다. 이때 시스템 비용을 최소화하는 희생자를 선택하는 것이 중요하며, 일반적으로 다음과 같은 기준이 사용됩니다.

  • 프로세스 우선순위: 우선순위가 낮은 프로세스를 먼저 희생시킵니다.
  • 작업 진행 시간: 실행 시간이 짧았거나, 작업 진행률이 낮은 프로세스를 선택하여 복구 비용을 줄입니다.
  • 사용된 자원: 더 적은 자원을 사용한 프로세스, 또는 반대로 더 많은 자원을 점유하여 다른 프로세스들을 기다리게 만드는 프로세스를 선택할 수 있습니다.

5. 결론: 교착 상태 관리의 현실적 트레이드오프​

전략 종합 및 평가

교착 상태 예방, 회피, 검출 및 회복 전략은 각각 이상과 현실, 성능과 안정성 사이의 뚜렷한 트레이드오프 관계를 보여줍니다.
예방은 가장 이상적이지만 자원 효율성과 시스템 성능을 크게 희생시키며, 회피는 복잡한 제약 조건과 높은 오버헤드로 인해 실용성이 떨어집니다.
검출 및 회복은 가장 현실적이지만, 교착 상태가 발생한 후의 사후 처리 방식이라는 한계를 가집니다.

현대 운영체제의 선택​

이러한 이유로, 대부분의 범용 운영체제(예: Windows, UNIX)는 교착 상태 예방이나 회피를 위한 복잡한 메커니즘을 구현하지 않습니다. 대신, 교착 상태는 극히 드물게 발생한다고 가정하고 이 문제를 의도적으로 무시하는(ignore) 방법을 택합니다. 이는 교착 상태를 막기 위해 치러야 하는 성능 저하 비용이, 드물게 발생하는 교착 상태로 인한 피해보다 훨씬 크다고 판단하기 때문입니다. 실제로 범용 시스템 환경에서 웹 브라우저나 문서 편집기와 같은 일반적인 응용 프로그램들이 네 가지 필요조건, 특히 완벽한 원형 대기 사슬을 동시에 만족시키는 경우는 통계적으로 매우 드뭅니다. 이는 대규모 트랜잭션을 처리하여 교착 상태가 실질적인 문제로 다뤄지는 데이터베이스 시스템과는 대조적입니다. 따라서 범용 OS에서는 교착 상태 발생 시 사용자가 직접 응용 프로그램을 강제 종료하거나 시스템을 재부팅하는 방식에 의존하는 것이 더 현실적인 접근법입니다.

최종 요약​

결론적으로 교착 상태는 완벽한 단일 해결책이 없는, 시스템 설계의 근본적인 트레이드오프 문제입니다. 실시간 제어 시스템에서는 치명적인 오류를 막기 위해 예방이나 회피가 필수적일 수 있지만, 데이터베이스 시스템에서는 트랜잭션 롤백을 동반한 검출 및 회복이 더 실용적입니다. 반면, 대부분의 범용 운영체제는 성능과 유연성을 위해 문제를 무시하는 과감한 선택을 합니다. 이처럼 시스템의 목적과 환경에 맞는 최적의 균형점을 찾는 것이야말로 안정적이고 효율적인 시스템을 설계하는 핵심입니다.