mdh.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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
Resource Augmentation for Fault-Tolerance Feasibility of Real-time Tasks under Error Bursts
Mälardalens högskola, Akademin för innovation, design och teknik. (IS (Dependability))ORCID-id: 0000-0002-6355-3564
Mälardalens högskola, Akademin för innovation, design och teknik. (IS)ORCID-id: 0000-0003-4157-3537
Mälardalens högskola, Akademin för innovation, design och teknik. (IS)ORCID-id: 0000-0001-5269-3900
Mälardalens högskola, Akademin för innovation, design och teknik. (IS)ORCID-id: 0000-0001-5053-6725
2012 (Engelska)Ingår i: Proceedings of the 20th International Conference on Real-Time and Network Systems (RTNS 12), Association for Computing Machinery (ACM), 2012, s. 41-50Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Dependability is a vital system requirement, particularly in safety critical and mission critical real-time systems, due to the potentially catastrophic consequences of failures. In most critical applications different fault tolerance mechanisms using redundancy are employed to prevent possible failures. In the case of real-time systems the system designer must ensure that the task set is feasible even under faults, which we refer to as 'fault tolerance feasibility'. Due to cost considerations, often temporal redundancy has been prevalently used to meet this objective.

In this paper we focus on guaranteeing fault-tolerance feasibility under error bursts on uni-processor systems by the usage of resource augmentation, specifically through processor speed-up. Firstly, we derive a processor demand bound based sufficient condition for a set of real-time tasks to be fault tolerance feasible under an assumption that no more than one error burst occurs during the hyper-period of the task set. Subsequently, we derive the necessary resource augmentation bounds (i.e., the processor speed-up), that guarantees the fault tolerance feasibility, if the sufficient test fails. Finally, we prove that, if the error burst length is no more than half the shortest relative deadline of the task set, the minimum processor speed-up required to guarantee fault tolerance feasibility is upper-bounded by 6.

Ort, förlag, år, upplaga, sidor
Association for Computing Machinery (ACM), 2012. s. 41-50
Nationell ämneskategori
Teknik och teknologier
Identifikatorer
URN: urn:nbn:se:mdh:diva-16074DOI: 10.1145/2392987.2392992OAI: oai:DiVA.org:mdh-16074DiVA, id: diva2:563680
Konferens
The 20th International Conference on Real-Time and Network Systems, ACM, Pont à Mousson, France
Tillgänglig från: 2012-10-31 Skapad: 2012-10-31 Senast uppdaterad: 2013-12-03Bibliografiskt granskad
Ingår i avhandling
1. Resource Augmentation for Performance Guarantees in Embedded Real-time Systems
Öppna denna publikation i ny flik eller fönster >>Resource Augmentation for Performance Guarantees in Embedded Real-time Systems
2012 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

Real-time scheduling policies have been widely studied, with many known schedulability and feasibility analysis techniques for different task models, that have advanced the state-of-the-art. Most of these techniques are typically derived under the assumption of negligible runtime overheads which may not be realistic for modern embedded real-time systems, and hence potentially compromises the guarantees on their correct behaviors. This calls for methods to reason about the functioning of the system under the presence of such overheads as well as to predictably control them. Controlling these overheads may place additional performance demands, consequently requiring more resources such as faster processors. At the same time, the need for energy efficiency in these class of systems further complicates the problem and necessitates a holistic approach.

In this thesis, we apply resource augmentation, viz., processor speed-up, to guarantee desired real-time properties even under the presence of runtime overheads. We specifically consider preemptions and faults that, at runtime, manifest as overheads in the system in various ways. Our aim is to provide specified non-preemption and fault tolerance feasibility guarantees in a real-time system. We first propose offline and online methods, that uses CPU frequency scaling, to control the number of preemptions in periodic and sporadic task systems, under a preemptive Fixed Priority Scheduling (FPS) policy. Furthermore, we derive the resource augmentation bound, specifically the upper-bound on the lowest processor speed, that guarantees the feasibility of a specified non-preemption behavior for any real-time task. We show that, for any task Ti , the resource augmentation bound that guarantees a non- reemptive execution for a specified duration Li , is given by 4Li/Dmin, where Dmin  is the shortest deadline in the task set. Consequently, we show that the upper-bound on the lowest processor speed that guarantees the feasibility of a non-preemptive schedule for the task set is 4Cmax/Dmin, where Cmax  is the largest execution time in the task set. We then propose a method to guarantee specified upper-bounds on the preemption related overheads in the schedule. We first translate the requirements of meeting specified upper-bounds on the preemption related overheads to a set of non-preemption requirements for the task set. The resource augmentation bound in conjunction with a sensitivity analysis is used to calculate the optimal processor speed that guarantees the derived non-preemption requirements, achieving the specified bounds on the preemption related costs. Finally, we derive the resource augmentation bound that guarantees the fault tolerance feasibility of a set of real-time tasks under an error burst of known length. We show that if the error burst length is no longer than half the shortest deadline in the task set, the resource augmentation bound that guarantees fault tolerance feasibility is 6. 

Our contribution bounds the extra resources, specifically the required processor speed-up, that provides specified non-preemption and fault tolerance feasibility guarantees in a real-time system. It allows us to quantify the 'goodness' of non-preemptive scheduling, referred to as its sub-optimality, as compared to an optimal uni-processor scheduling algorithm, in terms of the required processor speed-up that guarantees a non-preemptive schedule for any uni-processor feasible task set. We intend to extend this work to provide non-preemption and fault tolerance feasibility guarantees in multi-processor systems.

Ort, förlag, år, upplaga, sidor
Västerås: Malardalen University, 2012
Serie
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 160
Nationell ämneskategori
Data- och informationsvetenskap
Identifikatorer
urn:nbn:se:mdh:diva-16092 (URN)978-91-7485-086-4 (ISBN)
Presentation
2012-11-30, Kappa, Mälardalens högskola, Västerås, 09:15 (Engelska)
Opponent
Handledare
Tillgänglig från: 2012-11-02 Skapad: 2012-11-01 Senast uppdaterad: 2018-01-12Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Thekkilakattil, AbhilashDobrin, RaduPunnekkat, SasikumarAysan, Huseyin

Sök vidare i DiVA

Av författaren/redaktören
Thekkilakattil, AbhilashDobrin, RaduPunnekkat, SasikumarAysan, Huseyin
Av organisationen
Akademin för innovation, design och teknik
Teknik och teknologier

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

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

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • 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