Minimum and maximum utilization bounds for multiprocessor RM scheduling
- 13 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This paper deals with the problem of finding utilization bounds for multiprocessor rate monotonic scheduling with partitioning. The minimum and maximum utilization bounds among all the reasonable allocation algorithms are calculated. We prove that the utilization bound associated with the reasonable allocation heuristic Worst Fit (WF) is equal to that minimum. In addition, we prove that the utilization bound associated with the heuristics First Fit Decreasing (FFD) and Best Fit Decreasing (BFD) is equal to the maximum, of value (n+1)(2/sup 1/2/-1), where n is the number of processors.Keywords
This publication has 10 references indexed in Scilit:
- An efficient RMS admission control and its application to multiprocessor schedulingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Using exact feasibility tests for allocating real-time tasks in multiprocessor systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Worst-case utilization bound for EDF scheduling on real-time multiprocessor systemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor AssignmentReal-Time Systems, 1998
- Assignment and scheduling communicating periodic tasks in distributed real-time systemsIEEE Transactions on Software Engineering, 1997
- Allocating fixed-priority periodic tasks on multiprocessor systemsReal-Time Systems, 1995
- New strategies for assigning real-time tasks to multiprocessor systemsIEEE Transactions on Computers, 1995
- Allocating hard real-time tasks: An NP-Hard problem made easyReal-Time Systems, 1992
- On a Real-Time Scheduling ProblemOperations Research, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973