토픽 35 / 85·프로세스 동기화와 교착상태
데드락 탐지 및 복구 (Deadlock Detection & Recovery)
데드락 탐지 및 복구 (Deadlock Detection & Recovery)
데드락 발생을 허용하되, 주기적으로 탐지 알고리즘을 실행하여 데드락을 발견하고 복구 조치를 취하는 전략
탐지 기법
- •자원 할당 그래프(단일 인스턴스): 프로세스→자원, 자원→프로세스 간선, 사이클 존재 = 데드락
- •Wait-for 그래프: 자원 노드 제거, 프로세스→프로세스 간선만, 사이클 탐지 O(V²)
- •행렬 기반(다중 인스턴스): Available/Allocation/Request 행렬, 은행원 유사 알고리즘으로 완료 불가능한 프로세스 집합 = 데드락
탐지 주기: CPU 사용률 급락 시, 일정 간격(매분/매초), 자원 요청 실패 시
복구 전략
- •프로세스 종료: 전체 종료(확실, 비용 큼) / 하나씩 종료(비용 기준 선택, 데드락 해소까지 반복)
- •자원 선점: 데드락 프로세스에서 자원 강제 회수, 해당 프로세스 롤백(체크포인트 복원)
- •선점 대상 선택 기준: 우선순위, 실행 시간, 보유 자원 수, 완료까지 남은 시간
- •기아 방지: 동일 프로세스 반복 선점 제한(카운터)
비교
연관: 데드락, 자원 할당 그래프, 은행원 알고리즘, 롤백, 체크포인트