ASR2 - Gestion des processus et des ressources¶

0 - Rappels¶

0.1 Exécution d'un programme¶

Un programme est une suite d'instructions élémentaires ayant vocation à être exécutées par une machine. On parle d'exécutable lorsque ce programme est écrit en langage machine, directement lisible par la machine.

Le langage machine est écrit directement en binaire et est propre au processeur utilisé. Il se lit comme une succession de mots binaires, les commandes, de longeur fixe (généralement 32 ou 64 bits : ARM, MIPS) ou variable (x86). Ces commandes se décomposent ainsi :

• une partie du mot (généralement le début) constitue le code opération ou opcode de la commande et indique au processeur quelle opération (addition, lecture ou écriture mémoire, comparaison, etc.) il doit effectuer ;
• le reste du mot correspond aux arguments de la commande (adresse mémoire de lecture, registre à utiliser, nombre binaire à ajouter etc.).

Par exemple, sur les processeurs d'architecture MIPS (32 bits) on peut utiliser la commande suivante :

000000 00001 00010 00110 00000 100000
op rs rt rd shamt fonct

On a donné des noms aux différentes parties de constitutives de cette commande :

• op = 000000 et fonct = 100000 indiquent au processeur qu'il doit effectuer une addition ;
• rs = 00001 et rt = 00010 lui indiquent qu'il doit effectuer l'addition des contenus des registres 1 et 2 ;
• rd = 00110 indique que le résultat doit être stocké dans le registre 6 ;
• shamt = 00000 indique qu'il ne doit pas appliquer de décalage au résultat.

Remarque : Pour chaque langage de programmation, il existe un programme appelé compilateur dont le rôle est de traduire les programmes de ce langage en langage machine. Certains langages (comme C) sont utilisés avec un compilateur seul qui crée l'exécutable d'un programme une bonne fois pour toute, exécutable pouvant être exécuté ensuite. Pour d'autres (comme Python) on utilise un interpréteur qui se charge à la fois de la compilation et de l'exécution du programme. En Python, un programme est donc compilé à chacune de ses exécutions.

Lorsqu'une machine exécute un programme (exécutable), elle en lit et exécute les commandes une par une en suivant le cycle d'exécution.

La vidéo suivante explique plus en détail le fonctionnement de ce cycle.

0.2 - Système d'exploitation¶

Lorsqu'on démarre un ordinateur, un premier programme partiulier est lancé : le système d'exploitation souvent abrégé en OS : operating system. Il en existe de nombreux plus ou moins spécialisés dans l'exploitation de différents types de machines, libres ou non. Parmis les plus connus on trouve Windows, GNU/Linux et MaxOS pour les ordianteurs de bureau et Android et iOS pour les smartphones et tablettes.

Le système d'exploitation a pour objectif de faciliter l'utilisation de la machine par les utilisateurs et les autres programmes en leurs offrant un certain nombre de services :

• utilisation de périphériques (claviers, souris, écran, lecteurs, etc.) ;
• gestion des fichiers (arborescence) et des permissions ;
• allocation des ressources (quel programme utilise le processeur, la carte graphique, un périphérique ?) ;
• etc.

Le service d'allocation des ressources doit permettre aux programmes de se partager l'utilisation de la machine. Plus précisément, le système d'explotation va décider (en fonction des demandes de l'utilisateur) quel autre programme doit être exécuté.

0.3 - Lancement d'un programme par le système d'exploitation (mono-tâche)¶

Lorsqu'on demande au système d'exploitation d'exécuter un programme, celui-ci va effectuer plusieurs opérations :

1. allouer de l'espace mémoire au programme dans la mémoire vive ;
2. copier dans cet espace le code du programme en partant d'une certaine adresse ;
3. ecrire cette adresse dans le registre IP du processeur afin que celui-ci démarre l'exécution.

Une fois le programme terminé, celui-ci redonne la main au système d'exploitation en écrivant une certaine adresse dans le registre IP du processeur.

Pour donner un exemple concret considérons un système d'exploitation, disons Debian, ainsi que deux programmes que l'utilisateur veut exécuter, disons Firefox et VLC.

• au démarrage de la machine, Debian est chargé dans la RAM et exécuté ;
• l'utilisateur demande à Debian de lancer Firefox ;
• Debian alloue de l'espace mémoire disponible à Firefox et lui donne la main ;
• Firefox s'exécute puis rend la main à Debian ;
• l'utilisateur demande à Debian de lancer VLC ;
• Debian alloue de l'espace mémoire disponible à VLC et lui donne la main ;
• VLC s'exécute puis rend la main à Debian.

Pour résumer¶

• un fichier exécutable est un programe écrit en langage machine ;
• le langage machine est un langage écrit en binaire interprété directement par le processeur ;
• pour chaque langage de programmation, un compilateur est chargé de traduire les programmes en langages machines ;
• le système d'exploitation est un des premiers programmes chargés lorsqu'on lance un machine ;
• il a pour rôle, entre autre, d'allouer les ressources disponibles aux autres programmes qui en ont besoin.

1- L'ordonnanceur de processus¶

Le mode de fonctionnement décrit plus haut permet bien au système d'exploitation d'excuter plusieurs programmes. Cependant, il ne permet pas de les exécuter simultanément, on parle d'd'exécution concurrente. Il s'agît là d'un point essentiel : imaginez travailler avec une machine qui ne peut exécuter qu'un seul programme à la fois : pas de navigateur internet pour vous aider à coder, pas de discussion vocale pendant que vous jouez à un jeu en ligne, etc.

La partie du système d'exploitation chargée de contourner ce problème est appelée un ordonnanceur de processus.

1.1 - Processus, PCB¶

Un processus est un programme en cours d'exécution. Il est décrit à un instant $t$ par les caractéristiques suivantes :

• son PID (Process ID) : l'identifiant numérique du processus ;
• son état : nouveau, prêt, en exécution, en attente ou terminé) ;
• les valeurs stockées dans les registres du processeur ;
• l'ensemble de la mémoire qui lui est allouée ;
• la liste des ressources qu'il utilise (fichiers ouverts, connexion réseau, périphériques, etc.).

L'ensemble de ces informations est appelé le PCB (Process Control Bloc) du processus. Pour chaque nouveau processus, l'ordonnanceur génère et sauvegarde à un certain endroit de la mémoire un nouveau PCB, qu'il supprime dès que le processus est terminé.

Le PCB permet notamment de partager la RAM en plusieurs zones dédiées à l'exécution de différents programmes et éventuellement de "sauvegarder" l'état courrant d'un processus.

1.2 - Interruptions¶

Il existe de plusieurs moyens d'interromptre un processus. Par exemple, en Python :

• un erreur non-rattrapée interrompt définitivement l'exécution du programme ;
• une interruption clavier par l'utilisateur (Ctrl+C sur IDLE) a le même effet ;
• un input interrompt l'exécution du programme tant que l'utilisateur n'a pas entré de valeur.

Ces différentes interruptions qui peuvent terminer ou mettre en pause l'exécution du programme sont gérées par un programme appelé gestionnaire d'interruptions.

Le gestionnaire d'interruptions dispose d'un type d'interruption bien particulier appelé interruption horloge. Cette interruption a lieu automatiquement à intervalle de temps régulier (typiquement une fois toute les 100ns) et met en pause le processus en cours sur le processeur pour rendre la main au système d'exploitation et plus précisément à l'ordonnanceur.

1. Celui-ci met à jour le PCB du processus interrompu et décide d'un autre processus à reprendre jusque la prochaine interruption.
2. Puis, il charge dans les registres du processeur l'ensemble des valeurs enregistrées dans le PCB du nouveau processus.
3. Il redonne la main au nouveau processus qui reprend donc son exécution.

On appelle cela une commutation de contexte.

Ce fonctionnement permet donc de répartir l'utilisation du processeur sur plusieurs processus à la fois, les uns après les autres : chaque processus peut travailler 10ns avant de rendre la main à un autre. Cela donne l'impression que tous les processus fonctionnent en même temps, l'oeuil et le cerveau humain ne parvenant pas à distinguer des intervalles de temps aussi petits !

Remarque : l'exécution concurrente générère une illusion de simultanéité des processus. En particulier, elle ne permet pas de travailler plus vite, au contraire ! Pour véritablement exécuter plusieurs programmes en même temps, on utilise plusieurs processeurs ou plusieurs coeurs.

On peut résumer le cycle de vie d'un processus sur le schéma suivant :

Pour résumer¶

• Un système d'explotation (Windows, MacOS, GNU/Linux) permet entre autre d'exécuter plusieurs programmes "en même temps" sur une seule machine.
• On parle de processus pour désigner un programme en cours d'exécuhtion.
• Les processus sont exécutés en concurrence sur un seul processeur, c'est à dire que chaque processus peut travailler sur celui-ci pendant un certain temps avant de laisser la place à un autre.
• Le gestionnaire d'exceptions est chargé d'interromptre le processus en cours exécucution à intervalle de temps régulié via des interruptions horloge.
• L'ordonnanceur de processus du système d'exploitation décide ensuite à chaque instant de redonner la main à tel ou tel processus.

2 - Threads Python¶

Pour illustrer en quoi l'exécution concurentielle des processus peut être compliquée à gérer, nous allons introduire la programmation multithreadée en Python.

Les thread, ou processus légers sont des sous-processus qu'on peut générer à l'intérieur d'un programme. Ils sont exécuté au sein d'un même processus mais en concurrence les uns avec les autres.

2.1 - Créer un thread en Python¶

On peut créer et utiliser des threads en python grace au module threading.

Le programme précédent crée quatre objets Thread. Pour définir un thread, ont donne :

• la fonction que le thread doit appeler; ici target = hello ;
• les arguments sur lesquels la fonction est appelée sous la forme d'un tableau, ici args = [n].

La méthode start permet alors de démarrer le thread.

Comme on peut l'observer sur l'exemple ci-dessus, les threads ne s'exécutent pas toujours dans le même ordre, parfois un thread ne termine pas sont exécution avant de laisser la main à un autre. Comme les processus, les threads fonctionnent de manière concurente.

2.2 - Attente et verrou¶

Voyons un autre exemple : on veut quatre threads incrémentant chacuns la valeur d'un seul et même compteur global un certain nombre de fois. Esayons un premier programme :

Ce programme a l'air de fonctionner. Nos quatre threads ajoutent 1000 à COMPTEUR et on obtient 4000.

Cependant, lorsque'on modifie légèrement le programme, on se rend compte qu'il n'est pas satisfaisant. En remplaçant 1000 par 1000000 par exemple. Lorsqu'on fait cela, le résultat n'est plus le bon, que ce passe-t-il ?

Un premier problème vient du fait que la méthode start démarre le thread puis rend la main au processur principal. Ici, les quatre thread démarrent mais n'ont pas le temps de terminer avant le print. On peut le vérifier en ajoutant un print à la fin de la fonction incr.

Pour régler ce problème, on peut indiquer au programme principal d'attendre que le threads soient terminés à l'aide de la méthode join. Notez bien que ceci a uniquement un effet sur le programme principal, les thread sont toujours exécutés de manière concurrente.

Cette fois tout va bien. Presque... Modifions encore un peu le programme :

Le problème est ici plus subtile et provient de la commutation de contexte ayant lieu entre les threads.

Comme pour les processus, les threads se déroulent opération par opération pendant un certain temps avant de passer la main à un autre thread. À ce moment, les valeurs des différentes variables du threads sont sauvegardées à un endroit de la mémoire pour être reprises ensuite.

Dans notre programme, imaginons que cette commutation ait lieu pour un thread t entre les commandes v = COMPTEUR et COMPTEUR = v+1 : la valeur v = COMPTEUR est sauvegardée jusque la reprise de t. C'est un problème car entre temps, les autres threads ont augmenté la valeur du compteur et la commande COMPTEUR = v+1 ne correspond plus à une incrémentation.

Pour régler ce problème, il faudrait pouvoir spécifier à Python de ne jamais interrompre nos threads entre ces deux commandes critiques. On utilise pour cela des verrous :

On retrouve la bonne valeur finale !

Un verrou peut être vu comme un objet qui peut être associé à un thread (et à un seul) et qui lui donne le droit de continuer.

La méthode v.acquire() essaie d'acquérir le verrou :

• s'il est déjà possédé par un autre thread, la méthode ne fonctionne pas et le thread est mis en attente ;
• s'il n'est possédé par personne, le thread en fait l'acquisition et peut passe à la suite de son code.

La méthode v.release() libère le verrou afin que d'autres threads puissent l'utiliser.

Comme on l'a vu dans l'exempple précédent, un verrou peu servir à "protéger" une partie du code d'un processus, alors nommée section critique qui ne pourra être exécutée que par un thread à la fois.

2.3 - Verrous multiples, interblocage¶

Il est tout à fait possible de créer plusieurs verrous. Par exemple :

Cependant, ces deux verrous n'intéragissent pas ensemble. En effet, le thread t1 nécessite pour s'exécuter d'acquérir verrou1 ce qu'il pourra toujours faire puisque celui-ci n'est pas contesté par t2. Ces deux verrous sont donc ici parfaitement inutiles.

En revanche, s'il y avait eu plus de threads appelant f1 ou f2, alors le fait que les deux sections critiques soient protégées par des verrous différents a son intérêt : si la section critique 1 n'a aucun effet sur la section critique 2, il n'y a pas de raison de bloquer l'exécution de l'une lorsque l'autre est exécutée.

Voyons maintenant un problème classique pouvant apparaître en programmation concurentielle : l'interblocage.

Le programme ci-dessus peut très bien se dérouler, par exemple si le premier thread s'exécute complétement avec de laisser la main au second.

Mais il est aussi possible que se programme ne termine pas. Pour cela il suffit que les threads s'exécutent comme suit :

• t1 acquière verrou1 et entre dans la section critique 1.1 ;
• t1 est interrompu par l'horloge et passe la main à t2 ;
• t2 acquière verrou2 et entre dans la section critique 1.2 ;
• à partir de ce point, nos thread sont en situation d'interblocage (ou deadlock), ils se bloquent l'un autre. En effet, pour continuer, t1 a besoin de verrou2 détenu par t2, mais pour continuer et éventuellement libérer verrou2, t2 a besoin de verrou1 qui est détenu par t1. Le résultat est que les deux thread vont attendre indéfiniment que l'autre libère son verrou.

En fait, on peut retrouver des situations l'interblocage pour n'importe quel ensembles de processus ou thread tant que ceux-ci partages des ressources communes et sous certaines conditions, appelées conditions de Coffman :

1. il existe une ressource exclusive (qui ne peut être utilisée par un seul processus ou thread à la fois) ;
2. un processus ou thread tenant une ressource et en attendant une autre ne la libère pas ;
3. non-préemption : une ressource ne peut être rendue que par le processus qui la détient ;
4. attente circulaire : pour $n$ processus ou threads $P_1$, ..., $P_n$, on a une situation où $P_1$ attend une ressource tenue par $P_2$ qui attend une ressource tenue par $P_3$ ... $P_n$ qui attend une ressource tenue par $P_1$.

Dans le cas des threads, les verrous sont les ressources exclusives.

Pour résumer¶

• un thread ou processus léger est un sous-processus ;
• t = threading.Thread(target = ..., args = [...]) crée un thread t ;
• target représente la fonction que le thread doit exécuter ;
• args représente les arguments passés à la fonction exécutée par le thread ;
  • la méthode t.start() démarre le thread t (il n'est pas exécuté sinon) ;
• les threads sont exécutés comme les processus en concurrences au sein de leur programme ;
• la méthode t.join() indique au processus principal qu'il doit attendre la fin du thread t avant de passer à la suite ;
• v = threading.Lock() crée un verrou ;
• on utilise un verrou v en écrivant des instruction entre les appels des méthodes v.acquire()et v.release() ;
• un thread ne peut pas être interrompu lorsqu'il exécute les instructions dans un verrou ;
• lorsqu'on définit plusieurs verrous, on peut générer des situations d'interblocage (deadlock) ;
• un interblocage peut advenir lorsque le condition de Coffman sont réunies.

Commandes UNIX processsus¶