Improving and Estimating the Precision of Bounds on the Worst-Case Latency of Task Chains

Abstract : One major issue that hinders the use of performance analysis in industrial design processes is the pessimism inherent to any analysis technique that applies to realistic system models. Indeed, such analyses may conservatively declare unschedulable systems that will in fact never miss any deadlines. We advocate the need to compute not only tight upper bounds on worst-case behaviors, but also tight lower bounds. As a first step, we focus on uniprocessor systems executing a set of sporadic or periodic hard real-time task chains. Each task has its own priority, and the chains are scheduled according to the fixed-priority preemptive scheduling policy. Computing the worst-case end-to-end latency (WCEL) of each chain is complex because of the intricate relationship between the task priorities. Compared to the state of the art, our analysis provides upper bounds on the WCEL in the more general case of asynchro-nous task chains, and also provides lower bounds on the WCEL both for synchronous and asynchronous chains. Our computed lower bounds correspond to actual system executions exhibiting a behavior that is as close to the worst case as possible, while all other approaches rely on simulations. Extensive experiments show the relevance of lower bounds on the worst-case behavior for the industrial design of real-time embedded systems. CCS CONCEPTS • Computer systems organization → Embedded systems; KEYWORDS Worst-case end to end latency, Latency analysis, Task chains ACM Reference format:
Document type :
Journal articles
Complete list of metadatas

Cited literature [9 references]  Display  Hide  Download
Contributor : Sophie Quinton <>
Submitted on : Tuesday, December 18, 2018 - 2:50:16 PM
Last modification on : Thursday, February 7, 2019 - 2:25:09 PM
Long-term archiving on : Wednesday, March 20, 2019 - 12:31:35 PM


Files produced by the author(s)




Alain Girault, Christophe Prévot, Sophie Quinton, Rafik Henia, Nicolas Sordon. Improving and Estimating the Precision of Bounds on the Worst-Case Latency of Task Chains. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, IEEE, 2018, 37 (11), pp.2578-2589. ⟨10.1109/TCAD.2018.2861016⟩. ⟨hal-01956931⟩



Record views


Files downloads