Generalized Weakly Hard Schedulability Analysis for Real-Time Periodic Tasks
Open Access
- 7 December 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 20 (1) , 1-26
Abstract
The weakly hard real-time model is an abstraction for applications, including control systems, that can tolerate occasional deadline misses, but can also be compromised if a sufficiently high number of late terminations occur in a given time window. The weakly hard model allows us to constrain the maximum number of acceptable missed deadlines in any set of consecutive task executions. A big challenge for weakly hard systems is to provide a schedulability analysis that applies to a general task model, while avoiding excessive pessimism. In this work, we develop a general weakly hard analysis based on a Mixed Integer Linear Programming (MILP) formulation. The analysis applies to constrained-deadline periodic real-time systems scheduled with fixed priority and no knowledge of the task activation offsets, while allowing for activation jitter. Our analysis considers two common policies for handling missed deadlines, i.e., (i) letting the job continue until completion or (ii) killing its execution immediately. For this policy, ours is the first and only m-k analysis currently available. Experiments conducted on randomly generated task sets show the applicability and accuracy of the proposed technique as well as the improvements with respect to competing techniques.Keywords
This publication has 31 references indexed in Scilit:
- Improved Deadline Miss Models for Real-Time Systems Using Typical Worst-Case Analysis2015
- Co-design of control and platform with dropped signals2013
- Measuring the Performance of Schedulability TestsReal-Time Systems, 2005
- Real Time Scheduling Theory: A Historical PerspectiveReal-Time Systems, 2004
- Weakly hard real-time systemsIEEE Transactions on Computers, 2001
- Overload management in real-time control applications using (m, k)-firm guaranteeIEEE Transactions on Parallel and Distributed Systems, 1999
- A dynamic priority assignment technique for streams with (m, k)-firm deadlinesIEEE Transactions on Computers, 1995
- Finding Response Times in a Real-Time SystemThe Computer Journal, 1986
- On the complexity of fixed-priority scheduling of periodic, real-time tasksPerformance Evaluation, 1982
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973