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

Examensarbete för masterexamen

Please use this identifier to cite or link to this item: https://hdl.handle.net/20.500.12380/255118
Download file(s):
File Description SizeFormat 
255118.pdfFulltext4.68 MBAdobe PDFView/Open
Type: Examensarbete för masterexamen
Master Thesis
Title: Implementation and Evaluation of a Fixed Priority Scheduler based on Priority Promotions for the Linux Kernel
Authors: Ackelman, Christoffer
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.
Keywords: Informations- och kommunikationsteknik;Data- och informationsvetenskap;Information & Communication Technology;Computer and Information Science
Issue Date: 2018
Publisher: Chalmers tekniska högskola / Institutionen för data- och informationsteknik (Chalmers)
Chalmers University of Technology / Department of Computer Science and Engineering (Chalmers)
URI: https://hdl.handle.net/20.500.12380/255118
Collection:Examensarbeten för masterexamen // Master Theses



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.