Round-Robin-Planung

Ein rundes Robin -Präventivplanungsbeispiel mit Quantum = 3

Round-Robin (Rr) ist einer der Algorithmen, die von verwendet werden Prozess und Netzwerkplaner in Computer.^[1][2] Da wird der Begriff allgemein verwendet, time slices (auch als Zeitquanta bekannt)^[3] werden jedem Prozess in gleichen Teilen und in zirkulärer Reihenfolge zugewiesen, um alle Prozesse ohne Priorität zu behandeln (auch als bekannt als Cyclic Executive). Round-Robin-Planung ist einfach, einfach zu implementieren und Hunger-frei. Die Round-Robin-Planung kann auf andere Planungsprobleme angewendet werden, wie z. B. die Datenpaketplanung in Computernetzwerken. Es ist ein Betriebssystem Konzept.^[4]

Der Name des Algorithmus stammt aus dem Round-Robin Prinzip, bekannt aus anderen Feldern, bei denen jede Person einen gleichen Anteil an etwas hat.

Prozessplanung

Um Prozesse fair zu planen, beschäftigt ein Round-Robin-Scheduler im Allgemeinen Zeitteilung, jedem Job einen Zeitfenster geben oder Quanten^[5] (seine Zulage der CPU -Zeit) und unterbrechen den Job, wenn er bis dahin nicht abgeschlossen ist. Der Job wird beim nächsten Mal wieder ein Zeitfenster zugewiesen. Wenn der Prozess seinen Status während des zugeschriebenen Zeitquantums endet oder ändert, wählt der Scheduler den ersten Prozess in der ausführenden Queue -Warteschlange aus. In Ermangelung von Zeitteilung oder wenn die Quanta im Verhältnis zu den Größen der Arbeitsplätze groß war, würde ein Prozess, der große Arbeitsplätze erzeugt, gegenüber anderen Prozessen bevorzugt.

Der Round-Robin-Algorithmus ist ein präventiver Algorithmus, da der Scheduler den Prozess aus der CPU erzwingt, sobald die Zeitquote abläuft.

Zum Beispiel, wenn der Zeitfenster 100 Millisekunden beträgt, und Job1 Der Rund-Robin-Scheduler nimmt eine Gesamtzeit von 250 ms, um den Job nach 100 ms auszusetzen und anderen Jobs ihre Zeit auf der CPU zu geben. Sobald die anderen Jobs ihren gleichen Anteil hatten (jeweils 100 ms), Job1 wird eine weitere Zuteilung von bekommen Zentralprozessor Zeit und der Zyklus wird sich wiederholen. Dieser Prozess wird fortgesetzt, bis der Job abgeschlossen ist und keine Zeit mehr in der CPU benötigt.

• Job1 = Gesamtzeit für die Fertigstellung von 250 ms (Quantum 100 ms).

1. Erste Zuordnung = 100 ms.
2. Zweite Zuordnung = 100 ms.
3. Dritte Zuordnung = 100 ms aber Job1 Selbstbekämpfung nach 50 ms.
4. Gesamt -CPU -Zeit von Job1 = 250 ms

Betrachten Sie die folgende Tabelle mit der Ankunftszeit und führen Sie die Zeit des Prozesses mit der Quantenzeit von 100 ms aus, um die Round-Robin-Planung zu verstehen:

Ein anderer Ansatz besteht darin, alle Prozesse in eine gleiche Anzahl von Zeitpunktquanten zu unterteilen, so dass die Quantengröße proportional zur Größe des Prozesses ist. Daher enden alle Prozesse gleichzeitig.

Zeitplanung für Netzwerkpaket

Im Best-Effort Paketschaltung und andere Statistisches MultiplexingDie Round-Robin-Planung kann als Alternative zu verwendet werden Wer zuerst kommt, mahlt zuerst Warteschlange.

Ein Multiplexer, einen Schalter oder ein Router, der die Round-Robin-Planung bietet, verfügt über eine separate Warteschlange für jeden Datenfluss, bei dem ein Datenfluss anhand seiner Quelle und Zieladresse identifiziert werden kann. Der Algorithmus ermöglicht es jedem aktiven Datenfluss, der Datenpakete in der Warteschlange in der Warteschlange zum Übertragen von Paketen auf einem gemeinsam genutzten Kanal in regelmäßig wiederholter Reihenfolge abbiefen. Die Planung ist arbeitsbedingt, was bedeutet, dass der nächste Datenfluss seinen Platz einnimmt, wenn ein Fluss nicht mehr Pakete ist. Daher versucht die Planung, zu verhindern, dass Link -Ressourcen nicht genutzt werden.

Round-Robin-Planung führt zu Max-min-Fairness Wenn die Datenpakete gleich groß sind, da der Datenfluss, der die längste Zeit gewartet hat, haben die Planungspriorität. Es ist möglicherweise nicht wünschenswert, wenn die Größe der Datenpakete von einem Job zum anderen sehr unterschiedlich ist. Ein Benutzer, der große Pakete produziert, wird gegenüber anderen Benutzern bevorzugt. In diesem Fall faire Warteschlange wäre vorzuziehen.

Wenn garantiert oder differenzierte Servicequalität angeboten wird und nicht nur die Best-Effort-Kommunikation, Defizit Round-Robin (DRR) Planung, Gewichtter Round-Robin (WRR) Planung oder Gewichtete faire Warteschlange (WFQ) kann berücksichtigt werden.

Im mehrfacher Zugang Netzwerke, in denen mehrere Terminals mit einem gemeinsam genutzten physischen Medium verbunden sind, kann die Round-Robin-Planung von vorhanden sein von Token vorbei Kanalzugriff Pläne wie Token-Ring, oder von Umfragen oder Ressourcenreservierung von einer zentralen Kontrollstation.

In einem zentralisierten drahtlosen Paket-Radio-Netzwerk, in dem viele Stationen einen Frequenzkanal teilen, kann ein Planungsalgorithmus in einer zentralen Basisstation Zeitfenster für die mobilen Stationen runden Robin reservieren und Fairness bieten. jedoch, wenn Linkanpassung Wird verwendet, dauert es viel länger, bis eine bestimmte Datenmenge an "teure" Benutzer als an andere übertragen wird, da sich die Kanalbedingungen unterscheiden. Es wäre effizienter, mit dem Getriebe zu warten, bis die Kanalbedingungen verbessert sind, oder zumindest um weniger teure Benutzer Priorität zu ermöglichen. Die Round-Robin-Planung nutzt dies nicht. Höherer Durchsatz und Systemspektrumeffizienz kann durch kanalabhängige Planung erreicht werden, zum Beispiel a proportional fair Algorithmus, oder Maximale Durchsatzplanung. Beachten Sie, dass letzteres durch unerwünschte Weise gekennzeichnet ist Planungshunger. Diese Art der Zeitplanung ist eines der grundlegenden Algorithmen für Betriebssysteme in Computern, die durch die Datenstruktur für kreisförmige Warteschlangen implementiert werden können.

Siehe auch

• Multilevel -Warteschlange

Verweise