Integrating Job Parallelism in Real-Time Scheduling Theory

2008/05/21 by Collette, S., Cucu, L., Goossens, J.
#FOS: Computer and information sciences #Operating Systems (cs.OS)

paper · doi:10.48550/arxiv.0805.3237

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.

Related

• Push Forward: Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems
• On the Design of an Optimal Multiprocessor Real-Time Scheduling Algorithm under Practical Considerations (Extended Version)
• Semi-Partitioned Hard Real-Time Scheduling with Restricted Migrations upon Identical Multiprocessor Platforms
• Partitioned Multiprocessor Fixed-Priority Scheduling of Sporadic Real-Time Tasks
• An Optimal Real-Time Scheduling Approach: From Multiprocessor to Uniprocessor