Non-migratory online deadline scheduling on multiprocessors
Ho-Leung Chan
University of Hong Kong
Friday, Feb 20, 11-2, room 3464





Abstract
--------

We consider the online hard-deadline scheduling problem
on multiprocessors. Our focus is on eliminating migration
among the processors. The online hard-deadline scheduling
problem is defined as follows: We have a number of identical
processors. Jobs are released online at arbitrary time.
The processing time and deadline of a job are known 
immediately when it is released. The objective is to 
schedule all the jobs on the processors so that each job 
can be completed by its deadline. Note that preemption 
is allowed and a preempted job can resume later from the point
of preemption. If migration is allowed, a job can resume
on a different processor. From a practical point of view,
non-migratory schedules are preferable since migration
may incur significant overhead. Yet allowing migration
simplifies the design of scheduling algorithm.

In this talk, we present a new online algorithm PARK that
does not require job migration. When PARK is given 
processors of speed 6 times faster, PARK can guarantee 
completing all jobs by their deadlines, whenever some
offline migratory schedule (with normal speed processors) 
can do so. PARK also finds application in overloaded systems;
it gives the an online non-migratory algorithm that can
exploit moderately faster processors to match the 
performance of any migratory offline schedule.

This is joint work with Tak-Wah Lam and Kar-Keung To