Next: La synchronisation (communication) de Up: Gestion des Processus.
Previous: Un
processus. Index
Subsections
Les types d’ordonnancements.
Les critères d’ordonnancement.
Les différentes phases de l’ordonnancement.
o le bloc de contrôle d’un processus
o la table des processus et les files d’attentes
o la commutation de l’UC entre processus
Les algorithmes d’ordonnancement.
L’ordonnancement à plusieurs niveaux.
L’ordonnancement sur plusieurs processeurs.
L’ordonnancement de processus.
Les types d’ordonnancements.
Ils sont distingués suivant les transitions permises dans le graphe d’état d’un processus.
transition « interrompue » interdite
sans réquisition (multiprogrammation).
transition « interrompue » autorisée
avec réquisition (temps partagé).
Les critères d’ordonnancement.
l’utilisation maximale de l’UC.
la capacité de traitement maximale.
l’utilisation maximale des périphériques.
la diminution du temps moyen de restitution : le temps mis par un processus pour aller de
l’état ''nouveau'' à l’état ''terminé''.
la diminution du temps moyen d’attente : le temps passé dans l’état ''prêt''.
la diminution du temps moyen de réponse : dans un processus interactif, le temps entre une
fin d’entrée et le début d’une sortie de résultat (pas la fin). C’est une mesure de ''réactivité''.
l’équité.
Les objectifs sont contradictoires, il faut des compromis.
Les différentes phases de l’ordonnancement.
le bloc de contrôle d’un processus
Il contient toute l’information nécessaire pour qu’un processus lors d’une reprise se comporte
comme s’il n’avait pas été interrompu.
l’état du processus,
le compteur d’instructions,
les registres de l’UC,
des informations pour l’ordonnanceur (priorité, ...),
des informations pour la gestion mémoire (valeur des registres base et limite, les tables de
pages et/ou de segments ...),
des informations de comptabilisation (temps processeur écoulé, temps réel écoulé, numéros
des processus fils ...),
des informations sur les E/S (liste des périphériques alloués, liste des fichiers ouverts ...).
la table des processus et les files d’attentes
C’est une structure de stockage pour l’ensemble des blocs de contrôle.
la commutation de l’UC entre processus
Les algorithmes d’ordonnancement.
FIFO.
Utilisation maximale de l’UC. Équitable.
Garrot (Round Robin).
Un paramètre supplémentaire : le quantum (une durée) qui permet d’interrompre un processus en
cours d’exécution si sa prochaine E/S est trop éloignée dans le temps (supérieur au quantum).
Équitable. Utilisation de l’UC et temps moyen de réponse dépendent du quantum. Une grande valeur
de quantum favorise les processus de type calculs, tandis qu’une petite valeur favorise les E/S, donc
les processus interactifs.
Tourniquet avec priorités statiques.
Chaque processus possède une priorité, et chaque priorité possède son propre quantum : grand pour
les faibles priorités, et petit pour les hautes priorités. Généralement, les processus de calculs sont de
faible priorité et les processus interactifs de grande priorité.
Non équitable. Utilisation de l’UC et temps moyen de réponse peuvent être bons.
Tourniquet avec priorités dynamiques.
Un paramètre supplémentaire (une durée, un nombre d’interruptions) qui permet de faire passer les
processus de la file d’attente de priorité à celle de priorité .
Équitable. Utilisation de l’UC et temps moyen de réponse sont bons. Diverses stratégies pour la
gestion des priorités. Généralement, après une interruption, un processus réintègre la file d’attente
correspondante à sa priorité initiale.
PCTE (plus court temps d’exécution).
Non équitable. Temps moyen de restitution optimale. (analogie avec la file d’attente à une caisse de
grande surface, où une règle de politesse est de laisser passer quelqu’un qui a peu d’objets si l’on a
un plein caddie).
Exemple : deux tâches (A d’une durée de 5 minutes, et B de 30 secondes). A puis B donne un temps
moyen de 5 minutes et 15 secondes, alors que B puis A donne seulement 3 minutes.
Implémentable dans les SGBD, mais pas dans un SE généraliste, car le temps du prochain cycle
d’exécution n’est pas connu.
Une implémentation est possible en utilisant une fonction d’estimation du temps du prochain cycle.
Par exemple t= a * t + b * te. (t : estimation, te : temps effectif, a+b=1).
PCTER (Plus Court Temps d'Exécution Restant).
Une variante du précédent. Il y à réquisition pour un nouveau processus dont le temps d’exécution
serait plus court que celui ''restant'' du processus en cours.
L’ordonnancement à plusieurs niveaux.
L’ensemble des processus prêts est souvent trop important pour tenir fr RAM. Certains sont donc sur
disque. Un processus élu qui est sur disque prend beaucoup plus de temps qu’un processus en RAM
pour être chargé dans l’UC.
Le processus élu est donc toujours pris parmi ceux en BÉLIER. L’algorithme est alors non équitable.
La solution consiste à utiliser un deuxième algorithme d’ordonnancement pour gérer les
déplacements des processus prêts entre le disque et la RAM.
L’ordonnancement sur plusieurs processeurs.
Le problème est plus complexe, il n’y a pas de solution optimale.
Next : La synchronisation (communication) de Up : Gestion des Processus. Précédent : Un
processus. Index
Alain GRIFFAULT
2000-12-22
