[운영체제-김덕수교수님] 교착상태(4/5) - Deadlock avoidance

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

‏‏‎ ‎

• Safe state
  • 모든 프로세스가 정상적 종료 가능한 상태
  • Safe sequence 가 존재
    • Deadlock 상태가 되지 않을 수 있음을 보장
• Unsafe state
  • Deadlock 상태가 될 가능성이 있음
  • 반드시 발생한다는 의미는 아님

‏‏‎ ‎

가정

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

‏‏‎ ‎

가정들이 비현실적이다. 그치만 Avoidance 를 위한 알고리즘이 존재한다.

---

(출처: 위키피디아) 데이크스트라님

다익스트라 알고리즘은 최단 경로 알고리즘이 유명하긴 한데, 다른 많은 알고리즘도 만드셨다.

Dijkstra's banker's algorithm

• Deadlock avoidance 를 위한 간단한 이론적 기법
• 가정
  • 한 종류(resource type) 의 자원이 여러개(unit)
• 시스템을 항상 safe state 로 유지
• 은행가 알고리즘인데, 파산할 것 같은 채무자에게 채권을 빌려주지 않는 것과 같은 이론이다.
• 핵심은 자원을 줬다 치고 문제가 발생하지 않는 경우에만 실제로 빌려준다는 것

• 프로세스 3개, 자원의 종류는 1개이고 그 개수는 10개이다.
• cur. Alloc 의 상태를 보면
  • 1 + 5 + 2 = 8
  • 남은 자원은 2다
• 추가적인 필요 열을 보면
  • P1 -2
  • P2 - 4
  • p3 - 3
  • 순으로 필요하다.
• 남은 자원 2개를 P1 에게 주면?!
• P1 은 실행을 마치고 자원을 반납한다. 그걸 가지고 P3에게 주면 P3도 일을 마치고 5를 내놓으면 p2 에게 4를 빌려줄 수 있다.
• Safe sequence
  • P1 -> P3 -> P2

‏‏‎ ‎

• 현재 상태에서 안전 순서가 하나이상 존재하면 안전 상태임
• 프로세스들이 모두 자기 실행을 마치는 것이 존재하는 순서

추가 요청이 변경되는 경우

• 현재 할당은 8 이고, 남은 자원은 2인데 필요자원들이 4,4,5 다
• 어느 프로세스에 자원을 주더라도 마칠 수가 없다.(파산, unsafe)

현재 요청 자원이 변경되는 경우

- 자원을 주었다고 가정을 해보고 safe state가 되면 빌려주고 안되면 안빌려준다.

• P2 의 현재 요청 자원이 5에서 6으로 변경되었다고 하면(Max 는 그대로 9)
• 가지고 있는 자원이 1이고, 자원을 내주더라도 완료할 수 있는 프로세스가 없으므로, 자원을 내주기를 거절한다.

근데 만약에, P1 이 자원을 1에서 2로 요청하면?(Max는 그대로 3)

• P1 -> P3 -> P2 로 safe state 가 존재한다.

---

Habermann's algorithm

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

‏‏‎ ‎

• 현재 남은 자원이 3,3,2 이니까 P2나 P4 가 실행을 마칠 수 있다.
• 천천히 순서를 따라가 보면 safe state 가 있는 것을 확인 가능하다.

‏‏‎ ‎

결론

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

‏‏‎ ‎

‏‏‎ ‎