next up previous index
Next: La synchronisation (communication) de Up: Gestion des Processus. Previous: Un processus.   Index

Subsections

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 "interrompu" interdite
sans réquisition (multiprogrammation).
transition "interrompu" autorisée
avec réquisition (temps partagé).

Les critères d'ordonnancement.

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.

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.

Tourniquet (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 que 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é $N$ à celle de priorité $N+1$.

É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 optimal. (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 en 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 RAM. 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.


\begin{automate}[ct]{400}{150}{Deux niveaux d'ordonnancement}{1}(25,5)
\etat[i]{...
...e E/S}
\trans{trois}{cinq}{exit}
\trans{quatre}{six}{fin E/S}
\par\end{automate}

L'ordonnancement sur plusieurs processeurs.

Le problème est plus complexe, il n'y a pas de solution optimale.


next up previous index
Next: La synchronisation (communication) de Up: Gestion des Processus. Previous: Un processus.   Index
Alain GRIFFAULT
2000-12-22