ENSI 2012/2013 - Ordonnancement des processus
ENSI 2012/2013 - Ordonnancement des processus
Ordonnancement des processus, systèmes d'exploitation, programmation · course
Fiche de révisionFiche de cours
Rédigée à partir de ce document, puis vérifiée avant publication.
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.
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 :
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.
Ces objectifs peuvent parfois être contradictoires, rendant impossible la création d'un algorithme optimisant tous les critères simultanément.
Les ordonnanceurs non préemptifs ne retirent pas la ressource processeur à un processus avant sa terminaison. Les principaux algorithmes sont :
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.
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
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.
Ces ordonnanceurs peuvent interrompre un processus pour en exécuter un autre. Les principaux algorithmes sont :
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 :
Le système utilise plusieurs files d'attente (FA) avec différents niveaux de priorité et différents quanta de temps.
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.
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 :
Les systèmes multi-niveaux utilisent plusieurs files d'attente (FA) avec priorités :
Chaque file d'attente peut avoir son propre algorithme d'ordonnancement (ex. RR pour les files basses, FCFS pour les files hautes).