uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Uniprocessor feasibility of sporadic tasks remains coNP-complete under bounded utilization
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. (Embedded Systems)
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik. (Embedded Systems)
2015 (Engelska)Ingår i: Proc. 36th Real-Time Systems Symposium, IEEE Computer Society, 2015, s. 87-95Konferensbidrag, Publicerat paper (Refereegranskat)
Ort, förlag, år, upplaga, sidor
IEEE Computer Society, 2015. s. 87-95
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap med inriktning mot realtidssystem
Identifikatorer
URN: urn:nbn:se:uu:diva-265784DOI: 10.1109/RTSS.2015.16ISI: 000380424600009ISBN: 978-1-4673-9507-6 (digital)OAI: oai:DiVA.org:uu-265784DiVA, id: diva2:866563
Konferens
RTSS 2015, December 1–4, San Antonio, TX
Projekt
UPMARCTillgänglig från: 2016-01-18 Skapad: 2015-11-03 Senast uppdaterad: 2018-01-10Bibliografiskt granskad
Ingår i avhandling
1. Models and Complexity Results in Real-Time Scheduling Theory
Öppna denna publikation i ny flik eller fönster >>Models and Complexity Results in Real-Time Scheduling Theory
2015 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Uppsala: Acta Universitatis Upsaliensis, 2015. s. 32
Serie
Digital Comprehensive Summaries of Uppsala Dissertations from the Faculty of Science and Technology, ISSN 1651-6214 ; 1324
Nyckelord
Real-time systems, Scheduling theory, Task models, Computational complexity
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
Datavetenskap med inriktning mot inbyggda system
Identifikatorer
urn:nbn:se:uu:diva-267017 (URN)978-91-554-9423-0 (ISBN)
Disputation
2016-01-15, ITC, 2446, Lägerhyddsvägen 2, Uppsala, 13:15 (Engelska)
Opponent
Handledare
Projekt
UPMARC
Tillgänglig från: 2015-12-16 Skapad: 2015-11-16 Senast uppdaterad: 2019-02-25

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Ekberg, PontusYi, Wang

Sök vidare i DiVA

Av författaren/redaktören
Ekberg, PontusYi, Wang
Av organisationen
Datorteknik
Datavetenskap (datalogi)

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 401 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf