Mailinglisten-Beitrag
Der in der Vorlesung vorgestellte \(\mathcal{O}(1)\) Scheduler[1] wurde vom 2.6er Linux Kernel bis Version 2.6.23 verwendet und dann durch den sogenannten Completely Fair Scheduler (CFS)[2] abgelöst, der Rot-Schwarz-Bäume verwendet, und daher in \(\mathcal{O}(\log(n))\) läuft -- dafür aber komplett fair ist 😉 Beide Scheduler wurden von Ingo Molnár entworfen und größtenteils implementiert. Abgesehen von den Wikipedia Artikeln fand ich auch Ingos eigene Beschreibung[3] sehr interessant. In der prä-2.6-Ära des Linux Kernels wurde ein Scheduler verwendet, zu dessen Effizienz ich keine Angaben gefunden habe. Anhand der (ziemlich detaillierten) Beschreibung in Kapitel 10 von „Understanding the Linux Kernel“[1] gehe ich jedoch davon aus, dass es \(\mathcal{O}(n)\) gewesen sein muss. Auch wenn die dort beschriebenen Algorithmen inzwischen mehrfach überholt sind, fand ich das Kapitel sehr lesenswert.
Wie in der Vorlesung vermutet wurde, kann man den Scheduler natürlich konfigurieren. Dazu ist es aber nicht notwendig, neu zu kompilieren -- noch nicht einmal neu zu booten. Stattdessen kann man (beim CFS) einfach über das /proc Dateisystem in die verschiedenen Dateien in
/proc/sys/kernel/...
schreiben. Die Änderungen werden instantan wirksam. (Und spätestens zum nächsten Reboot wieder zurückgesetzt, man kann also nicht viel kaputt machen.) Permanente Änderungen kann man in /etc/sysctl.conf schreiben. (Habe ich noch nicht probiert.)
Ich habe ein kleines Programm geschrieben, das sehr viele Subprozesse erzeugt, die alle sinnlose Rechnungen auf der CPU ausführen und zwischendurch in regelmäßigen Intervallen eine (eigentlich zwei) Zellen auf dem Terminal umfärben. Man kann anhand dessen, wie sich das Muster ändert, schön sehen, wie oft ein einzelner Prozess an die Reihe kommt, und wie lange er es bleibt, wenn er es einmal ist. Das Programm kann von meiner Website heruntergeladen werden. In dem Archiv ist auch ein kleines Shell-Skript, sched-tune.sh, mit dem man die wichtigsten Parameter ändern kann. Die README Datei in dem Archiv erklärt genauer, wie man das Programm benutzen kann.
Da der Bildschirm beim Ausführen des Programms (gewollt) stark flackert, muss ich Epileptikern und anderen empfindlichen Personen unter Umständen leider davon abraten.
Leider lässt der Kernel keine völlig unsinnigen Werte zu. Man kann also nur bedingt ausprobieren, welchen Einfluss extreme Einstellungen haben / hätten. Wie in Referenz 4 beschrieben, „friert“ die grafische Oberfläche übrigens auch nicht ein, wenn man größere Scheduling Intervalle wählt, da jeder Tastendruck einen Interrupt auslöst, der -- egal wie geschedulet wird -- immer die Kontrolle an jenen Prozess übergibt, der gerade das Keyboard „gegrabbt“ hat.
Grüße
Moritz
Video
Ich habe mal ein Video von Moritz' Programm gemacht:
Referenzen
[1] ↑: „O(1) Scheduler“ in: Wikipedia, the free encyclopedia. Abgerufen am 13. November 2012. [2] ↑: „Completely Fair Scheduler“ in: Wikipedia, the free encyclopedia. Abgerufen am 13. November 2012. [3] ↑: Ingo Molnár, „This is the CFS scheduler“. Abgerufen am 13. November 2012. [4] ↑: Daniel P. Bovet und Marco Cesati, „Understanding the Linux Kernel“. O'Reilly, 2000, abgerufen am 13. November 2012.