uu.seUppsala University Publications
Change search
ReferencesLink to record
Permanent link

Direct link
Real-Time Workload Models: Expressiveness vs. Analysis Efficiency
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Division of Computer Systems. Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
2014 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]

The requirements for real-time systems in safety-critical applications typically contain strict timing constraints. The design of such a system must be subject to extensive validation to guarantee that critical timing constraints will never be violated while the system operates. A mathematically rigorous technique to do so is to perform a schedulability analysis for formally verifying models of the computational workload. Different workload models allow to describe task activations at different levels of expressiveness, ranging from traditional periodic models to sophisticated graph-based ones. An inherent conflict arises between the expressiveness and analysis efficiency of task models. The more expressive a task model is, the more accurately it can describe a system design, reducing over-approximations and thus minimizing wasteful over-provisioning of system resources. However, more expressiveness implies higher computational complexity of corresponding analysis methods. Consequently, an ideal model provides the highest possible expressiveness for which efficient exact analysis methods exist.

This thesis investigates the trade-off between expressiveness and analysis efficiency. A new digraph-based task model is introduced, which generalizes all previously proposed models that can be analyzed in pseudo-polynomial time without using any analysis-specific over-approximations. We develop methods allowing to efficiently analyze variants of the model despite their strictly increased expressiveness. A key contribution is the notion of path abstraction which enables efficient graph traversal algorithms. We demonstrate tractability borderlines for different classes of schedulers, namely static priority and earliest-deadline first schedulers, by establishing hardness results. These hardness proofs provide insights about the inherent complexity of developing efficient analysis methods and indicate fundamental difficulties of the considered schedulability problems. Finally, we develop a novel abstraction refinement scheme to cope with combinatorial explosion and apply it to schedulability and response-time analysis problems. All methods presented in this thesis are extensively evaluated, demonstrating practical applicability.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2014. , 172 p.
Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1104-2516 ; 103
Keyword [en]
Real-time systems, task models, EDF, fixed-priority scheduling, schedulability analysis, response-time analysis, abstraction refinement
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
URN: urn:nbn:se:uu:diva-219307ISBN: 978-91-554-8888-8OAI: oai:DiVA.org:uu-219307DiVA: diva2:699155
Public defence
2014-04-11, Room 2446, Polacksbacken, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Available from: 2014-03-20 Created: 2014-02-26 Last updated: 2014-07-21

Open Access in DiVA

fulltext(1634 kB)415 downloads
File information
File name FULLTEXT01.pdfFile size 1634 kBChecksum SHA-512
Type fulltextMimetype application/pdf
Buy this publication >>

Search in DiVA

By author/editor
Stigge, Martin
By organisation
Division of Computer SystemsComputer Systems
Computer Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 415 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 1105 hits
ReferencesLink to record
Permanent link

Direct link