(m,k)-firm constraints and DBP scheduling: impact of the initial k-sequence and exact schedulability test

2008/05/02 by Joël Goossens, Goossens, Joël
Computer Science · #Distributed systems and fault tolerance #FOS: Computer and information sciences #Operating Systems (cs.OS) #Petri Nets in System Modeling #Real-Time Systems Scheduling

paper · pdf · doi:10.48550/arxiv.0805.0200

openalex publication_date 2008/05/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper we study the scheduling of (m,k)-firm synchronous periodic task systems using the Distance Based Priority (DBP) scheduler. We first show three phenomena: (i) choosing, for each task, the initial k-sequence 1^k is not optimal, (ii) we can even start the scheduling from a (fictive) error state (in regard to the initial k-sequence) and (iii) the period of feasible DBP-schedules is not necessarily the task hyper-period. We then show that any feasible DBP-schedule is periodic and we upper-bound the length of that period. Lastly, based on our periodicity result we provide an exact schedulability test.

Related

• Exact Feasibility Tests for Real-Time Scheduling of Periodic Tasks upon Multiprocessor Platforms
• Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results
• Exact Schedulability Test for global-EDF Scheduling of Periodic Hard\n Real-Time Tasks on Identical Multiprocessors
• On the periodic behavior of real-time schedulers on identical multiprocessor platforms
• Sufficient FTP Schedulability Test for the Non-Cyclic Generalized Multiframe Task Model