Preemption-light multiprocessor scheduling of sporadic tasks with high utilisat...

• Autor(es): Bletsas, Konstantinos ; Andersson, Björn
• Data: 2011
• Identificador Persistente: http://hdl.handle.net/10400.22/3729
• Origem: Repositório Científico do Instituto Politécnico do Porto
• Assunto(s): Multiprocessor scheduling; Utilisation bound; Multicore; Preemptions; Migrations
• Tipo de Documento: Parte ou capítulo de livro
• Idioma: Inglês

Descrição

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.