Deadlock detection and resolution in a CODASYL based data management system

ABSTRACT

In a multi-task computer system many different types of situations may occur in which productive computation may be brought to a standstill. One of these is deadlock or "deadly embrace". Some of the earliest investigation into this problem was undertaken by Dijkstra [1], Habermann [2] and Havender [3]. A detailed presentation of the deadlock problem and its ramifications may be found in [1, 2, 3, 4, 5].Because deadlock is so costly, modern computer system software is designed so that deadlock is either impossible [6, 7] or the probability of its occurrence is minimized at the system level. For example, the INGRES data base management system [7] accomplishes deadlock prevention without compromising data base integrity. Unfortunately, the CODASYL design [8] does not preclude the possibility of deadlock. It leaves the burden of minimizing the probability of its occurrence to the design of the application. There are two parts to the application design: the database design and the software design. Judicious design of both parts can sometimes minimize deadlock. However, deadlock cannot be prevented in all cases. Therefore, deadlock detection and resolution mechanisms are essential for operation in a multi-thread environment. Initially, the CODASYL based data management system employed (DMS 1100 [11]) had very simple deadlock detection and resolution mechanisms. The deadlock detection mechanism was based on the sufficient condition that deadlock exists when the number of transactions registered with the data management system equals the number of transactions locked out of resources. A least number of page alterations criterion was used by the deadlock resolution mechanism to resolve deadlock. That is, the transaction with the least number of altered pages was rolled back in an attempt to resolve deadlock. If this failed to resolve deadlock, the roll back selection process was repeated until deadlock was resolved. It was discovered that these mechanisms seriously degraded throughput on our system and a new approach was needed. This paper contains a description of the deadlock detection algorithm and the deadlock resolution algorithm which was implemented to overcome this defficiency. The former detects deadlock and the latter resolves deadlock in a manner consistent with maximum system throughput.In order to establish a common framework for discussion, the concepts of lock out and deadlock will be defined before proceeding.

REFERENCES

• 1: Dijkstra, E. W., "Cooperating sequential processes," in Programming Languages (F. Genuys, ed.) Academic Press, N. Y. 1968, (43-112).
• 2: 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]
• 3: Havender, J. W., "Avoiding deadlock in multi tasking systems", IBM Sys. J. 7,1 (1968), 74-87.
• 4: Shoshiani, A. and E. G. Coffman, Jr., "Sequencing tasks in multi-process, multiple resource systems to avoid deadlocks". Proc. 11th Symp. Annual Switching and Automatic Theory (Oct 1970), 225-233.
• 5: Coffman, E. G., Jr. and P. J. Denning, Operating Systems Prentice-Hall, Inc., Englewood Cliffs, New Jersey.
• 6: Chamberlain, D. et al, "A Deadlock-Free Scheme for Resource Locking in a Data-Base Environment", IBM Research Laboratory, San Jose, Cal. March 1974.
• 7: Stonebraker, M. "High Level Integrity Assurance in Relational Data Base Management Systems" Memorandum No. ERL-M473 August 16, 1974, Electronics Research Laboratories, College of Engineering, University of California, Berkely.
• 8: "CODASYL Data Description Language", Journal of Development, June 1973, U. S. Department of Commerce, National Printing Office, Washington, D. C. 1974.
• 9: Holt, R. C. "On Deadlock in Computer Systems", Technical Report CSRG-6; Computer Systems Research Group; University of Toronto; January, 1971.
• 10: King, P. F. and A. J. Collmeyer "Database sharing - An efficient mechanism for supporting concurrent processes" pgs 271, 275, Proceedings of the National Computer Conference, 1973, Chicago.
• 11: UNIVAC 1100 Series, Data Management System (DMS 1100) Data Manipulation Language Programmer Reference, UP-7908.