Implementation and Evaluation of a Fixed Priority Scheduler based on Priority Promotions for the Linux Kernel

Abstract

Priority promotions is a mechanism to make the priorities in a fixed priority schedulers more dynamic. The purpose of this thesis was to investigate whether the Fixed Priority with Priority Promotions (FPP) scheduler, which is uses a number of priority promotions to generate an Earliest Deadline First (EDF) schedule, is an effective strategy for reducing the overhead of real-time EDF schedulers when implemented on a real platform. To investigate, the FPP scheduler, a “standard” EDF scheduler based on a binary heap, and an EDF scheduler based on a Red-Black Tree were implemented. The FPP scheduler was then benchmarked against the standard EDF scheduler, but also against the rather mature and optimized EDF scheduler in the Linux kernel, SCHED_DEADLINE, which is based on a Red-Black Tree. The hypothesis was that the FPP scheduler would perform better than the binaryheap based EDF scheduler, but that it would be inferior to SCHED_DEADLINE since this scheduler has been developed and improved over several years by many very competent developers. The first results showed that the implemented FPP and EDF schedulers were largely incomparable to SCHED_DEADLINE with regard to the release and scheduling overheads. Thus, the second EDF scheduler using the Red-Black Tree from SCHED_DEADLINE was developed. The results showed that the FPP scheduler outperform both the heap based and Red-Black Tree based EDF schedulers implemented in this thesis. It was concluded that FPP is an effective strategy for reducing the overhead of EDF schedulers, even for very optimized implementations of EDF, when implemented on real platforms.