Round-robin (informatique)

Pour les articles homonymes, voir Round-robin et RR.

Round-robin (RR) est un algorithme d'ordonnancement courant dans les systèmes d'exploitation. Ce dernier attribue des tranches de temps à chaque processus en proportion égale, sans accorder de priorité aux processus.

Système round-robin

Le round-robin est un jeu de parcs : un tourniquet. C'est l'idée intuitive derrière l'algorithme, chaque processus est sur le tourniquet et ne fait que passer devant le processeur, a son tour et pendant un temps fini.

Plus formellement :

• un nouveau processus est ajouté en fin de liste (pour ne pas doubler des processus déjà existants, ce qui pourrait créer une possibilité de famine),
• l'utilisation par un processus du processeur ne peut pas dépasser un certain quantum de temps ce qui nous assure de nouveau qu'il n'y aura pas de famine,
• l'attente maximum est donnée par la multiplication du nombre de processus en cours multiplié par le quantum de temps accordé à chaque processus (NB : Chaque processus dispose du même quantum de temps que les autres),
• un processus qui vient de finir d'utiliser le processeur (quantum écoulé) est placé en fin de liste,
• un processus qui a terminé son travail est sorti de la liste, par conséquent le temps d'attente pour les autres processus diminue.

Ainsi pour un quantum de temps donné q, un processus attendra au plus où n est le nombre de processus en attente, pour accéder au processeur.

Quand le processeur choisit un nouveau processus à traiter et le charge, cela prend du temps. Il faut donc trouver le juste milieu entre :

• Un quantum court : changements de processus réguliers donc perte d'efficacité (overhead) car la commutation de contexte interviendra plus souvent.
• Un quantum long : le temps de réponse sera allongé et à la limite (quantum infini), cela devient un algorithme FIFO (first in first out) premier arrivé premier servi.

En général le quantum de temps est défini en fonction du comportement statistique des processus. L'idée est de définir un quantum de temps qui fait que les processus vont à 80 % finir leur utilisation du processeur avant la fin du quantum de temps. Ainsi il n'y a que peu de perte d'efficacité.

Exemple problématique

Si le quantum est de 4 ms et qu'il faut 1 ms pour changer de processus, on perd donc 20 % du temps en changement (exemple de quantum trop court par rapport au temps de chargement).

Si le quantum est de 4 ms et que le processus met 2 ms à s'exécuter, on perd 50 % du temps (exemple de quantum trop long par rapport au temps d'exécution).

Réseau

Un Round-robin est une répartition de charge (load balancing) équitable entre serveurs d'une ferme informatique (cluster). Chaque serveur traite le même nombre de requêtes. Cela nécessite une ferme de serveurs homogènes en capacité de traitement. Cette répartition de charge peut être effectuée par le serveur DNS (Domain Name System) qui associe plusieurs adresses IP à un nom de domaine. On parle alors de DNS Round Robin.

• Portail de l’informatique
• Portail de l’algorithmique
• Portail de la programmation informatique