Multiprocessor schedulability of arbitrary-deadline sporadic tasks: complexity and antichain algorithm

DOI10.1007/s11241-012-9172-yzbMath1291.68081OpenAlexW2036749964MaRDI QIDQ2251369

Gilles Geeraerts, Markus Lindström, Joël Goossens

Publication date: 14 July 2014

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

Full work available at URL: https://doi.org/10.1007/s11241-012-9172-y

zbMATH Keywords

complexityautomata theorymultiprocessor schedulingformal methodssporadic taskshard real-time schedulingexact schedulability test

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items

On the ineffectiveness of \(1/m\)-based interference bounds in the analysis of global EDF and FIFO scheduling, A pre-order relation for exact schedulability test of sporadic tasks on multiprocessor global fixed-priority scheduling, Synthesising succinct strategies in safety games with an application to real-time scheduling, Unnamed Item

Uses Software

• Antichains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Feasibility analysis of sporadic real-time multiprocessor task systems
• Priority-driven scheduling of periodic task systems on multiprocessors
• Task automata: Schedulability, decidability and undecidability
• Antichain Algorithms for Finite Automata
• An Antichain Algorithm for LTL Realizability
• Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline Tasks
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment
• Antichains: A New Algorithm for Checking Universality of Finite Automata