Global scheduling of real-time tasks on multiprocessors based on priority promotion

Abstract

With the widespread deployment of intelligent embedded systems across various application scenarios, the processing capabilities and scheduling strategies of singleprocessor platforms are increasingly unable to meet the growing computational demands of real-time tasks. To host more and more functions with additional processing requirements and stricter real-time constraints, multiprocessor platforms are attracting growing attention and adoption. However, scheduling real-time tasks on multiprocessor platforms still faces many challenges. One major challenge is how to assign priorities in an optimal way for scheduling on multiprocessors. There are many methods for assigning fixed priorities to tasks in multiprocessor systems, but the optimal method is still unclear, and some tasks cannot be scheduled feasibly under fixed-priority assignments. To overcome the limitations of fixed-priority scheduling, it becomes necessary to introduce some form of dynamic priority. Although the schedulers under dynamic-priority may perform better in terms of schedulability, they are significantly more complex to implement than the schedulers under fixed-priority. This leads to another challenge: how to make a compromise between static and dynamic priority behaviour? Dual-priority (DP) scheduling provides a new approach to balance between pure fixed-priority and full dynamic-priority scheduling strategies. In dual-priority scheduling, each task is assigned two priorities: an initial priority and a promoted priority. The task begins execution with the initial priority, and after a fixed duration, which is called priority promotion time, its priority is elevated to the promoted priority. However, to the best of our knowledge, there has been no prior research on applying DP scheduling to multiprocessor platforms. This thesis focuses on the study of global scheduling with priority promotion in multiprocessor systems and proposes a DP scheduling algorithm for multiprocessors, along with two tests to verify schedulability. Furthermore, with a priority assignment algorithm known as Audsley’s optimal priority assignment, we develop a hybrid algorithm where a subset of the tasks will have pure fixed priority, and each of the other tasks will have two priorities: one before the priority promotion point(PPP) and one after the PPP. We have evaluated the proposed test using extensive simulation experiments, and the results demonstrate that the proposed test performs well compared to the existing test.