Terminplanung (Informatik)

In der Informatik bezeichnet Scheduling die Zuweisung von Ressourcen zur Ausführung von Aufgaben . Bei den Ressourcen kann es sich um Prozessoren , Netzwerkverbindungen oder Erweiterungskarten handeln . Die Aufgaben können Threads , Prozesse oder Datenflüsse sein .

Die Planungsaktivität wird von einem Mechanismus namens Scheduler durchgeführt . Scheduler sind häufig so konzipiert, dass sie alle Computerressourcen auslasten (wie beim Lastausgleich ), es mehreren Benutzern ermöglichen, Systemressourcen effektiv zu teilen oder eine angestrebte Dienstgüte zu erreichen .

Die Ablaufplanung ist grundlegend für die Datenverarbeitung selbst und ein integraler Bestandteil des Ausführungsmodells eines Computersystems; das Konzept der Ablaufplanung ermöglicht Multitasking mit einer einzigen zentralen Verarbeitungseinheit (CPU).

Ein Scheduler kann ein oder mehrere Ziele verfolgen, zum Beispiel:

• Maximierung des Durchsatzes (die Gesamtmenge der pro Zeiteinheit erledigten Arbeit);
• Minimierung der Wartezeit (Zeitraum von der Fertigstellung des Auftrags bis zum Beginn seiner Ausführung);
• Minimierung der Latenz oder Reaktionszeit (Zeit von der Bereitstellung der Arbeit bis zu deren Abschluss bei Stapelverarbeitung ^{[ 1 ] [ 2 ] [ 3 ]} oder bis das System antwortet und dem Benutzer die erste Ausgabe liefert bei interaktiver Verarbeitung ^{[ 4 ]}
• Maximierung der Fairness (gleiche CPU-Zeit für jeden Prozess oder allgemeiner angemessene Zeiten entsprechend der Priorität und Arbeitslast jedes Prozesses).

In der Praxis stehen diese Ziele oft im Konflikt (z. B. Durchsatz versus Latenz), daher implementiert ein Scheduler einen geeigneten Kompromiss. Die Präferenz wird anhand eines der oben genannten Kriterien gemessen, abhängig von den Bedürfnissen und Zielen des Nutzers.

In Echtzeitumgebungen , wie beispielsweise eingebetteten Systemen zur automatischen Steuerung in der Industrie (z. B. in der Robotik ), muss der Scheduler zudem sicherstellen, dass Prozesse ihre Fristen einhalten ; dies ist entscheidend für die Systemstabilität. Geplante Aufgaben können auch auf entfernte Geräte in einem Netzwerk verteilt und über ein administratives Backend verwaltet werden .

Der Scheduler ist ein Betriebssystemmodul, das die nächsten auszuführenden Jobs und Prozesse auswählt. Betriebssysteme können bis zu drei verschiedene Scheduler-Typen aufweisen: einen Langzeit-Scheduler (auch Zulassungs-Scheduler oder High-Level-Scheduler genannt), einen Mittelzeit-Scheduler und einen Kurzzeit-Scheduler . Die Bezeichnungen geben die relative Häufigkeit ihrer Ausführung wieder.

Der Prozess-Scheduler ist ein Teil des Betriebssystems, der entscheidet, welcher Prozess zu einem bestimmten Zeitpunkt ausgeführt wird. Er kann üblicherweise einen laufenden Prozess anhalten, ihn ans Ende der Warteschlange verschieben und einen neuen Prozess starten; ein solcher Scheduler wird als präemptiver Scheduler bezeichnet . Kann der Scheduler einen laufenden Prozess nicht anhalten und einen neuen Prozess starten, handelt es sich um einen kooperativen Scheduler . ^{[ 5 ]}

Wir unterscheiden zwischen langfristiger , mittelfristiger und kurzfristiger Planung je nachdem, wie häufig Entscheidungen getroffen werden müssen. ^{[ 6 ]}

Der Langzeit-Scheduler , auch Zulassungs-Scheduler genannt , entscheidet, welche Jobs oder Prozesse in die Warteschlange (im Hauptspeicher) aufgenommen werden. Das heißt, wenn versucht wird, ein Programm auszuführen, wird dessen Aufnahme in die Menge der aktuell laufenden Prozesse vom Langzeit-Scheduler entweder genehmigt oder verzögert. Somit legt dieser Scheduler fest, welche Prozesse auf einem System ausgeführt werden, welcher Grad an Parallelität zu jedem Zeitpunkt unterstützt werden soll – ob viele oder wenige Prozesse gleichzeitig ausgeführt werden – und wie die Aufteilung zwischen E/A-intensiven und CPU-intensiven Prozessen erfolgt. Der Langzeit-Scheduler ist für die Steuerung des Multiprogramming-Grades verantwortlich.

Im Allgemeinen lassen sich die meisten Prozesse entweder als E/A-gebunden oder als CPU-gebunden beschreiben . Ein E/A-gebundener Prozess verbringt mehr Zeit mit E/A-Operationen als mit Berechnungen. Ein CPU-gebundener Prozess hingegen generiert E/A-Anforderungen nur selten und nutzt den Großteil seiner Zeit für Berechnungen. Es ist wichtig, dass ein langfristiger Scheduler eine optimale Mischung aus E/A-gebundenen und CPU-gebundenen Prozessen auswählt. Sind alle Prozesse E/A-gebunden, ist die Warteschlange für bereite Prozesse fast immer leer, und der kurzfristige Scheduler hat wenig zu tun. Sind hingegen alle Prozesse CPU-gebunden, ist die E/A-Warteschlange fast immer leer, Geräte bleiben ungenutzt, und das System gerät erneut aus dem Gleichgewicht. Das leistungsstärkste System zeichnet sich daher durch eine Kombination aus CPU-gebundenen und E/A-gebundenen Prozessen aus. In modernen Betriebssystemen wird dies genutzt, um sicherzustellen, dass Echtzeitprozesse genügend CPU-Zeit erhalten, um ihre Aufgaben abzuschließen. ^{[ 7 ]}

Die langfristige Ablaufplanung ist auch in großen Systemen wie Stapelverarbeitungssystemen , Computerclustern , Supercomputern und Renderfarmen wichtig . Beispielsweise ist in parallelen Systemen die gemeinsame Ablaufplanung interagierender Prozesse oft erforderlich, um Blockierungen durch gegenseitiges Warten zu verhindern. In diesen Fällen wird typischerweise spezielle Job-Scheduler -Software eingesetzt, um diese Funktionen zusätzlich zur im Betriebssystem vorhandenen Zugriffsplanung zu unterstützen.

Manche Betriebssysteme erlauben das Hinzufügen neuer Aufgaben nur dann, wenn sichergestellt ist, dass alle Echtzeitfristen eingehalten werden können. Der spezifische heuristische Algorithmus, den ein Betriebssystem zur Annahme oder Ablehnung neuer Aufgaben verwendet, ist der Zulassungskontrollmechanismus . ^{[ 8 ]}

Der mittelfristige Scheduler entfernt Prozesse vorübergehend aus dem Hauptspeicher und lagert sie in den Sekundärspeicher (z. B. auf eine Festplatte ) aus oder umgekehrt. Dieser Vorgang wird üblicherweise als Auslagern oder Einlagern bezeichnet (fälschlicherweise auch als Paging ). Der mittelfristige Scheduler kann entscheiden, einen Prozess auszulagern, der längere Zeit inaktiv war, eine niedrige Priorität hat, häufig Seitenfehler verursacht oder viel Speicher belegt, um Hauptspeicher für andere Prozesse freizugeben. Der Prozess wird später wieder in den Hauptspeicher eingelagert, sobald mehr Speicher verfügbar ist oder der Prozess nicht mehr blockiert ist und nicht mehr auf eine Ressource wartet.

In vielen Systemen (solchen, die die Zuordnung von virtuellem Adressraum zu sekundärem Speicher außer der Auslagerungsdatei unterstützen) kann der mittelfristige Scheduler die Rolle des langfristigen Schedulers übernehmen, indem er Binärdateien bei ihrer Ausführung als ausgelagerte Prozesse behandelt . Dadurch kann ein Segment der Binärdatei bei Bedarf nachgeladen werden ( Lazy Loading , auch Demand Paging genannt ).

Der Kurzzeit-Scheduler (auch CPU-Scheduler genannt ) entscheidet nach einem Takt- Interrupt , einem E/A-Interrupt, einem Betriebssystemaufruf oder einem anderen Signal, welcher der bereiten, im Speicher befindlichen Prozesse ausgeführt (und ihm eine CPU zugewiesen) wird. Daher trifft der Kurzzeit-Scheduler Scheduling-Entscheidungen deutlich häufiger als der Langzeit- oder Mittelzeit-Scheduler – mindestens nach jedem sehr kurzen Zeitschlitz muss eine Entscheidung getroffen werden. Dieser Scheduler kann präemptiv sein, d. h. er kann Prozesse von einer CPU entfernen, wenn er diese einem anderen Prozess zuweisen möchte, oder nicht-präemptiv (auch freiwillig oder kooperativ genannt ), im letzteren Fall kann er Prozesse nicht von der CPU entfernen .

Eine weitere Komponente der CPU-Planungsfunktion ist der Dispatcher. Dieses Modul weist dem vom Kurzzeit-Scheduler ausgewählten Prozess die CPU-Kontrolle zu. Er erhält die Kontrolle im Kernel-Modus durch eine Interrupt- oder Systemaufruf-Anforderung. Zu den Funktionen eines Dispatchers gehören:

• Kontextwechsel , bei denen der Dispatcher den Zustand (auch Kontext genannt ) des zuvor laufenden Prozesses oder Threads speichert; anschließend lädt der Dispatcher den anfänglichen oder zuvor gespeicherten Zustand des neuen Prozesses.
• Wechsel in den Benutzermodus.
• Springen zur entsprechenden Stelle im Benutzerprogramm, um dieses Programm anhand seines neuen Zustands neu zu starten.

Der Dispatcher sollte so schnell wie möglich sein, da er bei jedem Prozesswechsel aufgerufen wird. Während der Kontextwechsel ist der Prozessor für einen Bruchteil der Zeit praktisch im Leerlauf; unnötige Kontextwechsel sollten daher vermieden werden. Die Zeit, die der Dispatcher benötigt, um einen Prozess zu beenden und einen anderen zu starten, wird als Dispatch-Latenz bezeichnet . ^{[ 7 ] : 155}

Eine Scheduling-Disziplin (auch Scheduling-Richtlinie oder Scheduling-Algorithmus genannt ) ist ein Algorithmus zur Verteilung von Ressourcen an Parteien, die diese gleichzeitig und asynchron anfordern. Scheduling-Disziplinen werden in Routern (zur Verarbeitung des Paketverkehrs) sowie in Betriebssystemen (zur Aufteilung der CPU-Zeit zwischen Threads und Prozessen ), Festplatten ( E/A-Scheduling ), Druckern ( Druckspooler ), den meisten eingebetteten Systemen usw. eingesetzt .

Die Hauptziele von Scheduling-Algorithmen sind die Minimierung von Ressourcenengpässen und die Gewährleistung einer fairen Ressourcenverteilung zwischen den Nutzern. Das Scheduling befasst sich mit der Frage, welchen der ausstehenden Anfragen Ressourcen zugeteilt werden sollen. Es gibt viele verschiedene Scheduling-Algorithmen. In diesem Abschnitt stellen wir einige davon vor.

In paketvermittelten Computernetzwerken und anderen statistischen Multiplexverfahren wird der Begriff eines Scheduling-Algorithmus als Alternative zur Warteschlangenverwaltung nach dem Prinzip „ Wer zuerst kommt, mahlt zuerst“ verwendet.

Die einfachsten Best-Effort-Scheduling-Algorithmen sind Round-Robin , Fair Queuing (ein Max-Min-Fair -Scheduling-Algorithmus), Proportional-Fair Scheduling und Maximum Throughput . Wird differenzierte oder garantierte Dienstgüte anstelle von Best-Effort-Kommunikation angeboten, kann Weighted Fair Queuing eingesetzt werden.

In modernen paketfunkbasierten Mobilfunknetzen wie HSDPA (High-Speed ​​Downlink Packet Access) 3.5G kann kanalabhängiges Scheduling genutzt werden, um Kanalzustandsinformationen auszunutzen . Bei günstigen Kanalbedingungen lassen sich Durchsatz und spektrale Effizienz des Systems steigern. In noch fortschrittlicheren Systemen wie LTE wird das Scheduling durch kanalabhängige, paketweise dynamische Kanalzuweisung oder durch die Zuweisung von OFDMA -Mehrträgern oder anderen Frequenzbereichsentzerrungskomponenten an die Nutzer kombiniert, die diese am besten nutzen können. ^{[ 9 ]}

First In, First Out ( FIFO ), auch bekannt als First Come, First Served (FCFS), ist der einfachste Scheduling-Algorithmus. FIFO reiht Prozesse einfach in der Reihenfolge ihres Eintreffens in der Warteschlange ein. Dies wird häufig für … verwendet.Aufgabenwarteschlange , wie sie beispielsweise in diesem Abschnitt dargestellt wird.

• Da Kontextwechsel nur bei Beendigung eines Prozesses erfolgen und keine Reorganisation der Prozesswarteschlange erforderlich ist, ist der Planungsaufwand minimal.
• Der Durchsatz kann gering sein, weil lange Prozesse die CPU blockieren und dadurch kurze Prozesse lange warten müssen (bekannt als Konvoi-Effekt).
• Kein Verhungern, da jeder Prozess nach einer bestimmten Zeit die Chance erhält, ausgeführt zu werden.
• Bearbeitungszeit , Wartezeit und Reaktionszeit hängen von der Reihenfolge ihres Eintreffens ab und können aus den oben genannten Gründen hoch sein.
• Es findet keine Priorisierung statt, daher hat dieses System Schwierigkeiten, Prozessfristen einzuhalten.
• Die fehlende Priorisierung bedeutet, dass es zu keinem Ressourcenmangel kommt, solange jeder Prozess letztendlich abgeschlossen wird. In einer Umgebung, in der einige Prozesse möglicherweise nicht abgeschlossen werden, kann es jedoch zu Ressourcenmangel kommen.
• Es basiert auf einem Warteschlangensystem.

Earliest Deadline First (EDF) oder Least Time to Go ist ein dynamischer Scheduling-Algorithmus, der in Echtzeitbetriebssystemen verwendet wird, um Prozesse in eine Prioritätswarteschlange einzureihen. Sobald ein Scheduling-Ereignis eintritt (z. B. Abschluss einer Aufgabe, Freigabe einer neuen Aufgabe), wird in der Warteschlange der Prozess gesucht, dessen Deadline am nächsten liegt. Dieser wird dann als Nächstes zur Ausführung eingeplant.

Ähnlich wie bei der Strategie „Shortest Job First“ (SJF) ordnet der Scheduler bei dieser Strategie die Prozesse mit der geringsten verbleibenden Bearbeitungszeit in der Warteschlange an. Dies erfordert fortgeschrittene Kenntnisse oder Schätzungen über die für die Ausführung eines Prozesses benötigte Zeit.

• Wenn während der Ausführung eines anderen Prozesses ein kürzerer Prozess eintrifft, wird der aktuell laufende Prozess unterbrochen (Präemption) und in zwei separate Rechenblöcke aufgeteilt. Dies führt zu zusätzlichem Aufwand durch weitere Kontextwechsel. Der Scheduler muss zudem jeden eingehenden Prozess an einer bestimmten Stelle in der Warteschlange einordnen, was zusätzlichen Aufwand verursacht.
• Dieser Algorithmus ist auf maximalen Durchsatz in den meisten Szenarien ausgelegt.
• Mit steigendem Rechenaufwand des Prozesses erhöhen sich Warte- und Antwortzeit. Da sich die Durchlaufzeit aus Wartezeit und Bearbeitungszeit zusammensetzt, sind längere Prozesse davon deutlich betroffen. Insgesamt ist die Wartezeit jedoch kürzer als bei FIFO, da kein Prozess auf den Abschluss des längsten Prozesses warten muss.
• Besondere Beachtung finden Fristen; der Programmierer kann lediglich versuchen, Prozesse mit Fristen so kurz wie möglich zu gestalten.
• Ein Verhungern der Prozesse ist möglich, insbesondere in einem stark ausgelasteten System, in dem viele kleine Prozesse gleichzeitig laufen.
• Um diese Richtlinie anwenden zu können, sollten wir mindestens zwei Prozesse mit unterschiedlichen Prioritäten haben.

Das Betriebssystem weist jedem Prozess eine feste Priorität zu, und der Scheduler ordnet die Prozesse in der Warteschlange entsprechend ihrer Priorität an. Prozesse mit niedrigerer Priorität werden durch eingehende Prozesse mit höherer Priorität unterbrochen.

• Die Gemeinkosten sind weder minimal noch signifikant.
• FPPS bietet gegenüber FIFO-Scheduling keinen besonderen Vorteil hinsichtlich des Durchsatzes.
• Bei begrenzter Anzahl an Prioritätsstufen lässt sich das System als Sammlung von FIFO-Warteschlangen darstellen, eine für jede Prioritätsstufe. Prozesse in Warteschlangen mit niedrigerer Priorität werden nur dann ausgewählt, wenn alle Warteschlangen mit höherer Priorität leer sind.
• Wartezeit und Antwortzeit hängen von der Priorität des Prozesses ab. Prozesse mit höherer Priorität weisen kürzere Warte- und Antwortzeiten auf.
• Fristen können eingehalten werden, indem Prozessen mit Fristen eine höhere Priorität eingeräumt wird.
• Bei einer großen Anzahl von Prozessen mit hoher Priorität, die auf CPU-Zeit warten, kann es zu einer Vernachlässigung von Prozessen mit niedrigerer Priorität kommen.

Der Scheduler weist jedem Prozess eine feste Zeiteinheit zu und arbeitet diese zyklisch ab. Wird ein Prozess innerhalb dieser Zeiteinheit abgeschlossen, wird er beendet; andernfalls wird er neu eingeplant, nachdem allen anderen Prozessen die Möglichkeit zur Ausführung gegeben wurde.

• Die Planung von Eisenbahnzügen ist mit einem erheblichen Aufwand verbunden, insbesondere bei kleinen Zeiteinheiten.
• Ausgewogener Durchsatz zwischen FCFS/FIFO und SJF/SRTF, kürzere Aufträge werden schneller abgeschlossen als bei FIFO und längere Prozesse werden schneller abgeschlossen als bei SJF.
• Gute durchschnittliche Antwortzeit, die Wartezeit hängt von der Anzahl der Prozesse ab, nicht von der durchschnittlichen Prozesslänge.
• Aufgrund der langen Wartezeiten werden in einem reinen RR-System Fristen nur selten eingehalten.
• Ein Verhungern der Prozesse kann nicht auftreten, da keine Priorität vergeben wird. Die Reihenfolge der Zeiteinheitenzuteilung basiert auf der Ankunftszeit der Prozesse, ähnlich dem FIFO-Prinzip.
• Ist der Zeitschlitz groß, wird er nach dem FCFS-/FIFO-Prinzip verfahren; ist er klein, wird er nach dem SJF-/SRTF-Prinzip verfahren.

Dies eignet sich für Situationen, in denen Prozesse leicht in verschiedene Gruppen unterteilt werden können. Beispielsweise wird üblicherweise zwischen Vordergrundprozessen (interaktiven Prozessen) und Hintergrundprozessen (Batch-Prozessen) unterschieden. Diese beiden Prozesstypen haben unterschiedliche Anforderungen an die Reaktionszeit und benötigen daher möglicherweise unterschiedliche Planungsanforderungen. Es ist besonders nützlich bei Problemen mit gemeinsam genutztem Speicher .

Ein arbeitssparender Scheduler versucht stets, die geplanten Ressourcen auszulasten, sofern Aufträge zur Ausführung bereitstehen. Im Gegensatz dazu kann ein nicht arbeitssparender Scheduler die geplanten Ressourcen unter Umständen ungenutzt lassen, obwohl Aufträge zur Ausführung bereitliegen.

Es gibt verschiedene Planungsprobleme, bei denen es darum geht, zu entscheiden, welcher Auftrag wann an welche Station geht, sodass die Gesamtbearbeitungszeit minimiert wird:

• Job-Shop-Planung  – es gibt n Aufträge und m identische Stationen. Jeder Auftrag soll auf einer einzelnen Maschine ausgeführt werden. Dies wird üblicherweise als Online-Problem betrachtet.
• Offene Fertigungsplanung  – es gibt n Aufträge und m verschiedene Stationen. Jeder Auftrag soll an jeder Station eine gewisse Zeit verbringen, in freier Reihenfolge.
• Ablaufplanung im Fertigungsfluss  – es gibt n Aufträge und m verschiedene Stationen. Jeder Auftrag soll in einer vorgegebenen Reihenfolge eine gewisse Zeit an jeder Station verbringen.

Eine gängige Methode in eingebetteten Systemen ist die manuelle Jobplanung. Dies kann beispielsweise zeitmultiplexiert erfolgen. Manchmal wird der Kernel in drei oder mehr Teile unterteilt: manuelle Planung, präemptives Verfahren und Interrupt-Ebene. Die genauen Methoden zur Jobplanung sind oft proprietär.

• Keine Ressourcenknappheitsprobleme
• Sehr hohe Vorhersagbarkeit; ermöglicht die Implementierung von harten Echtzeitsystemen
• Nahezu kein Verwaltungsaufwand
• Möglicherweise nicht für alle Anwendungen optimal.
• Die Wirksamkeit hängt vollständig von der Umsetzung ab.

Bei der Entwicklung eines Betriebssystems muss der Programmierer abwägen, welcher Scheduling-Algorithmus für die vorgesehene Systemnutzung am besten geeignet ist. Es gibt keinen universell besten Scheduling-Algorithmus; viele Betriebssysteme verwenden erweiterte oder kombinierte der oben genannten Algorithmen.

Windows NT /XP/Vista verwendet beispielsweise eine mehrstufige Feedback-Warteschlange , eine Kombination aus präemptivem Scheduling mit fester Priorität, Round-Robin- und FIFO-Algorithmen. In diesem System kann die Priorität von Threads dynamisch steigen oder fallen, je nachdem, ob sie bereits bearbeitet wurden oder lange warten mussten. Jede Prioritätsstufe wird durch eine eigene Warteschlange repräsentiert, wobei Threads mit hoher Priorität im Round-Robin-Verfahren und Threads mit niedrigerer Priorität nach dem FIFO-Prinzip abgearbeitet werden. Dadurch ist die Antwortzeit für die meisten Threads kurz, und kurze, aber kritische Systemthreads werden sehr schnell abgeschlossen. Da Threads in der Warteschlange mit der höchsten Priorität nur eine Zeiteinheit des Round-Robin-Verfahrens nutzen können, kann es bei längeren Threads mit hoher Priorität zu Ressourcenmangel kommen.

Der verwendete Algorithmus kann so einfach sein wie Round-Robin, bei dem jeder Prozess in einer zyklischen Liste gleich lange ausgeführt wird (beispielsweise 1 ms, üblicherweise zwischen 1 ms und 100 ms). Prozess A wird also 1 ms lang ausgeführt, dann Prozess B, dann Prozess C und dann wieder Prozess A.

Fortgeschrittenere Algorithmen berücksichtigen die Prozesspriorität bzw. die Wichtigkeit eines Prozesses. Dadurch können manche Prozesse mehr Zeit nutzen als andere. Der Kernel verwendet stets alle Ressourcen, die er für die ordnungsgemäße Funktion des Systems benötigt, und besitzt daher quasi unendliche Priorität. In SMP- Systemen trägt die Prozessoraffinität zur Steigerung der Gesamtleistung bei, selbst wenn dies die Laufzeit einzelner Prozesse verlangsamen kann. Im Allgemeinen verbessert dies die Leistung durch die Reduzierung von Cache-Thrashing .

IBM OS/360 war mit drei verschiedenen Schedulern erhältlich. Die Unterschiede waren so groß, dass die Varianten oft als drei verschiedene Betriebssysteme betrachtet wurden:

• Die Option „Single Sequential Scheduler“ , auch bekannt als „ Primary Control Program (PCP)“, ermöglichte die sequentielle Ausführung eines einzelnen Jobstroms.
• Die Option „Mehrere sequentielle Scheduler“ ( Multiprogrammierung mit fester Anzahl von Aufgaben, MFT) ermöglichte die Ausführung mehrerer paralleler Jobs. Die Ausführung wurde durch eine Priorität gesteuert, die entweder für jeden Stream standardmäßig festgelegt oder für jeden Job separat angefordert werden konnte. MFT Version II führte Unteraufgaben (Threads) ein, deren Priorität sich nach der Priorität des übergeordneten Jobs richtete. Jeder Job-Stream definierte die maximale Speichermenge, die von einem Job innerhalb dieses Streams verwendet werden durfte.
• Die Option „Mehrere Prioritätsplaner“ oder „Multiprogrammierung mit variabler Anzahl von Aufgaben“ (MVT) beinhaltete von Anfang an Unteraufgaben; jeder Job forderte vor der Ausführung die Priorität und den Speicher an, die er benötigte.

Spätere Versionen von MVS für den virtuellen Speicher fügten dem Scheduler eine Workload-Manager -Funktion hinzu, die die Prozessorressourcen nach einem von der Installation definierten detaillierten Schema plant.

Die ersten MS-DOS- und Microsoft Windows-Systeme waren nicht multitaskingfähig und besaßen daher keinen Scheduler. Windows 3.1x verwendete einen nicht-präemptiven Scheduler, der Programme nicht unterbrach. Er verließ sich darauf, dass das Programm beendet wurde oder dem Betriebssystem mitteilte, dass es den Prozessor nicht mehr benötigte, um mit einem anderen Prozess fortzufahren. Dies wird üblicherweise als kooperatives Multitasking bezeichnet. Windows 95 führte einen rudimentären präemptiven Scheduler ein; aus Gründen der Abwärtskompatibilität ließ man 16-Bit-Anwendungen jedoch ohne Präemption laufen. ^{[ 10 ]}

Windows NT -basierte Betriebssysteme verwenden eine mehrstufige Feedback-Warteschlange. Es sind 32 Prioritätsstufen definiert (0 bis 31), wobei die Prioritäten 0 bis 15 normale Prioritäten und die Prioritäten 16 bis 31 weiche Echtzeitprioritäten darstellen, deren Zuweisung Berechtigungen erfordert. Priorität 0 ist für das Betriebssystem reserviert. Benutzerschnittstellen und APIs arbeiten mit Prioritätsklassen für den Prozess und die Threads im Prozess, die vom System anschließend zur absoluten Prioritätsstufe kombiniert werden.

Der Kernel kann die Priorität eines Threads abhängig von dessen E/A- und CPU-Auslastung sowie seiner Interaktivität (d. h. ob er Eingaben von Benutzern entgegennimmt und darauf reagiert) anpassen. Dabei wird die Priorität interaktiver und E/A-intensiver Prozesse erhöht und die von CPU-intensiven Prozessen gesenkt, um die Reaktionsfähigkeit interaktiver Anwendungen zu verbessern. ^{[ 11 ]} In Windows Vista wurde der Scheduler so modifiziert , dass er den Zykluszähler moderner Prozessoren nutzt, um die genaue Anzahl der von einem Thread ausgeführten CPU-Zyklen zu erfassen, anstatt lediglich eine Intervalltimer-Interruptroutine zu verwenden. ^{[ 12 ]} Vista verwendet außerdem einen Prioritäts-Scheduler für die E/A-Warteschlange, um zu verhindern, dass Defragmentierungsprogramme und ähnliche Anwendungen Vordergrundoperationen beeinträchtigen. ^{[ 13 ]}

Mac OS 9 verwendet kooperatives Scheduling für Threads, wobei ein Prozess mehrere kooperative Threads steuert, und bietet außerdem präemptives Scheduling für Multiprocessing-Tasks. Der Kernel plant Multiprocessing-Tasks mithilfe eines präemptiven Scheduling-Algorithmus. Alle Process-Manager-Prozesse laufen innerhalb eines speziellen Multiprocessing-Tasks, dem sogenannten Blue Task . Diese Prozesse werden kooperativ mithilfe eines Round-Robin-Scheduling- Algorithmus geplant; ein Prozess gibt die Kontrolle über den Prozessor an einen anderen Prozess ab, indem er explizit eine blockierende Funktion wie ` run` aufruft WaitNextEvent. Jeder Prozess verfügt über eine eigene Kopie des Thread-Managers , der die Threads dieses Prozesses kooperativ plant; ein Thread gibt die Kontrolle über den Prozessor an einen anderen Thread ab, indem er `run` YieldToAnyThreadoder ` run` aufruft YieldToThread. ^{[ 14 ]}

macOS verwendet eine mehrstufige Feedback-Warteschlange mit vier Prioritätsstufen für Threads: normal, hohe Systempriorität, nur im Kernelmodus und Echtzeit. ^{[ 15 ]} Threads werden präemptiv eingeplant; macOS unterstützt in seiner Implementierung des Thread-Managers in Carbon auch kooperativ geplante Threads . ^{[ 14 ]}

In AIX Version 4 gibt es drei mögliche Werte für die Thread-Scheduling-Richtlinie:

• First In, First Out (FIFO): Sobald ein Thread mit dieser Richtlinie eingeplant ist, wird er bis zum Ende ausgeführt, es sei denn, er wird blockiert, gibt die CPU-Kontrolle freiwillig ab oder ein Thread mit höherer Priorität kann gestartet werden. Nur Threads mit fester Priorität können eine FIFO-Richtlinie verwenden.
• Round Robin: Dies ähnelt dem Round-Robin-Scheduler-Verfahren von AIX Version 3, das auf 10-ms-Zeitscheiben basiert. Sobald ein RR-Thread am Ende der Zeitscheibe die Kontrolle übernimmt, wird er ans Ende der Warteschlange der verteilbaren Threads seiner Priorität eingereiht. Nur Threads mit fester Priorität können die Round-Robin-Scheduling-Richtlinie verwenden.
• SONSTIGES: Diese Richtlinie ist gemäß POSIX 1003.4a implementierungsabhängig. In AIX Version 4 entspricht sie der RR-Richtlinie, gilt jedoch für Threads mit nicht fester Priorität. Die Neuberechnung der Priorität des laufenden Threads bei jedem Taktinterrupt kann dazu führen, dass ein Thread die Kontrolle verliert, weil seine Priorität die eines anderen ausführbaren Threads übersteigt. Dieses Verhalten entspricht dem von AIX Version 3.

Threads sind vor allem für Anwendungen interessant, die aktuell aus mehreren asynchronen Prozessen bestehen. Durch die Umstellung auf eine Multithread-Architektur könnten diese Anwendungen die Systemlast verringern.

AIX 5 implementiert die folgenden Scheduling-Richtlinien: FIFO, Round Robin und Fair Round Robin. Die FIFO-Richtlinie existiert in drei verschiedenen Implementierungen: FIFO, FIFO2 und FIFO3. Die Round-Robin-Richtlinie heißt in AIX SCHED_RR, die Fair-Round-Robin-Richtlinie SCHED_OTHER. ^{[ 16 ]}

Linux 1.2 verwendete ein Round-Robin-Scheduling- Verfahren. ^{[ 17 ]}

Linux 2.2 führte Scheduling-Klassen und Unterstützung für symmetrisches Multiprocessing (SMP) ein. ^{[ 17 ]}

In Linux 2.4 ^{[ 17 ]} wurde ein O(n)-Scheduler mit einer mehrstufigen Feedback-Warteschlange mit Prioritätsstufen von 0 bis 140 verwendet; die Stufen 0–99 sind für Echtzeitaufgaben reserviert, die Stufen 100–140 gelten als „Nice“ -Aufgaben. Für Echtzeitaufgaben betrug das Zeitquantum zum Umschalten der Prozesse etwa 200 ms, für „Nice“-Aufgaben etwa 10 ms. Der Scheduler verarbeitete die Ausführungswarteschlange aller bereiten Prozesse, wobei die Prozesse mit der höchsten Priorität zuerst ausgeführt wurden und ihre Zeitschlitze durchliefen. Anschließend wurden sie in eine Ablaufwarteschlange eingereiht. Sobald die aktive Warteschlange leer war, wurde die Ablaufwarteschlange zur aktiven Warteschlange und umgekehrt.

Allerdings ersetzten einige Enterprise -Linux-Distributionen wie SUSE Linux Enterprise Server diesen Scheduler durch eine Rückportierung des O(1)-Schedulers (der von Alan Cox in seiner Linux 2.4-ac Kernel-Serie gepflegt wurde ) auf den von der Distribution verwendeten Linux 2.4-Kernel.

In den Versionen 2.6.0 bis 2.6.22 verwendete der Kernel einen O(1)-Scheduler, der von Ingo Molnar und vielen anderen Kernel-Entwicklern während der Entwicklung von Linux 2.5 entwickelt worden war. Für viele Kernel aus diesem Zeitraum entwickelte Con Kolivas Patch-Sets, die die Interaktivität mit diesem Scheduler verbesserten oder ihn sogar durch eigene Scheduler ersetzten.

Die Arbeit von Con Kolivas, insbesondere seine Implementierung eines fairen Scheduling-Verfahrens namens Rotating Staircase Deadline (RSDL), inspirierte Ingo Molnár zur Entwicklung des Completely Fair Scheduler (CFS) als Ersatz für den früheren O(1)-Scheduler . In seiner Ankündigung würdigte Molnár Kolivas. ^{[ 18 ]} CFS ist die erste Implementierung eines fairen Warteschlangen -Schedulers, der in einem Allzweckbetriebssystem weit verbreitet eingesetzt wurde. ^{[ 19 ]}

Der CFS verwendet einen gut erforschten, klassischen Scheduling-Algorithmus namens Fair Queuing , der ursprünglich für Paketnetzwerke entwickelt wurde . Fair Queuing wurde zuvor unter dem Namen Stride Scheduling für die CPU-Planung eingesetzt . Der Fair-Queuing-CFS-Scheduler hat eine Scheduling-Komplexität von O(N^ N) , wobei N die Anzahl der Aufgaben in der Ausführungswarteschlange ist . Die Auswahl einer Aufgabe erfolgt in konstanter Zeit, das Wiedereinfügen einer ausgeführten Aufgabe erfordert jedoch O(N ^N) Operationen, da die Ausführungswarteschlange als Rot-Schwarz-Baum implementiert ist . ${\displaystyle O(\log N)}$${\displaystyle O(\log N)}$

Der Brain Fuck Scheduler , ebenfalls von Con Kolivas entwickelt, ist eine Alternative zum CFS.

Im Jahr 2023 schlug Peter Zijlstra vor, CFS durch einen EEVDF-Prozessplaner ( Earliest Eligible Virtual Deadline First Scheduling ) zu ersetzen. ^{[ 20 ] [ 21 ]} Ziel war es, die Notwendigkeit von CFS- Latenzverbesserungspatches zu beseitigen . ^{[ 22 ]}

Linux 6.12 führte die Unterstützung für Scheduler-Erweiterungen ein, die aus dem Benutzermodus hinzugefügt werden können ; dieser Mechanismus ist als sched_ext bekannt. Ein eBPF- Programm kann in den Kernel geladen werden, um eine Scheduling-Richtlinie zu implementieren. ^{[ 23 ]} Diese Scheduler können den Standard-Scheduler ersetzen. ^{[ 24 ]}

FreeBSD verwendet eine mehrstufige Feedback-Warteschlange mit Prioritäten von 0 bis 255. Die Prioritäten 0–63 sind für Interrupts reserviert, 64–127 für die obere Hälfte des Kernels, 128–159 für Echtzeit-Benutzerthreads, 160–223 für zeitgeteilte Benutzerthreads und 224–255 für inaktive Benutzerthreads. Wie Linux verwendet auch FreeBSD eine aktive Warteschlange, verfügt aber zusätzlich über eine Leerlauf-Warteschlange. ^{[ 25 ]}

NetBSD verwendet eine mehrstufige Feedback-Warteschlange mit Prioritäten von 0 bis 223. Die Prioritäten 0 bis 63 sind für zeitgeteilte Threads reserviert (Standard, SCHED_OTHER-Richtlinie), 64 bis 95 für Benutzer-Threads, die in den Kernel-Bereich eingetreten sind , 96 bis 128 für Kernel-Threads, 128 bis 191 für Benutzer-Echtzeit-Threads (SCHED_FIFO- und SCHED_RR-Richtlinien) und 192 bis 223 für Software-Interrupts .

Solaris verwendet eine mehrstufige Feedback-Warteschlange mit Prioritäten von 0 bis 169. Die Prioritäten 0–59 sind für zeitgeteilte Threads reserviert, 60–99 für System-Threads, 100–159 für Echtzeit-Threads und 160–169 für Interrupts mit niedriger Priorität. Anders als unter Linux ^{[ 25 ]} erhält ein Prozess nach Ablauf seines Zeitquantums eine neue Priorität und wird wieder in die Warteschlange eingereiht. Solaris 9 führte zwei neue Scheduling-Klassen ein: die Klasse mit fester Priorität und die Klasse mit fairer Ressourcenverteilung. Threads mit fester Priorität haben denselben Prioritätsbereich wie die Threads der Klasse mit zeitgeteilter Priorität, ihre Prioritäten werden jedoch nicht dynamisch angepasst. Die Klasse mit fairer Ressourcenverteilung verwendet CPU- Anteile , um Threads für Scheduling-Entscheidungen zu priorisieren. CPU-Anteile geben den Anspruch auf CPU-Ressourcen an. Sie werden einer Gruppe von Prozessen, die zusammen ein Projekt bilden, zugewiesen. ^{[ 7 ]}

• Betriebssysteme: Drei leicht verständliche Teile von Remzi H. Arpaci-Dusseau und Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevante Kapitel: Scheduling: Einführung, Mehrstufige Rückkopplungswarteschlange, Proportional-Share- Scheduling, Multiprozessor-Scheduling
• Kurze Erläuterung der Job-Scheduling-Algorithmen
• Den Linux-Kernel verstehen: Kapitel 10 Prozessplanung
• Kerneltrap: Artikel zum Linux-Kernel-Scheduler
• AIX CPU-Überwachung und -Optimierung
• Josh Aas' Einführung in die Linux 2.6.8.1 CPU-Scheduler-Implementierung
• Peter Brucker, Sigrid Knust. Komplexitätsresultate für Scheduling-Probleme [2]
• Die TORSCHE Scheduling Toolbox für Matlab ist eine Toolbox mit Scheduling- und Graphalgorithmen.
• Eine Studie zur Paketplanung in Mobilfunknetzen
• Großflächiges Clustermanagement bei Google mit Borg