Multiprocessor Scheduling with Few Preemptions
Authors:
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 23251271,p. 322-334
Abstract
Consider the problem of scheduling a set of periodically arriving tasks on a multiprocessor with the goal of meeting deadlines. Processors are identical and have the same speed. Tasks can be preempted and they can migrate between processors. We propose an algorithm with a utilization bound of 66% and with few preemptions. It can trade a higher utilization bound for more preemptions and in doing so it has a utilization bound of 100%Keywords
This publication has 9 references indexed in Scilit:
- Multiprocessor Scheduling with Few Preemptions2006
- Mixed Pfair/ERfair scheduling of asynchronous periodic tasksJournal of Computer and System Sciences, 2004
- Multiprocessor scheduling of periodic tasks in a hard real-time environment2003
- Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor AssignmentReal-Time Systems, 1998
- Proportionate progress: A notion of fairness in resource allocationAlgorithmica, 1996
- Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processorReal-Time Systems, 1990
- On the complexity of fixed-priority scheduling of periodic, real-time tasksPerformance Evaluation, 1982
- On a Real-Time Scheduling ProblemOperations Research, 1978
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973