데드락(Deadlock)

데드락(Deadlock, 교착 상태)의 개념과 발생 조건,
그리고 이를 방지하거나 회피하기 위한 대표적인 전략들을 정리하였다.

---

1. 데드락(Deadlock)이란?

데드락은 둘 이상의 프로세스가 서로 상대방의 자원을 기다리며 무한 대기 상태에 빠지는 현상을 의미한다.
이는 공유 자원을 사용하는 환경에서 적절한 제어 없이 동시 접근이 발생할 경우 흔히 발생할 수 있다.

---

2. 데드락 발생 조건 (Coffman 조건)

데드락은 다음 4가지 조건이 모두 만족될 때 발생할 수 있다:

조건	설명
상호 배제 (Mutual Exclusion)	자원은 한 번에 하나의 프로세스만 사용할 수 있음
점유와 대기 (Hold and Wait)	자원을 점유한 상태에서 다른 자원을 기다림
비선점 (No Preemption)	점유한 자원을 외부에서 강제로 빼앗을 수 없음
순환 대기 (Circular Wait)	프로세스들이 원형으로 자원을 기다리는 구조가 존재함

---

3. 데드락 처리 전략

운영체제는 데드락을 다음 방식 중 하나로 대응한다:

1) 예방 (Prevention)

• 4가지 조건 중 하나 이상을 제거하여 원천적으로 데드락 발생 불가능하게 설계
• 예: 자원 요청 전에 모두 할당하도록 강제, 자원 순서를 고정하여 순환 대기 방지

2) 회피 (Avoidance)

• 데드락이 발생할 수 있는 상태로 가지 않도록 스케줄링
• 대표 알고리즘: 은행원 알고리즘(Banker's Algorithm)
  • 현재 자원 상태와 프로세스 요청을 바탕으로 안전한 상태(Safe State)만 허용

3) 발견과 회복 (Detection & Recovery)

• 데드락이 발생할 수 있음을 허용하되, 주기적으로 감지하고 회복한다
• 회복 방식: 프로세스 종료, 자원 선점 등

---

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

Dijkstra가 제안한 데드락 회피 알고리즘으로,
모든 자원 할당 요청이 시스템을 안전한 상태(Safe State)로 유지할 수 있을 경우에만 허용한다.

알고리즘 흐름:

1. 각 프로세스의 최대 자원 요청량을 사전에 알아야 함
2. 현재 할당된 자원과 가용 자원을 기준으로 시뮬레이션 수행
3. 모든 프로세스가 순차적으로 종료 가능한 경로가 존재하는 경우 → 안전한 상태

---

5. 개발자가 마주할 수 있는 데드락 사례

• 데이터베이스 트랜잭션 간 잠금(Lock) 충돌
• 두 개의 스레드가 서로의 자원을 점유하고 대기하는 상황
• 다중 스레드 환경에서의 잘못된 락 순서

해결 전략

• 락 순서 통일
• 타임아웃 기반 락 재시도
• 락 분산 또는 최소화
• Lock-free, Wait-free 알고리즘 적용

---

학습 정리

데드락은 병렬 시스템에서 자원을 공유할 때 발생할 수 있는 대표적인 문제 중 하나이며,
운영체제는 이를 예방, 회피, 감지/복구 등 다양한 전략으로 대응한다.
실제 개발 환경에서는 데이터베이스, 스레드 락, 리소스 스케줄링 등 다양한 영역에서 데드락이 발생할 수 있기 때문에,
그 원인과 구조를 이해하고 적절한 대응 방식을 설계하는 것이 중요하다.