RefinedProsa: Connecting Response-Time Analysis with C Verification for Interrupt-Free Schedulers
Open Access
- 10 June 2025
- journal article
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 9 (PLDI) , 73-97
Abstract
There has been a recent upsurge of interest in formal, machine-checked verification of timing guarantees for C implementations of real-time system schedulers. However, prior work has only considered tick-based schedulers, which enjoy a clearly defined notion of time: the time "quantum". In this work, we present a new approach to real-time systems verification for interrupt-free schedulers, which are commonly used in deeply embedded and resource-constrained systems but which do not enjoy a natural notion of periodic time. Our approach builds on and connects two recently developed Rocq-based systems—RefinedC (for foundational C verification) and Prosa (for verified response-time analysis)—adapting the former to reason about timed traces and the latter to reason about overheads. We apply the resulting system, which we call RefinedProsa, to verify Rössl, a simple yet representative, fixed-priority, non-preemptive, interrupt-free scheduler implemented in C.Keywords
Funding Information
- ERC (803111)
This publication has 29 references indexed in Scilit:
- Hard Real-Time Computing Systems2024
- CertiCAN certifying CAN analyses and their resultsReal-Time Systems, 2023
- Integrating Formal Schedulability Analysis into a Verified OS Kernel2019
- Many suspensions, many problems: a review of self-suspending tasks in real-time systemsReal-Time Systems, 2018
- Correspondence article: a correction of the reduction-based schedulability analysis for APA schedulingReal-Time Systems, 2018
- Calculating WCET estimates from timed tracesReal-Time Systems, 2015
- OTAWA: An Open Toolbox for Adaptive WCET Analysis2010
- Controller Area Network (CAN) schedulability analysis: Refuted, revisited and revisedReal-Time Systems, 2007
- TinyOS: An Operating System for Sensor Networks2005
- Applying new scheduling theory to static priority pre-emptive schedulingSoftware Engineering Journal, 1993