Qu’est-ce que l’ordonnancement Round-Robin ?
Le nom de cet algorithme vient du principe du round-robin, où chaque personne obtient une part égale de quelque chose à tour de rôle. C’est l’algorithme d’ordonnancement le plus ancien et le plus simple, qui est surtout utilisé pour le multitâche.
Dans l’ordonnancement round-robin, chaque tâche prête s’exécute tour à tour uniquement dans une file d’attente cyclique pour une tranche de temps limitée. Cet algorithme offre également une exécution sans famine des processus.
Dans ce tutoriel sur les systèmes d’exploitation, vous apprendrez :
- Qu’est-ce que l’ordonnancement Round-Robin ?
- Caractéristiques de l’ordonnancement round-robin
- Exemple d’ordonnancement round-robin
- Avantage de l’ordonnancement round-robin
- Inconvénients de l’ordonnancement round-robin
- Latence dans le pire des cas
Caractéristiques de l’ordonnancement round-robin
Voici les caractéristiques importantes de l’ordonnancement round-robin :
- Le round robin est un algorithme préemptif
- L’unité centrale de traitement est transférée au processus suivant après un intervalle de temps fixe, qui est appelé quantum de temps/tranche de temps.
- Le processus qui est préempté est ajouté à la fin de la file d’attente.
- Le round robin est un modèle hybride qui est piloté par l’horloge
- La tranche de temps doit être minimale, qui est attribuée pour une tâche spécifique qui doit être traitée. Cependant, il peut différer d’un OS à l’autre.
- C’est un algorithme en temps réel qui répond à l’événement dans une limite de temps spécifique.
- Le round robin est l’un des algorithmes les plus anciens, les plus justes et les plus faciles.
- Méthode d’ordonnancement largement utilisée dans les OS traditionnels.
Exemple de Round-robin Scheduling
Considérons les trois processus suivants
| File de processus | Temps de rafale |
| P1 | 4. |
| P2 | 3 |
| P3 | 5 |
Etape 1) L’exécution commence avec le processus P1, qui a un temps de rafale de 4. Ici, chaque processus s’exécute pendant 2 secondes. P2 et P3 sont toujours dans la file d’attente.
Étape 2) Au temps =2, P1 est ajouté à la fin de la file d’attente et P2 commence à s’exécuter
Étape 3) Au temps=4 , P2 est préempté et ajouté à la fin de la file d’attente. P3 commence à s’exécuter.
Etape 4) Au temps=6 , P3 est préempté et ajouté à la fin de la queue. P1 commence à s’exécuter.
Étape 5) Au temps=8 , P1 a un temps de rafale de 4. Il a terminé son exécution. P2 commence l’exécution
Étape 6) P2 a un temps de rafale de 3. Il a déjà exécuté pendant 2 intervalles. Au temps=9, P2 termine son exécution. Ensuite, P3 commence son exécution jusqu’à ce qu’elle soit terminée.
Étape 7) Calculons le temps d’attente moyen pour l’exemple ci-dessus.
Wait time P1= 0+ 4= 4P2= 2+4= 6P3= 4+3= 7
Avantage de l’ordonnancement Round-robin
Voici, les avantages/avantages de la méthode d’ordonnancement Round-robin :
- Elle ne fait pas face aux problèmes de famine ou d’effet de convoi.
- Tous les travaux obtiennent une allocation équitable du CPU.
- Elle traite tous les processus sans aucune priorité.
- Si vous connaissez le nombre total de processus sur la file d’attente d’exécution, alors vous pouvez également supposer le pire cas de temps de réponse pour le même processus.
- Cette méthode d’ordonnancement ne dépend pas du temps de rafale. C’est pourquoi elle est facilement implémentable sur le système.
- Une fois qu’un processus est exécuté pour un ensemble spécifique de la période, le processus est préempté, et un autre processus s’exécute pour cette période de temps donnée.
- Permet à l’OS d’utiliser la méthode de commutation de contexte pour sauvegarder les états des processus préemptés.
- Elle donne les meilleures performances en termes de temps de réponse moyen.
Inconvénients de l’ordonnancement Round-robin
Voici, les inconvénients/cons de l’utilisation de l’ordonnancement Round-robin :
- Si le temps de tranchage de l’OS est faible, le rendement du processeur sera réduit.
- Cette méthode passe plus de temps sur la commutation de contexte
- Ses performances dépendent fortement du quantum de temps.
- Les priorités ne peuvent pas être définies pour les processus.
- L’ordonnancement round-robin ne donne pas de priorité spéciale aux tâches plus importantes.
- Diminue la compréhension
- Un quantum de temps plus faible entraîne une augmentation de la surcharge de commutation de contexte dans le système.
- Trouver un quantum de temps correct est une tâche assez difficile dans ce système.
Latence du pire cas
Ce terme est utilisé pour le temps maximum pris pour l’exécution de toutes les tâches.
- dt = Dénote le temps de détection lorsqu’une tâche est amenée dans la liste
- st = Dénote le temps de commutation d’une tâche à une autre
- et = Dénote le temps d’exécution de la tâche
Formule :
Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISRt,SR = sum of all execution times
Summary:
- Le nom de cet algorithme vient du principe du round-robin, où chaque personne obtient une part égale de quelque chose à tour de rôle.
- Le round robin est l’un des algorithmes les plus anciens, les plus équitables et les plus faciles à mettre en œuvre, ainsi que des méthodes d’ordonnancement largement utilisées dans les OS traditionnels.
- Le round robin est un algorithme préemptif
- Le plus grand avantage de la méthode d’ordonnancement round-robin est que Si vous connaissez le nombre total de processus sur la file d’attente d’exécution, alors vous pouvez également supposer le pire cas de temps de réponse pour le même processus.
- Cette méthode passe plus de temps sur la commutation de contexte
- La latence du pire cas est un terme utilisé pour le temps maximum pris pour l’exécution de toutes les tâches.