Linux Completely-Fair Scheduler (CFS)
Präemptive Verteilungsgerechtigkeit

Graphiken und Animationen

PreviousNext

Wie im echten Leben, so ist auch beim Scheduling von Threads auf eine CPU, der Begriff der Gerechtigkeit eine Frage der Definition. Im Grunde hat jede Schedulingmethode ein eigenes Ideal von Gerechtigkeit, welches angestrebt wird. Dieses schlägt sich in den Zeitpunkten der Schedulingaktivierung, der Auswahlstrategie des nächsten Threads und in der Länge der zugeteilten CPU-Zeit nieder. Bisher haben wir uns First-In-First-Out (FIFO) Scheduling als ein nicht-präemptives Schedulingverfahren und Round-Robin (RR) Scheduling als ein einfaches, präemptives Verfahren angeschaut.

Wenn wir uns nun die Frage stellen, welche Gerechtigkeit bei Round-Robin-Scheduling angestrebt wird, so kommen wir zum Begriff der Aktivierungsgerechtigkeit: Jeder Thread, wenn er gerade ausgeführt werden kannEr also bereit ist., wird gleich häufig aktiviert. Dieses Verfahren ist also insofern fair, als das jeder Thread gleich oft die Fackel in die Hand bekommt und Prozessorzeit verbrauchen könnte. Dabei wird der Scheduler in konstanten Zeitintervallen aufgerufen und muss nur die Elemente der Bereitliste sequentiell durchgehen, was sehr effizient (O(1)) implementierbar ist.

Allerdings gibt ein Problem mit der Aktivierungsgerechtigkeit: Schlafende Threads. Wenn ein Thread schläft bzw. auf die Beendigung eines I/O-Ereignisses wartet, so ist er nicht in der Bereitliste und kann demnach auch vom RR-Scheduler nicht aktiviert werden. Er ist also bei der Verteilung der CPU außen vor. Diese Form von Gerechtigkeit ist, wenn wir es auf die Essensausgabe übertragen würden, in etwa so fair wie zu sagen: Jeder der in der Schlange steht bekommt gleich oft etwas zu essen, außer man möchte, nach 18 Stunden stehen, auch einmal schlafen; Dann geht der Kelch an einem Vorbei und man ist wieder ganz am Ende der Schlange. Ist in gewisser Weise fair, aber irgendwie nicht den Bedürfnissen des Einzelnen entsprechend.

Zurück zu den Threads: Bei RR ist es so, dass ein schlafender Thread zunehmend im Anteil der Prozessorzeit, die er verbraucht hat, zurück fällt. Und dennoch werden, sobald man aufwacht gegebenenfalls andere bevorzugt. Daher hat diese Art des Scheduling einen Bias gegen I/O-intensive Threads, da sie inhärent weniger Prozessorzeit abbekommen können. Gerade im Bereich der Desktop-Computer ist dies aber tödlich, da die meisten unserer Programme auf unsere Eingabe warten. Oder um es etwas plakativer zu sagen: Mit RR-Scheduling ist meine Shell ziemlich rucklig. Und das ist ja nicht wirklich ein Zustand.

Daher wollen wir uns ein anderes Schedulingverfahren anschauen: Das Fair-Share Scheduling. Für diese Art des Schedulings verwenden wir einen anderen Begriff von Gerechtigkeit, der mehr an den Rechenbedürfnissen der einzelnen Threads orientiert ist: Die Verteilungsgerechtigkeit. Grundidee dabei ist, dass wir nicht mehr darauf schauen, wer wie oft die CPU bekommen hat, sondern wir uns darauf konzentrieren, welcher Thread wie lange die CPU hatte. Insgesamt möchten wir bei diesem Begriff der Gerechtigkeit erreichen, dass die CPU-Zeit, die zur Verfügung steht, möglichst gleichmäßig auf die Threads aufgeteilt wird, unabhängig davon wie häufig diese Threads schlafen. Die Grundüberzeugung bei dieser Gerechtigkeit ist also, dass jeder Thread, egal wie häufig er eine Mütze voller Schlaf braucht, den gleichen Anspruch auf die CPU-Zeit hat.

Wir erreichen diese Gerechtigkeit dadurch, dass wir einem schlafenden Thread ein Defizit an CPU-Zeit aufbauen lassen, welches er abfeiern kann, sobald seine Wartebedingung erfüllt ist. Von diesem Defizit kann der Thread dann so lange zehren, bis er mit den anderen Threads, die in der Zwischenzeit lustig vor sich hingerechnet haben, wieder gleich auf ist.

Dieses Fair-Share Scheduling ist der aktuelle Standard für normale ThreadsNormale Threads muss man hier im Gegensatz zu Threads mit Echtzeitanforderungen sehen. Zu diesen kommen wir noch später in der Vorlesung. Aber so viel vorneweg: Für einen Echtzeitthread ist es nicht wichtig viel CPU-Zeit zu bekommen, sondern es ist essentiell, Echtzeitthreads bis zu einem gewissen Zeitpunkt (Deadline) fertig werden. unter Linux. Und mit dem Completely Fair Scheduler (CFS) werden wir heute eine Implementierung kennen lernen, die Verteilungsgerechtigkeit anstrebt. Der CFS wurde 2007 in den Linux-Kern integriert und hat den sogenannten O(1)-Scheduler ersetzt. Dabei war das Versprechen der Verteilungsgerechtigkeit einer der zentralen Gründe das Schedulingverfahren zu ändern, obwohl CFS deutlich mehr Kosten zu Laufzeit (O(log n)) erzeugt.

Wenn wir auf die Implementierung schauen, so ist CFS im Falle von Single-Core Systemen relativ einfach (2000 Zeilen) und hat ein sehr klares Design. Allerdings ist auch dieser Scheduler mit seinen Anforderungen gewachsen, sodass der vollständige CFS Code inzwischen über 10k Codezeilen umfasst. Grund für diese gestiegene Komplexität sind vor allem die Multi-Core Unterstützung, Systeme mit nicht-uniformen SpeicherBei diesen sog. NUMA Systemen dauert der Zugriff auf Speicher nicht uniform lange, sondern unterschiedliche Speicherbereiche sind unterschiedlichen Prozessoren zugeteilt. Daher kommt es bei diesen Systemen darauf an, Threads besonders nahe an ihren Daten auszuführen., und das hierarchische Scheduling, zu dem wir später noch kommen werden. Damit Sie einen Eindruck von diesem Scheduler bekommen, habe ich ihnen eine herunter gebrochene CFS Variante erstellt, die nur den essentiellen Teil des Scheduler, exklusive aller Erweiterungen, enthält. Im Folgenden werden wir auch einzelne neuralgische Codestellen des CFS betrachten. Die vollständige Version des Schedulers finden sie hier bzw. an entsprechender Stelle im Linux-Kern.

Graphiken und Animationen

PreviousNext

Jeder Scheduler trifft seine Einplanungsentscheidungen auf einer gewissen Datenbasis. Diese Datenbasis ist der dynamische Zustand des Schedulers, in dem das notwendige Wissen über Threads und die Prozessoren, die bespielt werden sollen, gespeichert wird. Der Scheduler wird die Datenbasis fortlaufend anpassen umso Bezug auf seine bisherigen Entscheidungen nehmen zu können. Im Falle des RR-Schedulers ist diese Datenbasis relativ einfach, da er nur eine Queue braucht, aus der vorne Threads entnommen und an die Hinten Threads angehangen werden. Daher kommt der RR-Scheduler im Grunde damit aus, die Liste der lauffähigen Threads zu manipulieren.

Beim CFS ist eine etwas komplexere Datenlage nötig um die angestrebte Verteilungsgerechtigkeit zu erzielen: Für jeden Thread (nicht nur die Lauffähigen) erstellen wir ein virtuelles Laufzeitkonto, auf dem wir die verbrauchte CPU-Zeit dieses Threads verbuchen. Immer wenn ein Thread die CPU für eine gewisse Zeitspanne bekommen hat, "buchen" wir diese Zeit auf sein Konto. In der Linux-Implementierung heißt dieses Konto vruntime und hängt an einer struct sched_entityDa der CFS auch andere Zeitverbraucher verwaltet kann, wurde im Kern der Begriff des Threads auf sched entity verallgemeinert. Denken Sie sich zunächst aber für jedes auftreten einfach "Thread".:

struct sched_entity {
      ....
        u64                             vruntime;
      ...
};

Der CFS verwaltet nun eine Menge dieser Objekte und trifft anhand der vruntime seine Schedulingentscheidung. Dazu passieren bei einer Aktivierung des Schedulers immer 2 Dinge: Zuerst verbuchen wir die Zeit seit der letzten Aktivierung auf dem Konto des aktuell laufenden Threads. In einem zweiten Schritt betrachten wir uns alle Threads, die wir verwalten, und wählen denjenigen Thread mit dem niedrigsten virtuellen Laufzeitkonto aus und lasten ihn auf der CPU ein. Auf diese Weise erhält immer derjenige Thread die CPU, der gerade das größte Zeitdefizit aufweist, und damit den größten Aufholbedarf gegenüber der fairen Verteilung hat. Im Code sieht das dann in etwa so aus (Kommentare und Auslassungen sind hinzugefügt):

// Schritt 1: Update der vruntime
static void update_curr(struct cfs_rq *cfs_rq)
{
    // Wir bestimmen den laufenden Thread und die aktuelle Zeit
        struct sched_entity *curr = cfs_rq->curr;
        u64 now = rq_clock_task(rq_of(cfs_rq));
        u64 delta_exec;

    // Wenn niemand läuft, hat auch niemand Zeit verbraucht.
        if (!curr)
                return;

    // delta_exec: Wie lange wurde gerade gerechnet?
        delta_exec = now - curr->exec_start;
        if ((s64)delta_exec <= 0)
                return;

    // Aktuellen Zeitpunkt für nächste delta_exec Berechnung wegspeichern
        curr->exec_start = now;

    // [...]
        // Update der vruntime
        curr->vruntime += calc_delta_fair(delta_exec, curr);

    // [...]
}

Dabei wird die gerade verbrauchte CPU Zeit (delta_exec) noch mittels calc_delta_fair() gestaucht oder gestreckt, wozu wir allerdings später noch genauer kommen. Nachdem die vruntime aktualisiert wurde, muss nur noch der Thread mit dem niedrigsten Laufzeitkonto ausgewählt werden und fertig ist die Schedulerentscheidung.

Allerdings ist das Finden eines Objekts mit einer gewissen Eigenschaft in einer Menge von Objekten nicht so einfachIm Komplexitätstheoretischen Sinne einfach.: Für eine allgemeine Eigenschaft müssen wir alle Objekte durchgehen, ein Prädikat auf jedes Objekt anwenden, und dasjenige Objekt finden, was passt. Dieser Aufwand würde linear mit der Anzahl der untersuchten Objekte steigen. Das ist blöd und das will niemand haben, O(n) ist immer blöd, wenn n groß werden kann.

Allerdings haben wir das Glück, dass die Eigenschaft für die wir uns interessieren eine Zahl ist und wir denjenigen Thread suchen, der die kleinste Zahl hat. Wir suchen also in einer Eigenschaft die eine totale (zumindest partielle) Ordnung aufweist. Daher können wir einen Trick anwenden, der unseren Aufwand drastisch minimiert: Wir halten unsere Datenstruktur, in der wir die Threads verwalten, immer sortiert. Das bedeutet, dass jede Operation auf unserer Datenstruktur eine sortierte Menge an Threads vorfindet und ebenfalls eine sortierte Menge an Threads zurück lässt. Eine solche Datenstruktur ist der Rot-Schwarz-BaumWikipedia: Rot-Schwarz-Baum, der sowohl das sortierte Einfügen, sowie das Finden und Entfernen des kleinsten Objekts in O(log n) ermöglicht.

Im vereinfachten C-Pseudocode sieht dann der CFS Scheduler in etwa so aus:

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr) {
    // cfs_rq: Ready-Queue, implementiert als Rot-Schwarz-Baum

    // 1. Schritt Update
    update_curr(cfs_rq, curr);

    // 2. Find Minimum Thread
    struct sched_entity *next;
    next = rb_pick_first(cfs_rq); // Thread mit kleinster vruntime

    // next und curr können gleich sein!
    return next;
}

Im Beispiel sehen wir, wie der CFS die Threads A und B zuerst ihre Defizite aufholen lässt, bevor die Threads C und D überhaupt erst in Erwägung gezogen werden. Um Ihnen die Möglichkeit zu geben, mit diesem Scheduler ein bisschen zu spielen, habe ich eine Mockup-Implementierung des Schedulers in Python geschrieben, die Sie direkt hier im Browser ausführen und Live editieren können.

class sched_entity:
    def __init__(self, name, vruntime=0):
        self.name = name
        self.vruntime = vruntime

    def __repr__(self):
        return "(%s | %s)" % (self.name, self.vruntime)


cfs_rq = [
    sched_entity("A", 2),
    sched_entity("B", 10),
    sched_entity("C", 20),
    sched_entity("D", 23)
]

def update_curr(cfs_rq, curr):
    # Wir simulieren Zeit
    delta_exec = 6

    if curr:
        curr.vruntime += delta_exec

def rb_pick_first(cfs_rq):
    # Wir simulieren das Verhalten des Rot-Schwarz-Baums, indem wir
    # bei jedem Updaten die Liste in Place sortieren.

    cfs_rq[:] = list(sorted(cfs_rq, key=lambda se: se.vruntime))

    return cfs_rq[0]

def pick_next_entity(cfs_rq, curr):
    update_curr(cfs_rq, curr)

    next = rb_pick_first(cfs_rq)

    return next


curr = None
for i in range(0, 11):
    curr = pick_next_entity(cfs_rq, curr)
    print "Schedule:", curr

Um das Beispiel aus zu führen, müssen Sie auf Load Interpreter klicken und das Nachladen externer Ressourcen in ihrem Browser aktivieren.

Graphiken und Animationen

PreviousNext

Wir haben nur diskutiert, welchen Thread der CFS einplant, wenn er einmal aktiviert wird. Allerdings ist die Frage, für wie lange wir diesem Thread die CPU geben ebenfalls von zentraler Bedeutung. Würden wir einem Thread die CPU so lange geben, wie er diese brauchen würde, könnte ein Thread, der Pi ausrechnet, leicht die CPU für alle Zeiten monopolisieren und wir würden niemals eine Verteilungsgerechtigkeit hin bekommen. Daher ist es notwendig, dass CFS ein **präemptives Verfahren ist, welches die zugeteilte CPU einem Thread nach einer gewissen Zeit wieder entzieht. Aber nach welcher Zeit soll dies geschehen?

Wenn wir nur vom unserem Begriff von Gerechtigkeit ausgehen würden, so würden wir eigentlich haben wollen, dass die Laufzeitkonten der einzelnen Threads immer so nah wie möglich beisammenbleiben. Dies würde bedeuten, dass wir die maximale Verteilungsgerechtigkeit dann hin bekommen, wenn jeder Thread für genau einen Befehl drankommt und wir danach zu einem anderen Thread wechseln. Das ist natürlich eine blöde Idee, weil wir nur noch mit dem Wechseln der Threads beschäftigt wären und kaum noch Rechenzeit für den Benutzer übrighätten. Daher ist hier ein Kompromiss zwischen Verteilungsgerechtigkeit und Kosten für das Scheduling nötig.

Dazu geht der CFS den Weg, dass er seinen Begriff von Gerechtigkeit etwas aufweicht und sagt: "Innerhalb einer gewissen Periode soll jeder Thread gleich viel Rechenzeit bekommen". Innerhalb dieser Periode kann es dann durchaus Unterschiede geben, aber am Ende ist es wieder ausgeglichen. Der CFS geht dazu her und definiert die ideale Laufzeit eines Threads. Dazu wird die Periode durch die Anzahl der lauffähigen Threads geteilt. In der Realität könnte diese ideale Laufzeit allerdings bei vielen Threads sehr klein werden, weswegen es eine untere Schranke gibt, die nicht unterschritten wird. Lieber gibt der CFS noch mehr von seinem Gerechtigkeitsbegriff auf. Diese Realität macht auch immer aller kompliziert, wenn es um Gerechtigkeit geht…..

Graphiken und Animationen

PreviousNext

Nun, da wir die Grundzüge des CFS verstanden haben wollen wir uns einmal anschauen, wie sich dieser im Gegensatz zum Round-Robin Scheduler verhält. Im Beispiel auf den Folien sehen wir wie zwei Threads (A und B) auf der CPU eingeplant werden. Zu einem gewissen Zeitpunkt (wait(B)) schläft B ein und wartet auf einem externem Ereignis, welches dann zum Zeitpunkt (wake(B)) eintritt, wodurch B wieder lauffähig wird.

Im ersten Abschnitt, wo beide Threads lauffähig sind, sehen wir das sich RR und CFS im Grunde gleich verhalten. Beide geben die CPU reihum an die beiden Threads. Der einzige Unterschied ist das CFS die Länge der Zeitscheiben aus der Periode und aus der Anzahl der lauffähigen Threads berechnet, während RR konstant lange Zeitscheiben durchsetzt.

Die Dinge beginnen in dem Moment wo Thread B einschläft auseinander zu laufen: Plötzlich sinkt die Anzahl der lauffähigen Threads bei CFS auf 1, womit die zugeteilte Zeitscheibe plötzlich doppelt so lang wird. RR zieht weiterhin seine langen Zeitscheiben durch und zahl daher höhere Kosten für das Scheduling.

Der größte Unterschied ist dort zu beobachten, wo Thread B wieder aufwacht: Bei RR ist aktuell noch A dran und darf seine Zeitscheibe erst stumpf durchziehen. Danach geht RR wieder zu seiner Aktivierungsgerechtigkeit über und wechselt A und B ab. Bei CFS dagegen zieht das Aufwachen eines Threads allerdings eine Scheduleraktivierung nach sich bei der sofort auffällt, dass B ein riesiges Defizit an Rechenzeit hat. CFS lässt B dieses Defizit zuerst aufholen, bevor A überhaupt erst wieder in Erwägung gezogen wird.

Allerdings ist es nicht in jedem System gewünscht alle Threads gleich zu behandeln. Manchmal sind einige Threads wichtiger als andere Threads, was der Nutzer gerne in einer Priorisierung der Threads zum Ausdruck bringen möchte. Da bei CFS, die Länge der Zeitscheiben keinen Einfluss auf die Verteilung der Prozessorzeit hat (im Gegensatz zu RR), wendet man einen Trick um das grundlegende Prinzip von CFS beibehalten zu können: Langsame Uhren.

Bei CFS gibt ein Thread dann die CPU ab, wenn er mehr virtuelle Laufzeit auf sein Konto verbucht bekommen hat als ein anderer Thread. Daher können wir eine Priorisierung durchführen, indem wir die Uhr von wichtigeren Threads einfach langsamer laufen lassen. Diese Threads häufen so viel langsamer eine vruntime an und bekommen so, auf lange Sicht, einen größeren Anteil an der CPU Zeit.

Auf den (Ergänzungs-)Folien habe ich ihnen im Detail noch einmal erklärt, wie sich die Prioritäten, die bei Linux nice-Level heißen, sich auf das Verhalten des CFS auswirken. Zusammengefasst funktioniert es so, das wichtigere Threads längere Zeitscheiben bekommen als unwichtigere, aber alle Threads die gleiche virtuelle Laufzeit angeschrieben bekommen.

Graphiken und Animationen

PreviousNext

Allerdings ist es bei der Entwicklung einem Schedulingverfahren nicht ausreichend einen Gerechtigkeitsbegriff zu definieren und diesen zu implementieren, sondern man muss sich auch in die Rolle eines bösartigen Teilnehmers versetzen, der die Mechanismen zu seinem eigenen Vorteil ausnützen will und damit unseren Begriff von Gerechtigkeit ad absurdum zu führen. Im Falle des CFS ist diese kritische Situation darin begründet, dass die Prozessorzeit fair über Threads und nicht ProzesseJeder Thread lebt in einem Prozess. Ein Prozess kann mehrere Threads umfassen zugeteilt wird.

Ein bösartiger Angreifer würde einen Prozess starten und darin so viele Threads wie nur irgend möglich erzeugen. Dies hat zwei Dinge zur Folge: Zum einen wird der CFS die Zeitscheibe für jeden Thread auf die untere Schranke (z.B. 0.75ms) erhöhen, was zu einer großen Latenz für alle anderen Threads führt. Zum anderen bekommt ja jeder Thread den gleichen Anteil an den 100% CPU-Zeit. Wenn also alle anderen Prozesse 10 Threads haben und unser bösartiger Prozess 990 Threads hat, so kann der Angreifer 99% aller Prozessorzeit monopolisieren. Insgesamt käme im Schnitt nur alle 75 ms ein Thread eines anderen Prozesses dran. Das ist dann zwar nach unserer Definition fair, aber doch unbefriedigend.

Die Lösung, die man bei CFS für dieses Problem gefunden hat ist hierarchisches Scheduling. Dabei startet man mehrere Ebenen von Schedulerinstanzen. Auf der obersten Ebene werden die gesamten 100% CPU-Zeit an die Teilnehmer des Schedulings durch eine einzelne CFS-Instanz verteilt, die zum Beispiel einzelne Prozesse sein könnten. Damit bekommt dann jeder Prozess den gleichen Anteil an CPU-Zeit zugewiesen, egal wie er intern diese Zeit in Berechnungen umsetzt.

Da wir aber keinen Prozess auf einer CPU einlasten könnenEine CPU kann zu einem Zeitpunkt genau einen Thread ausführen., wird die zugewiesene Zeit aus der ersten Ebene durch eine zweite Ebene von CFS-Instanzen fair weiter nach unten verteilt. Im Beispiel würde bekommt die rote CFS Instanz 33% der gesamten CPU Zeit. Jeder der 6 Threads des roten Prozesses bekommt nach CFS dann 5.5% der gesamten CPU Zeit. Im grünen und im blauen Prozess, bekommt jeder Thread 16.5%. Wir erkaufen uns diese bessere Steuerung der Verteilungsgerechtigkeit allerdings dadurch, dass wir nun mehrere CFS-Aufrufe pro Scheduleraktivierung bekommen.

Dieses Prinzip von hierarchisch angeordneten CFS-Instanzen lässt sich prinzipiell noch tiefer Schachteln. So kann man zuerst die CPU-Zeit auf virtuelle Maschinen, dann auf Betriebsarten, dann auf Nutzer, dann auf Terminal-Sessions, dann auf Prozesse und schlussendlich auf Threads verteilen. Insgesamt ist es dabei so, dass auf jeder Zwischenebene CFS-Instanzen der CPU-Zeit, die von oben kommt, sind und nur auf der tiefsten Ebene, an den Blättern, Threads angedockt sind.