loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Ninth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'03)
Global Multiprocessor Scheduling of Aperiodic Tasks using Time-Independent Priorities
Toronto, Canada
May 27-May 30
ISBN: 0-7695-1956-3
Lars Lundberg, Blekinge Institute of Technology
H?kan Lennerstad, Blekinge Institute of Technology
We provide a constant time schedulability test for a multiprocessor server handling aperiodic tasks. Dhall?s effect is avoided by dividing the tasks in two priority classes based on task utilization: heavy and light. We prove that if the load on the multiprocessor server stays below Uthreshold = 3 - \[\sqrt 7 \] \approx 35.425%, the server can accept incoming aperiodic tasks and guarantee that the deadlines of all accepted tasks will be met. 35.425% utilization is also a threshold for a task to be characterized as heavy.
The bound Uthreshold = 3 - \[\sqrt 7 \] \approx 35.425% is easy-to-use, but not sharp if we know the number of processors in the multiprocessor. For a server with m processors, we calculate a formula for the sharp bound Uthreshold(m), which converges to Uthreshold from above as m \rightarrow \infty.
The results are based on a utilization function um(x) = 2(1 - x)/(2 + \[\sqrt {2 + 2x} \]) + x/m. By using this function, the performance of the multiprocessor can in some cases be improved beyond Uthreshold(m) by paying the extra overhead of monitoring the individual utilization of the current tasks.
Citation:
Lars Lundberg, H?kan Lennerstad, "Global Multiprocessor Scheduling of Aperiodic Tasks using Time-Independent Priorities," rtas, pp.170, Ninth IEEE Real-Time and Embedded Technology and Applications Symposium (RTAS'03), 2003
Usage of this product signifies your acceptance of the Terms of Use.