INF583 - Concurrence

Retour au cours.

Au cours de ce TD, nous allons étudier les problèmes de concurrences au sein d'un ensemble de processus, qu'ils soient légers ou non. Nous nous intéressons au cas d'école où plusieurs processus doivent incrémenter un compteur partagé de 1 un nombre fixé de fois. Ces N processus seront lancés par un processus père qui vérifiera, à la fin de l'exécution, que la valeur du compteur (C) soit bien égale au produit du nombre de processus (N) par le nombre d'incrémentations effectuées par chacun (INC). Notre objectif est de comparer différentes méthodes qui garantissent toutes que l'exécution du travail s'effectue correctement et de comparer leurs performances. Toute la difficulté réside dans la synchronisation entre les processus pour empêcher que deux processus différents n'essaient simultanément de mettre à jour le compteur.

0. Introduction

Pourquoi l'incrémentation simultanée par deux processus concurrents d'un compteur peut être problématique ?

Une incrémentation n'est pas une opération atomique. Elle se décompose en effet en 3 parties :

  1. La lecture de la valeur à incrémenter à partir de la mémoire.
  2. L'incrémentation de la valeur.
  3. Le stockage en mémoire de la nouvelle valeur.
Lors d'une exécution concurrente, deux processus peuvent lire la même valeur en mémoire, effectuer l'incrémentation à partir de cette même valeur et stocker en mémoire des valeurs identiques. Au final, une seule incrémentation a lieu au lieu des deux attendues. Dans notre exemple, où le pas d'incrémentation est 1, le compteur est augmenté de 1 au lieu de 2.

Puisque même une simple opération comme une incrémentation n'est pas atomique, la plupart des opérations usuelles des programmes ne le sont également pas. En programmation concurrente, il est donc nécessaire d'utiliser des techniques de synchronisation afin d'obtenir un fonctionnement correct. La technique de synchronisation la plus simple (et probablement la plus utilisée) est l'exclusion mutuelle. Elle consiste à imposer qu'un seul processus exécute un bout de code déterminé à la fois (ce bout de code est appelé section critique).

Nous allons maintenant étudier un algorithme d'implémentation de l'exclusion mutuelle.

1. L'algorithme de la boulangerie (Bakery algorithm)

Dans ce premier exercice, nous proposons d'implémenter l'exclusion mutuelle grâce à l'algorithme dit "de la boulangerie" (bakery), proposé par Leslie Lamport. Il généralise l'algorithme de Peterson car, contrairement à ce dernier, il n'est pas restreint à deux processus.

L'algorithme de la boulangerie fonctionne sur n'importe quelle machine fournissant des garanties de consistance mémoire élevées (sequential consistency, par exemple). Fait remarquable, il fonctionne même si la machine ne fournit aucune instruction manipulant la mémoire de manière atomique, comme une lecture ou écriture isolée et atomique sur un mot. Dans le reste du TD, nous ne nous intéressons qu'à des architectures modernes, sur lesquelles les lectures ou écritures isolées d'un entier 32 bits aligné sur 32 bits sont nécessairement atomiques. Nous considèrerons donc que toutes les lectures et écritures de l'algorithme sont effectuées de manière atomique, ce qui simplifie les raisonnements.

Le nom de l'algorithme provient de l'analogie avec la gestion d'une file d'attente dans un petit commerce (boulangerie) ou une administration (préfecture). Chaque client attend son tour pour être servi, et si plusieurs clients entrent en même temps, ils décident entre eux de leur ordre relatif.

L'algorithme se décompose en 3 parties. La première est l'initialisation, qui ne doit être faite qu'une seule fois, avant toute tentative de synchronisation. Elle positionne les valeurs par défaut des variables utilisées par l'algorithme. Voici son pseudo-code C :

La deuxième et la troisième partie constituent respectivement l'entrée et la sortie en section critique. L'entrée en section critique est elle-même divisée en deux phases, comme indiqué en commentaire dans le code ci-dessous. p désigne le numéro du processus qui exécute le code présenté. Voici son pseudo-code C :

Etudions la conception et le fonctionnement de cet algorithme :

Quelle est la valeur de compteur[p] lorsque le processus numéro p :

Quel est le rôle de la variable compteur[p] ?

Lorsque le processus p n'est pas ou ne veut pas entrer en section critique, son numéro (compteur[p]) est 0. En effet:

Lorsque le processus p veut entrer en section critique, il exécute la seconde partie. Durant la 1ère phase, il calcule la valeur maximale des compteurs des autres processus, puis s'attribue une valeur de compteur immédiatement supérieure à celle-ci (cette valeur est donc nécessairement non nulle). Dans la 2ème phase, il ne modifie pas son numéro de compteur, ni évidemment dans la section critique.

compteur[p] correspond donc au numéro d'ordre (ou ticket), que le processus p s'attribue dans la 1ère phase, et qui sera utilisé dans la 2ème phase pour décider de l'ordre d'entrée en section critique. compteur[p] est nul hors de la section critique et hors de la partie d'entrée en section critique.

Supposons que deux processus p1 et p2 veuillent entrer dans la section critique. Pour simplifier, on peut supposer qu'aucun autre processus n'essaie de faire de même. Lequel entrera le premier :

Pourquoi ce dernier cas est-il possible ?

Quel est le but de la deuxième phase ?

L'entrée en section critique est régie par la 2ème phase de la seconde partie. La boucle for permet de tester le numéro d'ordre de tous les processus chacun à son tour. Le test de la dernière boucle while compare le numéro d'ordre du processus courant p à celui d'un autres processus i, à condition que ce dernier soit non-nul.

Nous avons vu à la question précédente que les numéros d'ordre des processus ne cherchant pas à entrer en section critique sont nuls. Cette comparaison n'est donc réalisé dans le cas présent que pour i = p1 ou i = p2. Pour les autres valeurs de i, le processus courant sort immédiatement de la boucle while et passe à l'itération suivante de la boucle for.

Si compteur[p1] < compteur[p2], alors le processus p1 exécute la comparaison et sort immédiatement de la boucle while. Il finit donc l'exécution de la boucle for et entre dans la section critique. Le processus p2, au contraire, reste bloqué dans la même boucle while, jusqu'à ce que p1 sorte de la section critique et remette compteur[p1] à 0. A ce moment seulement, il sortira de la boucle while, finira sa boucle for et entrera en section critique.

Si compteur[p1] = compteur[p2], une comparaison supplémentaire entre p1 est réalisée par le dernier while, entre p1 et p2. L'un des deux est nécessairement plus grand que l'autre. Supposons que p1 < p2, l'autre cas étant symétrique. Alors le processus p1 sort immédiatement de la boucle while, puisque le test ci == cp && i < p, avec i valant p2 et p valant p1, est faux. Le processus p2 effectue le même test, qui est vrai de son point de vue, et reste donc dans la boucle. Comme précédemment, seule la sortie du processus p1 de la section critique permet à p2 de sortir de la boucle et d'entrer finalement en section critique.

Il peut sembler étonnant que le cas compteur[p1] = compteur[p2] soit traité. A priori, puisque chaque processus s'attribue un numéro d'ordre plus grand que les numéros d'ordre des autres processus dans la première phase, deux processus ne devraient pas pouvoir obtenir le même numéro. En réalité, le raisonnement précédent ne tient pas si p1 et p2 exécutent la première phase en même temps. Dans ce cas, il peut arriver que les deux processus atteignent la fin de la boucle for au même moment. Se basant sur les mêmes valeurs de compteur[i], ils ont calculé la même valeur maximale. Dans un deuxième temps, ils mettent à jour leurs numéros respectifs avec la même valeur.

Le rôle de la deuxième phase est donc d'assurer l'entrée d'un seul processus k en section critique: celui dont le couple (compteur[k],k) est le plus petit pour l'ordre lexicographique sur l'ensemble des couples (compteur[i],i).

Supposez que l'on supprime le tableau partagé choix (ce qui équivaut fonctionnellement à supprimer le premier while de la 2ème phase).

Pouvez-vous trouver un exemple d'exécution où deux processus exécutent la section critique en même temps ?

L'utilité du tableau choix est peut-être un des points les plus délicats de l'algorithme de la boulangerie.

Considérons une exécution où deux processus exécutent leur première phase et s'arrêtent tout deux juste avant de mettre à jour leur numéro d'ordre (i.e., juste avant la ligne compteur[p] = max + 1;). Nous supposerons que, s'il y a d'autres processus, ils ne cherchent pas à entrer en section critique; nous pouvons donc les ignorer. Nous notons p1 le premier processus et p2 le second. Nous supposons enfin que p1 > p2.

Comme expliqué à la question précédente, les deux processus sont donc sur le point de s'attribuer le même ticket. Supposons que p1 poursuit son exécution et entame la 2ème phase, alors que p2 ne progresse pas. Puisque p2 n'a pas progressé, on a toujours compteur[p2] égal à 0.

Dans l'itération i = p2 de la deuxième phase, p1 teste la valeur de compteur[p2]. Cette valeur étant égale à 0, p1 considère que p2 ne cherche pas à entrer en section critique. Il poursuit donc la 2ème phase, et finit par rentrer en section critique.

Supposons maintenant que, pendant que p2 atteint un point donné de la section critique, p1 poursuit son exécution et exécute la 2ème phase. Lors de l'itération i = p2, il s'aperçoit que compteur[p2] = compteur[p1]. Il compare alors les identifiants de processus. Comme p1 > p2, il en déduit qu'il est prioritaire par rapport à p1 et finit par entrer dans la section critique, alors que p1 n'en est pas encore sorti! Autrement dit, dans ce cas, les deux processus exécutent la section critique en même temps.

Le tableau choix (qui n'est donc pas inutile !) permet de savoir à quel moment un processus donné est dans la phase d'attribution d'un numéro. Cette information est essentielle pour garantir, grâce au test de choix[i], qu'un processus entrant dans la 1ère phase après le test sera nécessairement moins prioritaire que le processus qui a fait le test. Cette dernière condition est vérifiée car, lorsque le processus p effectue le test sur choix[i] et que le test est négatif, on est certain que compteur[p] a bien été mis à jour. Sa valeur sera donc prise en compte dans le calcul du maximum et tout nouveau numéro d'ordre sera strictement supérieur à celui-ci.

Supposez maintenant que l'on remplace le tableau partagé compteur par un tableau de booléens, où le booléen d'indice i indique si le processus i souhaite entrer ou non en section critique. La mise à jour du booléen à true a lieu lors de la 1ère phase, à la place du calcul du maximum et de la mise à jour de compteur[p]. Le booléen est remis à false dans la 3ème partie (à la place de la remise à zéro de compteur[p]).

Montrer que ce nouvel algorithme réalise toujours l'exclusion mutuelle.

Quels sont ses avantages et inconvénients ?

On peut prouver que le nouvel algorithme fonctionne en utilisant un raisonnement analogue à ceux développés plus haut pour l'algorithme original.

Mais le plus simple est encore de remarquer que le nouvel algorithme correspond au cas particulier d'exécution de l'algorithme de la boulangerie où tous les processus en compétition pour la section critique se voient attribuer le même numéro d'ordre, par exemple 1, si l'on suppose qu'ils ont tous calculé le même max mais n'ont pas encore écrit leur numéro en mémoire partagée.

Le nouvel algorithme présente l'avantage de requérir moins d'espace mémoire que l'original. Il n'est pas non plus sujet aux possibles dépassements de capacité des entiers de compteur, si des processus cherchent continuellement à entrer en section critique (ce qui n'arrive jamais en pratique, sauf dans des cas très particuliers).

Par contre, il a l'inconvénient de privilégier systématiquement les processus qui ont les plus petits identifiants, y compris lorsque ces derniers viennent d'exécuter la section critique et cherchent à y entrer à nouveau. Un processus d'identifiant i, en attente dans la 2ème phase, peut y rester arbitrairement longtemps, si un autre processus j, avec j < i, essaie d'entrer continuellement en section critique et si i n'a pas le temps de progresser dans la 2ème phase, entre le moment où j est sorti de la section critique et où il commence la 1ère phase. Le processus i est alors déclaré en famine (starvation).

Un des intérêts de l'algorithme de la boulangerie est de ne pas avoir ce défaut. En effet, lorsque des processus exécutent la première phase, ils s'attribuent nécessairement un numéro strictement supérieur à tout processus se trouvant soit dans la 2ème phase, soit en section critique, soit hors de la section critique et du code de l'algorithme. Cela implique que lorsqu'un processus sort de la section critique et qu'il rentre à nouveau dans la première phase, son nouveau numéro est supérieur à ceux des processus précédemment bloqués dans la 2ème phase en attente d'entrer en section critique.

2. Implémentation et Expérimentation

Nous allons implémenter cet algorithme dans le cadre de l'application décrite au début de cet énoncé.

Étendez le squelette contenu dans l'archive suivante afin d'obtenir une application qui incrémente le même compteur grâce à différents processus. N'implémentez pas pour l'instant d'exclusion mutuelle.

Testez le programme. Que constatez-vous ?

Voir au bas du TD pour le lien vers le code.

On constate effectivement que certaines incrémentations sont perdues, comme on l'a expliqué dans l'introduction du TD.

Rajoutez maintenant l'implémentation de l'algorithme de la boulangerie pour effectuer l'exclusion mutuelle.

Testez le programme, de préférence avec peu de processus et un grand nombre d'incrémentations. Que constatez-vous ? Essayez de proposer une explication.

Voir au bas du TD pour le lien vers le code.

Malgré l'introduction de l'algorithme de la boulangerie, des incrémentations sont perdues ou le programme se bloque.

Cela est dû à la consistance mémoire implémentée sur x86 (ia32 ou amd64). En particulier, sur les processeurs Intel, une lecture mémoire peut en réalité être réalisée avant une écriture qui la précède dans l'ordre du programme. Cela brise la garantie qu'un processus i est en train de s'attribuer un numéro uniquement lorsque choix[i] vaut 1.

Pour remédier à cela, il faut utiliser des barrières (fence) qui indiquent au processeur de ne pas continuer à traiter d'autres instructions avant de s'être assuré que les précédentes ont réellement été effectuées et leurs résultats propagés. Veuillez vous référer à la correction.

3. Amélioration à l'aide de signaux

L'algorithme de la boulangerie a pour inconvénient de faire de nombreuses attentes actives, ce qui utilise inutilement les processeurs et ralentit donc potentiellement l'exécution d'autres processus. On décide donc d'utiliser les signaux Unix pour suspendre et pour réveiller un processus lorsque ce dernier attend trop longtemps.

Modifiez le code du squelette afin que chaque boucle d'attente active, le processus utilise sigsuspend (2) pour s'endormir. Déterminez à quels endroits et à qui des signaux doivent être envoyés afin d'être sûr que les processus en sommeil soient bien réveillés. Vous utiliserez les signaux utilisateurs SIGUSR1 et SIGUSR2.

Voir au bas du TD pour le lien vers le code.

On peut, par exemple, faire en sorte que les processus attendant qu'une valeur du tableau choix passe à 0 pour pouvoir poursuivre la 2ème phase s'endorment jusqu'à réception d'un signal SIGUSR1. Comme on ne sait pas a priori quel processus est en attente à ce niveau ni quel est l'indice de la valeur qu'il surveille, il faut envoyer SIGUSR1 à tous les processus. Le signal doit être envoyé dès que la condition est susceptible de changer. Ici, il suffit d'envoyer un signal après la remise à zéro d'une valeur de choix.

Le même raisonnement est valable pour l'attente du test sur la valeur de compteur[j] dans la 2ème phase (attente d'un changement de la valeur de compteur dans la deuxième phase, envoi du signal depuis la 3ème partie, i.e., la fin de la section critique). On peut alors utiliser le signal SIGUSR2 de manière analogue pour ce cas.

Il serait tout à fait possible d'utiliser également SIGUSR1 ici, puisque, au réveil, un processus teste à nouveau la condition pour laquelle il attendait avant de s'endormir. Il est cependant préférable de l'éviter pour des raisons de performances, puisque l'on sait à l'avance, par exemple, que la modification de compteur[i] n'influera pas sur le test de la valeur de choix[j]. Si les deux cas utilisent le même signal, les processus modifiant compteur[i] réveilleraient inutilement ceux qui attendent un changement de valeur de choix[j].

On peut remarquer que l'utilisation de signaux est particulièrement bien adaptée, sémantiquement parlant, pour le remplacement de l'attente active. Le même signal envoyé plusieurs fois à un processus n'entraîne qu'un seul appel au gestionnaire de signal, si celui-ci n'a pas été invoqué dès le premier signal à cause, par exemple, de l'ordonnancement des processus. Dans ce dernier cas, la condition associée ne sera vérifiée qu'une seule fois, c'est-à-dire pas plus que le strict nécessaire.

En terme de performance, par contre, l'utilisation des signaux n'est pas recommandée en général. On emploiera plutôt des sémaphores, des files de messages ou, dans le cas de threads, des variables conditionelles. Dans le cadre de l'algorithme de la boulangerie, les performances se dégraderont de toute manière relativement vite avec l'augmentation du nombre de processus participant à l'exclusion mutuelle, puisqu'on ne sait pas a priori quels sont les processus à réveiller et que l'algorithme choisi est par conséquent de les réveiller tous.

4. Cas concret

Il n'est pas nécessaire de faire appel à l'algorithme de la boulangerie pour obtenir une exclusion mutuelle entre deux processus en pratique. Il existe de nombreuses méthodes beaucoup plus performantes. Nous en verrons certaines d'entre elles, implémentées avec des opérations atomiques combinées (lecture, test ou opération, puis écriture combinées), ultérieurement.

En attendant, nous pouvons employer une technique très simple: utiliser flock (2), comme vous avez pu le voir dans le squelette de l'exercice 3 du TD n°2. Il est également possible d'utiliser des sémaphores, comme introduit dans le cours (voir aussi la page de manuel: sem_overview (7), ou bien: sem_open (3)).

En reprenant le squelette cité ci-dessus, modifiez votre implémentation pour réaliser l'exclusion mutuelle avec flock ou avec des sémaphores.

La correction de toutes les implémentations demandées est disponible en suivant ce lien.