# Brain Fuck Scheduler

Der Brain Fuck Scheduler (BFS) oder Multiple Queue Skiplist Scheduler (MuQSS) ist ein Desktop-orientierter Prozess-Scheduler für den Linux-Kernel. Er wurde im August 2009 als Alternative zum Completely Fair Scheduler (kurz CFS) und dem O(1)-Scheduler entwickelt. Das Ziel des BFS ist eine überragende Desktop-Interaktivität (desktop interactivity) und System-Reaktionsfähigkeit (responsiveness).

## Geschichte

Seit 2009 wird der BFS von dem langjährigen Kernel-Entwickler Con Kolivas entwickelt und verbessert das Reaktionsverhalten bei Linux-basierten Mobilgeräten mit light-NUMA-Architektur (Non-Uniform Memory Architecture) und Desktop-Rechnern mit weniger als 16 Kernen.
Kurz nach seiner Einführung sorgte der neue Scheduler in der Linux-Gemeinde für Schlagzeilen unter anderem mit Berichten auf der Frontseite von Slashdot, im Linux Magazine und Linux Pro Magazine.
Der Brain Fuck Scheduler hat keine direkte Beziehung zur Programmiersprache Brainfuck.
Im Dezember 2012 wurde bekannt, dass der Linux-Entwickler Matthias Kohler an einem neuen Scheduler auf Basis von BFS und Linux 3.6.2 arbeitet. Die Besonderheit ist die Unterstützung von verschiedenen Run-Queue-Konfigurationen. BFS benutzt nur eine run-queue für alle CPUs. Zusätzlich zu dieser Funktion kann über den zu jenem Zeitpunkt noch unbenannten Scheduler zum Beispiel eine run-queue pro CPU oder eine run-queue je zwei CPUs konfiguriert werden.
Am 3. Oktober 2016 gab Con Kolivas bekannt, dass der Scheduler in Multiple Queue Skiplist Scheduler (MuQSS) umbenannt wurde. Als Gründe für die Umbenennung gab Kolivas die großen und einschneidenden Code-Änderungen und den einigen Leuten zu anstößigen Namen Brain Fuck Scheduler an. MuQSS unterstützt eine run-queue per logischer CPU und eine Skiplist für task lookups. Mit den beiden neuen Eigenschaften möchte Kolivas zwei große BFS-Beschränkungen (nur eine run-queue und teure lookups mit der Zeitkomplexität ${\mathcal {O}}(n)$) umgehen.

## Funktionsweise

Der BFS orientiert sich beim Verteilen von Rechenzeiten am CFS. Allerdings beeinflussen beim CFS auch die am Prozess gemessenen Ruhepausen der Vergangenheit die Entscheidung, wie lange eine Zeitscheibe für den Prozess in der Zukunft dauern wird.
Gerade bei leistungsschwacher Hardware, wie beispielsweise Mobiltelefonen, kann dies für die Benutzereingaben hinderlich sein. Wenn zu viele Ruhezeiten des Eingabeprozesses in der Vergangenheit aufgetreten sind, wird auch in Zukunft weniger Zeit dafür vorgesehen, bis sich die Statistik wieder ändert – eben dann, wenn wieder eine Benutzerinteraktion stattfindet. Der BFS entfernt diese komplexe Berechnung der Zeitscheiben anhand von Sleep-Aufrufen und versucht eine komplett faire Verteilung anzustreben.
Dieser „verkehrten“ Herangehensweise verdankt der Algorithmus auch seinen Namen.

## Verwendung

Ein erster Test der Version 0.208 durch Ingo Molnár ergab keine Performancevorteile. Der Kernel-Entwickler stimmte aber dem grundsätzlichen Ziel von Con Kolivas nach mehr Unterstützung von Desktop-Systemen zu. Obwohl es verschiedene Berichte über verbesserte Leistung und Reaktionsverhalten gab, ist es unwahrscheinlich, dass BFS in den Hauptzweig des Linuxkernels übernommen wird.
Der BFS wurde mit Version 4.1.6 in den CyanogenMod, eine Distribution des Mobil-Betriebssystems Android, integriert und hat zu berichteten Geschwindigkeitsverbesserungen geführt. Stefanie Kondik kündigte Ende Oktober 2009 an, den BFS wieder aus dem Hauptentwicklungszweig zu entfernen. Der BFS wurde am 23. September 2009 auch in einen experimentellen Zweig des Android-Entwicklungsrepositoriums aufgenommen. Er wurde jedoch nicht in die Froyo-Veröffentlichung (Android 2.2.x) aufgenommen, nachdem Blindtests mit dem Motorola Milestone und dem Nexus One keine Verbesserung im Benutzererlebnis zeigten.
Der BFS ist der vorgegebene Scheduler der GNU/Linux-Distributionen Zenwalk Linux 6.4 und PCLinuxOS 2010.