Brain Fuck Scheduler

Brain Fuck Scheduler (BFS)
Basisdaten

Hauptentwickler Con Kolivas
Entwickler Con Kolivas
Erscheinungsjahr September 2009
Aktuelle Version 0.512 für
Linux-Kernel 4.8
(3. Oktober 2016[1])
Betriebssystem Linux
Programmier­sprache C
Lizenz GPL
kernel.kolivas.org
Multiple Queue Skiplist Scheduler (MuQSS)
Basisdaten

Hauptentwickler Con Kolivas
Entwickler Con Kolivas
Erscheinungsjahr Oktober 2016
Aktuelle Version 0.193 für
Linux-Kernel 5.2
(22. Juli 2019[2])
Betriebssystem Linux
Programmier­sprache C
Lizenz GPL
kernel.kolivas.org

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.[3] Das Ziel des BFS ist eine überragende Desktop-Interaktivität (desktop interactivity) und System-Reaktionsfähigkeit (responsiveness).[4]

Geschichte

[Bearbeiten | Quelltext bearbeiten]

Seit 2009 wird der BFS von dem langjährigen Kernel-Entwickler Con Kolivas entwickelt[5] 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[6], im Linux Magazine[7] und Linux Pro Magazine.[3]

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.[8]

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.[9] 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 ) umgehen.[10]

Funktionsweise

[Bearbeiten | Quelltext bearbeiten]

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.[5]

Verwendung

[Bearbeiten | Quelltext bearbeiten]

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.[11] Obwohl es verschiedene Berichte über verbesserte Leistung und Reaktionsverhalten[4] 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.[12][13] Stefanie Kondik kündigte Ende Oktober 2009 an, den BFS wieder aus dem Hauptentwicklungszweig zu entfernen.[14][15] Der BFS wurde am 23. September 2009 auch in einen experimentellen Zweig des Android-Entwicklungsrepositoriums aufgenommen.[16] 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.[17][18]

Siehe auch

[Bearbeiten | Quelltext bearbeiten]
[Bearbeiten | Quelltext bearbeiten]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. ↑ BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8
  2. ↑ linux-5.2-ck1, MuQSS version 0.193 for linux-5.2
  3. ↑ a b Marcel Hilzinger: Con Kolivas Introduces New BFS Scheduler. In: Linux Pro Magazine Online. 2. September 2009, abgerufen am 18. Dezember 2012.
  4. ↑ a b graysky: CPU SCHEDULERS 3COMPARED. (PDF; 631 kB) 20. Oktober 2012, abgerufen am 18. Dezember 2012.
  5. ↑ a b Con Kolivas: FAQS about BFS. v0.330. In: ck.kolivas.org. 5. September 2010, abgerufen am 18. Dezember 2012.
  6. ↑ timothy: Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler. In: linux.slashdot.org. 6. September 2009, abgerufen am 18. Dezember 2012.
  7. ↑ Britta Wuelfing: Ingo Molnar Tests New BF Scheduler. In: Linux Magazine Online. 8. September 2009, abgerufen am 18. Dezember 2012.
  8. ↑ Matthias Kohler: Multiple run-queues for BFS. In: LKML.org. 15. Dezember 2012, abgerufen am 18. Dezember 2012.
  9. ↑ Con Kolivas: BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8. 3. Oktober 2016, abgerufen am 11. Januar 2017.
  10. ↑ Con Kolivas: MuQSS - The Multiple Queue Skiplist Scheduler v0.105. 1. Oktober 2016, abgerufen am 11. Januar 2017.
  11. ↑ Ingo Molnar: BFS vs. mainline scheduler benchmarks and measurements. In: Linux-Kernel-Mailingliste. 6. September 2009, abgerufen am 18. Dezember 2012.
  12. ↑ cyanogen: CyanogenMod-4.1.6 with BFS is here! In: Twitter. 8. September 2009, abgerufen am 18. Dezember 2012.
  13. ↑ cyanogen: [ROM] CyanogenMod - This is Bat Country! (EXPERIMENTAL) [9/18 - v4.1.11.1]. changelog and user comments. In: xda-developers.com. 18. September 2009, abgerufen am 18. Dezember 2012.
  14. ↑ cyanogen: Going to drop BFS for the stable release. In: Twitter. 21. Oktober 2009, abgerufen am 19. Dezember 2012.
  15. ↑ CyanogenMod 5 Changelog. In: wiki.cyanogenmod.org. 2010, archiviert vom Original am 3. Dezember 2012; abgerufen am 16. November 2022 (englisch).
  16. ↑ BFS wird dem Android-Repositorium hinzugefügt (Memento vom 30. Mai 2010 im Internet Archive)
  17. ↑ Zenwalk 6.4 is ready! In: zenwalk.org. 27. Mai 2010, archiviert vom Original am 23. Oktober 2013; abgerufen am 16. November 2022 (englisch).
  18. ↑ admin: PCLinuxOS 2010 Edition is now available for download. In: PCLinuxOS.com. 20. April 2010, abgerufen am 18. Dezember 2012.