(2017) An Exact and Sustainable Analysis of Non-preemptive Scheduling.
Abstract
This paper provides an exact and sustainable schedulability test for a set of non-preemptive jobs scheduled with a fixed-job-priority (FJP) policy upon a uniprocessor. Both classic work-conserving and recent non-work-conserving schedulers are supported. Jobs may exhibit both release jitter and execution time variation. Both best- and worst-case response time bounds are derived. No prior response-time analysis (RTA) for this general setting is both exact and sustainable, nor does any prior RTA support non-work-conserving schedulers. The proposed analysis works by building a schedule graph that precisely abstracts all possible execution scenarios. Key to deferring the state-space explosion problem is a novel path-merging technique that collapses similar scenarios without giving up analysis precision. In an empirical evaluation with randomly generated workloads based on an automotive benchmark, the method is shown to scale to 30+ periodic tasks with thousands of jobs (per hyperperiod).
| Item Type: | Conference or Workshop Item (A Paper) (Paper) |
|---|---|
| Uncontrolled Keywords: | Algorithm design and analysis;Jitter;Real-time systems;Runtime;Schedules;Scheduling algorithms;Task analysis;fixed-job-priority;non-preemptive-scheduling;non-work-conserving-scheduling;real-time-systems;schedulability-analysis;sustainability |
| Conference: | RTSS Real Time Systems Symposium |
| Depositing User: | Andreas Rau |
| Date Deposited: | 22 Feb 2018 10:42 |
| Last Modified: | 18 Jul 2019 12:12 |
| Primary Research Area: | NRA5: Empirical & Behavioral Security |
| URI: | https://publications.cispa.saarland/id/eprint/1535 |
Actions
Actions (login required)
 |
View Item |