Deadlock 조건 및 해결방안
궁금한 점이나 오류는 댓글로 달아주시면, 답변 혹은 수정하겠습니다! “:)”
교착상태 발생 조건
- 하기 **네 가지 조건이 동시 **성립 시 교착 발생.
- 상호 배제 ; Mutual Exclusion
- At least one resource must be held in a non-shareable way.
- 점유와 대기 ; Hold and wait
- A process must be holding a resource and waiting for another.
- 비선점 ; No preemption
- Resource cannot be preempted.
- 환형대기 ; Circular wait
- A waits for B, B waits for C, C waits for A.
교착상태 해결방안
- 교착상태 해결방안
- 예방, 회피, 발견, 회복
- 예방 Prevention
- 상호배제 예방 ; 상호배제 사용하지 않음(동시액세스 허락)
- 부분할당 예방 ; 프로세스가 필요로 하는 자원을 일시에 요구/할당
- 비선점 예방 ; 자원임시 할당해제 및 원상복구(다루기가 힘듦)
- 환형대기 예방 ; 모든 자원 고유번호 지정하여 환형대기 예방
- 회피(Avoidance) - Banker’s Algorithm 은행가 알고리즘
- OS는 자원의 상태를 감시
- 프로세스는 사전에 자기 작업에서 필요한 자원의 수를 제시
- OS는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태인지 면밀하게 분석
- OS는 안전한 상태를 유지할 수 있는 요구만을 수락, 그 외의 요구는 만족될 때까지 계속 거절
- 발견 Detection
- 시스템의 상태를 감시하는 알고리즘을 통하여 교착상태를 검사하는 알고리즘
- 시스템의 자원할당 그래프로 교착상태검출 Graph reduction, cycle Detection, Knot detection
- 교착상태 발생 시 자원할당 소거
- 회복 Recovery
- Deadlock이 없어질 때까지 프로세스를 순차적으로 Kill하여 제거
- 프로세스 종료비용 최소화 ; 우선순위, 진행비용, 복귀비용 등
- 자원의 우선순위 할당 ; 희생자 선택, 복귀, 기아상태
Banker’s 알고리즘 은행가 알고리즘
- 개념
- 운영체제는 자원의 상태를 감시하고, 사용자 프로세스는 사전에 자신의 작업에서 필요한 자원의 수를 제시하는 교착상태 회피 알고리즘
- 운영체제는 안정상태를 유지할 수 있는 요구만을 수락하고 불안전 상태를 초래할 사용자의 요구는 나중에 만족될 수 있을 때까지 계속 거절하는 교착상태 회피 알고리즘
- 문제점
- 쉽게 구현할 수 있지만 추가비용이 큼
- 은행원(Banker)에게 통신하는 메시지가 너무 많아 은행원(Banker)이 Bottleneck이 될 수 있음
- 할당할 자원이 일정량 존재해야 함
- 최대 자원 요구량을 미리 알아야 함
- 프로세스들은 유한한 시간 안에 자원을 반납해야 함.