Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
Ref: HURRAY-TR-110105 Publication Date: Jul 2011
Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation boundRef: HURRAY-TR-110105 Publication Date: Jul 2011
Known algorithms capable of scheduling implicit-deadline sporadic tasks over identical processors at up to 100% utilisation invariably involve numerous preemptions and migrations. To the challenge of devising a scheduling scheme with as few preemptions and migrations as possible, for a given guaranteed utilisation bound, we respond with the algorithm NPS-F. It is configurable with a parameter, trading off guaranteed schedulable utilisation (up to 100%) vs preemptions. For any possible configuration, NPS-F introduces fewer preemptions than any other known algorithm matching its utilisation bound.
A clustered variant of the algorithm, for systems made of multicore chips, eliminates (costly) off-chip task migrations, by dividing processors into disjoint clusters, formed by cores on the same chip (with the cluster size being a parameter). Clusters are independently scheduled (each, using non-clustered NPS-F). The utilisation bound is only moderately affected.
We also formulate an important extension (applicable to both clustered and non-clustered NPS-F) which optimises the supply of processing time to executing tasks and makes it more granular. This reduces processing capacity requirements for schedulability without increasing preemptions.
Published in Real-Time Systems, Springer US, Volume 47, Issue 4, pp 319-355.
WOS ID: 000291254200002.