1 Synchronisation et communication entre processus Schémas classiques de synchronisation

1

Synchronisation et communication entre processus

Schémas classiques de synchronisation

2

Un premier problème simple :l'exclusion mutuelle entre processus

Accès à une ressource critique

3

Introduction : un exemple simple de concurrence

(I)

Réservation :Si nb_place > 0alors

Réserver une placenb_place = nb_place - 1

fsi

4

Introduction : un exemple simple de concurrence

• Client 1

Demande Réservation

Nb_Place > 0 = 1

Nb_Place = Nb_Place - 1

Nb_Place = -1 !!!

• Client 2

Demande Réservation

Nb_Place > 0 = 1

Nb_Place = Nb_Place - 1

Nb_Place = 0

5

Notion d'exclusion mutuelle(I)

• Ressource utilisable par un seul processus à la fois

ProcessusDébut

Prélude Section Critique

Ressource CritiqueNb_Place

Postlude Section CritiqueFin

SECTION CRITIQUE

6

Un exemple simple de concurrence

• Client 1

Demande Réservation

Protection de Nb_Place

Nb_Place > 0 = 1

Nb_Place = Nb_Place - 1

Fin protection Nb_Place

• Client 2

Demande Réservation

Nb_Place non accessible

Protection de Nb_Place

Nb_Place = 0

7

Problème de la section critiqueSolutions matérielles

• Masquage des interruptions

Processus 1 Noyau

Processus 2

Traitement IT Horloge

Nb_Place

Nb_Place

8

Problème de la section critiqueSolutions matérielles

• Masquage des interruptions

Processus 1

Masquage IT

Nb_Places

Démasquer IT

Non prise en compte

Processus 2

Attente

IT

9

Problème de la section critique

• Une ressource critique est une ressource accessible par un seul processus à la fois. L'accès se fait en exclusion mutuelle dans la section critique.

• Une solution pour réaliser une section critique est d'interdire la prise en compte des interruptions durant l'utilisation de la ressource critique.

• Mais

– dangereux

– mode superviseur

– attente active

bloquer les processus : les sémaphores

10

Les sémaphores

• Structure

File L

Compteur K

P (Sem)

V (Sem)

INIT (Val, Sem)

Sem

Val

Opérations atomiques

11

Les sémaphores

• Opération Init (Val, Sem)

Init (Val, Sem)

début

Sem. K := Val;Sem. L :=

fin

Val

12

Les sémaphores

• Opération P (Sem)

P (Sem)

débutSem.K := Sem.K - 1;Si Sem.K < 0alors

ajouter ce processus à Sem.Lendormir ce processus

fsifin

Endormissement

< 0

13

Les sémaphores

• Opération P (Sem) Endormissement

< 0

CPU

élu prêt

bloqué

P(Sem)

Sem

14

Les sémaphores

• Opération V (Sem)

V (Sem)

débutSem.K := Sem.K + 1;Si Sem.K 0alors

sortir un processus de Sem.Lréveiller ce processus

fsifin

0

Réveil

15

Les sémaphores

• Opération V (Sem)

0

Réveil

CPU

élu prêt

bloqué

V(Sem)

Sem

16

Les sémaphores

• Signification du compteur K

Si Sem.K > 0, Sem.K est le nombre d'opérations P(Sem) passantes

2

P1 P2 P3

P(Sem)

P(Sem)P(Sem)

K = 1

K = 0K < 0 Bloqué

17

Les sémaphores

• Signification du compteur K

Si Sem.K 0, valeur_absolue(Sem.K) est le nombre de processusbloqués dans Sem.L

- 2

P3

P(Sem)

P(Sem)

K = - 2Bloqué

K = -1Bloqué

P4 P1

V(Sem)K = -1Réveil de P3

P3P4

18

Les sémaphores

Section critique

Sémaphore Mutex initialisé à 1

P (Mutex)

V (Mutex)

Prélude

Postlude

Section Critique

19

Les sémaphoresSection critique

P (Mutex)

Processus 1 Processus 2

V (Mutex)

P (Mutex)Mutex.K = 0Entrée en SC

Mutex.K = - 1Mise en attente

Mutex.K = 0Réveil

Entrée en SC

20

Les sémaphoresAllocations de ressources

N ressources exclusives de même type

Sémaphore Res initialisé à N

Allocation : P(Res)

Restitution V(Res)

Utilisation Ressource

21

Les sémaphoresAllocations de ressources

P1

P2

P3

P4

P(Res) P(Res)

P(Res)

Res.K = 2 Res.K = 1

Res.K = 0

P(Res)

Res.K = - 1Bloqué

V(Res)Res.K = 0

alloué alloué

alloué

22

Notion de synchronisationProducteur-Consommateur

Tampon de messages

Producteur

Consommateur

23

Notion de synchronisationProducteur-Consommateur

• Producteur

Si il y a au moins

une case libre

alors

déposer le message

prévenir le consommateur

sinon

attendre

fsi

• Consommateur

Si il y a au moins une case pleine

alors

prendre le message prévenir le producteur

sinon

attendre

fsi

24

Un exemple de Producteur-Consommateurles Tubes Unix

Ecriture bloquante - pas de consommateurs- tube plein

Lecture bloquante- pas de producteurs- tube vide

25

Un exemple de Producteur-Consommateurles messages queue d'Unix

Clé 1

Clé 2

Clé 3

Clé 4

Clé 5

Clé 6

A B A

C A

Prod

ConsB

Clé 1

Clé 1

Clé 2

Clé 6Clé 6

61

26

Les sémaphoresProducteur-Consommateur

Tampon de N messages

ProducteurConsommateur

Ressources cases videsN

Ressources cases pleines 0

Sémaphore Vide Sémaphore Plein

retrait case jdépot case i

27

Les sémaphores Producteur-Consommateur

• Producteur

Si il y a au moins

une case libre

alors

déposer le message

prévenir le consommateur

sinon

attendre

fsi

allocation de ressources cases videsP (Sémaphore Vide)

une ressource case pleine disponibleV (Sémaphore Plein)

28

Les sémaphores Producteur-Consommateur

• Consommateur

Si il y a au moins une case pleine

alors

prendre le message prévenir le producteur

sinon

attendre

fsi

allocation de ressources cases pleinesP (Sémaphore Plein)

une ressource case vide disponibleV (SémaphoreVide)

29

• Producteur

index i de dépot : = 0

P(Vide)

déposer le message

dans T(i);

i : = i + 1 mod N;

V(Plein)

• Consommateur

index j de retrait := 0

P(Plein)

retirer le message

de T(j);

j : = j + 1 mod N;

V(Vide)

Sémaphore Vide initialisé à N : Init (Vide, N)

Sémaphore Plein initialisé à 0 : Init (Plein, 0)

30

Les sémaphoresProducteur-consommateur

Producteur Consommateur

P(Plein)Plein.K = -1Bloqué

P(Vide)Vide.K := 1dépotV(Plein)

Débloqué1 case pleine

31

Les sémaphoresProducteur-consommateur

Producteur Consommateur

P(Vide)Vide.K := 0dépotV(Plein) 2 cases pleines

P(Vide)Vide.K := - 1Bloqué

Retrait V(Vide)

Débloqué

32

Notion de synchronisationLecteurs / Rédacteurs

• Ecriture seule - Lectures simultanées

Un écrivain exclut - les écrivains- les lecteurs

Un lecteur exclut - les écrivains

FICHIER

ECRITURE

LECTURES

33

Un exemple de lecteurs / rédacteursMémoire partagée distribuée Mach

Serveur DSM

P1

Lecteur P1

Lecteur P1

Rédacteur P1

Accès Ecriture (P1)

INVALIDER P1

P1r

P1r

1

2

P1w 3

34

Les sémaphoresLecteurs / Rédacteurs

• Ecriture seule - Lectures simultanées

Un écrivain exclut - les écrivains- les lecteurs

Un lecteur exclut - les écrivains

FICHIER

ECRITURE

LECTURES

35

Les sémaphoresLecteurs / Rédacteurs

• Un écrivain exclut les écrivains et les lecteurs

ECRITURE

Un écrivain effectue des accès en exclusion mutuelle des autres écrivains et des lecteurs

Sémaphore d'exclusion mutuelle Accès initialisé à 1

36

Ecrivain

M'assurer que l'accès au fichier est libre

P(Accès)

entrer en écriture

Libérer l'accès au fichier

V(Accès)

Les sémaphoresLecteurs / Rédacteurs

37

Les sémaphoresLecteurs / Rédacteurs

• Un lecteur exclut les écrivains

LECTURES

Un premier lecteur doit s'assurer qu'il n'y a pas d'accès en écriture en cours

Le dernier lecteur doit réveiller un éventuel écrivain

NL, nombre de lecteurs courants, initialisé à 0

38

Lecteur

Compter un lecteur de plusSi je suis le premier lecteuralors

Y-a-t-il un écrivain ?si oui, attendre

fsi

entrer en lecture

Compter un lecteur de moinsSi je suis le dernier, réveiller un écrivain

Les sémaphoresLecteurs / Rédacteurs

NL = 1

NL : = NL + 1

V(Accès)

NL : = NL - 1NL = 0

P(Accès)

P(Mutex)

V(Mutex)

P(Mutex)

V(Mutex)

39

Lecteur Les sémaphoresLecteurs / Rédacteurs

P(Mutex)NL : = NL + 1Si (NL = 1)alors

P(Accès)fsiV(Mutex)

P(Mutex)NL := NL - 1;Si (NL = 0) alors

V(Accès)fsiV(Mutex)

Accès lecture

40

Les sémaphoresLecteurs / Rédacteurs

Lecteur 1 Rédacteur 1Lecteur 2 Rédacteur 2

P(Mutex)NL = 1

P(E)Accès autoriséFichier (L)V(Mutex)

P(E)Bloqué

Non actifNon actif

41

Les sémaphores

Lecteurs / Rédacteurs

Lecteur 1 Rédacteur 1Lecteur 2 Rédacteur 2

P(Mutex)NL = 2

Accès autorisé

V(Mutex)

Lecture Bloqué Non actif

42

Les sémaphoresLecteurs / Rédacteurs

Lecteur 1 Rédacteur 1Lecteur 2 Rédacteur 2

P(Mutex)NL -- = 1V(Mutex) Bloqué Non actif

P(Mutex)NL -- = 0V(E)V(Mutex)

Lecture

Fichier (E)P(E)Bloqué

43

Les sémaphoresLecteurs / Rédacteurs

Lecteur 1 Rédacteur 1Lecteur 2 Rédacteur 2

Bloqué

Ecriture

V(E)Ecriture

P(Mutex)NL = 1P(E)bloqué

P(Mutex)bloqué

44

Les sémaphoresLecteurs / Rédacteurs

• Coalition des lecteurs contre les écrivains

Lecteur 1P(E) et accès

Lecteur 2...iaccès direct Ecrivain

P(E) bloquant

Lecteur j.. accès direct

Fichier libre

Fichier en lecture

45

Les sémaphoresLecteurs / Rédacteurs

• Solution à la coalition

Fichier libre

Lecteur 1P(E) et accès

Lecteur 2...iaccès direct Ecrivain

P(E) bloquant

Lecteur j..

Fichier en lecture

Interdire l'accès