학습 목표
데드락(deadlock) 이 무엇인지, 왜 영원히 풀리지 않는 상태인지 설명할 수 있다.
데드락 필요조건 4가지를 나열하고 각각의 의미를 설명할 수 있다.
자원 할당 그래프(RAG) 에서 사이클이 데드락과 어떤 관계인지 설명할 수 있다.
락 순서를 통일하지 않아 생기는 전형적 2-process 데드락을 그릴 수 있다.
문제 상황
- 마이크로서비스 A→B, B→A 동기 HTTP 호출 후 둘 다 타임아웃 없이 대기
- 스레드 1:
lock(A); lock(B);/ 스레드 2:lock(B); lock(A);— 재현율 낮은 hang - DB 트랜잭션이 락 대기로 쌓이고 애플리케이션 전체가 멈춘 것처럼 보인다
kill -9로만 풀리는 프로세스 — OS가 자동으로 고르지 않는다
동기화 도구를 쓰면 배제는 되지만, 잘못 쓰면 교착에 빠진다.
1. 데드락이란
둘 이상의 프로세스·스레드가 서로가 가진 자원을 기다리며 무한 대기하는 상태.
- CPU가 아무에게도 할당되지 않거나, 일부만 돌아가는 부분 교착도 있다
- OS는 탐지·복구를 할 수도 있고, 예방·회피로 안 들어가게 할 수도 있다
2. 필요조건 4가지 (Coffman)
네 가지가 동시에 성립해야 데드락이 가능하다. 하나라도 깨면 예방·회피 여지가 생긴다.
| 조건 | 의미 | 깨는 아이디어 |
|---|---|---|
| 상호 배제 | 자원을 한 번에 하나만 사용 | 공유 가능 자원만 쓰기(항상 가능하진 않음) |
| 점유와 대기 | 일부 자원을 쥔 채 다른 자원 대기 | 한꺼번에 요청(all-or-nothing) |
| 비선점 | 자원을 강제로 빼앗을 수 없음 | 선점 가능 자원(주로 CPU·메모리 일부) |
| 순환 대기 | P0→P1→…→P0 형태의 대기 고리 | 락 순서 전역 정렬 |
- 실무에서 가장 자주 쓰는 해법: 순환 대기 제거 — 모든 락을 정해진 순서로만 획득
3. 자원 할당 그래프 (RAG)
| 요소 | 표기 |
|---|---|
| 프로세스 | 원 |
| 자원 타입 | 사각형 (인스턴스 점으로) |
| 할당 | 자원 → 프로세스 화살표 |
| 요청 | 프로세스 → 자원 점선 |
| 그래프 | 데드락 |
|---|---|
| 사이클 없음 | 데드락 없음 |
| 사이클 있음, 자원당 인스턴스 1개 | 데드락 |
| 사이클 있음, 인스턴스 여러 개 | 데드락 가능 (추가 분석 필요) |
4. 고전 예: 두 스레드·두 락
Thread 1: lock(mutex_A); lock(mutex_B);
Thread 2: lock(mutex_B); lock(mutex_A);
| 시점 | Thread 1 | Thread 2 |
|---|---|---|
| t1 | A 획득 | B 획득 |
| t2 | B 대기 | A 대기 |
| 결과 | 순환 대기 — 둘 다 영원히 block |
- 해결: 항상 A → B 순서로만 lock
std::lock(m1, m2)처럼 동시 획득 API도 순환 대기를 막는 패턴
5. 데드락 vs 기아(starvation)
| 데드락 | 기아 | |
|---|---|---|
| 상태 | 아무도 진행 못 함 | 일부만 영원히 대기 |
| 필요조건 | 4가지 동시 | 우선순위·불공정 스케줄링 |
| 예 | A↔B 락 | 낮은 우선순위 프로세스 |
- Livelock: 서로 양보하며 진행도 못 하는 바쁜 대기 — 데드락은 아님
6. 정리
- 데드락 = 상호 배제 + 점유 대기 + 비선점 + 순환 대기
- RAG 사이클은 직관적 모델, 단일 인스턴스면 사이클 ↔ 데드락
- 락 전역 순서가 실무 1순위 예방책
- 다음: 예방·회피(Banker)·탐지·복구
다음에 다룰 것
- 데드락 해결
- 예방, 회피, Banker 알고리즘, 탐지·복구
해당 내용은 Operating System Concepts, 10/E (Avraham Silberschatz, Peter Baer Galvin, Greg Gagne) 의 내용을 기반으로 합니다.