Deadlock이란?

  • The situation when a waiting process is never again able to change state, because the resources it has requested are held by other waiting processes.
  • 즉, A라는 프로세스가 B라는 프로세스에게 필요한 resource를 안 놔주고 있어서 B가 계속 기다리는 상태에 놓여져있을 때를 의미한다.

Deadlock의 특징

  • Mutual Exclusion : 적어도 하나의 resource가 공유되지 않은 상태로 held되어야 한다. (한번에 리소스 1개에 프로세스 1개)
  • Hold and wait : 하나의 프로세스는 다른 프로세스가 잡고있는 resource를 사용하기 위해 기다리고 있어야 한다.
  • No preemption : Resource는 다른 프로세스에 의해서 선취될 수 없다. (하나가 잡으면 걔가 놔주지 않는 한 다른 방법 없음!)
  • Circular wait : 프로세스와 리소스 간에 Cycle이 있어야 한다.

Resource-Allocation Graph란?

  • Deadlock은 Directed Graph를 이용한 Resource-Allocation Graph를 활용한다면 쉽게 볼 수 있다.
  • Resource-Allocation Graph는 P, R이라는 vertex와 E라는 edge로 구성되어 있다.
  • P : 프로세스 (동그라미로 표현)
  • R : 리소스 (직사각형으로 표현)
  • P -> R : P가 R을 Acquire하려고 한다.
  • R -> P : P가 R을 use하는 중이다.

과정

  1. P가 R을 Acquire하려고 하면 P->R edge가 생긴다.
  2. P가 R을 wait하다가 잡으면 P->R edge가 R->P edge로 변하게 된다.
  3. P가 R을 release하면 R->P edge가 사라진다.

예시

사진

  • Process P1 is holding an instance of resource type R2 and is waiting for an instance of resource type R1.
  • Process P2 is holding an instance of R1 and an instance of R2 and is waiting for an instance of R3.
  • Process P3 is holding an instance of R3.

A cycle in Resource-Allocation Graph(RAG)

Resource Allocation Graph에서 Cycle이 발생하면 이것은 Deadlock의 가능성이 매우 크다고 볼 수 있다.

사진

  • 위의 사진과 같은 경우에는 P1이 잡으려고 하는 R1을 P2가 잡고 있고 P2가 잡으려고 하는 R2는 P3가 잡고 있고 P3가 잡고 있는 R2는 P1이 잡고 있다.
  • 즉, P1 -> R1 -> P2 -> R3 -> P3 -> R2 -> P1으로 Cycle이 발생했다.

이 상태는 Deadlock이 발생한 상태이다.

그렇지만 이것을 매번 Deadlock이 발생했다고 볼 수 는 없다!!

사진

위의 상태를 보면

  • P1 -> R1 -> R3 -> R2 -> P1으로 Cycle이 발생했다.
  • 그러나 P4나 P2가 relase 시켜준다면 이것은 Deadlock은 발생하지 않을 것이다.

그러므로 Cycle이 존재하더라도 Deadlock이 발생하지 않을 수도 있다.

요약

  • RAG에 Cycle이 존재하지 않는다면 Deadlock은 없다.
  • RAG에 Cycle이 있다면 Deadlock일 수도..!?
  • 그렇다면 어떻게 Cycle이 발생했을 때도 Deadlock을 검거해낼 수 있을까?

느낀점

  • RAG를 활용한다면 Deadlock의 가능성을 확인할 수 있을 것이다.
  • 문제는 Cycle이 있을 때 Deadlock을 확실히 잡을 방법이 뭔가를 고민해봐야할 것 같다.
  • 일단 힌트를 조금 얻었다!!