Brain Fuck Scheduler

The Brain Fuck Scheduler (BFS) is a process scheduler designed for the Linux kernel in August 2009 based on earliest eligible virtual deadline first scheduling (EEVDF), as an alternative to the Completely Fair Scheduler (CFS) and the O(1) scheduler. BFS was created by Con Kolivas.

The objective of BFS, compared to other schedulers, is to provide a scheduler with a simpler algorithm, that does not require adjustment of heuristics or tuning parameters to tailor performance to a specific type of computational workload. Kolivas asserted that these tunable parameters were difficult for the average user to understand, especially in terms of interactions of multiple parameters with each other, and claimed that the use of such tuning parameters could often result in improved performance in a specific targeted type of computation, at the cost of worse performance in the general case. BFS has been reported to improve responsiveness on Linux desktop computers with fewer than 16 cores.

Shortly following its introduction, the new scheduler made headlines within the Linux community, appearing on Slashdot, with reviews in Linux Magazine and Linux Pro Magazine. Although there have been varied reviews of improved performance and responsiveness, Con Kolivas did not intend for BFS to be integrated into the mainline kernel.

The name "Brain Fuck Scheduler" was intentionally provocative, chosen by its creator Con Kolivas to express frustration with the complexity of existing Linux process schedulers at the time. Kolivas aimed to highlight how the proliferation of tunable parameters and heuristic-based designs in other schedulers, such as the Completely Fair Scheduler (CFS), made them difficult for non-experts to understand or optimize. In contrast, BFS was designed with simplicity and predictability in mind, targeting improved desktop interactivity and responsiveness without requiring user-level configuration.

In 2009, BFS was introduced and had originally used a doubly linked list data structure, but the data structure is treated like a queue. Task insertion is ⁠${\displaystyle O(1)}$⁠. Task search for next task to execute is ⁠${\displaystyle O(n)}$⁠ worst case. It uses a single global run queue which all CPUs use. Tasks with higher scheduling priorities get executed first. Tasks are ordered (or distributed) and chosen based on the virtual deadline formula in all policies except for the realtime and Isochronous priority classes.

The execution behavior is still a weighted variation of the Round-Robin Scheduler especially when tasks have the same priority below the Isochronous policy. The user tuneable round robin interval (time slice) is 6 milliseconds by default which was chosen as the minimal jitter just below detectable by humans. Kolivas claimed that anything below the 6 ms was pointless and anything above 300 ms for the round robin timeslice is fruitless in terms of throughput. This important tuneable can tailor the round robin scheduler as a trade off between throughput and latency. All tasks get the same time slice with the exception of realtime FIFO which is assumed to have infinite time slice.

Kolivas explained the reason why he choose to go with the doubly linked list mono-runqueue than the multi-runqueue (round robin) priority array per CPU that was used in his RDSL scheduler was to put to ease fairness among the multiple CPU scenario and remove complexity that each runqueue in a multi-runqueue scenario had to maintain its own latencies and [task] fairness. He claimed that deterministic latencies was guaranteed with BFS in his later iteration of MuQSS. He also recognized possible lock contention problem (related to the altering, removal, creation of task node data) with increasing CPUs and the overhead of ⁠${\displaystyle O(\log n)}$⁠ next task for execution lookup. MuQSS tried to resolve those problems.

Kolivas later changed the design to a skip list in the v0.480 release of BFS in 2016. This time this altered the efficiency of the scheduler. He noted ⁠${\displaystyle O(\log n)}$⁠ task insertion, ⁠${\displaystyle O(1)}$⁠ task lookup; ⁠${\displaystyle O(k)}$⁠, with ⁠${\displaystyle k\leq 16}$⁠, for task removal.