임베디드 스터디 - 교착상태 대처(예방/회피/탐지/복구)

교착상태 대처 전략 개요

전략	시점	핵심
예방	사전	4가지 필요조건 중 하나를 원천 차단
회피	사전	자원 할당 전 안전 상태 여부 검사
탐지	사후	주기적으로 대기 그래프 순환 탐색
복구	사후	탐지 후 프로세스 종료 또는 자원 선점

---

예방(Prevention)

• 교착상태 4가지 조건 중 하나를 제거하여 원천 차단

제거 조건	방법
상호배제	자원 공유 허용 (배타 자원엔 불가)
점유대기	필요 자원을 동시에 모두 할당, 아니면 미할당
비선점	대기 시 보유 자원 강제 반납
환형대기	자원에 우선순위 부여, 순서대로만 요청

---

회피(Avoidance) — Banker’s Algorithm

• 은행가 비유: 은행이 대출 전에 “모든 고객이 상환 가능한 순서가 존재하는가?”를 검사하듯, OS가 자원 할당 전에 안전 순서열 존재 여부를 검사
• 안전 상태: 모든 프로세스가 최대 요구량을 충족하며 완료될 수 있는 안전 순서열이 존재하는 상태
• 불안전 상태: 안전 순서열이 존재하지 않는 상태 → 데드락 가능성 있음 (확정 아님)

안전 순서열 탐색 절차

① 가용 자원으로 추가 필요량을 충족할 수 있는 프로세스 탐색
② 해당 프로세스 실행 완료 → 할당 자원 전량 반납 → 가용 자원 증가
③ ①~② 반복 → 모든 프로세스 완료 가능 → 안전 상태
④ 중간에 막힘 → 불안전 상태 → 자원 할당 거절

안전/불안전/데드락 관계

안전 상태    → 데드락 없음
불안전 상태  → 데드락 가능성 있음
데드락       → 불안전 상태의 부분집합

---

탐지(Detection)

• 데드락 발생을 허용하되 주기적으로 탐지
• 대기 그래프(Wait-for Graph): 자원 할당 그래프에서 자원 노드를 제거하고 프로세스 간 대기 관계만 남긴 그래프

자원 할당 그래프:  P1 → R1 → P2 → R2 → P1
대기 그래프:       P1 → P2 → P1  ← 순환 = 데드락

• 순환이 존재하면 → 데드락 상태로 판정

---

복구(Recovery)

탐지 후 두 가지 방법으로 해소:

방법	설명	단점
프로세스 종료	데드락 프로세스를 전부 또는 하나씩 종료	작업 전체 손실
자원 선점	프로세스 종료 없이 자원만 강제 회수, 빼앗긴 프로세스는 롤백	구현 복잡