Upload
others
View
0
Download
0
Embed Size (px)
Citation preview
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