2026-09-30T21:36:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26605 2026-09-29T14:37:27Z ddc:004 open_access

CacheFlow: Using Maximum Flow to Bound Cache-Based Preemption Delays He, Tiancheng Ward, Bryan C. Cache-related Preemption Delay Real-Time Systems Maximum Flow Cache-related preemption delay (CRPD) analysis bounds the additional execution time caused by cache evictions during preemptions. Tightly bounding CRPDs is challenging as there are many possible preemption patterns that can occur at runtime, and thus there has been continuous work over three decades to refine these bounds. This paper presents CacheFlow, a framework that formulates total CRPD as a maximum-flow problem. In the flow network, nodes and edge capacities can be constructed to model certain eviction patterns that can occur. Therefore, by (safely) removing nodes or edges, or reducing edge capacities, tighter CRPD bounds can be derived. This is demonstrated with different CacheFlow refinements, some of which include insights from prior analyses, as well as a refinement for simply periodic systems. An iterative max-flow formulation is also described to more efficiently integrate the max-flow solving in the context of standard fixed-priority response-time analysis. Experiments on synthetic task systems demonstrate significant schedulability improvements across a range of system configurations, while also having reasonable solving times. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tiancheng He and Bryan C. Ward 2026 Is Part Of LIPIcs, Volume 375, 38th European Conference on Real-Time Systems (ECRTS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2026.13 urn:nbn:de:0030-drops-266058 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode