Deadlock: Resource Allocation Graph

What is a Resource Allocation Graph?

Resource Allocation Graph는 어떤 프로세스에 의해 어떤 리소스가 잡혀있고, 어떤 프로세스가 특정한 타입의 리소스를 기다리고 있는지를 추적합니다. 이것은 어떻게 상호작용하는 프로세스들이 데드락에 걸리는지 설명해주는 강력하고 단순한 도구입니다.

만약 프로세스가 리소스를 사용 중이라면 화살표는 리소스 노드로부터 프로세스 노드로 연결됩니다. 만약 프로세스가 리소스를 요청하고 있으면, 프로세스 노드로부터 리소스 노드로 화살표가 연결됩니다.

만약 Resource Allocation Graph와 각각의 resource 사이에 사이클이 존재한다면, 프로세스는 deadlock입니다. 예를 들어 만약 process 1이 resource A를 사용하고, process 2가 resource B를 사용하면서 process 1은 resource B를 기다리고 process 2가 resource A를 기다린다면 process 1과 process 2는 deadlock입니다.

위 그림에서보면 P1과 P2는 R1과 R2를 각각 사용하고 있습니다. P3는 R1과 R2를 모두 기다리고 있습니다. 위 예에서는 cycle이 존재하지 않으므로 deadlock이 존재하지 않습니다.

Deadlock!

대부분의 경우 resource를 사용하는 특정한 순서를 알 수 없기 때문에 그래프를 바로 그릴 수는 없습니다.

일단 위와 같은 가능한 그림을 그려놓습니다. 그리고 나서 아래와 같이 화살표의 방향을 그려 데드락이 있는지 없는지를 확인할 수 있습니다.

위에서는 cycle이 발생해 deadlock에 걸리게 됩니다.

아래와 같은 그래프를 생각해 봅시다.

프로세스들은 파일에 독점적인 접근을 요구한다고 가정합니다. 만약 여러개의 프로세스가 동작중이고 그 프로세스들이 resource들을 요구하고 OS가 이 상태로 종료된다면 deadlock입니다.

OS가 몇몇 프로세스를 선점해  cycle을 부순다고 생각할지도 모르지만, 여전히 세 개의 프로세스가 deadlock에 걸릴 수 있습니다. 이러한 그래프 역시 make와 rule dependency에 따라 만들 수 있습니다.