CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Load Regulating Algorithm for Static-Priority Task Scheduling on Multiprocessors

Risat Mahmud Pathan (Institutionen för data- och informationsteknik, Datorteknik (Chalmers)) ; Jan Jonsson (Institutionen för data- och informationsteknik, Datorteknik (Chalmers))
Proceedings of the 24th IEEE International Parallel & Distributed Processing Symposium, Atlanta, USA, April 19-23, 2010. p. 1-12. (2010)
[Konferensbidrag, refereegranskat]

This paper proposes a fixed-priority partitioned scheduling algorithm for periodic tasks on multiprocessors. A new technique for assigning tasks to processors is developed and the schedulability of the algorithm is analyzed for worst-case performance. We prove that, if the workload (utilization) of a given task set is less than or equal to 55.2% of the total processing capacity on m processors, then all tasks meet their deadlines. During task assignment, the total work load is regulated to the processors in such a way that a subset of the processors are guaranteed to have an individual processor load of at least 55.2%. Due to such load regulation, our algorithm can be used efficiently as an admission controller for online task scheduling. And this online algorithm is scalable with increasing number of cores in chip multiprocessors. In addition, our scheduling algorithm possesses two properties that may be important for the system designer. The first one guarantees that if task priorities are fixed before task assignment they do not change during task assignment and execution, thereby facilitating debugging during development and maintenance of the system. The second property guarantees that at most m/2 tasks are split, thereby keeping the run-time overhead as caused by task splitting low.

Nyckelord: Admission controller, Online scheduling, Partitioned multiprocessor scheduling, Task-splitting

Den här publikationen ingår i följande styrkeområden:

Läs mer om Chalmers styrkeområden  

Denna post skapades 2010-05-24. Senast ändrad 2016-07-19.
CPL Pubid: 121825


Läs direkt!

Länk till annan sajt (kan kräva inloggning)