시스매

교착상태 핸드북 OS의 영원한 숙제 Deadlock 완벽 분석

28 min read

2025-09-22 23:24

교착상태 핸드북 OS의 영원한 숙제 Deadlock 완벽 분석

  • 프로세스가 필요한 자원을 기다리며 영원히 멈추는 현상인 교착 상태]는 다중 프로그래밍 시스템의 근본적인 문제다.

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

  • 교착상태를 해결하기 위해 예방, 회피, 탐지 및 회복, 무시 등 다양한 전략이 사용되며, 각 전략은 시스템의 특성과 요구사항에 따라 장단점을 가진다.

컴퓨터 과학의 발전은 동시에 여러 작업을 처리하는 ‘병렬성’을 향한 여정이었다. 중앙처리장치(CPU)의 효율을 극대화하기 위해 운영체제는 여러 프로세스를 동시에 실행하는 다중 프로그래밍 환경을 도입했다. 하지만 이 혁신적인 개념은 예상치 못한 그림자를 드리웠다. 바로 ‘교착상태(Deadlock)‘라는 문제다. 이 핸드북은 교착상태가 왜 발생하는지부터 시작해 그 구조를 분석하고, 이를 해결하기 위한 다양한 방법론과 심화 개념까지 포괄적으로 다룬다. 마치 교통 정체처럼, 여러 프로세스가 서로가 가진 자원(resource)을 무한정 기다리며 시스템 전체를 마비시키는 이 현상은 현대 운영체제의 가장 근본적이고 흥미로운 숙제 중 하나다.

1. 교착상태의 탄생 배경 필연적인 동시성의 산물

교착상태는 왜 컴퓨터 과학의 중요한 문제로 떠올랐을까? 그 답은 ‘자원의 공유’와 ‘동시성’이라는 현대 컴퓨팅의 핵심 개념에 있다.

1.1. 다중 프로그래밍과 자원 공유의 시작

초창기 컴퓨터는 한 번에 하나의 작업만 처리하는 단일 프로그래밍 방식이었다. 이는 CPU가 입출력(I/O) 작업을 기다리는 동안 아무 일도 하지 않고 낭비되는 비효율을 낳았다. 1960년대, 이를 해결하기 위해 여러 프로그램을 메모리에 동시에 올려놓고 CPU가 유휴 상태일 때 다른 프로그램으로 전환하여 실행하는 ‘다중 프로그래밍(Multiprogramming)’ 기술이 등장했다.

이로써 CPU 활용률은 극적으로 높아졌지만, 새로운 문제가 발생했다. 프린터, 파일, 메모리 공간과 같은 한정된 시스템 자원을 여러 프로세스가 동시에 사용하려고 경쟁하기 시작한 것이다. 만약 한 프로세스가 프린터를 사용하는 동안 다른 프로세스가 접근하지 못하도록 막지 않으면, 출력물은 뒤죽박죽 섞여버릴 것이다. 따라서 자원에 대한 ‘배타적 접근’ 권한, 즉 한 번에 하나의 프로세스만 자원을 사용할 수 있도록 보장하는 메커니즘이 필수적이었다.

1.2. 에츠허르 다익스트라와 문제의 공식화

이러한 동시성 환경에서 발생하는 복잡한 문제들을 처음으로 체계적으로 연구한 인물 중 한 명이 바로 네덜란드의 컴퓨터 과학자 **에츠허르 다익스트라(Edsger W. Dijkstra)**다. 그는 세마포어(Semaphore)와 같은 동기화 도구를 고안하며 병렬 처리의 기틀을 마련했다.

다익스트라는 ‘식사하는 철학자들(Dining Philosophers Problem)‘이라는 유명한 비유를 통해 교착상태의 본질을 설명했다.

5명의 철학자가 원탁에 앉아 식사를 한다. 각 철학자의 양옆에는 포크가 하나씩 놓여 있고, 철학자가 스파게티를 먹기 위해서는 양쪽의 포크 두 개가 모두 필요하다. 만약 모든 철학자가 동시에 왼쪽 포크를 집는다면 어떻게 될까? 각자 하나의 포크를 든 채, 오른쪽 포크가 다른 철학자에 의해 놓이기를 영원히 기다리게 된다. 아무도 식사를 하지 못하고 결국 모두 굶어 죽게 되는 상황, 이것이 바로 교착상태다.

이 비유는 한정된 자원(포크)을 여러 프로세스(철학자)가 특정 순서에 따라 요청할 때 어떻게 시스템 전체가 멈출 수 있는지를 명확하게 보여준다. 교착상태는 특정 프로세스의 버그가 아니라, 여러 프로세스가 자원을 공유하는 시스템의 구조적 문제점에서 비롯되는 필연적인 결과물이었던 것이다. 1971년, E. G. 코프먼 주니어(E. G. Coffman, Jr.)는 논문을 통해 교착상태가 발생하기 위한 네 가지 필요조건을 명확히 정의하며 이 문제에 대한 학문적 논의를 본격화했다.

2. 교착상태의 구조 네 가지 필수 조건

교착상태가 발생하기 위해서는 아래의 네 가지 조건이 모두 동시에 충족되어야 한다. 하나라도 깨지면 교착상태는 발생하지 않는다. 이 네 가지 조건은 교착상태를 이해하고 해결하는 열쇠다.

2.1. 상호 배제 (Mutual Exclusion)

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

  • 설명: 프린터와 같은 자원은 본질적으로 공유가 불가능하다. 만약 여러 프로세스가 동시에 프린터에 데이터를 보낸다면 결과물은 의미 없는 종이 낭비일 뿐이다. 이처럼 자원의 무결성을 보호하기 위해, 운영체제는 특정 자원을 사용하는 프로세스가 작업을 마칠 때까지 다른 프로세스의 접근을 막는다. 이것이 상호 배제 조건이다.

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

  • 정의: 프로세스가 최소한 하나의 자원을 점유한 상태에서, 다른 프로세스에 할당된 자원을 추가로 기다리고 있다.

  • 설명: ‘식사하는 철학자’ 비유에서 철학자가 왼쪽 포크를 손에 쥔(점유) 상태로, 오른쪽 포크를 기다리는(대기) 상황과 같다. 프로세스가 이미 할당받은 자원을 놓지 않은 채로 다른 자원을 계속해서 요구할 때 이 조건이 성립된다.

2.3. 비선점 (No Preemption)

  • 정의: 다른 프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없다.

  • 설명: 어떤 프로세스가 파일을 사용하고 있는데, 다른 프로세스가 필요하다고 해서 운영체제가 그 파일의 제어권을 강제로 빼앗아 올 수 없다는 의미다. 자원은 할당받은 프로세스가 자발적으로 ‘놓아줄(release)’ 때만 반납된다. 만약 자원을 강제로 빼앗을 수 있다면(선점이 가능하다면), 한 프로세스가 무한정 기다리는 일은 없을 것이다.

2.4. 환형 대기 (Circular Wait)

  • 정의: 대기하고 있는 프로세스들이 원형으로 구성되어, 각 프로세스가 다음 프로세스가 점유한 자원을 기다린다.

  • 설명: 교착상태의 핵심 조건이다. 프로세스 P0는 P1이 가진 자원을 기다리고, P1은 P2가 가진 자원을, …, 그리고 마지막 프로세스 Pn은 P0가 가진 자원을 기다리는 꼬리물기 형태의 대기 사슬이 만들어지는 것이다. 이 원형 고리가 형성되면 어느 누구도 자신의 자원을 놓지 못하고, 다른 프로세스가 자원을 놓기만을 영원히 기다리게 된다.

이 네 가지 조건의 관계를 시각적으로 표현하는 데 유용한 도구가 바로 **자원 할당 그래프(Resource-Allocation Graph)**다.

구성 요소기호의미
프로세스원 (○)시스템 내의 실행 중인 프로세스
자원 유형사각형 (□)프린터, CPU, 메모리 등 자원의 종류
자원 인스턴스사각형 내의 점 (•)해당 자원의 개수 (예: 프린터 2대)
요청 간선P → R프로세스 P가 자원 R을 요청함 (화살표가 자원으로 향함)
할당 간선R → P자원 R이 프로세스 P에 할당됨 (화살표가 프로세스로 향함)

만약 이 그래프에 **사이클(Cycle)**이 존재한다면 교착상태가 발생할 가능성이 있다.

  • 자원 인스턴스가 1개인 경우: 사이클이 존재하면 반드시 교착상태다.

  • 자원 인스턴스가 여러 개인 경우: 사이클이 존재하더라도 다른 인스턴스를 통해 대기 상태가 풀릴 수 있으므로, 교착상태가 아닐 수도 있다.

그림: 자원 할당 그래프. P1 → R1 → P2 → R2 → P1의 사이클이 형성되어 교착상태를 나타낸다.

3. 교착상태 사용법 문제 해결을 위한 4가지 접근법

교착상태라는 문제를 다루는 방법은 크게 네 가지로 나뉜다. 이는 문제에 대한 태도에 따라 ‘예방’, ‘회피’, ‘탐지 및 회복’, ‘무시’로 구분할 수 있다.

3.1. 교착상태 예방 (Deadlock Prevention)

가장 보수적이고 확실한 방법이다. 교착상태의 네 가지 필요조건 중 어느 하나라도 원천적으로 발생하지 않도록 시스템을 설계하는 방식이다.

  • 상호 배제 조건의 부정: 공유가 불가능한 자원은 상호 배제를 없애기 어렵다. 예를 들어, 여러 프로세스가 동시에 프린터에 접근하게 허용할 수는 없다. 하지만 읽기 전용 파일처럼 공유 가능한 자원의 경우, 상호 배제를 적용하지 않음으로써 이 조건을 완화할 수 있다. 현실적으로는 적용이 제한적이다.

  • 점유와 대기 조건의 부정: 두 가지 전략이 있다.

    1. 프로세스가 실행에 필요한 모든 자원을 한꺼번에 요청하고 할당받도록 한다.

    2. 프로세스가 자원을 전혀 가지고 있지 않을 때만 자원을 요청하도록 한다.

    • 단점: 자원 활용률이 낮아진다. 당장 필요하지 않은 자원까지 미리 선점해야 하므로 다른 프로세스는 그 자원을 사용하지 못하고 기다려야 한다(기아 상태 발생 가능).

  • 비선점 조건의 부정: 다른 자원을 기다리는 프로세스가 있다면, 그 프로세스가 현재 점유하고 있는 자원을 강제로 빼앗아(선점하여) 다른 프로세스에게 할당하는 방식이다.

    • 단점: 상태를 저장하고 복원하는 데 드는 비용(문맥 교환 비용)이 크다. 특정 자원의 경우(예: 프린터 출력 중인 작업) 중간에 빼앗으면 데이터가 손상될 수 있어 일관성을 유지하기 어렵다.

  • 환형 대기 조건의 부정: 모든 자원 유형에 고유한 번호를 부여하고, 각 프로세스가 번호 순서대로만 자원을 요청하도록 강제하는 방법이다. 예를 들어, 1번 자원을 가진 프로세스는 3번 자원을 요청할 수 있지만, 3번 자원을 가진 프로세스는 1번 자원을 요청할 수 없다. 이렇게 하면 자원 요청 방향이 한쪽으로만 흘러 원형 대기열이 형성될 수 없다.

    • 장점: 앞의 세 방법에 비해 현실적이고 효율적인 예방책이다.

3.2. 교착상태 회피 (Deadlock Avoidance)

예방보다 덜 제한적인 방법이다. 시스템이 자원 요청에 대한 정보를 미리 파악하여, 교착상태를 유발할 ‘불안전 상태(unsafe state)‘로 진입하지 않도록 자원 할당을 조절하는 방식이다. 즉, 자원 요청이 들어왔을 때, 이 요청을 수락해도 시스템이 여전히 ‘안전 상태(safe state)‘를 유지할 수 있는지를 검사한다.

  • 안전 상태 (Safe State): 시스템 내의 모든 프로세스가 정상적으로 종료될 수 있는 실행 순서(안전 순서, Safe Sequence)가 존재하는 상태.

이 방법의 가장 대표적인 알고리즘이 바로 **은행원 알고리즘(Banker’s Algorithm)**이다.

은행원 알고리즘 (Banker’s Algorithm)

다익스트라가 고안한 이 알고리즘은 은행이 모든 고객의 최대 대출 요구액을 감당할 수 있는 한도 내에서만 대출을 승인하는 방식에서 유래했다.

  1. 전제 조건: 각 프로세스는 실행 전에 필요한 자원의 최대 개수를 미리 선언해야 한다.

  2. 동작 원리:

    • 프로세스가 자원을 요청하면, 시스템은 일단 그 자원을 할당해준다고 가정한다.

    • 가정한 상태에서 시스템이 여전히 ‘안전 상태’인지 검사한다.

    • 안전 상태라면 요청을 수락하고 자원을 실제로 할당한다.

    • 불안전 상태로 이어진다면, 요청을 거부하고 프로세스를 대기시킨다.

  • 은행원 알고리즘의 데이터 구조

    • Available: 각 자원 유형별로 현재 사용 가능한 인스턴스 수.

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

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

    • Need: 각 프로세스가 앞으로 더 필요로 하는 자원의 수 (Need = Max - Allocation).

  • 안전성 검사 알고리즘 (Safety Algorithm)

    1. 현재 Available 자원으로 작업을 완료할 수 있는 프로세스(Need ⇐ Available)를 찾는다.

    2. 그런 프로세스가 없다면, 시스템은 불안전 상태다.

    3. 찾았다면, 해당 프로세스가 작업을 마치고 모든 자원을 반납한다고 가정한다 (Available += Allocation).

    4. 해당 프로세스를 완료 목록에 추가하고, 1번부터 다시 반복하여 모든 프로세스가 완료될 수 있는지 확인한다.

    모든 프로세스가 완료 목록에 포함될 수 있다면 시스템은 안전 상태다.

  • 장점: 예방보다 자원 활용률이 높다.

  • 단점: 프로세스가 필요한 최대 자원 수를 미리 알아야 한다는 비현실적인 가정이 필요하며, 매번 자원 할당 시 알고리즘을 실행해야 하므로 오버헤드가 크다.

3.3. 교착상태 탐지 및 회복 (Deadlock Detection & Recovery)

교착상태 발생을 막지 않고, 일단 발생하도록 내버려 둔 뒤, 시스템이 교착상태에 빠졌는지를 주기적으로 검사(탐지)하고, 발견되면 이를 해결(회복)하는 방식이다.

  • 탐지 (Detection)

    • 대기 그래프(Wait-for Graph): 자원 할당 그래프를 단순화한 형태로, 노드가 프로세스만으로 구성된다. 프로세스 Pi가 Pj를 기다리고 있다면 Pi → Pj 간선을 그린다. 이 그래프에서 사이클이 발견되면 교착상태가 발생한 것이다.

    • 은행원 알고리즘과 유사한 탐지 알고리즘을 주기적으로 실행하여 교착상태 여부를 판별한다.

  • 회복 (Recovery)

    • 프로세스 종료: 교착상태에 빠진 프로세스를 하나 또는 여러 개 강제 종료하여 사이클을 끊는다.

      • 고려사항: 어떤 프로세스를 종료할 것인가? (우선순위가 낮은 프로세스, 실행 시간이 짧은 프로세스, 자원을 많이 사용하는 프로세스 등)

    • 자원 선점: 교착상태에 빠진 프로세스로부터 자원을 빼앗아 다른 프로세스에게 할당한다.

      • 고려사항: 어떤 자원을 선점할 것인가? 어떤 프로세스를 희생시킬 것인가? 선점 후 해당 프로세스를 어디까지 되돌릴 것인가(Rollback)? 희생된 프로세스가 계속해서 선택되지 않도록 하는 방안(기아 상태 방지)은 무엇인가?

3.4. 교착상태 무시 (Deadlock Ignorance)

가장 흔하게 사용되는 방법이다. 교착상태가 매우 드물게 발생한다고 가정하고, 이를 처리하는 데 드는 비용이 교착상태로 인한 손실보다 더 크다고 판단될 때 사용된다. 교착상태가 발생하면 시스템이 비정상적으로 느려지거나 멈추게 되는데, 이때 사용자가 시스템을 재부팅하는 방식으로 해결한다.

유닉스(Unix), 리눅스(Linux), 윈도우(Windows) 등 대부분의 범용 운영체제는 이 방식을 채택하고 있다. 이를 ‘타조 알고리즘(Ostrich Algorithm)‘이라고 부르기도 한다. 타조가 위험이 닥치면 머리를 모래에 파묻고 아무것도 보지 않으려는 행동에 빗댄 것이다.

4. 심화 내용 분산 시스템과 그 너머

교착상태는 단일 시스템을 넘어 여러 컴퓨터가 네트워크로 연결된 분산 시스템(Distributed System)에서 더욱 복잡한 양상을 띤다.

4.1. 분산 교착상태 (Distributed Deadlock)

분산 시스템에서는 여러 사이트(컴퓨터)에 자원과 프로세스가 흩어져 있다. 따라서 하나의 사이트에서는 교착상태가 아닌 것처럼 보여도, 전체 시스템 관점에서는 환형 대기가 발생할 수 있다. 예를 들어, 사이트 1의 P1이 사이트 2의 P2를 기다리고, 사이트 2의 P2는 사이트 1의 P1을 기다리는 상황이다.

이를 해결하기 위한 알고리즘은 중앙 집중형, 계층형, 분산형 등으로 나뉜다.

  • 중앙 집중형: 하나의 제어 사이트가 모든 자원 할당 정보를 수집하여 전역 대기 그래프(Global Wait-for Graph)를 만들고 사이클을 탐지한다.

  • 분산형: 각 사이트가 로컬 정보를 교환하며 교착상태를 탐지한다. 대표적으로 **경로 푸싱(Path-pushing)**이나 간선 추적(Edge-chasing) 알고리즘이 있다.

4.2. 기아 상태와 라이브락

  • 기아 상태 (Starvation): 교착상태와 혼동하기 쉬운 개념으로, 특정 프로세스가 자원을 할당받지 못하고 계속해서 대기하는 상태다. 교착상태는 여러 프로세스가 ‘함께’ 멈추는 것이라면, 기아 상태는 특정 프로세스 ‘혼자’ 자원을 받지 못하는 것이다. 주로 우선순위 기반 스케줄링에서 낮은 순위의 프로세스가 계속해서 밀릴 때 발생한다.

  • 라이브락 (Livelock): 교착상태와 유사하지만, 프로세스들이 멈춰 있는 것이 아니라 계속 상태를 바꾸며 서로를 방해하는 상황이다. 좁은 복도에서 두 사람이 서로 길을 비켜주려고 좌우로 계속 움직이지만 결국 아무도 지나가지 못하는 상황과 같다. 프로세스들은 활발하게 동작하지만 실질적인 작업 진행은 이루어지지 않는다.

결론 교착상태와의 공존

교착상태는 다중 프로그래밍 환경이 탄생하면서부터 함께한 운영체제의 오래된 숙제다. 이를 해결하기 위한 예방, 회피, 탐지 및 회복 전략은 각각 이상과 현실, 성능과 안정성 사이의 트레이드오프를 담고 있다.

  • 예방은 너무 엄격해서 자원 효율성을 떨어뜨리고,

  • 회피는 비현실적인 가정을 요구하며 오버헤드가 크다.

  • 탐지 및 회복은 복잡하고 비용이 많이 든다.

이 때문에 대부분의 현대 운영체제는 교착상태를 ‘무시’하는 실용적인 노선을 택했다. 하드웨어의 발전으로 시스템이 멈추는 빈도가 줄었고, 데이터베이스 관리 시스템(DBMS)과 같이 데이터 무결성이 극도로 중요한 특정 응용 프로그램 수준에서 교착상태를 탐지하고 처리하는 것으로 책임을 넘겼다.

결국 교착상태는 완전히 제거해야 할 ‘악’이라기보다는, 동시성을 추구하는 과정에서 관리하고 공존해야 할 ‘현상’에 가깝다. 이 핸드북을 통해 교착상태의 근본 원인부터 정교한 해결책까지 이해했다면, 복잡하게 얽힌 현대 컴퓨터 시스템의 내부 동작을 한층 더 깊이 있게 파악하게 된 것이다.

그래프 뷰