2020-11-20 운영체제 기초(10) 데드락방지

데드락의 처리방법

  • Deadlock Prevention(방지) : 자원할당시 데드락 4가지 필요조건 중 어느 하나가 만족하지 않도록 한다. => 방지하는 방법은 오버헤드가 크기때문에 지금 사용하지는 않는다.
  • Deadlock Avoidance :
    • 자원요청에 대한 부가정보를 활용하여 데드락의 가능성이 없는 경우에만 자원을 할당
    • 시스템 상태가 원래 상태로 돌아갈 수 있는 경우에만 자원을 할당
  • Deadlock Detection and recovery : 데드락 발생은 허용하되 그에 대한 detectin 루틴을 만들어서 데드락 발생시 recover
  • Deadlock Ignoreance : 데드락을 시스템이 책임지지 않는다. => Unix를 포함한 대부분의 OS가 채택

Deadlock Prevention

  • Mutual Exclusion : 공유해서 안되는 자원의 경우 반드시 성립
  • Hold and Wait : 프로스세가 자원을 요청할때 다른 어떤 자원도 가지고 있으면 안된다.
    • 방법1 프로세스 시작 시 모든 필요한 자원을 할당받게 한다.
    • 방법2 자원이 필요한ㄹ 경우 보유 자원을 모두 놓고 다시 요청
  • No Preemption
    • 프로세스가 어떤 자원을 기다려야하는 경우 이미 보유한 자원이 선점된다.
    • 모든 필요한 자원을 얻을 수 있을 때 그 프로세스는 다시 시작된다.
    • State를 쉽게 저장하고 restore할 수 있는 자원에서 주로 사용(CPU, 메모리)
  • Circular Wait : 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 할당.
  • 문제 : 활용저하, 처리량감소, starvation문제

Deadlock Avoidance

  • Prevention과 마찬가지로 데드락을 미리 방지.
  • 자원 요청에 대한 부가정보를 활용하여 자우너 할당이 데드락으로부터 안전한지를 동적으로 조사해서 안전한 경우에만 할당
  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각자원별 최대 사용량을 미리 선언하도록 하는 방법이다.
  • safe state : 시스템 내의 프로세스들에 대한 safe Sequence가 존재하는 상태
  • 시스템이 safe state가 있으면 no deadlock
  • 시스템이 unsafe state에 있으면 데드락 가능성이 있다.
  • Deadlock Avoidance는 시스템이 unsafe state에 들어가지 않는 것을 보장한다.
  • 구체적으로 Resouce Allocation Graph alogorithm과 Banker’s Algorithm을 사용한다.

  • 점선 : 해당프로세스가 점선이 가리키는 자원을 쓸 가능성이 있다. 프로세스가 해당 자원을 사용하면 점선이 실선으로 변한다.
  • 프로세스가 자원을 요청했을때, 가능하더라도 데드락이 발생할 가능성이 존재하면 바로 자원을 주지않는다. 데드락을 방지하는 방향으로 흘러간다.
  • 자원당 인스턴스가 여러개면 Banker’s Algorithm을 사용한다.

  • 뱅커스 알고리즘은 프로세스마다 최대로 사용하는 자원의 수를 명시한다.

Deadlock Detection and recovery

  • 데드락이 빈번이 발생하지 않기때문에 데드락이 발생하면 recovery한다.
  • 데드락 탐지
    • 자원이 1개인 경우 자원할당 그래프를 활용하여 데드락인지 확인
    • 자원이 여러개인 경우 뱅커스알고리즘을 활용
  • Wait-for graph 알고리즘
  • Recovery
    • Process termination
      • 데드락에 연관된 프로세스를 모두 다 kill
      • 데드락에 연관된 프로세스를 데드락이 사라질때까지 1개씩 kill해본다.
    • Resource Preemption : 데드락에 연관된 프로세스들로부터 자원을 뺏는다.
      • 비용을 최소화할 victim선정
      • safe state로 rollback하여 process를 재시작
      • starvation문제 : 동일한 프로세스가 계속해서 victim으로 선정되는 경우

Deadlock Ignorance

  • 데드락이 일어나지 않는다고 가정하고 아무런 행동을 취하지 않는다.
  • 데드락이 드물게 발생해서 데드락에 대한 조치가 오버헤드가 더 클수있다.
  • 시스템이 비정상적으로 작동하면 사람이 직접 프로세스를 죽인다.
  • Unix, Window 등 대부분의 OS가 채택한다.

Reference

  • https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/images/Chapter7/7_07_DeadlockAvoidance.jpg
  • https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/images/Chapter7/7_IllustrativeExample.jpg
Written on November 20, 2020