IT › 컴퓨터 시스템 › 운영체제 › 프로세스 관리

교착상태Deadlock

둘 이상의 프로세스나 스레드가 서로 상대가 쥔 자원을 기다리며 어느 쪽도 진행하지 못하는 상태이다. 상호 배제 · 점유 대기 · 비선점 · 순환 대기 네 조건이 모두 성립할 때 생긴다.

1요약

  1. 교착상태는 운영체제의 자원 관리 · 스레드 라이브러리의 뮤텍스 · DBMS 잠금 관리자에서 생기는 무한 대기이며, Coffman 외(1971)가 정리한 네 조건이 모두 성립할 때만 생기므로 그 위에서 예방 · 회피 · 탐지 · 회복의 네 대응이 나뉜다.
  2. 한 번 생기면 CPU 가 놀고 있어도 요청이 영원히 멈춘다 — Dijkstra 는 저장 장치 100페이지를 두 프로세스가 40 · 20페이지씩 쥔 상태에서 한 페이지씩 더 주면, 둘 다 39페이지를 더 기다리는데 남은 것은 38페이지라 누구도 끝나지 않는 「죽음의 포옹」을 보였다(EWD123 6절).
  3. 「멈췄다」는 대기 사슬이 닫혔는가로 가른다 — CPU 0% 로 서로 쥔 자원을 기다리는 원이 있으면 교착상태, CPU 를 쓰며 상태만 바뀌면 라이브락, 원은 없고 한쪽만 계속 밀리면 기아다.

2등장 배경

1960년대 다중 프로그래밍 시스템에서는 작업 여럿이 테이프 장치 · 저장 장치 · 파일을 나눠 썼다. 두 작업이 각자 하나씩 쥔 채 상대의 것을 요청하면 어느 쪽도 끝나지 않았고, 운영자가 한 작업을 강제로 끝낼 때까지 자원이 묶였다.

Dijkstra 는 1965년 EWD123 에서 이 현상을 deadly embrace 로 부르고, 각 프로세스가 최대 요구를 미리 밝히면 «모두 끝낼 순서가 남는 경우에만» 빌려주는 은행원 알고리즘을 냈다(EWD123 6.1절). Havender 는 1968년 IBM OS/360 에서 자원에 순서를 매겨 그 순서로만 요청하게 하는 예방 규칙을 보고했고(Havender 1968), Coffman · Elphick · Shoshani 는 1971년 네 조건과 탐지 알고리즘을 정리했다(Coffman 외 1971). Holt 는 1972년 프로세스와 자원을 노드로 둔 자원 할당 그래프로 판정 규칙을 형식화했다(Holt 1972).

지금 범용 운영체제와 응용은 최대 요구를 미리 알기 어려워 회피보다 예방(잠금 순서 규칙)과 탐지 도구를 쓴다. 리눅스 커널은 lockdep 으로 잠금 순서 역전을 찾고(lockdep 설계 문서), JVM 은 ThreadMXBean.findDeadlockedThreads() 로 순환 대기 스레드를 돌려준다(Java SE 21 API). DBMS 의 잠금 교착은 대기 그래프 탐지 뒤 트랜잭션 하나를 철회해 푸는 방식으로, 상세는 동시성 제어가 맡는다.

3쉽게 이해하기 — 도장과 서류철을 하나씩 쥔 두 직원

결재실에는 도장 하나와 서류철 하나가 있고, 결재 한 건을 끝내려면 둘 다 있어야 한다. 직원 김은 도장을 먼저 집고 서류철을 기다리고, 직원 박은 서류철을 먼저 집고 도장을 기다린다. 둘 다 «다 쓰면 줄게»라며 손에 쥔 것을 놓지 않아 결재실이 멈춘다. 순찰하던 총무 팀장이 서로를 기다리는 원을 발견하고 박에게 서류철을 내려놓고 처음부터 다시 하게 한 뒤, 「도장부터 집는다」는 규칙을 벽에 붙인다.

손에 쥠 = 할당 기다림 = 요청 도장 잠금 A 한 번에 한 사람만 서류철 잠금 B 한 번에 한 사람만 직원 김 스레드 T1 도장을 쥐고 서류철 대기 직원 박 스레드 T2 서류철을 쥐고 도장 대기 1 2 3 4 원이 닫힘 아무도 움직이지 못함 총무 팀장 탐지 · 회복 5 순찰하다 서로 기다리는 원을 발견 → 탐지 6 박이 서류철을 놓고 처음부터 다시 → 회복(희생자 선택)

그림 1 · 두 직원이 하나씩 쥐고 서로의 것을 기다리면 원이 닫혀 멈추고, 팀장이 원을 찾아 한 명을 물러나게 해야 풀린다.

도장 집기김이 도장을 쥠
서류철 집기박이 서류철을 쥠
서로 기다리기둘 다 놓지 않음
순찰팀장이 원을 발견
다시 하기박이 내려놓고 처음부터
규칙 붙이기도장부터 집기
비유 — 결재실의 네 습관 실제 — 교착상태의 네 조건 도장은 한 사람만 쓴다 쥔 것을 놓지 않고 다음 것을 기다린다 남의 손에 있는 것은 빼앗지 않는다 김은 박을, 박은 김을 기다린다 상호 배제 자원을 한 번에 하나만 씀 점유 대기 쥔 채로 더 요청함 비선점 강제로 회수하지 못함 순환 대기 대기 사슬이 원을 이룸 넷이 모두 있어야 원이 닫힌다 — 하나만 깨도 교착상태는 생기지 않는다

그림 2 · 결재실의 네 습관이 모두 있어야 원이 닫히고, 하나만 깨도 멈추지 않는다 — 이것이 교착상태의 네 조건이다.

비유 속 역할실제 이름실제로 하는 일
직원 김 · 박프로세스 · 스레드자원을 요청하고 쥐고 놓는다
도장 · 서류철자원(뮤텍스 · 장치 · 페이지)한 번에 정해진 수만 쓸 수 있다
쥔 채 기다림점유 대기 · 요청 간선할당받은 것을 둔 채 다음 획득 함수에서 잠든다
서로 기다리는 원순환 대기 · 그래프 사이클대기 사슬이 처음 프로세스로 돌아온다
팀장의 순찰탐지 알고리즘대기 그래프에서 사이클을 찾는다
한 명이 내려놓고 다시회복 · 희생자 선택프로세스 종료나 트랜잭션 철회로 자원을 되찾는다
「도장부터」 규칙예방 · 잠금 순서모든 코드가 같은 순서로만 잠가 원을 못 만들게 한다
최대 필요량 장부회피 · 은행원 알고리즘빌려줘도 모두 끝낼 순서가 남을 때만 허락한다

⚠ 비유가 맞지 않는 곳: 직원은 말로 양보할 수 있지만 스레드는 잠금 획득 함수 안에서 잠들어 스스로 풀지 못하며, 실제 회복은 대개 한 명이 내려놓는 정도가 아니라 프로세스 전체를 끝내는 것이라 그동안 한 일을 잃는다.

4구조 — 자원 할당 그래프와 네 조건

자원 할당 그래프는 프로세스(원)와 자원(사각형 · 안의 점 = 인스턴스 수)을 노드로 두고, 요청 간선 P → R 과 할당 간선 R → P 를 긋는다(Holt 1972). 자원마다 인스턴스가 하나이면 사이클이 곧 교착상태이고, 여럿이면 사이클은 필요조건일 뿐이다.

가 · 인스턴스 하나씩 — 교착상태 나 · R2 인스턴스 둘 — 교착상태 아님 R1 R2 P1 P2 사이클 = 교착상태 R2 를 줄 프로세스가 사이클 안에만 있음 R1 R2 P1 P2 P3 사이클 있음 교착상태 아님 P3 가 끝나면 R2 하나가 P1 에게 프로세스 자원 · 점 = 인스턴스 할당 R → P 요청 P → R

그림 3 · 같은 사이클도 R2 의 인스턴스가 하나이면 교착상태이고, 둘이면 사이클 밖의 P3 가 끝나 하나를 돌려주므로 풀린다.

요소표기역할값 · 근거
프로세스 노드원자원을 요청 · 보유하는 주체스레드도 같은 규칙(Holt 1972)
자원 노드사각형 + 점자원 유형과 인스턴스 수뮤텍스 = 인스턴스 1 · 저장 장치 페이지 = 여럿
요청 간선P → R아직 받지 못한 요구받으면 할당 간선으로 바뀜
할당 간선R → P지금 쥐고 있는 인스턴스해제하면 지워짐
사이클닫힌 경로순환 대기의 그래프 모양인스턴스 1이면 필요충분 · 여럿이면 필요조건만
대기 그래프P → P자원 노드를 지운 그래프인스턴스 1일 때 탐지에 씀(Coffman 외 1971)

네 조건은 동시에 성립해야 하므로(Coffman 외 1971), 예방은 그중 하나를 설계로 없앤다.

조건뜻없애는 예방 방법대가
상호 배제한 번에 하나만 사용읽기 전용 공유 · 스풀링쓰기 자원에는 못 씀
점유 대기쥔 채 더 요청시작 때 한꺼번에 받기 · 못 받으면 모두 놓기오래 쥐어 이용률 하락
비선점강제로 회수 불가못 받으면 쥔 것을 내놓고 다시 시도(pthread_mutex_trylock)되돌릴 수 있는 자원만
순환 대기대기 사슬이 원자원에 번호를 매겨 오름차순으로만 요청(Havender 1968)순서 규칙을 모든 코드가 지켜야 함

🔑 사이클은 교착상태의 증거가 아니라 후보다 — 자원마다 인스턴스가 하나일 때만 사이클이 곧 교착상태다.

5동작 — 잠금 두 개의 역순 획득부터 순서 규칙까지

x86-64 리눅스의 glibc 스레드 프로그램 qstat(PID 5120)에서 큐 스레드 T1(TID 5121)과 보고 스레드 T2(TID 5122)가 뮤텍스 q_lock · st_lock 을 반대 순서로 잡는 사례다. PID · 잠금 이름은 설명용 가정 값이다.

  1. T1 이 항목을 넣으려고 pthread_mutex_lock(&q_lock) 을 성공한다 — 할당 간선 q_lock → T1.
  2. T2 가 통계를 모으려고 pthread_mutex_lock(&st_lock) 을 성공한다 — 할당 간선 st_lock → T2.
  3. T1 이 처리 건수를 더하려고 st_lock 을 요청하고 잠든다 — 요청 간선 T1 → st_lock.
  4. T2 가 큐 길이를 읽으려고 q_lock 을 요청하고 잠든다 — 사이클 T1 → st_lock → T2 → q_lock → T1 이 닫힌다. 뮤텍스는 인스턴스가 하나이므로 이것이 곧 교착상태다.
  5. top -H -p 5120 에서 두 스레드가 모두 S(잠듦) 상태 · %CPU 0.0 이고 처리 건수가 늘지 않는다(top(1)).
  6. gdb -p 5120 -batch -ex "thread apply all bt" 로 두 스레드가 모두 pthread_mutex_lock 안에서 멈춘 것과 호출부 enqueue() · report() 를 확인하고, 각자 쥔 잠금을 소스와 맞춰 사이클을 그린다(GDB Threads).
  7. 사용자 공간 뮤텍스는 다른 스레드가 빼앗을 수 없으므로(비선점) 프로세스를 재시작해 회복한다 — 큐에 있던 처리 전 항목은 잃는다.
  8. report() 를 「q_lock → st_lock」 순서로 고쳐 순환 대기를 없애고, 시험 빌드를 -fsanitize=thread 로 돌려 역순 잠금이 다시 들어오면 보고되게 한다(ThreadSanitizer detect_deadlocks 기본 true).
T1 · 5121 q_lock st_lock T2 · 5122 1 lock 성공 · 보유 2 lock 성공 · 보유 3 st_lock 요청 · 잠듦 4 q_lock 요청 · 잠듦 사이클 닫힘 — T1 → st_lock → T2 → q_lock → T1 · 둘 다 깨어날 수 없음 5 증상 · top -H -p 5120 → 두 스레드 S 상태 · %CPU 0.0 6 탐지 · gdb thread apply all bt → 둘 다 pthread_mutex_lock 안 · enqueue() · report() 7 회복 · 프로세스 재시작 → 처리 전 항목 손실 8 예방 · report() 를 q_lock → st_lock 순서로 수정 · -fsanitize=thread 시험

그림 4 · 각자 하나씩 잡은 뒤(①②) 상대 잠금을 요청하는 순간(③④) 사이클이 닫히고, 그 뒤는 탐지 · 회복 · 순서 규칙(⑤~⑧)으로만 빠져나온다.

회피는 요청이 올 때마다 «허락한 뒤에도 모든 프로세스를 끝낼 순서가 남는가»를 검사한다(EWD123 6.1절). 아래는 같은 종류 자원 10단위를 프로세스 셋이 나눠 쓰는 가정 값이다 — 남은 요구 = 최대 − 보유이고, 남은 요구가 가용 이하인 프로세스를 하나씩 끝냈다고 보고 그 보유분을 가용에 더한다.

지금 상태 · 자원 10단위(가정 값) 프로세스 보유 최대 남은 요구 P1 3 8 5 P2 2 5 3 P3 2 4 2 가용 3 10 − (3 + 2 + 2) 남은 요구 = 최대 − 보유 요청 가 · P3 이 1단위 더 허락했다고 치면 P3 보유 3 · 가용 2 P3 남은 1 ≤ 가용 2 → 끝나면 가용 5 P2 남은 3 ≤ 가용 5 → 끝나면 가용 7 P1 남은 5 ≤ 가용 7 → 끝나면 가용 10 끝낼 순서 P3 → P2 → P1 = 안전 · 허락 요청 나 · P1 이 2단위 더 허락했다고 치면 P1 보유 5 · 가용 1 P1 남은 3 > 가용 1 P2 남은 3 > 가용 1 P3 남은 2 > 가용 1 끝낼 순서 없음 = 불안전 · P1 대기 가용 자원 안전 검사 통과 거절 · 대기

그림 5 · 같은 가용 3 에서 P3 의 1단위 요청은 끝낼 순서가 남아 허락되고, P1 의 2단위 요청은 남은 가용 1 로 끝낼 프로세스가 없어 거절된다.

🔑 회피는 «지금 남는가»가 아니라 «허락한 뒤에도 모두 끝낼 순서가 남는가»로 판정한다 — 가용 3 에서 2단위는 남지만 거절된다.

6비교 — 예방 · 회피 · 탐지와 회복

기준예방회피(은행원 알고리즘)탐지 · 회복
개입 시점설계 · 코딩 때요청이 올 때마다멈춘 뒤 주기적으로
미리 알아야 할 것자원 순서 규칙프로세스마다 최대 요구없음
자원 이용률낮음(한꺼번에 받기 · 순서 강제)중간(불안전 요청 대기)높음(제한 없이 할당)
실행 비용거의 없음요청마다 안전 검사사이클 검사 + 희생자 작업 손실
교착상태 발생없음없음생긴 뒤 푼다
대표 구현커널 잠금 순서 · lockdep · trylock 후퇴자원 수 · 최대 요구가 고정된 시스템DBMS 잠금 관리자 · findDeadlockedThreads

분석잠금 몇 개를 코드가 직접 다루는 응용과 커널은 예방(잠금 순서)이 맞고, 트랜잭션처럼 무엇을 잠글지 실행 중에 정해지고 철회가 가능한 곳은 탐지 · 회복이 맞다. 근거는 표의 「미리 알아야 할 것」 · 「실행 비용」 행 — 회피는 최대 요구를 미리 알아야 해서(EWD123 6.1절) 범용 환경에서는 그 전제가 서지 않는다.

7실무 진단 — 멈춤 원인 가르기

분석먼저 CPU 사용 여부로 교착상태(잠듦)와 라이브락 · 무한 루프(실행 중)를 가르고, 잠든 스레드의 스택으로 대기 사슬을 그려 원이 닫혔는지 본다. 원이 없으면 교착상태가 아니라 입출력 · 외부 응답 대기다.

#증상의심 원인구분확인 명령판정 기준(근거)
1응답 없음 · CPU 0%사용자 공간 잠금 교착스레드gdb -p <pid> -batch -ex "thread apply all bt"둘 이상이 잠금 획득 함수에서 멈추고 서로 쥔 잠금을 기다리면 교착(GDB Threads)
2응답 없음 · CPU 100%라이브락 · 바쁜 대기스레드top -H -p <pid>스레드가 R 상태로 CPU 를 쓰면 교착상태 아님(top(1))
3Java 서비스 멈춤모니터 · 소유 가능 동기화기 순환JVMThreadMXBean.findDeadlockedThreads()null 이 아니면 교착 스레드 ID 배열 · 가상 스레드가 낀 사이클은 못 찾음(Java SE 21 API)
4커널 로그에 hung task 경고커널 잠금 교착 · 느린 저장 장치커널sysctl kernel.hung_task_timeout_secs · dmesgD 상태가 이 값(초)보다 오래 스케줄되지 않으면 경고 · 0 이면 검사 안 함(커널 sysctl 문서)
5개발 커널에서 잠금 순서 경고잠금 순서 역전커널grep "lock-classes" /proc/lockdep_stats한 번이라도 일어난 역순 사슬을 실제 멈춤 전에 알림 · 클래스 상한 8191(lockdep 설계 문서)
6시험에서만 가끔 멈춤드문 역순 잠금빌드-fsanitize=thread역순 잠금 보고 · 5 ~ 15배 느려져 운영이 아닌 시험에서 씀(Clang ThreadSanitizer)

같은 멈춤이 재현되지 않으면 1행의 스택을 두 번 이상 떠서 같은 함수에 머무는지 본다. 4행 경고는 교착 외에 저장 장치 지연에도 나므로, 스택에 잠금 함수가 있는지로 다시 가른다.

8시험 대비

출제 정보 정보관리(124회, 116회, 86회) · 컴퓨터시스템응용(138회, 137회, 132회, 71회)문제 원문 — 큐넷 자료실 「기출문제(기술사)」 www.q-net.or.kr

시험에서는 네 조건과 예방 · 회피 · 탐지 · 회복을 정리하는 정의 · 특징형, 은행원 알고리즘의 안전 검사를 수치로 따라가는 동작 · 절차 설명형이 나올 수 있다. 장애 사례(멈춘 서비스)를 주고 원인과 대책을 묻는 장애 · 보안 대응형이면 4 · 6 항목을 늘린다.

답안 목차
  1. 개요 — 정의 · 무한 대기 · 죽음의 포옹 예(100페이지 · 가용 38 < 요구 39)
  2. 발생 조건 — 네 조건 표(뜻 · 없애는 예방 방법 · 대가) · 하나만 깨도 생기지 않음(Coffman 외 1971)
  3. 자원 할당 그래프 — 그림 3 인스턴스 하나 ↔ 둘 비교 · 사이클 = 필요조건
  4. 대응 넷 — 예방 · 회피 · 탐지 · 회복 비교표(개입 시점 · 미리 알 것 · 이용률)
  5. 은행원 알고리즘 — 그림 5 안전 검사(가용 3 · 허락 1건 · 거절 1건 · 불안전 ≠ 교착상태)
  6. 실무 대책 — 그림 4 역순 잠금 사례 · 잠금 순서 규칙 · lockdep · ThreadSanitizer

꼭 쓸 키워드
상호 배제점유 대기비선점순환 대기자원 할당 그래프대기 그래프은행원 알고리즘안전 상태희생자 선택잠금 순서

다른 답안과 차이를 내는 한 가지는 그림 3 처럼 «사이클이 있어도 교착상태가 아닌» 경우와, 그림 5 처럼 가용이 남는데도 거절되는 요청을 함께 보이는 것이다.

9오해와 사실

  • 오해자원 할당 그래프에 사이클이 있으면 반드시 교착상태다.
    사실자원 유형마다 인스턴스가 하나일 때만 그렇고, 여럿이면 사이클은 필요조건일 뿐이다(Holt 1972) — 그림 3 의 나는 P3 가 끝나면 풀린다.
  • 오해불안전 상태는 곧 교착상태다.
    사실불안전은 모든 프로세스가 최대 요구를 끝까지 요청하면 막힐 수 있다는 뜻이고, 실제 요구가 그보다 적으면 끝까지 진행된다(EWD123 6.1절 안전 상태 정의).
  • 오해PTHREAD_MUTEX_ERRORCHECK 뮤텍스를 쓰면 스레드 사이 교착상태를 오류로 돌려받는다.
    사실EDEADLK 는 같은 스레드가 이미 쥔 뮤텍스를 다시 잠글 때만 돌아오고, 두 스레드의 역순 잠금은 그대로 멈춘다(pthread_mutex_lock(3p)).

10핵심 정리

개념맡는 일시점판정 기준대표 구현 · 도구
네 조건교착상태가 생길 수 있는가설계상호 배제 · 점유 대기 · 비선점 · 순환 대기 모두Coffman 외 1971
자원 할당 그래프요청 · 할당 관계 표현분석인스턴스 1 = 사이클이면 교착Holt 1972 · 대기 그래프
예방조건 하나를 없앰설계 · 코딩잠금 순서 · 한꺼번에 받기 · 후퇴Havender 1968 · lockdep
회피불안전 요청을 미룸요청마다허락 뒤에도 끝낼 순서가 남는가은행원 알고리즘(EWD123)
탐지생긴 교착을 찾음주기 · 멈춘 뒤대기 그래프의 사이클findDeadlockedThreads · gdb 스택
회복자원을 되찾음탐지 뒤희생자 비용(진행량 · 재시작 비용)프로세스 종료 · 트랜잭션 철회
라이브락 · 기아교착과 구분할 멈춤진단CPU 사용 · 사슬이 열림top -H · 대기 시간

11참고 문헌

  1. 먼저 볼 문헌
  2. ★ System Deadlocks — 네 조건과 예방 · 회피 · 탐지 분류의 원래 정의를 볼 때
    E. G. Coffman Jr. · M. J. Elphick · A. Shoshani · ACM Computing Surveys 3(2) 67-78 · 1971-06 · doi.org/10.1145/356586.356588 · 확인 2026-11-03
  3. ★ Cooperating Sequential Processes (EWD 123) — 은행원 알고리즘과 안전 상태 정의를 원문으로 확인할 때
    E. W. Dijkstra · E.W. Dijkstra Archive (University of Texas at Austin) · 1965-09 · www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html · 확인 2026-11-03
  4. ★ Some Deadlock Properties of Computer Systems — 자원 할당 그래프와 사이클 판정 규칙을 볼 때
    R. C. Holt · ACM Computing Surveys 4(3) 179-196 · 1972-09 · doi.org/10.1145/356603.356607 · 확인 2026-11-03
  5. ★ Runtime locking correctness validator (lockdep) — 커널이 잠금 순서 역전을 실제 멈춤 전에 찾는 방법을 볼 때
    The Linux Kernel documentation · 2026-11 · docs.kernel.org/locking/lockdep-design.html · 확인 2026-11-03
  6. 본문 근거
  7. Avoiding deadlock in multitasking systems — J. W. Havender · IBM Systems Journal 7(2) 74-84 · 1968-06 · doi.org/10.1147/sj.72.0074 · 확인 2026-11-03
  8. pthread_mutex_lock(3p) POSIX manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man3/pthread_mutex_lock.3p.html · 확인 2026-11-03
  9. Interface ThreadMXBean (Java SE 21 API) — Oracle · 2023-09 · docs.oracle.com/en/java/javase/21/docs/api/java.management/java/lang/management/ThreadMXBean.html · 확인 2026-11-03
  10. Documentation for /proc/sys/kernel/ (hung_task_timeout_secs) — The Linux Kernel documentation · 2026-11 · docs.kernel.org/admin-guide/sysctl/kernel.html · 확인 2026-11-03
  11. ThreadSanitizer (Clang documentation) — LLVM Project · 2026-11 · clang.llvm.org/docs/ThreadSanitizer.html · 확인 2026-11-03
  12. Debugging Programs with Multiple Threads (GDB manual) — GNU Project · 2026-11 · sourceware.org/gdb/current/onlinedocs/gdb.html/Threads.html · 확인 2026-11-03
  13. top(1) Linux manual page — man7.org · 2026-11 · man7.org/linux/man-pages/man1/top.1.html · 확인 2026-11-03