Deadlock avoidance revisited
Toshimi Minoura · Journal of the ACM · 1982
Several new algorithms that utilize wmt-for relations mduced by processes are developed for deadlock avoidance in operating systems.One of the algorithms allows more concurrency than Havender's scheme and Habermann's algorithm; nonetheless, it can still be computed in polynomial time.Further, the deadlock,prediction problem for a set of processes using locks is reduced to a new NP-complete problem, and the deadlock-avoidanceproblemfor processes with branches is shown to be PSPACE-complete, Finally, the relative power of various algorithms is compared.