License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2017.4
URN: urn:nbn:de:0030-drops-73066
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7306/
Go to the corresponding OASIcs Volume Portal

Markovic, Filip ; Carlson, Jan ; Dobrin, Radu

Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling

pdf-format:
OASIcs-WCET-2017-4.pdf (0.5 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{markovic_et_al:OASIcs:2017:7306,
  author =	{Filip Markovic and Jan Carlson and Radu Dobrin},
  title =	{{Tightening the Bounds on Cache-Related Preemption Delay in Fixed Preemption Point Scheduling}},
  booktitle =	{17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)},
  pages =	{4:1--4:11},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-057-6},
  ISSN =	{2190-6807},
  year =	{2017},
  volume =	{57},
  editor =	{Jan Reineke},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7306},
  URN =		{urn:nbn:de:0030-drops-73066},
  doi =		{10.4230/OASIcs.WCET.2017.4},
  annote =	{Keywords: Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach}
}

Keywords: Real-time systems, CRPD Analysis, WCET analysis, Limited Preemptive Scheduling, Fixed Preemption Point Approach
Collection: 17th International Workshop on Worst-Case Execution Time Analysis (WCET 2017)
Issue Date: 2017
Date of publication: 23.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI