mdh.sePublikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.ORCID-id: 0000-0002-8461-0230
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.ORCID-id: 0000-0003-4157-3537
2017 (engelsk)Inngår i: OpenAccess Series in Informatics, 2017, Vol. 57, s. 41-411Konferansepaper, Publicerat paper (Fagfellevurdert)
Abstract [en]

Limited Preemptive Fixed Preemption Point scheduling (LP-FPP) has the ability to decrease and control the preemption-related overheads in the real-time task systems, compared to other limited or fully preemptive scheduling approaches. However, existing methods for computing the preemption overheads in LP-FPP systems rely on over-approximation of the evicting cache blocks (ECB) calculations, potentially leading to pessimistic schedulability analysis. In this paper, we propose a novel method for preemption cost calculation that exploits the benefits of the LP-FPP task model both at the scheduling and cache analysis level. The method identifies certain infeasible preemption combinations, based on analysis on the scheduling level, and combines it with cache analysis information into a constraint problem from which less pessimistic upper bounds on cache-related preemption delays (CRPD) can be derived. The evaluation results indicate that our proposed method has the potential to significantly reduce the upper bound on CRPD, by up to 50% in our experiments, compared to the existing over-approximating calculations of the eviction scenarios.

sted, utgiver, år, opplag, sider
2017. Vol. 57, s. 41-411
Emneord [en]
Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach
HSV kategori
Identifikatorer
URN: urn:nbn:se:mdh:diva-37013DOI: 10.4230/OASIcs.WCET.2017.4Scopus ID: 2-s2.0-85037724726ISBN: 9783959770576 (tryckt)OAI: oai:DiVA.org:mdh-37013DiVA, id: diva2:1160392
Konferanse
17th International Workshop on Worst-Case Execution Time Analysis WCET 2017, 27 Jun 2017, Dubrovnik, Croatia
Tilgjengelig fra: 2017-11-27 Laget: 2017-11-27 Sist oppdatert: 2018-06-14bibliografisk kontrollert
Inngår i avhandling
1. Improving the Schedulability of Real Time Systems under Fixed Preemption Point Scheduling
Åpne denne publikasjonen i ny fane eller vindu >>Improving the Schedulability of Real Time Systems under Fixed Preemption Point Scheduling
2018 (engelsk)Licentiatavhandling, med artikler (Annet vitenskapelig)
Abstract [en]

During the past decades of research in Real-Time systems, non-preemptive scheduling and fully preemptive scheduling have been extensively investigated, as well as compared with each other. However, it has been shown that none of the two scheduling paradigms dominates over the other in terms of schedulability. In this context, Limited Preemptive Scheduling (LPS) has emerged as an attractive alternative with respect to, e.g., increasing the overall system schedu- lability, efficiently reducing the blocking by lower priority tasks (compared to non-preemptive scheduling) as well as efficiently controlling the number of preemptions, thus controlling the overall preemption-related delay (compared to fully-preemptive scheduling).

Several approaches within LPS enable the above mentioned advantages. In our work, we consider the Fixed Preemption Point Scheduling (LP-FPP) as it has been proved to effectively reduce the preemption-related delay compared to other LPS approaches. In particular, LP-FPP facilitates more precise estimation of the preemption-related delays, since the preemption points of a task in LP-FPP are explicitly selected during the design phase, unlike the other LPS approaches where the preemption points are determined at runtime.

The main goal of the proposed work is to improve the schedulability of real-time systems under the LP-FPP approach. We investigate its use in different domains, such as: single core hard real-time systems, partitioned multi-core systems and real-time systems which can occasionally tolerate deadline misses. We enrich the state of the art for the single core hard real-time systems by proposing a novel cache-related preemption delay analysis, towards reducing the pessimism of the previously proposed methods. In the context of partitioned multi-core scheduling we propose a novel partitioning criterion for the Worst-Fit Decreasing based partitioning, and we also contribute with the comparison of existing partitioning strategies for LP-FPP scheduling. Finally, in the context of real-time systems which can occasionally tolerate deadline misses, we contribute with a probabilistic response time analysis for LP-FPP scheduling and a preemption point selection method for reducing the deadline-misses of the tasks.

sted, utgiver, år, opplag, sider
Stockholm: E-Print AB, 2018. s. 180
Serie
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 270
Emneord
Real-Time Systems, Limited Preemptive Scheduling, Fixed Preemption Points Scheduling, Probabilistic response time analysis, Cache-Related Preemption Delay Analysis
HSV kategori
Forskningsprogram
datavetenskap
Identifikatorer
urn:nbn:se:mdh:diva-39828 (URN)978-91-7485-390-2 (ISBN)
Presentation
2018-09-21, Kappa, Mälardalen University, Västerås, 13:15 (engelsk)
Opponent
Veileder
Tilgjengelig fra: 2018-06-15 Laget: 2018-06-14 Sist oppdatert: 2018-08-20bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekstScopus

Personposter BETA

Markovic, FilipCarlson, JanDobrin, Radu

Søk i DiVA

Av forfatter/redaktør
Markovic, FilipCarlson, JanDobrin, Radu
Av organisasjonen

Søk utenfor DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric

doi
isbn
urn-nbn
Totalt: 10 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf