ENSI 2012/2013 - Ordonnancement des processus

Ce document présente les principes fondamentaux de l'ordonnancement des processus dans un système d'exploitation multitâche. Il s'adresse aux étudiants en informatique et aux professionnels souhaitant comprendre les différents algorithmes d'ordonnancement, leurs objectifs, leurs avantages et leurs limites.

Introduction à l'ordonnancement des processus

Dans un système d'exploitation, plusieurs processus peuvent être présents en mémoire centrale en attente d'exécution. Lorsque plusieurs processus sont prêts, le système doit gérer l'allocation du processeur entre eux. Cette tâche est assurée par l'ordonnanceur (scheduler), tandis que l'allocateur (dispatcher) réalise l'allocation effective du processeur au processus choisi.

L'ordonnanceur doit résoudre deux problèmes principaux :

• Le choix du processus à exécuter.
• Le temps d'allocation du processeur à ce processus.

Un système multitâche est dit préemptif lorsqu'il peut interrompre un processus pour en exécuter un autre. Il est coopératif lorsque les processus ne sont pas interrompus avant leur terminaison.

Objectifs de l'ordonnanceur

• Assurer que chaque processus en attente reçoive une part de temps processeur.
• Minimiser le temps de réponse.
• Utiliser le processeur à 100%.
• Assurer une utilisation équilibrée des ressources.
• Prendre en compte les priorités des processus.
• Être prédictible.

Ces objectifs peuvent parfois être contradictoires, rendant impossible la création d'un algorithme optimisant tous les critères simultanément.

Ordonnanceurs non préemptifs

Les ordonnanceurs non préemptifs ne retirent pas la ressource processeur à un processus avant sa terminaison. Les principaux algorithmes sont :

• FCFS (First-Come First-Served) : le premier arrivé est le premier servi.
• SJF (Shortest Job First) : exécuter d'abord le processus avec le plus court temps d'exécution.
• Priorité : chaque processus se voit attribuer une priorité.

Algorithme SJF (Shortest Job First)

L'algorithme SJF suppose la connaissance préalable des temps d'exécution. Il exécute en priorité le processus le plus court, ce qui minimise le temps moyen d'exécution.

Algorithme FCFS (First Come First Served)

Chaque processus s'exécute jusqu'à sa terminaison sans interruption. Cet algorithme est simple à implanter mais peu efficace car il ne tient pas compte de l'utilisation du processeur.

Exemple :

Processus	Durée estimée	Date d'arrivée
P1	2	0
P2	4	1
P3	8	1
P4	12	2

Diagramme de Gantt :

P1 P2 P3 P4

0 2 6 14 26

Temps de traitement moyen = [(2 - 0) + (6 - 1) + (14 - 1) + (26 - 2)] / 4 = 35,25

Ordonnanceur par Priorité (non préemptif)

Chaque processus reçoit une priorité, soit statique (fixe), soit dynamique (modifiable). Le processus avec la plus grande priorité est exécuté en premier.

Problème de famine : un processus de faible priorité peut ne jamais s'exécuter si des processus plus prioritaires arrivent constamment.

Pour éviter cela, on peut recalculer périodiquement les priorités afin de permettre à tous les processus d'être servis.

Ordonnanceurs préemptifs

Ces ordonnanceurs peuvent interrompre un processus pour en exécuter un autre. Les principaux algorithmes sont :

• Round Robin (RR)
• Tourniquet avec priorités
• SRTF (Shortest Remaining Time First)

Round Robin (RR)

Chaque processus s'exécute pendant un quantum de temps Q. Si le processus n'a pas terminé à la fin de ce quantum, il est replacé en fin de file d'attente et le processeur passe au processus suivant.

Exemple :

Processus	Durée	Arrivée
P1	3	0
P2	4	1
P3	2	2
P4	3	3
P5	3	4
P6	5	5
P7	4	6
P8	2	7

Quantum Q = 2 unités.

Diagramme de Gantt :

P1 P2 P3 P4 P5 P6 P7 P8 P1 P2 P4 P5 P6 P7 P6

0 2 4 6 8 10 12 14 16 17 19 20 21 26 25

Temps de traitement moyen = [(17-0) + (19-1) + (6-2) + (20-3) + (21-4) + (26-5) + (25-6) + (16-7)] / 8 = 15,25

Le réglage du quantum est crucial :

• Quantum trop petit : trop de commutations, coût élevé en changement de contexte.
• Quantum trop grand : temps de réponse augmenté, RR se rapproche de FCFS.

Tourniquet avec priorités

Le système utilise plusieurs files d'attente (FA) avec différents niveaux de priorité et différents quanta de temps.

• À son arrivée, un processus est placé dans la file la plus prioritaire FA0.
• Si un processus épuise son quantum dans FAi, il est déplacé dans la file FAi+1 de priorité inférieure.
• Une file FAi ne peut être servie que si toutes les files FAj de priorité supérieure (j < i) sont vides.
• Un processus qui traverse toutes les files sans terminer reste dans la file la moins prioritaire.

Algorithme SRTF (Shortest Remaining Time First)

Version préemptive de SJF. Le processus choisi est celui dont le temps d'exécution restant est le plus court. Un nouveau processus arrivant avec un temps restant plus court peut provoquer la réquisition du processeur.

Exemple :

Processus	Durée estimée	Date d'arrivée
P1	8	0
P2	5	2
P3	5	3
P4	2	4

Diagramme de Gantt :

P1 (0-2) → P2 (2-4) → P4 (4-6) → P2 (6-9) → P3 (9-14) → P1 (14-20)

Temps de traitement moyen = [(20 - 0) + (9 - 2) + (14 - 3) + (6 - 4)] / 4 = 9,5

SRTF minimise théoriquement le temps d'attente moyen, mais il est difficile de prédire l'arrivée future des processus.

Hiérarchie d’ordonnancement

Les processus prêts ne sont pas toujours tous en mémoire centrale. Ceux sur disque prennent plus de temps à être chargés.

On distingue :

• Ordonnancement à court terme : gère les processus prêts en mémoire centrale.
• Ordonnancement à long terme : gère le swapping des processus entre disque et RAM.

Les systèmes multi-niveaux utilisent plusieurs files d'attente (FA) avec priorités :

• Files d'attente sans liens : un processus reste dans sa file jusqu'à sa terminaison.
• Files d'attente avec liens : un processus peut migrer entre files selon son comportement et son temps d'exécution.

Chaque file d'attente peut avoir son propre algorithme d'ordonnancement (ex. RR pour les files basses, FCFS pour les files hautes).

Ordonnancement des threads

• Local Scheduling : la bibliothèque de threads décide quel thread utilisateur exécuter dans un processus.
• Global Scheduling : le noyau décide quel thread noyau exécuter.

Exemples d’ordonnancement dans les systèmes

• Unix : multi-niveaux avec plusieurs politiques adaptatives.
• Linux : multi-niveaux avec trois niveaux principaux :
  • Realtime FIFO
  • Realtime Round Robin
  • Timesharing
• Windows Vista : politique à deux dimensions de priorité :
  • Classe des processus prioritaires (Real-time, High, Above Normal, Normal, Below Normal, Idle)
  • Priorités relatives des threads dans chaque classe

Glossaire des termes clés

• Ordonnanceur (Scheduler) : composant du système d'exploitation qui choisit quel processus exécuter.
• Allocateur (Dispatcher) : composant qui réalise l'allocation effective du processeur au processus choisi.
• Préemption : interruption d'un processus en cours pour en exécuter un autre.
• FCFS (First Come First Served) : algorithme où le premier processus arrivé est le premier servi.
• SJF (Shortest Job First) : algorithme qui exécute en priorité le processus avec le plus court temps d'exécution.
• Round Robin (RR) : algorithme préemptif où chaque processus s'exécute pendant un quantum de temps fixe.
• SRTF (Shortest Remaining Time First) : version préemptive de SJF, choisissant le processus avec le plus court temps restant.
• Quantum : durée maximale d'exécution allouée à un processus dans un algorithme Round Robin.
• File d'attente (FA) : structure de données utilisée pour gérer les processus selon leur priorité.
• Swapping : transfert des processus entre la mémoire centrale et le disque.
• Temps de traitement moyen : moyenne des temps entre l'arrivée et la fin d'exécution des processus.

Points clés à retenir

• L'ordonnancement vise à équilibrer l'utilisation du processeur, la réactivité et la justice entre processus.
• Les algorithmes non préemptifs sont simples mais peuvent être inefficaces dans un environnement multitâche.
• Les algorithmes préemptifs comme Round Robin et SRTF permettent une meilleure réactivité mais nécessitent une gestion plus complexe.
• Le choix du quantum dans Round Robin est crucial pour la performance globale.
• Les systèmes modernes utilisent des hiérarchies multi-niveaux pour combiner plusieurs stratégies d'ordonnancement.
• La gestion des threads ajoute une couche supplémentaire d'ordonnancement au sein des processus.