Processus et Ressources
Comment une machine organise l’exécution simultanée de plusieurs programmes ?
Programmes et Processus
Il ne faut pas confondre :
- programme (exécutable) : fichier binaire contenant des instructions machines
- processus : instance d’exécution d’un programme entraînant des échanges de données (registres, mémoire, interfaces, …)
Dans une même machine, il peut y avoir plusieurs instances d’exécution d’un même programme !
Objectif : partager un (ou plusieurs) processeur(s) entre différents processus, de manière à ce que chaque processus possède son propre processeur virtuel (point de vue conceptuel).
Problème : un processeur (ou un cœur de processeur) ne peut exécuter qu’une seule instruction à la fois, il doit « basculer » constamment d’un processus à l’autre.
PID et PPID
Chaque processus possède un code unique appelé identifiant de processus (PID – Process IDentifier).
Mais chaque processus (mis à part le premier !) a lui même été lancé par un processus parent, identifié par un identifiant de processus parent (PPID – Parent Process IDentifier).
Sous Linux le premier processus démarré s’appelle
init
et a le PID1
et le PPID0
Sous Windows c’est le processus
Idle
(ouSystem Idle Process
), de PID0
(idle signifie « inactif » en anglais)
Contexte d’exécution
Lorsque plusieurs processus sont lancés, le (cœur d’un) processeur doit basculer de l’un à l’autre (ce basculement rapide est appelé multiprogrammation).
Ce basculement étant imprévisible, la vitesse de traitement d’un processus donné :
- n’est pas uniforme : elle pourra être plus rapide au début de l’exécution qu’à la fin, ou l’inverse !
- n’est pas reproductible : si le même processus s’exécute une nouvelle fois, sa durée d’exécution sera différente.
Le contexte d’exécution (execution context) d’un processus est l’ensemble des éléments liés à son exécution :
- PID
- État du processus
- Valeurs des registres du processeur
- Mémoire : Plage d’adresses de la mémoire allouée par le processus
- Ressources :
- fichiers ouverts
- connexions réseau en cours d’utilisation
Cet ensemble de données constitue le bloc de données contextuelles ou bloc de contrôle du processus (PCB – Process Control Block)
Il est sauvegardé à chaque changement de contexte (context switching) : opération de remplacement d’un contexte d’exécution par un autre
États d’un processus
Lorsqu’un programme est lancé, les instructions machine qui le composent sont chargées en mémoire de travail (RAM) : le processus associé est alors créé.
Pendant son existence au sein d’une machine, un processus peut avoir différents états :
- nouveau : le processus est en cours de création, l’exécutable est en mémoire et le PCB initialisé
- prêt (ready ou runnable) ou en attente (waiting) : le processus attend d’être affecté à un processeur
- élu (running) : les instructions du processus sont en cours d’exécution (il utilise le CPU)
seul un processus peut être en exécution sur processeur à un instant donné. - bloqué (blocked) ou endormi (sleeping) : le processus est interrompu en attente qu’un événement se produise
- terminé (terminated) : le processus est terminé (soit normalement, soit suite à une anomalie).
il doit être déchargé de la mémoire par l’OS, et les ressources qu’il utilisait libérées.
Selon les systèmes d’exploitation, il peut se produire d’autres états possibles pour des processus :
- zombie : le processus est terminé mais ne peut pas être déchargé de la mémoire
- …
Ordonnancement des processus
La gestion des états des processus est confiée à un programme du système d’exploitation appelé ordonnanceur (scheduler). Il est chargé de gérer les accès concurrents aux ressources.
L’utilisation du processeur doit être optimisée : un processus en attente d’une ressource (donnée en mémoire, entrée/sortie, …) doit être mis dans l’état bloqué pour permettre à un autre processus en attente d’un processeur (état prêt) à passer dans l’état élu.
Lorsque plusieurs processus sont en attente (état prêt), l’ordonnanceur doit choisir le processus à élire : il les classe dans une file d’attente.
Dans le cas d’architecture à plusieurs processeurs, un répartiteur (dispatcher) attribut à chaque processeur un processus élu.
L’ordonnanceur de l’OS sélectionne un processus dans la file d’attente et le laisse s’exécuter pendant un délai maximum déterminé appelé le quantum de temps. À la fin de ce temps, ce processus et remis à l’état prêt et un autre est élu.
Une interruption matérielle peut venir écourter le quantum de temps.
Lorsqu’il n’y a plus de processus en attente (état prêt), le processeur redevenant inactif, sa vitesse peut être ralentie afin de diminuer sa consommation énergétique.
Politiques d’ordonnancement
L’ordonnanceur peut envisager diverses politiques d’ordonnancement :
- Premier arrivé, premier servi : simple, mais peu adapté
- Plus court d’abord : efficace, mais difficile de classer à l’avance la durée d’exécution d’un processus
- Priorité : chaque processus se voit attribuer un niveau de priorité
- Tourniquet : chaque processus se voit attribuer une durée d’exécution (appelé quantum de temps). Quand un processus a atteint cette durée, il cède la place à un autre.
- … politiques hybrides …
En pratique l’ordonnanceur octroie un quantum de temps à tous les processus tout en gérant les priorités.
Processus concurrents
Les exécutions des processus sont entrelacées. On parle d’exécution concurrente et l’OS est qualifié de multitâches.
Lorsqu’un processus est interrompu, son PCB est sauvegardé et quand son exécution reprend, le processus se retrouve dans l’exact état dans lequel il était.
→ Il n’a aucune connaissance de ce qui s’est passé autour de lui pendant ce temps !
Si ce processus ne manipulait que des objets visibles par lui seul (des variables par exemple), il n’y aurait aucune conséquence.
En revanche, dans le cas ou ce processus accède à des ressources partagées (des fichiers par exemple), il peut y avoir des conséquences non souhaitées.
Synchronisation
Interblocage
L’utilisation d’une ressource par un processus passe par les étapes suivantes :
- Demande de la ressource : si l’on ne peut pas satisfaire la demande il faut attendre, la demande sera mise dans une table d’attente des ressources,
- Utilisation de la ressource : le processus peut utiliser la ressource,
- Libération de la ressource : le processus libère la ressource demandée et allouée.
Un interblocage (ou étreinte fatale, deadlock en anglais) est un phénomène qui se produit lorsque des processus concurrents s’attendent mutuellement. Un processus peut aussi s’attendre lui-même. Les processus bloqués dans cet état le sont définitivement, il s’agit donc d’une situation catastrophique.
Exemple : accès à des périphériques
Supposons que deux processus A et B veulent imprimer, en utilisant la même imprimante, un fichier stocké sur un DVD. La taille de ce fichier est supérieure à la capacité
du disque. Chaque processus a besoin d’un accès exclusif au lecteur DVD et à l’imprimante simultanément. On a une situation d’interblocage si :
-
- Le processus A utilise l’imprimante et demande l’accès au lecteur DVD.
- Le processus B détient le lecteur DVD et demande l’imprimante.
source : https://cours.polymtl.ca/inf2610/documentation/notes/chap7.pdf
Conditions nécessaires
Une situation de blocage sur une ressource peut survenir si et seulement si toutes les conditions suivantes sont réunies simultanément dans un système :
- Exclusion mutuelle : la ressource système doit être en accès exclusif : elle est soit disponible, soit attribuée à un unique processus.
Sinon, les processus ne seraient pas empêchés d’utiliser la ressource si nécessaire. Un seul processus peut utiliser la ressource à un instant donné. - Rétention et attente (hold and wait ou resource holding) : un processus qui détient une ressource peut en demander une autre, détenue par un autre processus.
- Non préemption : une ressource ne peut être libérée que volontairement par le processus qui la détient.
Elle ne peut pas être préemptée ou acquise de force par un autre processus - Attente circulaire : chaque processus doit attendre une ressource qui est détenue par un autre processus, qui à son tour attend que le premier processus libère la ressource.
En général, il existe un ensemble de processus en attente, P = { P1 , P2 ,…, PN }, tel que P1 attend une ressource détenue par P2 , P2 attend une ressource détenue par P3 …
Ces quatre conditions sont connues sous le nom de « conditions de Coffman » d’après leur première description dans un article de 1971 par Edward G. Coffman, Jr.
Bien que ces conditions soient suffisantes pour produire un blocage sur les systèmes de ressources à instance unique, elles indiquent uniquement la possibilité d’un blocage sur les systèmes ayant plusieurs instances de ressources.
Graphe d’allocation des ressources
Le graphe d’allocation des ressources est un graphe biparti composé de deux types de nœuds et d’un ensemble d’arcs :
- Les processus qui sont représentés par des cercles.
- Les ressources qui sont représentées par des rectangles. Chaque rectangle contient autant de points qu’il y a d’exemplaires de la ressource représentée.
Un arc orienté d’une ressource vers un processus signifie que la ressource est allouée au processus.
Un arc orienté d’un processus vers une ressource signifie que le processus est bloqué en attente de la ressource.
Ce graphe indique pour chaque processus les ressources qu’il détient ainsi que celles qu’il demande.
Exemple :
Soient trois processus A, B et C qui doivent utiliser trois ressources R, S et T dans l’ordre donné dans le tableau suivant :
A | B | C |
---|---|---|
Demande R | Demande S | Demande T |
Demande S | Demande T | Demande R |
Libère R | Libère S | Libère T |
Libère S | Libère T | Libère R |
Si les processus sont exécutés de façon séquentielle ( A suivi de B, suivi de C), il n’y pas d’interblocage.
Supposons maintenant que l’exécution des processus est gérée par un ordonnanceur du type circulaire. Si les instructions sont exécutées dans l’ordre :
-
- A demande R
- B demande S
- C demande T
- A demande S
- B demande T
- C demande R
on atteint une situation d’interblocage, fait qui est montré sur le graphe d’allocation des ressources suivants :
Quelques commandes
Linux
ps (process status)
Affiche un cliché instantané de tous les processus en cours
L’option −eo pid,ppid,s,command
de cette commande affiche dans l’ordre :
- l’identifiant du processus :
pid
(Process IDentifier), - l’identifiant du processus parent :
ppid
(Parent Process IDentifier), - l’état du processus :
s
(State)R
: processus en cours d’exécution (Running)S
: processus endormi (Sleeping)- …
- le nom de la commande à l’origine du processus :
command
top
affiche la liste en temps réel de tous les processus en cours d’exécution
Tri selon diverses colonnes :
- PID : touche « N » (en majuscule !)
- CPU% : touche « P »
Inversion de l’ordre : touche « R »
Gestion des colonne : touche « f » (puis suivre les consignes à l’écran)
htop
affiche le résultat en temps réel et est équipée de fonctionnalités conviviales
kill
tue un processus