Deadlock detection and resolution in a CODASYL based data management system

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.