Desynchronized Pfair scheduling on multiprocessors

Pfair scheduling, currently the only known way of optimally scheduling recurrent real-time tasks on multiprocessors, imposes certain requirements that may limit its practical implementation. In this paper, we address one such limitation - which requires processor time to always be allocated in units...

Full description

Saved in:
Bibliographic Details
Main Authors: Devi, U.C., Anderson, J.H.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Computer applications
Computer science
Operating systems
Processor scheduling
Protocols
Real time systems
Scheduling algorithm
Timing
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Pfair scheduling, currently the only known way of optimally scheduling recurrent real-time tasks on multiprocessors, imposes certain requirements that may limit its practical implementation. In this paper, we address one such limitation - which requires processor time to always be allocated in units of fixed-sized quanta that are synchronized across processors - and determine the impact of relaxing it. We show that if this requirement, which may lead to wasted processor time, is relaxed, then under an otherwise-optimal Pfair scheduling algorithm deadlines are missed by at most one quantum only, which is sufficient to provide soft real-time guarantees. This result can be shown to extend to most prior work on Pfair scheduling: in general, tardiness bounds guaranteed by previously-proposed suboptimal Pfair algorithms are worsened by at most one quantum only.
ISSN:1530-2075
DOI:10.1109/IPDPS.2005.167