Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
Ref: HURRAY-TR-090907 Publication Date: 1 to 4, Dec, 2009
Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
Ref: HURRAY-TR-090907 Publication Date: 1 to 4, Dec, 2009Abstract:
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.
Document:
30th IEEE Real-Time Systems Symposium (RTSS 2009), pp 447-456.
Washington, D.C., U.S.A..
DOI:10.1109/RTSS.2009.16.
WOS ID: 000277465500041.
Record Date: 11, Sep, 2009