Optimal Virtual Cluster-based Multiprocessor Scheduling

Arvind Easwaran, Insik Shin, Insup LeearXiv 2020 · arXiv

Introduction

In the realm of real-time multiprocessor systems, scheduling strategies traditionally fall into two camps: partitioned and global. Partitioned scheduling assigns tasks to specific processors, which is simple but often inefficient due to the "bin-packing" problem—where total idle time across processors cannot be utilized by a single large task. Global scheduling allows tasks to migrate, offering better flexibility but frequently suffering from high overhead or poor utilization guarantees.

This paper introduces a middle ground: virtual cluster-based scheduling. By grouping tasks into virtual clusters that are dynamically scheduled across physical processors, the authors provide a framework that achieves high utilization with manageable overhead.

The Virtual Cluster Framework

The core of the proposed approach is the Multiprocessor Periodic Resource (MPR) model. A cluster is defined by the interface $\langle \Pi, \Theta, m' \rangle$, where $\Theta$ is the execution time required every period $\Pi$, utilizing at most $m'$ concurrent processors. This abstraction decouples the cluster's resource needs from the underlying physical hardware.

Key to this framework is the VC-IDT (Virtual Cluster for Implicit-Deadline Tasks) algorithm. Unlike traditional "fair" schedulers like Pfair, which require tasks to execute at a near-constant rate (leading to excessive preemptions), VC-IDT uses McNaughton’s wrap-around algorithm for inter-cluster scheduling. This ensures optimality for implicit-deadline tasks—meaning any task set with total utilization $U \le m$ can be scheduled—while keeping preemption counts significantly lower than Pfair-based systems.

Comparative Analysis of Scheduling Algorithms

The advantages of the virtual cluster approach are best seen when compared to existing global scheduling techniques. Traditional algorithms like Global Earliest Deadline First (gEDF) or US-EDF often leave "gaps" in the schedule or fail to meet deadlines for high-utilization task sets.

Comparison of various multiprocessor scheduling algorithms including gEDF, gLLF, US-EDF, and the proposed cluster-based approach.

As shown in the figure above, the cluster-based approach provides a more structured and efficient allocation of tasks ($\tau_1$ through $\tau_6$) across four processors compared to gEDF/EDZL, gLLF, and FP-EDF/US-EDF. Specifically, the authors demonstrate that virtual clustering can improve the utilization bound of US-EDF from $\frac{m^2}{2m-1}$ to a higher value $\frac{m^2 + \alpha m}{2m-1}$, where $\alpha$ accounts for the load of heavy tasks.

Key Insights and Results

  • Optimality without Fairness: VC-IDT achieves the theoretical maximum utilization ($m$) for implicit-deadline tasks without the overhead of quantum-based fairness.
  • Reduced Overhead: While Pfair might incur $m$ preemptions every time unit, VC-IDT limits preemptions to at most $n$ (the number of tasks) every period $\Pi$.
  • Resource Abstraction: By aligning the cluster period $\Pi$ with the Greatest Common Divisor (GCD) of task periods, the framework eliminates the "abstraction overhead" typically found in hierarchical scheduling.

Conclusion and Future Directions

The virtual cluster-based framework offers a robust solution for high-performance real-time systems. However, its efficiency is currently tied to the GCD of task periods; systems with co-prime periods might experience higher overhead. Future work includes expanding the analysis to other internal schedulers like Rate Monotonic and exploring practical implementations in modern real-time operating systems.

Summary updated

BibTeX
@misc{easwaran2020optimal,
  author = {Arvind Easwaran and Insik Shin and Insup Lee},
  title = {{Optimal Virtual Cluster-based Multiprocessor Scheduling}},
  year = {2020},
  eprint = {2004.02439},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2004.02439},
}

Loading related content...

Figure