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
Probabilistic Response Time Analysis for Fixed Preemption Point Selection
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
Ericsson, Stockholm, Sweden.ORCID-id: 0000-0002-6355-3564
Mälardalens högskola, Akademin för innovation, design och teknik, Inbyggda system.ORCID-id: 0000-0003-4157-3537
Visa övriga samt affilieringar
2018 (Engelska)Ingår i: 13th International Symposium on Industrial Embedded Systems SIES '18, 2018, artikel-id 8442099Konferensbidrag, Publicerat paper (Refereegranskat)
Abstract [en]

Preemption point selection has a significant impact on the schedulability of Real-Time tasks under the Fixed Preemption Point approach in Limited Preemptive Scheduling. Many real time systems can occasionally tolerate deadline misses as long as their occurrence does not exceed a specified probabilistic threshold. However, the existing approaches for preemption point selection are inappropriate for such systems, as they are mainly aiming to provide hard guarantees, considering worst case (upper bounded) preemption overheads. Additionally, the worst case preemption overheads typically occur with very low probabilities. In this paper, we propose a novel preemption point selection approach, and an associated probabilistic response time analysis, considering preemption related overheads modelled as probabilistic distributions. The method is suitable for providing solutions in systems that can occasionally tolerate deadline misses and can be interesting in the context of mixed criticality systems. Our method is able to find solutions, in terms of preemption point selections, in all cases where the existing approaches do. Moreover, it provides preemption point selections for additional tasksets that guarantees the overall taskset schedulability with a certain probability. The evaluation results show an improvement with respect to increasing the number of tasksets for which a preemption point selection is possible compared to existing, upper-bound based, selection approaches. The results show that the deadline miss probabilities of the tasksets and associated preemption point selections are considerably low.

Ort, förlag, år, upplaga, sidor
2018. artikel-id 8442099
Nyckelord [en]
Real-time systems, Limited Preemptive Scheduling, Fixed Preemption Points Scheduling, Probabilistic Response Time Analysis, Preemption Point Selection
Nationell ämneskategori
Datorsystem
Identifikatorer
URN: urn:nbn:se:mdh:diva-39256DOI: 10.1109/SIES.2018.8442099Scopus ID: 2-s2.0-85053475648ISBN: 9781538641552 (tryckt)OAI: oai:DiVA.org:mdh-39256DiVA, id: diva2:1209686
Konferens
13th International Symposium on Industrial Embedded Systems SIES '18, 06 Jun 2018, Graz, Austria
Tillgänglig från: 2018-05-23 Skapad: 2018-05-23 Senast uppdaterad: 2018-09-27Bibliografiskt granskad
Ingår i avhandling
1. Improving the Schedulability of Real Time Systems under Fixed Preemption Point Scheduling
Öppna denna publikation i ny flik eller fönster >>Improving the Schedulability of Real Time Systems under Fixed Preemption Point Scheduling
2018 (Engelska)Licentiatavhandling, sammanläggning (Övrigt vetenskapligt)
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.

Ort, förlag, år, upplaga, sidor
Stockholm: E-Print AB, 2018. s. 180
Serie
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 270
Nyckelord
Real-Time Systems, Limited Preemptive Scheduling, Fixed Preemption Points Scheduling, Probabilistic response time analysis, Cache-Related Preemption Delay Analysis
Nationell ämneskategori
Datavetenskap (datalogi)
Forskningsämne
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 (Engelska)
Opponent
Handledare
Tillgänglig från: 2018-06-15 Skapad: 2018-06-14 Senast uppdaterad: 2018-08-20Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltextScopus

Personposter BETA

Markovic, FilipCarlson, JanThekilakkattil, AbhilashDobrin, RaduLisper, Björn

Sök vidare i DiVA

Av författaren/redaktören
Markovic, FilipCarlson, JanThekilakkattil, AbhilashDobrin, RaduLisper, Björn
Av organisationen
Inbyggda system
Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetricpoäng

doi
isbn
urn-nbn
Totalt: 32 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