CPU-Scheduling

Ein CPU-Scheduler wählt den bereiten Prozess oder Thread aus, der als Nächstes auf einer CPU läuft. Die Regel, der er folgt, ist seine Strategie. Der Dispatcher setzt die Auswahl um, indem er die Ausführung zum ausgewählten Auftrag wechselt. Eine andere Strategie kann denselben Wechselmechanismus nutzen.

Verfolge die Zustandswechsel

Ein laufender Auftrag belegt eine CPU. Ein bereiter Auftrag könnte laufen, wartet aber, bis er an der Reihe ist. Ein blockierter Auftrag wartet auf ein Ereignis, etwa den Abschluss eines Festplattenlesevorgangs. Nur bereite Aufträge kommen für die Auswahl infrage.

Angenommen, ein Editor startet einen Festplattenlesevorgang, während ein Compiler bereit ist. Der Editor wechselt von „laufend“ zu „blockiert“, sodass der Compiler laufen kann. Wenn der Lesevorgang endet, macht ein Interrupt den Editor wieder bereit. Er läuft nicht unbedingt sofort: Die Strategie muss zwischen ihm und anderer bereiter Arbeit wählen.

Schedulingentscheidungen fallen, wenn ein Auftrag blockiert, endet, bereit wird oder unterbrochen und wieder in den Zustand „bereit“ versetzt wird. Auch die freiwillige Prozessorabgabe gibt die CPU frei. Verdrängung bedeutet, einem Auftrag die CPU zu entziehen, obwohl er hätte weiterlaufen können; der Auftrag behält seinen gespeicherten Zustand und kann später fortgesetzt werden.

Ein Timerinterrupt ermöglicht dem Kernel, eine Zeitscheibe durchzusetzen, selbst wenn ein Programm eine Schleife ausführt, ohne die CPU abzugeben. Auch eine abgeschlossene Ein-/Ausgabe kann eine Verdrängung auslösen, indem sie eine stärker bevorzugte Aufgabe bereit macht. Linux, Windows und macOS verwenden Scheduling mit Verdrängung.

Arbeit verläuft in Phasen

Programme wechseln zwischen CPU-Bursts, in denen sie rechnen, und Zeiträumen, in denen sie auf Ein-/Ausgabe warten. Ein CPU-gebundenes Programm wie ein Kodierer hat lange CPU-Bursts. Ein ein-/ausgabegebundenes Programm wie ein Editor rechnet häufig kurz und wartet dann. Wenn ein Editor nach einem Tastendruck schnell bedient wird, kann das die Reaktionsfähigkeit verbessern, ohne dass er insgesamt viel CPU-Zeit erhält.

Der Dispatcher sichert den Zustand der alten Aufgabe, stellt die Register der ausgewählten Aufgabe wieder her und setzt ihre Befehlsfolge im Benutzermodus fort. Die Dispatch-Latenz ist die Zeit für die Übergabe der Ausführung. Ein Wechsel beeinträchtigt auch Caches und den Translation Lookaside Buffer, kurz TLB, der Adressübersetzungen zwischenspeichert. Die nächste Aufgabe muss sie möglicherweise neu füllen, sodass die Zeit zum Sichern der Register nur einen Teil des Aufwands ausmacht.

Drei Zeitskalen des Schedulings

Der langfristige Scheduler lässt eingereichte Aufträge zu und steuert, wie viele sich im System befinden. Der mittelfristige Scheduler kann ganze Prozesse suspendieren, indem er sie aus dem Speicher auslagert und später wiederherstellt. Der kurzfristige Scheduler wählt die nächste bereite Aufgabe und wird häufig tätig. Allzwecksysteme stützen sich hauptsächlich auf diese letzte Aufgabe; Stapelverarbeitungssysteme und Cluster können auch die Zulassung ausdrücklich steuern.

Beginne einen Strategievergleich mit einfachen Aufträgen, die nur die CPU nutzen und deren Längen bekannt sind. Verändere dann jeweils ein Merkmal: Ungleiche Längen zeigen die Verzögerungen bei FIFO, spätere Ankünfte zeigen die Grenzen von Verfahren ohne Verdrängung, Ein-/Ausgabe bietet Möglichkeiten zur Überlappung von Arbeit und unbekannte Längen erfordern Vorhersage oder Rückkopplung.

Ein Ablaufplan zeigt dir, wann Aufträge laufen. Eine Kennzahl zeigt dir, welcher Teil dieses Ablaufplans wichtig ist. Halte für jeden Auftrag die Ankunft, die erste Ausführung und den Abschluss fest, bevor du Mittelwerte berechnest.

Unterscheide die drei Zeiten

Die Durchlaufzeit misst den gesamten Zeitraum von der Ankunft bis zum Abschluss. Die Antwortzeit misst die Verzögerung bis zur ersten Ausführung. Die Wartezeit summiert alle Zeiträume, in denen ein Auftrag bereit ist, aber nicht läuft.

Bei einem Auftrag, der nur die CPU nutzt, entspricht die Durchlaufzeit der Wartezeit plus CPU-Laufzeit. Bei Ein-/Ausgabe gehört auch die blockierte Zeit zur Durchlaufzeit. Würdest du nur die CPU-Zeit abziehen, wäre die berechnete Wartezeit zu groß. Die Antwortzeit wird hier anhand der ersten Ausführung definiert; ein Dienst für Benutzer kann die Zeit bis zu seiner ersten Ausgabe gesondert messen.

Rechne ein FIFO-Zeitablaufdiagramm durch

A kommt bei 0 ms an und benötigt 8 ms CPU-Zeit. B kommt bei 1 ms an und benötigt 4 ms. C kommt bei 2 ms an und benötigt 2 ms. Ohne Wechselaufwand ergibt FIFO:

• A: 0–8 ms.
• B: 8–12 ms.
• C: 12–14 ms.

Die mittlere Durchlaufzeit beträgt $\frac{8+11+12}{3}=\frac{31}{3}\approx \mathrm{10,33}$ ms. Die mittlere Antwortzeit und die mittlere Wartezeit betragen beide $\frac{0+7+10}{3}=\frac{17}{3}\approx \mathrm{5,67}$ ms. Sie stimmen überein, weil jeder Auftrag einmal ohne Unterbrechung läuft. Bei Verdrängung kann ein Auftrag nach seinem ersten Einsatz erneut warten, sodass die Wartezeit die Antwortzeit übersteigen kann.

Miss die gesamte Arbeitslast

Der Durchsatz zählt die abgeschlossenen Aufträge pro verstrichener Zeiteinheit. Der Ablaufplan schließt drei Aufträge in 14 ms ab, etwa 214,29 Aufträge/s. Die CPU-Auslastung ist die beschäftigte CPU-Zeit geteilt durch die verstrichene Zeit; hier beträgt sie 100 %, weil die CPU nie untätig ist. Gib das Messintervall an: Eine zusätzliche Leerlaufzeit nach dem Abschluss würde beide Werte verändern.

Hohe Auslastung kann trotzdem mit langen Wartezeiten einhergehen. Sie muss auch nicht bedeuten, dass die gesamte beschäftigte Zeit für nützliche Anwendungsarbeit verwendet wird: Reale Messungen können Wechsel und andere Kernelarbeit als beschäftigte Zeit zählen. Gib an, ob eine Aufwandsberechnung beschäftigte Zeit oder nützliche Arbeit misst.

Wähle, was du optimieren möchtest

Bei Stapelverarbeitung ist oft die mittlere Durchlaufzeit wichtig. Bei interaktiver Arbeit ist eine schnelle Antwort wichtig. Gemeinsam genutzte Dienste benötigen neben Durchsatz auch fairen Zugang. Verhungern bedeutet, dass ein ausführbarer Auftrag unbegrenzt wartet; ein guter Mittelwert allein kann also keine faire Behandlung belegen.

Untersuche einzelne Verzögerungen und den oberen Randbereich der Verteilung. Die Antwortzeit am 99. Perzentil beschreibt die Verzögerung, die ungefähr 99 % der Beobachtungen nicht überschreiten; einzelne starke Verzögerungen können in einem niedrigen Mittelwert verschwinden. Ziehe immer die Ankunftszeit des jeweiligen Auftrags ab und zähle seine Laufzeiten zur Bedienzeit, niemals zur Wartezeit.

FIFO, auch FCFS genannt, führt bereite Aufträge in Ankunftsreihenfolge aus. Es arbeitet ohne Verdrängung: Ein später ankommender Auftrag kann einen laufenden CPU-Burst nicht unterbrechen. In Beispielen mit Aufträgen, die nur die CPU nutzen, läuft jeder ausgewählte Auftrag bis zum Ende.

Erkenne den Konvoieffekt

A, B und C kommen gleichzeitig an. A benötigt 60 ms; B und C benötigen jeweils 6 ms. Steht A an erster Stelle, führt FIFO A 0–60, B 60–66 und C 66–72 aus. Die Durchlaufzeiten sind 60, 66 und 72 ms, im Mittel 66 ms. Die kurzen Aufträge verbringen den größten Teil ihrer Zeit mit Warten hinter A. Das ist der Konvoieffekt.

Shortest Job First (SJF) wählt unter den bereiten Aufträgen den kürzesten nächsten CPU-Burst und verdrängt ihn nicht. Bei denselben Ankünften führt es B 0–6, C 6–12 und dann A 12–72 aus. Die mittlere Durchlaufzeit beträgt nun $\frac{6+12+72}{3}=30$ ms. Die gesamte CPU-Arbeit beträgt weiterhin 72 ms; die Verbesserung entsteht dadurch, dass kurze Aufträge früher enden.

Warum hilft das? Läuft ein langer CPU-Burst unmittelbar vor einem kurzen, warten beide Aufträge auf die gesamte vorherige Arbeit. Vertauschst du nur diese beiden, verkürzt sich die Verzögerung des kurzen Auftrags um die Länge des langen CPU-Bursts, während die Verzögerung des langen Auftrags nur um die Länge des kurzen CPU-Bursts zunimmt. Wiederholtes Vertauschen ordnet die CPU-Bursts aufsteigend. Wenn alle Aufträge gleichzeitig ankommen und ihre Längen bekannt sind, minimiert SJF die mittlere Durchlaufzeit und Wartezeit; in diesem Fall ohne Verdrängung und ohne Ein-/Ausgabe entspricht auch die Antwortzeit bis zur ersten Ausführung der Wartezeit.

Beschränke die Auswahl auf bereite Aufträge

Nun kommt A bei 0 ms an, während B und C bei 10 ms ankommen. Bei 0 ms ist A die einzige Wahl. SJF ohne Verdrängung führt A 0–60, B 60–66 und C 66–72 aus. Die Durchlaufzeiten sind 60, 56 und 62 ms, im Mittel etwa 59,33 ms. SJF kann weder einen zukünftigen Auftrag berücksichtigen noch einen bereits gestarteten CPU-Burst unterbrechen.

FIFO vermeidet Verhungern, wenn vorausgehende Aufträge die CPU irgendwann freigeben. Unter SJF kann ein langer wartender Auftrag verhungern, wenn ständig kurze Arbeit ankommt.

Sage einen CPU-Burst vorher

Der nächste CPU-Burst ist meist unbekannt. Exponentielle Glättung kombiniert den zuletzt gemessenen CPU-Burst mit der vorherigen Vorhersage:

Dabei ist $t_n$ der gemessene CPU-Burst, ${\tau }_n$ die vorherige Vorhersage und $\alpha$ ein Gewicht zwischen 0 und 1. Beginnst du mit 10 ms und verwendest $\alpha =\mathrm{0,5}$, ergeben gemessene 6 ms eine Vorhersage von 8 ms. Anschließende 4 ms ergeben 6 ms; weitere 6 ms belassen die Vorhersage bei 6 ms. Bei Gewicht null haben Messungen keinen Einfluss; bei Gewicht eins zählt nur die neueste Messung. Vorhergesagt wird die Länge des CPU-Bursts, nicht die Größe der Programmdatei oder die Zeilenanzahl.

Shortest Time-to-Completion First (STCF), auch Shortest Remaining Time First oder SRTF genannt, ist SJF mit Verdrängung. Vergleiche bei einer Ankunft oder einem Abschluss die CPU-Zeit, die jeder bereite Auftrag noch benötigt. Ein neu ankommender Auftrag unterbricht den laufenden, wenn er weniger Zeit benötigt, als dem laufenden noch bleibt.

Vergleiche die Restlaufzeit

A benötigt 60 ms und kommt bei 0 ms an. B und C benötigen jeweils 6 ms und kommen bei 10 ms an. A läuft 10 ms, sodass 50 ms verbleiben. Bei 10 ms gewinnt B, weil 6 ms weniger als 50 ms sind; C hat dieselbe Länge, daher entscheiden die Ankunftsreihenfolge und dann der Name über den Gleichstand.

Das Zeitablaufdiagramm zeigt A 0–10, B 10–16, C 16–22, A 22–72. Die Durchlaufzeiten sind für A 72 ms, für B 6 ms und für C 12 ms, im Mittel 30 ms. Die Antwortzeiten sind 0, 0 und 6 ms, im Mittel 2 ms. SJF ohne Verdrängung ergibt bei diesen Ankünften im Mittel etwa 59,33 ms Durchlaufzeit und 35,33 ms Antwortzeit.

Ziehe immer die bereits erhaltene Bedienzeit ab. Es wäre falsch, einen neuen CPU-Burst von 12 ms mit den ursprünglichen 60 ms von A zu vergleichen, wenn A nur noch 5 ms vor sich hätte. STCF würde A zuerst abschließen. Bei bekannten Längen für Aufträge ohne Ein-/Ausgabe und ohne Wechselaufwand minimiert STCF die mittlere Durchlaufzeit bei beliebigen Ankünften. Lange Aufträge können bei einem anhaltenden Strom kürzerer Arbeit trotzdem verhungern.

Wenn alle Aufträge ohne Ein-/Ausgabe gleichzeitig ankommen, ergeben SJF und STCF dieselbe Reihenfolge. Der laufende kürzeste Auftrag wird nur noch kürzer, sodass kein wartender Auftrag zum Grund für seine Verdrängung wird.

Nutze die blockierte Zeit eines anderen Auftrags

Ein blockierter Auftrag kann die CPU nicht nutzen. Seine Wartezeit auf Ein-/Ausgabe bietet Gelegenheit, andere bereite Arbeit auszuführen, selbst bei einer Strategie ohne Verdrängung. Verdrängung wird wieder wichtig, wenn eine abgeschlossene Ein-/Ausgabe einen kurzen CPU-Burst bereit macht, während ein anderer Auftrag läuft.

Betrachte A mit fünf CPU-Bursts von je 10 ms und einem Festplattenlesevorgang von 10 ms nach jedem seiner ersten vier CPU-Bursts. B benötigt einen CPU-Burst von 50 ms. Beide kommen bei 0 ms an. Bleibt die CPU während der Lesevorgänge von A untätig und verzögert B, bis A endet, schließt A bei 90 ms und B bei 140 ms ab.

Behandle jeden wieder bereiten CPU-Burst von A als kurze bereite Arbeit:

• A läuft 0–10; sein Lesevorgang belegt 10–20, während B läuft.
• A kehrt für 20–30 zurück; B hat noch 40 ms vor sich, daher gewinnen die 10 ms von A.
• B läuft während des nächsten Lesevorgangs 30–40. Der Wechsel wiederholt sich.
• Der letzte CPU-Burst von A läuft 80–90; B beendet seine letzten 10 ms während 90–100.

A endet weiterhin bei 90 ms, B aber bei 100 ms. Die CPU führt in 100 ms verstrichener Zeit 100 ms Arbeit aus. Festplatten- und CPU-Aktivität überlappen; die CPU führt A nicht aus, während A blockiert ist. Ein Geräteinterrupt markiert A nach jedem Lesevorgang als bereit. Danach vergleicht STCF den neuen CPU-Burst von A mit der verbleibenden Arbeit von B.

Das Round-Robin-Verfahren (RR) verwaltet eine FIFO-Bereitwarteschlange und gibt dem Auftrag an ihrer Spitze höchstens ein Zeitquantum, also eine Zeitscheibe. Ein Auftrag, der endet oder blockiert, gibt die CPU vorzeitig ab. Ein Auftrag, der beim Ablauf seiner Zeitscheibe noch bereit ist, wandert ans Ende.

Verfolge die Einsätze, bevor du Zeiten berechnest

A, B und C kommen bei 0 ms an und benötigen jeweils 9 ms. Mit einem Zeitquantum von 3 ms führt RR aus:

• Erste Runde: A 0–3, B 3–6, C 6–9.
• Zweite Runde: A 9–12, B 12–15, C 15–18.
• Letzte Runde: A 18–21, B 21–24, C 24–27.

Die ersten Ausführungen liegen bei 0, 3 und 6 ms, die mittlere Antwortzeit beträgt also 3 ms. Die Abschlüsse liegen bei 21, 24 und 27 ms, die mittlere Durchlaufzeit beträgt also 24 ms. FIFO ergibt eine mittlere Antwortzeit von 9 ms und eine mittlere Durchlaufzeit von 18 ms. Hier startet RR alle zügig, verschiebt aber den ersten abgeschlossenen Auftrag bis 21 ms.

RR teilt den CPU-Zugriff auf, während Aufträge konkurrieren; es gleicht die Abschlusszeitpunkte nicht an. Ein kurzer Auftrag kann bei seinem ersten Einsatz enden. Bei einer festen Anzahl von $n$ bereiten Aufträgen und einem Zeitquantum $q$ beträgt die Wartezeit zwischen zwei Einsätzen ohne Wechselaufwand höchstens $(n-1)q$. Fortlaufende Ankünfte, andere Prioritätsklassen und Einschränkungen, auf welchen CPUs Aufträge laufen dürfen, verändern die Voraussetzungen dieser Schranke.

Behandle Ankünfte am Ende einer Zeitscheibe

Verwende die Ankunftsreihenfolge und bei Gleichständen die alphabetische Reihenfolge. Ein Auftrag, der genau beim Ablauf einer Zeitscheibe ankommt, wird vor dem verdrängten Auftrag eingereiht. Wenn A bei 0 ms ankommt und 8 ms benötigt, B bei 1 ms ankommt und 4 ms benötigt und C bei 2 ms ankommt und 2 ms benötigt, ergibt ein Zeitquantum von 2 ms: A 0–2, B 2–4, C 4–6, A 6–8, B 8–10, A 10–14.

Der letzte Zeitraum von A enthält zwei aufeinanderfolgende Einsätze ohne Konkurrenten. Die Antwortzeiten sind 0, 1 und 2 ms; die Durchlaufzeiten sind 14, 9 und 4 ms. Ihre Mittelwerte betragen 1 ms und 9 ms. Kehrt ein blockierter Auftrag beim einfachen RR zurück, wird er für einen neuen Einsatz eingereiht; er reserviert während der Blockierung keine ungenutzte CPU-Zeit.

Stimme das Zeitquantum auf seinen Aufwand ab

Ein sehr großes Zeitquantum lässt RR sich für CPU-Bursts, die kürzer als dieses Quantum sind, wie FIFO verhalten. Ein winziges Zeitquantum erzeugt viele Ausführungsübergaben und wiederholte Beeinträchtigungen der Caches. In einer einfachen timerbasierten Umsetzung entspricht das Zeitquantum einer ganzen Anzahl von Timerperioden.

Bei einem Wechselaufwand $s$ nach jeder nützlichen Zeitscheibe der Länge $q$ beträgt der ungefähre Aufwandsanteil $\frac{s}{q+s}$. Ein Wechsel von 0,1 ms kostet bei einer Zeitscheibe von 1 ms etwa 9,1 %, bei einer Zeitscheibe von 10 ms aber etwa 0,99 %. Längere Zeitscheiben amortisieren den Wechselaufwand, indem sie ihn auf mehr nützliche Arbeit verteilen.

Eine verbreitete Faustregel zur Größenwahl besagt, dass die meisten CPU-Bursts, zum Beispiel etwa 80 %, innerhalb einer Zeitscheibe enden sollten. Die richtige Wahl hängt von den gemessenen CPU-Burst-Längen und den Antwortverzögerungen ab, die die Arbeitslast verträgt. Zähle Wechsel zwischen Aufgaben getrennt von Timerereignissen, bei denen lediglich dieselbe einzige bereite Aufgabe weiterläuft.

Ein Prioritätsscheduler führt den bereiten Auftrag mit der höchsten Priorität aus. Aufträge gleicher Priorität können FIFO oder dem Round-Robin-Verfahren folgen. In einer Variante mit Verdrängung erhält ein neu bereiter Auftrag mit höherer Priorität sofort die CPU; in einer Variante ohne Verdrängung wartet er, bis der laufende Auftrag sie freigibt.

Lies die Richtung der Skala

Prioritätszahlen haben keine einheitliche Richtung. Verwende in den hiesigen Lehrbuchbeispielen kleinere Zahlen für höhere Priorität. Linux-Nice-Werte folgen derselben Richtung, aber Windows-Prioritätsstufen und Linux-Echtzeitprioritäten verwenden größere Zahlen für höhere Priorität.

A, B und C kommen bei 0 ms mit CPU-Bursts von 4, 3 und 5 ms und den Prioritäten 2, 1 und 3 an. Prioritätsscheduling ohne Verdrängung führt B 0–3, A 3–7 und C 7–12 aus. Ihre Wartezeiten sind 0, 3 und 7 ms, im Mittel etwa 3,33 ms; die Durchlaufzeiten sind 3, 7 und 12 ms, im Mittel etwa 7,33 ms.

Eine interne Priorität entsteht aus gemessenem Verhalten wie CPU-Nutzung oder Wartezeiten auf Ein-/Ausgabe. SJF leitet den Rang aus der vorhergesagten Burst-Länge ab. Eine externe Priorität stammt von einer Person, etwa einem Administrator, der eine Sicherung als weniger dringend einstuft. Keine der beiden Varianten stellt sicher, dass Arbeit mit niedriger Priorität bei einem ständigen Zustrom höher priorisierter Arbeit Zeit erhält.

Erhöhe die Priorität beim Warten

Alterung erhöht schrittweise die Priorität eines wartenden Auftrags. Verbessert sich der Rang alle 100 ms um eins, erreicht ein Auftrag, der bei Priorität 20 beginnt, nach 2 s Wartezeit im Zustand „bereit“ die höchste Priorität 0. Der höhere Rang bringt ihn in Konkurrenz mit bevorzugter Arbeit; Regeln für Gleichstände bestimmen die Reihenfolge von Aufträgen auf demselben Rang.

Verhungern ist ausbleibender Fortschritt, weil wiederholt andere Arbeit ausgewählt wird. Alterung wirkt dem entgegen, indem sie den Rang im Laufe der Zeit verändert. Sie dient einem anderen Zweck als die Vorhersage der Burst-Länge: Ein lange wartender langer Auftrag kann einen Einsatz verdienen, obwohl sein CPU-Burst lang bleibt.

Verfolge die Abhängigkeit bei Prioritätsinversion

Ein Auftrag H mit hoher Priorität kann an einer Sperre blockiert sein, die der Auftrag L mit niedriger Priorität hält. Ein Auftrag M mit mittlerer Priorität kann L verdrängen. Nun kann H nicht fortfahren, obwohl M eine niedrigere Priorität als H hat: L muss erst laufen, um die Sperre freizugeben. Das ist eine Prioritätsinversion.

Bei der Prioritätsvererbung erbt L vorübergehend die Priorität von H, solange L die Sperre hält, die H benötigt. M kann L nicht mehr von der CPU fernhalten. L läuft, gibt die Sperre frei und verliert die geerbte Priorität; H wird bereit und kann laufen.

Eine Erhöhung der Priorität von H selbst gibt die Sperre nicht frei: H bleibt blockiert. Entscheidend ist, den Thread auszuführen, der die Abhängigkeit auflösen kann. 1997 trat bei Mars Pathfinder ein Problem durch Prioritätsinversion auf, das durch Einschalten der Prioritätsvererbung behoben wurde.

Eine mehrstufige Rückkopplungswarteschlange (MLFQ) kombiniert Prioritäten mit dem Round-Robin-Verfahren. Ihr Ziel ist es, die Bedienung kurzer Aufträge anzunähern und interaktive Arbeit reaktionsfähig zu halten, ohne dass ihr die zukünftige Laufzeit jedes Auftrags mitgeteilt wird. Die jüngste CPU-Nutzung liefert die Rückkopplung.

Wende die Warteschlangenregeln an

Jeder bereite Auftrag gehört zu einer Prioritätswarteschlange. Die grundlegende Variante mit Verbrauchserfassung folgt vier Regeln:

1. Wähle die Warteschlange mit der höchsten Priorität, die bereite Arbeit enthält.
2. Wechsle innerhalb dieser Warteschlange Aufträge gleicher Priorität im Round-Robin-Verfahren ab.
3. Setze einen neuen Auftrag in die oberste Warteschlange.
4. Stufe einen Auftrag herab, wenn er sein CPU-Zeitkontingent auf seiner aktuellen Stufe verbraucht. Erfasse dabei die Nutzung über alle Einsätze und Ein-/Ausgabeunterbrechungen hinweg.

Ein Zeitquantum begrenzt einen Einsatz. Ein Kontingent begrenzt die gesamte Bedienzeit auf einer Prioritätsstufe. Eine Stufe kann vor der Herabstufung mehrere Zeitquanten erlauben. Auf der untersten Stufe bleibt ein Auftrag bei einer Herabstufung in der untersten Warteschlange.

So erhält ein neuer Auftrag die Chance, schnell zu enden. Ein Auftrag, der wiederholt CPU-Zeit verbraucht, zeigt einen längeren Bedarf und steigt ab. Ein kurzer CPU-Burst, der blockiert, verbraucht wenig Kontingent, sodass interaktive Aufträge tendenziell länger oben bleiben.

Verfolge einen langen und einen neu ankommenden Auftrag

Verwende die Warteschlangen Q2, Q1 und Q0 mit Q2 als höchster Stufe, Zeitquanten von 10 ms und Kontingenten von 10 ms auf jeder Stufe sowie ohne Anhebung während dieses Ablaufs. A benötigt 200 ms und kommt bei 0 ms an. Er läuft in Q2 von 0–10, in Q1 von 10–20 und danach in Q0.

Bei 100 ms hat A 100 ms CPU-Zeit erhalten. B kommt an und benötigt 20 ms. B gelangt in Q2, verdrängt A und läuft dann 100–110 in Q2. Er hat das Kontingent dieser Stufe verbraucht und fällt auf Q1. Q1 hat Vorrang vor Q0, wo sich A befindet. Daher läuft B 110–120 und endet. A läuft bei 120 weiter und schließt seine verbleibenden 100 ms bei 220 ms ab. Die Durchlaufzeit von B beträgt 20 ms, obwohl er nach einem viel längeren Auftrag ankommt.

Verfolge die verbleibende Arbeit von A, während B läuft: Sie bleibt bei 100 ms. Während B bedient wird, vergeht Zeit, aber A erhält in dieser Zeit keine CPU-Bedienung.

Unterscheide Warten und CPU-Verbrauch

Ein Editor, der 1 ms läuft und auf Eingaben wartet, verbraucht ein Kontingent von 10 ms über zehn solche CPU-Bursts. Blockierte Zeit wird nicht auf das CPU-Zeitkontingent angerechnet. Bei strenger Verbrauchserfassung summieren sich diese kurzen CPU-Bursts dennoch, sodass der Editor schließlich absteigt, sofern er nicht zuvor durch eine Prioritätsanhebung zurückgesetzt wird.

Eine frühe MLFQ-Regel stufte nur Aufträge herab, die ein ganzes ununterbrochenes Zeitquantum verbrauchten. Ein Auftrag, der die CPU kurz vor Ablauf abgab, behielt seine Priorität. Diese Regel machte interaktive Arbeit reaktionsfähig, erlaubte aber auch gezielte Manipulation. Die kumulative Erfassung der CPU-Nutzung schließt diese Lücke.

Niedrigere Warteschlangen laufen immer dann, wenn alle höheren Warteschlangen keine bereite Arbeit enthalten. Ein blockierter Auftrag mit höherer Priorität hindert Aufträge mit niedrigerer Priorität nicht daran, die CPU zu nutzen. Bei anhaltendem Bedarf mit hoher Priorität benötigt niedriger priorisierte Arbeit einen zusätzlichen Schutz vor Verhungern, den regelmäßige Anhebungen bieten.

Rückkopplung trennt Aufträge auf nützliche Weise, doch das frühere Verhalten eines Auftrags kann aufhören, seinen aktuellen Bedarf abzubilden. Eine lange Berechnung kann später interaktiv werden. Zugleich kann ein Auftrag in der untersten Warteschlange unbegrenzt warten, wenn höhere Warteschlangen beschäftigt bleiben.

Beurteile jeden Auftrag regelmäßig neu

Eine Prioritätsanhebung verschiebt nach einer Zeitspanne $S$ alle Aufträge zurück in die oberste Warteschlange. Sie ermöglicht wartenden Aufträgen, sich die oberste Warteschlange zu teilen, und lässt den Scheduler verändertes Verhalten neu erlernen. Ein angehobener CPU-gebundener Auftrag verbraucht später sein Kontingent und steigt wieder ab.

Betrachte die frühen MLFQ-Regeln: Zwei interaktive Aufträge geben die CPU immer vor Ablauf einer vollständigen Zeitscheibe von 10 ms ab und halten Q2 zusammen beschäftigt. Ein CPU-gebundener Auftrag wartet in Q0. Ohne Anhebungen erhält er keine Bedienung. In einem sich wiederholenden Ablaufplan, in dem eine Anhebung alle 100 ms ihm einen Einsatz von 10 ms auf der höchsten Stufe gibt, bevor er herabgestuft wird und höher priorisierte Arbeit den Rest ausfüllt, erhält er 10 % der CPU. Dieser Prozentsatz ergibt sich aus diesem Ablauf; eine Anhebung weist keinen allgemeinen festen Anteil zu.

Ein langes Intervall zwischen Anhebungen führt zu langen Wartezeiten zwischen Einsatzmöglichkeiten. Ein sehr kurzes Intervall setzt CPU-gebundene Arbeit wiederholt zurück und schwächt den Vorteil interaktiver Arbeit. Entwürfe haben Intervalle um eine Sekunde verwendet, doch die Wahl hängt vom Verhalten der Arbeitslast und den Zielen für die Antwortzeit ab.

Erfasse den Verbrauch über Prozessorabgaben hinweg

Ein separates Problem ist die Manipulation. Nach der frühen Regel für vollständige Zeitscheiben kann ein Programm 9 ms laufen, eine Ein-/Ausgabe von 1 ms anfordern und dies wiederholen. Es verbraucht nie eine ganze Zeitscheibe von 10 ms am Stück und behält daher die höchste Priorität, während es fast die gesamte verfügbare CPU-Zeit verbraucht.

Bei einem kumulativen Kontingent von 10 ms verbraucht der erste CPU-Burst 9 ms und lässt 1 ms übrig. Nach der Ein-/Ausgabe erschöpft eine weitere Millisekunde das Kontingent und der Auftrag wird während seines zweiten CPU-Bursts herabgestuft. Eine Ein-/Ausgabeanfrage ändert den Zustand; sie löscht nicht die bereits erhaltene Bedienzeit. Die Erfassungsregel verhindert diese Taktik auch ohne Anhebung.

Stimme die Stufen ab

Wähle die Anzahl der Warteschlangen, das Zeitquantum jeder Warteschlange, das Kontingent jeder Stufe und das Intervall zwischen Anhebungen. Obere Warteschlangen verwenden meist kurze Zeitquanten, zum Beispiel 10 ms, um schnell zwischen interaktiven Aufträgen zu wechseln. Untere Warteschlangen können viel längere Zeitquanten verwenden, manchmal mehrere hundert Millisekunden, um bei anhaltender Berechnung Wechsel zu verringern.

Das Kontingent kann unabhängig vom Zeitquantum wachsen. Eine Stufe mit einem Zeitquantum von 5 ms und einem Kontingent von 15 ms kann drei vollständige Einsätze vor der Herabstufung erlauben. Ein größeres Kontingent verzögert die Einstufung als lang laufend; ein größeres Zeitquantum verlängert einen einzelnen Einsatz.

Der Zeitteilentwurf von Solaris veranschaulicht tabellenbasierte Rückkopplung: Seine klassische konfigurierbare Tabelle hat 60 Prioritätsstufen, deren Zeitquanten von etwa 20 ms bei hoher Priorität bis zu einigen hundert Millisekunden bei niedriger Priorität reichen. Klassische BSD-Entwürfe berechneten die Priorität stattdessen aus der jüngsten CPU-Nutzung, deren Einfluss mit der Zeit abnimmt. Beide lassen den Einfluss früherer CPU-Nutzung schwinden, sodass die weit zurückliegende Vorgeschichte eines Threads seine Behandlung nicht dauerhaft bestimmt.

Scheduling mit proportionalen Anteilen soll die CPU-Bedienzeit gemäß zugewiesenen Anteilen aufteilen. Beim Lotterie-Scheduling besitzt jeder ausführbare Auftrag Tickets. Ein zufälliges Gewinnticket wählt den Auftrag für die nächste gleich lange Zeitscheibe. Die Gewinnchance eines Auftrags ist seine Ticketzahl geteilt durch die Zahl aller Tickets ausführbarer Aufträge.

Finde ein Gewinnticket

A besitzt 100 Tickets, B 50 und C 250. Nummeriere die 400 Tickets von 0 bis 399. A besitzt 0–99, B besitzt 100–149 und C besitzt 150–399. Eine Ziehung von 300 wählt C.

Eine listenbasierte Implementierung zieht eine Zahl und summiert die Ticketzahlen. Die laufenden Summen sind 100 nach A, 150 nach B und 400 nach C. Halte bei der ersten Summe an, die echt größer als die gezogene Zahl ist. „Größer oder gleich“ würde Tickets an den Grenzen falsch zuordnen: Die gezogene 100 gehört zu B. Wenn Inhaber größerer Ticketzahlen vorne stehen, wird diese Listensuche im Mittel kürzer.

Unterscheide Erwartung und Garantie

Hat A 75 Tickets und B 25, beträgt der erwartete Anteil von A 75 %. Bei 100 unabhängigen Ziehungen gleich langer Zeitscheiben, während beide ausführbar sind, erwartet A 75 Gewinne. Die Standardabweichung beträgt:

$\sqrt{100\times \mathrm{0,75}\times \mathrm{0,25}}\approx \mathrm{4,33}$ Zeitscheiben.

Ein Ergebnis von etwa 71–79 Gewinnen liegt ungefähr innerhalb einer Standardabweichung vom Mittelwert; es ist kein garantierter Bereich. Bei kurzen Laufzeiten kann das Ergebnis deutlich vom angestrebten Verhältnis 3:1 abweichen. Je größer das Beobachtungsfenster, desto kleiner wird die relative zufällige Schwankung. Die Lotterie bietet wahrscheinlichkeitsbasierte Fairness, keine exakte Aufteilung über ein endliches Zeitfenster und keine beschränkte Wartezeit bis zum nächsten Einsatz.

Für zwei Aufträge mit gleicher Ticketzahl und gleichem CPU-Bedarf teilt die Unfairnesskennzahl U den früheren Abschlusszeitpunkt durch den späteren. Das Verhältnis erreicht 1, wenn sie gleichzeitig enden, und ist kleiner, wenn einer viel früher endet. Dieses Verhältnis der Abschlusszeitpunkte schwankt besonders stark bei kurzen Aufträgen unter Lotterie-Scheduling.

Verteile Tickets über Benutzer und Abhängigkeiten hinweg

Eine Ticketwährung ermöglicht es einem Benutzer, einen zugewiesenen globalen Anspruch lokal aufzuteilen. Benutzer X hat 200 globale Tickets und weist X1 300 lokale Tickets und X2 100 zu. Von 400 lokalen Tickets hat X1 drei Viertel und erhält damit 150 globale Tickets; X2 erhält 50. Benutzer Y hat 100 globale Tickets für Y1. Die Gesamtzahl beträgt 300, sodass X1 erwartungsgemäß 50 %, X2 etwa 16,67 % und Y1 etwa 33,33 % der umkämpften CPU erhält.

Die Ticketübertragung leiht die Tickets eines Clients vorübergehend einem Server, der für ihn arbeitet, und gibt sie nach Abschluss der Anfrage zurück. Sie folgt damit der Arbeitsabhängigkeit. Ticketinflation erlaubt kooperierenden Aufträgen, ihre eigenen Ticketzahlen zu erhöhen, um mehr Bedienzeit anzufordern. Das erfordert Vertrauen oder Begrenzungen: Unbeschränkte Inflation erlaubt einem gierigen Auftrag, die Anteile aller anderen zu verwässern.

Die Lotterie benötigt Ticketgesamtzahlen, aber keine Aufzeichnung darüber, wie weit jeder Auftrag bei der Bedienung vorausliegt. Ein neuer Auftrag steuert seine Tickets einfach zum Bestand der ausführbaren Aufträge bei. Die Zuweisung der Tickets bleibt eine Strategieentscheidung; die zufällige Ziehung setzt diese Entscheidung im Erwartungswert durch. Die Tickets eines blockierten Auftrags konkurrieren nicht um eine Zeitscheibe, die er nicht nutzen kann.

Stride-Scheduling wandelt Ticketanteile in eine deterministische Folge um. Jeder ausführbare Auftrag hat eine Schrittweite, berechnet als große Konstante geteilt durch seine Ticketzahl, und einen Pass-Wert, der seinen gewichteten Fortschritt erfasst. Wähle den niedrigsten Pass-Wert, führe den Auftrag eine gleich lange Zeitscheibe aus und addiere dann seine Schrittweite zu seinem Pass-Wert.

Berechne die Schrittweiten

A hat 50 Tickets, B 25 und C 100. Bei der Konstanten 1.000 sind ihre Schrittweiten 20, 40 und 10. Mehr Tickets ergeben eine kleinere Schrittweite. Der Pass-Wert eines bevorzugten Auftrags steigt langsam, sodass er häufiger das Minimum wird.

Beginne alle Pass-Werte bei null und löse Gleichstände alphabetisch auf. Behalte im Tupel die feste Reihenfolge A, B, C bei:

Nur der Pass-Wert des ausgewählten Auftrags ändert sich. In sieben Zeitscheiben erhält A zwei Einsätze, B einen und C vier: genau das Verhältnis 50:25:100. Beim gemeinsamen Pass-Wert 40 hat jeder den gleichen gewichteten Bedienfortschritt erreicht. Zwischen solchen Gleichständen müssen die Anteile in kurzen Zeitfenstern nicht exakt sein.

Trenne reale Bedienung und virtuellen Fortschritt

Der Pass-Wert ist ein Ordnungswert, keine verstrichene Zeit und keine Ticketzahl. Die große Schrittweite von B lässt ihn warten, während A und C beim Pass-Wert aufholen. Über diesen sich wiederholenden Zyklus erhält B dennoch seinen vorgesehenen Anteil von einem Siebtel. Würde die Ticketzahl zum Pass-Wert addiert, würde das den Entwurf umkehren: Der Auftrag mit den meisten Tickets würde den größten Sprung machen und seltener ausgewählt.

Die Konstante steuert die Skala der Schrittweiten, nicht die beabsichtigten Ticketverhältnisse. Implementierungen mit ganzen Zahlen benötigen genügend Genauigkeit, um diese Verhältnisse nicht durch Rundung zu verzerren. Vergleiche und Aktualisierungen müssen dieselbe Skala verwenden.

Ordne einen neuen Auftrag sinnvoll ein

Angenommen, bestehende Aufträge haben Pass-Werte um 4.000. Ein neuer Auftrag, der bei null startet, würde beim Aufholen wiederholt gewinnen, selbst wenn er wenige Tickets hätte. Initialisiere seinen Pass-Wert in Bezug auf den aktuellen Systemfortschritt, etwa mit dem aktuellen Minimum, damit er keine Bedienzeit für die Zeit vor seiner Ankunft ansammelt.

Die virtuelle Laufzeit von Linux nutzt die verwandte Idee, tatsächliche CPU-Bedienzeit als gewichteten Fortschritt anzurechnen. In beiden Entwürfen lässt ein höherer Anspruch diesen Fortschritt langsamer wachsen, sodass die Aufgabe bei späterer Bedienung konkurrenzfähig bleibt.

Die fairen Linux-Scheduler erfassen gewichtete CPU-Bedienzeit. Der Completely Fair Scheduler (CFS), 2007 in Linux 2.6.23 eingeführt, wählte die ausführbare Aufgabe mit der kleinsten virtuellen Laufzeit. Linux begann 2023 in Version 6.6, diese Auswahlregel durch EEVDF zu ersetzen.

Teile Bedienzeit nach Gewicht auf

Ein Nice-Wert reicht von −20, am stärksten bevorzugt, bis +19, am wenigsten bevorzugt. Nice 0 hat das Gewicht 1024. Jede Stufe zu einem größeren Nice-Wert verringert das Gewicht um etwa den Faktor 1,25. Beispielgewichte sind 3121 bei Nice −5, 820 bei Nice 1, 335 bei Nice 5, 110 bei Nice 10 und 15 bei Nice 19.

Nice 0 gegenüber Nice 1 ergibt $\frac{1024}{1024+820}\approx \mathrm{0,555}$, also etwa 55,5 % gegenüber 44,5 %. Die Anteile hängen ungefähr von der Differenz der Nice-Werte ab: $3121\mathrm{/}1024$ und $335\mathrm{/}110$ betragen beide etwa 3,05. Nice +19 erhält in diesem einfachen Modell mit zwei Aufgaben bei Konkurrenz mit Nice 0 immer noch etwa 1,4 %.

Der klassische CFS teilt eine angestrebte Schedulinglatenz nach Gewicht auf:

Für die Gewichte 1024, 1024 und 335 beträgt die Summe 2383. Ein angestrebter Zeitraum von 48 ms ergibt für jede stärker gewichtete Aufgabe etwa 20,63 ms und für die schwächer gewichtete 6,75 ms. Das sind beispielhafte Parameter, keine allgemeingültigen Kernelstandardwerte. Bei vier gleich gewichteten Aufgaben ergeben 48 ms jeweils 12 ms. Bei zehn lägen jeweils 4,8 ms unter einer beispielhaften Mindestgranularität von 6 ms, sodass der Zeitraum wachsen muss.

Rechne virtuellen Fortschritt an

CFS erhöht die virtuelle Laufzeit einer laufenden Aufgabe um:

Eine Aufgabe mit Gewicht 1024 erhält eine virtuelle Millisekunde pro realer Millisekunde. Eine Aufgabe mit Gewicht 335 erhält etwa 3,06. Die schnellere Anrechnung bei schwächer gewichteten Aufgaben lässt diese früher warten, während stärker gewichtete Aufgaben mehr reale Bedienzeit erhalten.

Der klassische CFS ordnet eingereihte ausführbare Aufgaben in einem Rot-Schwarz-Baum nach virtueller Laufzeit. Einfügen und Entfernen benötigen logarithmische Zeit; ein zwischengespeicherter Zeiger auf den Knoten ganz links ermöglicht es, das Minimum in konstanter Zeit zu finden. Blockierte Aufgaben verlassen diesen Baum ausführbarer Aufgaben. Die Einordnung beim Aufwachen verhindert, dass früheres Schlafen zu einem unbegrenzten Anspruch auf Bedienzeit zum Aufholen wird.

Wähle mit EEVDF unter zugelassenen Aufgaben

Earliest Eligible Virtual Deadline First behält Gewichte und die Erfassung virtueller Bedienzeit bei. Eine Aufgabe hat einen positiven Lag, wenn ihr Bedienzeit zusteht, und einen negativen Lag, wenn sie mehr als ihren Anspruch erhalten hat. Aufgaben mit nicht negativem Lag sind zugelassen. EEVDF wählt die zugelassene Aufgabe mit der frühesten virtuellen Frist.

Die Frist kombiniert den virtuellen Beginn einer Anforderung mit ihrer angeforderten, in virtuelle Zeit umgerechneten Bedienlänge. Sie ist ein Wert zur Reihenfolge der Bedienung, kein zugesagter Abschlusszeitpunkt auf der Uhr. Eine kürzer angeforderte Zeitscheibe kann einer zugelassenen Aufgabe eine frühere Frist geben und die Latenz verbessern, ohne ihren langfristigen Gewichtsanteil zu erhöhen. Aktuelles Linux unterstützt Zeitscheibenanforderungen über sched_setattr().

Mehrere CPUs helfen nur, wenn parallele Arbeit vorhanden ist. Ein einzelner Thread läuft jeweils auf einer logischen CPU; mehrere Threads oder unabhängige Programme können mehrere CPUs gemeinsam nutzen. Ein Scheduler muss sowohl wählen, welcher Auftrag läuft, als auch wo er läuft.

Teile die Verantwortung für das Scheduling auf

Beim symmetrischen Mehrprozessorbetrieb (SMP) führen CPUs Kernelcode aus und treffen Schedulingentscheidungen für sich selbst. Beim asymmetrischen Mehrprozessorbetrieb koordiniert ein Hauptprozessor das Scheduling, während andere zugewiesene Arbeit ausführen. Zentrale Steuerung ist einfacher, aber der Hauptprozessor kann zum Engpass werden. Allzwecksysteme nutzen SMP.

Gleichzeitige Entscheidungen erfordern Koordination. Wenn zwei CPUs Aufgaben aus einer gemeinsamen Bereitwarteschlange entfernen, müssen deren Aktualisierungen synchronisiert werden, damit weder ein Eintrag verloren geht noch dieselbe eingereihte Aufgabe zweimal ausgewählt wird. Mehr CPUs können die Konkurrenz um diese gemeinsame Struktur erhöhen.

Erhalte nützliche Cache-Inhalte

Kerne haben kleine schnelle Caches, typischerweise private L1- und L2-Caches und einen größeren L3-Cache, den mehrere Kerne teilen. Zeitliche Lokalität bedeutet, kürzlich abgerufene Daten erneut zu verwenden. Räumliche Lokalität bedeutet, auf benachbarte Daten zuzugreifen, etwa auf aufeinanderfolgende Array-Elemente.

Ein sortierender Thread auf Kern 0 füllt dessen Caches und TLB. Läuft er nach einer kurzen Verdrängung dort weiter, können viele benötigte Einträge noch vorhanden sein. Auf Kern 3 muss er möglicherweise dieselben Daten erneut aus einem gemeinsamen Cache oder dem Speicher holen. Cache-Affinität ist die Tendenz des Schedulers, einen Thread in der Nähe der CPU zu halten, die er kürzlich genutzt hat. Der genaue Nutzen hängt davon ab, was im Cache verbleibt und wie die Caches gemeinsam genutzt werden.

Unterscheide Kohärenz und Synchronisierung

Cache-Kohärenz verhindert, dass Kerne dauerhaft widersprüchliche zwischengespeicherte Kopien einer einzelnen Speicherstelle verwenden. Busüberwachung ist eine Umsetzungsidee: Caches beobachten den Datenverkehr und invalidieren oder aktualisieren Kopien, wenn ein anderer Kern schreibt. Größere Systeme können andere Kohärenzmechanismen nutzen.

Kohärenz macht aus mehreren Befehlen keine atomare Operation. Wenn zwei CPUs beide eine Warteschlangenlänge lesen, Einträge ändern und die Länge zurückschreiben, erlauben kohärente einzelne Lese- und Schreibvorgänge dennoch schädliche Verzahnungen. Der Scheduler benötigt für die gesamte Aktualisierung Sperren oder eine andere Synchronisierungsmethode. Die gemeinsam genutzte Cache-Zeile einer Sperre kann selbst zwischen Kernen wandern, während diese um sie konkurrieren.

Lies den Hardwareaufbau

Intel nennt seine SMT-Implementierung Hyper-Threading. Zwei ausgelastete Threads auf logischen CPUs desselben Kerns konkurrieren um dessen Ressourcen; zwei logische CPUs entsprechen nicht zwei unabhängigen physischen Kernen. Eine NUMA-Migration kann außerdem Berechnungen vom verwendeten Speicher entfernen, selbst wenn das erneute Füllen des Caches kurz dauert.

Das Verschieben eines Threads auf eine untätige CPU kann eine lange Wartezeit in der Warteschlange beseitigen. Ihn an Ort und Stelle zu halten, kann die Lokalität erhalten. Vergleiche diese Kosten anhand der tatsächlichen Arbeitslast: Affinität ist eine Leistungspräferenz, während eine explizite Affinitätsmaske einschränkt, welche CPUs überhaupt erlaubt sind.

Ein Mehrprozessorscheduler benötigt einen Ort für bereite Arbeit. Eine gemeinsame Warteschlange macht Arbeit leicht auffindbar. Getrennte Warteschlangen pro CPU verringern die gemeinsame Konkurrenz und erhalten die Platzierung, können aber dazu führen, dass eine CPU überlastet ist, während eine andere untätig bleibt.

Vergleiche Warteschlangenentwürfe

Beim Mehrprozessorscheduling mit einer Warteschlange entnehmen alle CPUs Arbeit aus einer gemeinsamen Warteschlange. Wenn Aufträge auf jeder CPU laufen können, beschäftigt wartende Arbeit eine untätige CPU von selbst. Eine gemeinsame Sperre schützt die Warteschlange, sodass eine steigende CPU-Anzahl diese Sperre zum Engpass machen kann.

Bei fünf Round-Robin-Aufträgen A–E auf vier CPUs weist eine mögliche Folge in der ersten Runde A, B, C, D zu; in der zweiten E, A, B, C und in der dritten D, E, A, B. A läuft auf CPU 0, dann 1 und dann 2. Der Rechner bleibt beschäftigt, aber A wechselt wiederholt die privaten Caches. Affinitätsregeln können die meisten Platzierungen beibehalten und ausgewählte Aufträge zum Lastausgleich verschieben.

Erkenne ungleiche Anteile

Beim Mehrprozessorscheduling mit mehreren Warteschlangen plant jede CPU ihre eigene Warteschlange. Angenommen, CPU 0 hat A und C und CPU 1 hat B und D; alle sind CPU-gebunden und teilen sich ihre CPU lokal im Round-Robin-Verfahren. Anfangs erhält jeder Auftrag eine halbe CPU. Wenn C endet, erhält A die gesamte CPU 0, während B und D weiterhin jeweils die Hälfte von CPU 1 erhalten.

Der Rechner bleibt voll ausgelastet, aber die Aufträge erhalten keine gleichen Anteile mehr. Endet auch A, wird CPU 0 untätig, obwohl B und D bereit sind. Wird einer von ihnen auf CPU 0 verschoben, erhalten beide eine ganze CPU und zuvor ungenutzte Kapazität wird verwendet.

Bei drei gleichen CPU-gebundenen Aufträgen und zwei CPUs beträgt die gleiche langfristige Bedienung zwei Drittel einer CPU pro Auftrag. Bei fester Platzierung läuft ein Auftrag allein und zwei teilen sich eine CPU. Wenn regelmäßig gewechselt wird, welcher Auftrag allein läuft, kann sich die Aufteilung der Gleichheit annähern. Kein einzelner Thread läuft auf beiden CPUs gleichzeitig.

Entscheide, wann migriert wird

Migration verschiebt eine Aufgabe in die Warteschlange einer anderen CPU. Work Stealing ist eine Strategie, bei der Arbeit geholt wird: Eine CPU mit wenig Arbeit prüft die Warteschlange einer stärker beschäftigten CPU und übernimmt Arbeit. Häufige Prüfungen erzeugen Synchronisierungsverkehr; seltene Prüfungen lassen Ungleichgewichte bestehen. Beim Stehlen müssen auch die zulässigen CPUs und die Speicherlokalität berücksichtigt werden.

Vergleiche die erwartete eingesparte Wartezeit mit dem Migrationsaufwand. Eine lange Warteschlange auf einer CPU und eine untätige geeignete CPU sind ein starker Grund für eine Verschiebung. Ein kleiner vorübergehender Unterschied zwischen Warteschlangen kann verschwinden, bevor sich der Aufwand für das erneute Füllen des Caches ausgleicht.

Die O(1)- und CFS-Entwürfe von Linux verwendeten Ausführungswarteschlangen pro CPU; Linux gleicht die Last über Hardware-Schedulingdomänen hinweg aus und berücksichtigt dabei gemeinsam genutzte Kerne und Prozessorsockel. Der alternative BF Scheduler verwendete eine gemeinsame Warteschlange. Benutzer können die Platzierung unter Linux mit taskset oder sched_setaffinity() und unter Windows mit SetThreadAffinityMask() einschränken. Eine eingeschränkte Affinitätsmaske kann erklären, warum eine bereite Aufgabe eine scheinbar untätige CPU nicht nutzt.

Linux plant Threads ein, die im Kernel Tasks heißen. Schedulingstrategie, Nice-Wert, Gruppensteuerung und CPU-Affinität eines Tasks beantworten unterschiedliche Fragen dazu, wann und wo er läuft.

Lies zuerst die Strategie

Die normalen Strategien haben die statische Priorität 0. Echtzeit-FIFO und -RR nutzen 1–99, wobei 99 die höchste ist. Ein FIFO-Task läuft weiter, bis er blockiert, die CPU freiwillig abgibt oder von Arbeit mit höherer Priorität verdrängt wird. RR ergänzt Einsätze für Tasks gleicher Priorität; sched_rr_get_interval() meldet sein Zeitquantum. Diese Namen bezeichnen Linux-Strategien: Normales faires Scheduling ist nicht der RR-Lehrbuchalgorithmus mit gleichen Zeitscheiben.

Ändere Anteile und Platzierung

Nice reicht von −20 bis +19, mit dem Standardwert 0. Größere Werte verringern das Gewicht in der fairen Klasse um ungefähr den Faktor 1,25 pro Stufe. Bei einem typischen Start mit Nice 0 startet nice -n 10 make einen Build mit Nice 10; -n ist eine Anpassung des geerbten Nice-Werts. renice -n 5 -p 4321 setzt den Zielprozess auf Nice 5. Ein Benutzer kann seine eigene Arbeit weniger stark bevorzugen lassen; eine Erhöhung der Priorität erfordert passende Rechte oder ein erlaubtes Ressourcenlimit.

taskset -c 0,1 ./app erlaubt einem Programm, auf den CPUs 0 und 1 zu laufen. Es erzeugt keinen zweiten Thread und sichert keine der CPUs exklusiv zu. ps -o pid,cls,ni,rtprio,comm zeigt strategierelevante Felder, während top hilft, Priorität, Nice-Wert und CPU-Verbrauch zu beobachten.

chrt -f 50 ./app wählt die FIFO-Echtzeitpriorität 50. Nutze Echtzeiteinstellungen nur in einer kontrollierten Umgebung: Ein ausgelasteter Thread mit hoher Priorität kann die Shell und wichtige Systemarbeit verzögern. Standardmäßige Echtzeit-Bandbreitengrenzen reservieren etwas Zeit für normale Arbeit, sorgen aber nicht dafür, dass jede solche Arbeitslast reaktionsfähig bleibt. Vorrang ändert den Zugang zur CPU-Bedienzeit, nicht die Geschwindigkeit eines Befehls.

Unterscheide Gruppengewicht und Quote

In cgroup v2 reicht cpu.weight von 1 bis 10000, mit Standardwert 100, und teilt umkämpfte CPU-Kapazität der fairen Klasse unter aktiven Gruppen derselben Ebene auf. Die Gewichte 200 und 100 ergeben etwa zwei Drittel und ein Drittel einer CPU, wenn beide Gruppen beschäftigt sind. Wird die zweite untätig, kann die erste die gesamte verfügbare Kapazität nutzen.

cpu.max setzt eine Bandbreitenobergrenze. Der Wert „50000 100000“ erlaubt insgesamt 50 ms CPU-Zeit pro Zeitraum von 100 ms, was im Mittel einer halben CPU entspricht. Mehrere Threads können dieses Budget parallel verbrauchen und es bezogen auf die verstrichene Zeit früher erschöpfen. Eine begrenzte Gruppe kann selbst dann gedrosselt werden, wenn freie CPU-Kapazität vorhanden ist.

Ordne die Namen zeitlich ein

Der O(1)-Scheduler von Linux 2.6.0 verwendete Prioritätsfelder und Interaktivitätsrückkopplung. CFS kam 2007 in 2.6.23 hinzu. Linux 6.6 begann 2023 den Übergang zur EEVDF-Auswahl in der fairen Klasse. Seit Linux 6.12 im Jahr 2024 unterstützt sched_ext auf entsprechend konfigurierten Kerneln dynamisch geladene BPF-Schedulingstrategien. Schlägt ein solcher Scheduler fehl oder hält er ausführbare Arbeit auf, stellt der Kernel das eingebaute Scheduling wieder her.

Windows plant bereite Threads nach Priorität von 0 bis 31 ein, wobei größere Zahlen höher sind. Bereite Threads gleicher Priorität wechseln sich im Round-Robin-Verfahren ab. Ein neu bereiter Thread mit höherer Priorität verdrängt einen mit niedrigerer, ohne auf das Ende seines Zeitquantums zu warten. Priorität 0 gehört dem Thread zum Nullsetzen von Seiten, der freie Seiten löscht.

Bestimme die Basispriorität aus zwei Einstellungen

Die Basispriorität eines Threads hängt von der Prioritätsklasse seines Prozesses und seiner eigenen relativen Threadstufe ab. Prozessklassen sind Idle, Below normal, Normal, Above normal, High und Realtime. Zu den Threadstufen gehören Idle, Lowest, Below normal, Normal, Above normal, Highest und Time critical.

Time critical ergibt außerhalb der Klasse Realtime 15 und innerhalb davon 31. Die Threadstufe Idle ergibt außerhalb von Realtime 1 und innerhalb davon 16. Diese Randstufen sind besondere Tabelleneinträge, sodass das Addieren eines festen Versatzes zu jeder Klasse falsche Ergebnisse liefern würde.

Verfolge eine vorübergehende Anhebung

Die Prioritäten 1–15 bilden den variablen Bereich; 16–31 bilden den Echtzeitbereich. Ein Thread beginnt mit einer dynamischen Priorität, die seiner Basispriorität entspricht. Bei Threads im variablen Bereich können Ereignisse wie eine Eingabe oder das Ende eines Wartens die dynamische Priorität vorübergehend erhöhen. Threads mit Echtzeit-Basisprioritäten erhalten keine solchen Anhebungen.

Angenommen, ein Thread mit Basispriorität 8 wird auf 14 angehoben. Rechnet er weiter, sinkt seine dynamische Priorität nach jedem vollständigen Zeitquantum um eine Stufe: auf 13 nach dem ersten, 12 nach dem zweiten und 8 nach dem sechsten. Die Anhebung ändert die Basispriorität nicht dauerhaft und fällt nicht unter diese Basis.

Das ist Rückkopplung: Gerade freigegebene Arbeit wird schnell bedient, während anhaltende CPU-Nutzung den vorübergehenden Vorteil verliert. Windows verwendet auch vorübergehende Anhebungen für lange wartende bereite Threads, um Verhungern entgegenzuwirken. Eine solche Anhebung kann einem Sperrinhaber mit niedrigem Rang helfen, Fortschritt zu machen, ist aber ein anderer Mechanismus als die sperrenspezifische Prioritätsvererbung.

Erkenne verwandte Entwürfe

Die Zeitteilklasse von Solaris ist ein tabellengesteuerter MLFQ-Entwurf. ULE von FreeBSD verwendet Ausführungswarteschlangen pro CPU und vergleicht das Schlaf- mit dem Laufverhalten, um interaktive Threads zu erkennen. Diese Systeme teilen die Idee, die Bedienung an beobachtetes Verhalten anzupassen, ohne identische Warteschlangenregeln zu verwenden.

macOS bietet Dienstgüteklassen (QoS), darunter benutzerinteraktiv, benutzerinitiiert, Standard, Hilfsprogramm und Hintergrund. Sie beschreiben die Dringlichkeit der Arbeit. Auf Apple Silicon hilft QoS dem System, Arbeit auf Leistungs- und Effizienzkerne zu verteilen. Programme teilen die Wichtigkeit der Arbeit mit; das Betriebssystem wählt die Platzierung gemäß Strategie und verfügbarer Hardware.

Reale Scheduler kombinieren Rückkopplung, Prioritäten, Fairness und Affinität. Eine Windows-Klasse Realtime bietet stärkeren Vorrang, aber weder eine garantiert schnellere Berechnung noch eine vollständige Garantie für Echtzeitkorrektheit.

Bestimme das Ziel der Arbeitslast, bevor du einen Scheduler auswählst. Bei einer Warteschlange für Stapelaufträge kann der schnelle Abschluss vieler kleiner Aufträge wichtig sein. Ein Editor benötigt nach Eingaben eine schnelle Bedienung. Ein gemeinsam genutzter Server braucht eine vertretbare Zuteilung unter Benutzern oder Gruppen.

Wähle den Mechanismus passend zum Ziel

Vergleiche Strategien bei gleichen Eingaben

A kommt bei 0 ms an und benötigt 8 ms, B bei 1 ms und benötigt 4 ms, C bei 2 ms und benötigt 2 ms. Der Wechselaufwand bleibt unberücksichtigt. FIFO führt A, B, C aus. SJF startet ebenfalls A, führt danach aber C vor B aus. STCF führt A 0–1, B 1–2, C 2–4, B 4–7, A 7–14 aus. RR nutzt ein Zeitquantum von 2 ms; Aufträge, die am Ende einer Zeitscheibe ankommen, werden vor der verdrängten Aufgabe eingereiht.

STCF gewinnt bei dieser Arbeitslast in beiden Kennzahlen, weil jeder neu ankommende kürzere Auftrag sofort läuft. RR ermöglicht einen schnellen Start, ohne die CPU-Burst-Längen zu kennen. Bei gleichzeitig ankommenden gleich langen Aufträgen kann FIFO eine niedrigere mittlere Durchlaufzeit als RR haben. Eine Rangfolge für eine Arbeitslast ist ein Beleg für diese Arbeitslast.

Wähle eine Bewertungsmethode

Deterministische Modellierung berechnet einen festen Ablauf von Hand. Sie liefert exakte Ergebnisse für ihre Eingaben und macht Entscheidungen leicht nachvollziehbar, lässt aber oft Dispatch- und Cache-Aufwand aus. Warteschlangenmodelle beschreiben Ankunfts- und Bedienmuster mithilfe von Verteilungen und sagen das mittlere Verhalten voraus.

Für ein stabiles System im stationären Zustand verknüpft das Gesetz von Little die mittlere Anzahl $n$, die Ankunftsrate $\lambda$ und die mittlere Verweildauer $W$:

Bei 14 Aufträgen/s und einer mittleren Zeit im System von 0,5 s beträgt die mittlere Anzahl 7 Aufträge. Wähle die Abgrenzung einheitlich: Zur Anzahl in der Bereitwarteschlange gehört die Wartezeit in dieser Warteschlange, zur Anzahl im ganzen System die Zeit im ganzen System. Rechne vor der Multiplikation die Einheiten um.

Eine Simulation führt ein Modell des Schedulers aus, oft mit einer aufgezeichneten Arbeitslast. Sie kann komplizierte Ankunfts- und Blockierungsmuster prüfen, aber ihre Schlussfolgerungen hängen vom Modell und den gewählten Aufzeichnungen ab. Eine Implementierung misst den Scheduler in einem realen Betriebssystem und umfasst den tatsächlichen Verwaltungsaufwand; sie erfordert mehr Arbeit und benötigt weiterhin repräsentative Arbeitslasten und wiederholbare Messungen.

Untersuche neben Mittelwerten auch Durchsatz, Auslastung, einzelne Verzögerungen und Verzögerungen im oberen Randbereich, Fairness und Energieverbrauch. In einem Mehrprozessorsystem kann ein ausgelasteter Rechner die Bedienzeit trotzdem ungleich aufteilen oder Zeit für das erneute Füllen von Caches aufwenden. Vergleiche Strategien bei gleichem Beobachtungsfenster und gleicher Arbeitslast und verändere dann die Merkmale der Arbeitslast, die für die vorgesehenen Benutzer wichtig sind.