Real-Time Scheduling on Multiprocessors
Real-time scheduling became a scientific area in the late 1960s during
the Apollo program that put man on the moon. During this mission,
it was necessary for an embedded computer to run multiple processes
with timing requirement. An approach was taken to assign a priority
to a process and this priority does not change at run-time
(fixed priority scheduling). Two contexts were explored:
(i) fixed-priority scheduling of processes on a single processor, and
(ii) fixed-priority scheduling of processes on a multiprocessor.
For fixed-priority scheduling of processes on a single processor, researchers developed two important results:
an optimal priority assignment and proving its utilization bound.
If processes arrive periodically,
then one can compute the rate of each process (the rate of a process is the inverse
of its period) and then one can assign priorities to processes so that the priority is monotonically
increasing with the rate; this priority assignment became known as Rate-Monotonic (RM).
It was shown that under certain assumptions, RM is optimal.
It was also shown that under certain assumptions, the utilization bound of RM is 69%; meaning that
if at most 69% of the processing capacity is used then RM schedules all processes to meet all deadlines.
This type of real-time scheduling was extended by several researchers to many realistic settings and
the results became widely used in industry.
(see for example the book:
Mark Klein, Thomas Ralya, Bill Pollak, Ray Obenza,
Michael González Harbour, "A Practitioner's Handbook for Real-Time Analysis:
Guide to Rate Monotonic Analysis for Real-Time Systems")
For fixed-priority scheduling of processes on a multiprocessor, progress was slow. The reason was that it was known that there are simple
processes that utilize an arbitrarily small fraction of the entire computing capacity of
a multiprocessor but if RM is used and all processes share a ready queue between processors
then RM generates a schedule that misses a deadline. For this reason, I (together with collaborators) developed
a new priority assignment called RM-US(m/(3m-2)) which avoids this issue.
For details, see:
Björn Andersson, Sanjoy K. Baruah, Jan Jonsson: Static-Priority Scheduling on Multiprocessors. RTSS 2001: 193-202.
)
I am currently exploring better scheduling theory for multiprocessors to (i) obtain better performance
in theory and (ii) be able to model real-world effects better (memory contention, parallel tasks).
Cyber-Physical Systems
In many computer systems, it is necessary for the computer to communicate (typically
for one computer node to disseminate its sensor reading(s) to other computer nodes).
Doing so and fulfilling real-time requirements is challenging. The automotive industry
has developed a technology called Controller Area Network (CAN) which assigns a priority
to a message and then messages contend for a shared bus so that the one with the highest
priority is granted access.
It is often desirable to use wireless channels. Unfortunately, for wireless channels,
there was no CAN bus available. So I (together with collaborators) invented it. See
Björn Andersson, Eduardo Tovar: Static-Priority Scheduling of Sporadic Messages on a Wireless Channel. OPODIS 2005: 322-333.
)
This protocol also has some other interesting properties: (i) it can be used as a building block in distributed algorithms
and then compute some aggregate quantities (MIN, MAX, logical-OR) with very low time-complexity, and (ii) it has the potential to achieve an improvement in reliability
that grows exponentially with the number of computer nodes in the network.
I am also exploring new ways of reasoning of computer systems and their physical world together.