IEEE Technical Committee on Real-Time Systems Test of Time and Influential Paper Awards

Lui Sha was among six publications recognized by the IEEE Technical Committee on Real-Time Systems with the 2020 Test of Time and Influential Paper Awards. His landmark 1990 paper, “Priority Inheritance Protocols: An Approach to Real-Time Synchronization,” was one of four papers recognized with a 2020 Real-Time Systems Test-of-Time Award. The paper introduced the now-standard methods for controlling priority inversion on uniprocessors. Seven years after it was published, this work played a critical role in the Mars Pathfinder mission.

References

1990

Priority Inheritance Protocols: An Approach to Real-Time Synchronization

L. Sha, R. Rajkumar, and J.P. Lehoczky

IEEE Transactions on Computers, 1990

Abs Bib

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. © 1990 IEEE
@article{Sha19901175, author = {Sha, L. and Rajkumar, R. and Lehoczky, J.P.}, title = {Priority Inheritance Protocols: An Approach to Real-Time Synchronization}, journal = {IEEE Transactions on Computers}, year = {1990}, volume = {39}, number = {9}, pages = {1175-1185}, doi = {10.1109/12.57058}, url = {https://www.scopus.com/inward/record.uri?eid=2-s2.0-0025488794&doi=10.1109%2f12.57058&partnerID=40&md5=2bd374a5b97172776cd2b203fb142b86}, author_keywords = {Priority inheritance; priority inversion; realtime systems; scheduling; synchronization}, keywords = {Computer Operating Systems - Design, Protocols; Real Time Systems; Synchronization, Computer Systems, Digital}, document_type = {Article}, source = {Scopus}, }