Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Models and Complexity Results in Real-Time Scheduling Theory
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)
2015 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

When designing real-time systems, we want to prove that they will satisfy given timing constraints at run time. The main objective of real-time scheduling theory is to analyze properties of mathematical models that capture the temporal behaviors of such systems. These models typically consist of a collection of computational tasks, each of which generates an infinite sequence of task activations. In this thesis we study different classes of models and their corresponding analysis problems.

First, we consider models of mixed-criticality systems. The timing constraints of these systems state that all tasks must meet their deadlines for the run-time scenarios fulfilling certain assumptions, for example on execution times. For the other scenarios, only the most important tasks must meet their deadlines. We study both tasks with sporadic activation patterns and tasks with complicated activation patterns described by arbitrary directed graphs. We present sufficient schedulability tests, i.e., methods used to prove that a given collection of tasks will meet their timing constraints under a particular scheduling algorithm.

Second, we consider models where tasks can lock mutually exclusive resources and have activation patterns described by directed cycle graphs. We present an optimal scheduling algorithm and an exact schedulability test.

Third, we address a pair of longstanding open problems in real-time scheduling theory. These concern the computational complexity of deciding whether a collection of sporadic tasks are schedulable on a uniprocessor. We show that this decision problem is strongly coNP-complete in the general case. In the case where the asymptotic resource utilization of the tasks is bounded by a constant smaller than 1, we show that it is weakly coNP-complete.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2015. , 32 p.
Series
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1324
Keyword [en]
Real-time systems, Scheduling theory, Task models, Computational complexity
National Category
Computer Science
Research subject
Computer Science with specialization in Embedded Systems
Identifiers
URN: urn:nbn:se:uu:diva-267017ISBN: 978-91-554-9423-0 (print)OAI: oai:DiVA.org:uu-267017DiVA: diva2:873310
Public defence
2016-01-15, ITC, 2446, Lägerhyddsvägen 2, Uppsala, 13:15 (English)
Opponent
Supervisors
Available from: 2015-12-16 Created: 2015-11-16 Last updated: 2016-01-13
List of papers
1. Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
Open this publication in new window or tab >>Bounding and shaping the demand of generalized mixed-criticality sporadic task systems
2014 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 50, no 1, 48-86 p.Article in journal (Refereed) Published
Abstract [en]

We generalize the commonly used mixed-criticality sporadic task model to let all task parameters (execution-time, deadline and period) change between criticality modes. In addition, new tasks may be added in higher criticality modes and the modes may be arranged using any directed acyclic graph, where the nodes represent the different criticality modes and the edges the possible mode switches. We formulate demand bound functions for mixed-criticality sporadic tasks and use these to determine EDF-schedulability. Tasks have different demand bound functions for each criticality mode. We show how to shift execution demand between different criticality modes by tuning the relative deadlines. This allows us to shape the demand characteristics of each task. We propose efficient algorithms for tuning all relative deadlines of a task set in order to shape the total demand to the available supply of thecomputing platform. Experiments indicate that this approach is successful in practice. This new approach has the added benefit of supporting hierarchical scheduling frameworks.

National Category
Computer Science
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-212779 (URN)10.1007/s11241-013-9187-z (DOI)000328351200003 ()
Projects
UPMARC
Available from: 2013-06-15 Created: 2013-12-13 Last updated: 2017-12-06Bibliographically approved
2. Schedulability analysis of a graph-based task model for mixed-criticality systems
Open this publication in new window or tab >>Schedulability analysis of a graph-based task model for mixed-criticality systems
2016 (English)In: Real-time systems, ISSN 0922-6443, E-ISSN 1573-1383, Vol. 52, no 1, 1-37 p.Article in journal (Refereed) Published
National Category
Computer Science
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-265781 (URN)10.1007/s11241-015-9225-0 (DOI)000370819700001 ()
Available from: 2015-05-01 Created: 2015-11-03 Last updated: 2017-12-01Bibliographically approved
3. An optimal resource sharing protocol for generalized multiframe tasks
Open this publication in new window or tab >>An optimal resource sharing protocol for generalized multiframe tasks
2015 (English)In: The Journal of logical and algebraic methods in programming, ISSN 2352-2208, E-ISSN 2352-2216, Vol. 84, no 1, 92-105 p.Article in journal (Refereed) Published
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-235474 (URN)10.1016/j.jlamp.2014.10.001 (DOI)000347601600007 ()
Projects
UPMARC
Available from: 2014-10-16 Created: 2014-11-04 Last updated: 2017-12-05Bibliographically approved
4. Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete
Open this publication in new window or tab >>Uniprocessor feasibility of sporadic tasks with constrained deadlines is strongly coNP-complete
2015 (English)In: Proc. 27th Euromicro Conference on Real-Time Systems, Piscataway, NJ: IEEE, 2015, 281-286 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
Piscataway, NJ: IEEE, 2015
National Category
Computer Science
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-265783 (URN)10.1109/ECRTS.2015.32 (DOI)000375052900025 ()978-1-4673-7570-2 (ISBN)
Conference
ECRTS 2015, July 7–10, Lund, Sweden
Projects
UPMARC
Available from: 2015-08-06 Created: 2015-11-03 Last updated: 2017-03-16Bibliographically approved
5. Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
Open this publication in new window or tab >>Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
2015 (English)In: Proc. 36th Real-Time Systems Symposium, IEEE Computer Society, 2015, 87-95 p.Conference paper, Published paper (Refereed)
Place, publisher, year, edition, pages
IEEE Computer Society, 2015
National Category
Computer Science
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
urn:nbn:se:uu:diva-265784 (URN)10.1109/RTSS.2015.16 (DOI)000380424600009 ()978-1-4673-9507-6 (ISBN)
Conference
RTSS 2015, December 1–4, San Antonio, TX
Projects
UPMARC
Available from: 2016-01-18 Created: 2015-11-03 Last updated: 2017-03-17Bibliographically approved

Open Access in DiVA

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

Authority records BETA

Ekberg, Pontus

Search in DiVA

By author/editor
Ekberg, Pontus
By organisation
Division of Computer SystemsComputer Systems
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 120 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

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 1467 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf