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.


Hinweis

In gewisser Weise ergänzt RR das FCFS-Verfahren um eine Zeitscheibe. Alle Prozesse werden gleich behandelt.


Aufgabe 1

Aufgabe
RR animiert

RR wird in dieser Animation behandelt. Probiere es aus!
Was ist in der Animation der Unterschied zwischen RR1 und RR4?

Hier findest du noch einige Hinweise zum Applet.


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

Aufgabe
Zu kurz oder zu lang

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.)


Win7-quantum-anpassen.JPG


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.


Win2008r2-quantum-anpassen.JPG


Hinweis

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:

und kann dort - je nach Verfügbarkeit der Quellen - nachgelesen werden.


Aufgabe 3

Aufgabe
RR und E/A-lastige Prozesse

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 80x15.png