7/21/2021 Laura Schmitt, Illinois CS
Two papers by Illinois CS professor Lui Sha and a paper by the late C.L. “Dave” Liu were among six publications recognized by the IEEE Computer Society's Technical Committee on Real-Time Systems.
Written by Laura Schmitt, Illinois CS
Two papers by Illinois CS professor Lui Sha and a paper by the late C.L. “Dave” Liu were among six publications recognized by the IEEE Computer Society's Technical Committee on Real-Time Systems with the 2020 Test of Time and Influential Paper Awards, which were presented at the 2021 Real-Time and Embedded Technology and Applications Symposium in May.
Sha’s 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.
In the paper, Sha and his Carnegie Mellon University (CMU) co-authors identified the priority inversion problem and proposed a solution, which they called the priority ceiling protocol. Priority inversion refers to an operating system scheduling issue, where a high-priority task is pre-empted by a lower-priority task.
Several days into the Mars mission, as the Pathfinder rover began collecting meteorological data, the spacecraft experienced several complete resets because of software scheduling problems between high-, medium-, and low-priority tasks. Specifically, the information bus thread (high priority) was blocked from executing while the meteorological data collection thread (low priority) was running—a classic example of priority inversion.
Back on Earth, JPL engineers ran the same system software on their Pathfinder model and were able to replicate the conditions that caused the reset, thus identifying the priority inversion issue.*
Sha’s second paper, “The Rate-Monotonic Scheduling Algorithm: Exact Characterization and Average-Case Behavior,” received the 2020 RTSS Influential Paper Award. Sha co-published the paper with colleagues from the Department of Statistics at CMU in 1989. In it, they proposed a necessary and sufficient scheduling test for fixed-priority pre-emptive real-time systems.
Their algorithm assigned execution priority based on how long it takes to execute the job. For example, a thread that takes only a short time to execute is assigned high priority. Rate monotonic scheduling algorithms is the only real-time computing method approved for safety-critical applications in civil aviation since the 1990s.
Throughout his career, Sha has developed a systemic approach to identifying high-impact research problems that might be solved with reasonable effort. A former member of the NASA Advisory Council, he used this method to assist NASA in selecting research programs. At Illinois, he teaches this research method to graduate students through the CS 591 LRS (formerly CS 598) course, “Improving Your Research Skills.”
Liu’s 1973 paper with James W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” was also recognized with a 2020 Real-Time Systems Test-of-Time Award.
“He pioneered scheduling analysis of real-time systems,” said Sha, noting that the paper's 12,000-plus citations is an incredibly large number. “The impact of Dave’s paper is still being felt, which means the work has stood the test of time.”
*The Pathfinder software problems were reported by Mike Jones at the Forum on Risks to the Public in Computers and Related Systems in December 1997.