교착상태 #2 - Deadlock prevention, Deadlock avoidance

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이 절대 발생하지 않음

 

모든 자원을 공유 허용

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

모든 자원에 대해 선점 허용

• Non-preemptible resources 조건 제거
• 현실적으로 불가능
• 유사한 방법
  • 프로세스가 할당 받을 수 없는 자원을 요청한 경우, 기존에 가지고 있던 자원을 모두 반납하고 작업 취소
  • 이후 처음 (또는 check-point) 부터 다시 시작
  • 심각한 자원 낭비 발생 -> 비현실적

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

• Hold and wait 조건 제거
• 자원 낭비 발생
• 필요하지 않은 순간에도 가지고 있음
• 무한 대기 현상 발생 가능

Circular wait 조건 제거

• Totally allocation을 일반화 한 방법
• 자원들에게 순서를 부여
• 프로세스는 순서의 증가 방향으로만 자원 요청 가능
• 자원 낭비 발생

단점

• 심각한 자원 낭비 발생
  • Low device utilization
  • Reduced system throughput
• 비현실적

---

Deadlock Avoidance

• 시스템의 상태를 계속 감시
• 시스템이 deadlock 상태가 될 가능성이 있는 자원 할당 요청 보류
• 시스템을 항상 safe state로 유지 

Safe state

• 모든 프로세스가 정상적 종료 가능한 상태
• Safe sequence가 존재
  • Deadlock상태가 되지 않을 수 있음을 보장

Unsafe state

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

 

< 가정 >

• 프로세스의 수가 고정됨
• 자원의 종류와 수가 고정됨
• 프로세스가 요구하는 자원 및 최대 수량을 알고 있음
• 프로세스는 자원을 사용 후 반드시 반납한다
• Not practical

 

• Dijkstra’s algorithm
  • Banker’s algorithm
• Habermann’s algorithm

 

Dijkstra’s banker’s algorithm

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

 

Safe state

• 1 resource type R, 10 resource units, 3 processes
• Safe state example
• Max. Claim : 최대 자원 필요 수
• Cur.Alloc. :  현재 할당된 자원 수
• Additional Need : 추가로 필요한 자원수

Safe sequence : 프로세스들이 모두 안전하게 종료할 수 있는 순서

• 자원 10개 중 8개 할당 중
  -> 할당 가능한 자원 수 2개
• P1에 자원 2개 추가 할당 후 P1 프로세스 종료 후 자원 반납
  -> 할당 가능 자원 3개
• P3에 자원 3개 추가 할당 후 P3 프로세스 종료 후 자원 반납
  -> 할당 가능 자원 5개
• P2에 자원 4개 추가 할당 후 P2 프로세스 종료

 

 

Unsafe state 

• 1 resource type R, 10 resource units, 3 processes
• Unsafe state : safe sequence가 없는 상태 

• 반드시 교착상태는 아니지만 교착상태가 될 가능성이 있다!

 

Dijkstra’s banker’s algorithm (example)
• 1 resource type R, 10 resource units, 3 processes

• P1이 자원 하나를 요청하여 할당했다고 가정 ( state 1-1 )
  (P1의 현재 할당 자원 1 -> 2 , 추가로 필요한 자원 2 -> 1, 할당 가능한 자원 2 -> 1 )
• 그 후 safe sequence가 있다면 자원 할당 O (accept)

• P2이 자원 하나를 요청하여 할당했다고 가정 ( state 1-2 )
  (P2의 현재 할당 자원 5 -> 6 , 추가로 필요한 자원 4 -> 3, 할당 가능한 자원 2 -> 1 )
• 그 후 safe sequence가 없으므로 자원 할당 X (reject)

=> 자원 요청이 들어오면 자원을 할당 했다고 가정하고 safe sequence가 있으면 accept 없으면 reject 되는 것이 Dijkstra’s banker’s algorithm 이다.

 

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: Ra, Rb, Rc
• Number of resource units for each type: (10, 5, 7)
• 5 processes

• Max. Claim : 최대 자원 필요 수
• Cur.Alloc. :  현재 할당된 자원 수
• Additional Need : 추가로 필요한 자원수

• 전체 자원수 ( 10, 5, 7 ) - 현재 할당된 자원수 ( 7, 2, 5 ) = 가용 자원수 ( 3, 3, 2 )
• safe sequence 가 존재하므로 safe state

• P2가 (1, 0, 2) 자원 요청을 하여 자원 할당 가정 ( state 2-1 )
• 가용 자원 ( 3, 3, 2 ) -> ( 2, 3, 0 )
• safe sequence가 있으므로 safe state -> 요청 수락

• P1가 (0, 3, 0) 자원 요청을 하여 자원 할당 가정 ( state 2-2 )
• 가용 자원 ( 3, 3, 2 ) -> ( 3, 0, 2 )
• safe sequence가 없으므로 unsafe state -> 요청 거부

특징

• Daedlock의 발생을 막을 수 있음
• High overhead
  • 항상 시스템을 감시하고 있어야 한다
• Low resource utilization
  • Safe state 유지를 위해, 사용 되지 않는 자원이 존재
• Not practical
  • 가정
  • 프로세스 수, 자원 수가 고정
  • 필요한 최대 자원 수를 알고 있음

---

강의

www.youtube.com/watch?v=XMrlt3ZwfM4&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=21

www.youtube.com/watch?v=qmtOsmixfsA&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=22