Théorie et pratique de la concurrencefrancoisl/DIVERS/tpc2021c1.pdfenvoi de messages), le choix de la sémantique d’entrelacement est raisonnable… ‣Système multi-tâches: Un

Théorie et pratique de la concurrence

2020-2021

1

Équipe enseignante: - Carole Delporte - Hugues Fauconnier - François Laroussinie

Page web: https://www.irif.fr/~francoisl/m1tpc.html

CM: mercredi 8h30-10h30. Amphi 6C TDs/TPs: mardi 13h45-15h45 et

mardi 16h-18h. Salle 2027 (SG)2

Pourquoi utiliser des programmes concurrents (ou parallèles) ?

Pour gagner en efficacité ! Distribuer les données, partager les ressources, utiliser des réseaux…

3

Plan du cours

‣ Introduction: définitions, instructions atomiques, sémantique d’entrelacement, (kit de survie de logique temporelle),…

‣Exclusion mutuelle Algorithmes de Dekker, de Peterson, de la boulangerie.

‣Moniteurs, sémaphores ‣Lecteurs/écrivains ‣Producteurs/consommateurs ‣Extensions: Communication par envoi

de messages, …

‣Concurrence en Java thread, variables partagées, synchronized, wait, signal,…

||

4

Installer spin sur vos machines… http://spinroot.com/spin/

5

Programme concurrent ?

Un programme concurrent est un ensemble de programmes séquentiels exécutés en « parallèle » avec de la communication entre eux.

« parallèle »: ici on considère des exécutions sur des processus différents (sens habituel de « parallèle ») mais aussi des systèmes multi-tâches où le parallélisme n’est qu’apparent.

« communication »: - communication de données. - synchronisation: échange d’informations sur le contrôle

(état) des processus.

→ par mémoire partagée, ou par envoi de messages6

Exécutions concurrentes

Rappel: un processus = un programme en cours d’exécution.

Exécution d’un programme concurrent:

- Ensemble fini de processus séquentiels, - chaque processus est décrit par un ensemble fini

d’instructions atomiques.

- chaque processus dispose d’un pointeur d’instructions (pointeur de contrôle, compteur de prog.) désignant la prochaine instruction devant être exécutée.

- l’exécution du prog concurrent consiste en un entrelacement arbitraire des instructions des processus.

- lors d’une exécution, la prochaine instruction est donc choisie parmi celles pointées par les pointeurs de contrôle.

Plusieurs scénarios possibles !7

Exécutions concurrentes

Exemple:

Plusieurs scénarios:

Processus P1: int x,y a1 : x:= 10 a2 : y:= 20

Processus P2: int u,v b1 : u:= 3 b2 : v:= 56 b3 : u:= 10

a1, a2, b1, b2, b3a1, b1, a2, b2, b3a1, b1, b2, a2, b3a1, b1, b2, b3, a2…

8

La communication par mémoire partagéeDifférents processus peuvent partager de la mémoire (des variables). On peut distinguer plusieurs cas:

- des variables « simples » avec une lecture et une écriture atomiques. On distingue plusieurs types: ‣ les variables en lecture et en écriture pour plusieurs processus

« Multiple-Reader/Multiple-Writer » ‣ les variables « propres », en lecture pour plusieurs processus

mais en écriture pour un seul « Multiple Reader/Single-Writer ».

- des constructions plus élaborées: ‣ sémaphores ‣ test-and-set, swap,… ‣ moniteur

9

Exécutions concurrentesExemple:

Plusieurs scénarios:

Processus P1: int x a1 : x:= 1 a2 : n:= x

Processus P2: int u b1 : u:= 2 b2 : n:= u

int n:=0 // var. partagée

(n=0,a1,x=⊥,b1,u=⊥)

(n=0,a2,x=1,b1,u=⊥)

(n=1,end,x=1,b1,u=⊥)

(n=1,end,x=1,b2,u=2)

(n=2,end,x=1,end,u=2)

(n=2,a2,x=1,end,u=2)


(n=2,a1,x=⊥,end,u=2)

(n=0,a1,x=⊥,b2,u=2)

(n=0,a2,x=1,b2,u=2)

10

Instructions atomiques

Notion cruciale ! La correction des programmes dépend des hypothèses d’atomicité. Une instruction atomique est exécutée complètement sans interruption.

x:=5 x:= x+1 Si x=2 Alors x:=3

✓✖✖

Exemples:temp:=x x := temp+1{sauf Test-And-Set

Pas toujours simple à définir !

On supposera (sauf indication contraire) que chaque ligne dans les programmes sera atomique…

11

Processus P1: a1 : n:= n+1

Processus P2: b1 : n:= n+1

int n:=0 // var. partagée

Si « n:=n+1 » atomique: (n=0,a1,b1)(n=1,end,b1) (n=1,a1,end)

(n=2,end,end)

Et sinon: Processus P1: int temp a1 : temp := n a2: n:= temp+1

Processus P2: int temp’ b1 : temp’ := n b2 : n := temp’+1

A la fin, on peut avoir des résultats très différents !A faire en exercice…

12

Hypothèses d’atomicité

Nos hypothèses sont peu réalistes !

Les instructions atomiques peuvent changer d’une machine à l’autre, d’un compilateur à l’autre…

Une règle:

Eviter les instructions manipulant plusieurs variables ou occurrences de variables pouvant être modifiées et lues par plusieurs processus.

n := n+1 → 2 ! temp := n → 1 n := temp+1 → 1 mais13

Hypothèses d’atomicitéPlusieurs cas:

- registres atomiques: opérations de lecture et d’écriture atomiques.

- test-and-set: on affecte une valeur à un registre et on renvoie son ancienne valeur

- swap: on échange la valeur d’un registre partagé et d’un registre local

- …

14

Sémantique d’entrelacement

Définition: L’état d’un programme concurrent P est un n-uplet avec:

‣ un pointeur d’instructions par processus, ‣ une valeur pour chaque variable (locale ou partagée)

Exemple: (n=1,end,x=1,b2,u=2)

Définition: Pour deux états s1 et s2, on écrit s1→P s2 lorsque l’on peut passer de s1 à s2 en utilisant une instruction pointée dans s1.

Exemple: (n=1,end,x=1,b2,u=2) →P (n=2,end,x=1,end,u=2)

15

Sémantique d’entrelacementDéfinition: Le diagramme d’état de P est le « système de transitions » (ie graphe) SP=(S,A,s0) où:

- S est l’ensemble des états possibles pour P, - A est la relation →P - s0 est l’état initial de P.Un chemin dans SP est un scénario possible pour P.

(n=0,a1,x=⊥,b1,u=⊥)

(n=0,a2,x=1,b1,u=⊥)

(n=1,end,x=1,b1,u=⊥)

(n=1,end,x=1,b2,u=2)


(n=2,a2,x=1,end,u=2)


(n=2,a1,x=⊥,end,u=2)

(n=0,a1,x=⊥,b2,u=2)

(n=0,a2,x=1,b2,u=2)

Exemple:

16

Sémantique d’entrelacement

Les chemins de SP correspondent à tous les entrelacements possibles pour P. On suppose donc possible n’importe quel entrelacement !

Même si en pratique ce n’est pas le cas. → c’est une abstraction

Mais on se limitera parfois aux scénarios « équitables » où chaque processus avance de temps en temps…

On prouvera la correction de nos algorithmes pour tout entrelacement (ou tout entrelacement équitable) → notion robuste !

17

Discussion de la sémantique

Que l’on considère des systèmes multi-tâches sur 1 CPU, ou des systèmes multi-processeurs, ou encore des systèmes distribués (avec envoi de messages), le choix de la sémantique d’entrelacement est raisonnable…

‣Système multi-tâches: Un CPU avec plusieurs processus (pas de « vrai » parallélisme) → il y a bien une succession d’instructions d’un processus, puis d’un autre, etc. Sémantique OK !

18

Discussion de la sémantique

‣Système multi-processeurs: Plusieurs CPU (avec mémoire locale) + mémoire globale Chaque processus est affecté à un CPU. La sémantique d’entrelacement ne correspond pas exactement à la réalité, mais elle est correcte si il n’y a pas de conflit de ressources (ie d’accès en lecture et en écriture à une même donnée). → importance du problème de l’exclusion mutuelle.

‣Système distribués: Plusieurs machines, pas de ressources globales, des canaux de communication. Très différent des deux autres cas… mais la sémantique d’entrelacement reste intéressante (on y intègre l’envoi et la réception de messages).

19

Ecriture des programmes concurrents

Instructions classiques… + hypothèses d’atomicité !

Des instructions spéciales: - loop forever : boucle infinie - await C : attente active d’une condition booléenne C

dépendant de variables partagées. Equivalent à « while ¬ C fo skip »

Plus une syntaxe particulière pour les sémaphores, les test-and-set, les moniteurs…

Plus la syntaxe Java pour les TP !

20

La concurrence complexifie l’analyse des programmes !

21 22

23

Pour s’entraîner…

24

Les noirs viennent de jouer. Quel est leur dernier coup ?

Voir « The Retrograde Analysis Corner » https://www.janko.at/Retros/index.htm

Raymond Smullyan The Chess Mysteries of Sherlock Holmes, 1979

Ernest Clement Mortimer Shortest Proof Games, 1991 Version by A. Frolkin

Position après le 4eme coup des Noirs. Comment s’est déroulée la partie ?

25

Le roi venait de a7 à a8 où il a pris un cavalier blanc qui venait de b6


Raymond Smullyan The Chess Mysteries of Sherlock Holmes, 1979

80ZKZ0Z0Z7j0Z0Z0Z060M0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z020Z0Z0Z0O1Z0Z0Z0A0

a b c d e f g h

Position après le quatrième coup des Noirs. Comment s’est déroulée la partie ? [Ernest

Clement Mortimer, Shortest Proof Games, 1991, Version by A. Frolkin]

8rmblka0s7opo0Zpop60Z0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBZR

a b c d e f g h

La séquence pour y arriver :

8rmblkans7opopopop60Z0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBMR

a b c d e f g h

2

26


Ernest Clement Mortimer Shortest Proof Games, 1991 Version by A. Frolkin


a b c d e f g h



a b c d e f g h

8rmblkans7opopopop60Z0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0ZNZ02POPOPOPO1SNAQJBZR

a b c d e f g h

2

1. C f1


a b c d e f g h



a b c d e f g h

8rmblkans7opopopop60Z0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0ZNZ02POPOPOPO1SNAQJBZR

a b c d e f g h

2

e5

8rmblkans7opopZpop60Z0Z0Z0Z5Z0Z0o0Z040Z0Z0Z0Z3Z0Z0ZNZ02POPOPOPO1SNAQJBZR

a b c d e f g h

8rmblkans7opopZpop60Z0Z0Z0Z5Z0Z0M0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBZR

a b c d e f g h

8rmblka0s7opopmpop60Z0Z0Z0Z5Z0Z0M0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBZR

a b c d e f g h

3


a b c d e f g h


a b c d e f g h


a b c d e f g h

3

2. Cxe5


a b c d e f g h


a b c d e f g h


a b c d e f g h

3

Ce7

8rmblka0s7opoNmpop60Z0Z0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBZR

a b c d e f g h

8rmblka0s7opoNZpop60ZnZ0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBZR

a b c d e f g h

8rMblka0s7opo0Zpop60ZnZ0Z0Z5Z0Z0Z0Z040Z0Z0Z0Z3Z0Z0Z0Z02POPOPOPO1SNAQJBZR

a b c d e f g h

4

3. Cxd7


a b c d e f g h


a b c d e f g h


a b c d e f g h

4

Cc6


a b c d e f g h


a b c d e f g h


a b c d e f g h

4

4. Cxb8 Cxb8

27

Problème d’exclusion mutuelle

28

Problèmes de section critique

Le problème:- N (≥2) processus exécutent continuellement deux séquences

d’instructions: ‣ une section non critique (SNC) ‣ une section critique (SC)

de telle manière que l’exclusion mutuelle soit assurée en SC : au plus un processus se trouve en SC à tout instant.

Pour y parvenir, on va utiliser des variables partagées (qui ne seront pas utilisées en SNC et SC !) dans:

- un préprotocole avant d’accéder en SC - un postprotocole après avoir accéder à la SC.29


Processus P: loop forever: p1: section NC p2… pré-protocole pi: section critique pj…: post-protocole

Structure des programmes

Hypothèses supplémentaires: - la SC critique termine toujours… - la SNC peut ne pas terminer (boucle infinie). - Les deux processus restent tjs actifs.

30


Processus P1: loop forever: p1: section NC p2: await turn==1 p3: section critique p4: turn:=2

Exemples

Processus P2: loop forever: q1: section NC q2: await turn==2 q3: section critique q4: turn:=1

int turn := 1 // var. partagée

Quels scénarios ? 31



Exemples



Diagramme d’états:Un état contient:

- un pointeur sur les instructions de P1, - un pointeur sur les instructions de P2, - la valeur de turn, - la valeur des variables locales de chaque processus…32

Problèmes de section critiqueExemples

p1, q1, 1 p1, q2, 1

p2, q1, 1 p2, q2, 1

p3, q1, 1 p3, q2, 1

p4, q1, 1 p4, q2, 1

p1, q1, 2 p1, q2, 2

p2, q1, 2 p1, q3, 2

p2, q2, 2 p1, q4, 2

p2, q3, 2

p2, q4, 2

1, 2

1

2

2

2

1, 2

2

1

1

1

2

1 1

2

2

1 1

2

2

1 1

2

2

1 1

2

2

1 2

12

1

2

12

1

1

2

2

1

1

2

Figure 2 – Diagramme d’états de A1.

Equité entre processus. Une exécution de l’algorithme A1 correspond à un chemin (infini)dans le graphe d’états. Mais l’inverse n’est pas vrai : certains chemins infinis du graphe nesont pas de ⌧ bonnes � exécutions de l’algorithme. Par exemple, les chemins qui bouclentinfiniment dans un unique état avec une transition ⌧ pleine � correspondent à une exécutioninfinie soit du pré-protocole de P1 (pour les états de la forme (p2,�, 2)), soit du pré-protocolede P2 (pour les états de la forme (�, q2, 1)). Or dans tous ces cas, cela signifierait que l’undes deux processus est systématiquement empêché de progresser : ce serait toujours l’autrequi aurait la main. Ce genre de situation n’est pas acceptable : on souhaite autoriser lesentrelacements d’actions des deux processus mais pas l’exclusion ad vitam aeternam d’un desdeux processus. . . Les exécutions de A1 seront donc représentées par les chemins équitables où⌧ un processus qui peut avancer, avancera un jour �. Dans le diagramme d’états de la figure 2,les deux processus peuvent toujours exécuter une action, et donc les chemins équitables sontles chemins infinis où il y a une infinité de transitions étiquetées par 1 et une infinité detransitions étiquetées par 2.

L’analyse du graphe d’états de A1 montre clairement que les états (p3, q3, 1) et (p3, q3, 2)ne sont pas accessibles. La propriété d’exclusion mutuelle est donc vérifiée.

5


équitables où ⌧ un processus qui peut avancer, avancera un jour �. Dans le diagrammed’états de la figure 6, les deux processus peuvent toujours exécuter une action,

et donc les chemins équitables sont les chemins infinis où il y a une infinité de

transitions étiquetées par 1 et une infinité de transitions étiquetées par 2.

Etude des propriétés de l’algorithme. L’analyse du graphe d’états de A1 montre claire-ment que les états (p3, q3, 1) et (p3, q3, 2) ne sont pas accessibles. La propriété d’exclusionmutuelle est donc vérifiée.

Qu’en est-il des autres propriétés ?– absence d’inter-blocage : les processus ne peuvent pas se bloquer mutuellement dans

la phase de pré-protocole.Cette propriété est aussi vérifiée : une analyse du graphe de la figure 6 montre quelorsque les deux processus sont ensemble dans leur phase de Pre-protocole, il y en atoujours un qui peut accéder à la SC : P1 si turn vaut 1, et P2 si turn vaut 2, sachantque turn vaut toujours 1 ou 2.

– absence de famine : La question est de savoir si à tout moment lorsqu’un processus setrouve dans son pré-protocole (i.e. quand il souhaite accéder à sa SC), alors il y arrivera

9

id du proc. actif

1 ou 2 actions possible en SNC…

Correct ?(p3,q3,-) accessible ?

Exécutions équitables…

(p,q,v)

inst. de P1inst. de P2

val. de turn


33



Exemples



Un bon algorithme d’exclusion mutuelle ?Est-ce que les exécutions équitables sont correctes?

34

Problèmes de section critiqueExemples

p1, q1, 1 p1, q2, 1

p2, q1, 1 p2, q2, 1

p3, q1, 1 p3, q2, 1

p4, q1, 1 p4, q2, 1

p1, q1, 2 p1, q2, 2

p2, q1, 2 p1, q3, 2

p2, q2, 2 p1, q4, 2

p2, q3, 2

p2, q4, 2

1, 2

1

2

2

2

1, 2

2

1

1

1

2

1 1

2

2

1 1

2

2

1 1

2

2

1 1

2

2

1 2

12

1

2

12

1

1

2

2

1

1

2


Equité entre processus. Une exécution de l’algorithme A1 correspond à un chemin (infini)dans le graphe d’états. Mais l’inverse n’est pas vrai : certains chemins infinis du graphe nesont pas de ⌧ bonnes � exécutions de l’algorithme. Par exemple, les chemins qui bouclentinfiniment dans un unique état avec une transition ⌧ pleine � correspondent à une exécutioninfinie soit du pré-protocole de P1 (pour les états de la forme (p2,�, 2)), soit du pré-protocolede P2 (pour les états de la forme (�, q2, 1)). Or dans tous ces cas, cela signifierait que l’undes deux processus est systématiquement empêché de progresser : ce serait toujours l’autrequi aurait la main. Ce genre de situation n’est pas acceptable : on souhaite autoriser lesentrelacements d’actions des deux processus mais pas l’exclusion ad vitam aeternam d’un desdeux processus. . . Les exécutions de A1 seront donc représentées par les chemins équitables où⌧ un processus qui peut avancer, avancera un jour �. Dans le diagramme d’états de la figure 2,les deux processus peuvent toujours exécuter une action, et donc les chemins équitables sontles chemins infinis où il y a une infinité de transitions étiquetées par 1 et une infinité detransitions étiquetées par 2.

L’analyse du graphe d’états de A1 montre clairement que les états (p3, q3, 1) et (p3, q3, 2)ne sont pas accessibles. La propriété d’exclusion mutuelle est donc vérifiée.

5


équitables où ⌧ un processus qui peut avancer, avancera un jour �. Dans le diagrammed’états de la figure 6, les deux processus peuvent toujours exécuter une action,

et donc les chemins équitables sont les chemins infinis où il y a une infinité de

transitions étiquetées par 1 et une infinité de transitions étiquetées par 2.

Etude des propriétés de l’algorithme. L’analyse du graphe d’états de A1 montre claire-ment que les états (p3, q3, 1) et (p3, q3, 2) ne sont pas accessibles. La propriété d’exclusionmutuelle est donc vérifiée.

Qu’en est-il des autres propriétés ?– absence d’inter-blocage : les processus ne peuvent pas se bloquer mutuellement dans

la phase de pré-protocole.Cette propriété est aussi vérifiée : une analyse du graphe de la figure 6 montre quelorsque les deux processus sont ensemble dans leur phase de Pre-protocole, il y en atoujours un qui peut accéder à la SC : P1 si turn vaut 1, et P2 si turn vaut 2, sachantque turn vaut toujours 1 ou 2.

– absence de famine : La question est de savoir si à tout moment lorsqu’un processus setrouve dans son pré-protocole (i.e. quand il souhaite accéder à sa SC), alors il y arrivera

9

35


Les propriétés attendues (la spécification):- Exclusion mutuelle :

Au plus un seul processus en section critique à tout instant.- Absence de famine :

Si un processus souhaite accéder à sa SC, il y parviendra un jour.- Absence d’inter-blocage :

Si plusieurs processus essaient d’accéder au même moment à leur SC, ils ne doivent pas se bloquer dans le préprotocole et un processus doit réussir à y accéder.

- Attente bornée :Lorsqu’un processus attend pour accéder à sa SC, on peut borner le nb de fois où il sera « doubler » par d’autres processus.

- Absence de privilèges :Chaque processus est traité à égalité.

36



Exemples



Spécification:- Exclusion mutuelle :- Absence d’inter-blocage :- Absence de famine :- Attente bornée :- Absence de privilèges :

✓✖✓

✖(✓)

37

Documents

Théorie et pratique de la concurrencefrancoisl/DIVERS/tpc2021c1.pdfenvoi de messages), le choix de la sémantique d’entrelacement est raisonnable… ‣Système multi-tâches: Un