Utilization Bounds for RM Scheduling on Uniform Multiprocessors
Authors:
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 315-321
Abstract
Utilization bounds for earliest deadline first (EDF) and rate monotonic (RM) scheduling are known and well understood for uniprocessor systems. In this paper, we derive limits on similar bounds for the multiprocessor case, when the individual processors need not be identical. Tasks are partitioned among the processors and RM scheduling is assumed to be the policy used in individual processors. A minimum limit on the bounds for a 'greedy' class of algorithms is given and proved, since the actual value of the bound depends on the algorithm that allocates the tasks. We also derive the utilization bound of an algorithm which allocates tasks in decreasing order of utilization factors. Knowledge of such bounds allows us to carry out very fast schedulability tests although we are constrained by the fact that the tests are sufficient but not necessary to ensure schedulabilityKeywords
This publication has 7 references indexed in Scilit:
- Task Assignment on Uniform Heterogeneous Multiprocessors2006
- Feasibility Analysis of Preemptive Real-Time Systems upon Heterogeneous Multiprocessor Platforms2005
- Real Time Scheduling Theory: A Historical PerspectiveReal-Time Systems, 2004
- Utilization Bounds for EDF Scheduling on Real-Time Multiprocessor SystemsReal-Time Systems, 2004
- Partitioning real-time tasks among heterogeneous multiprocessors2004
- Minimum and maximum utilization bounds for multiprocessor RM scheduling2002
- On-line scheduling on uniform multiprocessors2001