13

Synchronisation et communication entre processus

Nous avons déjà dit que, si les processus étaient des entités autonomes et indépendantes, ils pouvaient se trouver en conflit pour l'accès à certaines ressources communes. Ceci nécessite la mise en œuvre de mécanismes dits de synchronisation pour gérer ces conflits. Par ailleurs, si les processus sont en général indépendants, cela ne doit pas interdire la communication. La conséquence de ces mécanismes est le blocage des processus en attente d'une ressource momentanément indisponible. Deux problèmes en découlent: l'interblocage et la famine.

13.1. Les mécanismes de synchronisation

Considérons un compte bancaire, dont le montant est mémorisé dans un emplacement donné A sur disque. Le programme qui consiste à ajouter 100 à ce compte pourrait être le suivant, où N est une variable locale du programme:
			lire (N, A);
			N := N + 100;
			écrire (N, A);
Si maintenant deux processus différents consistent en l'exécution de ce même programme, le processeur sera alloué à chacun d'eux dans un ordre quelconque. En particulier, on peut imaginer que l'ordre soit le suivant:
			processus P1			processus P2
			lire (N, A);
								lire (N, A);
								N := N + 100;
								écrire (N, A);
			N := N + 100;
			écrire (N, A);
N étant une variable locale du programme, implique qu'il en existe un exemplaire pour chacun des deux processus. Il s'ensuit que, si la valeur initiale du compte est 1000, on constate qu'après ces exécutions, il est de 1100 au lieu de 1200. Les deux processus ne sont pas en fait totalement indépendants. Ils partagent la ressource commune qu'est la valeur du compte bancaire à l'adresse A sur disque. Cette ressource doit être à un seul point d'accès, c'est donc une ressource critique, et les processus sont en exclusion mutuelle sur cette ressource critique.
Si la variable N est commune aux deux processus, le problème n'est pas résolu pour autant. En effet l'instruction N := N + 100 n'est pas une instruction “indivisible”. En fait elle est décomposée en trois instructions de la machine qui sont par exemple:
			LOAD		N
			ADD		100
			STORE	N
L'allocateur du processeur prend en compte les instructions de la machine et non les instructions du langage évolué pour déterminer les moments où il peut remplacer le processus actif par un autre. En particulier, dans cet exemple, il est possible que le changement ait lieu juste après la première instruction, donnant la séquence suivante:
			processus P1			processus P2
			LOAD		N
								LOAD		N
								ADD		100
								STORE	N
			ADD		100
			STORE	N

13.1.1. Les verrous

Un mécanisme proposé pour permettre de résoudre l'exclusion mutuelle d'accès à une ressource est le mécanisme de verrou (en anglais lock). Un verrou est un objet système sur lequel deux opérations sont définies. Un tel objet peut s'assimiler à une ressource logiciel, les opérations permettant d'acquérir ou de libérer cette ressource.
En tant qu'opérations systèmes, ces opérations sont indivisibles, c'est-à-dire que le système garantit l'absence d'interférence entre leurs exécutions par plusieurs processus. On dit encore que ce sont des primitives.

13.1.2. Les sémaphores

Un sémaphore est un mécanisme proposé par E.W.Dijkstra en 1965, et qui est un peu plus général que le verrou. Il se présente comme un distributeur de jetons, mais le nombre de jetons est fixe et non renouvelable: les processus doivent restituer leur jeton après utilisation. S'il y a un seul jeton en circulation, on retrouve le verrou. Les deux opérations sur un sémaphore sont traditionnellement dénotées P(s) et V(s), mais cette notation est de peu de signification pour ceux qui parlent le Hollandais, et aucune pour les autres[1]!
Notons qu'un sémaphore peut être vu comme un couple constitué d'un entier, encore appelé le niveau du sémaphore et d'une file d'attente de processus. Le niveau est le nombre de jetons encore disponibles. Il est évident que si le niveau est positif, la file d'attente est vide. Parfois on utilise les valeurs négatives du niveau pour représenter le “déficit” en jetons, c'est à dire le nombre de processus en attente de jeton.
À la création d'un sémaphore, il faut décider du nombre de jetons dont il dispose. On voit que si une ressource est à un seul point d'accès (critique), le sémaphore doit avoir initialement 1 jeton, qui sera attribué successivement à chacun des processus demandeurs. Si une ressource est à n points d'accès, c'est-à-dire, peut être utilisée par au plus n processus à la fois, il suffit d'un sémaphore initialisé avec n jetons. Dans les deux cas, un processus qui cherche à utiliser la ressource, demande d'abord un jeton, puis utilise la ressource lorsqu'il a obtenu le jeton et enfin rend le jeton lorsqu'il n'a plus besoin de la ressource.

13.1.3. Les mécanismes plus élaborés

Les mécanismes proposés ci-dessus sont assez rudimentaires. Ils posent deux problèmes:
Le premier problème peut être résolu en construisant un algorithme plus ou moins complexe, qui utilise une zone de mémoire commune aux processus et des sémaphores pour assurer la synchronisation. La figure 13.1 donne un exemple où l'on distingue deux sortes de processus qui accèdent à un même fichier, les “lecteurs” qui exécutent une suite de lectures sur le fichier, et les “rédacteurs” qui exécutent une suite de lectures et d'écritures. Les morceaux de programme correspondants montrent une façon de garantir qu'un rédacteur accède seul au fichier, alors que les lecteurs peuvent y accéder ensembles.
						initialisation
						mutex.niveau := 1;
						lect_redac.niveau := 1;
						n_l := 0;
			processus lecteurs			processus rédacteurs
			down(mutex);
			n_l := n_l + 1;
			si n_l = 1 alors
				down(lect_redac);		down(lect_redac);
			finsi;
			up(mutex);
			...
			lectures					lectures et écritures
			...
			down(mutex);
			n_l := n_l - 1;
			si n_l = 0 alors
				up(lect_redac);		up(lect_redac);
			finsi;
			up(mutex);
Fig. 13.1. Exemple de synchronisation entre des lecteurs et des rédacteurs.
Deux sémaphores dotés chacun d'un seul jeton sont utilisés, ainsi qu'un compteur commun qui note le nombre de lecteurs en cours. Le jeton lect_redac est possédé soit par un rédacteur, soit par l'ensemble des lecteurs. C'est pourquoi, seul le premier lecteur demande ce jeton, qui est restitué par le dernier lecteur qui sort. Le deuxième sémaphore contrôle l'accès à la ressource critique n_l par les lecteurs.
Le deuxième problème évoqué ci-dessus est bien visible dans cet exemple: comment obliger les processus lecteurs ou rédacteurs à respecter la règle du jeu qui vient d'être décrite? La solution adoptée par certains systèmes est de définir plusieurs politiques de gestion de certaines ressources par le biais d'opérations spécifiques, et de contrôler le respect de la règle du jeu par les processus dans ces opérations.
Ainsi certains systèmes de gestion de fichiers ont un paramètre particulier de l'opération d'ouverture qui précise si le processus désire l'accès exclusif ou partagé au fichier.
Notons que ceci implique que le système exécute pour le compte du processus un algorithme voisin de celui d'un lecteur ou d'un rédacteur proposé plus haut.
De même, les SGBD prennent en compte les conflits d'accès aux données de la base, et obligent explicitement ou implicitement les processus à respecter une règle du jeu fixée par le SGBD ou par l'administrateur de la base de données. Du point de vue des processus, une règle du jeu implicite transforme la base de données en une ressource virtuelle au sens où nous l'avons défini dans le chapitre précédent, les processus pouvant y accéder comme s'ils étaient seuls.

13.2. La communication entre processus

Lorsque des processus ont besoin d'échanger des informations, ils peuvent le faire par l'intermédiaire d'une zone de mémoire commune. Nous en avons déjà vu un exemple lors de la présentation des lecteurs et des rédacteurs ci-dessus: les lecteurs accèdent au même compteur n_l. Cette communication présente l'inconvénient d'être peu structurée, et de nécessiter l'utilisation de l'exclusion mutuelle d'accès à cette zone commune. Par ailleurs elle pose des problèmes de désignation des données de cette zone qui doit être dans l'espace de chaque processus qui désire communiquer avec les autres.

13.2.1. Le schéma producteur-consommateur

On peut définir un mécanisme général de communication entre processus, où l'un est l'émetteur de l'information (on lui donne le nom de producteur), et l'autre est le récepteur de l'information (on lui donne le nom de consommateur). Il n'est souvent pas nécessaire de faire attendre le producteur jusqu'à ce que le consommateur ait reçu l'information. Pour cela il suffit de disposer d'un tampon entre les deux processus pour assurer la mémorisation des informations produites non encore consommées. Nous appellerons message le contenu d'une telle information. Le tampon peut recevoir un nombre limité de ces messages, noté N. Les deux processus doivent se synchroniser entre eux de façon à respecter certaines contraintes de bon fonctionnement. La figure 13.2 donne un schéma de cette synchronisation.
					initialisation
					n_plein.niveau := 0;
					n_vide.niveau := N;
		producteur						consommateur
		down(n_vide);					down(n_plein);
		dépôt dans le tampon;			retrait du tampon;
		up(n_plein);					up(n_vide);
Fig. 13.2. Le schéma producteur-consommateur.
Informellement, on peut dire que le producteur prend d'abord un jeton de place libre, dépose son message et rend un jeton de message disponible. De son côté, le consommateur prend un jeton de message disponible, retire le message et rend un jeton de place libre.
Pour obliger les processus à respecter la règle du jeu, les systèmes proposent souvent des opérations de dépôt et de retrait qui assurent elles-mêmes la synchronisation entre les processus.

13.2.2. Les tubes Unix

Les tubes Unix (en anglais pipes) sont une implantation de la communication suivant le schéma producteur-consommateur, avec un tampon de taille fixe, interne au système. Pour un processus, un tube se présente comme deux flots, l'un ouvert en écriture (pour le producteur), l'autre ouvert en lecture (pour le consommateur). Lorsqu'un processus crée un tube, le système lui retourne les deux flots. Si ce processus crée ensuite un processus fils (opération fork vue précédemment), celui-ci obtient une copie des flots ouverts, lui permettant ainsi de lire ou d'écrire dans le tube, à moins que l'un de ces flots n'ait été fermé. Ne peuvent donc communiquer par un tube que les processus situés dans la sous-arborescence dont la racine est le processus qui a créé ce tube.
Lors d'une écriture de n octets par le producteur, celui-ci sera mis en attente s'il n'y a pas assez de place dans le tube pour y mettre les n octets. Il sera réactivé lorsque les n octets auront pu être tous écrits dans le tube. Par ailleurs, le système interrompra l'exécution normale du processus s'il n'y a plus de consommateur pour ce tube.
Lors d'une lecture de p octets par le consommateur, celui-ci sera mis en attente s'il n'y a pas assez d'octets dans le tube pour satisfaire la demande. Il sera réactivé lorsque le nombre d'octets demandé aura pu lui être délivré. Par ailleurs, s'il n'y a plus de producteur pour ce tube, le système lui délivrera les octets restants, à charge pour le consommateur, lorsqu'il obtient un nombre d'octets nul, d'en déduire que la production est terminée.
La figure 13.3 donne un exemple de cette communication. Le processus père crée le tube et le processus fils, puis envoie dans le tube la suite des entiers de 0 à 1000, les entiers étant supposés sur 2 octets. Le processus fils lit les octets 2 par 2 depuis le tube dans un entier et imprime celui-ci. Il s'arrête lorsque le tube est vide et que le père a fermé le tube en écriture, puisque alors il n'y a plus de producteur.
	var tube: tableau [0..1] de flot;
	   i : entier;
	début pipe(tube);							  { création du tube }
		si fork() ≠ 0 alors				{ création du processus fils }
			fermer (tube[0]);			{ le père ne lit pas dans le tube }
			pour i := 0 jusqu'à 1000 faire
				écrire (tube[1], i, 2);		  { écriture de deux octets }
			fait;
			fermer (tube[1]);						{ le père a fini }
			wait(0);					 { attente de la fin du fils }
		sinon
			fermer (tube[1]);			{ le fils n'écrit pas dans le tube }
			tant que lire (tube[0], i, 2) = 2 faire
				imprimer (i); { on suppose qu'un entier occupe 2 octets }
			fait;
			fermer (tube[0]);						 { le fils a fini }
		finsi;
	fin;
Fig. 13.3. Communication par tubes Unix.
Les tubes Unix ne conservent pas la structuration des messages qui sont envoyés par le producteur. Dans l'exemple ci-dessus, producteur et consommateur participent tous les deux à cette structuration: le consommateur lit depuis le tube les octets 2 par 2 pour retrouver la structure des messages émis par le producteur. Notons que ceci est conforme à la philosophie déjà énoncée de ce système qui présente tout objet externe comme une suite linéaire d'octets. Cette uniformité présente l'avantage de cacher au programme la nature de l'objet externe manipulé, même lorsqu'il s'agit d'un tube.

13.2.3. La communication par boîte aux lettres

Nous appellerons boîte aux lettres un objet système qui implante le schéma producteur-consommateur défini plus haut, en conservant le découpage en messages tels que les a déposés le producteur. Les messages sont parfois typés, comme dans iRMX86, où les messages comportent un en-tête qui précise, en particulier, sa longueur et son type sous la forme d'un code défini par le programmeur.
Le problème de la désignation d'une boîte aux lettres par les processus est résolu de différentes façons. Il s'agit, en effet, de permettre à des processus dont les espaces mémoire sont disjoints de pouvoir désigner une même boîte aux lettres. Une solution comme celle proposée par Unix pour les tubes, peut être retenue, qui consiste à mettre cette désignation dans le contexte des processus au moment de leur création. On préfère, en général, une solution semblable à une édition de liens, qui consiste à donner un nom symbolique aux boîtes aux lettres, sous forme d'une chaîne de caractères. Le système maintient une table de ces noms symboliques associés aux boîtes aux lettres qui ont déjà été créées et non encore détruites. Lorsqu'un processus demande l'accès à une telle boîte aux lettres, le système consulte cette table, et retourne au demandeur le descripteur de la boîte aux lettres (c'est, par exemple, son indice dans le table). Les opérations suivantes se feront en utilisant ce descripteur. Dans certains cas, cette demande d'accès entraîne sa création implicite si elle n'existe pas, alors que d'autres systèmes séparent l'opération de création explicite de la demande d'accès.
Les opérations sur une boîte aux lettres sont l'envoi et la réception de message. L'envoi peut être avec ou sans blocage du demandeur lorsque la boîte aux lettres est pleine. La réception peut être également avec ou sans blocage lorsque la boîte aux lettres est vide. De plus, certains systèmes permettent de filtrer les messages reçus, c'est-à-dire, qu'il est possible de préciser le type des messages que l'on accepte de recevoir.
Les boîtes aux lettres ont souvent une capacité limitée de messages, comme nous l'avons indiqué dans le schéma général. Parfois cette capacité est nulle, l'envoi de message ne pouvant avoir lieu que lorsque le receveur est prêt à recevoir le message. Constatons que le schéma précédent doit être modifié; nous en laissons le soin au lecteur. On dit alors qu'il y a communication synchrone entre le producteur et le consommateur. L'intérêt essentiel est que cette fois, après le retour de la primitive d'envoi, le producteur a la garantie que le consommateur a effectivement reçu le message, alors que dans le cas général, le producteur ne peut préjuger du moment où cette réception aura lieu. En contrepartie, les processus supportent une contrainte de synchronisation plus forte.

13.3. Les conséquences sur les temps de réponse

Dans les premiers chapitres, nous avons défini le temps de réponse comme le délai qui sépare l'envoi d'une commande par un utilisateur, de la fin d'exécution de la commande. Nous pouvons ici décomposer ce délai en trois mesures différentes, suivant les états du processus correspondant.
Dans l'état actif, on mesure le temps de processeur (le temps virtuel) nécessaire à l'exécution proprement dite de la commande. Ce temps est évidemment incompressible, pour un programme donné. L'algorithme de la commande elle-même doit être efficace pour minimiser ce temps.
Dans l'état prêt, on mesure le temps pendant lequel le processus attend le processeur, ressource possédée par un autre processus. L'idéal, pour l'utilisateur, est de réduire le plus possible ce temps. C'est en quelque sorte le prix qu'il doit payer pour ne pas avoir à payer plus cher la machine. Sur un système normalement chargé, ce temps ne devrait pas être important. Si ce temps est important pour tous les processus, il est probable que ce soit l'indication d'un système surchargé, qui nécessite une augmentation de puissance.
Dans l'état bloqué, on mesure le temps pendant lequel le processus attend une ressource autre que le processeur. Cette attente peut avoir deux causes:

13.4. La notion d'interblocage

La synchronisation et la communication des processus peut conduire à un autre problème. Supposons qu'un premier processus P1 demande et obtienne la ressource imprimante, seule ressource de ce type. Un second processus P2 demande ensuite et obtient la ressource dérouleur de bande, également seule de ce type. Si P1 demande ultérieurement la ressource dérouleur de bande sans avoir libéré la ressource imprimante, il est bloqué en attendant la libération par P2 . Si maintenant, P2 demande la ressource imprimante avant de libérer la ressource dérouleur de bande, il est bloqué en attendant la libération par P1 de cette ressource. On voit que chacun des processus est bloqué, en attendant que l'autre libère la ressource qu'il possède. On dit qu'il y a un interblocage entre les processus (en anglais deadlock).
On peut donner une représentation graphique à l'interblocage. Représentons les ressources par des rectangles, et les processus par des cercles. On met une flèche d'une ressource vers un processus lorsque la ressource est allouée au processus, et une flèche d'un processus vers une ressource lorsque le processus attend cette ressource. La figure 13.4 représente l'évolution du graphe de notre exemple précédent conduisant à l'interblocage.

Fig. 13.4. Allocation conduisant à l'interblocage.
On peut constater que dans le graphe final, il y a un cycle représenté par:

En fait, tout interblocage est signalé par la présence d'un tel cycle dans ce graphe, et inversement, ce qui explique l'intérêt de cette représentation.
Le problème de l'interblocage est résolu de diverses façons par les systèmes.

Fig. 13.5. Évitement de l'interblocage.
La méthode utilisée dépend des applications qui sont les plus courantes sur le système. Par exemple, les systèmes d'IBM, mais aussi ceux de bien d'autres constructeurs, ont utilisé successivement plusieurs de ces méthodes. Après avoir appliqué la politique de l'autruche justifiée par le fait que les “plantages” du système étaient bien plus fréquents que les interblocages, la politique de prévention a été utilisée pour le traitement par lot. La politique d'évitement est également souvent utilisée pour le traitement par lot. Par contre, la plupart des systèmes transactionnels préfèrent la politique de détection-guérison, en détruisant une transaction qui demande une ressource si son blocage entraîne un cycle. Le noyau d'Unix utilise la politique de l'autruche, considérant que l'utilisateur qui constate un interblocage entre ses processus, peut toujours les tuer lui-même depuis sa console.

13.5. La notion de famine

Un processus qui est en attente d'une ressource peut rester bloqué indéfiniment sans être pour autant en situation d'interblocage. On dit que l'on a une situation de famine (en anglais starvation), lorsque un ou plusieurs processus n'obtiennent pas les ressources dont ils ont besoin par suite du comportement de l'ensemble des processus, sans être en situation d'interblocage. La différence essentielle réside dans le fait qu'il est possible de sortir de la situation de famine par suite du changement du comportement des processus, alors qu'il n'est pas possible de sortir d'un interblocage sans retirer autoritairement une ressource à un des processus en interblocage.
Reprenons l'exemple des lecteurs-rédacteurs que nous avons présenté plus haut. Supposons qu'aucun processus n'accède initialement au fichier. Lorsque le premier lecteur obtient le jeton lect_redac, il interdit à tous les écrivains de l'obtenir tant que le dernier lecteur ne l'a pas été libéré. Par contre les lecteurs peuvent toujours obtenir l'accès en lecture qu'ils désirent. Il peut s'en suivre une coalition des lecteurs de telle sorte qu'il y ait toujours un lecteur en permanence sur le fichier. Les rédacteurs n'obtiendront alors jamais satisfaction. Cependant, il ne s'agit pas d'un interblocage, puisque si les lecteurs s'arrêtent de travailler, le dernier libèrera le jeton lect_redac permettant ainsi aux rédacteurs d'obtenir l'un après l'autre satisfaction.
						initialisation
						équité.niveau := 1;
						mutex.niveau := 1;
						lect_redac.niveau := 1;
						n_l := 0;
			processus lecteurs			processus rédacteurs
			down(équité);				down(équité);
			down(mutex);
			n_l := n_l + 1;
			si n_l = 1 alors
				down(lect_redac);		down(lect_redac);
			finsi;
			up(mutex);
			up(équité);				up(équité);
			...
			lectures					lectures et écritures
			...
			down(mutex);
			n_l := n_l - 1;
			si n_l = 0 alors
				up(lect_redac);		up(lect_redac);
			finsi;
			up(mutex);
Fig. 13.6. Synchronisation équitable des lecteurs et des rédacteurs.
La famine est souvent une conséquence de la politique d'allocation qui est suivie. Si elle est équitable, elle sera évitée. Sur notre exemple (figure 13.6), l'introduction d'un sémaphore supplémentaire équité évite la famine, pourvu que le déblocage des processus en attente sur un sémaphore soit effectué dans l'ordre où ils sont arrivés. En effet, tous les processus doivent maintenant acquérir un jeton équité pour savoir s'ils peuvent entrer, et le libèrent lorsqu'ils ont obtenu l'autorisation. Comme l'attribution du jeton équité est faite dans l'ordre où les processus sont demandeurs, un processus lecteur n'obtiendra le sien que lorsque tous les rédacteurs arrivés avant lui auront obtenu satisfaction. Par contre, si plusieurs lecteurs se suivent, le premier obtiendra le jeton équité puis le jeton lect_redac, et libèrera le jeton équité permettant aux lecteurs qui le suivent immédiatement d'entrer dans leur phase de lecture.

13.6. Conclusion

+ Le mécanisme de verrouillage permet de faire en sorte qu'au plus un seul processus possède le verrou à un instant donné. Les opérations sur les verrous sont des primitives systèmes.
+ Un sémaphore est une généralisation du verrou. Il s'apparente à un distributeur de jetons non renouvelables qui sont rendus après utilisation. Lorsqu'un processus désire un jeton et qu'aucun n'est disponible, il est mis en attente jusqu'à ce qu'un autre processus rende son jeton.
+ Des mécanismes plus élaborés peuvent être construits à l'aide des sémaphores et de variables communes aux processus. Le respect d'une règle du jeu est souvent imposé par le système en fournissant directement ces mécanismes, comme par exemple l'accès exclusif ou partagé à un fichier.
+ Le schéma producteur-consommateur est un mécanisme général de communication entre processus, dont les tubes Unix sont une implantation fournie par le système. Les boîtes aux lettres sont aussi une implantation de ce schéma qui tient compte de la structure des messages échangés.
+ Le blocage des processus en attente de ressources a des conséquences évidentes sur les temps de réponse, et ceci ne doit pas être négligé.
+ La conséquence du blocage des processus est le risque d'interblocage. Ceci se présente lorsqu'on a un ensemble de processus qui attendent des ressources qui sont toutes possédées par des processus de l'ensemble. Lorsqu'il survient, il est nécessaire de tuer des processus de l'ensemble.
+ Un processus peut également être en famine, lorsqu'il attend une ressource qu'il n'obtient pas parce que les autres processus se coalisent pour l'en empêcher. On l'évite par une allocation équitable.
+ La différence entre la famine et l'interblocage est qu'un changement de comportement des processus permettrait de satisfaire le processus en famine, alors que l'on ne peut sortir de l'interblocage qu'en retirant autoritairement une ressource à l'un des processus.

[1] En Français, on peut leur donner éventuellement la signification mnémonique Puis-je pour P, et Vas-y pour V.