System Deadlocks

ABSTRACT

A problem of increasing importance in the design of large multiprogramming systems is the, so-called, deadlock or deadly-embrace problem. In this article we survey the work that has been done on the treatment of deadlocks from both the theoretical and practical points of view.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	DIJKSTRA, E. W. "Co-operating sequential processes." In Programming languages: NATO advanced study institute. F. GENUYS (ED.), Academic Press, London. 1968.
	2	IBM System/360 operating system, ,supervisor and data management services. Form C28-6646- 2, IBM, White Plains, N. Y., 1968.
	3	Jack B. Dennis , Earl C. Van Horn, Programming semantics for multiprogrammed computations, Communications of the ACM, v.9 n.3, p.143-155, March 1966 [doi>10.1145/365230.365252]
	4	HAVENDER. J. W. "Avoiding deadlock in multi-tasking systems." IBM Systems Journal 2 (1968), 74-84.
	5	BRAUOE, E. J. "An algorithm for the detection of system deadlocks." IBM Technical Report: TROO. 791, IBM Data Systems Division, Poughkeepsie, N. Y., 1961.
	6	COLLIER, W. W. "System deadlocks." IBM Technical Report TR-00. 1756, IBM Systems Development Division, Poughkeepsie, N.Y., 1968.
	7	REITER. A. "A resource-allocation scheme for multi-user on-line operation of a small computer." Proc. AFIPS SJCC, Vol. 30, pp. 1-7. AFIPS Press. Montvale, N. J., 1967.
	8	MURPHY, J. E. "Resource allocation with interlock detection in a multi-task system." Proc. AFIPS FJCC, Vol. 33. Pt. 2, pp. 1169- 1176. AFIPS Press, Montvale, N. J., 1968.
	9	MERIKALLIO. R. A.; AND HOLLAND, F. C. "Sinnllation design of a multi-processing system." Proc. AFIPS FJCC, Vol. 33, Pt. 2, pp. 1399-1410. AFIPS Press, Montvale, N. J., 1968.
	10	SHOSHANI, A.; AND COFFMAN, E.G. "Sequencing tasks in multi-process, multiple resource systems lo avoid deadlocks." In Proc. 11th Annual Symposium on Switching and Automata Theory, Oct. 1970. pp. 225-233.
	11	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]
	12	R. M. Needham , D. F. Hartley, Theory and practice in operating system design, Proceedings of the second symposium on Operating systems principles, October 20-22, 1969, Princeton, New Jersey [doi>10.1145/961053.961058]
	13	A. Shoshani , A. J. Bernstein, Synchronization in a parallel-accessed data base, Communications of the ACM, v.12 n.11, p.604-607, Nov. 1969 [doi>10.1145/363269.363277]
	14	SHOSHANI A.; AND COFFMAN. E. G. "Prevention, detection, and recovery from system deadlocks." In Proc. 4th Annual Princeton Conf. on Information Sciences alul Sgstems, March 1970. (See also Computer Science Lab. Technical Report No. 80, Department of Electrical Engineering. Princeton University, 1969.)
	15	Edsger W. Dijkstra, The structure of the “THE”-multiprogramming system, Communications of the ACM, v.11 n.5, p.341-346, May 1968 [doi>10.1145/363095.363143]
	16	Richard Craig Holt, On deadlock in computer systems, 1971
	17	RUSSELL, R.D. "A model of de'tdlock-free resource allocation--preliminary version." Memo CGTM #93. Department of Computer Science, Stanford University, Stanford, Calif., June 1970.
	18	HEBALKAR, PRAKASH. "Deadlock-free resource sharing in asynchronous systems." (PhD Dissertation) Electrical Engineering Department, MIT, Cambridge, Mass., Sept. 1970.