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.
Theoretical design and efficiency
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 . Task search for next task to execute is 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 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 task insertion, task lookup; , with , for task removal.
Virtual deadline
The virtual deadline formula is a future deadline time that is the scaled round robin timeslice based on the nice level offset by the current time (in niffy units or nanosecond jiffies, an internal kernel time counter). The virtual deadline only suggests the order but does not guarantee that a task will run exactly on the future scheduled niffy.
First a prio ratios lookup table is created. It is based on a recursive sequence. It increases 10% each nice level. It follows a parabolic pattern if graphed, and the niced tasks are distributed as a moving squared function from 0 to 39 (corresponding from highest to lowest nice priority) as the domain and 128 to 5089 as the range. The moving part comes from the variable in the virtual deadline formula that Kolivas hinted.
Index Numerator 0 128 1 140 2 154 3 169 4 185 5 203 6 223 7 245 8 269 9 295 10 324 11 356 12 391 13 430 14 473 15 520 16 572 17 629 18 691 19 760 20 836 21 919 22 1010 23 1111 24 1222 25 1344 26 1478 27 1625 28 1787 29 1965 30 2161 31 2377 32 2614 33 2875 34 3162 35 3478 36 3825 37 4207 38 4627 39 5089
The task's nice-to-index mapping function is mapped from nice −20...19 to index 0...39 to be used as the input to the prio ratio lookup table. This mapping function is the macro in sched.h in the kernel header. The internal kernel implementation slightly differs with range between 100 and 140 static priority but users will see it as −20...19 nice.
Nice Index −20 0 −19 1 −18 2 −17 3 −16 4 −15 5 −14 6 −13 7 −12 8 −11 9 −10 10 −9 11 −8 12 −7 13 −6 14 −5 15 −4 16 −3 17 −2 18 −1 19 0 20 1 21 2 22 3 23 4 24 5 25 6 26 7 27 8 28 9 29 10 30 11 31 12 32 13 33 14 34 15 35 16 36 17 37 18 38 19 39
The virtual deadline is based on this exact formula:
Alternatively,
where is the virtual deadline in u64 integer nanoseconds as a function of nice and which is the current time in niffies, is the prio ratio table lookup as a function of index, is the task's nice-to-index mapping function, is the round robin timeslice in milliseconds, is a constant of 1 millisecond in terms of nanoseconds as a latency reducing approximation of the conversion factor of but Kolivas uses a base 2 constant with approximately that scale. Smaller values of mean that the virtual deadline is earlier corresponding to negative nice values. Larger values of indicate the virtual deadline is pushed back later corresponding to positive nice values. It uses this formula whenever the timeslice expires.
128 in base 2 corresponds to 100 in base 10 and possibly a "pseudo 100". 115 in base 2 corresponds to 90 in base 10. Kolivas uses 128 for "fast shifts", as in division is right shift base 2.
Nice Virtual deadline in timeslices relative to Virtual deadline in exact seconds relative to −20 1.0 0.006 −19 1.09 0.006562 −18 1.2 0.007219 −17 1.3 0.007922 −16 1.4 0.008672 −15 1.5 0.009516 −14 1.7 0.010453 −13 1.9 0.011484 −12 2.1 0.012609 −11 2.3 0.013828 −10 2.5 0.015187 −9 2.7 0.016688 −8 3.0 0.018328 −7 3.3 0.020156 −6 3.6 0.022172 −5 4.0 0.024375 −4 4.4 0.026812 −3 4.9 0.029484 −2 5.3 0.032391 −1 5.9 0.035625 0 6.5 0.039188 1 7.1 0.043078 2 7.8 0.047344 3 8.6 0.052078 4 9.5 0.057281 5 10.5 0.063000 6 11.5 0.069281 7 12.6 0.076172 8 13.9 0.083766 9 15.3 0.092109 10 16.8 0.101297 11 18.5 0.111422 12 20.4 0.122531 13 22.4 0.134766 14 24.7 0.148219 15 27.1 0.163031 16 29.8 0.179297 17 32.8 0.197203 18 36.1 0.216891 19 39.7 0.238547
Scheduling policies
BFS uses scheduling policies to determine how much of the CPU tasks may use. BFS uses 4 scheduling tiers (called scheduling policies or scheduling classes) ordered from best to worst which determines how tasks are selected with the ones on top being executed first.
Each task has a special value called a prio. In the v0.462 edition (used in the -ck 4.0 kernel patchset), there are total of 103 "priority queues" ( prio) or allowed values that it can take. No actual special data structure was used as the priority queue but only the doubly linked list runqueue itself. The lower prio value means it is more important and gets executed first.
Realtime policy
The realtime policy was designed for realtime tasks. This policy implies that the running tasks cannot be interrupted (i.e. preempted) by the lower prio-ed task or lower priority policy tiers. Priority classes considered under the realtime policy by the scheduler are those marked SCHED_RR and SCHED_FIFO. The scheduler treats realtime round robin (SCHED_RR) and realtime FIFO (SCHED_FIFO) differently.
The design laid out first 100 static priority queues.
The task that will get chosen for execution is based on task availability of the lowest value of prio of the 100 queues and FIFO scheduling.
On forks, the process priority will be demoted to normal policy.
On unprivileged use (i.e. non-root user) of sched_setscheduler called with a request for realtime policy class, the scheduler will demote the task to Isochronous policy.
Isochronous policy
The Isochronous policy was designed for near realtime performance for non-root users.
The design laid out 1 priority queue that by default ran as pseudo-realtime tasks, but can be tuned as a degree of realtime.
The behavior of the policy can allow a task can be demoted to normal policy when it exceeds a tuneable resource handling percentage (70% by default) of 5 seconds scaled to the number of online CPUs and the timer resolution plus 1 tick. The formula was altered in MuQSS due to the multi-runqueue design. The exact formulas are:
where is the total number of isochronous ticks, is the timer frequency, is the number of online CPUs, is the tuneable resource handling percentage not in decimal but as a whole number. The timer frequency is set to 250 by default and editable in the kernel, but usually tuned to 100 Hz for servers and 1000 Hz for interactive desktops. 250 is the balanced value. Setting to 100 made tasks behave as realtime and 0 made it not pseudo-realtime and anything in the middle was pseudo-realtime.
The task that had an earliest virtual deadline was chosen for execution, but when multiple Isochronous tasks are in existence, they schedule as round robin allowing tasks to run the tuneable round robin value (with 6 ms as the default) one after another in a fair equal chance without considering the nice level.
This behavior of the Isochronous policy is unique to only BFS and MuQSS and may not be implemented in other CPU schedulers.
Normal policy
The normal policy was designed for regular use and is the default policy. Newly created tasks are typically marked normal.
The design laid out one priority queue and tasks are chosen to be executed first based on earliest virtual deadline.
Idle priority policy
The idle priority was designed for background processes such as distributed programs and transcoders so that foreground processes or those above this scheduling policy can run uninterrupted.
The design laid out 1 priority queue and tasks can be promoted to normal policy automatically to prevent indefinite resource hold.
The next executed task with Idle priority with others residing in the same priority policy is selected by the earliest virtual deadline.
Preemption
Preemption can occur when a newly ready task with a higher priority policy (i.e. higher prio) has an earlier virtual deadline than the currently running task - which will be descheduled and put at the back of the queue. Descheduled means that its virtual deadline is updated. The task's time gets refilled to max round robin quantum when it has used up all its time. If the scheduler found the task at the higher prio with the earliest virtual deadline, it will execute in place of the less important currently running task only if all logical CPUs (including hyperthreaded cores / SMT threads) are busy. The scheduler will delay preemption as long as possible if there are unused logical CPUs.
If a task is marked idle priority policy, it cannot preempt at all even other idle policy marked tasks but rather use cooperative multitasking.
Task placement, multiple cores