Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible

DOI10.1007/S11241-010-9092-7zbMath1197.68027OpenAlexW2074573349MaRDI QIDQ987535

Nathan Fisher, Joël Goossens, Sanjoy K. Baruah

Publication date: 13 August 2010

Published in: Real-Time Systems (Search for Journal in Brave)

Full work available at URL: https://cdr.lib.unc.edu/downloads/5h73q507x

zbMATH Keywords

multiprocessor systemsreal-time schedulingoptimal scheduling algorithmssporadic task model

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Online algorithms; streaming algorithms (68W27)

Related Items (10)

Online and offline scheduling with cache-related preemption delays ⋮ Energy-efficient thermal-aware multiprocessor scheduling for real-time tasks using TCPN ⋮ {\textsf{LRE}}-{\textsf{TL}}: An optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines ⋮ A constant-approximate feasibility test for multiprocessor real-time scheduling ⋮ {\textsc{DP-Fair}}: a unifying theory for optimal hard real-time multiprocessor scheduling ⋮ An optimal boundary fair scheduling algorithm for multiprocessor real-time systems ⋮ Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound ⋮ Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory ⋮ Laxity dynamics and LLF schedulability analysis on multiprocessor platforms ⋮ Feasibility analysis of sporadic real-time multiprocessor task systems

Cites Work

• Unnamed Item
• Feasibility problems for recurring tasks on one processor
• The feasibility of general task systems with precedence constraints on multiprocessor platforms
• Dynamic- and static-priority scheduling of recurring real-time tasks
• Proportionate progress: A notion of fairness in resource allocation
• Impossibility of distributed consensus with one faulty process
• On the complexity of fixed-priority scheduling of periodic, real-time tasks
• On a Real-Time Scheduling Problem
• Some simple scheduling algorithms
• Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline Tasks
• Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
• Optimal rate-based scheduling on multiprocessors
• Optimal time-critical scheduling via resource augmentation

This page was built for publication: Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible