2026-07-17T13:53:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8994 2024-03-06T10:43:04Z ddc:004 open_access

A Response-Time Analysis for Non-Preemptive Job Sets under Global Scheduling Nasri, Mitra Nelissen, Geoffrey Brandenburg, Björn B. global multiprocessor scheduling schedulability analysis non-preemptive tasks worst-case response time best-case response time An effective way to increase the timing predictability of multicore platforms is to use non-preemptive scheduling. It reduces preemption and job migration overheads, avoids intra-core cache interference, and improves the accuracy of worst-case execution time (WCET) estimates. However, existing schedulability tests for global non-preemptive multiprocessor scheduling are pessimistic, especially when applied to periodic workloads. This paper reduces this pessimism by introducing a new type of sufficient schedulability analysis that is based on an exploration of the space of possible schedules using concise abstractions and state-pruning techniques. Specifically, we analyze the schedulability of non-preemptive job sets (with bounded release jitter and execution time variation) scheduled by a global job-level fixed-priority (JLFP) scheduling algorithm upon an identical multicore platform. The analysis yields a lower bound on the best-case response-time (BCRT) and an upper bound on the worst-case response time (WCRT) of the jobs. In an empirical evaluation with randomly generated workloads, we show that the method scales to 30 tasks, a hundred thousand jobs (per hyperperiod), and up to 9 cores. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mitra Nasri and Geoffrey Nelissen and Björn B. Brandenburg 2018 Is Part Of LIPIcs, Volume 106, 30th Euromicro Conference on Real-Time Systems (ECRTS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ECRTS.2018.9 urn:nbn:de:0030-drops-89941 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2018.9 eng https://creativecommons.org/licenses/by/3.0/legalcode