자원 할당 그래프와 교착상태

자원 할당 그래프와 교착상태

각 프로세스 별 자원할당 그래프를 통해 교착상태 발생 가능여부를 판단할 수 있습니다.
Pl, P2, P3 는 처리가 진행 중인 프로세스，Rl, R2, R3, R4는 자원이며 자원은 하나(Rl, R3) 또는 하나 이상R2，R4) 의 요소로 구성되고 할당받은 자원은 실선, 할달을 요청중인 경우 점선으로 표시하는 것으로 가정합니다. 



위 자원할당 그래프를 보면 간선의 사이클(cycle)을 포함하고 있으며, 일반적으로 사이클을 포함하는 경우 교착상태가 발생했을 확률이 높아지게 됩니다. P1 프로세스는 R2자원을 점유한 상태에서 R1 자원을 요청합니다. 그러나 R1 자원은 P2 프로세스에게 
점유되었고 P2 프로세스는 R3 자원을 요청하여 할당받기를 기다리고 있습니다. 그러나 R3 자원은 P3 자원에 할당되었고 P3 자원은 또 다시 R2 자원을 요청하여 할당받기를 기다리고 있습니다. 따라서 Pl, P2, P3 프로세스는 더 이상 진행되지 못하는 교착상태에 빠지게 됩니다.                             

만약 P3 프로세스가 R2 자원을 요청하지 않았다고 가정한다면, P3 프로세스가 R3 자원을 사용하고 반납을 합니다. 그러면 R3 자원은 P2 에게 할당될 수 있고 P2 프로세스는 진행될 수 있으므로，진행이 완료되면 R1 자원을 반납합니다. 그리고 P1 프로세
스는 R1 자원을 할당받으면 되기 때문에 기다림은 발생하지만 더 이상 진행될 수 없는 교착상태에 빠지지는 않습니다. P3 프로세스가 점유 및 대기(Hold and Wait)상태가 아니었기 때문에 교착상태가 발생하지 않은 것입니다.

마찬가지로 P2 프로세스가 R3 자원을 요청하지 않았다면 교착상태에 빠지지 않습니다.
P2 프로세스가 처리를 완료하고 R1 과 R2 자원을 반납하게 되면 P1 프로세스와 P3 프로세스가 각각 Rl, R2 자원을 할당받아 처리를 진행할 수 있기 때문입니다

위 자원할당그래프의 경우 사이클이 존재하지만 앞선 그래프와 달리 P2 프로세스와 P4 프로세스는 점유 및 대기（Hold and wait)상태가 아니기 때문에 교착상태가 발생하지 않습니다. P1 프로세스와 P3 프로세스의 경우 사이클이 존재하여 교착상태가 발생 할 수 있는 것처럼 보이지만 P2 프로세스가 진행될 수 있으므로 처리가 끝나면  R1 자원을 반납하고 P1 프로세스에게 R1 자원을 할당하면 P1 프로세스도 계속 진행될 수 있습니다. P4 프로세스의 경우에도 계속 처리될 수 있으므로 처리 후 R2 자원을 반납하면 P3 프로세스는 R2 지원을 할당받아 계속 진행이 가능하게 되어 교착상태가 발생 하지 않습니다. 위와 같은 경우 하나의 자원이 여러 개로 구성되어 있기 때문에 사이클이 존재해도 교착상태가 발생하지 않는 경우이며 자원이 하나의 구성요소로 되어 있 다면 사이클 발생 시 교착상태에 빠지게 됩니다.

첫 번째 교착상태가 발생한 그림의 경우, 하나의 자원을 여러 프로세스가 동시에 사용하지 못하므로 상호배제 조건을 만족하였고，자원을 강제로 빼앗지 못하므로 비선점조건을 만족하며, 앞서 살펴본 바와 같이 점유 및 대기 발생하였습니다. 또한 사이클이 발생하도록 자원을 환형으로 요청할 수 있는 경우이므로 환형대기의 조건까지 만족하여，교착상태 발생을 위한 4가지 조건을 모두 만족하기 때문에 교착 상태에 빠지게됩니다.

그러나 두 번째 자원할당 그래프의 경우 상호배제，비선점, 환형대기의 조건은 만족하였지만 점유 및 대기 조건을 만족하지 않았기 떄문에 교착상태에 빠지지 않는 것입니다. 마찬가지로 첫 번째 자원할당 그래프의 경우 시스템이 자원을 선점하여 필요한 프로세스에게 할당하면 되므로 나머지 3가지 조건을 만족하였다고 할지라도 비선점의 조건을 부정함으로써 교착상태를 예방할 수 있게 됩니다.

이렇게 교착상태는 필요조건 4가지를 모두 충족하는 경우 발생하므로, 이 중 하나의 조건이라도 만족하지 않도록 하여 교착상태를 예방할 수 있습니다.