L'ordonnancement ou Scheduling
Les bases de l'ordonnancement
Principe
Du fait de la possibilité d'avoir plusieurs utilisateurs sur un serveur Unix et de la possibilité pour chacun de ces utilisateurs de lancer plusieurs processus, Unix est depuis toujours un système en temps partagé. Les differents utilisateurs ont ainsi l'illusion de disposer entièrement des ressources de la machine.
Comme chaque utilisateur n'a pas le ou les cpus pour lui seul, il a fallu utiliser un algorithme permettant de passer d'un processus à un autre sans devoir attendre la fin du processus et tout en conservant le contexte de celui-ci pour pouvoir continuer son exécution par la suite.
L'algorithme de sheduling choisi est l'algorithme dit du tourniquet (round robin) qui favorise l'exécution de programme court et intéractif et non les traitements par lots (batch).
Le système passe par le sheduler pour connaître le processus à exécuter. Celui-ci pour s'y retrouver utilise deux queues:
- Une queue d'élection (run queue), on trouvera dedans tous les processus prêt à exécuter une instruction. De plus, chaque processus se voit attribuer un niveau de priorité (recalculer cycliquement). Dès que le mécanisme des priorités lui permet de devenir le meilleur candidat à l'acquisition du CPU càd qu'il a la plus grande priorité pour l'exécution, alors le processus pourra s'exécuter mais durant une certaine période. En effet, le temps d'exécution est découpé en tranches ou quantum ou quotas (time slice)). Lorsque son quotas de temps est écoulé, le sheduler le remettra (préempté) dans la queue d'élection. Il arrive qu'un processus n'utilise pas entièrement son quotas de temps. ceci se produit lorsqu'il demande lui-même l'attente d'un évènement...le processus va alors s'endormir.
- Une queue des processus endormis (sleep queue). Ce sont les processus qui se bloquent pour attendre un évènement. Comme par exemple un processus attendant qu'un utilisateur tape un caractère au clavier. Dans ce cas, le processus ne sera plus exécuté jusqu'à ce qu'une interruption du clavier indique au système qu'il faut "réveiller" le dit processus pour que celui-ci interprète le caractère reçu.
Non-préemption
du noyau:
Le noyau standard d'UNIX est non préemptif. Les appels systèmes, trappe, interruption ne sont donc pas interruptible.
Quelques définitions
Quantum de temps (time slice): Egalement appelé cycle majeur. Le quantum est dans l'intervalle 0 à 1 seconde. Il s'agit du temps maximum qui sera donné à un processus avant que le sheduler ne donne la main à un autre traitement.
Horloge (clock):Servira a envoyer de manière régulière
des interruptions pour piloter le système. Ces interruptions sont envoyés
à un rythme régulier. Ces tops sont les cycles mineurs(minor cycle
ou tick) par rapport au quantum.
A chaque top d'horloge, le noyau effectue un certain nombre d'opérations
comme la collecte des statistiques nécessaires pour la comptabilité(accounting),
le calcul des priorités, les temporisations. On peut donc résumer
les principales fonctions de l'horloge :
- Scheduling (calcul des priorités…).
- Gestion du temps système.
- Exécution de fonctions particulières après un certain
nombre de tops d'horloge (fonctions appelées à partir d'une table
interne appelée : " callout table ".
- Statistiques de comptabilité.
- Signaux d'alarme au compte des processus les ayant demandés pour déclencher
des traitements particuliers.
- Temps consommé en mode utilisateur/système et dans l'exécution
de sous-programmes particuliers (profiling).
- ...
Priorités: Pour chaque processus, la table des processus contient
sa priorité : plus la valeur est faible, plus la priorité est
grande. On classe les priorités en priorités système et
en priorités utilisateur.
- Priorités système
Ces priorités non recalculées au cours d'un quantum vont de 0
à 39. Ce sont les priorités du mode système (mode noyau).
Par ailleurs, celle qui vont de 0 à 25 ou de 0 à PZERO (désignation
de la limite 25) sont insensibles aux signaux. Ce sera le cas si un processus
s'endort avec une priorité <= PZERO.
- Priorités utilisateur
Elles vont de 40 à 119 et son recalculées à chaque cycle
majeur. Ces priorités sont affectées aux processus lorsqu'ils
s'exécutent en mode utilisateur, selon le principe du tourniqué
déjà énoncé.
Remarques
:
Un processus en mode utilisateur ne peut avoir une priorité système ; alors qu'un processus en mode système peut très bien avoir une priorité utilisateur. Le système priorité étudié est celui du système V.
Commutation de processus
La commutation de processus ou changement de contexte se produit lorsque le sheduler sélectionne un autre processus pour l'exécution. Le contexte machine du processus précédent est sauvegardé pour permettre une reprise lors de sa prochaine élection.
Les cas de changement de contexte sont les suivants :
- Le processus se bloque (sleep) pour attendre un événement particulier
ou une ressource.
- Le processus se termine (exit).
- Le processus sort d'un appel système (passage du mode système
(mode noyau) au mode utilisateur).
- Le processus sort d'une interruption.
- Le processus a épuisé son quantum.
Etats d'un processus
Au cours de sa vie, un processus passe par différents états
; les transitions entre ces différents états sont assurées
par l'émission de signaux aux processus concernés. Ces états
ainsi que les flags indiquent le lieu où se trouve le processus dans
le système sont indiqués dans le fichier /usr/include/sys/proc.h.
Les états de base sont :
· SSLEEP : état endormi dans l'attente d'un événement
qui peut être l'attente d'une ressource non disponible, l'attente de la
mort d'un fils, etc.
· SWAIT : état abandonné (processus en mode trace stoppé
par exemple et processus père terminé).
· SRUN : processus actif ou prêt à tourner dès que
le CPU lui est attribué.
· SIDL : état intermédiaire d'un processus nouvellement
créé.
· SZOMB : processus zombie, le père n'a pas encore exécuté
le wait ou ne l'exécutera pas alors que le fils est terminé.
· SSTOP : processus en mode trace arrêté
Les flags indiquant le " lieu du processus " sont :
· SLOAD : processus en mémoire centrale
· SLOCK : processus non swappable
· SSWAP : processus en train d'être swappé
· SSEL : processus en train d'être élu
· Etc…