A deadlock detection and resolution algorithm for sequential transaction processing with multiple lock modes

Young Chul Parkt, Peter I Scheuermann

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

Abstract

An algorithm for deadlock detection and resolution in the sequential transaction processing is presented, where twophase locking is assumed for ensuring serializability, the lock requests obey the granularity locking protocol and each granule may be locked in one of the following lock modes: IS, IX, S, SIX and X. For each object, lock requests are honored according to a first-come-first-served basis except for lock conversions. The basic idea for the deadlock detection and resolution is in the construction of a new direct graph called a Holder/Waiter-Transaction Waited-By Graph. We establish guidelines for the identification of a victim in a deadlock cycle and propose a resolution algorithm whose time and space requirements are resonable and its solution is near optimal. In addition, our algorithm allows us to resolve some deadlocks without aborting any transaction.

Original languageEnglish (US)
Title of host publicationProceedings of the15th Annual International Computer Software and Applications Conference, CMPSAC 1991
PublisherIEEE Computer Society
Pages70-77
Number of pages8
ISBN (Electronic)0818621524
DOIs
StatePublished - Jan 1 1991
Event15th Annual International Computer Software and Applications Conference, CMPSAC 1991 - Tokyo, Japan
Duration: Sep 11 1991Sep 13 1991

Publication series

NameProceedings - International Computer Software and Applications Conference
ISSN (Print)0730-3157

Conference

Conference15th Annual International Computer Software and Applications Conference, CMPSAC 1991
CountryJapan
CityTokyo
Period9/11/919/13/91

ASJC Scopus subject areas

  • Software
  • Computer Science Applications

Cite this