Round Robin – Der Held der Datenwelt

Der Robin Hood der digitalen Welt nennt sich Round Robin. Wo der Eine Geld von den Reichen an die Armen verteilt, kümmert sich Round Robin um die faire Zuteilung von Zeit.

Round Robin – Held der Datenwelt

Im digitalen Zeitalter und modernen Prozessen ist nicht Geld das Mittel der Begierde sondern Zeit. Jeder Prozess möchte zum Zug kommen und möchte ein wenig Rechenzeit um sich auszutoben.

So gesehen ist Round Robin, der Held der Datenwelt, welcher dafür sorgt, dass scheinbar unwichtige Prozesse ebenfalls gesehen werden und fairerweise zum Zug kommen.

Die Realität ist wohl eher weniger spannend als die Geschichte um Mr. Hood und seine Gefährten, dennoch sehe ich eine Menge Parallelen.

Falls es noch nicht klar geworden ist, hier dreht es sich um ein Scheduling-Verfahren der CPU. Grundlage dabei ist die gerechte Verteilung von CPU-Zeit an verschiedenste Prozesse.

Round Robin

Hunderte Aufgaben strömen pro Sekunde auf einen Rechnerkern ein und alle wollen das Eine: Zeit. Genauer CPU-Zeit zur eigenen Bearbeitung. Doch wie soll diese Gerecht verteilt werden? Wie wird entschieden welcher Prozess bearbeitet wird und welcher nicht? Hier kommt der Protagonist Round Robin ins Spiel.

Round Robin lässt sich relativ schnell erklären. Grundlage sind mehrere Zeitschlitze (Quanten). Dabei wird jedem Prozess ein Zeitraum zur Verfügung gestellt in dem er arbeiten darf. Dann kommt der nächste Prozess dran mit dem gleichen Quantum.

Beispiel:

Drei Prozesse konkurrieren um die Zeit der CPU. Round Robin schreitet ein und legt ein Quantum von 100 Millisekunden fest. Das heißt. Prozess 1 (P1) wird 100 mS ausgeführt, dann kommt Prozess 2 (P2) für 100 mS zum Zug, dann Prozess 3 (P3) ebenfalls mit 100 mS. Dann fängt dieser Vorgang wieder von Vorn an bis die Prozesse fertig sind.

Round Robin – Zeitschlitzverfahren

Jetzt wird laut Round Robin jeder Prozess gleich behandelt. Dabei kann es zu gravierenden Problemen kommen. Nicht jeder Prozess ist gleich. Es gibt bspw. Kritische Hardware Meldungen zur Stromversorgung oder Eingaben wie die Bewegung der Maus, die möglichst schnell umgesetzt werden sollte.

Round Robin und seine Gefährten

Seine wahre Stärke entfaltet Round Robin wenn man ihm ein paar Freunde an die Seite stellt. Priorität könnte somit einer seiner Gefährten heißen. Weist man jetzt den Prozessen eine Priorität zu, kann Robin der Runde relativ schnell entscheiden welcher Prozess wichtig ist oder nicht. Es werden erst alle wichtigen Prozesse abgearbeitet und sich dann sukzessive zu den minderen Prioritäten durch gearbeitet. Kommen zu einer Zeit höhere Prioritäten rein, so werden diese wiederum bevorzugt.

Durchdenkt man das Vorgehen, stellt man schnell fest, dass es ein großes Problem gibt. Das sogenannte Starvation-Problem (Verhungern). Kommen immer wieder Prozesse mit hoher Priorität rein, so werden niedere Prioritäten niemals abgearbeitet. Diese Verhungern dann förmlich.

Round Robin und Bruder Feedback

(Multi-Level-Feedback-Scheduling)

Ein zweiter Geselle heißt Feedback. Dieser berät Round Robin darüber, ob es Prozesse gibt die schon lange nicht mehr am Zuge waren. Tritt dieser Fall ein, so wird die Priorität stückweise erhöht. Damit wird sichergestellt, dass auch die armen und unterdrückten Prozesse mal zum Zuge kommen. Die Priorität wird dann, mit erfolgreicher Quanten-Zuteilung, auch wieder vermindert bis zum Normalniveau.

Die Realität

In der Realität legt das Betriebssystem fest welche Scheduling Strategie angewendet wird. Dabei gibt es beispielsweise Implementierungen mit variablen Quanten. Das Feedback bietet dem verhungernden Prozess dabei die Möglichkeit an, dass wenn er die CPU erhält, diese entsprechend länger benutzen darf. Ebenfalls die Intensität der Erhöhung und Verminderung der Prioritäten wird vom Betriebssystem entschieden.