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.

• 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.

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.

L'ordonnancement sur plusieurs processeurs.

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