데드락

• 교착상태, 이미 답이 없는 상황이라 상황을 조정하기 위해서 오버헤드가 크다.
• 데드락 : 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태.
• 자원 : 하드웨어, 소프트웨어, I/O Device, CPU Cycle, Memory Space…
  • 프로세스가 자원을 사용하는 절차 : Request, Allocate, Use, Release
• 예시 : P0이 자원 A를가지고 B를 요청, P1는 B를 가지고, A를 요청. => Circular wait

데드락 발생 4가지 조건

• 아래 4가지 조건을 모두 만족해야 데드락이 발생한다.
• Mutual Exclusion(상호배제) : 매 순간 하나의 프로세스만이 자원을 사용할 수 있다.
• No premmption(비선점) : 프로세스는 자원을 스스로 내어놓을 뿐이고 빼앗기지 않는다.

• Hold and Wait(보유대기) : 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유자원을 놓지 않고 계속 가지고 있다.

• Circular wait(순환대기) : 자원을 기다리는 프로세스간 사이클이 형성되어야한다.

자원할당그래프

• 자원 할당 그래프
• 그래프에 cycle이 없으면 데드락이 아니다. => 그림1
• 그래프에 cycle이 존재할때
  • 자원당 인스턴스가 1개만 존재하면 데드락 => 그림2는 R2가 2개인스턴스임에도 불구하고, 사이클이 2개라서 데드락이다.
  • 자원이 여러개의 인스턴스가 여러개면 데드락일수도 있고, 아닐수도 있다. => **그림3에 사이클이 존재하지만, 자원이 2개씩 존재하고 P2, P4의 자원반납이 이루어지면 P1, P3가 R1, R2를 할당받을 수 있기때문에 데드락이 아니다.

Reference

• https://zoomkoding.github.io/os/2019/05/27/deadlock-1.html => Resouce Allocation Graph
• https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/images/Chapter7/7_07_DeadlockAvoidance.jpg => Resource Allocation Graph Algorithm