CPU-Planungsalgorithmen in Betriebssystemen

Inhaltsverzeichnis:

Anonim

Was ist CPU-Planung?

Bei der CPU-Planung wird ermittelt, welcher Prozess die CPU zur Ausführung besitzt, während ein anderer Prozess angehalten wird. Die Hauptaufgabe der CPU-Planung besteht darin, sicherzustellen, dass das Betriebssystem immer dann, wenn die CPU inaktiv bleibt, mindestens einen der Prozesse auswählt, die in der Warteschlange für die Ausführung verfügbar sind. Der Auswahlprozess wird vom CPU-Scheduler ausgeführt. Es wählt einen der Prozesse im Speicher aus, die zur Ausführung bereit sind.

In diesem Tutorial zur CPU-Planung erfahren Sie Folgendes:

  • Was ist CPU-Planung?
  • Arten der CPU-Planung
  • Wichtige Terminologien für die CPU-Planung
  • CPU-Planungskriterien
  • Intervall-Timer
  • Was ist der Dispatcher?
  • Arten von CPU-Planungsalgorithmen
  • Wer zuerst kommt, malt zuerst
  • Kürzeste verbleibende Zeit
  • Prioritätsbasierte Planung
  • Round-Robin-Planung
  • Kürzester Job zuerst
  • Planung von Warteschlangen auf mehreren Ebenen
  • Der Zweck eines Planungsalgorithmus

Arten der CPU-Planung

Hier sind zwei Arten von Planungsmethoden:

Präventive Planung

In der vorbeugenden Planung werden die Aufgaben meist mit ihren Prioritäten zugewiesen. Manchmal ist es wichtig, eine Aufgabe mit einer höheren Priorität vor einer anderen Aufgabe mit niedrigerer Priorität auszuführen, selbst wenn die Aufgabe mit der niedrigeren Priorität noch ausgeführt wird. Die Aufgabe mit niedrigerer Priorität hält einige Zeit an und wird fortgesetzt, wenn die Aufgabe mit höherer Priorität ihre Ausführung beendet hat.

Non-Preemptive Scheduling

Bei dieser Art von Planungsmethode wurde die CPU einem bestimmten Prozess zugeordnet. Der Prozess, der die CPU beschäftigt, gibt die CPU entweder durch Umschalten des Kontexts oder durch Beenden frei. Dies ist die einzige Methode, die für verschiedene Hardwareplattformen verwendet werden kann. Dies liegt daran, dass keine spezielle Hardware (z. B. ein Timer) wie die präventive Planung erforderlich ist.

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

Berücksichtigen Sie diese vier Parameter, um festzustellen, ob die Zeitplanung präemptiv oder nicht präemptiv ist:

  1. Ein Prozess wechselt vom laufenden in den Wartezustand.
  2. Ein bestimmter Prozess wechselt vom laufenden Zustand in den Bereitschaftszustand.
  3. Ein bestimmter Prozess wechselt vom Wartezustand in den Bereitschaftszustand.
  4. Prozess beendet seine Ausführung und beendet.

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

Alle anderen Planungen sind präventiv.

Wichtige Terminologien für die CPU-Planung

  • Burst-Zeit / Ausführungszeit: Dies ist eine Zeit, die der Prozess benötigt, um die Ausführung abzuschließen. Es wird auch Laufzeit genannt.
  • Ankunftszeit: Wenn ein Prozess in einen Bereitschaftszustand übergeht
  • Endzeit: Wenn der Prozess abgeschlossen ist und das System verlassen wird
  • Multiprogramming: Eine Reihe von Programmen, die gleichzeitig im Speicher vorhanden sein können.
  • Jobs: Es ist eine Art Programm ohne jegliche Benutzerinteraktion.
  • Benutzer: Es ist eine Art Programm mit Benutzerinteraktion.
  • Prozess: Dies 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 E / A-Aktivität wechselt. Die CPU-Zeiten sind normalerweise kürzer als die E / A-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 beschäftigt wie möglich bleibt. Sie kann zwischen 0 und 100 Prozent liegen. Für das RTOS kann es 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 beenden, ist als Durchsatz bekannt. Wenn die CPU gerade mit der Ausführung des Prozesses beschäftigt ist, wird zu diesem Zeitpunkt die Arbeit erledigt, und die pro Zeiteinheit abgeschlossene Arbeit wird als Durchsatz bezeichnet.

Minimieren:

Wartezeit: Die Wartezeit ist ein Betrag, den ein bestimmter Prozess in der Bereitschaftswarteschlange warten muss.

Antwortzeit: Dies ist ein Zeitraum, in dem die Anforderung gesendet wurde, bis die erste Antwort erstellt wurde.

Bearbeitungszeit: Die Bearbeitungszeit ist eine Menge an Zeit , um einen bestimmten Prozess auszuführen. Dies ist die Berechnung der Gesamtzeit, die darauf gewartet wird, in den Speicher zu gelangen, in der Warteschlange zu warten und auf der CPU ausgeführt zu werden. Der Zeitraum zwischen der Übermittlung des Prozesses und der Fertigstellung ist die Bearbeitungszeit.

Intervall-Timer

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

Die meisten mehrfach programmierten Betriebssysteme verwenden eine Art Timer, um zu verhindern, dass ein Prozess das System für immer bindet.

Was ist der Dispatcher?

Es ist ein Modul, das dem Prozess die Steuerung der CPU ermöglicht. Der Dispatcher sollte schnell sein, damit er auf jedem Kontextwechsel ausgeführt werden kann. Die Versandlatenz 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
  • In den Benutzermodus wechseln
  • Verschieben an die richtige Stelle im neu geladenen Programm.

Arten von CPU-Planungsalgorithmen

Es gibt hauptsächlich sechs Arten von Prozessplanungsalgorithmen

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

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-Zuordnung. Diese Planungsmethode kann mit einer FIFO-Warteschlange verwaltet werden.

Wenn der Prozess in die Bereitschaftswarteschlange eintritt, wird seine Leiterplatte (Process Control Block) mit dem Ende der Warteschlange verknüpft. Wenn die CPU frei wird, sollte sie dem Prozess am Anfang der Warteschlange zugewiesen werden.

Eigenschaften der FCFS-Methode:

  • Es bietet einen nicht präemptiven und präventiven Planungsalgorithmus.
  • Jobs werden immer nach dem Prinzip "Wer zuerst kommt, mahlt zuerst" ausgeführt
  • Es ist einfach zu implementieren und zu verwenden.
  • Diese Methode weist jedoch eine schlechte Leistung auf und die allgemeine Wartezeit ist ziemlich hoch.

Kürzeste verbleibende Zeit

Die vollständige Form der SRT ist die kürzeste verbleibende Zeit. Es ist auch als SJF Preemptive Scheduling bekannt. Bei dieser Methode wird der Prozess der Aufgabe zugewiesen, die seiner Fertigstellung am nächsten kommt. Diese Methode verhindert, dass ein neuerer Bereitschaftsstatusprozess den Abschluss eines älteren Prozesses hä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, um es in einem gemeinsam genutzten System zu implementieren, in 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 so schnell wie möglich zu planen.

Prioritätsbasierte Planung

Die Prioritätsplanung ist eine Methode zum Planen von Prozessen basierend auf der Priorität. Bei dieser Methode wählt der Scheduler die zu erledigenden Aufgaben gemäß der Priorität aus.

Die Prioritätsplanung hilft dem Betriebssystem auch dabei, Prioritätszuweisungen vorzunehmen. Die Prozesse mit höherer Priorität sollten zuerst ausgeführt werden, während Jobs mit gleichen Prioritäten auf Round-Robin- oder FCFS-Basis ausgeführt werden. Die Priorität kann basierend auf Speicheranforderungen, Zeitanforderungen 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 jede Person nacheinander einen gleichen Anteil an etwas erhält. Es wird hauptsächlich zum Planen von Algorithmen im Multitasking verwendet. Diese Algorithmusmethode hilft bei der hungrigen freien Ausführung von Prozessen.

Merkmale der Round-Robin-Planung

  • Round Robin ist ein Hybridmodell, das uhrgetrieben ist
  • Die Zeitscheibe sollte minimal sein, die für eine bestimmte zu verarbeitende Aufgabe zugewiesen ist. Sie kann jedoch für verschiedene Prozesse variieren.
  • Es ist ein Echtzeitsystem, das innerhalb eines bestimmten Zeitlimits auf das Ereignis reagiert.

Kürzester Job zuerst

SJF ist eine vollständige Form von (kürzester Job zuerst) ist ein Planungsalgorithmus, bei dem der Prozess mit der kürzesten Ausführungszeit für die nächste Ausführung ausgewählt werden sollte. Diese Planungsmethode kann präemptiv oder nicht präemptiv sein. Dies reduziert die durchschnittliche Wartezeit für andere Prozesse, die auf die Ausführung warten, erheblich.

Merkmale der SJF-Planung

  • Es ist jedem Auftrag als Zeiteinheit 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 ist nützlich für die Stapelverarbeitung, bei der das Warten auf den Abschluss von Jobs nicht kritisch ist.
  • Es verbessert die Jobausgabe, indem kürzere Jobs angeboten werden, 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 einer Warteschlange zugewiesen, die auf einer bestimmten Eigenschaft des Prozesses basiert, z. B. der Prozesspriorität, der Größe des Speichers usw.

Dies ist jedoch kein unabhängiger Planungsalgorithmus für das Betriebssystem, da andere Arten von Algorithmen verwendet werden müssen, um die Jobs zu planen.

Charakteristik der mehrstufigen Warteschlangenplanung:

  • Für Prozesse mit einigen Merkmalen sollten mehrere Warteschlangen verwaltet werden.
  • Jede Warteschlange kann ihre eigenen Planungsalgorithmen haben.
  • Für jede Warteschlange werden Prioritäten angegeben.

Der Zweck eines Planungsalgorithmus

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

  • Die CPU verwendet die Zeitplanung, um ihre Effizienz zu verbessern.
  • Es hilft Ihnen, Ressourcen auf konkurrierende Prozesse zu verteilen.
  • Die maximale Auslastung der CPU kann durch Mehrfachprogrammierung erreicht werden.
  • Die auszuführenden Prozesse befinden sich in der Warteschlange.

Zusammenfassung:

  • Bei der CPU-Planung wird ermittelt, welcher Prozess die CPU zur Ausführung besitzt, während ein anderer Prozess angehalten wird.
  • In der vorbeugenden Planung 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 eine Zeit, die der Prozess benötigt, um die Ausführung abzuschließen. Es wird auch Laufzeit genannt.
  • Die CPU-Auslastung ist die Hauptaufgabe, bei der das Betriebssystem sicherstellen muss, dass die CPU so beschäftigt wie möglich bleibt
  • Die Anzahl der Prozesse, die ihre Ausführung pro Zeiteinheit beenden, ist als Durchsatz bekannt.
  • Die Wartezeit ist ein Betrag, den ein bestimmter Prozess in der Bereitschaftswarteschlange warten muss.
  • Dies ist eine Zeitspanne, in der die Anfrage gesendet wurde, bis die erste Antwort erstellt wurde.
  • Die Bearbeitungszeit ist die Zeit, die zum Ausführen eines bestimmten Prozesses benötigt wird.
  • Timer-Unterbrechung ist eine Methode, die eng mit Preemption verbunden ist.
  • Ein Dispatcher ist ein Modul, das dem Prozess die Steuerung der CPU ermöglicht.
  • Sechs Arten von Prozessplanungsalgorithmen sind:
  • First Come First Serve (FCFS), 2) SJF-Planung (Shortest-Job-First) 3) Kürzeste verbleibende Zeit 4) Priority-Planung 5) Round-Robin-Planung 6) Mehrstufige Warteschlangenplanung
  • Bei der First Come First Serve-Methode erhält der Prozess, der die CPU anfordert, zuerst die CPU-Zuordnung.
  • In der kürzesten verbleibenden Zeit wird der Prozess der Aufgabe zugewiesen, die seiner Fertigstellung am nächsten kommt.
  • In Prioritätsplanung wählt der Planer die Aufgaben aus, die gemäß der Priorität ausgeführt werden sollen.
  • Diese Round-Robin-Planung funktioniert im Prinzip, bei der jede Person nacheinander einen gleichen Anteil an etwas erhält
  • Im kürzesten Job zuerst sollte die kürzeste Ausführungszeit für die nächste Ausführung ausgewählt werden
  • Bei der mehrstufigen Planung trennt die Methode die Bereitschaftswarteschlange in verschiedene separate Warteschlangen. Bei dieser Methode werden Prozesse einer Warteschlange basierend auf einer bestimmten Eigenschaft zugewiesen
  • Die CPU verwendet die Zeitplanung, um ihre Effizienz zu verbessern.