L’objectif de ce document est d’essayer de faire comprendre les idées mises en œuvre lors de l’écriture des système d’exploitation afin qu’un nombre de programmes plus important que le nombre de processeurs puisse fonctionner « simultanément ».
L’ordonnanceur
Rappel sur l’exécution d’un programme
-
Un programme est un fichier contenant une suite d’instructions écrites en langage machine. C’est une suite d’octets que le processeur est capable de décoder et d’exécuter.
-
Actions du système d’exploitation au lancement d’un programme :
- Le contenu du fichier contenant le programme est copié dans la mémoire vive (RAM), à une certaine adresse $a$.
- Le système d’exploitation écrit l’adresse $a$ dans le registre IP (instruction pointer).
-
Au cycle d’horloge du processeur suivant, ce dernier lit l’instruction qui se trouve dans le registre IP et l’exécute. Par la suite, il exécute la deuxième instruction puis les suivantes.
- Remarque
- L’exécution d’une instruction par le processeur se décompose en en plusieurs sous-étapes : le chargement (récupération de l’instruction en mémoire), le décodage (quelle action est codée par la suite d’octets) et l’exécution.
Interruptions
La description précédente est correcte mais incomplète : elle laisse penser qu’une fois un programme lancé le processeur se focalise sur son exécution, au détriment de l’exécution de tout autre programme.
Il existe plusieurs types d’interruptions :
-
les interruptions générées par le matériel (un disque dur signale qu’il a fini d’écrire un octet, une carte réseau signale qu’une trame vient d’arriver, …)
-
les interruptions d’horloges générées par le processeur (historiquement toutes les $\pu{55 ms}$, toutes les $\pu{100 ns}$ de nos jours).
Lorsqu’un processeur reçoit une interruption il interrompt son exécution à la fin de l’instruction courante et exécute un programme se trouvant à une adresse prédéfinie.
Ce programme, le gestionnaire d’interruption, reçoit une copie des valeurs courante des registres, ainsi qu’un code numérique lui permettant de savoir quel est le type de l’interruption qui a stoppé le processeur.
On utilise les interruptions, principalement dans deux buts :
-
permettre des communications non bloquantes avec des périphériques externes ;
-
commuter entre les tâches dans un ordonnanceur.
Les interruptions constituent le fondement de l’exécution concurrente des programmes.
Vocabulaire
- Exécutable
- Fichier binaire contenant des instructions en langage machine directement exécutables par le processeur de la machine.
- Processus
- Instance du programme en cours d’exécution. Un système d’exploitation identifie généralement les processus par un numéro unique.
Un processus est décrit par :
-
L’ensemble de la mémoire allouée par le système d’exploitation pour l’exécution du programme (instructions codées et données manipulées, qu’elles soient contenues dans la pile ou sur le tas) ;
-
L’ensemble des ressources utilisées par le programme (fichiers ouverts, connexions réseau, etc.) ;
-
Les valeurs stockées dans tous les registres du processeur.
- Thread ou tâche
- Éxécution d’une suite d’instructions démarrée par un processus. Deux processus sont l’exécution de deux programmes différents (traitement de texte et navigateur web, par exemple). Deux threads sont l’exécution concurrente de deux suites d’instructions d’un même processus (téléchargement d’une page web et affichage d’une page web).
- Exécution concurrente
- Deux processus ou threads s’exécutent de manière concurrente s’ils se partagent l’accès à un processeur. Ils ne s’exécutent donc pas au même moment.
- Exécution parallèle
- Deux processus ou threads s’exécutent en parallèle s’ils s’exécutent au même instant. Plusieurs processeurs dans l’ordinateur sont donc nécessaires à une exécution parallèle.
Nom | Description |
---|---|
PID | Process ID, l’identifiant numérique du processus |
État | L’état dans lequel se trouve le processus |
Registres | La valeur des registres lors de la dernière interruption |
Mémoire | Zone mémoire (plage d’adresses) allouée par le processus lors de son exécution |
Ressources | Liste des fichiers ouverts, connexions réseau en cours d’utilisation, etc. |
Informations pour la description d’un Processus.
Ordonnanceur du système d’exploitation
Exemple
-
Le processus « traitement de texte » a accès au processeur. Il est en cours d’exécution.
-
Une interruption d’horloge se déclenche.
-
Le code du gestionnaire d’interruption est appelé. Il reçoit comme arguments les valeurs de tous les registres avant le déclenchement de l’interruption (donc tout ce qui concerne le processus ayant accès au processeur).
-
Le gestionnaire d’interruption sauvegarde ces valeurs à un endroit particulier de la mémoire.
-
Le gestionnaire d’interruption choisit dans la liste des processus un processus en attente, par exemple celui correspondant à un navigateur web.
-
Il restaure les valeurs des registres qu’il avait sauvegardés lors de la dernière interruption du navigateur web.
Parmi ces registres, il y a en particulier IP, le pointeur d’instruction, qui contient l’adresse de la prochaine instruction à exécuter. -
Le gestionnaire d’interruption a fini son travail et « rend la main ». Le processeur exécute le code du processus lié au navigateur web jusqu’à la prochaine interruption.
Afin de pouvoir décider à quel processus donner la main, l’ordonnanceur utilise une structure de données telle qu’une file pour stocker la liste des processus et ainsi partager les tâches.
États d’un processus
La plupart des systèmes d’exploitation définissent différents états pour les processus :
- Nouveau
- État d’un processus en cours de création. Le système d’exploitation vient de copier le code exécutable en mémoire.
- Prêt
- Le processus est dans la file des processus à exécuter et attend d’être choisi par l’ordonnanceur.
- En exécution
- Le processus est en train d’être exécuté.
- En attente
- Le processus est en interrompu et en attente d’un évènement externe (entrée/sortie, allocation mémoire, etc).
- Terminé
- Le processus est terminé. Le système d’exploitation est en train de désallouer les ressources que le processus utilisait.
L’ordonnancement
Plusieurs processus peuvent donc être dans l’état prêt : comment choisir celui qui sera élu ?
Il existe plusieurs politiques d’ordonnancement dont le choix va dépendre des objectifs du système.
Quelques exemples :
-
Premier arrivé, premier servi : simple, mais peu adapté à la plupart des situations.
-
Plus court d’abord : très efficace, mais il est la plupart du temps impossible de connaître à l’avance le temps d’exécution d’un processus.
-
Priorité : le système alloue un niveau de priorité aux processus (SCHED_FIFO sur Linux). Cependant des processus de faible priorité peuvent ne jamais être élus.
-
Tourniquet : un quantum de temps est alloué à chaque processus (SCHED_RRsous Linux). Si le processus n’est pas terminé au bout de ce temps, il est mis en bout de file en état prêt.
-
Un système hybride entre tourniquet et priorité qu’on retrouve dans les systèmes Unix.
Commandes Unix de gestion des processus
ps
(process status) est la commande de base pour lister tous les processus en cours. Options utiles :
a
: tous les processus ;u
: nom des utilisateurs qui ont lancé le processus ;x
: fait aussi apparaître les processus qui n’ont pas été lancés depuis la ligne de commande.
|
|
La colonne STAT
l’état du processus :
R
(Running ou Runnable) : le processus est dans l’état Prêt ou En exécution.S
(Sleeping) : le processus est En attente.
top
permet en temps réel les processus en cours.
|
|
Le processus qui monopolise le plus le processeur apparaît dans la première ligne.
init
ou systemd
sur Linux). Son rôle est par la suite de démarrer tous les autres processus.
pstree
.
|
|
L’exemple précédent montre que l’utilisateur ubuntu a accédé au serveur ubuntu par ssh et a lancé depuis le terminal (en ligne de commande donc) deux commandes qui s’exécutent en parallèle pstree
et top
. Les processus ont été créés par le processus bash
.
kill
envoie un signal de terminaison aux processus dont le PID est passé en argument.
|
|
Programmation concurrente
Processus concurrents
Remarque : cette partie nécessite une bonne compréhension des sections 1.4, 1.5 et 1.6 de ce document.
- Écrire le programme Python suivant :
|
|
- À quoi sert la fonction
getpid
?
Réponse
La fonction getpid
retourne le PID du processus qui la lance.
- À quoi sert la fonction
flush()
?
Réponse
La fonction flush
donne un ordre d’écriture immédiate des caractères dans le fichier.
- Prévoir ce que doit contenir le fichier.
Lancer le programme et vérifier la correction de la prédiction.
Réponse
Le fichier est constitué de 1000 lignes de la forme PID : i
.
La première ligne est par exemple 418 : 0
La dernière ligne du même fichier est alors 418 : 999
.
- Depuis la console (shell), lancer trois fois le programme en une commande, en plaçant l’exécution de ces programmes en arrière plan (c’est le rôle de l’esperluette
&
).
|
|
Relever les PID des processus.
- Examiner le contenu du fichier
test.txt
et recommencer plusieurs fois l’opération. Quelles remarques peut-on faire ? Essayer de justifier ce comportement.
Réponse
-
On a l’impression que certaines lignes n’ont été écrites que par certains des processus et le choix du processus qui a écrit la ligne en question semble être aléatoire. Ils semblent s’être réparti les travaux d’écriture alors qu’ils fonctionnent indépendamment les uns des autres !!!
-
Justification. Chaque processus, lors de l’ouverture du fichier, enregistre la position du curseur d’écriture. À chaque écriture de caractères, ce curseur est avancé du nombre de caractères (octets en fait) correspondant.
Chaque fois qu’un processus est interrompu par l’ordonnanceur, il conserve en mémoire son état, en particulier la position du curseur au moment de l’interruption. Lorsqu’il est à nouveau appelé par la suite il reprend donc depuis cette position… et peut donc écraser les entrées des autres processus si ces derniers étaient plus avancés.
Interblocage
Exemple 1
Trois élèves doivent réaliser lors d’un cours de math un travail à l’aide d’une règle et d’une équerre. Le premier élève n’a apporté qu’une règle, le deuxième qu’une équerre et le troisième a oublié toutes ses affaires.
-
Que devront-ils faire pour réaliser le travail demandé par le professeur ?
-
Des processus peuvent-ils procéder de la sorte (s’il n’ont pas été programmés pour) ?
Réponses
-
Les élèves doivent discuter et se mettre d’accord sur une stratégie d’utilisation du matériel.
-
Un processus d’enregistrement du son qui utilise une carte fonctionne de façon indépendante d’un processus qui diffuse du son à travers cette même carte réseau. Aucun dialogue n’existe entre les deux.
Exemple 2
Sur une route à deux sens, des travaux occupent la moitié de la route. Des véhicules roulant dans les deux sens se sont engagés simultanément et se retrouvent face à face. Plusieurs véhicules les ont suivis ; plus personne ne peut reculer. Le véhicule venant de la gauche occupe la partie de la route dont l’accès serait nécessaire au véhicule venant de la droite et inversement.
Exercice 3
Le même blocage peut intervenir dans un rond-point lorsque le traffic est dense si personne ne souhaite sortir à la première sortie mais plutôt à la sortie en face de l’entrée.
L’origine de l’interblocage est l’accès exclusif à certaines ressources.
Exemple d’interblocage
-
Un processus $p_1$ possède un accès exclusif à la ressource $R_1$ alors qu’un processus $p_2$ possède un accès exclusif à une ressource $R_2$.
-
Le processus $p_1$ a alors besoin d’un accès à la ressource $R_2$ avant de pouvoir libérer $R_1$. Comme la ressource $R_2$ est occupée, ce processus est placé dans l’état En attente.
-
Le processus $p_2$ passe dans l’état En exécution et essaie d’accéder à la ressource $R_1$, sans avoir encore libéré $R_2$. Comme $R_1$ n’a pas encore été libéré par $p_1$, la ressource n’est pas accessible et $p_2$ est placé En attente.
-
Le processus $p_1$ passe dans l’état En exécution et essaie d’accéder à la ressource $R_2$. cette dernière n’est pas accessible et $p_1$ est placé En attente.
-
Le processus $p_2$ passe dans l’état En exécution et essaie d’accéder à la ressource $R_2$. cette dernière n’est pas accessible et $p_2$ est placé En attente.
-
….
Illustration d’une situation d’interblocage en Python
- Écrire le programme suivant :
|
|
- Étudier le programme. Expliquer le rôle des deux dernières lignes.
Réponse
Ce programme utilise des threads pour réaliser l’exécution en parallèle de la fonction hello
.
- Exécuter le programme. L’affichage est-il surprenant ?
Réponse
Comme pour les processus, les threads alternent leur exécution en fonction des commutations de contexte. L’ordre dans lequel sont démarrés les threads ne donne aucune indication sur l’ordre dans lequel ils peuvent se terminer.
- Écrire le programme suivant :
|
|
- Expliquer le rôle de l’instruction
global COMPTEUR
.
Réponse
COMPTEUR
est une variable globale, accessible depuis une fonction mais non modifiable.
Pour outrepasser ce comportement, il faut utiliser le mot clé globla
. On peut alors modifier la valeur de la variable depuis la fonction.
- Expliquer le rôle de l’instruction
t.join()
.
Réponse
Attend que le fil d’exécution se termine. Ceci bloque le fil appelant jusqu’à ce que le fil dont la méthode join
est appelée se termine – soit normalement, soit par une exception non gérée – ou jusqu’à ce que le délai optionnel timeout soit atteint.
- Exécuter le programme. L’affichage est-il surprenant ?
Réponse
Comme on a démarré 4 threads et que chacun d’eux effectue 100 000 tours de boucles, on pouvait s’attendre à ce que la valeur finale soit égale à 400 000. Ce n’est pas le cas.
- Expliquer la valeur finale obtenue.
Réponse
Lorsqu’un thread est interrompu par la commutation de contexte, son état est conservé. Lorsque ce thread reprend son travail, il utilise la valeur de COMPTEUR
lors de son arrêt et ne prend pas en compte les incrémentations réalisées par les autres threads alors qu’il était dans l’état En attente.
- Écrire le programme suivant :
|
|
-
Expliquer pourquoi on obtient bien maintenant la valeur 400000.
-
Écrire le programme suivant :
|
|
-
Quelle situation essaie-t-il d’illustrer ? Justifier la réponse.
-
Exécuter le programme plusieurs fois. La situation prévue à la question précédente intervient-elle vraiment ? Pourquoi ?
-
Ajouter les lignes
|
|
au dessous de l’instruction print("Section critique 1.1")
.
Expliquer pourquoi le comportement du programme a été modifié.