Comments on prevention of system deadlocks

ABSTRACT

Habermann's method of deadlock prevention is discussed, where deadlock is defined as a system state from which resource allocations to certain processes are not possible. It is shown that the scheduler may introduce “artificial” deadlocks which Habermann's method does not prevent. Permanent blocking is the situation where certain processes never receive their resource requests. It is shown that deadlock prevention does not necessarily eliminate permanent blocking. A method of preventing permanent blocking is given.

REFERENCES

• 1: A. N. Habermann, Prevention of system deadlocks, Communications of the ACM, v.12 n.7, p.373-ff., July 1969 [doi>10.1145/363156.363160]
• 2: Richard Craig Holt, On deadlock in computer systems, 1971
• 3: IBM System/360 Operating System Supervisor and Data Management Services. IBM Form No. C28-6646.
• 4: MURPHY, J. E. Resource allocation with interlock detection in a multi-task system. Proc. AFIPS 1968 FJCC, Vol. 33, Pt. 2, AFIPS Press, Montvale, N.J., pp. 1169-1176.
• 5: HABERMANN, A.N. OD the harmonious cooperation of abstract machines. Th. Math. Dep., Technological U., Eindhbven, The Netherlands, 1967.
• 6: Donald E. Knuth, Additional comments on a problem in concurrent programming control, Communications of the ACM, v.9 n.5, p.321-322, May 1966 [doi>10.1145/355592.365595]
• 7: E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, v.8 n.9, p.569, Sept. 1965 [doi>10.1145/365559.365617]

INDEX TERMS

Keywords:
deadlock, deadly embrace, interlock, knotting, lockout, multiprogramming, resource allocation, scheduling, time-sharing