교착상태(Deadlock)

교착상태(Deadlock)란?

둘(또는 그 이상)의 프로세스/스레드가 서로가 가진 자원을 기다리며 영원히 진행되지 못하는 상태.
자원 예: 락/뮤텍스, 파일·디바이스, 메모리/버퍼, 세마포어, 소켓 등.

---

발생 4조건 (Coffman Conditions)

네 가지 모두 만족해야 교착이 발생할 수 있음.

1. 상호배제(Mutual Exclusion)
   • 어떤 자원은 한 시점에 한 프로세스만 사용 가능(비공유 자원).
2. 점유와 대기(Hold & Wait)
   • 이미 자원을 보유한 상태에서 추가 자원을 요청하며 대기.
3. 비선점(Non-preemption)
   • 점유 중인 자원을 강제로 빼앗을 수 없음. (소유자가 자발적으로 반납해야 함)
4. 환형대기(Circular Wait)
   • 프로세스들이 원형으로 서로의 자원을 기다림.
   • 예: P1→(R2대기), P2→(R3대기), …, Pn→(R1대기)

---

간단 예시 (두 락 교차 획득)

Thread A: lock(L1) → lock(L2) 대기
Thread B: lock(L2) → lock(L1) 대기

• A는 L1 보유, L2가 필요 / B는 L2 보유, L1이 필요
• 네 조건 모두 충족 → 교착상태

---

대처 전략

1) 예방(Prevention) – 4조건 중 최소 하나를 원천 차단

• 상호배제 완화: 가능하면 자원을 공유 가능(락 대신 원자적 연산/락프리 자료구조).
• 점유와 대기 차단: 자원 한 번에 모두 요청(all-or-nothing), 또는 보유 자원 반납 후 재요청.
• 비선점 허용: 선점 가능하도록 설계(예: 락 타임아웃 후 보유 자원 반납).
• 환형대기 차단: 자원에 전역 순서 부여(작은 번호→큰 번호 순서로만 획득).

2) 회피(Avoidance) – 안전 여부를 미리 판단해 위험한 요청 거절

• 대표: 은행가 알고리즘(Banker’s Algorithm)
  • 시스템이 안전 상태(safe state)를 유지할 수 있을 때만 자원 할당.
  • 장점: 교착 회피, 단점: 최대 요구량 파악 필요·오버헤드.

3) 탐지 및 복구(Detection & Recovery) – 일단 허용, 주기적으로 그래프 분석 후 복구

• 자원 할당 그래프(Resource Allocation Graph, RAG)에서 사이클 탐지.
• 사이클 발견 시 복구:
  • 프로세스 강제 종료 또는 롤백(트랜잭션),
  • 자원 선점(가능한 자원만),
  • 우선순위/가중치로 희생자 선택(작업량/진행도/재시작 비용 고려).