ch8 : Deadlock 부터 시작합니다
Deadlock 상태
프로세스가 발생 가능성이 없는 이벤트를 기다리는 경우
자원의 분류
일반적 분류
하드웨어와 소프트웨어 성능에 따라
데드락이 발생할 수도, 안 할 수도 있다
다른 분류
•
선점 가능 여부에 따른 분류
◦
선점 가능 자원
◦
선점 불가능 자원
•
할당 단위에 따른 분류
◦
Total Allocation Resources
◦
Partitioned Allocation Resoucres
•
동시 사용 가능 여부에 따른 분류
◦
Exclusive Allocation Resources
◦
Shared Allocation Resources
•
재사용 가능 여부에 따른 분류
◦
Serially Reusable Resources
◦
Consumable Resources
Deadlock이 발생 가능한 자원의 종류
•
Non-Preemptible 자원(Resources)
•
Exclusive Allocation 자원
•
Serially Reusable 자원
•
CR을 대상으로 하는 데드락 모델
chapter objectives : 목표
System Model
자원을 사용하는 단계는 세 단계
요청 단계 사용 단계 : 프로세스가 임계구역에 들어가는 단계 방출 단계
Deadlock in Multithreaded Application
데드락이 발생한 상황
Deadlock Characterization
데드락이 생기는 상황 : 4가지
자원 성격의 경우
•
Mutual Exclusion
•
Hold & Wait(Partial Allocation)
시스템 성격의 경우
•
No Preemption
•
Circular Wait
Resource Allocation Graph
1.
Request edge
•
그래프에서 엣지 표현이 P → R 인 경우
2.
Assignment edge
•
그래프에서 엣지 표현이 R → P 인 경우
데드락을 다루기 위한 방법들
3가지 모두 비현실적이긴 합니다(이상적인 경우들)
•
Prevention
◦
4개의 데드락 발생 필요조건 중 하나를 제거한다
▪
4가지 조건이란?
1. Exclusive use of Resources
2. Non-preemptible Resources
3. Hold & Wait (Paritial allocation)
4. Circular Wait
▪
데드락도 발생이 쉬운게 아닌게, 윗 4가지 중 하나라도 충족 안 하면 발생X
그럼 어떤 방식?
▪
필요 자원들을 한번에 모두 할당(Total Allocation)
▪
Circular Wait 조건 제거
→ 이 방식들은 현실적으로는 불가능하다
•
Avoidance : ch8_part2 부터 이어서 진행
◦
시스템의 상태를 계속 감시
◦
데드락 상태가 될 가능성이 있느 자원할당 요청 보류
◦
시스템을 항상 safe state로 유지
그럼 어떤 방식?
◦
프로세스 수가 고정
◦
자원의 종류와 수가 고정
◦
프로세스가 요구하는 자원 및 최대 수를 미리 알고 있다
◦
프로세스가 자원을 사용한 후 반드시 반납
→ 비현실적이다..
Avoidance 알고리즘을 작성한 사람
다익스트라 : Banker's Algorithm
Habormann's Algorithm : 다익스트라 알고리즘 확장판
•
여러 종류 자원 고려
•
다익스트라 알고리즘은 1개의 단일유닛
•
하버만 알고리즘은 n개의 유닛
•
Detection & Recovery (← 가장 현실적)
ch8_part3 끝