Dead Lock - Resource-Allocation Graph

Deadlock

semaphore는 한가지 임계 자원이 아닌 여러 임계 자원에 대한 상태를 나태낼 수 있고

아래와 같이 P0, P1가 S, Q라는 임계 자원을 동시에 접근했다고 하면,

 

첫 S와 Q는 각각 1개의 프로세스가 사용할 수 있다고 가정했을 때 P0와 첫줄의 wait함수를 호출하면 S의 count가 1에서 0으로 바뀐다.

 

이 때 만약 스케쥴러가 P1을 할당하면 Q도 마찬가지로 0으로 바뀔 것이다. 하지만 또다시 스케쥴러가 P0를 호출한다면 두번째 줄의 wait함수를 호출했을 때 Q가 0이므로 대기 상태로 들어가고 다시 P1이 실행되면 P1도 마찬가지로 S가 0이므로 대기 상태로 들어갈 것이다.

 

이렇게 두 프로세스가 어느 한쪽도 수행되지 못하는 Deadloack이 발생된다. 

 

Deadlock의 특징

• Mutual Exclusion  - 적어도 하나의 resource가 공유되지 않은 상태로 hold되어야 한다. (한번에 리소스 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와 edge로 구성되어 있는데

P : 프로세스

R : 리소스

P -> R : P가 R을 Acquire하려고 한다.

R -> P : P가 R을 use하는 중이다.

 

 

예시

P가 R을 Acquire하려고 하면 P->R edge가 추가되고,

P가 R을 wait하다가 잡으면 P->R edge가 R->P edge로 변하게 된다.

P가 R을 release하면 R->P edge가 사라진다.

A cycle in Resource-Allocation Graph(RAG)

resource Allocation Graph에서 Cycle이 발생하면 Deadlock의 가능성이 매우 큰 것인데,

위의 사진과 같은 경우에는

P1이 잡으려고 하는 R1을 P2가 잡고 있고,

P2가 잡으려고 하는 R2는 P3가 잡고 있고,

P3가 잡고 있는 R2는 P1이 잡고 있어서 cycle이 발생한다.

 

 

결과적으로 모두 요청 후에 block 되면 다시 깨워줄 프로세스가 존재하지 않아 Deadlock이 발생했다고 볼 수 있다.

그러나 cycle이 발생했다고 무조건 Deadlock이라고는 할 수 없다.

위 예시를 보면 P1 -> R1 -> R3 -> R2 -> P1으로 Cycle이 발생헀지만 P4나 P2에서 하나를 relase한다면 deadlock 은 발생하지 않는다.