운영체제 7. 교착 상태 Deadlock (4) - Deadlock avoidance

출처 : https://www.youtube.com/watch?v=qmtOsmixfsA&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=22

 

 

 

Deadlock Avoidance

 

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

 

 

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

 

 

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

 

 

• Dijkstra's algorithm
  • Banker's algorithm : 수많은 다익스트라 알고리즘 중에 Deadlock avoidance를 해결한 알고리즘
• Habermann's algorithm

 

 

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

 

 

• State 1 - Safe state example
  • 1 개의 리소스 타입, 10개의 리소스 유닛, 3개의 프로세스가 존재. 즉, R이 10개, P1~P3이 존재
  • Max. Claim : 최대로 필요한 리소스 수
  • Cur. Alloc : 현재 할당된 리소스 수
  • Additional Need : 앞으로 최대로 필요한 리소스 수 (Max. Claim - Cur. Alloc)

자원이 10개가 있는 상황에서 P1이 1개, P2가 5개, P3가 2개를 가지고 있다.

그러면 총 2개의 자원이 남은 상황에서 P1이 2개, P2가 4개, P3가 3개의 자원을 추가로 요구하고 있다.

그렇다면 어떤 순으로 자원을 할당해줘야 할까?

 

 

먼저 P1에게 자원 2개를 할당해주면, P1이 작업을 마치고 3개의 자원을 반환할 것이다. 그러면 P3에게 자원 3개를 할당해주고 5개의 자원을 반납하고, P2에게 4개의 자원을 할당하고 9개의 자원을 반납하게 될 것이다.

 

이렇게 현재 상태에서 프로세스들이 모두 자신의 작업을 마칠 수 있는 안전 순서(safe sequence)가 하나 이상 존재하면 안전 상태(safe state)이다.

 

• State 2 - Unsafe state example
  • resource type R이 10개, 프로세스가 3개 존재함

현재 남은 리소스 R이 2개가 있는데 어느 하나의 프로세스도 만족을 시켜줄 수 없다. 이렇게 safe sequence가 존재하지 않는 상태를 Unsafe state라고 한다.

 

물론 프로세스가 작업을 추가로 받지 않고 작업을 끝내버릴 수도 있기 때문에 반드시 deadlock 상태를 야기하는 것은 아니다. 하지만 모든 프로세스들이 모두 2개 이상의 자원을 요구해서 deadlock을 발생시킬 수 있는 가능성이 있는 상태가 바로 Unsafe state 이다.

 

• Dijkstra's banker's algorithm (example)
  • R 10개, 프로세스 3개가 있다고 가정
  • P1이 1개, P2가 5개, P3가 2개의 자원을 할당받아서 남은 자원은 2개가 존재함
• P1이 자원 1개를 요청했다. P1에게 자원 1개를 더 할당해주었을 때, Safe sequence를 찾을 수 있는지를 검토한다. 만약 Safe sequence를 찾을 수 있다면 할당해준다.

 

 

• P2가 자원을 1개 요청했다. P2에게 자원 1개를 더 할당해주었을 때, 만약 Safe sequence가 존재하지 않는다면(Unsafe state가 된다면) 해당 요청을 거절한다.

 

즉, banker's algorithm이란 자원을 요청받았을 때, 그 자원을 할당해줬다고 가정해보고 safe sequence가 존재하는 지를 검토한 다음, safe sequence가 존재하면 할당해주고, 존재하지 않는다면 거절해주는 알고리즘이다.

 

 

• Habermann's algorithm
  • 다익스트라 알고리즘의 확장
  • 여러 종류의 자원이 있는 상황을 고려
    • Multiple resource types
    • Multiple resource units for each resource type
  • 시스템을 항상 safe state로 유지. banker's algorithm과 아이디어 자체는 동일함

 

 

• Habermann's algorithm example
  • 리소스 타입은 3 종류가 존재함 : Ra, Rb, Rc
  • 각 타입당 리소스 수는 Ra : 10개, Rb : 5개, Rc : 7개가 존재함
  • 프로세스는 P1~P5로 5개가 존재함

 

 

• 이용 가능한 자원의 수는 각각 Ra : 3개, Rb : 3개, Rc : 2개가 남아있다.
• P2 -> P4 -> P1 -> P3 -> P5 순으로 자원을 할당해주면 모든 프로세스가 작업을 완료할 수 있다.
• 즉, safe sequence가 존재하므로 safe state이다.
• Banker's algorithm과 방식은 동일하고 자원의 종류의 수만 늘어났다.

 

 

• 만약 P2가 Ra 1개, Rb 0개, Rc 2개를 요청한다고 해보자. 그러면 P2가 가진 자원은 (2, 0, 0) -> (3, 0, 2)가 되고 남은 자원은 (2, 3, 0)이 된다.
• 이 상태에서 만약 P2에게 추가로 Rb 2개를 할당해줘서 P2의 작업을 끝마친 뒤 자원을 회수하고 P4 -> P1 -> P3 -> P5 에게 자원을 할당하면 모든 프로세스의 요구를 충족시켜줄 수 있다.
• 즉, safe sequence가 존재하는 safe state 이므로 해당 요청을 승인하고 자원을 할당해준다.

 

 

• 이번에는 다시 state 2에서 P1이 (0, 3, 0)의 자원을 요청했다고 해보자. 그러면 P1에게 할당된 자원은 (0, 1, 0) -> (0, 4, 0)이 되고, 남은 자원은 (3, 3, 2) -> (3, 0, 2)가 될 것이다.
• 이 경우 그 어떤 프로세스에게 남은 자원을 할당해줘도 safe sequence가 존재하지 않는다. 즉 Unsafe state가 되므로 요청을 승인해주지 않는다.

 

 

Deadlock Avoidance

 

• 시스템을 항상 safe state로 유지시켜줌으로써, Deadlock의 발생을 막을 수 있음
• High overhead
  • 항상 시스템을 감시하고 있어야하므로 오버헤드가 크다.
• Low resource utilization
  • Safe state 유지를 위해, 사용되지 않는 자원이 존재
  • Additional Need는 필요할 수도 있는 자원이지 반드시 필요한 자원은 아니다. 그렇지만 safe state를 유지하기 위해서 남은 자원을 할당해주지 않고 가지고 있어야 한다. 즉, 자원의 효용성이 떨어지게 된다.
• Not practical (비현실적이다.)
  • 가정
    • 프로세스 수, 자원 수가 고정
    • 필요한 최대 자원 수를 알고 있음