3.2.10.2.4 Round Robin
Round Robin (RR) ist ein Scheduling-Verfahren, welches die zur Verfügung stehende CPU-Zeit in kleine Zeitscheiben einteilt. Alle Prozesse werden in eine initiale Reihenfolge gebracht und der erste Prozess bekommt die CPU. Er darf diese genau bis zum Ablauf seines Zeit-Quantums nutzen, anschließend wird er unterbrochen und der nächste Prozess in der Reihenfolge ist am Zug. Auch hier findet wieder eine Unterbrechung am Ende des Quantums statt, usw. Nach dem letzten Prozess ist wieder der Erste an der Reihe.
In gewisser Weise ergänzt RR das FCFS-Verfahren um eine Zeitscheibe. Alle Prozesse werden gleich behandelt.
Aufgabe 1
RR wird in dieser Animation behandelt. Probiere es aus!
Achte darauf, dass unter 'Scheduling strategy' der richtige Scheduling-Algorithmus ausgewählt ist. Und finde heraus, welche Bedeutung 'CPU burst' und 'IO burst' in dieser Animation haben.
Optimale Länge einer Zeitscheibe
Es drängt sich die Frage nach der optimalen Länge einer Zeitscheibe auf. Sie soll nicht zu lang und nicht zu kurz sein. (Was eine herrlich diplomatische Antwort darstellt.)
Aufgabe 2
Es ist denkbar, dass das Betriebssystem deines PCs oder Laptops nach dem RR-Verfahren arbeitet. Was ist zu befürchten,
- wenn das Quantum zu kurz gewählt ist?
- wenn das Quantum zu lang gewählt ist?
Zeitscheiben in der Praxis
Tanenbaum 2009 und Strelen 2012 geben an, dass Zeitscheiben in einer Größenordnung von 10 bis 50 ms verbreitet seien. Eisenhardt et.al. 2007 sehen typische Längen zwischen 10 und 100 ms, und bei Mandl 2013 ist ein Intervall von 10 bis 200 ms zu finden. (Zumindest in der unteren Grenze sind sich alle einig.)
In einem Knowledge Base Artikel von Microsoft (KB 259025) finden sich einige Hinweise zur Länge der verwendeten Zeitscheiben bei Windows 2000 und Windows XP. Je nach Prozessor und Konfiguration von Windows gehen die Werte aber stark auseinander.
Die folgende Abbildung stammt aus einem Windows 7 Professional und zeigt den Ausschnitt eines Konfigurationsfensters. Durch ändern der Option Optimale Leistung anpassen für wird die Länge des Quantums für (Vordergrund-) Programme und Hintergrunddienste verändert, ohne dass man jedoch die tatsächliche Länge in Millisekunden beeinflussen könnte. (Das ist wohl auch besser so.)
Ist das Betriebssystem auf einem Computer installiert, der vorrangig im Dialogbetrieb mit einem User agiert, so ist die Option Optimale Leistung anpassen für Programme richtig gewählt. Fungiert der Computer hingegen als Server und bedient die Anfragen verschiedener Clients, so ist Optimale Leistung anpassen für Hintergrunddienste als Einstellung empfehlenswert. Es verwundert daher nicht, dass auf einem Windows Server 2008 R2 das gleiche Konfigurationsfenster zu finden ist, wobei jedoch die alternative Option ausgewählt ist.
Auch wenn viele aktuelle Betriebsysteme Zeitscheiben verwenden, so bedeutet dies nicht, dass auch das ursprüngliche Round Robin-Verfahren, wie es hier beschrieben ist, eingesetzt wird. In gewisser Weise kann man aber sicherlich von einem stark weiterentwickelten und optimierten RR-Verfahren sprechen.
Weiterführende Literatur
RR wird u.a. behandelt bei:
- Eisenhardt et.al. 2007, Kapitel 9.2.4
- Glatz 2010, Kapitel 3.4.3
- Mandl 2013, Kapitel 5.2
- Strelen 2012, Kapitel 4.1
- Tanenbaum 2009, Kapitel 2.4.3
und kann dort - je nach Verfügbarkeit der Quellen - nachgelesen werden.
Aufgabe 3
Dem RR-Verfahren wird nachgesagt, dass es E/A-lastige Prozesse benachteiligt.
Überlege, recherchiere und diskutiere in deiner Lerngruppe:
- Was versteht man unter E/A-lastigen Prozessen?
- Warum kommt es zu einer Benachteiligung?
- Macht es einen Unterschied, ob gerade sehr viele oder nur sehr wenige Prozesse auf dem System gestartet sind?
Diese Seite steht unter der Creative Commons Namensnennung 3.0 Unported Lizenz http://i.creativecommons.org/l/by/3.0/80x15.png