UC Santa Cruz

We consider the problem of scheduling a collection of processes, or tasks, on a multiprocessor platform. The tasks in question have real-time computing requirements, meaning that they have frequent processing deadlines that must be met. We are interested in optimal scheduling algorithms, which find a correct schedule for a set of tasks whenever it is possible to do so.

Recent work in the field has used the notions of fluid scheduling and deadline partitioning to guarantee optimality and improve performance. In the first part of this dissertation, we develop a unifying theory of existing approaches with the DP-Fair scheduling policy, and show how it easily proves and explains existing approaches. We then present a simple DP-Fair scheduling algorithm, DP-Wrap, which serves as a least common ancestor to many recent algorithms. We also show how to extend DP-Fair to the scheduling of sporadic tasks with arbitrary deadlines.

While easy to understand and implement, DP-Fair algorithms have the drawback of incurring a significant overhead in preemptions and migrations. In the second part of this dissertation, we present RUN, the first optimal algorithm which does not rely on a DP-Fair approach. Instead, RUN reduces the multiprocessor problem to a series of much easier uniprocessor problems. RUN's average preemptions per job never exceeded 3 in any simulation, and has a provable upper bound of 4 for most task sets. It also reduces to Partitioned EDF whenever a proper task-to-processor partitioning is found, and significantly outperforms all existing optimal algorithms.