Integrating job parallelism in real-time scheduling theory

DOI10.1016/J.IPL.2007.11.014MaRDI QIDQ963364zbMATH OpenOpenAlexFDO

Authors Sébastien Collette, Liliana Cucu, Joël Goossens

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0805.3237

zbMATH Keywords

schedulingreal-time systemsparallel systemsmultiprocessor systems

Mathematics Subject Classification ID

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

Abstract: We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the time-complexity of the feasibility problem of these systems is linear relatively to the number of (sporadic) tasks for a fixed number of processors. We propose a scheduling algorithm theoretically optimal (i.e., preemptions and migrations neglected). Moreover, we provide an exact feasibility utilization bound. Lastly, we propose a technique to limit the number of migrations and preemptions.

Recommendations

• Real-time scheduling of linear speedup parallel tasks
• Multiprocessor scheduling for real-time systems
• Non-migratory feasibility and migratory schedulability analysis of multiprocessor real-time systems

Cites work

• scientific article; zbMATH DE number 924427 (Why is no real title available?)
• An analysis of global \texttt{EDF} schedulability for arbitrary-deadline sporadic task systems
• Deadline-based scheduling of periodic task systems on multiprocessors.
• Priority-driven scheduling of periodic task systems on multiprocessors
• Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

Cited in

(11)

• Global EDF scheduling for parallel real-time tasks
• Stretching algorithm for global scheduling of real-time DAG tasks
• Mixed-criticality federated scheduling for parallel real-time tasks
• Analysis techniques for supporting hard real-time sporadic gang task systems
• Scheduling of hard real-time multi-phase multi-thread (MPMT) periodic tasks
• Characterizations of parallel real-time workloads
• Resource sharing among real-time components under multiprocessor clustered scheduling
• Multi-core real-time scheduling for generalized parallel task models
• The limited-preemptive feasibility of real-time tasks on uniprocessors
• Hard Real-Time Stationary GANG-Scheduling.
• T-L plane-based real-time scheduling for homogeneous multiprocessors

Describes a project that uses

Uses Software

• PVM
• MPI

This page was built for publication: Integrating job parallelism in real-time scheduling theory

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