Round-robin (informatique)
Un article de Wikipédia, l'encyclopédie libre.
  |
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
|
|
|
EDF - Rate-monotonic - Round-robin |
|
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.
[modifier] 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à existant, 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 auras pas de famine (attente infinie)
- un processus qui vient de finir d'utiliser le processeur (quantum écoulé) est placé en fin de liste
- un processus qui a terminé son utilisation immédiate du processeur est sorti de la liste.
Ainsi pour un quantum de temps donné q, un processus attendra au plus n*q ou n est le nombre de processus en attente, pour accéder au processeur.
Quand le processeur choisit un nouveau processus à traîter 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é car l'overhead interviendra plus souvent.
- Un quantum long : le temps de réponse sera allongé et à la limite (quantum infini) cella devient un algorithme FIFO (first in first out) premier arrivé premier servis.
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 que peu de perte d'efficacité.
[modifier] Exemple problématique
Si le quantum est de 4 ms et qu'il faut 1ms pour changer de processus, on perd donc 20% du temps en changement.
Article connexe : ordonnancement de tâches informatiques.[modifier] Réseau
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.
