A carregar...
Publicação
Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 1.89 MB | Adobe PDF |
Orientador(es)
Resumo(s)
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.
Descrição
Palavras-chave
Multiprocessor scheduling Utilisation bound Multicore Preemptions Migrations
Contexto Educativo
Citação
Editora
Springer