Brain Fuck Scheduler
| Brain Fuck Scheduler (BFS)
| |
|---|---|
| [[Datei:Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value)|150px]] | |
| Basisdaten
| |
| Hauptentwickler | Con Kolivas |
| Entwickler | Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value) |
| Erscheinungsjahr | September 2009 |
| Aktuelle Version | 0.512 für Linux-Kernel 4.8<ref>BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8</ref> (3. Oktober 2016) |
| Aktuelle Vorabversion | Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value) (Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value)) |
| Betriebssystem | Linux |
| Programmiersprache | C |
| Lizenz | GPL |
| kernel.kolivas.org | |
| Multiple Queue Skiplist Scheduler (MuQSS)
| |
|---|---|
| [[Datei:Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value)|150px]] | |
| Basisdaten
| |
| Hauptentwickler | Con Kolivas |
| Entwickler | Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value) |
| Erscheinungsjahr | Oktober 2016 |
| Aktuelle Version | 0.193 für Linux-Kernel 5.2<ref>linux-5.2-ck1, MuQSS version 0.193 for linux-5.2</ref> (22. Juli 2019) |
| Aktuelle Vorabversion | Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value) (Lua-Fehler in Modul:Wikidata, Zeile 1686: attempt to index field 'wikibase' (a nil value)) |
| Betriebssystem | Linux |
| Programmiersprache | 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.<ref name="lpm">Marcel Hilzinger: Con Kolivas Introduces New BFS Scheduler. In: Linux Pro Magazine Online. 2. September 2009, abgerufen am 18. Dezember 2012.</ref> Das Ziel des BFS ist eine überragende Desktop-Interaktivität (desktop interactivity) und System-Reaktionsfähigkeit (responsiveness).<ref name="SchedulersCompared">graysky: CPU SCHEDULERS 3COMPARED. (PDF; 631 kB) 20. Oktober 2012, abgerufen am 18. Dezember 2012.</ref>
Geschichte
Seit 2009 wird der BFS von dem langjährigen Kernel-Entwickler Con Kolivas entwickelt<ref name="BFSFAQ">Con Kolivas: FAQS about BFS. v0.330. In: ck.kolivas.org. 5. September 2010, abgerufen am 18. Dezember 2012.</ref> 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<ref>timothy: Con Kolivas Returns, With a Desktop-Oriented Linux Scheduler. In: linux.slashdot.org. 6. September 2009, abgerufen am 18. Dezember 2012.</ref>, im Linux Magazine<ref name="MolnarTest">Britta Wuelfing: Ingo Molnar Tests New BF Scheduler. In: Linux Magazine Online. 8. September 2009, abgerufen am 18. Dezember 2012.</ref> und Linux Pro Magazine.<ref name="lpm" />
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.<ref>Matthias Kohler: Multiple run-queues for BFS. In: LKML.org. 15. Dezember 2012, abgerufen am 18. Dezember 2012.</ref>
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.<ref name="RenamingToMuQSS">Con Kolivas: BFS version 0.512, linux-4.8-ck1, MuQSS for linux-4.8. 3. Oktober 2016, abgerufen am 11. Januar 2017.</ref> 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 <math>\mathcal{O}(n)</math>) umgehen.<ref name="IntroducingMuQSS">Con Kolivas: MuQSS - The Multiple Queue Skiplist Scheduler v0.105. 1. Oktober 2016, abgerufen am 11. Januar 2017.</ref>
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.<ref name="BFSFAQ" />
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.<ref name="IngoTest">Ingo Molnar: BFS vs. mainline scheduler benchmarks and measurements. In: Linux-Kernel-Mailingliste. 6. September 2009, abgerufen am 18. Dezember 2012.</ref> Obwohl es verschiedene Berichte über verbesserte Leistung und Reaktionsverhalten<ref name="SchedulersCompared" /> 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.<ref>cyanogen: CyanogenMod-4.1.6 with BFS is here! In: Twitter. 8. September 2009, abgerufen am 18. Dezember 2012.</ref><ref>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.</ref> Stefanie Kondik kündigte Ende Oktober 2009 an, den BFS wieder aus dem Hauptentwicklungszweig zu entfernen.<ref>cyanogen: Going to drop BFS for the stable release. In: Twitter. 21. Oktober 2009, abgerufen am 19. Dezember 2012.</ref><ref>CyanogenMod 5 Changelog. In: wiki.cyanogenmod.org. 2010, archiviert vom Vorlage:IconExternal am 3. Dezember 2012; abgerufen am 16. November 2022 (Lua-Fehler in Modul:Multilingual, Zeile 153: attempt to index field 'data' (a nil value)).</ref> Der BFS wurde am 23. September 2009 auch in einen experimentellen Zweig des Android-Entwicklungsrepositoriums aufgenommen.<ref><templatestyles src="Webarchiv/styles.css" />BFS wird dem Android-Repositorium hinzugefügt ( vom 30. Mai 2010 im Internet Archive)</ref> 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.<ref>Zenwalk 6.4 is ready! In: zenwalk.org. 27. Mai 2010, archiviert vom Vorlage:IconExternal am 23. Oktober 2013; abgerufen am 16. November 2022 (Lua-Fehler in Modul:Multilingual, Zeile 153: attempt to index field 'data' (a nil value)).</ref><ref>admin: PCLinuxOS 2010 Edition is now available for download. In: PCLinuxOS.com. 20. April 2010, abgerufen am 18. Dezember 2012.</ref>
Siehe auch
Weblinks
- FAQ zum BFS (englisch)
Einzelnachweise
<references responsive />