DEPARTMENT OF COMPUTER SCIENCE

DOCTORAL DISSERTATION DEFENSE

**Competitive On-Line Scheduling **

for

Overloaded Real-Time Systems

DOCTORAL DISSERTATION DEFENSE

Candidate: | Gilad Koren |

Advisor: | Dennis Shasha |

Co-advisor: | Bhubaneswar Mishra |

for

Overloaded Real-Time Systems

10:30 a.m., Friday, September 3, 1993

12th floor conference room, 719 Broadway

Abstract

We study *competitive on-line
scheduling* in *uniprocessor* and *multiprocessor*
real-time environments. In our model,
tasks are sporadic and preemptable.
Every task has a deadline and a value
that the system obtains only if the task
completes its execution by its deadline.
The aim of a scheduler
is to maximize the total value obtained from all the tasks
that complete before their deadline.

An *on-line*
scheduler has no knowledge of a task until it is released.
The problem is to design an on-line scheduler
with worst case guarantees
even in the presence of overloaded periods.
The guarantee is given in terms of a positive competitive factor.
We say that an on-line algorithm has a competitive factor of
*r*,
0 < *r* <= 1,
when under all possible circumstances (i.e, task sets)
the scheduler will get at least *r*times the best possible value.
The best value is the value
obtained by a *clairvoyant* algorithm. In contrast
to an on-line scheduler, the clairvoyant algorithm
knows the entire task set *a priori* at time zero.

When a uniprocessor system is underloaded there exist several optimal on-line algorithms that will schedule all tasks to completion (e.g., the Earliest Deadline First algorithm). However, under overload, these algorithms perform poorly. Heuristics have been proposed to deal with overloaded situations but these give no worst case guarantees.

We present an optimal on-line scheduling algorithm for uniprocessor overloaded systems called D-over. D-over is optimal in the sense that it has the best competitive factor possible. Moreover, while the system is underloaded, D-over will obtain 100% of the possible value.

In the multiprocessor case, we study systems with two or more processors. We present an inherent limit (lower bound) on the best competitive guarantee that any on-line parallel real-time scheduler can give. Then we present a competitive algorithm that achieves a worst case guarantee which is within a small factor from the best possible guarantee in many cases.

These are the most general results yet known for competitive scheduling of multiprocessor real-time systems.