License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.WCET.2009.2285
URN: urn:nbn:de:0030-drops-22856
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/2285/
Go to the corresponding OASIcs Volume Portal

Burguière, Claire ; Reineke, Jan ; Altmeyer, Sebastian

Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions

pdf-format:
Burguiere.2285.pdf (0.2 MB)

Abstract

In preemptive real-time systems, scheduling analyses need - in addition to the worst-case execution time - the context-switch cost. In case of preemption, the preempted and the preempting task may interfere on the cache memory. These interferences lead to additional reloads in the preempted task. The delay due to these reloads is referred to as the cache-related preemption delay (CRPD). The CRPD constitutes a large part of the context-switch cost. In this article, we focus on the computation of upper bounds on the CRPD based on the concepts of useful cache blocks (UCBs) and evicting cache blocks (ECBs). We explain how these concepts can be used to bound the CRPD in case of direct-mapped caches. Then we consider set-associative caches with LRU, FIFO, and PLRU replacement. We show potential pitfalls when using UCBs and ECBs to bound the CRPD in case of LRU and
demonstrate that neither UCBs nor ECBs can be used to bound the CRPD in case of FIFO and PLRU. Finally, we sketch a new approach to circumvent these limitations by using the concept of relative competitiveness.

BibTeX - Entry

@InProceedings{burguire_et_al:OASIcs:2009:2285,
  author =	{Claire Burgui{\`e}re and Jan Reineke and Sebastian Altmeyer},
  title =	{{Cache-Related Preemption Delay Computation for Set-Associative Caches - Pitfalls and Solutions}},
  booktitle =	{9th International Workshop on Worst-Case Execution Time Analysis (WCET'09) },
  pages =	{1--11},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-14-9},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{10},
  editor =	{Niklas Holsti},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/2285},
  URN =		{urn:nbn:de:0030-drops-22856},
  doi =		{10.4230/OASIcs.WCET.2009.2285},
  note =	{also published in print by Austrian Computer Society (OCG) with ISBN 978-3-85403-252-6},
  annote =	{Keywords: WCET analysis, caches, set-associative, preemption, CRPD}
}

Keywords: WCET analysis, caches, set-associative, preemption, CRPD
Collection: 9th International Workshop on Worst-Case Execution Time Analysis (WCET'09)
Issue Date: 2009
Date of publication: 26.11.2009

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