Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
[go: Go Back, main page]


Slide: 1

Concurrence1


Mémoire partagée


Georges Gonthier
INRIA -- Rocquencourt




Georges.Gonthier@inria.fr

Slide: 2

Pourquoi la concurrence?



  1. Programmer des machines multi-processeur.
  2. Piloter de périphériques lents.
  3. Les humains sont concurrents.
  4. Un serveur a plusieurs clients.
  5. Réagir sur plusieurs échelles de temps.
Approche minimaliste : plusieurs programmes (ordinaires) opèrent simultanément sur les mêmes données.

Slide: 3

Communication implicite



Soit x une variable globale; initialement, x=0.

Considérons
S = [x := x+1; x := x+1 || x:= 2*x]

T = [x := x+1; x := x+1 || wait(x=1); x := 2*x]

Après S, on a x Î {2,3,4}.
Après T, on a x Î {3,4}.
T peut rester bloqué!





Conclusion : S et T interagissent via x (variable partagée).

Slide: 4

Atomicité

Soit x une variable globale; initialement, x=0

Considérons
S = [x := x+1 || x := x+1]

Après S, on a x=2.



Cependant si
[x := x+1] se compile en [A := x+1; x := A].



Alors
S = [A := x+1; x := A] || [A := x+1; x := A]

et après S, on a x Î {1,2}.



Conclusion :
  1. [x := x+1] n'est pas forcément atomique.
  2. Le degré d'atomicité est important.

Slide: 5

Sections critiques -- exclusion mutuelle

Soit P1 = [···; A; ···] et P2 = [···; B; ···];

On dit que A et B sont des sections critiques si elles ne doivent pas être exécutées simultanément. Implmentation?



Solution 1 Initialement, turn = 1.

P1 = [···; while  turn = 2  do  ; A; turn := 2; ···]
P2 = [···; while  turn = 1  do  ; B; turn := 1; ···]
P1 est avantagé (défaut d'équité).

Solution 2 Initialement, c1 = 1, c2 = 1.

P1 = [···; while  c2 = 0  do  ; c1 := 0; A; c1 := 1; ···]
P2 = [···; while  c1 = 0  do  ; c2 := 0; B; c2 := 1; ···]
Mauvais.



Solution 3 Initialement, c1 = 1, c2 = 1.

P1 = [···; c1 := 0; while  c2 = 0  do  ; A; c1 := 1; ···]
P2 = [···; c2 := 0; while  c1 = 0  do  ; B; c2 := 1; ···]
Blocage; ni P1 ni P2 ne peuvent s'exécuter.

Slide: 6

L'algorithme de Dekker



Solution 4 Initialement, c1 = 1, c2 = 1.
P1 = [ ···      
  c1 := 0;
  while  c2 = 0  do 
   if  turn = 2  then   begin 
  c1 := 1;
  while  turn = 2  do ;
  c1 := 0;
   end ;
  A;
  turn := 2; c1 := 1;
  ···;
]    
P2 = [ ···      
  c2 := 0;
  while  c1 = 0  do 
   if  turn = 1  then   begin 
  c2 := 1;
  while  turn = 1  do ;
  c2 := 0;
   end ;
  A;
  turn := 1; c2 := 1;
  ···;
]    

Slide: 7

L'algorithme de Peterson (IPL Juin 81)



Initialement, c1 = 0, c2 = 0.
P1 = [ ···      
  c1 := 1;
  turn := 1;
  wait  c2 = 0  or  turn = 2;
  A;
  c1 := 0;
  ···;
]    
P2 = [ ···      
  c2 := 1;
  turn := 2;
  wait  c1 = 0  or  turn = 1;
  B;
  c1 := 0;
  ···;
]    

Exercice: montrer la correction.

Slide: 8

Et dans la réalité...



En fait, dans une machine moderne, il n'y a plus qu'un ordre partiel sur les lectures-écritures en mémoire.

Il est donc nécessaire de disposer de primitives de synchronisation explicites. Au niveau assembleur on trouve :

  1. tset x (x booléen) : test/affectation atomique.
  2. cas x, v, v' : comparaison/échange atomique.
  3. ldf x, stoc x : lecture marquante/écriture conditionnelle.
  4. mbar : barrière de lecture/écriture
Nécessité de développer des mécanismes de plus haut niveau.

Slide: 9

Semaphores



Un sémaphore général s est une variable entière avec 2 opérations:

wait(s): Si s > 0 alors s := s-1
Sinon blocage sur s.

signal(s): Si un processus est bloqué sur s, le réveiller; s := s+1.



On peut facilement coder l'exclusion mutuelle:
Initialement, s = 1.
On fait P1 || P2 où
P1 = [···; wait(s) ;  A;   signal(s); ···]
P2 = [···; wait(s) ;  B;   signal(s); ···]

Slide: 10

Sémantique opérationelle (1)

á skip , s ñ ® á ·, s ñ

á x := e, s ñ ® á ·, s[s(e)/x] ñ

s(b) = true 
á  if  b  then  P  else  Q, s ñ ® á P, s ñ

s(b) = false 
á  if  b  then  P  else  Q, s ñ ® á Q, s ñ

á P, s ñ ® á P', s' ñ
á P;Q, s ñ ® á P';Q, s' ñ

á P, s ñ ® á ·, s' ñ
á P;Q, s ñ ® á Q, s' ñ

s(b) = true 
á while  b  do  P, s ñ ® á P;while  b  do  P, s ñ

s(b) = false 
á while  b  do  P, s ñ ® á ·, s ñ

Slide: 11

Sémantique opérationelle (2)



á P, s ñ ® á P', s' ñ
á P || Q, s ñ ® á P' || Q, s' ñ

á Q, s ñ ® á Q', s' ñ
á P || Q, s ñ ® á P || Q', s' ñ

s(b) = true 
á wait  b, s ñ ® á ·, s ñ

s(b) = true     á P, s ñ ® á ·, s' ñ
á await  b  do  P, s ñ ® á ·, s' ñ

s(b) = true     á P, s ñ ® á P', s' ñ
á await  b  do  P, s ñ ® á P', s' ñ




Slide: 12

Exécution de la SOS



á P0, s0 ñ ® á P1, s1 ñ ® á P2, s2 ñ ® ··· á Pn, sn ñ ®

On pose
á P0, s0 ñ ®* á Pn, sn ñ si n ³ 0,
á P0, s0 ñ ®+ á Pn, sn ñ si n > 0.






Noter qu'il n'y a pas de règles du style

s(b) = false 
á wait  b, s ñ ® á wait  b, s ñ

(attente active); il peut y avoir blocage.

Slide: 13

La synchronisation en Java



  1. Chaque objet contient un verrou (sémaphore binaire).
  2. Une instruction synchronized (x) {...} réalise une section critique.
  3. Une méthode wait permet de relâcher le verrou, en se mettant en attente.
  4. Des méthodes notify/notifyAll relancent les processus suspendus.
  5. On peut créer et lancer des Threads.

Slide: 14

Le modèle mémoire de Java



On modélise directement le cache par des indirections : L'ordre des use/assign est celui du programme, celui des load/store et read/write dépend uniquement du flot de données. Les lock/unlock sont globaux.

Problèmes : optimisations, initialisations, blocages.

This document was translated from LATEX by HEVEA.