2019년 3월 12일
교착상태 (Deadlock)
I. 멀티 프로세스 환경의 무한 자원대기, 교착상태
가. 교착상태(Deadlock)의 개념
 |
- 멀티 프로세스 환경에서 두 개 이상의 프로세스가 아무리 기다려도 자원을 사용할 수 없는 무한 대기 상태
나. 교착상태 발생 원인
| 원인 | 설명 |
|---|---|
| 상호배제 (Mutual Exclusion) | – 자원 배타 점유, 타 프로세스 사용 차단 |
| 점유와 대기 (Block & Wait) | – 특정 자원 할당 점유 후 다른 자원을 요구 |
| 비선점 (Non-Preemption) | – 할당된 자원의 사용이 끝날 때까지 회수 불가 |
| 환형대기 (Circular Wait) | – 프로세스 간 자원 요구가 하나의 원형 구성 |
- 교착상태는 한 시스템에서 위 4가지 조건이 동시 성립 시 발생
II. 교착상태 해결 방안
가. 교착상태 해결 방안 분류
 |
나. 교착상태 상세 해결 방안
– 교착상태 예방 (Prevention)
| 구분 | 설명 | 단점 |
|---|---|---|
| 상호배재 조건 부정 | – 공유할 수 없는 자원 사용 시 성립 | |
| 점유와 대기 조건 부정 | – 자원 요청 시 다른 자원 요청하지 않음 | – 자원 낭비, 비용 증가 – 자원 공유 불가능 |
| 비선점 조건 부정 | – 자원 할당 실패 시 점유 자원 반납 | – Starvation 발생 가능 – 자원 안전선점 불가 |
| 환형대기 조건 부정 | – 모든 프로세스에 각 자원할당 순서 부여 | – 새로운 자원 추가 시 재구성 필요 |
– 교착상태 회피 (Avoidance)
| 알고리즘 | 설명 |
|---|---|
| 자원할당 그래프 알고리즘 |  – 종류 별 자원이 한 개 → 한 개씩 요청 가능 – 자원 요청 시 예약간선은 요청간선으로 전환 |
| 은행가 알고리즘 (Banker’s Algorithm) | – OS가 자원 상태 감시, 필요 자원 수 제시 관리 – Available: 사용 가능 자원의 수 – Max: 각 프로세스 최대 요구 – Need: 프로세스 마치기 위해 남은 요구 – Allocation: 각 프로세스에 할당된 자원 수 |
– 교착상태 발견 (Detection)
 |
– 교착상태 회복 (Recovery)
① 프로세스 종료법
| 방법 | 세부 기법 | 장단점 |
|---|---|---|
| 전체 종료 | – 교착상태인 프로세스 모두 종료 | – 구현 간단/종료 따른 cost 큼 |
| 부분 종료 | – 종료 시 cost가 낮은 Process, 우선순위, 처리시간 등 선정 | – 종료 프로세스 수 작음 |
② 자원 선점법
| 절차 | 세부 기법 |
|---|---|
| 대상자원 선정 | – 자원 점유 중 Process 보유 리소스 수 등 고려 |
| Rollback | – 전체 또는 부분 rollback, 관리 지점 필요 |
| 기아방지 | – 선점 count 등 관리하여 특정 프로세스가 지속적 자원 선점 근절 보장 |
About The Author
도리
One Comment
깔끔하고 핵심적인 자료 정리에 감탄했습니다. 감사합니다.