Deadlock Avoidance : 교착상태 회피기법
➡️ Deadlock의 4가지 필요 조건을 부정하는 것은 너무 심각한 자원의 낭비를 초래하니, 그대로 두자!
1. Deadlock Avoidance
✔️ 컴퓨터의 시스템 자원의 상태를 지속적으로 모니터링한다.
✔️ 항상 각 리소스를 각각의 프로세스에게 특정 순서로 할당하여 deadlock을 피하도록 만드는 "안전 상태"에 있도록 만든다.
📌 안전 상태란 무엇인가?!
안전한 상태란, 모든 프로세스들이 정상적으로 종료할 수 있는 상태를 의미한다.
안전 상태는 'safe sequence'가 존재한다.
시스템이 교착 상태에 들어가지 않는다고 보장할 수 있는 상태이다.
📌안전하지 않은 상태란 무엇인가?!
교착 상태가 무조건 발생한다는 의미는 아니다.
교착상태를 피하지 못할 수도 있는 상태이다.
2. Avoidance 알고리즘의 전제
1) 프로세스의 개수가 고정되어 있다.
2) 리소스의 종류(자원형)와 Unit(단위자원)도 고정되어 있다.
☑️ Consumable Resource 같은 경우는 리소스의 개수가 고정되어 있는 것이 아니기 때문에 Avoidance 알고리즘은 적용할 수 없다.
3) 각 프로세스가 자원을 얼마나 필요로 하는지 최대 요구량이 이미 알려져 있어야 한다.
4) 프로세스는 할당 받은 자원을 반드시 반납해야 한다.
➡️ Prevention에 비해서 자원의 낭비는 완화된 기법이지만, 각 프로세스가 자원을 얼마나 필요로 하는지 알 수 없기 때문에 비현실적이고 실제로는 사용하기 어려운 비실용적 기법이다.
3. Deadlock Avoidance 알고리즘
1) Dijkstra's 알고리즘
✔️ 이론적인 기법으로서, Resource Type이 하나뿐이라고 가정한다. Resource Type은 하나이며 Unit은 여러개 있을 수 있다. 시스템을 항상 안전 상태에 있도록 한다.
📌 Example: Safe State
✅ Max Claim : 각 프로세스별 자원의 최대 요구량
ex) P1은 최대 요구량 = 3
✅ Cur. Alloc : 현재 프로세스별 자원의 할당량
ex) P1의 할당량 = 1
전체 총 리소스 10개 중에, P1~P3에 현재 8개가 할당중이므로 남은 자원은 2개이다.
✅ Additional Need : 추가적으로 필요한 자원의 양.
Max Claim - Cur Alloc
ex) P1의 추가 필요량 = 3-1 = 2
- 남아 있는 자원 2개를 'P1'에 할당해버리면, P1은 더 이상 자원 요구하지 않고 실행이 종료된다.
종료 후 반납하면 자원이 3개 반납된다.- P3에 할당하면, P3의 추가요구는 3가지 이므로 모두 사용 후 실행 종료하고 반납한다.
- 반납된 5가지 자원 중 P2가 추가적으로 필요한 4가지를 P2에게 주면, P2도 다 사용 후 종료한다.
➡️ 즉, 각 프로세스 P1->P3->P2 순서로 자원을 줌으로써 정상 할당시킨다.
📌 Example: Unsafe State
✅ Max Claim : 각 프로세스별 자원의 최대 요구량
ex) P1은 최대 요구량 = 5
✅ Cur. Alloc : 현재 프로세스별 자원의 할당량
ex) P1의 할당량 = 1
전체 총 리소스 10개 중에, P1~P3에 현재 8개가 할당중이므로 남은 자원은 2개이다.
✅ Additional Need : 추가적으로 필요한 자원의 양.
Max Claim - Cur Alloc
ex) P1의 추가 필요량 = 5-1 = 4
- 현재 남은 자원은 2개 뿐인데, P1, P2, P3를 모두 만족시킬 수 없다. 즉, 이 상태는 Unsafe 상태다.
➡️ 즉, 다익스트라 알고리즘은 이런 식의 unsafe 상태로는 절대로 만들지 않겠다는 것이다.
📌 Scenario
✅ 현재 상태 : SAFE
Safe Sequence : P1에게 2개 주고 => P3에게 3개 주고 => P2에게 4개 주기
✅ P1이 리소스를 하나 더 요청한 경우
P1의 요청을 수용했을 때에도 계속 'Safe State'면 자원을 주고, 아니면 주지 않는다.
P1에게 주더라도 Current Alloc 상태와 Additional Need를 계산해 봤을 때, P1->P3->P4로 Safe Sequence가 존재하므로 P1의 요청을 들어준다.
✅ P2이 리소스를 하나 더 요청한 경우
P2의 요청을 수용했을 때에도 계속 'Safe State'면 자원을 주고, 아니면 주지 않는다.
P2에게 자원을 준다면 변할 Cur Alloc과 Additional Need를 계산해 본다.
이 때에는 남은 available resource unit = 1이므로, safe sequence를 찾을 수 없다. 따라서 P2의 요청을 거절하고, 남은 자원을 P2에게 주지 않고 'Sleep'시킨다.
➡️ 즉, 절대로 unsafe한 방식으로는 가지 않겠다는 것이다!
2) Habermann's 알고리즘
✔️ 다익스트라 알고리즘의 확장된 버전
Multiple Resource type과 Multiple Resource Unit이 존재한다는 가정을 한다.
항상 안전한 상태에 있도록 만든다.
📌 Scenario
✅ 가정
리소스 타입 : Ra, Rb, Rc 3가지
리소스 유닛 : Ra 10개, Rb 5개, Rc 7개
각 프로세스 자원의 최대 요구량은 위와 같다.
ex) P1에게 Ra 7개, Rb 5개, Rc 3개를 주면 P1은 종료할 수 있다.
✅ 현재 상태
5개의 프로세스에서 전체 할당된 양은 Ra, Rb, Rc 각각 7, 2, 5이므로 남은 자원은 Ra, Rb, Rc 각각 3, 3, 2이다.3, 3, 2로 종료가능한 프로세스 : P2, P4
P2에게 준다면 P2 종료 이후 남은 자원 (5, 3, 2)
만족 가능 프로세스는 P4와 P5
P4에게 준다면 P4 종료 이후 남은 자원 (7, 4, 3)
만족 가능 프로세스는 P1, P3, P5
P1에게 준다면 P1 종료 이후 남은 자원 (7, 5, 3)
P3에게 준다면 P3 종료 이후 남은 자원 (10, 5, 5)
P5에게 준다면 P5 종료 이후 남은 자원 (10, 5, 7) 전체 반납 완료!
=> 전부 다 SAFE 한 상태
✅ 현재 상태 : P2가 1, 0, 2만큼 자원을 요청했다면
할당할 경우, P2의 Current는 3, 0, 2 Additional Need는 0, 2, 0으로 바뀌고 남은 자원은 2, 3, 0이 된다.
이 경우 2, 3, 0으로 만족시킬 수 있는 것은 P2 가능
P2 정상 종료 이후 Sequence를 만들어 보면 P2 -> P4 -> P1 -> P3 -> P5 이다.
이 경우 P2의 요청을 받아들인다.
✅ 현재 상태 : P1이 0, 3, 0을 요청했다면
할당할 경우 P1의 Current는 0, 4, 0이 되고 Additional Need는 7, 1, 3이 된다. 남은 자원은 (3, 0, 2)가 된다.남은 자원 3, 0, 2로 만족시킬 수 있는 프로세스는 없다. 따라서 safe sequence가 만들어지지 못하므로, P1의 요청을 받아들일 경우 Unsafe해진다. 따라서 P1의 요청을 거절하고 P1은 sleep 상태에 가서 기다리도록 한다.
