데드락 (Deadlock)

데드락(교착 상태)은 두 개 이상의 프로세스나 스레드가 서로 상대가 가진 자원을 기다리느라 아무도 다음 단계로 못 나아가는 상태입니다. 데드락의 기본 개념을 먼저 보고, B4-2 03번 이슈(Deadlock 분석)에 필수 개념을 실제 테스트 로그와 함께 정리합니다. 이어서 운영체제가 데드락을 예방, 회피, 탐지, 회복하는 방법을 보고, 마지막에 02번 CPU 문제와 비교합니다.

데드락 기본 개념

비유: 좁은 골목에서 마주친 두 차

Thread A가 가진 것: 자원 🔑1
Thread A가 필요한 것: 자원 🔑2

Thread B가 가진 것: 자원 🔑2
Thread B가 필요한 것: 자원 🔑1

결과:
Thread A: "🔑2 줘!" → Thread B: "🔑1 먼저 줘!"
Thread B: "🔑1 줘!" → Thread A: "🔑2 먼저 줘!"

→ 둘 다 영원히 대기... 💀 데드락!

데드락 발생 4가지 조건 (모두 만족해야 발생)

1. 상호 배제 (Mutual Exclusion)
   → 자원을 한 번에 하나의 스레드만 사용 가능

2. 점유 대기 (Hold and Wait)
   → 자원을 가진 채로 다른 자원을 기다림

3. 비선점 (No Preemption)
   → 강제로 자원을 빼앗을 수 없음

4. 순환 대기 (Circular Wait)
   → A→B→C→A 형태로 순환하며 대기

데드락은 언제 생기나

여러 프로그램이 동시에 돌아가는 환경에서는 한정된 자원(락, 파일, 프린터, DB 행 등)을 서로 얻으려고 경쟁합니다. 어떤 프로세스가 자원을 요청했는데 그 자원을 이미 다른 프로세스가 쓰고 있으면 요청한 쪽은 대기 상태로 들어갑니다. 이렇게 기다리던 프로세스들이 영영 실행 상태로 돌아올 수 없게 되면 데드락입니다.

text

시각 t1: 프로세스1이 자원1을 얻음      프로세스2가 자원2를 얻음
시각 t2: 프로세스1은 자원2를 기다림     프로세스2는 자원1을 기다림

   프로세스1 ──가짐──▶ 자원1
       ▲                 │
     기다림            기다림
       │                 ▼
     자원2 ◀──가짐── 프로세스2

서로 원하는 자원을 상대가 쥐고 있어서 둘 다 끝없이 기다립니다. 외나무다리 양 끝에서 서로 비켜 주기만 기다리는 것과 같습니다.

Deadlock 분석 필수 개념

1. 멀티스레드 (Multithreading)

정의: 하나의 프로세스 내에서 여러 개의 스레드가 동시에 실행되는 것

프로세스 vs 스레드:

프로세스 (Process):
- 독립적인 프로그램 실행 단위
- 각자 메모리 공간 보유
- 예: 크롬, 유튜브, 카톡 앱

스레드 (Thread):
- 같은 프로세스 내의 실행 단위
- 메모리 공간 공유
- 예: 크롬 내의 여러 탭들이 동시에 작동

우리 테스트:
agent-leak-app 프로세스 내에
├─ Worker-Thread-1
├─ Worker-Thread-2
└─ (다른 스레드들)
이 동시에 실행

2. 자원 (Resource)

정의: 여러 스레드가 공유하는 데이터나 객체

우리 테스트의 자원:

1. Shared_Memory_A (공유 메모리)
2. Socket_Pool_B (소켓 풀)

이 둘을 여러 스레드가 동시에 접근하려 함

현실적 예시:

은행의 계좌 잔액 (자원):
- 스레드1: 입금 시도
- 스레드2: 출금 시도
→ 동시에 접근하면 일관성 깨짐
→ 따라서 한 번에 1개 스레드만 접근 가능

3. 락 (Lock / Mutual Exclusion - 상호 배제)

정의: 한 번에 1개 스레드만 자원을 사용하도록 제한하는 메커니즘

동작:

Lock 획득:
스레드1: "Shared_Memory_A 사용하겠습니다" (Lock 획득 ✓)
스레드2: "Shared_Memory_A 사용하겠습니다" (Lock 대기... ⏳)

스레드1이 작업 완료:
스레드1: "다 했습니다" (Lock 해제)
스레드2: "이제 사용합니다" (Lock 획득 ✓)

우리 로그에서:

2026-05-27 05:50:08,816 [INFO] LOCK ACQUIRED: [Shared_Memory_A]
→ 이 스레드가 락을 획득함
→ 다른 스레드는 접근 불가

4. 교착상태 (Deadlock)

정의: 2개 이상의 스레드가 서로가 가진 자원을 기다리며 무한히 대기하는 상태

우리 테스트의 상황:

시간순서:
T1: 스레드1이 자원A 획득
    스레드2가 자원B 획득

T2: 스레드1이 자원B 필요 → 스레드2가 가지고 있음 → 대기
    스레드2가 자원A 필요 → 스레드1이 가지고 있음 → 대기

T3: 둘 다 자신이 필요한 자원을 못 가지고 있음
    → 영원히 대기 (교착상태)

로그:
2026-05-27 05:50:10,820 [INFO] WAITING for [Socket_Pool_B]... (Status: BLOCKED)
2026-05-27 05:50:10,820 [INFO] WAITING for [Shared_Memory_A]... (Status: BLOCKED)
→ 둘 다 BLOCKED 상태에서 멈춤

현실적 예시:

교과서의 "식사하는 철학자 문제":

철학자 A, B가 앉아있고 포크 2개가 있음
(A 왼쪽에 포크1, 오른쪽에 포크2, B 오른쪽에 포크1... 등)

A: 왼쪽 포크 집음 (포크1 획득)
B: 오른쪽 포크 집음 (포크2 획득)

A: 오른쪽 포크 필요 → B가 가지고 있음 (대기)
B: 왼쪽 포크 필요 → A가 가지고 있음 (대기)

→ 둘 다 영원히 기다림 (밥을 못 먹음)

5. 데드락 4가지 필수 조건 (Deadlock Conditions)

데드락이 발생하려면 다음 4가지 조건을 모두 만족해야 함:

조건 1: 상호 배제 (Mutual Exclusion)

자원이 배타적으로 사용됨
= 한 번에 1개 스레드만 사용 가능

우리 경우:
Shared_Memory_A는 한 번에 1개 스레드만 접근 가능
Socket_Pool_B도 한 번에 1개 스레드만 접근 가능

✓ 만족

조건 2: 점유 대기 (Hold and Wait)

스레드가 자원을 보유하면서 다른 자원 대기
= 가진 것 놓지 않고 필요한 것 기다림

우리 경우:
스레드1: 자원A 보유 → 자원B 대기
스레드2: 자원B 보유 → 자원A 대기

✓ 만족

조건 3: 비선점 (No Preemption)

자원을 강제로 빼앗을 수 없음
= 획득한 스레드만 해제 가능

우리 경우:
스레드1이 자원A를 가지면
다른 스레드가 강제로 빼앗을 수 없음
(스레드1이 해제할 때까지 대기)

✓ 만족

조건 4: 순환 대기 (Circular Wait)

자원 대기가 순환 구조를 이룸
= A → B → A 형태 (또는 A → B → C → A 등)

우리 경우:
스레드1 (자원A 보유) → 스레드2 (자원B 보유) → 스레드1
                    ↑                              ↓
                    └──────────────────────────────┘

순환 구조!

✓ 만족

결론: 4가지 조건 모두 만족 → 데드락 발생

6. 자원 획득 순서 (Resource Ordering)

정의: 여러 자원을 사용할 때 획득하는 순서

문제 상황 (우리 테스트):

스레드1: 자원A → 자원B 순서로 획득
스레드2: 자원B → 자원A 순서로 획득
                 ↑
                다른 순서!

해결책:

모든 스레드가 동일 순서로 획득:

방법1:
스레드1: 자원A → 자원B
스레드2: 자원A → 자원B (동일 순서)

방법2:
스레드1: 자원B → 자원A
스레드2: 자원B → 자원A (동일 순서)

→ 순환 대기 불가능!

7. 블로킹 (Blocking) vs 대기 (Waiting)

블로킹 (Blocking):

스레드가 자원을 기다리며 실행을 멈춤

로그에서:
[INFO] WAITING for [Socket_Pool_B]... (Status: BLOCKED)
→ BLOCKED 상태 = 실행하지 않음, 기다리는 중

CPU/메모리 상태:

BLOCKED 상태의 스레드:
- CPU: 0% (실행하지 않음)
- 메모리: 변화 없음 (새로 할당 안 함)
- 로그: 안 나옴 (I/O 수행 안 함)

우리 테스트 결과:

2026-05-27 05:50:10,820 이후:
- CPU: 0%
- 메모리: 정체
- 로그: 없음
→ 모든 스레드가 BLOCKED 상태

요약: Deadlock (03번)

스레드1: 자원A 획득 → 자원B 대기
스레드2: 자원B 획득 → 자원A 대기

→ 서로의 자원을 무한히 기다림
→ 4가지 데드락 조건 모두 만족
→ 프로세스 멈춤 (응답 불가)

결론: 위험! 즉시 MULTI_THREAD=false로 전환 필요

데드락을 다루는 방법

앞에서 본 4가지 조건이 모두 성립해야 데드락이 생깁니다. 그래서 처리 방법은 크게 "아예 안 생기게 막기"와 "생기면 찾아서 풀기"로 나뉩니다.

방법	언제 손쓰나	한 줄 요약	비용
예방 (Prevention)	미리	4가지 조건 중 하나를 원천 차단	자원 낭비가 심함
회피 (Avoidance)	자원을 줄 때마다	줘도 안전한지 계산해 보고 위험하면 안 줌	매번 검사 비용, 최대 요구량을 미리 알아야 함
탐지 & 회복 (Detection & Recovery)	생긴 뒤	데드락을 허용하고, 찾아내서 풀어 줌	탐지 알고리즘 실행 비용, 작업 손실
무시 (Ignore)	안 함	드물게 생기니 그냥 둠, 생기면 재시작	가장 쌈. 실제 일반 운영체제가 주로 쓰는 방식

예방: 조건 하나를 없앤다

없앨 조건	방법	문제점
상호 배제	자원을 여러 프로세스가 함께 쓰게 함	프린터, 락처럼 원래 한 명만 써야 하는 자원이 많아 현실적으로 어려움
점유 대기	실행 전에 필요한 자원을 한꺼번에 모두 받게 함	당장 안 쓰는 자원까지 붙잡아 낭비, 자원을 다 못 받는 프로세스는 기아
비선점	다른 자원을 기다려야 하면 가진 자원을 내려놓게 함	하던 작업을 되돌려야 하는 손실
순환 대기	자원마다 번호를 매기고 번호 순서대로만 요청하게 함	번호 체계에 맞추느라 자원을 일찍 잡아야 할 수 있음

위에서 본 자원 획득 순서 통일이 바로 순환 대기를 없애는 예방법입니다. 실무에서 가장 많이 쓰는 방법이기도 합니다.

회피: 줘도 안전할 때만 준다

회피는 자원을 요청받을 때마다 "이걸 주고 나서도 모든 프로세스가 언젠가 끝날 수 있는 순서가 있는가?"를 미리 검사합니다. 그런 순서(안전 순서)가 있는 상태를 안정 상태라고 하고, 안정 상태가 유지될 때만 자원을 줍니다. 안정 상태가 깨지면 데드락이 꼭 생기는 것은 아니지만, 생길 가능성이 있다는 뜻이므로 주지 않고 기다리게 합니다.

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

은행이 가진 현금으로 모든 고객의 대출 요구를 결국 다 들어줄 수 있을 때만 돈을 빌려주는 방식에서 이름이 왔습니다. 각 프로세스는 처음에 자원을 최대 몇 개까지 쓸지 미리 알려 줘야 합니다.

Need(앞으로 더 필요한 양) = 최대 요구량 - 이미 받은 양
남은 자원으로 Need를 채울 수 있는 프로세스를 찾아 끝까지 실행시켰다고 치고, 그 프로세스가 가졌던 자원을 돌려받습니다.
이것을 반복해서 모든 프로세스를 끝낼 수 있으면 안정 상태입니다.

python

# 은행원 알고리즘: 지금 상태가 "안정 상태"인지 검사
available = [3, 3, 2]                      # 남은 자원 (A, B, C)
allocation = {"P0": [0, 1, 0], "P1": [2, 0, 0], "P2": [3, 0, 2], "P3": [2, 1, 1], "P4": [0, 0, 2]}
maximum    = {"P0": [7, 5, 3], "P1": [3, 2, 2], "P2": [9, 0, 2], "P3": [2, 2, 2], "P4": [4, 3, 3]}

need = {p: [m - a for m, a in zip(maximum[p], allocation[p])] for p in allocation}
work = available[:]
order = []
while len(order) < len(allocation):
    for p in allocation:
        if p not in order and all(n <= w for n, w in zip(need[p], work)):
            work = [w + a for w, a in zip(work, allocation[p])]   # 끝나면 빌린 자원을 돌려줌
            order.append(p)
            print(f"{p} 실행 가능 (필요 {need[p]}) → 반납 후 남은 자원 {work}")
            break
    else:
        print("더 실행할 수 있는 프로세스가 없음 → 불안정 상태")
        break
else:
    print("안전 순서:", " → ".join(order))

text

P1 실행 가능 (필요 [1, 2, 2]) → 반납 후 남은 자원 [5, 3, 2]
P3 실행 가능 (필요 [0, 1, 1]) → 반납 후 남은 자원 [7, 4, 3]
P0 실행 가능 (필요 [7, 4, 3]) → 반납 후 남은 자원 [7, 5, 3]
P2 실행 가능 (필요 [6, 0, 0]) → 반납 후 남은 자원 [10, 5, 5]
P4 실행 가능 (필요 [4, 3, 1]) → 반납 후 남은 자원 [10, 5, 7]
안전 순서: P1 → P3 → P0 → P2 → P4

남은 자원 (3, 3, 2)로는 P0(7, 4, 3)을 바로 채울 수 없지만, P1부터 끝내고 자원을 돌려받으면 결국 모두 끝낼 수 있으므로 이 상태는 안정 상태입니다.

자원 할당 그래프 알고리즘 (Resource-Allocation Graph)

프로세스와 자원을 점으로, "요청한다"와 "가지고 있다"를 화살표로 그린 그래프로 판단합니다.

프로세스가 자원을 요청하면, 그 요청 화살표를 할당 화살표로 바꿨을 때 그래프에 사이클(빙 도는 고리)이 생기는지 확인합니다.
사이클이 생기지 않으면 자원을 줍니다.
사이클이 생긴다고 무조건 데드락은 아닙니다.
- 자원마다 개수가 하나뿐이면 사이클 = 데드락
- 자원이 여러 개 있으면 사이클 = 데드락 가능성 (다른 프로세스가 반납하면 풀릴 수 있음)

탐지와 회복: 생기면 찾아서 푼다

데드락이 생기는 것을 일단 허용하고, 주기적으로(또는 자원 요청 때마다) 탐지 알고리즘을 돌려 찾아냅니다. 자원 할당 그래프의 사이클을 찾거나 은행원 알고리즘과 비슷한 계산을 씁니다. 자주 돌릴수록 빨리 찾지만 그만큼 오버헤드가 커집니다.

찾았으면 다음 두 가지 방법으로 풉니다.

프로세스 종료
- 데드락에 걸린 프로세스를 모두 한꺼번에 종료 (확실하지만 작업 손실이 큼)
- 데드락이 풀릴 때까지 하나씩 종료 (종료할 때마다 탐지 알고리즘을 다시 돌려야 함)
자원 선점
- 데드락에 걸린 프로세스의 자원을 빼앗아 다른 프로세스에게 줌 (빼앗긴 프로세스는 일시정지)
- 우선순위가 낮거나 지금까지 실행을 적게 한 프로세스부터 빼앗음. 같은 프로세스만 계속 희생되면 기아가 생기므로 희생 횟수도 고려함

데이터베이스가 대표적인 예입니다. 트랜잭션끼리 데드락이 생기면 DB가 이를 탐지해서 한쪽 트랜잭션을 롤백시킵니다. 동시성 문제와 격리 수준도 함께 보면 좋습니다.

식사하는 철학자 문제

원형 테이블에 철학자 5명이 앉아 있고, 철학자 사이마다 젓가락이 하나씩, 모두 5개 놓여 있습니다. 밥을 먹으려면 양옆 젓가락 2개가 모두 필요합니다.

text

철학자0 ─ 젓가락0 ─ 철학자1 ─ 젓가락1 ─ 철학자2
   │                                     │
젓가락4                               젓가락2
   │                                     │
철학자4 ─────────── 젓가락3 ─────────── 철학자3
(원형 테이블을 펼쳐 그린 모습. 철학자마다 양옆 젓가락 2개가 필요)

모두가 동시에 "왼쪽 젓가락을 먼저 집고, 오른쪽을 기다린다"면 5명 모두 왼쪽 하나씩만 쥔 채 영원히 기다립니다. 데드락의 4가지 조건이 그대로 들어 있는 대표 예제입니다. 또 데드락을 피하더라도 어떤 철학자는 계속 젓가락을 못 잡아 굶을 수 있어서 기아(Starvation) 문제를 설명할 때도 함께 나옵니다.

해결 방법은 다음과 같습니다.

철학자 5명 중 4명까지만 동시에 앉게 합니다. 젓가락 5개를 4명이 나누면 적어도 한 명은 2개를 잡을 수 있습니다.
양쪽 젓가락을 둘 다 집을 수 있을 때만 집게 합니다. (점유 대기 제거)
한 명(또는 짝수 번 철학자)은 오른쪽 젓가락부터 집게 합니다. 순환 대기 고리가 끊어집니다.

면접에서 자주 나오는 질문

데드락이 무엇이고, 발생 조건 4가지는 무엇인가요?
데드락을 예방하는 방법과 회피하는 방법은 어떻게 다른가요?
은행원 알고리즘을 설명해 보세요.
식사하는 철학자 문제와 해결 방법을 설명해 보세요.
데드락과 기아(Starvation)는 어떻게 다른가요? (데드락은 관련된 모두가 멈춘 상태, 기아는 다른 프로세스는 잘 돌아가는데 특정 프로세스만 계속 차례를 못 받는 상태)

CPU 문제 vs 데드락 비교

항목	CPU (02번)	Deadlock (03번)
문제	CPU 과사용	자원 경쟁
해결책	Cooldown (자동 조절)	자원 순서 통일
프로세스 상태	계속 실행 (CPU 낮춤)	멈춤 (BLOCKED)
CPU 사용률	30% 유지	0% (멈춤)
로그	계속 나옴	멈춤
자동 복구	✓ 있음	✗ 없음
위험도	낮음 (조절됨)	높음 (무한 대기)

정리

Deadlock 관련 개념

Multithreading: 하나의 프로세스 내 여러 스레드 동시 실행
자원: 여러 스레드가 공유하는 데이터/객체
락(Lock): 한 번에 1개 스레드만 접근하도록 제한
Deadlock: 2개 이상 스레드가 서로의 자원을 무한히 기다리는 상태
데드락 4가지 조건: Mutual Exclusion, Hold and Wait, No Preemption, Circular Wait
자원 획득 순서: 모든 스레드가 동일 순서로 자원 획득

데드락 처리 방법

개념	비전공자 버전 요약
예방	4가지 조건 중 하나를 아예 못 생기게 막기 (예: 자원 잡는 순서 통일)
회피	자원을 주기 전에 "줘도 다 끝날 수 있나" 계산해 보고 줌
은행원 알고리즘	남은 돈으로 모든 고객을 결국 만족시킬 수 있을 때만 대출
탐지 & 회복	생기도록 두고, 찾아내면 프로세스를 끝내거나 자원을 빼앗아 풀기
식사하는 철학자	모두 왼쪽 젓가락부터 집으면 다 같이 굶는 데드락 예제
기아	시스템은 돌아가는데 특정 작업만 계속 순서를 못 받음

학습 팁: Deadlock 이해하기

스레드가 여럿이면? (= Multithreading)
자원을 공유하면? (= Lock으로 보호)
서로 다른 순서로 획득하면? (= Deadlock 위험!)
한 스레드가 멈추면? (= 다른 스레드도 멈춤)

출처: Codyssey-B1/B4-2

변수와 자료형

흐름 제어

함수

클래스와 객체

CLI와 파일 입출력

데드락 (Deadlock)

데드락 기본 개념

비유: 좁은 골목에서 마주친 두 차

데드락 발생 4가지 조건 (모두 만족해야 발생)

데드락은 언제 생기나

Deadlock 분석 필수 개념

1. 멀티스레드 (Multithreading)

2. 자원 (Resource)

3. 락 (Lock / Mutual Exclusion - 상호 배제)

4. 교착상태 (Deadlock)

5. 데드락 4가지 필수 조건 (Deadlock Conditions)

조건 1: 상호 배제 (Mutual Exclusion)

조건 2: 점유 대기 (Hold and Wait)

조건 3: 비선점 (No Preemption)

조건 4: 순환 대기 (Circular Wait)

6. 자원 획득 순서 (Resource Ordering)

7. 블로킹 (Blocking) vs 대기 (Waiting)

요약: Deadlock (03번)

데드락을 다루는 방법

예방: 조건 하나를 없앤다

회피: 줘도 안전할 때만 준다

탐지와 회복: 생기면 찾아서 푼다

식사하는 철학자 문제

면접에서 자주 나오는 질문

CPU 문제 vs 데드락 비교

정리

Deadlock 관련 개념

데드락 처리 방법

학습 팁: Deadlock 이해하기

데드락 (Deadlock) ​

데드락 기본 개념 ​

비유: 좁은 골목에서 마주친 두 차 ​

데드락 발생 4가지 조건 (모두 만족해야 발생) ​

데드락은 언제 생기나 ​

Deadlock 분석 필수 개념 ​

1. 멀티스레드 (Multithreading) ​

2. 자원 (Resource) ​

3. 락 (Lock / Mutual Exclusion - 상호 배제) ​

4. 교착상태 (Deadlock) ​

5. 데드락 4가지 필수 조건 (Deadlock Conditions) ​

조건 1: 상호 배제 (Mutual Exclusion) ​

조건 2: 점유 대기 (Hold and Wait) ​

조건 3: 비선점 (No Preemption) ​

조건 4: 순환 대기 (Circular Wait) ​

6. 자원 획득 순서 (Resource Ordering) ​

7. 블로킹 (Blocking) vs 대기 (Waiting) ​

요약: Deadlock (03번) ​

데드락을 다루는 방법 ​

예방: 조건 하나를 없앤다 ​

회피: 줘도 안전할 때만 준다 ​

탐지와 회복: 생기면 찾아서 푼다 ​

식사하는 철학자 문제 ​

면접에서 자주 나오는 질문 ​

CPU 문제 vs 데드락 비교 ​

정리 ​

Deadlock 관련 개념 ​

데드락 처리 방법 ​

학습 팁: Deadlock 이해하기 ​

데드락 (Deadlock)

데드락 기본 개념

비유: 좁은 골목에서 마주친 두 차

데드락 발생 4가지 조건 (모두 만족해야 발생)

데드락은 언제 생기나

Deadlock 분석 필수 개념

1. 멀티스레드 (Multithreading)

2. 자원 (Resource)

3. 락 (Lock / Mutual Exclusion - 상호 배제)

4. 교착상태 (Deadlock)

5. 데드락 4가지 필수 조건 (Deadlock Conditions)

조건 1: 상호 배제 (Mutual Exclusion)

조건 2: 점유 대기 (Hold and Wait)

조건 3: 비선점 (No Preemption)

조건 4: 순환 대기 (Circular Wait)

6. 자원 획득 순서 (Resource Ordering)

7. 블로킹 (Blocking) vs 대기 (Waiting)

요약: Deadlock (03번)

데드락을 다루는 방법

예방: 조건 하나를 없앤다

회피: 줘도 안전할 때만 준다

탐지와 회복: 생기면 찾아서 푼다

식사하는 철학자 문제

면접에서 자주 나오는 질문

CPU 문제 vs 데드락 비교

정리

Deadlock 관련 개념

데드락 처리 방법

학습 팁: Deadlock 이해하기