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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
An optimal resource sharing protocol for generalized multiframe tasks
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems. (Embedded Systems)
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
Place, publisher, year, edition, pages
2015. Vol. 84, no 1, 92-105 p.
National Category
Computer Engineering
Research subject
Computer Science with specialization in Real Time Systems
Identifiers
URN: urn:nbn:se:uu:diva-235474DOI: 10.1016/j.jlamp.2014.10.001ISI: 000347601600007OAI: oai:DiVA.org:uu-235474DiVA: diva2:760714
Projects
UPMARC
Available from: 2014-10-16 Created: 2014-11-04 Last updated: 2017-12-05Bibliographically approved
In thesis
1. Models and Complexity Results in Real-Time Scheduling Theory
Open this publication in new window or tab >>Models and Complexity Results in Real-Time Scheduling Theory
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
Real-time systems, Scheduling theory, Task models, Computational complexity
National Category
Computer Science
Research subject
Computer Science with specialization in Embedded Systems
Identifiers
urn:nbn:se:uu:diva-267017 (URN)978-91-554-9423-0 (ISBN)
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

Open Access in DiVA

fulltext(1248 kB)126 downloads
File information
File name FULLTEXT01.pdfFile size 1248 kBChecksum SHA-512
21c901be9df1ca6ab1221cfcc5d6809b0d0ffd841185f22cff2619bf50786395834af16ae36437e10c7013e9de04a4423686900ce7cb5acfeb43fd3ad312aa32
Type fulltextMimetype application/pdf

Other links

Publisher's full text

Authority records BETA

Ekberg, PontusGuan, NanStigge, MartinYi, Wang

Search in DiVA

By author/editor
Ekberg, PontusGuan, NanStigge, MartinYi, Wang
By organisation
Computer Systems
In the same journal
The Journal of logical and algebraic methods in programming
Computer Engineering

Search outside of DiVA

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

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 474 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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