mdh.sePublications
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
Resource Augmentation for Fault-Tolerance Feasibility of Real-time Tasks under Error Bursts
Mälardalen University, School of Innovation, Design and Engineering. (IS (Dependability))ORCID iD: 0000-0002-6355-3564
Mälardalen University, School of Innovation, Design and Engineering. (IS)ORCID iD: 0000-0003-4157-3537
Mälardalen University, School of Innovation, Design and Engineering. (IS)ORCID iD: 0000-0001-5269-3900
Mälardalen University, School of Innovation, Design and Engineering. (IS)ORCID iD: 0000-0001-5053-6725
2012 (English)In: Proceedings of the 20th International Conference on Real-Time and Network Systems (RTNS 12), Association for Computing Machinery (ACM), 2012, p. 41-50Conference paper, Published paper (Refereed)
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.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2012. p. 41-50
National Category
Engineering and Technology
Identifiers
URN: urn:nbn:se:mdh:diva-16074DOI: 10.1145/2392987.2392992OAI: oai:DiVA.org:mdh-16074DiVA, id: diva2:563680
Conference
The 20th International Conference on Real-Time and Network Systems, ACM, Pont à Mousson, France
Available from: 2012-10-31 Created: 2012-10-31 Last updated: 2013-12-03Bibliographically approved
In thesis
1. Resource Augmentation for Performance Guarantees in Embedded Real-time Systems
Open this publication in new window or tab >>Resource Augmentation for Performance Guarantees in Embedded Real-time Systems
2012 (English)Licentiate thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Västerås: Malardalen University, 2012
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 160
National Category
Computer and Information Sciences
Identifiers
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 (English)
Opponent
Supervisors
Available from: 2012-11-02 Created: 2012-11-01 Last updated: 2018-01-12Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Thekkilakattil, AbhilashDobrin, RaduPunnekkat, SasikumarAysan, Huseyin

Search in DiVA

By author/editor
Thekkilakattil, AbhilashDobrin, RaduPunnekkat, SasikumarAysan, Huseyin
By organisation
School of Innovation, Design and Engineering
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 79 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