History
and Accomplishments (See powerpoint
presentation here)
Origins of Schedulability Analysis
The Networked Real-Time Embedded System
Laboratory (NRTESL) at UIUC has a long and distinguished record. Members
have conducted fundamental research with great impact on the engineering of
real-time embedded systems. The laboratory was founded by David Liu and
Jane Liu in the 70’s. Professor David C. L. Liu analyzed the basic
properties of the two mostly widely used scheduling algorithms, the rate
monotonic and deadline scheduling algorithms for independent periodic
tasks. The Rate Monotonic
Scheduling algorithm was used in the NASA Apollo program http://history.nasa.gov/apollo.html
His seminal work pioneered schedulability
analysis ¾- the foundation for many of the subsequent research
in real-time computing. Among many other awards, Prof. Liu received the 1st
Outstanding Technical Achievement Award from the IEEE Real-Time System
Committee in 1999 for his seminal work on real-time computing.
|
|
|
Imprecise Computations
During late 80’s and early
90’s, Professors Jane Liu and Kwei Jay Lin pioneered the research on
the imprecise computation technique which allows for flexible trade-offs
between timeliness and precision and is an effective means to handle overload
conditions and provide graceful degradation in real-time environments. They
and their students developed algorithms for scheduling imprecise tasks to
trade quality for time and fault tolerance strategies based on this
technique.
To
enable its use in application domains as diverse as databases, real-time
control and data communication, they developed a relational query processor
that returns partial answers with increasing accuracy as more data is
retrieved and processed, determined the quality/time tradeoffs of direct
digital controllers, and evaluated the effectiveness of this technique for
multimedia traffic congestion control.
|
Open Real-Time Computing Architecture
Professor Jane Liu's other work include algorithms
for end-to-end scheduling in multiprocessor and distributed systems and
rigorous and tractable methods to bound the effect of timing anomalies
exhibited by tasks in these systems. In the early 90's, she led the effort
in the development of PERTS
(Prototyping Environment for Real-Time Systems). This system of
schedulers and tools enables its users to experiment with alternative
real-time resource management strategies, to synthesize and tune the run-time
system, and to validate the timing properties of the resultant system.
PERTS is the earliest of such tools and is still the most widely marketed
and used one.
She and her students developed the Open
Real-Time Computing architecture and its underlying principles. This
architecture allows independently developed real-time and non-real-time
applications to effectively share computing and communication resources
without interfering each other.
|
|
Generalized Rate Monotonic Scheduling
Professor Lui Sha joined the laboratory
in 1998. Building upon the pioneering work by David C. L. Liu, he worked
with John Lehoczky and Ragunathan Rajkumar at CMU as well as with John
Goodenough and Mark Klein at SEI to develop and transition into practice a
comprehensive real-time scheduling theory known as Generalized Rate
Monotonic Scheduling (GRMS). Professor Sha was elected ACM Fellow in 2006
“for contributions to real time systems” and elected
IEEE Fellow in 1998 for “for technical leadership and research
contributions which enabled the transformation of real-time computing
practice from an ad hoc process to an engineering process based on analytic
methods.”
GRMS
is now the foundation for the real-time computing in IEEE Futurebus+, IEEE
POSIX RT extension, Ada 95, real-time CORBA, real-time Java, real-time UML.
This real-time computing infrastructure has become the basic building
blocks of modern real-time systems. GRMS was cited in the Selected
Accomplishment Section (p. 193) of the National Research Council's report, A
Broader Agenda for Computer Science and Engineering, 1992.
|
|
International Space Station
“Through the development of Rate
Monotonic Scheduling [theory], we now have a system that will allow [Space
Station] Freedom's computers to budget their time, to choose between a
variety of tasks, and decide not only which one to do first but how
much time to spend in the
process”
Deputy Administrator of NASA, Aaron
Cohen, “Charting The Future: Challenges and Promises Ahead of Space
Exploration”, pp. 3, October 1992.
International GPS Systems
“The navigation payload software
for the next block of Global Positioning System upgrade recently completed
testing. ... This design would have
been difficult or impossible prior to the development of rate monotonic
theory”, L. Doyle, and J.
Elzey, “Successful Use of Rate Monotonic Theory on A Formidable
Real-Time System”, in
the Proceedings of 11th IEEE Workshop on Real-Time Operating Systems and
Software, pp. 74, 1994.
|
The Mars
Pathfinder
“The Mars Pathfinder mission was
widely proclaimed as "flawless" in the early days after its July
4th, 1997 landing on the Martian surface. … But a few days into the mission, not
long after Pathfinder started gathering meteorological data, the spacecraft
began experiencing total system resets… Once diagnosed, it was clear
to the JPL engineers that using priority inheritance would prevent the
resets they were seeing. …No more system resets occurred.
David also said that some of the real
heroes of the situation were some people… who first identified the
priority inversion problem and proposed the solution …They were Lui
Sha, John Lehoczky, and Raj Rajkumar. …
When was the last time you saw a room of
people cheer a group of computer science theorists for their significant practical
contribution to advancing human knowledge? :-) It was quite a
moment.”
|
Building Robust Systems
Professor Lui Sha led the development of
Simplex architecture for building robust real time control systems. The
architecture principles include the use of GRMS for timing correctness,
real time publication and subscription to decouple system components, the
use of simple and analytically redundant components to ensure critical
functions, explicit and machine checkable environmental assumptions, and
the enforcement of well-formed dependency.
“The bottom line is that now we
are basing the mathematical Analysis on work done by Dr. Sha.” Greg Marin, Rockwell Collin March
2001. Report to FAA on the
analysis of timing behavior of Real Time Virtual Processors for DO 178B
level A certification.
“Lui’s
contribution is immeasurable. His superior knowledge in detailed
architecture design attributes, fault tolerant strategies, and software
development practices were a tremendous aid in calibrating the F35 Mission Systems Design Philosophy. His support has
been nothing short of flawless in accessing complex advanced avionics.” John L. Hudson, Major General, USAF,
JSF Program Executive Officer, April 5, 2004
“Prof Sha’s assistance has
been invaluable in raising software stability by an order of magnitude on
the F/A-22 lead jets. Prof Sha has played a central role in assisting
the F/A-22 program to improve its avionics stability.” Dr. Andre vanTilborg, Director of
Information Technology, Office of the Secretary of Defense, 9/24/2003
|
|
|
|
|
|
|
|
