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

DOI10.1007/S11241-010-9092-7MaRDI QIDQ987535zbMATH OpenOpenAlexFDO

Authors 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

real-time schedulingmultiprocessor systemsoptimal scheduling algorithmssporadic task model

Mathematics Subject Classification ID

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

Recommendations

• An optimal multiprocessor real-time scheduling algorithm
• Conditions for on-line scheduling of hard real-time tasks on multiprocessors
• Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach

Cites work

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

Cited in

(10)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987535)