Brain+++
핵심 인사이트 (3줄 요약)
- 본질: 교착 상태(Deadlock)는 두 개 이상의 트랜잭션이 서로가 보유한 잠금을 무한 대기하는 상태로, 순환 대기(Circular Wait) 조건에 의해 발생한다.
- 가치: 교착 상태 방지는 동시성 제어의 핵심 과제로, 감지(Deadlock Detection) 또는 예방(Deadlock Prevention) 전략이 사용된다.
- 융합: 교착 상태는 운영체제의 프로세스 간 교착과 동일한 이론이며, 탐지 알고리즘은 그래프 이론에 기반한다.
Ⅰ. 개요 및 필요성 (Context & Necessity)
개념
교착 상태(Deadlock)는 두 개 이상의 트랜잭션이 서로가 보유한 리소스를 기다리며 무한 대기하는 상태다. 데이터베이스에서 잠금 기반 동시성 제어를 사용할 때, 두 트랜잭션이 서로 다른 순서로 잠금을 획득하면 순환 대기가 발생하여 교착 상태에 빠질 수 있다.
필요성
교착 상태가 감지되지 않으면 관련 트랜잭션은 무한 대기에 빠진다. 이는 시스템 자원을 점유하면서 아무런 진전도 없게 만들어, 해당 트랜잭션이 접근하는 모든 데이터 항목이 다른 트랜잭션도 접근할 수 없게 차단한다. 결국 시스템 전체가 사용 불가 상태에 이른다.
비유
교착 상태는 두 사람이 서로의 핸드폰을 빌려야만 하는 상황에서 서로 상대방의 폰만 기다리고 있는 것과 같다. 아무도 양보하지 않으면 영원히 기다리게 된다.
섹션 요약 비유
교착 상태는 뷔페에서 각자 다른 음식을 잡고 있는 두 사람이, 서로의 접시를 필요로 하면서도 양보하지 않는 상황과 같다.
Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)
교착 발생 메커니즘과 네 가지 조건
┌───────────────────────────────────────────────────────────────────────┐
│ 교착 상태 발생의 네 가지 조건 (Coffman Conditions) │
├───────────────────────────────────────────────────────────────────────┤
│
│ ① 상호 배타 (Mutual Exclusion) │
│ → 리소스는 한 번에 하나의 트랜잭션만 접근 가능 │
│ │
│ ② 보유 및 대기 (Hold and Wait) │
│ → 리소스를 보유한 채 다른 리소스 대기 │
│ │
│ ③ 비선점 (No Preemption) │
│ → 보유 중인 리소스를 강제로 빼앗을 수 없음 │
│ │
│ ④ 순환 대기 (Circular Wait) ← ONLY 이것을 차단하면 교착 방지 가능 │
│ → T1 → T2 → T3 → T1 (순환 체인) │
│ │
│ ※ 핵심: ①②③은 트랜잭션 처리의 근본적 특성으로, │
│ 제거 불가능. 따라서 교착 방지는 ④ 순환 대기를 차단하는 것.
│
└───────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 교착 상태의 네 가지 조건은 1971년 Coffman이 정리한 것으로, 이 중 하나라도 성립하지 않으면 교착은 발생하지 않는다. 그러나 ①②③은 잠금 메커니즘의 근본적 특성으로 제거가 불가능하다. 따라서 교착 방지는 오직 ④ 순환 대기를 차단하는 것이다. 가장 효과적인 방법은 모든 트랜잭션이 동일한 순서로 잠금을 획득하도록 규칙을 정하는 것이다. 모든 트랜잭션이 A→B→C 순서로 접근하면, T1이 A와 B를 보유한 상태에서 C를 기다릴 때, T2는 아직 A도 획득하지 않은 상태이므로 T1이 보유한 B를 기다리는 상황이 발생할 수 없다.
대기 그래프 기반 교착 감지
┌───────────────────────────────────────────────────────────────────────┐
│ 대기 그래프 (Wait-For Graph) │
├───────────────────────────────────────────────────────────────────────┤
│
│ [잠금 테이블 상태] │
│ 리소스 R1 (A): T1(X), T2(S) 대기 │
│ 리소스 R2 (B): T2(X), T3(S) 대기 │
│ 리소스 R3 (C): T3(X) 대기 │
│
│ [대기 그래프] │
│
│ T2 ──→ R1 ──→ T1 │
│ │ │
│ │ (T2는 R1의 잠금을 기다리며, T1은 R1을 보유) │
│ ▼ │
│ T3 ──→ R2 ──→ T2 │
│ │ │
│ ▼ │
│ (T3 ──→ R3 ──→ T3 은 Self-loop이므로 즉시 감지) │
│
│ ※ 순환이 감지되면 → Deadlock! │
│
│ 감지 주기: 1초 ~ 수십 초 (시스템 부하에 따라 다름) │
│
└───────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] 대기 그래프는 현재 잠금 대기 관계를 방향 그래프로 표현한 것이다. 각 에지는 "트랜잭션 Ti가 리소스 Rj를 기다린다"를 의미한다. 이 그래프에 순환(Cycle)이 존재하면 교착 상태가 발생한 것이다. 감지 알고리즘은 주기적으로(예: 1초마다) 대기 그래프를 분석하여 순환을 탐지한다. 그러나 감지 주기가 길어지면 교착이طول 경우 시스템 자원이 불필요하게 점유될 수 있으므로, 적절한 감지 주기 설정이 중요하다.
교착 해결 전략: Wound-Wait와 Wait-Die
| 전략 | 설명 | 특징 |
|---|---|---|
| Wait-Die | 오래된 트랜잭션이年轻的 트랜잭션을 기다림 | 年长者优先, 年轻者은 중단(ROLLBACK) |
| Wound-Wait | 오래된 트랜잭션이年轻的 트랜잭션을 선점(ROLLBACK) | 年长우선,年轻者는 대기 |
┌───────────────────────────────────────────────────────────────────────┐
│ Wound-Wait vs Wait-Die 비교 │
├───────────────────────────────────────────────────────────────────────┤
│
│ T1 (старый, timestamp=10) T2 (молодой, timestamp=20) │
│
│ Wait-Die: │
│ - T1이 Rsrc 대기 → T1 기다림 (старый이므로) │
│ - T2가 Rsrc 대기 → T2 ROLLBACK (молодой이므로) │
│
│ Wound-Wait: │
│ - T1이 Rsrc 대기 → T1 기다림 (старый이므로) │
│ - T2가 Rsrc 대기 → T2가 Wound됨 (ROLLBACK) → старый 우선 │
│
│ ※ 공통점: старый 트랜잭션이 우선 보호 │
│ ※ 차이점: молодой의 처리가 다름 (대기 vs 롤백) │
│
└───────────────────────────────────────────────────────────────────────┘
[다이어그램 해설] Wound-Wait와 Wait-Die는 교착 예방算法的代表적 예시다. 두 算法 모두 старый(타임스탬프가 작은) 트랜잭션을 보호한다는 점에서 동일하다. 차이는 молодой 트랜잭션의 처리에 있다. Wait-Die는 молодой 트랜잭션이 즉시 롤백되어 다시 시작하므로 대기 시간을 줄일 수 있지만, 롤백 overhead가 발생한다. Wound-Wait는 jovem 트랜잭션이 잠금을 보유한 채 대기가 가능하므로 불필요한 롤백을 줄이지만, старый 트랜잭션의 대기 시간이 길어질 수 있다. 일반적으로 Wound-Wait가 더 실용적이다.
섹션 요약 비유
Wound-Wait는 군대 계급과 같다. 선임(старый)이 후임(молодой)의 잠금을横取り할 수 있지만, 후임이 선임의 잠금을横取り할 수는 없다. 후임은 그냥 물러서는 것이다.
Ⅲ. 융합 비교 및 다각도 분석
비교: 감지 vs 예방
| 구분 | 교착 감지 (Detection) | 교착 예방 (Prevention) |
|---|---|---|
| 원리 | 대기 그래프의 순환을 탐지 | 순환 발생 자체를 원천 차단 |
| 오버헤드 | 주기적 그래프 분석 | 잠금 순서 규칙 부과 |
| 트레이드오프 | 롤백 overhead 적음 | 불필요한 롤백 가능 |
| 구현 난이도 | 중간 | 낮음 (순서 규칙만으로 가능) |
섹션 요약 비유
감지는 CCTV로 범죄를 탐지하는 것이고, 예방은 범죄를 시도할 수 없도록 문을 잠그는 것과 같다.
Ⅳ. 실무 적용 및 기술사적 판단
실무 시나리오
시나리오 — 동적 순서 vs 정적 순서: 시스템의 객체 수가固定되어 있으면 정적 순서(A→B→C)를 부과할 수 있지만, 동적으로 객체가 생성되는 환경에서는 해시 기반 순서로 동일 순서를 보장해야 한다. 예컨대 "객체 ID의 해시값 오름차순으로 잠금 획득" 규칙을 적용하면, 어떤 객체가 생성되더라도 항상 동일한 순서가 보장된다.
도입 체크리스트
- 기술적: 잠금 순서 규칙이 모든 코드에 일관되게 적용되었는가? 교착 감지 주기가 시스템 부하에 적절한가?
- 운영·보안적: 교착 발생 시victim으로 선택된 트랜잭션이 중요한 트랜잭션인지 모니터링하는가?
안티패턴
- 잠금 순서 불일치: 일부 모듈만 순서를 어기고 접근하면 교착 가능성을 완전히 제거할 수 없다.
- 순환 감지 미작동: 감지 알고리즘의 버그로 순환을 놓치면 시스템이 무한 대기에 빠진다.
섹션 요약 비유
잠금 순서 강제는 뷔페에서의 한 줄 서기와 같다. 한 줄을 서면 모든 사람이同一 순서로 음식을 가져가므로, 누군가 앞 사람을 기다리는 교착 상황이 발생할 수 없다.
Ⅴ. 기대효과 및 결론
정량/정성 기대효과
| 구분 | 순서 규칙 없음 | 순서 규칙 적용 | 개선 효과 |
|---|---|---|---|
| 정량 | 교착 발생: 수십 회/일 | 교착: 0회 | 교착 100% 제거 |
| 정성 | 불규칙한 대기 시간 | 예측 가능한 대기 | 운영 안정성 향상 |
섹션 요약 비유
교착 상태 관리는 신호등 설치와 같다. 신호등이 없으면 네거리에서 차들이 서로 양보하지 않아 영원히 멈춰 서 있지만, 신호등이 있으면 한 번에 한 방향씩만 진행하여 순조롭게 흐른다.
📌 관련 개념 맵 (Knowledge Graph)
| 개념 명칭 | 관계 및 시너지 설명 |
|---|---|
| 잠금 (Lock) | 교착은 잠금의 보유 및 대기로 인해 발생하며, 잠금이 없으면 교착도 없다. |
| 2PL | 2PL은 직렬 가능성은 보장하지만 교착은 보장하지 못한다. |
| 타임스탬프 | Wound-Wait와 Wait-Die에서 старший/молодой 트랜잭션을 판단하는 기준이다. |
| ** 롤백** | 교착 해결 시victim 트랜잭션이 롤백되어 처음부터 재시작한다. |
👶 어린이를 위한 3줄 비유 설명
- 교착 상태는 네 명 자녀가 서로의 장난감을 빌려야만 하는 상황과 같아서, 각자가 상대방의 장난감만 기다리면 아무도 놀지 못해요.
- 이 문제를 해결하려면"항상 번호가 작은 사람부터 먼저"와 같은 규칙을 세우면 돼요.
- 컴퓨터도 누가 먼저 어떤 것에 접근할지 순서를 정하면, 서로 물러서지 않는 교착 상황을 막을 수 있어요!