View source for Brain Fuck Scheduler

{{Short description|Process scheduler in Linux}}
{{Distinguish|Brainfuck}}
{{Update|date=November 2016|talksection=MuQSS}}
{{Infobox software
| logo                   = 
| screenshot             = 
| caption                = 
| collapsible            = 
| developer              = [[Con Kolivas]]
| discontinued           = Yes
| latest_release_version = 0.512
| latest_release_date    = {{Start date and age|2016|10|03}}<ref>{{cite web|url=https://ck-hack.blogspot.co.uk/2016/10/bfs-version-0512-linux-48-ck1-muqss-for.html|title=-ck hacking: BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8 |website=ck-hack.blogspot.com |date=2016-10-03 |access-date=2016-11-10}}</ref>
| latest preview version = 
| latest preview date    = 
| programming language   = [[C (programming language)|C]]
| operating_system       = [[Linux]]
| platform               = 
| size                   = 
| language               = 
<!--| status                 = Discontinued<ref name = "bfsretired" />-->
| genre                  = 
| license                = [[GNU GPL]]
| website                = {{URL|http://kernel.kolivas.org/}}
}}
[[File:Simplified_Structure_of_the_Linux_Kernel.svg|thumb|upright=1.7|The location of [[process scheduler]]s in a simplified structure of the [[Linux kernel]]]]

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),<ref>{{Cite web|url=https://lwn.net/Articles/720227/|title=The MuQSS CPU scheduler [LWN.net]|website=[[LWN.net]]}}</ref> as an alternative to the [[Completely Fair Scheduler]] (CFS) and the [[O(1) scheduler]].<ref name="Linux Pro Magazine on BFS">{{cite web|url=http://www.linuxpromagazine.com/Online/News/Con-Kolivas-Introduces-New-BFS-Scheduler |title=Con Kolivas Introduces New BFS Scheduler » Linux Magazine |publisher=Linuxpromagazine.com |date=2009-09-02 |access-date=2013-10-30}}</ref> BFS was created by [[Con Kolivas]].<ref name="bfsfaq">{{cite web|url=http://ck.kolivas.org/patches/bfs/bfs-faq.txt |title=FAQs about BFS v0.330 |publisher=Ck.kolivas.org |access-date=2013-10-30}}</ref>

The objective of BFS, compared to other schedulers, is to provide a scheduler with a simpler [[algorithm]], that does not require adjustment of [[heuristic]]s or tuning [[Parameter (computer programming)|parameters]] to tailor [[Computer performance|performance]] to a specific type of [[computation]]al 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.<ref name="bfsfaq"/> BFS has been reported to improve responsiveness on Linux desktop computers with fewer than 16 [[CPU core|cores]].<ref name="shedulers compared" />

Shortly following its introduction, the new scheduler made headlines within the Linux community, appearing on ''[[Slashdot]]'', with reviews in ''[[Linux Magazine (USA)|Linux Magazine]]'' and ''[[Linux Magazine|Linux Pro Magazine]]''.<ref name="Linux Pro Magazine on BFS"/><ref>{{cite web|url=http://slashdot.org/story/09/09/06/0433209/Con-Kolivas-Returns-With-a-Slashdo |title=Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler |date=6 September 2009 |publisher=Slashdot |access-date=2013-10-30}}</ref><ref>{{cite web|url=http://www.linux-magazine.com/Online/News/Ingo-Molnar-Tests-New-BF-Scheduler |title=Ingo Molnar Tests New BF Scheduler |publisher=Linux Magazine |date=2009-09-08 |access-date=2013-10-30}}</ref> 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.<ref name="bfsfaq" />

==Theoretical design and efficiency==

In 2009, BFS was introduced and had originally used a [[doubly linked list]] data structure,<ref name="sched-bfs-001.patch">{{cite web|url=http://ck.kolivas.org/patches/old/sched-bfs-001.patch |title=sched-bfs-001.patch |publisher=Con Kolivas |date=2009-08-13 |access-date=2020-10-09}}</ref><ref name="4.0-sched-bfs-462.patch">{{cite web|url=http://ck.kolivas.org/patches/4.0/4.0/4.0-ck1/patches/4.0-sched-bfs-462.patch |title=4.0-sched-bfs-462.patch |publisher=Con Kolivas |date=2015-04-16 |access-date=2019-01-29}}</ref> but the data structure is treated like a [[FIFO (computing and electronics)|queue]].  Task insertion is {{tmath|O(1)}}.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 119–120}}  Task search for next task to execute is {{tmath|O(n)}} worst case.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 209}}  It uses a single global [[run queue]] which all CPUs use.  Tasks with higher scheduling priorities get executed first.<ref name="4.0-sched-bfs-462.patch" />{{rp|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 scheduling|Round-Robin Scheduler]] especially when tasks have the same priority below the Isochronous policy.<ref name="4.0-sched-bfs-462.patch" />{{rp|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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 306}}  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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 314–320}}  This important tuneable can tailor the round robin scheduler as a trade off between throughput and latency.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 229–320}}  All tasks get the same time slice with the exception of realtime FIFO which is assumed to have infinite time slice.<ref name="4.0-sched-bfs-462.patch" />{{rp|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<ref name="lwn-224865" />{{rp|par. 3}}) priority array<ref>{{cite web|url=http://ck.kolivas.org/patches/staircase-deadline/sched-rsdl-0.26.patch |archive-url=https://web.archive.org/web/20110726235345/http://ck.kolivas.org/patches/staircase-deadline/sched-rsdl-0.26.patch |url-status=dead |archive-date=2011-07-26 |title=sched-rsdl-0.26.patch |publisher=Con Kolivas |access-date=2019-01-30}}</ref><ref name="lwn-224865">{{cite web|url=https://lwn.net/Articles/224865/ |publisher=corbet |title=The Rotating Staircase Deadline Scheduler |date=2007-03-06 |access-date=2019-01-30}}</ref> 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 <nowiki>[task]</nowiki> fairness.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 81–92}}  He claimed that deterministic latencies was guaranteed with BFS in his later iteration of MuQSS.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 471–472}}  He also recognized possible lock contention problem (related to the altering, removal, creation of task node data)<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 126–144}} with increasing CPUs and the overhead of {{tmath|O(\log n)}} next task for execution lookup.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 472–478}}  MuQSS tried to resolve those problems.

Kolivas later changed the design to a [[skip list]] in the v0.480 release of BFS in 2016.<ref name="4.7-sched-bfs-480.patch">{{cite web|url=http://ck.kolivas.org/patches/bfs/4.0/4.7/4.7-sched-bfs-480.patch |title=4.7-sched-bfs-480.patch |publisher=Con Kolivas |date=2016-09-02 |access-date=2020-10-09}}</ref>  This time this altered the efficiency of the scheduler.  He noted {{tmath|O(\log n)}} task insertion, {{tmath|O(1)}} task lookup; {{tmath|O(k)}}, with {{tmath|k \le 16}}, for task removal.<ref name="4.7-sched-bfs-480.patch" />{{rp|ln 4}}

===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).<ref name="4.0-sched-bfs-462.patch" />{{rp|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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 161–163}}

First a prio ratios lookup table is created.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 8042–8044}}  It is based on a recursive sequence.  It increases 10% each nice level.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 161}} 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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 177–179, 120, 184–185}} The moving part comes from the {{mono|1=t}} variable in the virtual deadline formula that Kolivas hinted.

{{pre|1=
g(0) = 128
g(i) = INT( g(i-1)*11/10 )
}}

{| class="wikitable mw-collapsible autocollapse"
! 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 (Unix)|nice]]-to-index mapping function {{mono|1=f(n)}} 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 {{code|TASK_USER_PRIO()}} 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.

{| class="wikitable mw-collapsible autocollapse"
! 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:<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 4063, 4036, 4033, 1180}}

{{pre|1=
T = 6
N = 1<<20
d(n,t) = t + g(f(n)) * T * (N/128)
}}

Alternatively,

{{block indent|<math>\mathtt{
d(n,t) = \frac{g(f(n))}{128} * T * N + t
}</math><ref>The alternative formula is presented for ease of understanding.  All math is done in integer math so precision loss would be great.  It is possibly why Kolivas deferred the division by 128 to one of the largest numbers as a multiple of 128 resulting in no remainder.</ref>}}

where {{mono|1=d(n,t)}} is the virtual deadline in u64 integer nanoseconds as a function of nice {{mono|1=n}} and {{mono|1=t}} which is the current time in niffies, {{mono|1=g(i)}} is the prio ratio table lookup as a function of index, {{mono|1=f(n)}} is the task's nice-to-index mapping function, {{mono|1=T}} is the round robin timeslice in milliseconds, {{mono|1=N}} is a constant of 1 millisecond in terms of nanoseconds as a latency reducing approximation of the conversion factor of <math>\mathrm\frac{10^9 ns}{10^3 ms}</math> but Kolivas uses a base 2 constant {{mono|1=N}} with approximately that scale.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 1173–1174}} Smaller values of {{mono|1=d}} mean that the virtual deadline is earlier corresponding to negative nice values. Larger values of {{mono|1=d}} indicate the virtual deadline is pushed back later corresponding to positive nice values. It uses this formula whenever the timeslice expires.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 5087}}

128 in base 2 corresponds to 100 in base 10 and possibly a "pseudo 100".<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 3415}}  115 in base 2 corresponds to 90 in base 10.  Kolivas uses 128 for "fast [[Bitwise operation#Bit shifts|shifts]]",<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 3846, 1648, 3525}} as in division is right shift base 2.

{| class="wikitable mw-collapsible autocollapse" 
! Nice
! Virtual deadline in timeslices relative to {{mono|1=t}}
! Virtual deadline in exact seconds relative to {{mono|1=t}}
|-
| −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<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 4146–4161}} 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" (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.  The lower prio value means it is more important and gets executed first.

====Realtime policy====

The realtime policy was designed for [[Real-time computing|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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 351, 1150}}  The scheduler treats realtime round robin (SCHED_RR) and realtime FIFO (SCHED_FIFO) differently.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 3881–3934}}

The design laid out first 100 static priority queues.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 189}}

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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 4146–4161}}

On [[Fork (system call)|forks]], the process priority will be demoted to normal policy.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 2708}}

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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 350–359, 5023–5025}}

====Isochronous policy====

The Isochronous policy was designed for near realtime performance for non-[[superuser|root]] users.<ref name="4.0-sched-bfs-462.patch" />{{rp|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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 1201, 346–348}}

The behavior of the policy can allow a task can be demoted to normal policy<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 336}} when it exceeds a tuneable resource handling percentage (70% by default<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 343, 432}}) of 5 seconds scaled to the number of online CPUs and the timer resolution plus 1 tick.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 343, 3844–3859, 1167, 338}}<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 1678, 4770–4783, 734}}  The formula was altered in MuQSS due to the multi-runqueue design.  The exact formulas are:

{{block indent|<math>\mathtt{
T_{BFS} = ((5*F*n)+1)*R
}</math>}}
{{block indent|<math>\mathtt{
T_{MuQSS} = (5*F)*R
}</math>}} 
where {{mono|T}} is the total number of isochronous ticks, {{mono|F}} is the timer frequency, {{mono|n}} is the number of online CPUs, {{mono|R}} 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&nbsp;Hz for servers and 1000&nbsp;Hz for interactive desktops.  250 is the balanced value.  Setting {{mono|R}} to 100 made tasks behave as realtime and 0 made it not pseudo-realtime and anything in the middle was pseudo-realtime.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 346–348}}

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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 334}}

This behavior of the Isochronous policy is unique to only BFS and MuQSS and may not be implemented in other CPU schedulers.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 324, 8484–8485}}<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 1287–1288}}

====Normal policy====

The normal policy was designed for regular use and is the default policy.  Newly created tasks are typically marked normal.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 502}}

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 program]]s and [[transcoders]] so that foreground processes or those above this scheduling policy can run uninterrupted.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 363–368}}

The design laid out 1 priority queue and tasks can be [[Aging (scheduling)|promoted]] to normal policy automatically to prevent [[Starvation (computer science)|indefinite resource hold]].<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 368}}

The next executed task with Idle priority with others residing in the same priority policy is selected by the earliest virtual deadline.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 4160–4161}}

===Preemption===

[[Preemption (computing)|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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 169–175}}  Descheduled means that its virtual deadline is updated.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 165–166}}  The task's time gets refilled to max round robin quantum when it has used up all its time.<ref name="4.0-sched-bfs-462.patch" />{{rp|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.  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]].<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 2341–2344}}

===Task placement, multiple cores===

When the scheduler discovers a waking task on a non-unicore system, it will need to determine which logical CPU to run the task on.  The scheduler favors most the idle [[Hyper-threading|hyperthreaded]] cores (or idle [[Simultaneous multithreading|SMT]] threads) first on the same CPU that the task executed on,<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 261}} then the other idle core of a multicore CPU,<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 262}} then the other CPUs on the same NUMA node,<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 267, 263–266, 255–258}} then all busy hyperthreaded cores / SMT threads / logical CPUs to be preempted on the same [[Non-uniform memory access|NUMA]] node,<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 265–267}} then the other (remote) NUMA node<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 268–270}} and is ranked on a preference list.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 255–274}}  This special scan exists to minimize latency overhead resulting of migrating the task.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 245, 268–272}}

The preemption order is similar to the above paragraph.  The preemption order is hyperthreaded core / SMT units on the same multicore first, then the other core in the multicore, then the other CPU on the same NUMA node.<ref name="4.0-sched-bfs-462.patch" />{{rp|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.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 270}}  The scheduler will have to scan for a suitable task with a lower or maybe equal priority policy task (with a later virtual deadline if necessary) to preempt and avoid logical CPUs with a task with a higher priority policy which it cannot preempt.  Local preemption has a higher rank than scanning for a remote idle NUMA unit.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 265–269}}

When a task is involuntary preempted at the time the CPU is slowed down as a result of kernel mediated [[Dynamic frequency scaling|CPU frequency scaling]] (aka CPU frequency governor), the task is specially marked "sticky" except those marked as realtime policy.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 2085}}  Marked sticky indicates that the task still has unused time and the task is restricted executing to the same CPU.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 233–243}}  The task will be marked sticky whenever the CPU scaling governor has scaled the CPU at a slower speed.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 2082–2107, 8840–8848}}  The idled stickied task will return to either executing at full Ghz speed by chance or to be rescheduled to execute on the best idle CPU that is not the same CPU that the task ran on.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 2082–2086, 239–242, 2068–2079}}  It is not desirable to migrate the task to other places but make it idle instead because of increased latency brought about of overhead to migrating the task to another CPU or NUMA node.<ref name="4.0-sched-bfs-462.patch" />{{rp|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.

==schedtool==

A privileged user can change the priority policy of a process with the schedtool program<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 326, 373}} or it is done by a program itself.<ref name="4.0-sched-bfs-462.patch" />{{rp|ln 336}}  The priority class can be manipulated at the code level with a [[syscall]] like sched_setscheduler only available to root,<ref>{{cite web|url=https://www.linuxjournal.com/article/3910 |title=The Linux Scheduler |publisher=Moshe Bar |date=2000-04-01 |access-date=2019-01-29 }}</ref> which schedtool uses.<ref>{{cite web|url=https://github.com/freequaos/schedtool/blob/c7bf73dc92633713268c6b5393170fa3cfe369ec/schedtool.c#L431 |title=schedtool.c |access-date=2019-01-30 |date=2017-07-17 |publisher=freek}}</ref>

==Benchmarks==
In a contemporary study,<ref name="shedulers compared">{{cite web|url=http://repo-ck.com/bench/cpu_schedulers_compared.pdf |title=CPU Schedulers Compared |publisher=Repo-ck.com |access-date=2013-10-30}}</ref> the author compared the BFS to the CFS using the Linux kernel v3.6.2 and several performance-based endpoints. The purpose of this study was to evaluate the Completely Fair Scheduler (CFS) in the [[Vanilla (software)|vanilla]] Linux kernel and the BFS in the corresponding kernel patched with the ck1 patchset. Seven different machines were used to see if differences exist and, to what degree they scale using performance based metrics. Number of logical CPUs ranged from 1 to 16. These end-points were never factors in the primary design goals of the BFS. The results were encouraging.

Kernels patched with the ck1 patch set including the BFS outperformed the vanilla kernel by 1% to 8% using the CFS at nearly all the performance-based benchmarks tested.<ref name="shedulers compared"/> Further study with a larger test set could be conducted, but based on the small test set of 7 PCs evaluated, these increases in process queuing, efficiency/speed are, on the whole, independent of CPU type (mono, dual, quad, hyperthreaded, etc.), CPU architecture (32-bit and 64-bit) and of CPU multiplicity (mono or dual socket).

Moreover, on several "modern" CPUs, such as the Intel [[Core 2 Duo]] and [[Core i7]], that represent common workstations and laptops, BFS consistently outperformed the CFS in the vanilla kernel at all benchmarks. Efficiency and speed gains were small to moderate.

==Adoption==
BFS is the default scheduler for the following desktop Linux distributions:

* [[NimbleX]] and [[Sabayon Linux]] 7<ref>{{cite web|url=http://ostatic.com/blog/sabayon-7-brings-linux-heaven |title=Sabayon 7 Brings Linux Heaven |publisher=Ostatic.com |access-date=2013-10-30}}</ref>
* [[PCLinuxOS]] 2010<ref>{{cite web|url=http://pclinuxos.com/?p=579 |title=2010 Edition is now available for download. |publisher=PCLinuxOS |date=2013-10-22 |access-date=2013-10-30}}</ref>
* [[Zenwalk]] 6.4<ref>{{cite web |url=http://www.zenwalk.org/modules/news/article.php?storyid=107 |title=Zenwalk 6.4 is ready ! - Releases - News |publisher=Zenwalk.org |access-date=2013-10-30 |url-status=dead |archive-url=https://web.archive.org/web/20131023055842/http://www.zenwalk.org/modules/news/article.php?storyid=107 |archive-date=2013-10-23 }}</ref>
*[[GalliumOS]] 2.1<ref>{{Cite web|url=https://wiki.galliumos.org/About_GalliumOS|title=About GalliumOS - GalliumOS Wiki|website=wiki.galliumos.org|language=en|access-date=2018-06-08}}</ref>

Additionally, BFS has been added to an experimental branch of [[Google]]'s [[Android (operating system)|Android]] development repository.<ref>[http://android.git.kernel.org/?p=kernel/experimental.git;a=shortlog;h=refs/heads/android-2.6.29-bfs]
 {{webarchive|url=https://web.archive.org/web/20090922234416/http://android.git.kernel.org/?p=kernel%2Fexperimental.git%3Ba%3Dshortlog%3Bh%3Drefs%2Fheads%2Fandroid-2.6.29-bfs|date=September 22, 2009}}</ref> It was not included in the [[Android version history#Android 2.2–2.2.3 Froyo (API level 8)|Froyo release]] after [[blind testing]] did not show an improved user experience.<ref>{{cite web|url=https://lwn.net/Articles/389230/ |title=CyanogenMod 5 for the G1/ADP1 |publisher=Lwn.net |access-date=2013-10-30}}</ref>

==MuQSS==
BFS has been retired in favour of '''MuQSS''', known formally as the '''Multiple Queue Skiplist Scheduler''', a rewritten implementation of the same concept.<ref name="bfsretired">{{cite web|url=https://ck-hack.blogspot.co.uk/2016/10/linux-48-ck2-muqss-version-0114.html|title=ck-hacking: linux-4.8-ck2, MuQSS version 0.114 |website=ck-hack.blogspot.com |date=2016-10-21 |access-date=2016-11-10}}</ref><ref name="phoronix-MuQSS">{{Cite web|url=https://www.phoronix.com/scan.php?page=news_item&px=MuQSS-First-Major-Release|title = Con Kolivas Announces First Major Release of MuQSS, Successor to BFS - Phoronix}}</ref> The primary author abandoned<ref name="muqsseol">{{cite web|url=https://ck-hack.blogspot.com/2021/08/514-and-future-of-muqss-and-ck-once.html|title= 5.14 and the future of MuQSS and -ck once again |website=ck-hack.blogspot.com |date=2021-08-31 |access-date=2022-09-20}}</ref> work on MuQSS by the end of August 2021.

===Theoretical design and efficiency===

MuQSS uses a bidirectional static arrayed 8 level [[skip list]] and tasks are ordered by static priority <nowiki>[queues]</nowiki> (referring to the scheduling policy) and a virtual deadline.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch">{{cite web|url=http://ck.kolivas.org/patches/4.0/4.18/4.18-ck1/patches/0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch|title=0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch |publisher=Con Kolivas |date=2018-08-27 |access-date=2019-01-29}}</ref>{{rp|ln 519, 525, 537, 588, 608}}  8 was chosen to fit the array in the cacheline.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 523}}  Doubly linked data structure design was chosen to speed up task removal.  Removing a task takes only O(1) with a doubly skip list versus the original design by [[William Pugh (computer scientist)|William Pugh]] which takes {{tmath|O(n)}} worst case.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 458}}

Task insertion is {{tmath|O(\log n)}}.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 458}}  The next task for execution lookup is {{tmath|O(k)}}, where {{mvar|k}} is the number of CPUs.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 589–590, 603, 5125}}  The next task for execution is {{tmath|O(1)}} per runqueue,<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|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 {{tmath|O(k)}}.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 591–593, 497–501, 633–656}}  The max number of tasks it can handle are 64k tasks per runqueue per CPU.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 521}}  It uses multiple task runqueues in some configurations one runqueue per CPU, whereas its predecessor BFS only used one task runqueue for all CPUs.

Tasks are ordered as a gradient in the skip list in a way that realtime policy priority comes first and idle policy priority comes last.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 2356–2358}}  Normal and idle priority policy still get sorted by virtual deadline which uses [[Nice (Unix)|nice]] values.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 2353}}  Realtime and Isochronous policy tasks are run in [[FIFO (computing and electronics)|FIFO]] order ignoring nice values.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 2350–2351}}  New tasks with same key are placed in FIFO order meaning that newer tasks get placed at the end of the list (i.e. top most node vertically), and tasks at 0th level or at the front-bottom get execution first before those at nearest to the top vertically and those furthest away from the head node.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 2351–2352, 590}}  The key used for inserted sorting is either the static priority<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 2345, 2365, }} or the virtual deadline.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 2363}}

The user can choose to share runqueues among multicore or have a runqueue per logical CPU.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 947–1006}}  The speculation of sharing runqueues design was to reduce latency with a tradeoff of throughput.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|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.<ref name="0001-MultiQueue-Skiplist-Scheduler-version-v0.173.patch" />{{rp|ln 618–630, 3829–3851, 3854–3865, 5316}}

==See also==
{{Portal|Free and open-source software|Linux}}
* [[Fair-share scheduling]]

==References==
{{Reflist|30em}}

==External links==
* [http://ck.kolivas.org/patches/bfs/bfs-faq.txt Brain Fuck Scheduler FAQ]

{{Linux kernel}}

[[Category:Linux kernel process schedulers]]
[[Category:Free software programmed in C]]
[[Category:Software using the GNU General Public License]]