Round Robin Scheduling Algorithmus mit Beispiel

Inhaltsverzeichnis:

Anonim

Was ist Round-Robin-Planung?

Der Name dieses Algorithmus leitet sich vom Round-Robin-Prinzip ab, bei dem jede Person abwechselnd den gleichen Anteil an etwas erhält. Es ist der älteste und einfachste Planungsalgorithmus, der hauptsächlich für Multitasking verwendet wird.

Bei der Round-Robin-Planung wird jede fertige Aufgabe nur für eine begrenzte Zeit in einer zyklischen Warteschlange ausgeführt. Dieser Algorithmus bietet auch eine hungerfreie Ausführung von Prozessen.

In diesem Tutorial zum Betriebssystem lernen Sie:

  • Was ist Round-Robin-Planung?
  • Merkmale der Round-Robin-Planung
  • Beispiel für eine Round-Robin-Planung
  • Vorteil der Round-Robin-Planung
  • Nachteile der Round-Robin-Planung
  • Worst-Case-Latenz

Merkmale der Round-Robin-Planung

Hier sind die wichtigen Merkmale von Round-Robin Scheduling:

  • Round Robin ist ein vorbeugender Algorithmus
  • Die CPU wird nach einer festen Intervallzeit, die als Zeitquanten / Zeitscheibe bezeichnet wird, zum nächsten Prozess verschoben.
  • Der Prozess, der vorbelegt ist, wird am Ende der Warteschlange hinzugefügt.
  • Round Robin ist ein Hybridmodell, das uhrgetrieben ist
  • Die Zeitscheibe sollte minimal sein und wird für eine bestimmte Aufgabe zugewiesen, die verarbeitet werden muss. Es kann sich jedoch von Betriebssystem zu Betriebssystem unterscheiden.
  • Es ist ein Echtzeitalgorithmus, der innerhalb eines bestimmten Zeitlimits auf das Ereignis reagiert.
  • Round Robin ist einer der ältesten, fairsten und einfachsten Algorithmen.
  • Weit verbreitete Planungsmethode in herkömmlichen Betriebssystemen.

Beispiel für eine Round-Robin-Planung

Betrachten Sie diese folgenden drei Prozesse

Prozesswarteschlange Burst-Zeit
P1 4
P2 3
P3 5

Schritt 1) Die Ausführung beginnt mit dem Prozess P1, der die Burst-Zeit 4 hat. Hier wird jeder Prozess 2 Sekunden lang ausgeführt. P2 und P3 stehen noch in der Warteschlange.

Schritt 2 ) Zum Zeitpunkt = 2 wird P1 am Ende der Warteschlange hinzugefügt und P2 beginnt mit der Ausführung

Schritt 3) Zum Zeitpunkt = 4 wird P2 vorbelegt und am Ende der Warteschlange hinzugefügt. P3 wird ausgeführt.

Schritt 4) Zum Zeitpunkt = 6 wird P3 vorbelegt und am Ende der Warteschlange hinzugefügt. P1 beginnt mit der Ausführung.

Schritt 5) Zum Zeitpunkt = 8 hat P1 eine Burst-Zeit von 4. Die Ausführung ist abgeschlossen. P2 startet die Ausführung

Schritt 6) P2 hat eine Burst-Zeit von 3. Es wurde bereits für 2 Intervalle ausgeführt. Zum Zeitpunkt = 9 schließt P2 die Ausführung ab. Dann beginnt P3 mit der Ausführung, bis sie abgeschlossen ist.

Schritt 7) Berechnen wir die durchschnittliche Wartezeit für das obige Beispiel.

Wait timeP1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7

Vorteil der Round-Robin-Planung

Hier sind die Vor- und Vorteile der Round-Robin-Planungsmethode:

  • Es ist nicht mit den Problemen des Hungers oder des Konvoieffekts konfrontiert.
  • Alle Jobs erhalten eine faire CPU-Zuordnung.
  • Es behandelt alle Prozesse ohne Priorität
  • Wenn Sie die Gesamtzahl der Prozesse in der Ausführungswarteschlange kennen, können Sie auch die Antwortzeit im ungünstigsten Fall für denselben Prozess annehmen.
  • Diese Planungsmethode hängt nicht von der Burst-Zeit ab. Deshalb ist es leicht auf dem System zu implementieren.
  • Sobald ein Prozess für einen bestimmten Satz des Zeitraums ausgeführt wird, wird der Prozess vorab ausgeführt, und ein anderer Prozess wird für diesen bestimmten Zeitraum ausgeführt.
  • Ermöglicht dem Betriebssystem die Verwendung der Kontextumschaltmethode, um Status von vorab freigegebenen Prozessen zu speichern.
  • Es bietet die beste Leistung in Bezug auf die durchschnittliche Antwortzeit.

Nachteile der Round-Robin-Planung

Hier sind die Nachteile / Nachteile der Verwendung der Round-Robin-Planung:

  • Wenn die Schnittzeit des Betriebssystems niedrig ist, wird die Prozessorleistung reduziert.
  • Diese Methode verbringt mehr Zeit mit der Kontextumschaltung
  • Seine Leistung hängt stark vom Zeitquantum ab.
  • Für die Prozesse können keine Prioritäten festgelegt werden.
  • Bei der Round-Robin-Planung wird wichtigeren Aufgaben keine besondere Priorität eingeräumt.
  • Verringert das Verständnis
  • Ein niedrigeres Zeitquantum führt zu einem höheren Kontextumschaltaufwand im System.
  • In diesem System ist es ziemlich schwierig, ein korrektes Zeitquantum zu finden.

Worst-Case-Latenz

Dieser Begriff wird für die maximale Zeit verwendet, die für die Ausführung aller Aufgaben benötigt wird.

  • dt = Erkennungszeit, wenn eine Aufgabe in die Liste aufgenommen wird
  • st = Bezeichnet die Umschaltzeit von einer Aufgabe zur anderen
  • et = Bezeichnet die Ausführungszeit der Aufgabe

Formel:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +… + (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISRt,SR = sum of all execution times

Zusammenfassung:

  • Der Name dieses Algorithmus leitet sich vom Round-Robin-Prinzip ab, bei dem jede Person abwechselnd den gleichen Anteil an etwas erhält.
  • Round Robin ist einer der ältesten, fairsten und einfachsten Algorithmen und weit verbreiteten Planungsmethoden in herkömmlichen Betriebssystemen.
  • Round Robin ist ein vorbeugender Algorithmus
  • Der größte Vorteil der Round-Robin-Planungsmethode besteht darin, dass Sie, wenn Sie die Gesamtzahl der Prozesse in der Ausführungswarteschlange kennen, auch die Antwortzeit im ungünstigsten Fall für denselben Prozess annehmen können.
  • Diese Methode verbringt mehr Zeit mit der Kontextumschaltung
  • Die Worst-Case-Latenz ist ein Begriff für die maximale Zeit, die für die Ausführung aller Aufgaben benötigt wird.