Optimal virtual cluster-based multiprocessor scheduling
From MaRDI portal
Abstract: Scheduling of constrained deadline sporadic task systems on multiprocessor platforms is an area which has received much attention in the recent past. It is widely believed that finding an optimal scheduler is hard, and therefore most studies have focused on developing algorithms with good processor utilization bounds. These algorithms can be broadly classified into two categories: partitioned scheduling in which tasks are statically assigned to individual processors, and global scheduling in which each task is allowed to execute on any processor in the platform. In this paper we consider a third, more general, approach called cluster-based scheduling. In this approach each task is statically assigned to a processor cluster, tasks in each cluster are globally scheduled among themselves, and clusters in turn are scheduled on the multiprocessor platform. We develop techniques to support such cluster-based scheduling algorithms, and also consider properties that minimize total processor utilization of individual clusters. In the last part of this paper, we develop new virtual cluster-based scheduling algorithms. For implicit deadline sporadic task systems, we develop an optimal scheduling algorithm that is neither Pfair nor ERfair. We also show that the processor utilization bound of US-EDF{m/(2m-1)} can be improved by using virtual clustering. Since neither partitioned nor global strategies dominate over the other, cluster-based scheduling is a natural direction for research towards achieving improved processor utilization bounds.
Recommendations
- Cluster scheduling for real-time systems: utilization bounds and run-time overhead
- Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
- Optimal rate-based scheduling on multiprocessors
- scientific article; zbMATH DE number 1863333
- Deadline-based scheduling of periodic task systems on multiprocessors.
Cites work
- A new algorithm for scheduling periodic, real-time tasks
- An analysis of fixed-priority schedulability on a multiprocessor
- An analysis of global \texttt{EDF} schedulability for arbitrary-deadline sporadic task systems
- Deadline-based scheduling of periodic task systems on multiprocessors.
- Optimal rate-based scheduling on multiprocessors
- Priority-driven scheduling of periodic task systems on multiprocessors
- Proportionate progress: A notion of fairness in resource allocation
- Schedulability analysis of global EDF
- Scheduling with deadlines and loss functions
Cited in
(10)- Laxity dynamics and LLF schedulability analysis on multiprocessor platforms
- scientific article; zbMATH DE number 1863333 (Why is no real title available?)
- ECP: a novel clustering-based technique to schedule precedence constrained tasks on multiprocessor computing systems
- Cache-aware compositional analysis of real-time multicore virtualization platforms
- Preemption-light multiprocessor scheduling of sporadic tasks with high utilisation bound
- Multiprocessor real-time scheduling with arbitrary processor affinities: from practice to theory
- Quasi-partitioned scheduling: optimality and adaptation in multiprocessor real-time systems
- Multiprocessor scheduling by reduction to uniprocessor: an original optimal approach
- The aggregate capacity of virtual resources – linear models
- Multi-cluster co-allocation scheduling algorithms in virtual computing environments
This page was built for publication: Optimal virtual cluster-based multiprocessor scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1039304)
