CPU-Planung Algorithms in Operating Systems

Arten der CPU-Planung

Es gibt zwei Arten von Planungsmethoden:

Präventive Planung

Beim Preemptive Scheduling werden die Aufgaben meist mit ihren Prioritäten zugewiesen. Manchmal ist es wichtig, eine Aufgabe mit höherer Priorität vor einer anderen Aufgabe mit niedrigerer Priorität auszuführen, auch wenn die Aufgabe mit niedrigerer Priorität noch ausgeführt wird. Die Aufgabe mit niedrigerer Priorität bleibt einige Zeit bestehen und wird fortgesetzt, wenn die Aufgabe mit höherer Priorität ihre Ausführung abgeschlossen hat.

Nicht-präventive Planung

Bei dieser Art von Planungsmethode wurde die CPU einem bestimmten Prozess zugewiesen. Der Prozess, der die CPU beschäftigt hält, gibt die CPU frei, indem er entweder den Kontext wechselt oder beendet wird. Dies ist die einzige Methode, die für verschiedene Hardwareplattformen verwendet werden kann. Das liegt daran, dass keine spezielle Hardware (z. B. ein Timer) wie bei der präventiven Planung erforderlich ist.

Wann ist die Planung präventiv oder nicht präemptiv?

Um festzustellen, ob die Planung präventiv 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 laufenden Zustand in den Bereitschaftszustand.
3. Ein bestimmter Prozess wechselt vom Wartezustand in den Bereitschaftszustand.
4. Der Prozess hat seine Ausführung abgeschlossen und ist beendet.

Es gelten nur die Bedingungen 1 und 4, die Planung wird als nicht präemptiv bezeichnet.

Alle anderen Planungen sind präventiv.

Wichtige CPU-Scheduling-Terminologien

• Burstzeit/Ausführungszeit: Es ist eine Zeit, die der Prozess benötigt, um die Ausführung abzuschließen. Sie wird auch Laufzeit genannt.
• Ankunftszeit: wenn ein Prozess in einen Bereitschaftszustand eintritt
• Endzeit: wenn der Prozess abgeschlossen ist und ein System verlässt
• Multiprogrammierung: Mehrere Programme, die gleichzeitig im Speicher vorhanden sein können.
• Arbeitsplätze: Es ist eine Art Programm ohne jegliche Art von Benutzerinteraktion.
• Benutzer: Es ist eine Art Programm mit Benutzerinteraktion.
• Verarbeiten: Es ist die Referenz, die sowohl für den Job als auch für den Benutzer verwendet wird.
• CPU/IO-Burst-Zyklus: Charakterisiert die Prozessausführung, die zwischen CPU- und I/O-Aktivität wechselt. Die CPU-Zeiten sind in der Regel kürzer als die I/O-Zeit.

CPU-Planungskriterien

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

Maximieren

CPU-Auslastung:Die CPU-Auslastung ist die Hauptaufgabe, bei der das Betriebssystem sicherstellen muss, dass die CPU so ausgelastet wie möglich bleibt. Sie kann zwischen 0 und 100 Prozent liegen. Beim RTOS kann sie jedoch zwischen 40 Prozent für Low-Level-Systeme und 90 Prozent für High-Level-Systeme liegen.

Durchsatz: Die Anzahl der Prozesse, die ihre Ausführung pro Zeiteinheit abschließen, wird als Durchsatz bezeichnet. Wenn die CPU also mit der Ausführung des Prozesses beschäftigt ist, wird zu diesem Zeitpunkt Arbeit geleistet, und die pro Zeiteinheit erledigte Arbeit wird als Durchsatz bezeichnet.

Minimieren

Wartezeit: Die Wartezeit ist die Zeit, die ein bestimmter Prozess in der Bereitschaftswarteschlange warten muss.

Reaktionszeit: Dabei handelt es sich um die Zeitspanne, in der die Anfrage eingereicht wurde, bis die erste Antwort erfolgt.

Seitenwechsel: Die Bearbeitungszeit ist die Zeitspanne, die zur Ausführung eines bestimmten Prozesses benötigt wird. Dabei handelt es sich um die Berechnung der Gesamtzeit, die mit dem Warten auf den Speicher, dem Warten in der Warteschlange und der Ausführung auf der CPU verbracht wurde. Der Zeitraum zwischen der Einreichung des Prozesses und dem Zeitpunkt der Fertigstellung ist die Bearbeitungszeit.

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 multiprogrammierten Betriebssysteme verwenden eine Art Zeitgeber, um zu verhindern, dass ein Prozess das System für immer blockiert.

Was ist Dispatcher?

Es handelt sich um ein Modul, das dem Prozess die Steuerung der CPU ermöglicht. Der Dispatcher sollte schnell sein, damit er bei jedem Kontextwechsel ausgeführt werden kann. Die Dispatch-Latenz ist die Zeit, die der CPU-Scheduler benötigt, um einen Prozess zu stoppen und einen anderen zu starten.

Vom Dispatcher ausgeführte Funktionen:

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

Arten von CPU-Planungsalgorithmen

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

Wer zuerst kommt, malt zuerst

First Come First Serve ist die vollständige Form von FCFS. Es ist der einfachste und einfachste CPU-Planungsalgorithmus. Bei dieser Art von Algorithmus erhält der Prozess, der die CPU anfordert, zuerst die CPU-Zuteilung. Diese Planungsmethode kann mit einer FIFO-Warteschlange verwaltet werden.

Wenn der Prozess in die Bereitschaftswarteschlange eintritt, wird sein PCB (Prozesssteuerungsblock) mit dem Ende der Warteschlange verbunden. Wenn also die CPU frei wird, sollte sie dem Prozess am Anfang der Warteschlange zugewiesen werden.

Merkmale der FCFS-Methode

• Es bietet einen nicht-präemptiven und einen präemptiven Planungsalgorithmus.
• 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

Die vollständige Form von SRT ist die kürzeste verbleibende Zeit. Es wird auch als SJF-Preemptive-Scheduling bezeichnet. Bei dieser Methode wird der Prozess der Aufgabe zugeordnet, die seinem Abschluss am nächsten kommt. Diese Methode verhindert, dass ein neuerer Prozess im Bereitschaftszustand den Abschluss eines älteren Prozesses aufhält.

Merkmale der SRT-Planungsmethode

• Diese Methode wird hauptsächlich in Batch-Umgebungen angewendet, in denen kurze Jobs bevorzugt werden müssen.
• Dies ist keine ideale Methode zur Implementierung in einem gemeinsam genutzten System, bei dem die erforderliche CPU-Zeit unbekannt ist.
• Ordnen Sie jedem Prozess die Länge seines nächsten CPU-Bursts zu. Das Betriebssystem verwendet diese Längen, um den Prozess mit der kürzestmöglichen Zeit zu planen.

Prioritätsbasierte Planung

Prioritätsplanung ist eine Methode zur Planung von Prozessen nach Priorität. Bei dieser Methode wählt der Planer die zu bearbeitenden Aufgaben entsprechend der Priorität aus.

Die Prioritätsplanung hilft dem Betriebssystem auch dabei, Prioritätszuweisungen einzubeziehen. Die Prozesse mit höherer Priorität sollten zuerst ausgeführt werden, während Jobs mit gleicher Priorität im Round-Robin- oder FCFS-Verfahren ausgeführt werden. Die Priorität kann anhand des Speicherbedarfs, des Zeitbedarfs usw. festgelegt werden.

Round-Robin-Planung

Round Robin ist der älteste und einfachste Planungsalgorithmus. Der Name dieses Algorithmus leitet sich vom Round-Robin-Prinzip ab, bei dem jeder abwechselnd einen gleichen Anteil von etwas erhält. Er wird hauptsächlich für Planungsalgorithmen im Multitasking verwendet. Diese Algorithmusmethode hilft bei der unterbrechungsfreien Ausführung von Prozessen.

Merkmale der Round-Robin-Planung

• Round Robin ist ein Hybridmodell, das taktgesteuert ist
• Die Zeitscheibe sollte das Minimum sein, das einer bestimmten zu verarbeitenden Aufgabe zugewiesen ist. Sie kann jedoch für verschiedene Prozesse variieren.
• Es handelt sich um ein Echtzeitsystem, das innerhalb einer bestimmten Zeitspanne auf das Ereignis reagiert.

Kürzester Job zuerst

SJF ist eine vollständige Form von (Shortest job first) und ist ein Planungsalgorithmus, bei dem der Prozess mit der kürzesten Ausführungszeit als nächstes zur Ausführung ausgewählt werden soll. Diese Planungsmethode kann präventiv oder nicht präemptiv sein. Dadurch wird die durchschnittliche Wartezeit für andere Prozesse, die auf die Ausführung warten, erheblich verkürzt.

Merkmale der SJF-Planung

• Sie ist jedem Auftrag als Zeiteinheit für die Fertigstellung zugeordnet.
• Bei dieser Methode wird, wenn die CPU verfügbar ist, zuerst der nächste Prozess oder Job mit der kürzesten Abschlusszeit ausgeführt.
• Es wird mit einer nicht präventiven Richtlinie implementiert.
• Diese Algorithmusmethode eignet sich für die Stapelverarbeitung, bei der das Warten auf den Abschluss von Aufträgen nicht kritisch ist.
• Es verbessert die Auftragsleistung, indem es kürzere Aufträge anbietet, die zuerst ausgeführt werden sollten und meist eine kürzere Bearbeitungszeit haben.

Planung von Warteschlangen auf mehreren Ebenen

Dieser Algorithmus unterteilt die Bereitschaftswarteschlange in verschiedene separate Warteschlangen. Bei dieser Methode werden Prozesse basierend auf einer bestimmten Eigenschaft des Prozesses, wie der Prozesspriorität, der Größe des Speichers usw., einer Warteschlange zugewiesen.

Dies ist jedoch kein unabhängiger Planungsalgorithmus des Betriebssystems, da zur Planung der Jobs andere Algorithmentypen verwendet werden müssen.

Charakteristisch für die mehrstufige Warteschlangenplanung

• Für Prozesse mit bestimmten Merkmalen sollten mehrere Warteschlangen gepflegt werden.
• Jede Warteschlange kann über eigene Planungsalgorithmen verfügen.
• Für jede Warteschlange werden Prioritäten vergeben.

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, Ressourcen zwischen konkurrierenden Prozessen zu verteilen.
• Die maximale Auslastung der CPU kann durch Multiprogrammierung erreicht werden.
• Die auszuführenden Prozesse befinden sich in der Bereitschaftswarteschlange.

Zusammenfassung

• Bei der CPU-Planung handelt es sich um einen Prozess, bei dem bestimmt wird, welcher Prozess die CPU zur Ausführung erhält, während ein anderer Prozess in der Warteschleife ist.
• Beim Preemptive Scheduling werden die Aufgaben meist mit ihren Prioritäten zugewiesen.
• Bei der nicht präemptiven Planungsmethode wurde die CPU einem bestimmten Prozess zugewiesen.
• Die Burst-Zeit ist die Zeit, die der Prozess benötigt, um die Ausführung abzuschließen. Sie wird auch Laufzeit genannt.
• Die CPU-Auslastung ist die Hauptaufgabe, bei der das Betriebssystem sicherstellen muss, dass die CPU möglichst ausgelastet bleibt.
• Die Anzahl der Prozesse, die ihre Ausführung pro Zeiteinheit abschließen, wird als Durchsatz bezeichnet.
• Die Wartezeit ist die Zeitspanne, die ein bestimmter Prozess in der Bereitschaftswarteschlange warten muss.
• Dies ist die Zeitspanne, in der die Anfrage eingereicht wurde, bis die erste Antwort erfolgt.
• Die Bearbeitungszeit ist die Zeitspanne, die zur Ausführung eines bestimmten Prozesses benötigt wird.
• Die Timer-Unterbrechung ist eine Methode, die eng mit der Vorbelegung zusammenhängt.
• Ein Dispatcher ist ein Modul, das dem Prozess die Steuerung der CPU ermöglicht.
• Es gibt sechs Arten von Prozessplanungsalgorithmen: 2) First Come First Serve (FCFS), 3) Shortest-Job-First (SJF)-Planung, 4) Kürzeste verbleibende Zeit, 5) Prioritätsplanung, 6) Round-Robin-Planung, XNUMX) Multilevel-Warteschlangenplanung.
• Im „Wer zuerst kommt, mahlt zuerst“-Methode, erhält der Prozess, der die CPU anfordert, zuerst die CPU-Zuteilung.
• In der kürzesten verbleibenden Zeit wird der Prozess der Aufgabe zugewiesen, die seinem Abschluss am nächsten kommt.
• Bei der Prioritätsplanung wählt der Planer die zu bearbeitenden Aufgaben entsprechend der Priorität aus.
• Round-Robin-Planung funktioniert nach dem Prinzip, dass jede Person abwechselnd den gleichen Anteil an etwas bekommt.
• Im Kürzesten Job zuerst sollte die kürzeste Ausführungszeit für die nächste Ausführung ausgewählt werden.
• Die mehrstufige Planungsmethode unterteilt die Bereitschaftswarteschlange in verschiedene separate Warteschlangen. Bei dieser Methode werden Prozesse anhand einer bestimmten Eigenschaft einer Warteschlange zugeordnet.
• Die CPU nutzt Scheduling, um ihre Effizienz zu verbessern.