Tweet
Introduction aux systèmes d'exploitation - Chapitre 2 : Les processus
2.1 Modèle
2.1.1 Notion de processus
Modèle simple de représentation de l’exécution de tâches au sein d’un OS.
Un processus est une instance d’un programme en train de s’exécuter.
Un processus modélise l’exécution d’un programme sur un processeur virtuel disposant de :
- Un compteur ordinal —> Il pointe sur l’instruction à exécuter
- Un jeu de registres
- De mémoire virtuelle
…
Le processeur physique commute entre les processus sous l’ordre d’un ordonnanceur.
Dans un système à temps partagé, tous les processus s’exécutent en même temps mais un seul à la fois.
Si les même opérations étaient lancées deux fois de suite, le temps d’exécution ne serait pas forcément le même dû :
- Au positionnement des têtes du HDD
- À l’occupation des caches
- Au traitement des évènements asynchrones qui peuvent conduire à des ordonnancements très différents
On ne peut donc pas faire d’hypothèses sur le facteur temps —> Gestion plus compliquées des interruptions au point de vue matériel.
2.1.2 Relations entre les processus
Un processus est créé par un autre processus via un appel système. On peut donc définir (selon l’ OS) une arborescence de processus à partir d’un ancêtre commun (init sur Unix).
Les processus n’ont pas d’arborescence dans un système windows.
On peut donc créer des groupes de processus qui seront un fait une sous partie de l’arborescence de base. —> On peut contrôler plus finement les commandes sur les processus.
2.1.3 Etats d’un processus
Elu : En cours d’exécution sur le processeur. Machine multi-processus —> Plusieurs élus en même temps (au plus autant d’élus que de processeurs).
Prêt : Processus auquel il ne manque que la ressource processeur.
Bloqué : Il est en attente d’un processus externe (I/O, frappe clavier,…)
Le 2 n’existe pas dans un système de traitement par lots
2. Le processus a épuisé le temps qui lui était accordé et l’ordonnanceur (appelé de façon asynchrone par interruption) élit un autre processus.
3. L’ordonnanceur passe un processus en élu en choisissant dans les processus prêts.
1. Le processus s’endort en attente d’un évènement externe —> l’ordonnanceur est appelé ( de manière explicite par le processus) élit un autre processus.
4. L’évènement attendu par le processus se produit (c’est l’OS qui gère sont traitement vu que le processus est endormi). L’OS interrompt donc temporairement le processus en exécution pour gérer l’évènement et passer le processus de bloqué à prêt.
L’exécution d’un processus peut donc progresser de deux manières :
- Synchrone : le processus est élu et dispose de la ressource processeur.
- Asynchrone : le processus est élu mais est arrêté par l’OS pour finir une I/O
2.2 Mise en oeuvre
Les interruptions et la gestion des processus forment toujours la gestion la plus basse de l’OS afin de faire abstraction de ces problèmes pour les couches supérieures.
2.2.1 Gestion des processus
Pour mettre en oeuvre la gestion des processus, l’OS dispose d’une table des processus (jamais swapée) dont chaque entrée contient des informations sur un processus particulier tel que :
- Les valeurs de son compteur ordinal, de sont pointeur de pile et des autres registres processeur
- Son numéro de processus, son état sa priorité
- Son occupation mémoire
- Sa liste des fichiers ouverts
…
Pour éviter que cette table ne prenne trop de place, elle est découpée en 2 parties.
- La première (jamais swapée) contient les informations indispensables pour entamer le chargement d’un processus.
- La seconde (swappable car dans l’espace mémoire propre du processus) contient les informations nécessaire lors du passage de prêt à élu.
2.2.2 Gestion des interruptions
Lorsque le système reçoit une interruption, il localise la routine de traitement de celle-ci en la localisant dans un tableau indexé sur son type.
L'interruption logicielle est donc une interruption classique en langage machine et non une interruption provenant d’un autre composant.
Les étapes de traitement d’une interruption sont :
1. Le processeur sauvegarde la valeur de son compteur ordinal dans la pile courante, détermine le type d’interruption , passe en mode noyau et charge la nouvelle valeur de son compteur ordinal (l’adresse de la routine de traitement de l’interruption).
2. La routine sauvegarde les registres processeur dans la pile ou en construit une nouvelle puis appelle la routine de gestion de gestion de l’interruption.
3. Au retour de cette appel, la routine de traitement restaure les registres processeurs et replace la valeur du compteur ordinal afin de relancer le processeur sur le bon processus
2.3 Communication inter-processus
Les processus ne s’exécutent pas tous de manières isolée. Certains ont besoin de communiquer, de se synchroniser et d’autres encore sont en compétition pour les ressources du système (ressources non partageables au risque de créer des inter-blocages).
Exemple : Une liste d’impression
Si deux processus veulent imprimer, ils doivent chacun recevoir un numéro d’ordre puis placer leur document dans la file puis incrémenter pour le numéro suivant.
Cependant, si l’une des tâches est interrompue avant d’incrémenter le compteur, deux processus auront le même numéro et l’un d’eux sera perdu
Le système doit donc fournir un support sûr de la communication inter-processus, celui-ci peut être basé sur :
1. Les mécanismes du système de fichiers (pipes, pipes nommés)
2. Les mécanismes de gestion de la mémoire (mémoire partagée, sémaphores)
Le vrai problème est l’accès concurrentiel à une variable partagée, et ce à cause du fait que cela peut créer des résultats incohérents de façon imprévisible.
2.4 Sections critiques
Elles ont pour but d’interdire la modification de données partagées à plus d’un processus à la fois et donc définir des exclusions mutuelles sur des portions spécifiques de code appelées sections critiques.
On peut définir le comportement dans les sections critiques par :
- Deux processus ne peuvent être simultanément dans la même section critique —> Suffisante pour éviter le conflits mais ne garantit pas l’égalité.
- Aucune hypothèse ne peut être faite sur les vitesses des processus
- Aucun processus suspendu en dehors d’une section critique ne peut bloquer les autres
- Aucun processus ne doit attendre trop longtemps pour entrer en section critique
2.4.1 Masquage des interruptions
On désactive les interruptions avant d’entrer en section critique et on les restaure à la fin —> Pas d’ordonnancement.
Désavantages :
- Inéquitable : Un processus se tenant longtemps en section critique bloque les autres
- Dangereux : Si on oublie de restaurer les interruptions —> Blocage complet.
- Inefficace : - Sur les systèmes multi-processeurs puisque qu’un processus sur le deuxième processeur peut rentrer en section critique. - Quand un processus entre en section critique il bloque tout les autres, même ceux qui ne sont pas en section critique
Elle est utilisée par l’OS pour manipuler ses fonctions internes.
2.4.2 Variables de verrouillage ( équivalant à TSL )
Pour éviter de bloquer tout les autres processus, on crée une variable verrou par section critique.
Un processus voulant entrer en section critique teste donc cette variable :
Si VRAI, il attend (de manière active)
Si FAUX il entre et la positionne à VRAI et quand il sort, il la repositionne à FAUX
Désavantage :
- Uniquement pour les machines mono-processeur
- Les deux processus modifient la même variable en même temps
- Quand il a finit d’attendre et avant de positionner le verrou il peut être interrompu par un autre lui « volant » sa section critique
Une solution serait d’inhiber les interruptions à la sortie de l’attente active et de vérifier une dernière fois si le verrou est positionné avant d’entrer en section critique. Si ce n’est pas le cas on entre en section critique, sinon on réactive les interruptions et on retourne dans l’attente active.
2.4.3 Variable d’alternance
Pour éviter de modifier la même variable en même temps, on crée une variable d’alternance qui définit le numéro du processus qui peut entrer en section critique.
Désavantage :
- Quand un processus sort de section critique il s’interdit d’y retourner avant que ça ne soit de nouveau son tout —> Si un autre processus dure plus longtemps, on se bloque.
2.4.4 Variable d’alternance de Peterson
Elle améliorer la simple variable d’alternance car elle permet à un processus dont ce n’est pas le tour de rentrer en section critique si les autres ne sont pas prêts.
Cette solution se base sur deux procédures entrer_region() et sortir_region() qui encadrent la section critique.
Cette solution est valable et efficace.
2.4.5 Instruction TSL
On se base sur l’instruction TSL qui est une instruction en langage machine.
Cette solution est valable et efficace même sur les multi-processeurs car on bloque le bus d’accès à cette case mémoire.
2.4.6 Primitives sleep et wakeup
Ce sont des appels système.
Sleep : Endort le processus qui l’appelle en rendant la main à l’ordonnanceur
Wakeup : Réveille un processus dans l’identifiant est rentré en paramètre.
Ils peuvent dans certains cas former des inter-blocages ou des dead-locks
2.4.7 Sémaphores
On utilise une variable entière (appelée sémaphore) pour comptabiliser le nombre de réveils en attente et on encapsule cette variable dans un objet système manipulable uniquement par des appels systèmes spécifiques.
La primitive down décrémente le sémaphore et endort le processus appelant si il était déjà à 0.
La primitive up incrémente le sémaphore si aucun processus n’est endormi sinon, il en réveil un au hasard.
La manipulation des sémaphores via des appels systèmes permet de désactiver de manière efficace et sûre les interruptions vu que la manipulation du sémaphore est à la charge de l’OS et pas de l’utilisateur.
Dans le cas d’un système multi-processeur, les sémaphores sont protégés par des variables de verrouillages manipulées par l’instruction TSL (ici l’attente active n’est pas préjudiciable car elle sera de courte durée).
L’utilisation des sémaphores simplifie les exclusions mutuelles, mais elles restent tout de même fastidieuse et peut mener à des inter-blocages (au cas où on inverserait deux down).
2.4.8 Moniteurs
Il sert à offrir le support des exclusions mutuelles au niveau du langage.
Il est composé d’un ensemble de données et de procédure dont un seul processus peut être actif en même temps.
Dans ce cas, c’est le compilateur qui gère les exclusions mutuelles (en ajoutant des sémaphores) —> Le risque d’erreur est bien plus bas.
Le moniteur nécessite les instructions wait et signal pour fonctionner correctement et permettre l’échange de données dans sa structure.
Wait : bloque le processus appelant sur la variable passée en paramètre.
Signal : réveil l’un des processus bloqué sur la variable
Wait et signal ressemblent à sleep et wakeup mais ne permettent pas l’exclusion concurrente de celles-ci.
Ils règlent donc les problèmes de sleep et de wakeup
2.4.9 Echange de messages
Le problème de ressources partagées peut être reformulé en terme de communication inter-processus. Celle-ci est implémentée via deux primitives:
Send: envoi d'un message à un processus donné
Receive: lis un message provenant d’un processus donné ou quelconque. Si aucun message n’est disponible, receive bloque le processus appelé.
Cette solution permet la communication sur un système à mémoire partagée mais est beaucoup plus dur à mettre en oeuvre car elle nécessite de régler ces problèmes:
- La perte possible des messages —> Message de bonne réception avec des message numérotés pour éviter les doublons. Les messages récepteur —> envoyeur peuvent aussi être regroupés en un seul message.
- Le nomage des processus —> Ensemble de nomage global à l’ensemble des processus —> Goulot étranglement posé par l’accès à cette ressource. De plus il est impossible d’empêcher deux processus de porter le même nom
- L’authentification des messages —> Crypto systèmes (clés publiques et privées) mais dans ce cas on a besoin de services externes qui risquent de créer des goulots d’étranglement
- Surcoût dû à la latence —> Problème des intermédiaires mis en jeu, chaque intermédiaire représente une recopie mémoire
- Tolérance aux pannes —> Quand la réponse ne vient pas on ne peut pas savoir si l’opération s’est effectuée —> On peut obliger à envoyer une réponse
2.5 Problème classique de communication inter-processus
2.5.1 Le problème des philosophes
Cinq philosophes sont assis autour d’une table et chacun a devant lui une assiette pleine de spaghetti tellement glissant qu’il faut deux fourchettes pour les manger. Une fourchette étant systématiquement déposée entre deux assiettes consécutives.
Un philosophe passe son temps à penser ou à manger. S’il obtient les feux fourchettes, il mange pendant un certain temps puis se remet à manger.
Le problème consiste à permettre à chacun des philosophes de faire chacune de ses activités sans jamais être bloqué de manière irrémédiable.
Dans ce cas pour éviter les inter blocage, on utilisera des sémaphores et des mutes (sémaphores d’exclusion mutuelle).
2.6 Ordonnancement de processus
C’est un algorithme qui sélectionne lequel des processus prêt va s’exécuter.
Dans un système de traitement par lots, on exécute le programme suivant dès qu’un emplacement se libère dans la mémoire (dès qu’on a finit le précédent).
Dans un cas de multi-utilisateurs, multi-tâches et multi-processeurs l’ordonnancement peut devenir très complexe. Il s’appuie sur les critères suivants :
- Chaque processus doit pouvoir disposer du processeur
- L’utilisation du processeur doit être maximale
- On doit minimiser le temps de réponse
- On doit minimiser le temps d’exécution
- On doit maximiser le nombre de travaux par unité de temps
Ces critères sont mutuellement exclusifs.
Pour assurer l’équité il est nécessaire de mettre en oeuvre un mécanisme de temporisation et de rendre la main à l’ordonnanceur après avoir épuisé son temps d’exécution (système préemptif —> complexité ++) .
2.6.1 Ordonnancement circulaire
On assigne a chaque processus un quantum de temps, si dans ce quantum il se termine ou passe en état bloqué, on repasse la main à l’ordonnanceur. Sinon on va jusqu’au bout du quantum puis, on repasse à l’ordonnanceur.
Le principal problème ici est de fixer un bon quantum de temps, trop court —> on passe plus de temps à switcher qu’autre chose. Trop long —> Pas fluide
2.6.2 Ordonnancement avec priorité
On souhaite favoriser certaines tâches en leur attribuant une priorité plus élevée (les priorités changent dynamiquement).
Par exemple, certains processus passent la majeur partie de leur temps en état bloqué, il est donc préférable de leur donner une préférence haute afin de les « lancer » dans leurs travail sans attendre.
Les processus sont aussi regroupés en classe de priorité. Cela permet de faire de l’ordonnancement par priorité entre les classes et circulaire dans une même classe (dans les faits, les ordonnancements sont souvent hybrides).
Le problème majeure est de changer la classe de priorité d’un processus. Un processus qui a calculé longtemps avant de redevenir interactif aura donc une priorité très haute (car pendant son calcul elle était beaucoup plus faible).
2.6.3 Ordonnancement du plus court d’abord
Ce type d’ordonnancement se fait sur une série de tâche dont on peut savoir la durée à l’avance.
Si la file d’attente contient plusieurs tâches de même priorité, on minimise le temps d’exécution en effectuant toujours d’abord celle qui à le temps le plus court.
Cette technique peut être adaptée à des processus interactifs si l’on considère que chaque commande utilisateur est un processus indépendant. Si l’on ne connait pas la durée d’une tâche, on peut alors spéculer par rapport à la durée des tâches précédents.
2.6.4 Ordonnancement dicté par une politique
Le but de cet ordonnancement est de garantir à l’utilisateur un temps de réponse maximum annoncé (par exemple). Dans un tel cas, le système retient le temps processeur utilisé par chaque utilisateur et le divise par le nombre d’utilisateurs connecté afin de choisir le rapport le plus petit.
Utilisé principalement pour les systèmes en temps réel —> Les usines par exemple (chaine de production)
2.6.5 Ordonnancement à deux niveaux
Jusqu’ici on a supposé que tout les processus étaient en mémoire centrale dès le début. Dans les faits ce n’est pas forcément le cas.
Si le processus est swappé, le temps d’accès sera plusieurs fois plus long et cette latence doit être prise en compte par l’algorithme d’ordonnancement.
On utilise donc un ordonnanceur à deux niveaux :
- Ordonnanceur habituel (bas niveaux)
- Ordonnanceur haut niveau appelé de temps en temps qui échange les processus entre le disque et la mémoire centrale.
Pour décider de la migration l’ordonnanceur haut niveau se base sur :
- Le temps écoulé depuis le dernier va et vient
- La quantité de temps processeur déjà utilisée par le processus
- La taille du processus (déplacer un petit est moins couteux)
- La priorité du processus
Sous Unix :
L’ordonnanceur de haut niveau est le swapper qui s’exécute en mode noyau (pour ne pas devoir passer par des appels systèmes).
Si la swapper doit migrer un processus sur le disque (manque de place en mémoire), il choisit un processus non zombie (car ils ne consomment pas de place en mémoire) et non verrouillés. Donc les processus endormis sont choisi en priorité.
