Linux High Throughput Fair Scheduler

HTFS is a Completly Fair Scheduler (CFS) replacement for servers. I developed it for my bachelor thesis. The idea was to have a fair scheduler with a complexity class of O(1). The design supports most of the kernel scheduler features, including taskgroups. This is the release of my bachelor thesis, all measurements and the HTFS kernel patch. I am not continuing to develope this scheduler as it is more important to reduce calculation- and contextswitch-overheads than reducing the complexity class.


The server market is continously growing to fullfill the demands of cloud com- puting, internet related servers, like HTTP or Email server, high throughput computing and much more. To reach the highest possible ressource utilization, modern operating system kernels are highly optimized. This also is the case for the Linux CPU scheduler. But especially for servers the Completely Fair Scheduler has some performance flaws. In this bachelor thesis a new CPU-scheduler design is proposed. The High Throughput Fair Scheduler (HTFS) is a multi-queue design, which is able to fullfill O(1) limitations. To assure fairness to all tasks this classical queue- design is extended with virtual runtimes. Through a non-strict fairness HTFS can work with less task switches, which results in higher throughput. HTFS, aimed at high scheduling speed, fairness and throughput, is able to compete with the Linux version 2.6.38 CPU-scheduler.


Thanks to Matthias Grawinkel, Tobias Beisel and Andre Brinkmann for suppoting me.