Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor Systems |
| |
Authors: | J M López J L Díaz D F García |
| |
Affiliation: | (1) Departamento de Informática, Universidad de Oviedo, Gijón, 33204, Spain |
| |
Abstract: | The utilization bound for earliest deadline first (EDF) scheduling is extended from uniprocessors to homogeneous multiprocessor systems with partitioning strategies. First results are provided for a basic task model, which includes periodic and independent tasks with deadlines equal to periods. Since the multiprocessor utilization bounds depend on the allocation algorithm, different allocation algorithms have been considered, ranging from simple heuristics to optimal allocation algorithms. As multiprocessor utilization bounds for EDF scheduling depend strongly on task sizes, all these bounds have been obtained as a function of a parameter which takes task sizes into account. Theoretically, the utilization bounds for multiprocessor EDF scheduling can be considered a partial solution to the bin-packing problem, which is known to be NP-complete. The basic task model is extended to include resource sharing, release jitter, deadlines less than periods, aperiodic tasks, non-preemptive sections, context switches, and mode changes. |
| |
Keywords: | multiprocessor scheduling partitioning bin-packing problem earliest deadline first scheduling multiprocessor utilization bounds |
本文献已被 SpringerLink 等数据库收录! |
|