Algorithmes de planification du système d'exploitation

Un planificateur de processus planifie différents processus à affecter à la CPU en fonction d'algorithmes de planification particuliers. Il existe six algorithmes d'ordonnancement de processus populaires dont nous allons discuter dans ce chapitre -

  • Planification du premier arrivé, premier servi (FCFS)
  • Planification SJN (Shortest-Job-Next)
  • Planification prioritaire
  • Temps restant le plus court
  • Programmation à la ronde (RR)
  • Planification de files d'attente à plusieurs niveaux

Ces algorithmes sont soit non-preemptive or preemptive. Les algorithmes non préemptifs sont conçus de sorte qu'une fois qu'un processus entre dans l'état en cours d'exécution, il ne peut pas être préempté jusqu'à ce qu'il ait terminé son temps alloué, tandis que la planification préventive est basée sur la priorité où un planificateur peut préempter un processus en cours d'exécution de faible priorité à tout moment lorsqu'une priorité élevée le processus entre dans un état prêt.

Premier arrivé, premier servi (FCFS)

  • Les travaux sont exécutés sur la base du premier arrivé, premier servi.
  • Il s'agit d'un algorithme d'ordonnancement non préemptif et préemptif.
  • Facile à comprendre et à mettre en œuvre.
  • Son implémentation est basée sur la file d'attente FIFO.
  • Mauvaise performance car le temps d'attente moyen est élevé.

Wait time de chaque processus est comme suit -

Processus Temps d'attente: temps de service - heure d'arrivée
P0 0 - 0 = 0
P1 5 - 1 = 4
P2 8 - 2 = 6
P3 16 - 3 = 13

Temps d'attente moyen: (0 + 4 + 6 + 13) / 4 = 5,75

Travail le plus court ensuite (SJN)

  • Ceci est également connu comme shortest job first, ou SJF

  • Il s'agit d'un algorithme de planification non préemptif et préemptif.

  • Meilleure approche pour minimiser le temps d'attente.

  • Facile à mettre en œuvre dans les systèmes Batch où le temps CPU requis est connu à l'avance.

  • Impossible d'implémenter dans des systèmes interactifs où le temps CPU requis n'est pas connu.

  • Le transformateur doit savoir à l'avance combien de temps le processus prendra.

Données: tableau des processus, et leur heure d'arrivée, temps d'exécution

Processus Heure d'arrivée Temps d'exécution Temps de service
P0 0 5 0
P1 1 3 5
P2 2 8 14
P3 3 6 8

Waiting time de chaque processus est comme suit -

Processus Temps d'attente
P0 0 - 0 = 0
P1 5 - 1 = 4
P2 14 - 2 = 12
P3 8 - 3 = 5

Temps d'attente moyen: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25

Planification basée sur la priorité

  • La planification prioritaire est un algorithme non préemptif et l'un des algorithmes de planification les plus courants dans les systèmes par lots.

  • Chaque processus se voit attribuer une priorité. Le processus avec la priorité la plus élevée doit être exécuté en premier et ainsi de suite.

  • Les processus ayant la même priorité sont exécutés sur la base du premier arrivé, premier servi.

  • La priorité peut être décidée en fonction des besoins en mémoire, des besoins en temps ou de tout autre besoin en ressources.

Données: Tableau des processus, et leur heure d'arrivée, heure d'exécution et priorité. Ici, nous considérons que 1 est la priorité la plus basse.

Processus Heure d'arrivée Temps d'exécution Priorité Temps de service
P0 0 5 1 0
P1 1 3 2 11
P2 2 8 1 14
P3 3 6 3 5

Waiting time de chaque processus est comme suit -

Processus Temps d'attente
P0 0 - 0 = 0
P1 11 - 1 = 10
P2 14 - 2 = 12
P3 5 - 3 = 2

Temps d'attente moyen: (0 + 10 + 12 + 2) / 4 = 24/4 = 6

Temps restant le plus court

  • Le temps restant le plus court (SRT) est la version préemptive de l'algorithme SJN.

  • Le processeur est alloué au travail le plus proche de l'achèvement, mais il peut être préempté par un travail prêt plus récent avec un délai d'exécution plus court.

  • Impossible d'implémenter dans des systèmes interactifs où le temps CPU requis n'est pas connu.

  • Il est souvent utilisé dans les environnements par lots où les travaux courts doivent donner la préférence.

Planification à la ronde

  • Round Robin est l'algorithme de planification de processus préemptif.

  • Chaque processus reçoit un temps fixe pour s'exécuter, il est appelé un quantum.

  • Une fois qu'un processus est exécuté pendant une période donnée, il est préempté et un autre processus s'exécute pendant une période donnée.

  • La commutation de contexte est utilisée pour enregistrer les états des processus préemptés.

Wait time de chaque processus est comme suit -

Processus Temps d'attente: temps de service - heure d'arrivée
P0 (0 - 0) + (12 - 3) = 9
P1 (3 - 1) = 2
P2 (6 - 2) + (14 - 9) + (20 - 17) = 12
P3 (9 - 3) + (17 - 12) = 11

Temps d'attente moyen: (9 + 2 + 12 + 11) / 4 = 8,5

Planification de files d'attente à plusieurs niveaux

Les files d'attente à plusieurs niveaux ne sont pas un algorithme de planification indépendant. Ils utilisent d'autres algorithmes existants pour regrouper et planifier des tâches ayant des caractéristiques communes.

  • Plusieurs files d'attente sont conservées pour les processus ayant des caractéristiques communes.
  • Chaque file d'attente peut avoir ses propres algorithmes de planification.
  • Des priorités sont attribuées à chaque file d'attente.

Par exemple, les travaux liés au processeur peuvent être planifiés dans une file d'attente et tous les travaux liés aux E / S dans une autre file d'attente. Le planificateur de processus sélectionne ensuite alternativement les travaux dans chaque file d'attente et les attribue au processeur en fonction de l'algorithme affecté à la file d'attente.