Priority Inheritance Protocols: An Approach to Real-Time Synchronization

Lui Sha, Ragunathan Rajkumar, John P. Lehoczky

Research output: Contribution to journalArticlepeer-review


A direct application of commonly used synchronization primitives such as semaphores, monitors, or the Ada rendezvous can lead to uncontrolled priority inversion, a situation in which a higher priority job is blocked by lower priority jobs for an indefinite period of time. In this paper, we investigate two protocols belonging to the class of priority inheritance protocols, called the basic priority inheritance protocol and the priority ceiling protocol. We show that both protocols solve this uncontrolled priority inversion problem. In particular, the priority ceiling protocol reduces the worst case task blocking time to at most the duration of execution of a single critical section of a lower priority task. In addition, this protocol prevents the formation of deadlocks. We also derive a set of sufficient conditions under which a set of periodic tasks using this protocol is schedulable.

Original languageEnglish (US)
Pages (from-to)1175-1185
Number of pages11
JournalIEEE Transactions on Computers
Issue number9
StatePublished - Sep 1990
Externally publishedYes


  • Priority inheritance
  • priority inversion
  • realtime systems
  • scheduling
  • synchronization

ASJC Scopus subject areas

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


Dive into the research topics of 'Priority Inheritance Protocols: An Approach to Real-Time Synchronization'. Together they form a unique fingerprint.

Cite this