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

DOI10.1007/S11241-010-9092-7zbMATH Open1197.68027OpenAlexW2074573349MaRDI QIDQ987535FDOQ987535

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

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

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)

Cites Work

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

Cited In (10)

• Laxity dynamics and LLF schedulability analysis on multiprocessor platforms
• A constant-approximate feasibility test for multiprocessor real-time scheduling
• Online and offline scheduling with cache-related preemption delays
• 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
• {\textsc{DP-Fair}}: a unifying theory for optimal hard real-time multiprocessor scheduling
• {\textsf{LRE}}-{\textsf{TL}}: An optimal multiprocessor algorithm for sporadic task sets with unconstrained deadlines
• Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach
• Energy-efficient thermal-aware multiprocessor scheduling for real-time tasks using TCPN

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)