Three Articles with Illinois CS Ties Recognized by IEEE TCRTS for Timeless and Influential Contributions to Real-Time Systems | Computing
Two articles by Professor Lui Sha of Illinois CS and one article by the late CL “Dave” Liu were among six publications recognized by the IEEE 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 Technologies and Applications Symposium in May.
Sha’s flagship article in 1990, “Priority Inheritance Protocols: A Real-Time Synchronization Approach,” was one of four papers awarded a 2020 Real-Time Systems Time Testing Award. The document presented the now standard methods for controlling priority inversion on single processors. Seven years after its publication, this work played a vital role in the Mars Pathfinder mission.
In the article, Sha and his coauthors at Carnegie Mellon University (CMU) identified the priority reversal problem and proposed a solution, which they called the priority cap protocol. Priority reversal refers to an operating system scheduling problem, where a high priority task is preempted by a lower priority task.
Several days after the Mars mission began, as the Pathfinder rover began collecting weather data, the spacecraft underwent several full resets due to software programming issues between high, medium, and low priority tasks. Specifically, the execution of the information bus thread (high priority) was blocked while the weather data collection thread (low priority) was running, a classic example of priority reversal.
Back on Earth, JPL engineers ran the same system software on their Pathfinder model and were able to reproduce the conditions that caused the reset, identifying the priority reversal 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 article with colleagues from the CMU Statistics Department in 1989. They proposed a necessary and sufficient scheduling test for fixed-priority real-time preemptive systems.
Their algorithm assigned an execution priority based on the time required to complete the job. For example, a thread that only takes a short time to run is given high priority. Monotonic rate programming algorithms are the only real-time calculation method approved for safety-critical applications in civil aviation since the 1990s.
Throughout her career, Sha has developed a systems approach to identifying high impact research issues that could be resolved with reasonable effort. A former member of the NASA Advisory Board, he used this method to help NASA select research programs. In Illinois, he teaches this research method to graduate students as part of the CS 591 LRS (formerly CS 598) course, “Improving Your Research Skills.”
Liu’s 1973 article with James W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” also won a 2020 Real-Time Systems Test-of-Time Award.
“He pioneered real-time systems planning analysis,” Sha said, noting that the article’s 12,000+ citations are an incredibly high number. “The impact of Dave’s article is still being felt, which means the work has stood the test of time. “
* Pathfinder software issues were reported by Mike Jones at the Forum on Risks to the Public in Computers and Related Systems in December 1997.