Quelltext der Seite Round Robin (Informatik)

{{Quelle}}
Das '''Rundlauf-Verfahren''', englisch '''Round-Robin''', ist ein [[Scheduling]]-Verfahren, das u.&nbsp;a. [[Warteschlange (Datenstruktur)|Warteschlangen]] abarbeitet.

Zum Einsatz kommt es beispielsweise als [[Prozess-Scheduler]], wo es mehreren konkurrierenden Prozessen begrenzte Ausführungs-Ressourcen zuordnet. Das Round-Robin-Verfahren gewährt allen Prozessen nacheinander für jeweils einen kurzen Zeitraum während eines ''[[Zeitschlitz]]es'' Zuteilung zu einer ausführenden [[CPU]]; man nennt dies auch [[Arbiter|Arbitrierung]].

Round-Robin wird auch zur [[Lastverteilung (Informatik)|Lastverteilung]] (''load balancing'') verwendet. Ziel der Lastverteilung ist es, mehrere gleichartige Ressourcen möglichst gleichmäßig zu beanspruchen.

== Realisierung ==
=== Beispiel Prozess-Scheduler ===
Die Prozesse werden in einer [[Warteschlange (Datenstruktur)|Warteschlange]] verwaltet. Der vorderste Prozess erhält einen Zeitschlitz lang Zugang zu den Ressourcen, dann reiht er sich am Ende der Warteschlange ein und alle Prozesse rücken eine Position vor. Der nächste Prozess wird nach dem [[First In – First Out|FIFO]]-Prinzip ausgewählt. Der Prozess kann die Ressourcen auch freiwillig früher zurückgeben. Auch wenn ein Prozess vor Ende seines Zeitschlitzes abgeschlossen wird, werden die Ressourcen sofort neu zugeteilt.

=== Beispiel Scheduling Multitasking-Betriebssystem ===

Bei Betriebssystemen mit [[Multitasking#Präemptives Multitasking|präemptivem Multitasking]] erstellt der [[Prozess-Scheduler|Scheduler]] für die aktiven [[Prozess (Informatik)|Prozesse]] einen Ausführungsplan nach dem Round-Robin-Verfahren. Dann ermittelt er nach jedem Zeitschlitz über eine Warteschlange den Prozess, der als Nächstes an die Reihe kommt. Der [[Dispatcher]] teilt daraufhin diesem Prozess einen Zeitschlitz lang den Prozessor zu.
<!--
Gegeben seien z.&nbsp;B. eine Zeitscheibe von 20 ms und vier Prozesse (P1, P2, P3, P4) mit den Laufzeiten 57 ms, 18 ms, 23 ms, 40 ms. Die Zeit für den Kontextwechsel bleibt für das Beispiel unberücksichtigt. Je kleiner die Zeitscheibe gewählt wird, desto mehr [[Kontextwechsel]] sind erforderlich, d.&nbsp;h. der Overhead steigt an. Diese Zeit steht Prozessen nicht für die Abarbeitung zur Verfügung.
// ohne Bild fehlt das eigentliche Beispiel
-->
<!-- Das Zeitablaufdiagramm für die Abarbeitung der Prozesse gestaltet sich folgendermaßen:

[[Datei:Round robin.svg]] // Das Bild ist Schrott.
-->

=== Beispiel Lastenverteilung Domain-Server ===

Als Lastverteilung wird Round-Robin z.&nbsp;B. beim [[Domain Name System]] verwendet, wo ein [[Domain Name System#Nameserver|Nameserver]] auf Anfrage mehrere [[IP-Adresse]]n liefern kann. Zur Lastverteilung bei großen [[Website]]s oder [[IRC-Netzwerk]]en geschieht dies auf mehreren physischen [[Server]]n.

{{Siehe auch|Lastverteilung per DNS}}

=== Beispiel Lastverteilung Routing ===

Routing-Protokolle wie z.&nbsp;B. [[Routing Information Protocol]] (RIP) setzen das Round-Robin-Verfahren zur Lastverteilung auf verschiedene Leitungen (Routen) ein. Routen mit gleicher Knotenmetrik und gleichem Zielnetzwerk werden der Reihe nach zur Paketzustellung belastet. Dies geschieht entweder für jedes weitergeleitete Paket einzeln ''(per packet)'' oder für jeden neuen Zielhost ''(per destination)''.

== Bewertung ==

''Zu den Kriterien, auf denen diese Bewertung basiert, siehe [[Scheduling#Kriterien|Scheduling, Abschnitt „Kriterien“]].''

Round-Robin behandelt alle Prozesse gleich, so dass einerseits kein Prozess unfair behandelt wird oder gar verhungert, es aber andererseits auch nicht möglich ist, Prozesse mit höherer [[Dringlichkeit]] bevorzugt abzuarbeiten. Der Durchsatz dieses Scheduling-Verfahrens ist im Allgemeinen weder besonders niedrig noch besonders hoch. Die Verwendung von Zeitschlitzen fester Länge macht Round-Robin unflexibel.<!-- und führt dazu, dass Ressourcen häufig ungenutzt bleiben. // ? Ein Prozess kann doch auch vorzeitig die Ressource zurückgeben, was soll da denn "ungenutzt" bleiben? -->

== Literatur ==
* {{Literatur |Autor=Peter Mandl |Titel=Grundkurs Betriebssysteme: Architekturen, Betriebsmittelverwaltung, Synchronisation, Prozesskommunikation, Virtualisierung |Auflage=5., aktualisierte Auflage |Verlag=Springer Vieweg |Ort=Wiesbaden [Heidelberg] |Datum=2020 |Reihe=Lehrbuch |ISBN=978-3-658-30546-8 |Seiten=106–108 |Kapitel=5.2.4 |DOI=10.1007/978-3-658-30547-5}}

[[Kategorie:Betriebssystemtheorie]]
[[Kategorie:Algorithmus]]