A Survey of Hard Real-Time Scheduling for Multiprocessor Systems

A Survey of Hard Real-Time Scheduling for Multiprocessor Systems

2010 | ROBERT I. DAVIS AND ALAN BURNS
This survey provides an overview of hard real-time scheduling algorithms and schedulability analysis techniques for homogeneous multiprocessor systems. It reviews key results from the late 1960s to late 2009. The paper outlines fundamental results about multiprocessor real-time scheduling that are independent of specific scheduling algorithms. It provides a taxonomy of scheduling methods and considers performance metrics for comparison. It reviews partitioned, global, and hybrid scheduling algorithms, resource sharing approaches, and empirical results. The survey identifies open issues, research challenges, and future directions. The paper discusses the classification of multiprocessor systems, task models, and scheduling algorithms. It describes metrics for comparing scheduling algorithms and analyses, including utilisation bounds, approximation ratios, resource augmentation, and empirical measures. It presents fundamental results on optimality, feasibility, comparability, predictability, sustainability, and anomalies in multiprocessor scheduling. Partitioned scheduling is reviewed, with a focus on implicit-deadline tasksets and the use of Rate Monotonic (RM) priority assignment. The paper discusses approximation ratios, utilisation bounds, and the challenges of task allocation. It also addresses the critical instant effect, a scheduling anomaly where task parameters can lead to unschedulable tasksets. The paper concludes with an analysis of open issues and future research directions in multiprocessor real-time scheduling.This survey provides an overview of hard real-time scheduling algorithms and schedulability analysis techniques for homogeneous multiprocessor systems. It reviews key results from the late 1960s to late 2009. The paper outlines fundamental results about multiprocessor real-time scheduling that are independent of specific scheduling algorithms. It provides a taxonomy of scheduling methods and considers performance metrics for comparison. It reviews partitioned, global, and hybrid scheduling algorithms, resource sharing approaches, and empirical results. The survey identifies open issues, research challenges, and future directions. The paper discusses the classification of multiprocessor systems, task models, and scheduling algorithms. It describes metrics for comparing scheduling algorithms and analyses, including utilisation bounds, approximation ratios, resource augmentation, and empirical measures. It presents fundamental results on optimality, feasibility, comparability, predictability, sustainability, and anomalies in multiprocessor scheduling. Partitioned scheduling is reviewed, with a focus on implicit-deadline tasksets and the use of Rate Monotonic (RM) priority assignment. The paper discusses approximation ratios, utilisation bounds, and the challenges of task allocation. It also addresses the critical instant effect, a scheduling anomaly where task parameters can lead to unschedulable tasksets. The paper concludes with an analysis of open issues and future research directions in multiprocessor real-time scheduling.
Reach us at info@study.space