CPU-Planung Algorithms in Operating Systems

Was ist CPU-Planung?

CPU-Planung Die CPU-Planung bestimmt, welcher Prozess die CPU zur Ausführung nutzt, während ein anderer Prozess wartet. Ihre Hauptaufgabe ist es, sicherzustellen, dass das Betriebssystem bei Leerlauf der CPU mindestens einen der in der Warteschlange befindlichen Prozesse zur Ausführung auswählt. Diese Auswahl trifft der CPU-Scheduler, der einen der im Speicher befindlichen, ausführungsbereiten Prozesse auswählt.

Arten der CPU-Planung

Hier sind zwei Arten von Terminplanungsmethoden:

Präventive Planung

Bei der präemptiven Aufgabenplanung werden die Aufgaben meist anhand ihrer Prioritäten zugewiesen. Manchmal ist es wichtig, eine Aufgabe mit höherer Priorität vor einer anderen Aufgabe mit niedrigerer Priorität auszuführen, selbst wenn die Aufgabe mit niedrigerer Priorität noch läuft. Die Aufgabe mit niedrigerer Priorität wird für eine gewisse Zeit angehalten und fortgesetzt, sobald die Aufgabe mit höherer Priorität ihre Ausführung abgeschlossen hat.

Nicht-präventive Planung

Bei dieser Scheduling-Methode wird die CPU einem bestimmten Prozess zugewiesen. Der Prozess, der die CPU belegt, gibt sie entweder durch Kontextwechsel oder durch Beendigung wieder frei. Es ist die einzige Methode, die auf verschiedenen Hardwareplattformen eingesetzt werden kann, da sie im Gegensatz zum präemptiven Scheduling keine spezielle Hardware (z. B. einen Timer) benötigt.

Wann ist die Terminplanung präemptiv bzw. nicht-präemptiv?

Um festzustellen, ob die Terminplanung präemptiv oder nicht-präemptiv ist, berücksichtigen Sie diese vier Parameter:

1. Ein Prozess wechselt vom laufenden in den wartenden Zustand.
2. Ein bestimmter Prozess wechselt vom Zustand „Läuft“ in den Zustand „Bereit“.
3. Ein bestimmter Prozess wechselt vom Wartezustand in den Bereitschaftszustand.
4. Ein Prozess hat seine Ausführung abgeschlossen und wird beendet.

Wenn nur die Bedingungen 1 und 4 zutreffen, spricht man von einer nicht-präemptiven Terminplanung. Alle anderen Terminplanungssituationen sind präemptiv.

Wichtige Begriffe der CPU-Planung

• Burstzeit/Ausführungszeit: Die Zeit, die ein Prozess zur vollständigen Ausführung benötigt. Sie wird auch Laufzeit genannt.
• Ankunftszeit: Der Zeitpunkt, an dem ein Prozess in den Bereitschaftszustand eintritt.
• Endzeit: Der Zeitpunkt, an dem ein Prozess abgeschlossen ist und das System verlässt.
• Multiprogrammierung: Eine Reihe von Programmen, die gleichzeitig im Speicher vorhanden sein können.
• Arbeitsplätze: Ein Programmtyp ohne jegliche Benutzerinteraktion.
• Benutzer: Eine Art Programm, das Benutzerinteraktion erfordert.
• Verarbeiten: Die Referenz, die sowohl für eine Stelle als auch für einen Benutzer verwendet wird.
• CPU/IO-Burst-Zyklus: Charakterisiert die Prozessausführung, die zwischen CPU- und E/A-Aktivität wechselt. Die CPU-Zeiten sind üblicherweise kürzer als die E/A-Zeiten.

CPU-Planungskriterien

Ein CPU-Planungsalgorithmus versucht Folgendes zu maximieren und zu minimieren:

Maximieren

CPU-Auslastung: Die CPU-Auslastung ist die Hauptaufgabe des Betriebssystems, die CPU optimal auszulasten. Sie kann zwischen 0 und 100 Prozent liegen. Bei einem Echtzeitbetriebssystem (RTOS) variiert sie jedoch zwischen 40 Prozent für ein Low-Level-System und 90 Prozent für ein High-Level-System.

Durchsatz: Die Anzahl der Prozesse, die pro Zeiteinheit ihre Ausführung abschließen, wird als Durchsatz bezeichnet. Wenn die CPU also mit der Ausführung eines Prozesses beschäftigt ist, wird Arbeit verrichtet, und die pro Zeiteinheit geleistete Arbeit wird als Durchsatz bezeichnet.

Minimieren

Wartezeit: Die Wartezeit ist die Zeitspanne, die ein bestimmter Prozess in der Warteschlange warten muss.

Reaktionszeit: Es handelt sich um die Zeitspanne von der Einreichung der Anfrage bis zum Erhalt der ersten Antwort.

Seitenwechsel: Die Durchlaufzeit ist die Zeitspanne, die zur Ausführung eines bestimmten Prozesses benötigt wird. Sie umfasst die Wartezeit für den Speicherzugriff, die Wartezeit in der Warteschlange und die Ausführungszeit auf der CPU. Die Zeitspanne zwischen der Prozessübermittlung und dem Abschluss des Prozesses ist die Durchlaufzeit.

Intervall-Timer

Die Timer-Unterbrechung ist eine Methode, die eng mit der Vorbelegung zusammenhängt. Wenn ein bestimmter Prozess die CPU-Zuteilung erhält, kann ein Timer auf ein bestimmtes Intervall eingestellt werden. Sowohl die Timer-Unterbrechung als auch die Vorbelegung zwingen einen Prozess dazu, die CPU zurückzugeben, bevor sein CPU-Burst abgeschlossen ist.

Die meisten Betriebssysteme mit mehreren Programmen verwenden eine Art Timer, um zu verhindern, dass ein Prozess das System für immer blockiert.

Was ist Dispatcher?

Der Dispatcher ist ein Modul, das die CPU-Steuerung für den Prozess übernimmt. Er muss schnell sein, um bei jedem Kontextwechsel ausgeführt werden zu können. Die Dispatch-Latenz ist die Zeit, die der CPU-Scheduler benötigt, um einen Prozess zu beenden und einen anderen zu starten.

Vom Disponenten ausgeführte Funktionen:

• Kontextwechsel.
• Wechsel in den Benutzermodus.
• An die richtige Stelle im neu geladenen Programm wechseln.

Arten der CPU-Planung Algorithms

Es gibt hauptsächlich sechs Arten von Prozessplanungsalgorithmen:

1. Wer zuerst kommt, mahlt zuerst (FCFS)
2. Shortest-Job-First (SJF)-Planung
3. Kürzeste verbleibende Zeit
4. Prioritätsplanung
5. Round-Robin-Planung
6. Mehrstufige Warteschlangenplanung

Planung Algorithms

Wer zuerst kommt, malt zuerst

FCFS steht für Wer zuerst kommt, malt zuerstEs handelt sich um den einfachsten und unkompliziertesten CPU-Scheduling-Algorithmus. Bei diesem Algorithmus erhält der Prozess, der die CPU anfordert, diese zuerst. Dieses Scheduling-Verfahren kann mithilfe einer FIFO-Warteschlange umgesetzt werden.

Sobald ein Prozess in die Warteschlange eintritt, wird sein Prozesskontrollblock (PCB) mit dem letzten Prozess der Warteschlange verknüpft. Wenn die CPU frei wird, sollte sie daher dem Prozess am Anfang der Warteschlange zugewiesen werden.

Merkmale der FCFS-Methode

• Es handelt sich um einen nicht-präemptiven Scheduling-Algorithmus.
• Aufträge werden immer nach dem Prinzip „Wer zuerst kommt, mahlt zuerst“ ausgeführt.
• Es ist einfach zu implementieren und zu verwenden.
• Allerdings weist diese Methode eine schlechte Leistung auf und die allgemeine Wartezeit ist recht hoch.

Kürzeste verbleibende Zeit

SRT steht für „Shortest Remaining Time“ (kürzeste verbleibende Zeit). Es ist auch als präemptives Scheduling (SJF) bekannt. Bei dieser Methode wird der Prozess derjenigen Aufgabe zugewiesen, die am nächsten an ihrer Fertigstellung ist. Dadurch wird verhindert, dass ein neuerer, bereiter Prozess die Fertigstellung eines älteren Prozesses verzögert.

Merkmale der SRT-Planungsmethode

• Diese Methode wird hauptsächlich in Batch-Umgebungen angewendet, in denen kurzen Aufträgen Vorrang eingeräumt werden muss.
• Dies ist keine ideale Methode zur Implementierung in einem gemeinsam genutzten System, in dem die benötigte CPU-Zeit unbekannt ist.
• Jedem Prozess ist die Länge seines nächsten CPU-Bursts zugeordnet, sodass das Betriebssystem diese Längen nutzt, um den Prozess mit der kürzestmöglichen Zeit einzuplanen.

Prioritätsbasierte Planung

Prioritätsplanung ist eine Methode zur prioritätsbasierten Prozessplanung. Dabei wählt der Scheduler die zu bearbeitenden Aufgaben entsprechend ihrer Priorität aus.

Die Prioritätsplanung unterstützt das Betriebssystem bei der Prioritätsvergabe. Prozesse mit höherer Priorität werden zuerst ausgeführt, während Aufgaben mit gleicher Priorität nach dem Round-Robin- oder FCFS-Prinzip abgearbeitet werden. Die Priorität kann anhand von Speicherbedarf, Zeitanforderungen und anderen Faktoren festgelegt werden.

Round-Robin-Planung

Round Robin ist einer der ältesten und einfachsten Scheduling-Algorithmen. Sein Name leitet sich vom Round-Robin-Prinzip ab, bei dem jeder Teilnehmer abwechselnd die gleiche Menge an Ressourcen erhält. Er wird hauptsächlich für das Scheduling in Multitasking-Systemen eingesetzt. Diese Methode trägt dazu bei, dass Prozesse ohne Wartezeiten ausgeführt werden.

Merkmale der Round-Robin-Planung

• Round Robin ist ein hybrides, taktgesteuertes Modell.
• Der für die Bearbeitung einer bestimmten Aufgabe vorgesehene Zeitrahmen sollte minimal sein. Er kann jedoch je nach Prozess variieren.
• Es verhält sich wie ein Time-Sharing-System, das auf jeden Prozess innerhalb eines bestimmten Zeitlimits reagiert.

Kürzester Job zuerst

SJF (Shortest Job First) ist ein Scheduling-Algorithmus, bei dem der Prozess mit der kürzesten Ausführungszeit als nächster Prozess ausgewählt wird. Dieses Scheduling-Verfahren kann präemptiv oder nicht-präemptiv sein. Es reduziert die durchschnittliche Wartezeit für andere, auf die Ausführung wartende Prozesse erheblich.

Merkmale der SJF-Planung

• Jedem Auftrag ist eine Zeiteinheit für die Erledigung zugeordnet.
• Bei dieser Methode wird, wenn die CPU verfügbar ist, der nächste Prozess oder Auftrag mit der kürzesten Ausführungszeit zuerst ausgeführt.
• Die Umsetzung erfolgt mit einer nicht-präemptiven Strategie.
• Dieser Algorithmus eignet sich für die Stapelverarbeitung, bei der das Warten auf den Abschluss der Aufträge nicht kritisch ist.
• Es verbessert die Arbeitsleistung, indem es zuerst kürzere Aufträge ausführt, die meist eine kürzere Bearbeitungszeit haben.

Planung von Warteschlangen auf mehreren Ebenen

Dieser Algorithmus teilt die Warteschlange für bereite Prozesse in mehrere separate Warteschlangen auf. Dabei werden Prozesse anhand spezifischer Prozesseigenschaften, wie z. B. Prozesspriorität, Speichergröße usw., einer Warteschlange zugeordnet.

Dies ist jedoch kein unabhängiger Scheduling-Algorithmus, da er andere Algorithmen benötigt, um die Jobs zu planen.

Merkmale der mehrstufigen Warteschlangenplanung

• Für Prozesse mit gemeinsamen Eigenschaften sollten mehrere Warteschlangen geführt werden.
• Jede Warteschlange kann ihren eigenen separaten Planungsalgorithmus haben.
• Jedem Warteschlangenbereich werden Prioritäten zugewiesen.

Der Zweck eines Scheduling-Algorithmus

Hier sind die Gründe für die Verwendung eines Planungsalgorithmus:

• Die CPU nutzt Scheduling, um ihre Effizienz zu verbessern.
• Es hilft Ihnen dabei, Ressourcen auf konkurrierende Prozesse zu verteilen.
• Die maximale Auslastung der CPU kann durch Multiprogrammierung erreicht werden.
• Die auszuführenden Prozesse werden in der Warteschlange gespeichert.

Häufig gestellte Fragen