Ce document académique, destiné aux étudiants universitaires en informatique, propose une exploration approfondie de la gestion des processus dans les systèmes d'exploitation. Il vise à fournir une compréhension claire des mécanismes fondamentaux permettant de coordonner et d'exécuter efficacement les programmes.
Il couvre notamment les notions suivantes :
- Le concept de processus, ses définitions et ses différents états.
- Les mécanismes de scheduling, incluant les files d'attente et la commutation de contexte.
- Une analyse comparative des principaux algorithmes d'ordonnancement du processeur tels que FCFS, SJF, Round Robin et les approches multiniveaux.
Gestion des Processus
Concept de Processus
On peut trouver plusieurs appellations possibles pour les activités d'un processeur. Un système de traitement par lots exécute des travaux, tandis qu'un système en temps partagé gère des programmes utilisateurs ou des tâches.
Définition d'un Processus
Un processus (ou process) peut être défini comme un programme en exécution. Autrement dit, un programme par lui-même n’est pas un processus. Un programme est une entité passive, comme le contenu d’un fichier stocké sur disque, tandis qu’un processus est une entité active, avec un compteur d’instructions spécifiant l’instruction suivante à exécuter et un ensemble de ressources associées. Il est évidemment possible d’avoir plusieurs processus différents associés à un même programme. C’est le cas, par exemple, de plusieurs utilisateurs exécutant chacun une copie du programme de messagerie. Il est également courant qu’un processus génère à son tour plusieurs processus lors de son exécution.
Les États d'un Processus
Durant son séjour dans un système d'exploitation (SE), un processus peut changer d’état à plusieurs reprises. Ces états sont les suivants :
- Nouveau : Le processus vient d’être créé.
- Prêt : Le processus est placé dans la file d’attente des processus prêts, en attente d’affectation du processeur.
- En exécution : Le processus a été affecté à un processeur libre. Ses instructions sont en cours d'exécution.
- En attente : Le processus attend qu’un événement se produise, comme l’achèvement d’une opération d’E/S ou la réception d’un signal.
- Terminé : Le processus a terminé son exécution.
Bloc de Contrôle de Processus (PCB)
Pour suivre son évolution, le SE maintient pour chaque processus une structure de données particulière appelée bloc de contrôle de processus (PCB : Process Control Block) et dont le rôle est de reconstituer tout le contexte du processus.
Les informations contenues dans le PCB, et permettant de reconstituer le contexte d’un processus, sont multiples. On peut citer entre autres :
- L’état du processus : Il peut avoir l’une des valeurs suivantes : Nouveau, Prêt, En exécution ou En attente.
- Le compteur d’instructions : Le compteur indique l’adresse de la prochaine instruction à exécuter par le processus.
- Les registres du processeur : Les registres varient en nombre et en type en fonction de l’architecture de l’ordinateur. Ils englobent des accumulateurs, des registres d’index, des pointeurs de pile et des registres à usage général. Ces informations doivent être sauvegardées avec le compteur d’instructions lorsqu'une interruption se produit, afin de permettre au processus de poursuivre correctement son exécution après la reprise.
- Informations sur l'ordonnancement du processeur : Ces informations comprennent la priorité du processus, les pointeurs sur les files d’attente d'ordonnancement, etc.
- Informations sur la gestion de la mémoire : Ces informations peuvent inclure les valeurs de registres de base et limites, les tables de pages ou les tables de segments selon le système de mémoire utilisé.
- Informations sur l’état des E/S : Les fichiers ouverts, la liste des périphériques d’E/S.
Ordonnancement des Processus (Scheduling)
Files d'Attente pour l'Ordonnancement
Pour gérer les processus durant leur séjour, le SE maintient plusieurs files d’attente. On peut citer entre autres :
- File d’attente des processus prêts : Cette file contient tous les processus en attente du processeur.
- File d’attente de périphérique : Pour réguler les demandes d’affectation des différents périphériques, on peut imaginer une file d’attente pour chaque périphérique. Quand un processus demande une opération d’E/S, il est mis dans la file d’attente concernée.
Concrètement, une file d’attente est représentée par une liste chaînée de PCB.
Un nouveau processus est initialement placé dans la file d’attente des processus prêts. Il attend dans cette file jusqu’à ce qu’il soit sélectionné pour son exécution et qu'il obtienne le processeur.
Une fois qu'un processus a obtenu le processeur et qu'il est en cours d’exécution, il pourrait se produire l’un des événements suivants :
- Le processus pourrait émettre une requête d’E/S et être ensuite placé dans une file d’attente d’E/S.
- Le processus pourrait créer un nouveau processus et attendre la fin de celui-ci.
- Le processus pourrait être enlevé du processeur ; on dit aussi que le processeur a été réquisitionné (préempté). Dans ce cas, le processus est remis dans la file d’attente des processus prêts.
- Le processus pourrait se terminer.
Le Planificateur (Scheduler)
Le planificateur (ou scheduler) est un programme du SE qui s’occupe de choisir, selon une politique d'ordonnancement donnée, un processus parmi les processus prêts pour lui affecter le processeur.
Commutation de Contexte
La commutation de contexte est le processus qui consiste à sauvegarder l’état de l’ancien processus (le processus en cours d'exécution) et à charger l’état sauvegardé par le nouveau processus (le processus qui va être exécuté). Cette tâche est essentielle pour permettre au système d'exploitation de passer d'un processus à l'autre de manière fluide et sans perte d'information.
Critères d'Évaluation des Algorithmes d'Ordonnancement
Les divers algorithmes d'ordonnancement du processeur possèdent des propriétés différentes et peuvent favoriser une classe de processus plutôt qu’une autre. Pour choisir quel algorithme utiliser dans une situation particulière, nous devons tenir compte des propriétés des divers algorithmes. Plusieurs critères ont été proposés pour comparer et évaluer les performances des algorithmes d'ordonnancement du processeur. Les critères les plus souvent utilisés sont :
- Utilisation du processeur : Un bon algorithme d'ordonnancement est celui qui maintient le processeur aussi occupé que possible.
- Capacité de traitement (Throughput) : C’est le nombre de processus terminés par unité de temps.
- Temps de retournement (Turnaround Time) : C’est le temps s’écoulant entre la soumission du travail et sa terminaison. Il inclut le temps d'attente, le temps d'exécution et le temps d'E/S.
- Temps d’attente : C’est le temps total passé à attendre dans la file d’attente des processus prêts.
- Temps de première réponse (Response Time) : C’est le temps écoulé entre la soumission d'une requête et la première réponse générée par le système, indiquant que le processus a commencé son exécution.
Les Algorithmes d'Ordonnancement
Algorithme Premier Arrivé, Premier Servi (FCFS)
L’algorithme d'ordonnancement du processeur le plus simple est l’algorithme du Premier Arrivé, Premier Servi (First Come First Served : FCFS). Avec cet algorithme, le processeur est alloué au premier processus qui le demande. L’implémentation de la politique FCFS est facilement mise en œuvre avec une file d’attente FIFO (First-In, First-Out). Quand un processus entre dans la file d’attente des processus prêts, son PCB est ajouté à la queue de la file d’attente. Quand le processeur devient libre, il est alloué au processus en tête de la file d’attente.
Exemple : Trois processus P1, P2 et P3 arrivent dans cet ordre au système. Leurs durées d’exécution sont respectivement : 24, 3, 3 unités de temps. Pour représenter l’historique d’occupation du processeur, on utilise le diagramme de Gantt :
Diagramme de Gantt :
P1 P2 P3 0 24 27 30
Ce diagramme montre que le processus P1 occupe le processeur de l’instant 0 jusqu’à l’instant 24. À l’instant 24, le processeur est occupé par le processus P2, puis à l’instant 27 il sera suivi du processus P3.
Le temps d’attente est égal à 0 pour le processus P1, 24 pour le processus P2 et 27 pour le processus P3. Le temps d’attente moyen est égal à : (0+24+27)/3, soit 17 unités de temps.
Si les processus étaient arrivés dans l’ordre P2, P3 et P1, les résultats seraient différents :
Diagramme de Gantt :
P2 P3 P1 0 3 6 30
Le temps moyen d’attente serait : (0+3+6)/3 = 3 unités de temps. Ainsi, le temps moyen d’attente avec une politique FCFS n’est généralement pas minimal et peut varier substantiellement si les durées d’exécution des processus varient beaucoup.
Critique de la méthode :
La méthode FCFS tend à pénaliser les travaux courts : l’algorithme FCFS n’effectue pas de préemption (réquisition). C’est-à-dire qu’une fois que le processeur a été alloué à un processus, celui-ci le garde jusqu’à ce qu’il le libère, soit en terminant, soit après avoir demandé une opération d'E/S. L’algorithme FCFS est particulièrement incommode pour les systèmes à temps partagé, où il est important que l’utilisateur obtienne le processeur à des intervalles réguliers. Il peut paraître désastreux de permettre qu’un processus garde le processeur pendant une période prolongée.
Algorithme du Plus Court d'abord (SJF)
Cet algorithme (en anglais Shortest Job First : SJF) affecte le processeur au processus possédant le temps d’exécution le plus court. Si plusieurs processus ont la même durée, une politique FIFO sera alors utilisée pour les départager.
Exemple : On soumet au système quatre processus P1, P2, P3 et P4 dont les durées d’exécution sont données par le tableau suivant :
| Processus | Durée d’exécution |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
L’algorithme du travail le plus court donnera alors le résultat suivant :
Diagramme de Gantt :
P4 P1 P3 P2 0 3 9 16 24
Le temps moyen d’attente est = (0+3+9+16)/4 = 7. Alors que si on avait choisi une politique FCFS, le temps moyen serait de : 10.25 unités de temps.
Critique de la méthode :
Il a été prouvé que l’algorithme SJF est optimal, car il permet d'obtenir le temps d’attente le plus court pour un ensemble de processus donné. Toutefois, cet algorithme est difficile à implémenter pour une raison simple : comment peut-on connaître le temps d’exécution d’un processus à l’avance ? Dans la pratique, on estime souvent ce temps en se basant sur les exécutions précédentes.
Ordonnancement avec Priorité
Cet algorithme associe à chaque processus une priorité, et le processeur sera affecté au processus de plus haute priorité. Cette priorité varie selon les systèmes et peut aller de 0 à 127. Les priorités peuvent être définies en fonction de plusieurs paramètres : le type de processus, les limites de temps, les limites mémoires, etc.
Exemple : On dispose de 5 processus ayant des priorités différentes, comme le montre ce tableau :
| Processus | Durée d’exécution | Priorité |
|---|---|---|
| P1 | 10 | 2 |
| P2 | 1 | 4 |
| P3 | 2 | 2 |
| P4 | 1 | 1 |
| P5 | 5 | 3 |
(Note : Dans cet exemple, une valeur de priorité plus élevée indique une priorité plus haute.)
Diagramme de Gantt :
P2 P5 P1 P3 P4 0 1 6 16 18 19
Le temps moyen d’attente est = (0+1+6+16+18)/5 = 8.2 unités de temps.
Critique de la méthode :
Une situation de famine (ou blocage) peut survenir si les processus de basse priorité attendent indéfiniment le processeur, alors que des processus de haute priorité continuent à affluer. Pour éviter une telle situation, on peut utiliser la technique dite du vieillissement (aging). Elle consiste à incrémenter graduellement la priorité des processus en attente dans le système pendant longtemps. Par exemple, nous pourrions incrémenter de 1 la priorité d’un processus en attente toutes les 15 minutes. En fin de compte, même un processus ayant une priorité initiale faible (par exemple 0) augmenterait sa priorité jusqu'à être exécuté.
Algorithme Round Robin (Tourniquet)
L’algorithme d'ordonnancement du tourniquet, appelé aussi Round Robin, a été conçu pour des systèmes à temps partagé. Il alloue le processeur aux processus à tour de rôle, pendant une tranche de temps appelée quantum. Dans la pratique, le quantum s’étale généralement entre 10 et 100 ms.
Exemple : On dispose de 3 processus P1, P2 et P3 ayant comme durée d’exécution, respectivement 24, 3 et 3 ms. En utilisant un algorithme Round Robin, avec un quantum de 4 ms, on obtient le diagramme de Gantt suivant :
Diagramme de Gantt :
P1 P2 P3 P1 P1 P1 P1 P1 0 4 7 10 17 18 22 26 30
Le temps moyen d’attente est de : (6+4+7)/3 = 17/3 = 5.66 ms.
La performance de l’algorithme de Round Robin dépend largement de la taille du quantum. Si le quantum est très grand, la politique Round Robin serait similaire à celle du FCFS. Si le quantum est très petit, la méthode Round Robin permettrait un partage du processeur : chacun des utilisateurs aurait l’impression de disposer de son propre processeur. Cependant, le quantum doit être choisi de sorte à ne pas surcharger le système par de fréquentes commutations de contexte, qui introduisent un coût significatif.
Exemple de commutations de contexte : On dispose d’un processus P dont le temps d’exécution est de 10 ms. Calculons le nombre de commutations de contexte nécessaires pour un quantum donné :
- Quantum = 12 ms : Nombre de commutations de contexte = 1 (le processus termine avant la fin du quantum ou juste après un quantum)
- Quantum = 6 ms : Nombre de commutations de contexte = 2 (le processus est interrompu une fois après le premier quantum, puis termine au deuxième)
- Quantum = 1 ms : Nombre de commutations de contexte = 9 (le processus est interrompu 9 fois et termine à la 10ème tranche d'exécution, ce qui implique 9 commutations pour les 10 tranches)
Ordonnancement avec Files d'Attente Multiniveaux
Une autre classe d’algorithmes d'ordonnancement a été développée pour des situations où l'on peut facilement classer les processus dans des groupes différents. Par exemple, il serait intéressant de faire une distinction entre les processus de premier plan (interactifs) et les processus d’arrière-plan (traitement par lot). En effet, ces deux types de processus possèdent des besoins différents en ce qui concerne le temps de réponse et ils pourraient donc devoir être ordonnancés différemment. De plus, les processus de premier plan peuvent être prioritaires par rapport aux processus d’arrière-plan.
Ainsi, un algorithme d'ordonnancement avec des files d’attente multiniveaux découpe la file d’attente des processus prêts en plusieurs files d’attente séparées. Un exemple de découpage peut inclure :
- Processus système
- Processus interactifs
- Processus batch
- Processus utilisateurs
Les processus sont en permanence assignés à une file d’attente en se basant généralement sur certaines propriétés du processus, comme : le type de processus, la taille de la mémoire, la priorité, etc. Chaque file d’attente possède son propre algorithme d'ordonnancement. Par exemple, la file d’attente des processus systèmes est ordonnancée selon un algorithme de plus haute priorité, celle des processus interactifs est gérée selon l’algorithme Round Robin et la file des processus batch est gérée selon l’algorithme FCFS.
D’autre part, il doit y avoir un ordonnancement entre les files d’attente elles-mêmes. Observons par exemple, l’ensemble des files d’attente multiniveaux suivants :
- Processus systèmes
- Processus interactifs
- Processus batch
- Processus utilisateurs
Chaque file d’attente est absolument prioritaire par rapport aux files d’attente de niveau inférieur. Par exemple, aucun processus de la file d’attente des processus batch ne pourra s’exécuter à moins que les files d’attente des processus système et interactifs ne soient toutes vides. De plus, si un processus interactif arrive au système, alors qu’un processus batch est en train de s’exécuter, celui-ci doit être préempté.
Une autre manière de procéder serait d’affecter des tranches de temps aux files d’attente. Chaque file d’attente obtient une certaine partie du temps processeur, laquelle doit ordonnancer les différents processus qui la composent. Par exemple, on peut attribuer 80% du temps processeur à la file d’attente des processus de premier plan et 20% pour la file d’attente des processus d’arrière-plan.
Ordonnancement avec Files d'Attente Multiniveaux à Rétroaction (Feedback)
Normalement, dans un algorithme avec des files d’attente multiniveaux, les processus sont assignés en permanence à une file d’attente dès qu’ils rentrent dans le système. Les processus ne se déplacent pas entre les files d’attente. Cette organisation possède l’avantage d’une faible surcharge due à l'ordonnancement, mais elle manque de souplesse.
Ainsi, l'ordonnancement avec des files d’attente multiniveaux à rétroaction permet aux processus de se déplacer entre les files d’attente. L’idée revient à séparer les processus en fonction de l’évolution de leurs caractéristiques dans le système, permettant par exemple à un processus interactif de perdre de la priorité s'il utilise trop de temps CPU, ou à un processus long d'augmenter sa priorité au fil du temps (vieillissement).
Exemple : Un système est doté de 3 files d’attentes multiniveaux : File 0, File 1 et File 2. La file 0 est la plus prioritaire. Les files 0 et 1 sont gérées selon la politique Round Robin. La file 2 est gérée selon la technique FCFS.
- File d’attente 0 : Quantum = 8 ms (priorité la plus haute)
- File d’attente 1 : Quantum = 16 ms
- File d’attente 2 : FCFS (priorité la plus basse)
Un processus entrant dans le système sera rangé dans la file d’attente 0. On donne une tranche de temps de 8 ms au processus. S’il ne finit pas, il est déplacé vers la file d’attente 1. Si la file d’attente 0 est vide, on donne une tranche de temps de 16 ms au processus en tête de la file 1. S’il ne termine pas, il est interrompu et il est mis dans la file d’attente 2. Les processus de la file d’attente 2 sont exécutés seulement quand les files 0 et 1 sont vides.
Foire Aux Questions (FAQ)
1. Qu'est-ce qu'un processus dans un système d'exploitation ?
Un processus est un programme en exécution. Contrairement à un programme (qui est une entité statique, un ensemble d'instructions), un processus est une entité dynamique et active qui dispose de ses propres ressources (mémoire, registres du processeur) et d'un état d'exécution.
2. Quels sont les principaux états qu'un processus peut traverser ?
Les principaux états sont : Nouveau (le processus vient d'être créé), Prêt (le processus attend d'être affecté au processeur), En exécution (le processeur exécute ses instructions), En attente (le processus attend qu'un événement se produise, comme une opération d'E/S), et Terminé (le processus a achevé son exécution).
3. Quel est le rôle d'un scheduler et des files d'attente d'ordonnancement ?
Le scheduler (ou planificateur) est un programme du système d'exploitation chargé de choisir, selon une politique prédéfinie, quel processus parmi ceux qui sont prêts doit être exécuté par le processeur. Les files d'attente d'ordonnancement sont des structures de données qui organisent les processus en attente (par exemple, la file des processus prêts ou les files d'attente de périphériques) et permettent au scheduler de prendre sa décision.