Global scheduling of real-time tasks on multiprocessors based on priority promotion
Publicerad
Författare
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Global Scheduling, Dual Priority, Multi Processors, Schedulability Test, OPA Algorithm