1. Einführung
Round Robin ist einer der ältesten und einfachsten präemptiven Scheduling-Algorithmen, der u. a. in interaktiven Systemen verwendet wird. Wichtige Begrifflichkeiten im Umgang mit diesem Verfahren sind das Quantum und die Ready-Queue. Unter dem Quantum versteht man eine Zeitscheibe bzw. einen Zeitabschnitt, in dem ein Prozess die CPU nutzen darf. Die Ready-Queue enthält alle Prozesse, die sich im Zustand Ready befinden.
2. Wie funktioniert der Round Robin Algorithmus?
- Alle Prozesse/Threads im Zustand Ready befinden sich in einer Warteschlange (der Ready Queue).
- Jedem Prozess wird eine Zeitscheibe (Quantum) zugeordnet. Der erste Prozess in der Ready-Queue erhält für die Zeit des Quantums die CPU. Während dieser Zeit befindet sich der Prozess im Zustand Running.
- Wenn der Prozess nach Ablauf des Quantums noch aktiv ist (seinen Task also noch nicht beenden konnte und noch im Zustand Running ist) und mindestens ein Prozess in der Ready-Queue wartet, wird er verdrängt, wieder in den Zustand Ready versetzt und ans Ende der Ready-Queue beordert. Zudem wird der nächste Prozess in der Ready-Queue aktiviert und erhält die CPU.
- Ein blockierter Prozess, der in den Zustand Ready wechselt, wird ans Ende der Ready-Queue gesetzt.
3. Round Robin in der Praxis
Gegeben sei ein System, auf dem die folgenden Prozesse arbeiten:
Prozess P1
Ankunftszeit: 0ms
Verarbeitungszeit: 100ms
Prozess P2
Ankunftszeit: 10ms
Verarbeitungszeit: 40ms
Prozess P3
Ankunftszeit: 20ms
Verarbeitungszeit: 50ms
Prozess P4
Ankunftszeit: 30ms
Verarbeitungszeit: 30ms
Der Scheduler des Systems verwendet für die Zuteilung der CPU den Round Robin Algorithmus mit einem Quantum von 30ms, d. h. ein Prozess kann bis zu 30ms am Stück die CPU für sich beanspruchen.
- In der Ready-Queue befindet sich anfangs nur der Prozess P1. Dieser bekommt direkt die CPU zugeteilt und kann sein Quantum von 30ms aufbrauchen.
- Nach 10ms kommt Prozess P2 an und wird in die Ready-Queue gepackt.
- Nach weiteren 10ms taucht Prozess P3 auf.
- 30ms nach Start von Prozess P1 kommt Prozess P4 hinzu.
- Nachdem P1 sein Quantum aufgebraucht hat, wechselt er in den Zustand Ready und wird ans Ende der Ready-Queue gepackt.
- Nun erhält P2 die CPU und braucht sein Quantum vollständig auf. Der Prozess ist aber (wie bereits zuvor P1) noch nicht fertig. Deshalb wechselt er in den Zustand Ready und wird ans Ende der Ready-Queue gepackt.
- Jetzt ist P3 an der Reihe. P3 arbeitet ebenfalls 30ms lang seinen Task ab. Bei ihm verbleiben 20ms, die es noch abzuarbeiten gilt.
- Nun kommt endlich P4 dran. P4 schafft es, seine 30ms Verarbeitungszeit innerhalb des ihm zur Verfügung gestellten Quantums vollständig abzuarbeiten. Es besteht für den Scheduler also keine Notwendigkeit, diesen Prozess wieder in die Ready-Queue zu schicken.
- P1 ist nun wieder der erste Prozess in der Ready-Queue und erhält für 30ms die CPU. Er benötigt aber immer noch 40ms Verarbeitungszeit und wird, da er sein Quantum aufgebraucht hat, nach dem Wechsel in den Zustand Ready wieder ans Ende der Ready-Queue geschickt.
- Nun bekommt P2 die Chance, seinen Task zu beenden. Hierfür benötigt er nicht einmal das volle Quantum von 30ms, sondern er ist bereits nach 10ms fertig und muss deshalb auch nicht in die Ready-Queue zurückkehren.
- Nun ist wieder P3 an der Reihe. Auch dieser benötigt nur ⅔ seines Quantums und kehrt nicht wieder in die Ready-Queue zurück.
- Jetzt ist P1 der einzige Prozess in der Ready-Queue. Er bekommt direkt die CPU zugewiesen und kann das volle Quantum lang seinen Task abarbeiten.
- Nun hat P1 sein Quantum aufgebraucht. Da keine Prozesse in der Ready-Queue warten, wird er allerdings nicht in die Rady-Queue zurückbeordert, sondern arbeitet im Anschluss seine restlichen 10ms zum Beenden seines Tasks ab.
4. Die Wahl des Quantums
Die Wahl des Quantums muss gut überlegt sein. Es sollte in einem geeigneten Verhältnis zur Zeit für einen Kontextwechsel stehen:
- Wenn das Quantum zu groß ist, dann entstehen evtl. lange Verzögerungen bzw. lange Antwortzeiten.
- Wenn das Quantum zu gering ist, dann entsteht durch die häufigen Kontextwechsel ein großer Overhead.
Auch wenn man viele Performance-Probleme oft durch „mehr“ lösen kann, trifft dies auf das Quantum nicht unbedingt zu! Üblicherweise wählt man ein Quantum von 10ms und 100ms.
5. Fairness
Round Robin scheduled unfair gegenüber I/O-lastigen Prozessen, da diese nur einen Bruchteil ihres Quantums aufbrauchen und danach auf das Ende der CPU-lastigen Prozesse warten müssen, die ihr Quantum meist ganz aufbrauchen. Zur Lösung dieses Problems kann Virtual Round Robin verwendet werden, bei dem nicht verbrauchte Quanten als Guthaben vermerkt werden.
Autor: Florian André Dalwigk
Dieser Artikel hat 50 Bonuspunkte erhalten. Schreib auch du einen Artikel.
