Ordonnancement>Ordonnancement de processus>Ordonnancement sous Unix

3 Ordonnancement sous le système Unix

 
 
Les opérations relatives à l' ordonnancement sont réalisées par le système Unix à chaque fois qu'un processus s'apprête à passer du mode système au mode utilisateur, donc à la suite de l'occurrence soit d'une interruption, d'un appel système ou d'une trappe. La politique d'ordonnancement du système Unix est une politique à multiples niveaux de priorité avec quantum de temps. Le noyau recalcule la priorité d'un processus quand il passe du mode noyau au mode utilisateur. Dans une première approche, ce calcul permet une extinction de priorité des processus qui s'exécutent de manière à permettre l'exécution de tous les processus et à éviter les problèmes de famine

3.1 Structures de données liées à l'ordonnancement

 
 
La priorité de chaque processus est codée dans l'entrée de la table des processus qui lui correspond. La plage des priorités des processus est partitionnée en deux sous-ensembles. Chaque ensemble contient plusieurs niveaux de priorités et à chaque niveau de priorité est associé une file d'attente (fig 9) :
Fig 9 : Files de priorités pour l'ordonnancement sous Unix
  • les priorités utilisateurs : ce sont les processus préemptés par l' ordonnanceur au moment de leur retour en mode utilisateur. Un processus qui se réveille quitte la priorité noyau pour réintégrer les priorités utilisateur. La procédure de traitement de l'interruption horloge ajuste les priorités des processus en mode utilisateur toutes les secondes et fait entrer le noyau dans son algorithme d'ordonnancement pour éviter qu'un processus monopolise l'unité centrale
  • les priorités noyau : ce sont des processus endormis en attente d'un événement. La file où le processus s'endort est fonction de l'événement attendu et la priorité correspond à une "préférence" sur les réveils suite à un événement. Un processus endormi en priorité noyau demeure toujours dans la file où il s'est endormi

3.2 Algorithmes d'ordonnancement mis en oeuvre

 
 
L'algorithme mis en œuvre s'appuie sur la routine d'interruption horloge qui fait régulièrement passer le processus en mode noyau. Plus précisément :
  • A chaque interruption horloge, le système incrémente de une unité la valeur du champ "utilisation du processeur" pour le processus élu.
  • Toutes les secondes c'est-à-dire toutes les 50 à 100 interruptions horloge, la valeur du champ "utilisation du processeur" pour tous les processus est divisée par deux. Puis la priorité des processus est recalculée selon la formule suivante : priorité du processus = Utilisation du processeur /2 + (priorité de base du niveau utilisateur) Du fait de ce recalcul des priorités; les processus se déplacent dans les files de priorité
 
Un exemple de mise en œuvre
On considère trois processus A, B et C qui ont chacun une priorité initiale de 60. La priorité de base du niveau utilisateur est également la priorité 60. L'interruption horloge se déclenche 60 fois par seconde. A l'instant 0, le processus A est élu. Chaque seconde, l'interruption horloge survient et le champ "utilisation du processeur " (compte UC sur la figure 10) est incrémenté de une unité. Au bout de 60 secondes (instant t = 1), la priorité des processus est recalculée. Du fait que les processus B et C ne se sont pas encore exécutés leur priorité est inchangée (le compte UC est nul pour ces processus). La priorité du processus A par contre baisse et devient égale à 75 (60 + 30/2). C'est donc le processus B qui est à présent élu. A l'instant 2, de nouveau les priorités sont recalculées. Le compte UC du processus C étant toujours nul , la priorité de ce processus n'est pas modifiée. Les priorités du processus A et B par contre évoluent et deviennent respectivement égales à 67 pour le processus A (60 + 15/2) et à 75 pour le processus B. On voit à présent que le processus A a une priorité qui remonte du fait qu'il n'a pas pu utiliser l'unité centrale. 
Fig 10 : Exemple de mise en œuvre de l'ordonnancement sous Unix
Ordonnancement Ordonnancement de processus Ordonnancement sous Unix