Paper Info
Title
Utilization Bounds for N-Processor Rate Monotone Scheduling with Static Processor Assignment
Abstract
We consider the schedulability of a set of independent periodic tasks under fixed priority preemptive scheduling on homogeneous multiprocessor systems. Assuming there is no task migration between processors and each processor schedules tasks preemptively according to fixed priorities assigned by the Rate Monotonic policy, the scheduling problem reduces to assigning the set of tasks to disjoint processors in such a way that the Monotonic policy, the scheduling problem reduces to assigning the set of tasks to disjoint processors in such a way that the schedulability of the tasks on each processor can be guaranteed. In this paper we show that the worst case achievable utilization for such systems is between n(21/2-1) and (n+1)/(1+21/(n+1)), where n stands for the number of processors. The lower bound represents 41 percent of the total system capacity and the upper bound represents 50 to 66 percent depending on n. Practicality of the lower bound is demonstrated by proving it can be achieved using a First Fit scheduling algorithm.
Year
DOI
Venue
1998
10.1023/A:1008098013753
Realtime systems
Keywords
DocType
Volume
scheduling,rate monotone,utilization,real time,multi-processor
Journal
15
Issue
ISSN
Citations 
2
1573-1383
43
PageRank 
References 
Authors
3.49
6
2
Name
Order
Citations
PageRank
Oh Dong-ik1434.50
T. P. Baker21648171.36