There has been much recent interest in multiprocessor
Pfair scheduling algorithms. Under Pfair scheduling, each
task is broken into quantum-length subtasks, each of which
must execute within a "window" of time slots. These
windows divide each period of a task into subintervals of
approximately equal length. Almost all prior work on Pfair
scheduling has been limited to synchronous, periodic task
systems. This stands in contrast to most uniprocessor
scheduling schemes, where demand-based arguments can be
easily applied to reduce sporadic systems to asynchronous,
periodic ones. In Pfair systems, such demand-based
arguments do not work. Instead, arguments are used that
hinge on the exact alignment of the windows of
concurrently-enabled tasks. Unfortunately, such alignments
cannot always be predicted in sporadic systems, because some
jobs may be released "late." In this paper, we sketch a new
proof that shows that the PD Pfair algorithm is optimal for
scheduling sporadic tasks on a multiprocessor. We begin
by showing that PD can miss a deadline only if it previously
left a processor idle where an optimal scheduler would not.
Then, we use a swapping argument to show that PD cannot
leave more processors idle than an optimal scheduler, giving
a contradiction.
