Algorithme de planification Round Robin avec exemple

Qu’est-ce que la planification à tour de rôle ?

Le nom de cet algorithme vient du principe du round-robin, selon lequel chaque personne reçoit à tour de rôle une part égale de quelque chose. Il s’agit de l’algorithme de planification le plus ancien et le plus simple, principalement utilisé pour le multitâche.

Dans la planification Round-robin, chaque tâche prête s'exécute tour à tour uniquement dans une file d'attente cyclique pendant une tranche de temps limitée. Cet algorithme offre également une exécution de processus sans famine.

Caractéristiques de la planification à tour de rôle

Voici les caractéristiques importantes de la planification Round-Robin :

  • Le round robin est un algorithme préemptif
  • Le processeur passe au processus suivant après un intervalle de temps fixe, appelé quantum de temps/tranche de temps.
  • Le processus préempté est ajouté à la fin de la file d’attente.
  • Le round robin est un modèle hybride piloté par une horloge
  • La tranche de temps doit être minimale et attribuée à une tâche spécifique qui doit être traitée. Cependant, cela peut différer d’un système d’exploitation à l’autre.
  • Il s'agit d'un algorithme en temps réel qui répond à l'événement dans un délai précis.
  • Le round robin est l’un des algorithmes les plus anciens, les plus équitables et les plus simples.
  • Méthode de planification largement utilisée dans les systèmes d’exploitation traditionnels.

Exemple de planification à tour de rôle

Considérez ceci en suivant trois processus

File d'attente de processus Temps de rafale
P1 4
P2 3
P3 5

Planification à tour de rôle

Étape 1) L'exécution commence par 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.

Planification à tour de rôle

Étape 2) Au temps =2, P1 est ajouté à la fin de la file d'attente et P2 commence à s'exécuter

Planification à tour de rôle


Étape 3) À time=4 , P2 est préempté et ajouté à la fin de la file d'attente. P3 commence à s'exécuter.

Planification à tour de rôle

Étape 4) À time=6 , P3 est préempté et ajouté à la fin de la file d'attente. P1 commence à s'exécuter.

Planification à tour de rôle

Étape 5) À time=8 , P1 a un temps de rafale de 4. Son exécution est terminée. P2 commence l'exécution

Planification à tour de rôle

Étape 6) P2 a un temps de rafale de 3. Il s'est déjà exécuté pendant 2 intervalles. Au temps = 9, P2 termine l'exécution. Ensuite, P3 commence l’exécution jusqu’à la fin.

Planification à tour de rôle

Étape 7) Calculons le temps d'attente moyen pour l'exemple ci-dessus.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

Avantage de la planification à tour de rôle

Voici les avantages/avantages de la méthode de planification Round-robin :

  • Il n’est pas confronté aux problèmes de famine ou d’effet de convoi.
  • Tous les travaux bénéficient d'une allocation équitable de CPU.
  • Il traite tous les processus sans aucune priorité
  • Si vous connaissez le nombre total de processus dans la file d'attente d'exécution, vous pouvez également supposer le temps de réponse le plus défavorable pour le même processus.
  • Cette méthode de planification ne dépend pas du temps de rafale. C'est pourquoi il est facilement implémentable sur le système.
  • Une fois qu'un processus est exécuté pendant une période spécifique, le processus est préempté et un autre processus s'exécute pendant cette période donnée.
  • Permet au système d'exploitation d'utiliser la méthode de changement de contexte pour enregistrer les états des processus préemptés.
  • Il offre les meilleures performances en termes de temps de réponse moyen.

Inconvénients de la planification à tour de rôle

Voici les inconvénients/inconvénients de l’utilisation de la planification Round-robin :

  • Si le temps de découpage du système d’exploitation est faible, la sortie du processeur sera réduite.
  • Cette méthode passe plus de temps sur le changement de contexte
  • Sa performance dépend fortement du quantum de temps.
  • Des priorités ne peuvent pas être définies pour les processus.
  • La planification à tour de rôle n'accorde pas de priorité particulière aux tâches les plus importantes.
  • Diminue la compréhension
  • Un quantum de temps plus faible entraîne une surcharge de changement de contexte plus élevée dans le système.
  • Trouver un quantum de temps correct est une tâche assez difficile dans ce système.

Dans le pire des cas

Ce terme est utilisé pour désigner le temps maximum nécessaire à l'exécution de toutes les tâches.

  • dt = Désigne le temps de détection lorsqu'une tâche est introduite dans la liste
  • st = Désigne le temps de passage d'une tâche à une autre
  • et = Désigne 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} + tISR	
t,SR = sum of all execution times

Résumé

  • Le nom de cet algorithme vient du principe du round-robin, selon lequel chaque personne reçoit à tour de rôle une part égale de quelque chose.
  • Le round robin est l'un des algorithmes les plus anciens, les plus équitables et les plus simples, ainsi que des méthodes de planification largement utilisées dans les systèmes traditionnels. OS.
  • Le round robin est un algorithme préemptif
  • Le plus grand avantage de la méthode de planification à tour de rôle est que si vous connaissez le nombre total de processus dans la file d'attente d'exécution, vous pouvez également supposer le temps de réponse le plus défavorable pour le même processus.
  • Cette méthode passe plus de temps sur le changement de contexte
  • La latence dans le pire des cas est un terme utilisé pour désigner le temps maximum nécessaire à l'exécution de toutes les tâches.