A Real-Time Locking Protocol

Lui Sha, Ragunathan Rajkumar, Sang Hyuk Son, Chun Hyon Chang

Research output: Contribution to journalArticle

Abstract

When a database system is used in a real-time application, the concurrency control protocol must not only satisfy the consistency of shared data but also observe the priorities of the transactions. This is because priority scheduling is a commonly used method. In this paper, we examine a prioritydriven two-phase lock protocol called the read/write priority ceiling protocol. We show that this protocol leads to freedom from mutual deadlock. In addition, a high-priority transaction can be blocked by lower priority transactions for at most the duration of a single embedded transaction. These properties can be used by schedulability analysis to guarantee that a set of periodic transactions using this protocol can always meet their deadlines. Finally, we examine the performance of this protocol for randomly arriving transactions using simulation studies.

Original languageEnglish (US)
Pages (from-to)793-800
Number of pages8
JournalIEEE Transactions on Computers
Volume40
Issue number7
DOIs
StatePublished - Jul 1991

Fingerprint

Locking
Transactions
Real-time
Network protocols
Schedulability Analysis
Concurrency control
Concurrency Control
Ceiling
Ceilings
Deadlock
Deadline
Database Systems
Scheduling
Simulation Study

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computational Theory and Mathematics

Cite this

Sha, L., Rajkumar, R., Son, S. H., & Chang, C. H. (1991). A Real-Time Locking Protocol. IEEE Transactions on Computers, 40(7), 793-800. https://doi.org/10.1109/12.83617

A Real-Time Locking Protocol. / Sha, Lui; Rajkumar, Ragunathan; Son, Sang Hyuk; Chang, Chun Hyon.

In: IEEE Transactions on Computers, Vol. 40, No. 7, 07.1991, p. 793-800.

Research output: Contribution to journalArticle

Sha, L, Rajkumar, R, Son, SH & Chang, CH 1991, 'A Real-Time Locking Protocol', IEEE Transactions on Computers, vol. 40, no. 7, pp. 793-800. https://doi.org/10.1109/12.83617
Sha, Lui ; Rajkumar, Ragunathan ; Son, Sang Hyuk ; Chang, Chun Hyon. / A Real-Time Locking Protocol. In: IEEE Transactions on Computers. 1991 ; Vol. 40, No. 7. pp. 793-800.
@article{13d83aa3d9a24d7dabc6afc62dd1a9ed,
title = "A Real-Time Locking Protocol",
abstract = "When a database system is used in a real-time application, the concurrency control protocol must not only satisfy the consistency of shared data but also observe the priorities of the transactions. This is because priority scheduling is a commonly used method. In this paper, we examine a prioritydriven two-phase lock protocol called the read/write priority ceiling protocol. We show that this protocol leads to freedom from mutual deadlock. In addition, a high-priority transaction can be blocked by lower priority transactions for at most the duration of a single embedded transaction. These properties can be used by schedulability analysis to guarantee that a set of periodic transactions using this protocol can always meet their deadlines. Finally, we examine the performance of this protocol for randomly arriving transactions using simulation studies.",
author = "Lui Sha and Ragunathan Rajkumar and Son, {Sang Hyuk} and Chang, {Chun Hyon}",
year = "1991",
month = "7",
doi = "10.1109/12.83617",
language = "English (US)",
volume = "40",
pages = "793--800",
journal = "IEEE Transactions on Computers",
issn = "0018-9340",
publisher = "IEEE Computer Society",
number = "7",

}

TY - JOUR

T1 - A Real-Time Locking Protocol

AU - Sha, Lui

AU - Rajkumar, Ragunathan

AU - Son, Sang Hyuk

AU - Chang, Chun Hyon

PY - 1991/7

Y1 - 1991/7

N2 - When a database system is used in a real-time application, the concurrency control protocol must not only satisfy the consistency of shared data but also observe the priorities of the transactions. This is because priority scheduling is a commonly used method. In this paper, we examine a prioritydriven two-phase lock protocol called the read/write priority ceiling protocol. We show that this protocol leads to freedom from mutual deadlock. In addition, a high-priority transaction can be blocked by lower priority transactions for at most the duration of a single embedded transaction. These properties can be used by schedulability analysis to guarantee that a set of periodic transactions using this protocol can always meet their deadlines. Finally, we examine the performance of this protocol for randomly arriving transactions using simulation studies.

AB - When a database system is used in a real-time application, the concurrency control protocol must not only satisfy the consistency of shared data but also observe the priorities of the transactions. This is because priority scheduling is a commonly used method. In this paper, we examine a prioritydriven two-phase lock protocol called the read/write priority ceiling protocol. We show that this protocol leads to freedom from mutual deadlock. In addition, a high-priority transaction can be blocked by lower priority transactions for at most the duration of a single embedded transaction. These properties can be used by schedulability analysis to guarantee that a set of periodic transactions using this protocol can always meet their deadlines. Finally, we examine the performance of this protocol for randomly arriving transactions using simulation studies.

UR - http://www.scopus.com/inward/record.url?scp=0026188275&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026188275&partnerID=8YFLogxK

U2 - 10.1109/12.83617

DO - 10.1109/12.83617

M3 - Article

AN - SCOPUS:0026188275

VL - 40

SP - 793

EP - 800

JO - IEEE Transactions on Computers

JF - IEEE Transactions on Computers

SN - 0018-9340

IS - 7

ER -