Philip P. Macri
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.
- Dijkstra, E. W., "Cooperating sequential processes," in Programming Languages (F. Genuys, ed.) Academic Press, N. Y. 1968, (43-112).Google Scholar
- Habermann, N., "Prevention of system deadlock" Comm ACM 12, 7 (July 1969), 373-377. Google ScholarDigital Library
- Havender, J. W., "Avoiding deadlock in multi tasking systems", IBM Sys. J. 7,1 (1968), 74-87.Google ScholarDigital Library
- 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.Google Scholar
- Coffman, E. G., Jr. and P. J. Denning, Operating Systems Prentice-Hall, Inc., Englewood Cliffs, New Jersey.Google Scholar
- Chamberlain, D. et al, "A Deadlock-Free Scheme for Resource Locking in a Data-Base Environment", IBM Research Laboratory, San Jose, Cal. March 1974.Google Scholar
- 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.Google Scholar
- "CODASYL Data Description Language", Journal of Development, June 1973, U. S. Department of Commerce, National Printing Office, Washington, D. C. 1974.Google Scholar
- Holt, R. C. "On Deadlock in Computer Systems", Technical Report CSRG-6; Computer Systems Research Group; University of Toronto; January, 1971.Google Scholar
- 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.Google Scholar
- UNIVAC 1100 Series, Data Management System (DMS 1100) Data Manipulation Language Programmer Reference, UP-7908.Google Scholar
Recommendations
A Priority Based Distributed Deadlock Detection Algorithm
Deadlock handling is an important component of transaction management in a database system. In this paper, we contribute to the development of techniques for transaction management by presenting an algorithm for detecting deadlocks in a distributed ...
An optimal deadlock resolution algorithm in multidatabase systems
ICPADS '96: Proceedings of the 1996 International Conference on Parallel and Distributed SystemsIn this paper, we propose a novel deadlock resolution algorithm. In the presence of global deadlocks in a multidatabase system, this algorithm always selects an optimal set of victims for removing deadlocks. It makes use of network flow techniques, and ...
Multithreaded test synthesis for deadlock detection
OOPSLA '14Designing and implementing thread-safe multithreaded libraries can be a daunting task as developers of these libraries need to ensure that their implementations are free from concurrency bugs, including deadlocks. The usual practice involves employing ...
Comments