2026-07-23T12:28:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10730 2024-03-06T11:05:04Z ddc:004 open_access

NPM-BUNDLE: Non-Preemptive Multitask Scheduling for Jobs with BUNDLE-Based Thread-Level Scheduling (Artifact) Tessler, Corey Fisher, Nathan Scheduling algorithms Cache Memory Multi-threading Static Analysis The BUNDLE and BUNDLEP scheduling algorithms are cache-cognizant thread-level scheduling algorithms and associated worst case execution time and cache overhead (WCETO) techniques for hard real-time multi-threaded tasks. The BUNDLE-based approaches utilize the inter-thread cache benefit to reduce WCETO values for jobs. Currently, the BUNDLE-based approaches are limited to scheduling a single task. This work aims to expand the applicability of BUNDLE-based scheduling to multiple task multi-threaded task sets. BUNDLE-based scheduling leverages knowledge of potential cache conflicts to selectively preempt one thread in favor of another from the same job. This thread-level preemption is a requirement for the run-time behavior and WCETO calculation to receive the benefit of BUNDLE-based approaches. This work proposes scheduling BUNDLE-based jobs non-preemptively according to the earliest deadline first (EDF) policy. Jobs are forbidden from preempting one another, while threads within a job are allowed to preempt other threads. An accompanying schedulability test is provided, named Threads Per Job (TPJ). TPJ is a novel schedulability test, input is a task set specification which may be transformed (under certain restrictions); dividing threads among tasks in an effort to find a feasible task set. Enhanced by the flexibility to transform task sets and taking advantage of the inter-thread cache benefit, the evaluation shows TPJ scheduling task sets fully preemptive EDF cannot. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Corey Tessler and Nathan Fisher 2019 Is Part Of DARTS, Volume 5, Issue 1, Special Issue of the 31st Euromicro Conference on Real-Time Systems (ECRTS 2019) Article Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DARTS.5.1.2 urn:nbn:de:0030-drops-107306 https://drops.dagstuhl.de/entities/document/10.4230/DARTS.5.1.2 eng https://creativecommons.org/licenses/by/3.0/de/legalcode