임베디드 스터디 - 교착상태(Deadlock) 필요조건과 자원 할당 그래프

교착상태(Deadlock)란

• 두 개 이상의 프로세스가 서로 상대방이 점유한 자원을 기다리며 영원히 진행되지 못하는 상태
• 식사하는 철학자 문제: 모든 철학자가 동시에 왼쪽 포크을 집으면 → 오른쪽 포크을 서로 기다리는 순환 구조 형성 → 아무도 식사 불가

---

교착상태 4가지 필요조건

4가지 조건이 동시에 성립할 때만 데드락 발생 — 하나라도 깨지면 데드락 없음

조건	이름	의미
①	상호배제 (Mutual Exclusion)	자원은 한 번에 한 프로세스만 사용 가능
②	점유대기 (Hold and Wait)	자원을 점유한 채로 다른 자원을 기다림
③	비선점 (No Preemption)	다른 프로세스의 자원을 강제로 빼앗을 수 없음
④	환형대기 (Circular Wait)	프로세스들이 원형으로 서로의 자원을 기다림

조건 제거로 데드락 예방

제거 조건	방법	현실적 문제
점유대기	필요한 자원을 동시에 모두 할당, 아니면 아예 미할당	자원 활용률 저하
환형대기	자원에 우선순위 부여, 순서대로만 요청	자원 종류 많을 시 복잡
비선점	대기 시 보유 자원 강제 반납	데이터 손상 위험
상호배제	자원 공유 허용	본질적 배타 자원엔 불가

---

자원 할당 그래프(Resource Allocation Graph)

• 데드락을 시각적으로 표현하는 도구
• 두 종류의 간선:
  • 요청 간선: 프로세스 → 자원 (자원 요청 중)
  • 할당 간선: 자원 → 프로세스 (자원이 할당됨)

예시

P1이 R1 점유, R2 요청 / P2가 R2 점유, R1 요청

• 순환 탐색: P1 → R2 → P2 → R1 → P1
• 판정: 데드락

데드락 판별 기준

상황	판정
그래프에 순환 없음	데드락 없음
순환 있고 자원 인스턴스 1개	데드락 확정
순환 있고 자원 인스턴스 여러 개	데드락 가능성 있음