HomePublicationsPaper

Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
Ref: HURRAY-TR-090907       Publication Date: 1 to 4, Dec, 2009

Abstract:
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 a new 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 it in terms of its utilisation bound.
We also introduce a clustered variant of the algorithm, for use with systems made of multicore chips. It eliminates off-chip task migrations, which are costly, by dividing processors into independently-scheduled clusters (each, using the non-clustered algorithm). Each cluster is formed out of cores on the same chip. (The cluster size is a parameter to the algorithm.) We show that the utilisation bound is only moderately affected.

Konstantinos Bletsas

,

Björn Andersson

Document:

View
PDF Download
PDF