When Scholten and I tried this morning to prove the correctness of the assertion made in the Note on page EWD744-2, we encountered difficulties, which were only resolved by finding a counterexample.
Obviously the six edges p, q, a, b, c, and d can not be ordered in a way with which pab, qbc, pcd, and qda are compatible. It is also easily verified that the four-process system, in which the processes claim three resources in the given orders, is deadlock-free. All by itself the cyclic path (a,b,c,d) could cause deadlock, but the shared resources p and q —even one of them would have sufficed— prevent the deadlock. The counterexample is symmetric in the four processes!
| Plataanstraat 5 5671 AL NUENEN The Netherlands |
17 October 1980 prof. dr. Edsger W.Dijkstra Burroughs Research Fellow |