Brain Fuck Scheduler
[4] BFS has been reported to improve responsiveness on Linux desktop computers with fewer than 16 cores.
[3][6][7] 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.
[9]: ln 4146–4161 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.
[9]: ln 1193–1195, 334–335 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.
[9]: ln 314–320 This important tuneable can tailor the round robin scheduler as a trade off between throughput and latency.
[9]: ln 1646, 1212–1218, 4062, 3910 Kolivas explained the reason why he choose to go with the doubly linked list mono-runqueue than the multi-runqueue (round robin[10]: par.
[9]: ln 4023, 4063 The virtual deadline only suggests the order but does not guarantee that a task will run exactly on the future scheduled niffy.
The internal kernel implementation slightly differs with range between 100 and 140 static priority but users will see it as −20...19 nice.
The virtual deadline is based on this exact formula:[9]: ln 4063, 4036, 4033, 1180 Alternatively, where d(n,t) is the virtual deadline in u64 integer nanoseconds as a function of nice n and t which is the current time in niffies, g(i) is the prio ratio table lookup as a function of index, f(n) is the task's nice-to-index mapping function, T is the round robin timeslice in milliseconds, N is a constant of 1 millisecond in terms of nanoseconds as a latency reducing approximation of the conversion factor of
In the v0.462 edition (used in the -ck 4.0 kernel patchset), there are total of 103 "priority queues" (aka 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.
[9]: ln 325 The design laid out 1 priority queue that by default ran as pseudo-realtime tasks, but can be tuned as a degree of realtime.
[9]: ln 334 This behavior of the Isochronous policy is unique to only BFS and MuQSS and may not be implemented in other CPU schedulers.
[9]: ln 502 The design laid out one priority queue and tasks are chosen to be executed first based on earliest virtual deadline.
[9]: ln 363–368 The design laid out 1 priority queue and tasks can be promoted to normal policy automatically to prevent indefinite resource hold.
[9]: ln 4057–4062, 5856 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.
[9]: ln 255–274 This special scan exists to minimize latency overhead resulting of migrating the task.
[9]: ln 265–267 When it goes scanning for a task to preempt in the other remote NUMA node, the preemption is just any busy threads with lower to equal prio or later virtual deadline assuming that all logical CPUs (including hyperthreaded core / SMT threads) in the machine are all busy.
Local preemption has a higher rank than scanning for a remote idle NUMA unit.
[9]: ln 228, 245 This sticky feature was removed in the last iteration of BFS (v0.512) corresponding to Kolivas' patchset 4.8-ck1 and did not exist in MuQSS.
[9]: ln 336 The priority class can be manipulated at the code level with a syscall like sched_setscheduler only available to root,[15] which schedtool uses.
[16] In a contemporary study,[5] the author compared the BFS to the CFS using the Linux kernel v3.6.2 and several performance-based endpoints.
[21] It was not included in the Froyo release after blind testing did not show an improved user experience.
[22] BFS has been retired in favour of MuQSS, known formally as the Multiple Queue Skiplist Scheduler, a rewritten implementation of the same concept.
[12]: ln 523 Doubly linked data structure design was chosen to speed up task removal.
per runqueue,[12]: ln 5124 but the scheduler examines every other runqueues to maintain task fairness among CPUs, for latency or balancing (to maximize CPU usage and cache coherency on the same NUMA node over those that access across NUMA nodes), so ultimately
[12]: ln 2356–2358 Normal and idle priority policy still get sorted by virtual deadline which uses nice values.
[12]: ln 2353 Realtime and Isochronous policy tasks are run in FIFO order ignoring nice values.
[12]: ln 947–1006 A new behavior introduced by MuQSS was the use of the high resolution timer for below millisecond accuracy when timeslices were used up resulting in rescheduling tasks.
