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
Improving the Schedulability of Real Time Systems under Fixed Preemption Point Scheduling
Mälardalen University, School of Innovation, Design and Engineering, Embedded Systems.
2018 (English)Licentiate thesis, comprehensive summary (Other academic)
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.

Place, publisher, year, edition, pages
Stockholm: E-Print AB , 2018. , p. 180
Series
Mälardalen University Press Licentiate Theses, ISSN 1651-9256 ; 270
Keywords [en]
Real-Time Systems, Limited Preemptive Scheduling, Fixed Preemption Points Scheduling, Probabilistic response time analysis, Cache-Related Preemption Delay Analysis
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:mdh:diva-39828ISBN: 978-91-7485-390-2 (print)OAI: oai:DiVA.org:mdh-39828DiVA, id: diva2:1218609
Presentation
2018-09-21, Kappa, Mälardalen University, Västerås, 13:15 (English)
Opponent
Supervisors
Available from: 2018-06-15 Created: 2018-06-14 Last updated: 2018-06-15Bibliographically approved
List of papers
1. Probabilistic Response Time Analysis for Fixed Preemption Point Selection
Open this publication in new window or tab >>Probabilistic Response Time Analysis for Fixed Preemption Point Selection
Show others...
2018 (English)In: 13th International Symposium on Industrial Embedded Systems SIES '18, 2018Conference paper, Published paper (Refereed)
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.

Keywords
Real-time systems, Limited Preemptive Scheduling, Fixed Preemption Points Scheduling, Probabilistic Response Time Analysis, Preemption Point Selection
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-39256 (URN)
Conference
13th International Symposium on Industrial Embedded Systems SIES '18, 06 Jun 2018, Graz, Austria
Available from: 2018-05-23 Created: 2018-05-23 Last updated: 2018-06-14Bibliographically approved
2. A Comparison of Partitioning Strategies for Fixed Points-based Limited Preemptive Scheduling
Open this publication in new window or tab >>A Comparison of Partitioning Strategies for Fixed Points-based Limited Preemptive Scheduling
(English)In: IEEE Transactions on Industrial Informatics, ISSN 1551-3203, E-ISSN 1941-0050Article in journal (Refereed) Epub ahead of print
Abstract [en]

The increasing industrial demand for handling complex functionalities has influenced the design of hardware architectures for time critical embedded systems, during the past decade. Multi-core systems facilitate the inclusion of many complex functionalities, while, at the same time, inducing cache related overheads, as well as adding partitioning complexity to the overall system schedulability. One of the efficient paradigms for controlling and reducing the cache related costs in real-time systems is Limited Preemptive Scheduling (LPS), with its particular instance Fixed Preemption Points Scheduling (LP-FPPS), that has been shown to outperform other alternatives as well as has been supported by and investigated in the automotive domain. With respect to the partitioning constraints, Partitioned Scheduling has been widely used to pre-runtime allocate tasks to specific cores, resulting in a predictable cache-related preemption delays estimations. In this paper we propose to integrate LP-FPPS and Partitioned Scheduling on fixed-priority multicore real-time systems in order to increase the overall system schedulability.We define a new joint approach for task partitioning and preemption point selection, that is based on the computation of the maximum blocking tolerance upon each allocation, thus being able to quantify the schedulability of the taskset on each processor. Furthermore, we investigate partitioning strategies based on different heuristics, i.e. First Fit Decreasing and Worst Fit Decreasing, and priority and density taskset orderings. The evaluation performed on randomly generated tasksets shows that in the general case, no single partitioning strategy fully dominates the others. However, the evaluation results reveal that certain partitioning strategies perform significantly better with respect to the overall schedulability for specific taskset characteristics. The results also reveal that the proposed partitioning strategies outperform Fully Preemptive and Non-Preemptive partitioned scheduling in terms of successful partitioning.

Keywords
Real-Time Systems, Partitioned Scheduling, Limited Preemptive Scheduling, Fixed Preemption Points
National Category
Computer Sciences
Research subject
Computer Science
Identifiers
urn:nbn:se:mdh:diva-39827 (URN)10.1109/TII.2018.2848879 (DOI)
Available from: 2018-06-14 Created: 2018-06-14 Last updated: 2018-06-26Bibliographically approved
3. Improved Cache-Related Preemption Delay Estimation for Fixed Preemption Point Scheduling
Open this publication in new window or tab >>Improved Cache-Related Preemption Delay Estimation for Fixed Preemption Point Scheduling
2018 (English)In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Volume 10873, 2018Conference paper, Published paper (Refereed)
Abstract [en]

Cache-Related Preemption Delays (CRPD) can significantly increase tasks’ execution time in preemptive real-time scheduling, potentially jeopardising the system schedulability. In order to reduce the cumulative CRPD, Limited Preemptive Scheduling (LPS) has emerged as a scheduling approach which limits the maximum number of preemptions encountered by real-time tasks, thus decreasing CRPD compared to fully preemptive scheduling. Furthermore, an instance of LPS, called Fixed Preemption Point Scheduling (LP-FPP), defines the exact points where the preemptions are permitted within a task, which enables a more precise CRPD estimation. The majority of the research, in the domain of LP-FPP, estimates CRPD with pessimistic upper bounds, without considering the possible sources of over-approximation: 1) accounting for the infeasible preemption combinations, and 2) accounting for the infeasible cache block reloads. In this paper, we improve the analysis by accounting for those two cases towards a more precise estimation of the CRPD upper bounds. The evaluation of the approach on synthetic tasksets reveals a significant reduction of the pessimism in the calculation of the CRPD upper bounds, compared to the existing approaches.

Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 10873
Keywords
Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-38962 (URN)10.1007/978-3-319-92432-8_6 (DOI)2-s2.0-85049013263 (Scopus ID)9783319924311 (ISBN)
Conference
23rd International Conference on Reliable Software Technologies -Ada-Europe 2018 Ada-Europe-2018 , 18 Jun 2018, Lisbon, Portugal
Available from: 2018-05-08 Created: 2018-05-08 Last updated: 2018-07-05Bibliographically approved
4. Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling
Open this publication in new window or tab >>Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling
2017 (English)In: OpenAccess Series in Informatics, 2017, Vol. 57, p. 41-411Conference paper, Published paper (Refereed)
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.

Keywords
Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach
National Category
Computer Systems
Identifiers
urn:nbn:se:mdh:diva-37013 (URN)10.4230/OASIcs.WCET.2017.4 (DOI)2-s2.0-85037724726 (Scopus ID)9783959770576 (ISBN)
Conference
17th International Workshop on Worst-Case Execution Time Analysis WCET 2017, 27 Jun 2017, Dubrovnik, Croatia
Available from: 2017-11-27 Created: 2017-11-27 Last updated: 2018-06-14Bibliographically approved

Open Access in DiVA

No full text in DiVA

Authority records BETA

Markovic, Filip

Search in DiVA

By author/editor
Markovic, Filip
By organisation
Embedded Systems
Computer Sciences

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 35 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