교착상태Deadlock
둘 이상의 프로세스나 스레드가 서로 상대가 쥔 자원을 기다리며 어느 쪽도 진행하지 못하는 상태이다. 상호 배제 · 점유 대기 · 비선점 · 순환 대기 네 조건이 모두 성립할 때 생긴다.
1요약
- 교착상태는 운영체제의 자원 관리 · 스레드 라이브러리의 뮤텍스 · DBMS 잠금 관리자에서 생기는 무한 대기이며, Coffman 외(1971)가 정리한 네 조건이 모두 성립할 때만 생기므로 그 위에서 예방 · 회피 · 탐지 · 회복의 네 대응이 나뉜다.
- 한 번 생기면 CPU 가 놀고 있어도 요청이 영원히 멈춘다 — Dijkstra 는 저장 장치 100페이지를 두 프로세스가 40 · 20페이지씩 쥔 상태에서 한 페이지씩 더 주면, 둘 다 39페이지를 더 기다리는데 남은 것은 38페이지라 누구도 끝나지 않는 「죽음의 포옹」을 보였다(EWD123 6절).
- 「멈췄다」는 대기 사슬이 닫혔는가로 가른다 — 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쉽게 이해하기 — 도장과 서류철을 하나씩 쥔 두 직원
결재실에는 도장 하나와 서류철 하나가 있고, 결재 한 건을 끝내려면 둘 다 있어야 한다. 직원 김은 도장을 먼저 집고 서류철을 기다리고, 직원 박은 서류철을 먼저 집고 도장을 기다린다. 둘 다 «다 쓰면 줄게»라며 손에 쥔 것을 놓지 않아 결재실이 멈춘다. 순찰하던 총무 팀장이 서로를 기다리는 원을 발견하고 박에게 서류철을 내려놓고 처음부터 다시 하게 한 뒤, 「도장부터 집는다」는 규칙을 벽에 붙인다.
그림 1 · 두 직원이 하나씩 쥐고 서로의 것을 기다리면 원이 닫혀 멈추고, 팀장이 원을 찾아 한 명을 물러나게 해야 풀린다.
그림 2 · 결재실의 네 습관이 모두 있어야 원이 닫히고, 하나만 깨도 멈추지 않는다 — 이것이 교착상태의 네 조건이다.
| 비유 속 역할 | 실제 이름 | 실제로 하는 일 |
|---|---|---|
| 직원 김 · 박 | 프로세스 · 스레드 | 자원을 요청하고 쥐고 놓는다 |
| 도장 · 서류철 | 자원(뮤텍스 · 장치 · 페이지) | 한 번에 정해진 수만 쓸 수 있다 |
| 쥔 채 기다림 | 점유 대기 · 요청 간선 | 할당받은 것을 둔 채 다음 획득 함수에서 잠든다 |
| 서로 기다리는 원 | 순환 대기 · 그래프 사이클 | 대기 사슬이 처음 프로세스로 돌아온다 |
| 팀장의 순찰 | 탐지 알고리즘 | 대기 그래프에서 사이클을 찾는다 |
| 한 명이 내려놓고 다시 | 회복 · 희생자 선택 | 프로세스 종료나 트랜잭션 철회로 자원을 되찾는다 |
| 「도장부터」 규칙 | 예방 · 잠금 순서 | 모든 코드가 같은 순서로만 잠가 원을 못 만들게 한다 |
| 최대 필요량 장부 | 회피 · 은행원 알고리즘 | 빌려줘도 모두 끝낼 순서가 남을 때만 허락한다 |
⚠ 비유가 맞지 않는 곳: 직원은 말로 양보할 수 있지만 스레드는 잠금 획득 함수 안에서 잠들어 스스로 풀지 못하며, 실제 회복은 대개 한 명이 내려놓는 정도가 아니라 프로세스 전체를 끝내는 것이라 그동안 한 일을 잃는다.
4구조 — 자원 할당 그래프와 네 조건
자원 할당 그래프는 프로세스(원)와 자원(사각형 · 안의 점 = 인스턴스 수)을 노드로 두고, 요청 간선 P → R 과 할당 간선 R → P 를 긋는다(Holt 1972). 자원마다 인스턴스가 하나이면 사이클이 곧 교착상태이고, 여럿이면 사이클은 필요조건일 뿐이다.
그림 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 · 잠금 이름은 설명용 가정 값이다.
- T1 이 항목을 넣으려고
pthread_mutex_lock(&q_lock)을 성공한다 — 할당 간선 q_lock → T1. - T2 가 통계를 모으려고
pthread_mutex_lock(&st_lock)을 성공한다 — 할당 간선 st_lock → T2. - T1 이 처리 건수를 더하려고
st_lock을 요청하고 잠든다 — 요청 간선 T1 → st_lock. - T2 가 큐 길이를 읽으려고
q_lock을 요청하고 잠든다 — 사이클 T1 → st_lock → T2 → q_lock → T1 이 닫힌다. 뮤텍스는 인스턴스가 하나이므로 이것이 곧 교착상태다. top -H -p 5120에서 두 스레드가 모두 S(잠듦) 상태 · %CPU 0.0 이고 처리 건수가 늘지 않는다(top(1)).gdb -p 5120 -batch -ex "thread apply all bt"로 두 스레드가 모두pthread_mutex_lock안에서 멈춘 것과 호출부enqueue()·report()를 확인하고, 각자 쥔 잠금을 소스와 맞춰 사이클을 그린다(GDB Threads).- 사용자 공간 뮤텍스는 다른 스레드가 빼앗을 수 없으므로(비선점) 프로세스를 재시작해 회복한다 — 큐에 있던 처리 전 항목은 잃는다.
report()를 「q_lock → st_lock」 순서로 고쳐 순환 대기를 없애고, 시험 빌드를-fsanitize=thread로 돌려 역순 잠금이 다시 들어오면 보고되게 한다(ThreadSanitizer detect_deadlocks 기본 true).
그림 4 · 각자 하나씩 잡은 뒤(①②) 상대 잠금을 요청하는 순간(③④) 사이클이 닫히고, 그 뒤는 탐지 · 회복 · 순서 규칙(⑤~⑧)으로만 빠져나온다.
회피는 요청이 올 때마다 «허락한 뒤에도 모든 프로세스를 끝낼 순서가 남는가»를 검사한다(EWD123 6.1절). 아래는 같은 종류 자원 10단위를 프로세스 셋이 나눠 쓰는 가정 값이다 — 남은 요구 = 최대 − 보유이고, 남은 요구가 가용 이하인 프로세스를 하나씩 끝냈다고 보고 그 보유분을 가용에 더한다.
그림 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)) |
| 3 | Java 서비스 멈춤 | 모니터 · 소유 가능 동기화기 순환 | JVM | ThreadMXBean. | null 이 아니면 교착 스레드 ID 배열 · 가상 스레드가 낀 사이클은 못 찾음(Java SE 21 API) |
| 4 | 커널 로그에 hung task 경고 | 커널 잠금 교착 · 느린 저장 장치 | 커널 | sysctl kernel. · dmesg | D 상태가 이 값(초)보다 오래 스케줄되지 않으면 경고 · 0 이면 검사 안 함(커널 sysctl 문서) |
| 5 | 개발 커널에서 잠금 순서 경고 | 잠금 순서 역전 | 커널 | grep "lock-classes" / | 한 번이라도 일어난 역순 사슬을 실제 멈춤 전에 알림 · 클래스 상한 8191(lockdep 설계 문서) |
| 6 | 시험에서만 가끔 멈춤 | 드문 역순 잠금 | 빌드 | -fsanitize=thread | 역순 잠금 보고 · 5 ~ 15배 느려져 운영이 아닌 시험에서 씀(Clang ThreadSanitizer) |
같은 멈춤이 재현되지 않으면 1행의 스택을 두 번 이상 떠서 같은 함수에 머무는지 본다. 4행 경고는 교착 외에 저장 장치 지연에도 나므로, 스택에 잠금 함수가 있는지로 다시 가른다.
8시험 대비
www.q-net.or.kr시험에서는 네 조건과 예방 · 회피 · 탐지 · 회복을 정리하는 정의 · 특징형, 은행원 알고리즘의 안전 검사를 수치로 따라가는 동작 · 절차 설명형이 나올 수 있다. 장애 사례(멈춘 서비스)를 주고 원인과 대책을 묻는 장애 · 보안 대응형이면 4 · 6 항목을 늘린다.
- 개요 — 정의 · 무한 대기 · 죽음의 포옹 예(100페이지 · 가용 38 < 요구 39)
- 발생 조건 — 네 조건 표(뜻 · 없애는 예방 방법 · 대가) · 하나만 깨도 생기지 않음(Coffman 외 1971)
- 자원 할당 그래프 — 그림 3 인스턴스 하나 ↔ 둘 비교 · 사이클 = 필요조건
- 대응 넷 — 예방 · 회피 · 탐지 · 회복 비교표(개입 시점 · 미리 알 것 · 이용률)
- 은행원 알고리즘 — 그림 5 안전 검사(가용 3 · 허락 1건 · 거절 1건 · 불안전 ≠ 교착상태)
- 실무 대책 — 그림 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참고 문헌
- 먼저 볼 문헌
- ★ System Deadlocks — 네 조건과 예방 · 회피 · 탐지 분류의 원래 정의를 볼 때
- ★ Cooperating Sequential Processes (EWD 123) — 은행원 알고리즘과 안전 상태 정의를 원문으로 확인할 때
- ★ Some Deadlock Properties of Computer Systems — 자원 할당 그래프와 사이클 판정 규칙을 볼 때
- ★ Runtime locking correctness validator (lockdep) — 커널이 잠금 순서 역전을 실제 멈춤 전에 찾는 방법을 볼 때
- 본문 근거
- 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 - 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 - 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 - 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 - ThreadSanitizer (Clang documentation) — LLVM Project · 2026-11 ·
clang.llvm.org/docs/ThreadSanitizer.html· 확인 2026-11-03 - Debugging Programs with Multiple Threads (GDB manual) — GNU Project · 2026-11 ·
sourceware.org/gdb/current/onlinedocs/gdb.html/Threads.html· 확인 2026-11-03 - top(1) Linux manual page — man7.org · 2026-11 ·
man7.org/linux/man-pages/man1/top.1.html· 확인 2026-11-03