A Discrete DP-Wrap Scheduling Algorithm for Multiprocessor Systems

摘要

A discrete scheduling algorithm basing on DP-Wrap(DDP) for multiprocessor real-time systems is proposed in this paper. As fairness is a popular concept used in most of the published optimal algorithms(e.g., Pfair, Bfair), many of the scheduling produced by these algorithms leads to much run-time overhead such as preemptions and migrations. Meanwhile, many of the scheduling algorithms(e.g., LLREF, DP-Wrap) adopt a continuous time model, which mismatches the property of real-world digital computer system. Inspired by the DP-fair theory framework, a hierarchical scheduling mechanism is adopted in DDP. At the bottom level, the scheduling is carried out by a global scheduling algorithm basing on discrete time model, while at the top level, tasks are locally scheduled by uniprocessor EDF, which significantly reduces the run-time overhead in that execution pieces of a job can be packed together with a best effort. Analysis and experiment imply that DDP is expectable to outperform the algorithms adopting fairness notion in terms of preemptions and migrations.