Brain Fuck Scheduler

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Brain Fuck Scheduler
Maintainer Con Kolivas
Erscheinungsjahr September 2009
Aktuelle Version 0.512 für
Linux-Kernel 4.8
(3. Oktober 2016[1])
Betriebssystem Linux
Programmiersprache C
Lizenz GPL
kernel.kolivas.org

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

BFS wurde von dem langjährigen Kernel-Entwickler Con Kolivas entwickelt[4] 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[5], im Linux Magazine[6] und Linux Pro Magazine.[2]

Der BFS hat keine direkte Beziehung zur Programmiersprache Brainfuck.

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

Funktionsweise[Bearbeiten | Quelltext bearbeiten]

Der Brain Fuck Scheduler 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. [4]

Verwendung[Bearbeiten | Quelltext bearbeiten]

Ein erster Test der Version 0.208 durch Ingo Molnar ergab keine Performancevorteile. Der Kernel-Entwickler stimmte aber dem grundsätzlichen Ziel von Con Kolivas nach mehr Unterstützung von Desktop-Systemen zu.[9] Obwohl es verschiedene Berichte über verbesserte Leistung und Reaktionsverhalten[3] 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.[10][11] Steve Kondik kündigte Ende Oktober 2009 an, den BFS wieder aus dem Hauptentwicklungszweig zu entfernen.[12][13] Der BFS wurde am 23. September 2009 auch in einen experimentellen Zweig des Android-Entwicklungsrepositoriums aufgenommen.[14] Er wurde jedoch nicht in die Froyo-Veröffentlichung (Android 2.2.x) aufgenommen, nachdem Blindtests mit dem Droid und dem NexusOne keine Verbesserung im Benutzererlebnis zeigten.

Der BFS ist der vorgegebene Scheduler der GNU/Linux-Distributionen Zenwalk Linux 6.4 und PCLinuxOS 2010.[15] [16]

Im Dezember 2012 wurde bekannt, dass der Linux-Entwickler Matthias Kohler an einem neuen Scheduler auf BFS-Basis und Linux 3.6.2 arbeitet. Die Besonderheit ist die Unterstützung von verschiedenen run-queues-Konfigurationen. BFS benutzt nur eine run-queue für alle CPUs. Zusätzlich zu dieser Funktion kann über den noch unbenannten Scheduler zum Beispiel eine run-queue pro CPU oder eine runqueue alle zwei CPUs konfiguriert werden.[17]

Siehe auch[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

Quellen[Bearbeiten | Quelltext bearbeiten]

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