DeadLock - Resource Allocation Graph

자원 할당 그래프(Resource Allocation Graph, 이하 RAG)는 각 자원들이 사용 가능한지, 할당되어 있는지,

 

또 어느 프로세스에게 할당되어 있는지 시각적으로 표현한 방향 그래프이다.

 

이러한 그래프를 통해서 현재 상황이 DeadLock상태인지 아닌지, 또 DeadLock상태라면

 

어디서 DeadLock상태가 발생되었는지 한 눈에 알아 볼수 있다.

 

RAG를 그리려면 모든 노드들의 집합인 V와 연결 상태를 나타내는 집합 E가 필요하다.

 

여기서 V의 경우에는 프로세스들의 집합인 P와 리소스의 집합인 R로 나누어 진다. 즉

 

V = P U R

P = { P1, P2, ... ,Pn }

R = { R1, R2, ... ,Rm }

E = { Pi -> Rj or Rj -> Pi }

( Pi -> Rj : Pi가 Rj를 요청, Rj -> Pi : Rj가 Pi에게 할당 )

 

 

보통 RGA에서 프로세스는 원으로 리소스는 사각형으로 많이 그린다.

 

이쯤에서 예제를 통해서 확인해 보자

 

P = { P1, P2, P3 }

R = { R1, R2, R3, R4 }

E = { P1->R1, P2->R3, R1->P2, R2->P2, R2->P1, R3->P3 }

 

위와 같은 상태일 경우의 RGA는 아래의 그림과 같다.

 

 

 

 

 

만일 위의 그림에서 E에 P3->R2 가 추가 된다면  아래의 그림과 같이 된다.

 

 

 

 

첫번째 그림 같은 경우에는 DeadLock이 발생 하지 않았지만 그 상황에서 P3가 R2를 요청함으로서

 

R2->P1->R1->P2->R2

 

R2->P1->R1->P2->R3->P3->R2

 

위와 같은 두개의 사이클이 생기게 되고 DeadLock상태에 빠지게 된다.