A periodic deadlock detection and resolution algorithm with a new graph model for sequential transaction processing

The authors address the deadlock problem in sequential transaction processing where the strict two-phase locking and the multiple granularity locking protocol with five lock modes are used. The scheduling policy honors lock requests in a first-in-first-out basis except for lock conversions. As a basic tool, a direct graph model called the holder/wire-transaction waited-by graph (H/W-TWBG) is introduced to capture the precise status of systems in terms of deadlock. The properties of H/W-TWBG are presented. Based on H/W-TWBG, the identification principles of the victim candidates are established in a deadlock cycle, and a periodic deadlock detection and resolution algorithm which has a reasonable time and storage complexity is preserved. One important feature of the deadlock resolution scheme is that some deadlocks can be resolved without aborting any transaction