Deadlock Handling

Deadlock Handling

일반적으로 운영체제는 deadlock ignorance를 채택한다.

prevention, avoidance, detection은 성능적인 비용이 많이 들기 때문이다.

• deadlock preventation : deadlock을 예방함으로써 deadlock을 해결한다.
• deadlock avoidance : deadlock이 발생할 가능성은 있지만, 발생하지 않도록 자원을 운용한다.
• deadlock detection and recovery : deadlock이 발생하도록 냅두고, 발생하면 처리한다.
• deadlock ignore : deadlock이 발생해도 무시한다. 프로그래머가 deadlock이 발생하지 않도록 해야 한다.

 

---

Deadlock Prevention

deadlock을 발생하는 조건 중 하나라도 없애면 deadlock이 발생하지 않는다.

→ mutual exclusion, hold and wait, no preemption, circular wait

 

각 조건들을 깨기는 힘들기 때문에 현실적으로 preventation은 불가능하다.

 

• mutual exclusion
  
  • resource의 성질에 의해서 결정되는 것이므로 인위적으로 깰 수 없다.
  • non-sharable resource : 기본적으로 mutual exclusion을 요구함 (프린터 등)
  • sharable resource : read-only files
• hold and wait
  • 프로세스가 실행 전에 필요한 resource들을 모두 할당받은 후 실행하도록 한다.
  • 이는 프로그램 동작에 제한을 걸어야 하므로 low resource utilization을 보인다.
  • 또한 starvation을 일으킬 수 있다.
• no preemption
  • 인위적으로 강제할 수 없는 resource 고유의 성질에 의해 결정된다.
  • non-preemptive : 기본적으로 no preemption을 요구한다. (network paket 등)
• circular wait
  • hold and wait이 형성하는 사이클을 깨야 한다.
  • 그러나 concurrent한 프로세스들이 여러 개의 critical section에 진입하는 경우에 hold and wait을 깨는 것은 쉽지 않다.

 

---

Deadlock Avoidance

deadlock이 발생할 가능성이 있지만, 발생하지 않도록 자원을 운용한다.

 

priori information을 필요로 한다.

• 현재 이용 가능한 resource들
• 각 프로세스에 할당된 resource들
• 각 프로세스의 request와 release

 

가장 간단하고 유용한 모델은 각 프로세스가 필요로 하는 각 타입의 resource의 maximum number을 선언하는 것이다.

이를 이용해서 system의 state를 판단해서 safe 할 때 resource를 할당한다.

 

Safe State

state가 safe 한다는 것은 프로세스가 필요로 하는 resource를 충족시킬 수 있는 상태를 말한다.

safe sequence of processes가 존재하는 경우이다.

 

safe sequence는 프로세스가 요구하는 resource를 충족시킬 수 있는 resource allocation의 순서이다.

safe sequence가 있다면 system은 safe state에 있다.

 

state가 safe 하면 deadlock이 발생하지 않는다.

state가 unsafe 하면 deadlock이 발생할 가능성이 있다.

 

예시

12개의 resource instance가 있고, 3개의 프로세스가 있을 때 다음과 같은 상황이라고 하자.

 

이 때 safe sequence는 <P1, P0, P2> 이다.

이 순서로 자원을 할당했을 때 deadlock이 발생하지 않고 자원을 할당할 수 있다.

 

---

Deadlock Detection and Recovery

Deadlock을 허용하고, deadlock이 발생하면 복구한다.

 

system에는 detection algorithm과 recovery scheme이 있어야 한다.

• detection algorithm : system의 state가 deadlock이 발생할지를 체크하는 알고리즘
• recovery scheme : deadlock이 발생했을 때 복구하는 체계

 

Detection Algorithm

detection에는 2가지 방법이 있다.

• resource instance가 한 개인 경우
  
  • wait-for graph에서 cycle이 존재하는지 확인한다.
  • wait-for graph
    • resource allocation graph에서 프로세스만 추출 한 것이다.
    • node들은 모두 프로세스이다.
    • Pi → Pj : Pi가 Pj의 작업이 끝나기를 기다리고 있다.
      

      

• resource instance가 여러 개인 경우
  • cycle이 존재하는지 확인한다.
    • cycle이 없으면 deadlock이 발생하지 않는다.
    • cycle이 존재하면 deadlock이 발생할 수 있으므로, safe sequence가 있는지 확인한다.

 

Detection 알고리즘은 다음과 같다.

safe sequence를 찾는 방식과 같다.

 

Detection Alogrithm의 실행 시기

Detection algorithm을 실행하는 시기는 3가지로 나눌 수 있다.

각 시기마다 문제가 있기 때문에 deadlock detection도 좋은 방법은 아니다.

• 프로세스가 critical section 진입을 요청할 때 마다
  • 비용이 너무 크다.
• 주기적으로 
  • 일정 시간 내에 deadlock이 발생하면 그대로 내버려두는 문제가 있다.
  • 주기를 짧게 하더라도 그 시간 내에는 deadlock이 발생할 수 있고, 비용이 높아지는 문제가 있다.
• CPU utilization이 일정 이하로 내려갈 경우
  • CPU utilization이 떨어져도 deadlock이 아닌 경우가 대부분이다.
  • 또한 직접적으로 연관을 지을 수 없다.

 

Recovery

Deadlock이 발생했을 때 복구하는 방법은 다음과 같다.

• Process kill
  
  • 방법
    • deadlock에 연루된 모든 프로세스를 kill 한다.
    • deadlock이 발생하면 deadlock cycle이 사라질 때 까지 하나씩 프로세스를 kill 한다.
  • 문제
    • 이들은 프로그래머의 의지에 반하는 행위이다. 
    • 또한 어떤 순서로 kill 할 것인지도 고민해야 한다.
• Preemption
  
  • 방법
    • critical section에서 특정 프로세스를 쫒아내고 다른 프로세스를 진입시켜서 deadlock을 깬다.
  •  문제
    • preemption의 여부는 resource의 고유한 성질이기 때문에 항상 적용 가능하지는 않다.