Round-robin (informatique)

Exemple de planification de tâches en round-robin

Le Round-robin (ou tourniquet) est un algorithme d'ordonnancement courant dans les systèmes d'exploitation adapté aux systèmes travaillant en temps partagés.

Une petite unité de temps, appelée quantum de temps, est définie. La file d'attente est gérée comme une file circulaire. L'ordonnanceur parcourt cette file et alloue un temps processeur à chacun des processus pour un intervalle de temps de l'ordre d'un quantum au maximum.

La performance de round-robin dépend fortement du choix du quantum de base.

Système du tourniquet

Le système du tourniquet prend son nom du jeu de parcs pour enfants. L'image pour l'algorithme est que chaque processus est assis sur le tourniquet et, chacun à son tour, ne fait que passer devant le processeur pendant un laps de temps fini.

Formellement on a :

• 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 (N.B. : 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.

Exemple de traitement de 6 tâches arrivant à des moments différents et avec des temps d'exécution variés, réalisé par un ordonnanceur préemptif utilisant la méthode du tourniquet (Round-Robin) avec un quantum de temps de 1ms.

En reprenant l'exemple proposé dans la version anglaise de l'encyclopédie : 6 tâches avec des débuts et des durées d'exécutions différentes et un quantum de temps fixé à 1 ms, vous trouverez ci contre le diagramme de traitement d'un ordonnanceur préemptif utilisant la méthode du tourniquet. Ainsi pour un quantum de temps donné $q$, un processus attendra au plus $n\times q$ 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 sorti.

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 $1/(4+1)$ = 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 $2/(4+2)$ = 33 % du temps (exemple de quantum trop long par rapport au temps d'exécution).

Réseau

Un tourniquet (round-robin en anglais) 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.