Deadlock

Deadlock

concurrent하게 실행되는 프로세스가 있을 때, 그 프로세스들이 progress를 만들지 못하고 영원히 정지되는 현상을 말한다.

 

다음과 같은 상황은 deadlock에 빠질 수 있다.

 

Deadlock의 조건

Deadlock이 발생하기 위해서는 아래 4가지 조건이 충족되어야 한다.

역은 성립하지 않는다.

즉, 아래 4가지 조건이 충족되어도 무조건 deadlock은 아니다.

• mutual exclusion
  • critical section에 오직 하나의 프로세스만 들어갈 수 있다.
• hold and wait
  • 어떤 프로세스가 이미 critical section에 들어가있고, 다른 critical section에도 들어가기 위해서 기다린다.
  • 다른 프로세스에서 이미 들어가있는 critical section에 들어가기 위해서 기다린다.
• no preemption
  • 어떤 프로세스가 critical secton에 들어가있는데 다른 프로세스가 그걸 쫒아낼 수 없다.
  • 해당 프로세스의 작업이 완료되어야만 다른 프로세스에서 critical section에 들어갈 수 있다.
• circular wait
  • hold and wait의 강화된 조건이다.
  • hold and wait이 사이클을 형성한다.

 

---

Resource-Allocation Graph

Deadlock 문제를 잘 표현하는 그래프이다.

• node
  • process와 resource를 표현한다.
  • process는 원으로 표현한다.
  • resource는 네모로 표현한다.
  • n개의 instance가 있는 resource라면 큰 네모 안에 n개의 작은 사각형을 그려서 표현한다.
• edge
  • request edge : process가 resource를 요청하는 것을 표현한다.
  • assignment edge : resource가 process에 할당되는 것을 표현한다.

 

 

Resource-Allocation Graph and Deadlock

아래에서 왼쪽 그래프는 사이클을 형성하므로 deadlock이 발생된다.

그러나 오른쪽 그림은 P2가 작업이 끝날 경우 사이클이 깨지기 때문에 deadlock이 발생하지 않는다.