먼저 데드락이란 여러 프로세스들이 한정된 자원을 사용하기 위해서 서로 경쟁하는 과정에서 각각의 프로세스가 자원을 점유한 상태에서 다른 프로세스가 점유한 자원을 기다리면서 블록된 상태를 의미합니다. 일반적으로 데드락이 발행하기 위해서는 상호배제, 비선점, 점유대기, 순환대기 조건을 모두 만족해야 하는데 이 중에서 데드락이 발생했는지 알기 위해서 사용될 수 있는 조건은 순환대기 입니다.
데드락의 유무를 확인하기 위해서는 자원 할당 그래프라는 프로세스들과 자원들 사이의 관계를 도식화한 그래프를 활용할 수 있는데 이 때 그래프에서 사이클이 존재하는지 여부에 따라서 데드락이 발생하는지 여부를 확인할 수 있습니다. 먼저 그래프에 사이클이 존재하지 않는다면 데드락이 존재하지 않다고 판단할 수 있지만 그래프에 사이클이 존재한다고 해서 반드시 데드락이 존재하는 것은 아니며 데드락이 존재할 가능성을 가지고 있다는 것으로 해석할 수 있습니다.
그래프에서의 사이클은 말 그대로 가능성만을 의미하기 때문에 해당 사이클에서 데드락이 발생하는지 여부를 따져보아야 합니다. 만약 그래프에 사이클이 존재하면서 사이클을 이루는 자원들의 인스턴스가 하나만 존재하는 경우라면 데드락을 발생시키지 않고 문제를 해결할 수 있는 방법이 존재하지 않기 때문에 데드락이 발생한다고 판단할 수 있습니다. 반면에 사이클을 이루는 자원들의 인스턴스가 여러개인 경우에는 단순히 자원할당 그래프만 보고 이를 판단할 수 없기 때문에 은행원 알고리즘과 같은 별도의 알고리즘을 통해 해당 사이클이 데드락을 발생시키는지 아닌지 판단할 수 있습니다.