[OS] 7. Deadlock - Deadlock Prevention

Deadlock 발생 필요 조건은 다음 4가지를 전부 만족시켜야한다.

• Exclusive use of resources
• Non preemptible resources
• Hold and wait (Partial allocation)
• Circular wait

이 중에서 하나라도 만족시키지 않으면 Deadlock이 발생하지 않는다. 

Deadlock을 해결하는 다음 3가지 방법이 있다. 

 

Deadlock 해결 방법

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

---

Deadlock Prevention

• 4 개의 deadlock 발생 필요 조건 중 하나를 제거
  • Exclusive use of resources
  • Non preemptible resources
  • Hold and wait (Partial allocation
  • Circular wait
• Deadlock 이 절대 발생하지 않음
• 심각한 자원 낭비 발생
  • Low device utilization
  • Reduced system throughput
• 비현실적

 

1. 모든 자원을 공유 허용

• Exclusive use of resources 조건 제거
• 현실적으로 불가능

2. 모든 자원에 대해 선점 허용

• Non preemptible resources 조건 제거 (모든 자원에 선점을 허용)
• 현실적으로 불가능 (많은 문제들이 발생함)
• 유사한 방법
  
  • 프로세스가 할당 받을 수 없는 자원을 요청한 경우 , 기존에 가지고 있던 자원을 모두 반납하고 작업 취소
  • Ex) P1이 P2이 쓰고 있는 Rj를 요청할 때 P1의 모든 자원을 반납하고 작업을 취소함
  • 이후 처음 (또는 check point) 부터 다시 시작
  • 선점 가능한 비슷한 효과를 낼 수 있다.
  • 심각한 자원 낭비 발생 -> 비현실적

3. 필요 자원 한번에 모두 할당 (Total allocation)

• Hold and wait 조건 제거
• 자원 낭비 발생 (필요하지 않은 순간에도 가지고 있음)
• (자원을 요청 할때 필요한 자원을 모두 받고 내일이 다 끝날 때 까지 반납하지 않음)
• 무한 대기 현상 발생 가능 (다른 프로세스가 해당 자원을 받으려고 계속 기다림)

4. Circular wait 조건 제거

• Totally allocation 을 일반화 한 방법
• 자원들에게 순서를 부여
• 프로세스는 순서의 자원 순서가 증가 방향으로만 자원 요청 가능
  • Ex) R1 R2 R3 R4 ... P1 P2 이있다고 가정
  • P1은 R1234 필요 P2 는 R13번이 필요하다고 가정 
  • R1:1 R2:1 R3:3 R4:2 개 있다고 가정
  • P1이 증가순서대로 R1234 요청을 순차적으로 할것임
  • P2이 자원을 요청하면 P1요청
  • P1할당 못받으니 P3도 요청할 수 없음
  • Curcle이 만들어 질 수 없다 -> dead lock이 발생하지 않음
  • 그런데 이는 자원의 낭비가 발생함. (R3는 사용할 수 있는데 R1을 사용하지 못해서 R3도 사용할 수 없음)
• 자원 낭비 발생

 

---

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

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

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

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

---