2026-07-25T01:46:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23595 2025-10-27T10:21:53Z ddc:004 open_access

Theoretical Foundations of Utility Accrual for Real-Time Systems Chen, Jian-Jia Shi, Junjie Günzel, Mario von der Brüggen, Georg Chen, Kuan-Hsun Bella, Peter Soft Real-Time Systems Utility Accrual Markov Chains Dismiss Points Providing guaranteed quantification of properties of soft real-time systems is important in practice to ensure that a system performs correctly most of the time. We study utility accrual for real-time systems, in which the utility of a real-time job is defined as a time utility function with respect to its response time. Essentially, we answer the fundamental questions: Does the utility accrual of a periodic real-time task in the long run converge to a single value? If yes, to which value? We first show that concrete problem instances exist where evaluating the utility accrual by simulating the scheduling algorithm or conducting scheduling experiments in a long run is erroneous. Afterwards, we show how to construct a Markov chain to model the interactions between the scheduling policy, the probabilistic workload of a periodic real-time task, the service provided by the system to serve the task, and the effect on the utility accrual. For such a Markov chain, we also provide the theoretical fundamentals to determine whether the utility accrual converges in the long run and the derivation of the utility accrual if it converges. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jian-Jia Chen and Junjie Shi and Mario Günzel and Georg von der Brüggen and Kuan-Hsun Chen and Peter Bella 2025 Is Part Of LIPIcs, Volume 335, 37th Euromicro Conference on Real-Time Systems (ECRTS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2025.17 urn:nbn:de:0030-drops-235950 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2025.17 eng https://creativecommons.org/licenses/by/4.0/legalcode