Title :
A Polynomial-Time Algorithm for Computing Response Time Bounds in Static Priority Scheduling Employing Multi-linear Workload Bounds
Author :
Stein, Steffen ; Ivers, Matthias ; Diemer, Jonas ; Ernst, Rolf
Author_Institution :
Inst. for Comput. & Network Eng. (IDA), Tech. Univ. Braunschweig, Braunschweig, Germany
Abstract :
Despite accuracy, analysis speed is sometimes a concern for the performance analysis of real-time systems, e.g. if to performed at runtime for online admission tests. As of today, several algorithms to compute an upper bound to the worst-case response time of a task scheduled under static priority preemptive scheduling with polynomial run-time have been proposed. Most approaches assume periodic activation of all tasks, some allow activation jitter. We generalize the approach to support convex activation patterns, by using multi-linear workload approximations and introduce the possibility to model processor availability to the task set under analysis.
Keywords :
polynomials; processor scheduling; real-time systems; multilinear workload bounds; performance analysis; polynomial-time algorithm; real-time systems; response time bounds computation; static priority scheduling; Equations; Indexes; Linear approximation; Mathematical model; Time factors; Upper bound; WCRT bound; real-time; scheduling analysis;
Conference_Titel :
Real-Time Systems (ECRTS), 2010 22nd Euromicro Conference on
Conference_Location :
Brussels
Print_ISBN :
978-1-4244-7546-9
Electronic_ISBN :
1068-3070
DOI :
10.1109/ECRTS.2010.27