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 Performance Guarantees in Embedded Real-time Systems
Mälardalen University, School of Innovation, Design and Engineering. (Dependability)ORCID iD: 0000-0002-6355-3564
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 Science
Identifiers
URN: urn:nbn:se:mdh:diva-16092ISBN: 978-91-7485-086-4 (print)OAI: oai:DiVA.org:mdh-16092DiVA: diva2:564504
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: 2013-12-03Bibliographically approved
List of papers
1. Probabilistic Preemption Control using Frequency Scaling for Sporadic Real-time Tasks
Open this publication in new window or tab >>Probabilistic Preemption Control using Frequency Scaling for Sporadic Real-time Tasks
2012 (English)In: 7th IEEE International Symposium on IndustrialEmbedded Systems (SIES): Conference Proceedings, IEEE Computer Society, 2012, 158-165 p.Conference paper, Published paper (Refereed)
Abstract [en]

Preemption related costs are major sources of unpredictability in the task execution times in a real-time system. We examine the possibility of using CPU frequency scaling to control the preemption behavior of real-time sporadic tasks scheduled using a preemptive Fixed Priority Scheduling (FPS) policy. Our combined offline-online method provides probabilistic preemption control guarantees by making use of the release time probabilities of the sporadic tasks. The offline phase derives the probability related deviation from the minimum inter-arrival time of tasks. The online algorithm uses this information to calculate appropriate CPU frequencies that guarantees non-preemptive task executions while preserving the overall system schedulability. The online algorithm has a linear complexity and does not lead to significant implementation overheads. Our evaluations demonstrate the effectiveness of the method as well as the possibility of energy-preemption trade offs. Even though we have considered FPS, our method can easily be extended to dynamic priority scheduling schemes

Place, publisher, year, edition, pages
IEEE Computer Society, 2012
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-16075 (URN)10.1109/SIES.2012.6356581 (DOI)2-s2.0-84871567582 (Scopus ID)978-1-4673-2683-4 (ISBN)
Conference
The 7th IEEE International Symposium on Industrial Embedded Systems, Karlsruhe, Germany, June 20-22, 2012
Available from: 2012-10-31 Created: 2012-10-31 Last updated: 2013-12-03Bibliographically approved
2. Quantifying the Sub-Optimality of Non-Preemptive Real-time Scheduling
Open this publication in new window or tab >>Quantifying the Sub-Optimality of Non-Preemptive Real-time Scheduling
2013 (English)In: Proceedings - Euromicro Conference on Real-Time Systems, 2013, 2013, 113-122 p.Conference paper, Published paper (Other academic)
Abstract [en]

A number of preemptive real-time scheduling algorithms, such as Earliest Deadline First (EDF), are known to be optimal on uni-processor systems under specified assumptions. However, no uni-processor optimal algorithm exists under the non-preemptive scheduling paradigm. Hence preemptive schemes strictly dominate non-preemptive schemes with respect to uni-processor feasibility. However, the 'goodness' of non-preemptive schemes, compared to uni-processor optimal preemptive scheduling schemes such as EDF, which can also be referred to as its sub-optimality, has not been fully investigated yet. In this paper, we apply resource augmentation, specifically processor speed-up, to quantify the sub-optimality of non-preemptive scheduling with respect to EDF, and apply the results to guarantee user specified upper-bounds on the preemption related scheduling costs. In particular, we derive an upper bound on the minimum processor speed-up required to guarantee the non-preemptive feasibility of tasks that are deemed feasible under the preemptive EDF, and we prove that, in the cases where, for all tasks in the task set, the largest execution requirement is not greater than the shortest deadline, this bound is equal to 4. We also show how the proposed approach enables a system designer to choose an optimal processor, in order to, e.g., guarantee specified upper bounds on the preemption related overheads.

National Category
Computer and Information Science
Identifiers
urn:nbn:se:mdh:diva-16091 (URN)10.1109/ECRTS.2013.22 (DOI)000333895000012 ()2-s2.0-84885234311 (Scopus ID)9780769550541 (ISBN)
Conference
25th Euromicro Conference on Real-Time Systems, ECRTS 2013; Paris; France; 9 July 2013 through 12 July 2013
Available from: 2012-11-01 Created: 2012-11-01 Last updated: 2015-11-12Bibliographically approved
3. Resource Augmentation for Fault-Tolerance Feasibility of Real-time Tasks under Error Bursts
Open this publication in new window or tab >>Resource Augmentation for Fault-Tolerance Feasibility of Real-time Tasks under Error Bursts
2012 (English)In: Proceedings of the 20th International Conference on Real-Time and Network Systems (RTNS 12), Association for Computing Machinery (ACM), 2012, 41-50 p.Conference 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
National Category
Engineering and Technology
Identifiers
urn:nbn:se:mdh:diva-16074 (URN)10.1145/2392987.2392992 (DOI)
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
4. Reducing the Number of Preemptions in Real-Time Systems Scheduling by CPU Frequency Scaling
Open this publication in new window or tab >>Reducing the Number of Preemptions in Real-Time Systems Scheduling by CPU Frequency Scaling
2010 (English)In: 18th International Conference on Real-Time and Network Systems, Toulouse, France, 2010Conference paper, Published paper (Refereed)
Abstract [en]

Controlling the number of preemptions in real-time systems is highly desirable in order to achieve an efficient system design in multiple contexts. For example, the delays due to context switches account for high preemption overheads which detrimentally impact the system schedulability. Preemption avoidance can also be potentially used for the efficient control of critical section behaviors in multi-threaded applications. At the same time, modern processor architectures provide for the ability to selectively choose operating frequencies, primarily targeting energy efficiency as well as system performance. In this paper, we propose the use of CPU Frequency Scaling for controlling the preemptive behavior of real-time tasks. We present a framework for selectively eliminating preemptions, that does not require modifications to the task attributes or to the underlying scheduler. We evaluate the proposed approach by four different heuristics through extensive simulation studies.

Place, publisher, year, edition, pages
Toulouse, France: , 2010
Identifiers
urn:nbn:se:mdh:diva-10872 (URN)
Available from: 2010-11-10 Created: 2010-11-10 Last updated: 2013-12-03Bibliographically approved

Open Access in DiVA

fulltext(548 kB)347 downloads
File information
File name FULLTEXT02.pdfFile size 548 kBChecksum SHA-512
8a9e7f695bef809cdcba75ca789a7a33e1c06022c1a0f1da3d00dfe06c99330c948f37dc3f26b3cf9968b37a647199559ef174352250ed31dacb28f173cae0c8
Type fulltextMimetype application/pdf

Search in DiVA

By author/editor
Thekkilakattil, Abhilash
By organisation
School of Innovation, Design and Engineering
Computer and Information Science

Search outside of DiVA

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