05 - semaphorebosio/HMEE209/04 - semaphore.pdf · 2017. 2. 13. · 3 Notion de ressources n...

1

Agendan Synchronisation et communication entre

processusn Schémas classiques de synchronisation

2

P1

P2

P3

F Processus non indépendants : accès concurrents aux ressources

Introductionn Système multiprocessusn L'ordonnancement "entrelace" les exécutions

3

Notion de ressources

n Définitionsn Une ressource désigne toute entité dont a

besoin un processus pour s'exécuter.n Ressource matérielle (processeur, périphérique)n Ressource logicielle (variable)

n Une ressource est caractérisén par un état : libre /occupéen par son nombre de points d'accès (nombre de

processus pouvant l'utiliser en même temps)

4

Notion de ressources

n Utilisation d'une ressource par un processusn Trois étapes :

n Allocation, Utilisation, Restitutionn Les phases d'allocation et de restitution

doivent assurer que le ressource estutilisée conformément à son nombre depoints d'accès

n ressource critique à un seul point d'accès

5

Les sémaphores

n StructureFile L

Compteur K(niveau du sémaphore)

P (Sem)

V (Sem)

INIT (Val, Sem)Sem

Val

Opérations indivisibles

6

n Un sémaphore Sem peut être vu comme un distributeur de jetons; le jeton étant un droit à poursuivre son exécution

n l'opération INIT (Sem, Val) fixe le nombre de jetons initial

n l'opération P(Sem) attribue un jeton au processus appelant si il en reste sinon bloque le processus dans Sem.L

n l'opération V(Sem) restitue un jeton et débloque un processus de Sem.L si il en existe un.

Les sémaphores

7

n Opération Init (Val, Sem)Init (Val, Sem)

débutmasquer_itSem. K := Val;Sem. L := Ædemasquer_it

fin

Val jetons

Les sémaphores

8

Les sémaphoresn Opération P (Sem)P (Sem)

débutmasquer_itSi il reste un jetonalors

le donner à ce processussinon

ajouter ce processus à Sem.Lbloquer ce processus

fsidemasquer_it

fin

Endormissement

0 jetons

9

P (Sem)

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

ajouter ce processus à Sem.Lendormir ce processus

fsifin

Endormissement

< 0

Les sémaphoresn Opération P (Sem)

10

V (Sem)

débutmasquer_itAjouter un jeton à Sem.KSi il y a un processus en attente de jeton dans Sem.Lalors

sortir un processus de Sem.Llui donner un jetonréveiller ce processus

fsidemasquer_itfin

Réveil

jetons

n Opération V (Sem)

Les sémaphores

11

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

n Opération V (Sem)

Les sémaphores

12

n Signification du compteur K n 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é

Les sémaphores

13

n Signification du compteur K n Si Sem.K £ 0, valeur_absolue(Sem.K) est le nombre de

processus bloqués dans Sem.L

-2

P3 P4 P1

P(Sem)

P(Sem)V(Sem)

K = -1Bloqué

K = -2Bloqué K = -1

Réveil de P3

Les sémaphores

P3P4

14

1 seul processus en section critique=> 1 seul jetonSémaphore Mutex initialisé à 1

P (Mutex)

V (Mutex)

Entrée section_critique

Sortie section_critique

Section Critique

Section critique avec sémaphore

15

N ressources exclusives de même type

Sémaphore Res initialisé à N

Allocation : P(Res)

Restitution V(Res)

Utilisation Ressource

Allocations de ressources

16

P1

P2

P3

P4

P(Res) P(Res)

P(Res)

Res.K = 2 Res.K = 1

Res.K = 0

P(Res)Res.K = - 1

Bloqué

V(Res)Res.K = 0

alloué alloué

alloué

Allocations de ressources

17

Tampon de messages géré circulairement

Producteur Consommateur

Notion de synchronisationProducteur - Consommateur

18

n ProducteurSi il y a au moins une case libre alorsdéposer le message prévenir le consommateursinon attendrefsi

n ConsommateurSi il y a au moins une case pleine alorsprendre le message prévenir le producteursinonattendrefsi

Notion de synchronisationProducteur - Consommateur

19

Tampon de N messages

ProducteurConsommateur

Ressources cases videsN

Ressources cases pleines 0

Sémaphore Vide Sémaphore Plein

retrait case jdépot case i

Les sémaphoresProducteur-Consommateur

20

n ProducteurSi il y a au moins une case libre alorsdéposer le message prévenir le consommateursinon attendrefsi

allocation de ressources cases videsP (Sémaphore Vide)

une ressource case pleine disponibleV (Sémaphore Plein)

Les sémaphoresProducteur-Consommateur

21

n ConsommateurSi il y a au moins une case pleine alorsprendre le message prévenir le

producteursinonattendrefsi

allocation de ressources cases pleinesP (Sémaphore Plein)

une ressource case vide disponibleV (SémaphoreVide)

Les sémaphoresProducteur-Consommateur

22

n Producteurindex i de dépot : = 0

P(Vide)déposer le message dans T(i);i : = i + 1 mod N;V(Plein)

n 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)

23

Producteur ConsommateurP(Plein)Plein.K = -1Bloqué

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

1 case pleine

Les sémaphoresProducteur-Consommateur

24

Producteur ConsommateurP(Vide)Vide.K := 0dépotV(Plein)

2 cases pleines

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

Retrait V(Vide)

Débloqué

Les sémaphoresProducteur-Consommateur

25

FICHIER

ECRITURE

LECTURES

n Ecriture seule - Lectures simultanéesn Un écrivain exclut

n les écrivainsn les lecteurs

n Un lecteur exclut n les écrivains

Les sémaphoresLecteurs / Rédacteurs

26

ECRITURE

n Un écrivain exclut les écrivains et les lecteursn Un écrivain effectue des accès en exclusion

mutuelle des autres écrivains et des lecteurs

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

Les sémaphoresLecteurs / Rédacteurs

27

Les sémaphoresLecteurs / Rédacteursn 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)Ecrivain

28

Les sémaphoresLecteurs / Rédacteursn M'assurer que l'accès au fichier est libre

P(Accès)

entrer en lecture

Libérer l'accès au fichier

V(Accès)Lecteur

29

LECTURES

n Un lecteur exclut les écrivainsn Un premier lecteur doit s'assurer qu'il n'y a pas d'accès en

écriture en coursn Le dernier lecteur doit réveiller un éventuel écrivain

n NL, nombre de lecteurs courants, initialisé à 0

Les sémaphoresLecteurs / Rédacteurs

30

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 = 1NL : = NL + 1

V(Accès)

NL : = NL - 1NL = 0

P(Accès)

P(Mutex)

V(Mutex)

P(Mutex)

V(Mutex)

Lecture

31

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

Lecteur

Les sémaphoresLecteurs / Rédacteurs

32

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

P(Mutex)NL = 1

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

P(ACCES)Bloqué

Non actifNon actif

Les sémaphoresLecteurs / Rédacteurs

33

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

P(Mutex)NL = 2

Accès autorisé

V(Mutex)

Lecture Bloqué Non actif

Les sémaphoresLecteurs / Rédacteurs

34

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

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

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

Lecture

Fichier (E) P(ACCES)Bloqué

Les sémaphoresLecteurs / Rédacteurs

35

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

Bloqué

Ecriture

V(ACCES) Ecriture

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

P(Mutex)bloqué

Les sémaphoresLecteurs / Rédacteurs

36

n 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

Les sémaphoresLecteurs / Rédacteurs

37

n 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

Les sémaphoresLecteurs / Rédacteurs

38

Agendan Semaphore and Threads

Mutexn Mutex is an abbreviation for "mutual

exclusion”n Variable:

n pthread_mutex_t lock;

n Functions:n pthread_mutex_init (*mutex, *attr) n pthread_mutex_destroy (*mutex)n pthread_mutex_lock (*mutex) n pthread_mutex_unlock (*mutex) 39

Implementation with Threadstypedef struct sem_t {

pthread_mutex_t lock; int k;pthread_cond_t sem_cond;

} semaphore;

40

Implementation with Threadsvoid sem_init (semaphore *b, int value) {

pthread_mutex_init (&b->lock, NULL); pthread_cond_init (&b->sem_cond,

NULL); b->k=value;

}

41

Implementation with Threadsvoid sem_p (semaphore *b) {

pthread_mutex_lock (&b->lock);b->k--;if (b->k < 0)

pthread_cond_wait (&b->sem_cond, &b->lock);

pthread_mutex_unlock (&b->lock);

}

42

Implementation with Threadsvoid sem_v (semaphore *b) {

pthread_mutex_lock (&b->lock);b->k++;if (b->k <= 0)

pthread_cond_signal (&b->sem_cond);

pthread_mutex_unlock (&b->lock);}

43

Implementation with Threadsvoid sem_close (semaphore *b) {

pthread_mutex_destroy (&b->lock); pthread_cond_destroy (&b->sem_cond);

}

44

n http://linuxdevcenter.com/pub/a/linux/2007/05/24/semaphores-in-linux.html?page=1

n http://www.csc.villanova.edu/~mdamian/threads/posixsem.html

45

Exercice

n On considère deux machines (M1 et M2) qui travaillent en ligne (concurrence). Un robot permet de transporter une pièce à la fois soit du stock aval de la Machine 1 vers le Stock S, soit du Stock S vers le stock amont de la Machine 2. Le Stock S a une capacité limité à 4 pièces.

n Quelle sont les ressources ?n Ecrire un programme pour modéliser le system 46

M1 M2StockS

Robot