A scalable deadlock avoidance policy for batch processes

Allocating non-sharable resources for jobs in batch processes can lead to deadlocks. Using colored digraphs to model the wait-relationship between resources in a job-path, a graph-theoretic approach is proposed to give necessary conditions for the existence of unsafe system states, i.e., allocations that will prevent some jobs from successful execution. Based on these necessary conditions a correct and scalable control policy for deadlock avoidance is given, which is somewhat conservative and allows some trade-off between computational complexity and permissiveness