[OS] 7. Deadlock - Deadlock Avoidance

Deadlock 해결 방법

• Deadlock prevention methods (교착상태 예방)
• Deadlock avoidance method (교착상태 회피)
• Deadlock detection and deadlock recovery methods (교착상태 탐지 및 복구)

---

Deadlock Avoidance

• 시스템의 상태를 계속 감시
• 시스템이 deadlock 상태가 될 가능성이 있으면 해당 자원 할당 요청 보류
• 시스템을 항상 safe state (안전한 상태) 로 유지

 

Safe state

• 모든 프로세스가 정상적 종료 가능한 상태 (safe sequence가 존재하면 safe state이다.)
• Safe sequence 가 존재 하느냐로 판단함.
• Deadlock 상태가 되지 않을 수 있음을 보장

Unsafe state

• Deadlock 상태가 될 가능성이 있음
• 반드시 deadlock이 발생한다는 의미는 아님

 

가정 해보자

• 프로세스의 수가 고정됨
• 자원의 종류와 수가 고정됨
• 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
• 프로세스는 자원을 사용 후 반드시 반납한다
• 현실적이지 않지만...

---

Deadlock Avoidance 방법

1. Dijkstra’s algorithm (Banker’s algorithm)
2. Habermann’s algorithm

 

Dijkstra’s banker’s algorithm

• Deadlock avoidance 를 위한 간단한 이론적 기법
• 한 종류 (resource type) 의 자원이 여러 개 (unit)를 가정함.
• 시스템을 항상 safe sate 로 유지

---

• 1 resource type R, 10 resource units, 3 processes
• Safe state example

(Max.claim: 최대필요수, Cur.alloc: 현재할당 수, Additional Need: 최대필요 수)

이 알고리즘의 핵심은 누구에게 자원을 빌려줄 것인지에 대한 답을 찾는 알고리즘이다.

(가정: 다 믿을 수 있는 프로세스이고 빌려간 자원을 갚는다.) 

 

만약 셋 다 자원이 필요하다고 자원을 빌려달라고 한다면 누구에게 먼저 빌려줄 것인가?

1. 현재 자원 2개를 가지고 있다. P1에게 자원 2개를 빌려주고 (1+2) = 3자원으로 일을 하고 다시 자원 3개를 반납할 것이다.
2. 나의 현재 자원수는 3개 
3. 이후 P3에게 자원 3개를 빌려주고 P3는 (2+3) = 자원 5개로 일을 하고 자원 5개를 반납한다.
4. P2는 자원 4개를 추가적으로 필요하므로 현재 가지고 있는 자원 5개중 4개를 P2에게 빌려준다.
5. P2 은 (5+4) = 자원9개로 일을 하고 반납함. 

P1->P3->P2 순서대로 자원을 빌려주면 자신의 일을 마칠 수 있다. => Safe Sequence (=순서가 존재함)

 

 

---

• Unsafe state example

• Safe sequence를 찾을 수 없음(실행순서를 찾을 수 없음)
• 현재 가지고 있는 자원이 각 프로세스가 필요로 하는 자원보다 작게 가지고 있음..
• 반드시 교착상태는 아니지만 교착 상태가 될 수 있음.

 

Dijkstra’s banker’s algorithm (example)

뱅커 알고리즘은 프로세스를 빌려줬을 때를 가정하고 Safe sequence가 있는지 찾는다. 

P1에게 자원 1개를 빌려주었다고 가정한다 (stage - 1-1) 이렇게 되면

P1 -> P3 -> P2 순으로 자원을 빌려주고 자원을 받으면 모든 프로세스가 자원을 순차적으로 받을 수 있다.

---

반대로... 같은 상황인데 P2에 자원 1개를 주었다고 가정을 한다. 

이 상태에서  Safe sequence가 존재할까? (없다..) Unsafe sequnce이다.

즉, 자원을 해당 프로세스에게 빌려주었다고 가정했을 때 그 상태가 Unsafe sequence면 해당 요청을 거절한다. 

 

• 어떤 현재상태에서 자원 요청이 발생하면, 그 자원을 해당 프로세스에게 주었다고 가정하고
• Safe sequence가 있으면 Ok, 없으면 Reject한다.

---

Habermann’s algorithm

• Dijkstra’s algorithm 의 확장
• 여러 종류의 자원 고려
  
  • Multiple resource types
  • Multiple resource units for each resource type
• 시스템을 항상 safe sate 로 유지

 

Habermann’s algorithm (Example)

• 3 types of resources: R a , R b , R c (자원 3개)
• Number of resource units for each type: (10, 5, 7) (a,b,c)
• 5 processes

최대로 필요한 갯수

---

(Max. Claim: 최대 필요 수, Cur.Alloc: 현재 가진 수, Additional Need: 추가 필요 수)

각 자원 수 = 10, 5, 7 , 현재 가진 수 = 7, 2, 5 , 쓸수 있는 자원 수 = 3, 3, 2

• P2 -> P4 -> P1 -> P3 -> P5 순서대로 safe squence를 만들 수 있음.
• 앞서 뱅커 알고리즘의 확장형임.(뱅커는 1개의 자원 고려, HaberMan 알고리즘은 여러개 자원 고려)

---

이 상태에서는 Safe sequence를 찾을 수 있음

(남은 자원 3,3,2 중에 P2가 원하는 자원 1,0,2를 빌려주면 남은 자원 2,3,0 이 된다.

safe sequence를 찾을 수 있기 때문..)

---

P1이 0,3,0을 요청하면 현재 남은 자원은 3,0,2 가 됨.

이 상태에서는 safe state를 찾을 수 없다. 그러므로 자원을 빌려주는 것을 거절함. 

 

Deadlock Avoidance 요약

• Daedlock 의 발생을 막을 수 있음
• High overhead (항상 시스템을 감시하고 있어야 한다)
• Low resource utilization (자원 효율이 낮아짐)
  • Safe state 유지를 위해 , 사용 되지 않는 자원이 존재 (쓸 수 있는데도 못쓰는 경우가 발생함)
• Not practical (현실적이지 않음)
  • 가정...
  • 프로세스 수 , 자원 수가 고정
  • 필요한 최대 자원 수를 알고 있음

 

어떻게 문제를 해결할 수 있을까?

=> DeadLock을 허용하고 복구하면 되지 않을까?

 

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---