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
Quantifying the Sub-Optimality of Non-Preemptive Real-time Scheduling
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (IS (Dependability))ORCID iD: 0000-0002-6355-3564
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (IS)ORCID iD: 0000-0003-4157-3537
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems. (IS)ORCID iD: 0000-0001-5269-3900
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.

Place, publisher, year, edition, pages
2013. 113-122 p.
National Category
Computer and Information Science
Identifiers
URN: urn:nbn:se:mdh:diva-16091DOI: 10.1109/ECRTS.2013.22ISI: 000333895000012Scopus ID: 2-s2.0-84885234311ISBN: 9780769550541 (print)OAI: oai:DiVA.org:mdh-16091DiVA: diva2:564498
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
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 Science
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: 2013-12-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Thekkilakattil, AbhilashDobrin, RaduPunnekkat, Sasikumar
By organisation
Embedded Systems
Computer and Information Science

Search outside of DiVA

GoogleGoogle Scholar

Altmetric score

Total: 64 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