A Polynomial-Time Algorithm for Computing Response Time Bounds in Static Priority Scheduling Employing Multi-linear Workload Bounds

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.