A constant-approximate feasibility test for multiprocessor real-time scheduling

DOI10.1007/s00453-011-9497-2zbMath1247.68033MaRDI QIDQ2428689

Sebastian Stiller, Vincenzo Bonifaci, Alberto Marchetti-Spaccamela

Publication date: 26 April 2012

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11590/381274

zbMATH Keywords

approximation algorithm; multiprocessor; real-time scheduling; feasibility test; earliest deadline first; sporadic task system

Mathematics Subject Classification ID

68M20: Performance evaluation, queueing, and scheduling in the context of computer systems

68W25: Approximation algorithms

Related Items

Assigning sporadic tasks to unrelated machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feasibility problems for recurring tasks on one processor
• Optimal online multiprocessor scheduling of sporadic real-time tasks is impossible
• An analysis of global \texttt{EDF} schedulability for arbitrary-deadline sporadic task systems
• A note on preemptive scheduling of periodic, real-time tasks
• Schedulability analysis of global EDF
• A PTAS for Static Priority Real-Time Scheduling with Resource Augmentation
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
• Optimal rate-based scheduling on multiprocessors
• Optimal time-critical scheduling via resource augmentation