Accueil🇫🇷Chercher

Round-robin (informatique)

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

Exemple de planification de tâches en round-robin

Une petite unité de temps, appelé 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.
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é à 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é , un processus attendra au plus où 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 ms et qu'il faut 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 ms et que le processus met ms Ă  s'exĂ©cuter, on perd = 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.

Notes et références

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.