2025-10-06 21:24

• 운영체제에서 교착 상태]란 두 개 이상의 프로세스가 서로가 가진 자원을 기다리며 무한정 대기하는 상태를 의미한다.

• 교착상태는 상호 배제, 점유와 대기, 비선점, 환형 대기라는 네 가지 조건이 모두 충족될 때 발생하며, 하나라도 제거하면 해결할 수 있다.

• 교착상태 해결 방법에는 예방, 회피, 탐지 및 회복 기법이 있으며, 각각 장단점을 고려하여 시스템에 적합한 방식을 선택해야 한다.

운영체제 교착상태 완벽 핸드북 당신의 시스템을 구원할 필독서

컴퓨터 과학, 특히 운영체제(OS)를 공부하다 보면 반드시 마주치는 난해한 개념이 있다. 바로 **교착상태(Deadlock)**다. 마치 좁은 외나무다리에서 두 사람이 마주 보고 옴짝달싹 못 하는 상황처럼, 컴퓨터 시스템 내부에서도 프로세스들이 서로 필요한 자원을 붙잡고 놓아주지 않아 전체 시스템이 멈춰버리는 현상이 발생할 수 있다.

이 핸드북은 교착상태라는 개념이 왜 등장했는지 그 근본적인 이유부터 시작하여, 교착상태가 발생하는 조건, 구조, 그리고 이를 해결하기 위한 다양한 기법까지 심도 있게 탐구한다. 단순한 이론 나열을 넘어, 실제 시스템이 어떻게 이 문제를 다루고 있는지, 개발자로서 무엇을 고려해야 하는지 실질적인 관점을 제공하는 것을 목표로 한다.

교착상태는 왜 우리를 괴롭히기 시작했나

초창기 컴퓨터는 한 번에 하나의 작업만 처리하는 단순한 구조였다. 하지만 컴퓨터 기술이 발전하면서, 한정된 자원(CPU, 메모리 등)을 여러 작업이 동시에 공유하며 효율성을 극대화하는 다중 프로그래밍(Multi-programming) 환경이 등장했다. 바로 이 ‘공유’라는 개념이 교착상태의 씨앗을 잉태했다.

여러 프로세스가 동시에 프린터, 파일, 데이터베이스 등 **공유 자원(Shared Resource)**에 접근하려고 경쟁하면서 문제가 발생하기 시작했다. 만약 A라는 프로세스가 프린터를 사용하고 있고, B라는 프로세스는 파일을 사용하고 있다고 가정해 보자. 이때 A가 파일을 추가로 요청하고, B는 프린터를 추가로 요청한다면 어떻게 될까?

A는 B가 파일을 놓아주기 전까지 프린터를 점유한 채 기다리고, B는 A가 프린터를 놓아주기 전까지 파일을 점유한 채 기다리게 된다. 결국 두 프로세스 모두 영원히 다음 단계로 진행하지 못하는 상태에 빠지는데, 이것이 바로 교착상태의 본질이다. 즉, 교착상태는 자원의 효율적인 공유와 분배라는 과제를 해결하는 과정에서 필연적으로 발생한 부작용인 셈이다. 이는 마치 도시가 발전하며 교통 체증이 필연적으로 발생하는 것과 같은 이치다.

교착상태의 구조 해부 네 가지 필요조건

교착상태가 발생하기 위해서는 마치 퍼즐 조각처럼 아래 네 가지 조건이 모두 충족되어야 한다. 역으로 말하면, 이 중 단 하나의 조건이라도 깨뜨리면 교착상태를 예방할 수 있다는 의미이기도 하다.

1. 상호 배제 (Mutual Exclusion)

• 정의: 한 번에 하나의 프로세스만이 자원을 사용할 수 있다.

• 비유: 화장실은 한 사람만 들어갈 수 있다. 다른 사람이 사용 중이라면 밖에서 기다려야 한다.

• 설명: 프린터나 파일처럼 본질적으로 동시에 여러 프로세스가 사용할 수 없는 자원들이 이에 해당한다. 만약 여러 프로세스가 동시에 한 자원에 접근하여 데이터를 수정한다면 데이터의 일관성이 깨질 수 있기 때문에 상호 배제는 필수적인 조건이다.

2. 점유와 대기 (Hold and Wait)

• 정의: 자원을 최소 하나 이상 보유한 프로세스가 다른 프로세스에 할당된 자원을 추가로 요청하며 기다린다.

• 비유: 식사를 위해 포크를 손에 든 사람이 나이프를 들고 있는 다른 사람이 내려놓기를 기다리는 상황이다. 자신은 포크를 내려놓을 생각이 없다.

• 설명: 프로세스는 자신이 이미 확보한 자원을 포기하지 않은 채, 다른 자원을 무작정 기다리면서 교착상태의 가능성을 높인다.

3. 비선점 (No Preemption)

• 정의: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다. 자원은 오직 점유하고 있는 프로세스가 자발적으로 해제해야만 한다.

• 비유: 영화관에서 영화를 보고 있는 사람을 중간에 강제로 끌어낼 수 없는 것과 같다. 영화가 끝나야만 자리에서 일어난다.

• 설명: 프로세스의 작업 안정성을 보장하기 위한 조건이다. 만약 시스템이 마음대로 자원을 빼앗아 간다면, 진행 중이던 작업의 상태를 저장하고 복원하는 복잡한 과정이 필요하며 데이터 무결성을 해칠 위험이 있다.

4. 환형 대기 (Circular Wait)

• 정의: 각 프로세스가 다음 프로세스가 요구하는 자원을 가지고 있고, 자신은 그 다음 프로세스가 가진 자원을 요구하는 원형의 대기 사슬이 존재한다. (P0 → P1 → P2 → … → Pn → P0)

• 비유: 여러 사람이 원형으로 둘러앉아 각각 자신의 오른쪽 사람이 가진 물건을 달라고 요청하는 상황이다. 아무도 자신의 물건을 내려놓지 않으면 이 사슬은 절대 끊어지지 않는다.

• 설명: 교착상태의 직접적인 원인이 되는 구조다. 각 프로세스가 서로의 꼬리를 무는 형태로 자원을 기다리고 있기 때문에 누구 하나 먼저 양보하지 않으면 영원히 대기 상태에 머무르게 된다.

조건 (Condition)	핵심 개념 (Core Concept)	실생활 비유 (Analogy)
상호 배제 (Mutual Exclusion)	자원은 한 번에 하나만 사용 가능	1인용 화장실
점유와 대기 (Hold and Wait)	내 것은 쥔 채 남의 것을 요구	포크를 들고 나이프를 기다림
비선점 (No Preemption)	남의 것을 강제로 뺏을 수 없음	영화 관람 중인 사람
환형 대기 (Circular Wait)	원형으로 서로를 기다림	꼬리잡기 게임

교착상태 해결을 위한 전략적 접근법

교착상태 문제를 해결하는 방법은 크게 네 가지로 나뉜다. 각각의 방법은 효과와 시스템 부하 측면에서 장단점을 가지므로, 시스템의 특성과 요구사항에 따라 적절한 전략을 선택해야 한다.

1. 예방 (Prevention)

교착상태가 애초에 발생하지 않도록 네 가지 필요조건 중 하나 이상을 깨뜨리는 가장 강력하고 근본적인 방법이다.

• 상호 배제 부정: 공유 가능한 자원(Read-only 파일 등)을 늘리는 방식이지만, 대부분의 자원은 본질적으로 상호 배제가 필요하므로 적용이 제한적이다.

• 점유와 대기 부정: 프로세스가 실행되기 전에 필요한 모든 자원을 한꺼번에 할당받거나, 자원을 전혀 가지지 않았을 때만 요청할 수 있도록 제한한다. 이는 자원 낭비(미리 할당받고 사용하지 않는 자원)를 초래하고, 특정 자원을 언제 사용할지 예측하기 어렵다는 단점이 있다.

• 비선점 부정: 다른 프로세스가 요청한 자원을 가진 프로세스가 대기 상태에 들어가면, 가지고 있던 자원을 모두 반납하게 하고 필요할 때 다시 요청하게 하는 방식이다. 이는 문맥 교환 비용이 크고, 동일한 자원을 계속해서 빼앗기고 할당받는 **기아 상태(Starvation)**를 유발할 수 있다.

• 환형 대기 부정: 모든 자원 유형에 고유한 번호를 부여하고, 각 프로세스는 현재 보유한 자원의 번호보다 높은 번호의 자원만 요청할 수 있도록 강제한다. 이는 환형 대기 사슬을 원천적으로 차단하지만, 자원 요청 순서를 강제하여 유연성을 떨어뜨리고 비효율을 낳을 수 있다.

2. 회피 (Avoidance)

프로세스에 자원을 할당할 때, 해당 할당으로 인해 시스템이 **불안전 상태(Unsafe State)**로 들어설 가능성이 있는지 미리 검사하여 교착상태를 피해 가는 방식이다. 이는 예방보다 덜 엄격한 접근법이다.

• 자원 할당 그래프 알고리즘 (Resource-Allocation Graph Algorithm): 자원 유형별 인스턴스가 하나일 때 사용한다. 자원 요청 시, 해당 요청을 허용했을 때 그래프에 사이클(환형 대기)이 생기는지 검사하여 사이클이 생긴다면 요청을 대기시킨다.

• 은행원 알고리즘 (Banker’s Algorithm): 자원 유형별 인스턴스가 여러 개일 때 사용한다. 각 프로세스는 시작 전에 자신이 최대로 필요로 할 자원의 양을 미리 선언한다. 시스템은 자원 할당 요청이 있을 때마다, 이 요청을 들어주어도 시스템이 **안전 상태(Safe State)**로 유지될 수 있는지(즉, 모든 프로세스를 정상적으로 종료시킬 수 있는 순서가 존재하는지)를 계산한다. 안전 순서가 존재할 경우에만 자원을 할당한다. 은행이 모든 고객의 최대 대출 요구액을 파악하고, 현재 가용 자금으로 모든 고객을 파산시키지 않고 대출을 처리할 수 있는지 계산하는 것과 유사하다.

은행원 알고리즘은 교착상태를 회피하는 매우 정교한 방법이지만, 프로세스가 필요로 할 최대 자원량을 미리 알아야 한다는 제약과 매번 안전성을 검사하는 데 따르는 오버헤드가 크다는 단점이 있다.

3. 탐지 및 회복 (Detection & Recovery)

교착상태 발생을 막거나 피하지 않고, 일단 발생하도록 내버려 둔 뒤 시스템이 교착상태에 빠졌는지 주기적으로 검사하여 탐지하고, 탐지되었다면 이를 회복시키는 방법이다.

• 탐지 (Detection):

  • 대기 그래프 (Wait-for Graph): 자원 할당 그래프를 단순화한 형태로, 프로세스들 간의 대기 관계만을 나타낸다. 이 그래프에서 사이클이 발견되면 교착상태가 발생했다고 판단한다.

  • 은행원 알고리즘 변형: 현재 자원 할당 상태를 기반으로, 모든 프로세스가 작업을 마칠 수 있는지 안전성 검사를 수행한다. 모든 프로세스를 만족시킬 수 없다면 교착상태로 판단한다.

• 회복 (Recovery):

  • 프로세스 종료: 가장 간단하고 확실한 방법이다. 교착상태에 빠진 프로세스를 하나 또는 전부 강제 종료시킨다. 어떤 프로세스를 희생시킬지(우선순위, 실행 시간, 자원 사용량 등을 고려) 결정하는 기준이 필요하다.

  • 자원 선점: 교착상태에 빠진 프로세스로부터 자원을 강제로 빼앗아 다른 프로세스에게 할당한다. 이때 어떤 프로세스의 자원을 얼마나 빼앗을지, 그리고 자원을 빼앗긴 프로세스를 어떻게 처리할지(보통 해당 지점부터 재시작) 결정하는 것이 중요하다. 이 과정에서 기아 상태가 발생하지 않도록 주의해야 한다.

4. 무시 (Ignorance)

놀랍게도 가장 널리 사용되는 방법이다. 교착상태는 이론적으로 매우 중요하지만 실제 시스템에서는 매우 드물게 발생한다. 따라서 교착상태를 예방, 회피, 탐지하는 데 드는 비용과 성능 저하가 교착상태 발생으로 인한 손실보다 크다고 판단될 때 이 방법을 사용한다.

대부분의 범용 운영체제(Windows, UNIX, Linux 등)는 이 방식을 채택한다. 시스템이 비정상적으로 느려지거나 멈추면 사용자가 직접 문제가 되는 프로세스를 종료하거나 시스템을 재부팅하는 방식으로 해결하도록 맡기는 것이다. 이는 마치 “타조가 위험할 때 모래에 머리를 박는 것과 같다”고 해서 **타조 알고리즘(Ostrich Algorithm)**이라고도 불린다. 데이터베이스 시스템처럼 데이터의 일관성과 무결성이 매우 중요한 특수 목적 시스템에서는 교착상태를 정교하게 처리하지만, 일반적인 PC 환경에서는 성능을 위해 교착상태를 무시하는 것이 더 합리적인 선택일 수 있다.

심화 내용 알아두면 쓸모 있는 교착상태 이야기

기아 상태 (Starvation) vs 교착상태 (Deadlock)

두 개념은 혼동하기 쉽지만 분명한 차이가 있다.

• 교착상태: 여러 프로세스가 서로가 가진 자원을 기다리며 영원히 대기하는 상태. 사이클이 존재한다.

• 기아 상태: 특정 프로세스가 자원을 할당받을 수 있는 기회를 계속해서 다른 프로세스에게 빼앗겨 오랫동안 기다리는 상태. 교착상태와 달리, 시스템 전체는 정상적으로 동작하고 있을 수 있으며, 이론적으로는 언젠가 자원을 할당받을 가능성이 있다. 우선순위 기반의 스케줄링에서 낮은 우선순위의 프로세스가 계속해서 높은 우선순위의 프로세스에 밀리는 경우가 대표적인 예다.

식사하는 철학자 문제 (Dining Philosophers Problem)

교착상태와 관련된 가장 유명한 고전 문제다. 다섯 명의 철학자가 원형 식탁에 앉아 있고, 각 철학자의 양옆에는 포크가 하나씩 놓여 있다. 철학자들은 생각하거나 식사하는 두 가지 상태만 가진다. 식사를 하려면 반드시 자신의 왼쪽과 오른쪽 포크를 모두 집어야 한다.

만약 모든 철학자가 동시에 자신의 왼쪽 포크를 집는다면 어떻게 될까? 모든 철학자는 오른쪽 포크를 집기 위해 자신의 오른쪽 철학자가 포크를 내려놓기를 영원히 기다리게 된다. 이는 교착상태의 네 가지 조건(상호 배제, 점유와 대기, 비선점, 환형 대기)이 모두 충족되는 전형적인 사례다.

이 문제를 해결하기 위해 다양한 해법이 제시되었다.

• 최대 네 명의 철학자만 동시에 식사를 시도하도록 허용한다.

• 포크를 두 개 모두 집을 수 있을 때만 포크를 집도록 허용한다.

• 홀수 번호의 철학자는 왼쪽 포크부터, 짝수 번호의 철학자는 오른쪽 포크부터 집도록 순서를 다르게 한다. (환형 대기 조건 파괴)

이 문제는 다중 스레드 환경에서 공유 자원 접근을 제어하는 복잡성을 명확하게 보여주는 훌륭한 예시다.

결론 시스템 설계의 영원한 딜레마

교착상태는 다중 프로그래밍 환경에서 효율성과 안정성 사이의 균형을 맞추는 것이 얼마나 어려운지를 보여주는 대표적인 사례다. 교착상태를 완벽하게 예방하거나 회피하려다 보면 시스템의 성능이 저하되고 자원 활용률이 떨어지는 대가를 치러야 한다. 반대로 이를 무시하면 드물게나마 시스템 전체가 멈추는 치명적인 위험을 감수해야 한다.

따라서 어떤 하나의 방법이 절대적으로 옳다고 말할 수는 없다. 시스템의 목적과 환경(예: 실시간 시스템, 데이터베이스, 범용 OS)에 따라 최적의 전략은 달라진다. 개발자와 시스템 설계자는 교착상태의 근본적인 원리를 깊이 이해하고, 각 해결책의 장단점을 명확히 파악하여 주어진 상황에 가장 적합한 트레이드오프를 찾아내는 지혜를 발휘해야 할 것이다. 이 핸드북이 그 여정에 든든한 길잡이가 되기를 바란다.