SYSTÈMES D’EXPLOITATION 2
Module 5
Mondher Bouden
Maître assistant
Semestre 2
2023-2024
Partage d’information entre
les processus / threads :
conditions de concurrence
2
Communication inter-processus
• Mémoire partagée
RAM
• Tubes (pipes)
write( ) read( )
fichiers à accès sériel
en sens unique
3
Conditions de concurrence
• Partager un système de stockage (écriture/lecture)
– fichiers (e.g. 2 ajouts parallèles dans un répertoire)
– base de données
– mémoire partagée (shared memory)
• Si deux processus tente d’accéder à ce stockage
partagé, il peut y avoir des bogues subtils:
condition de concurrence / race condition
bogues qui sont très très difficiles à détecter
IFT-2001 Systèmes d'exploitation 4
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
Répertoire de spoule
Proc
Proc
IFT-2001 Systèmes d'exploitation 5
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
interruption
Répertoire de spoule
Proc
Proc
IFT-2001 Systèmes d'exploitation 6
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
B 8
Répertoire de spoule
Proc
B
Proc
IFT-2001 Systèmes d'exploitation 7
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
B 8
retourne à A
Répertoire de spoule
Proc
B
Proc
IFT-2001 Systèmes d'exploitation 8
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
B 8
Répertoire de spoule
Proc
B
Proc
IFT-2001 Systèmes d'exploitation 9
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
• A écrase B…
A 8
Répertoire de spoule
Proc
A
Proc
IFT-2001 Systèmes d'exploitation 10
Exemple condition concurrence
• Spoule d’impression spooler FIFO
• A et B veulent imprimer…
• A écrase B…
A 8
On a un problème….
Répertoire de spoule
Proc
A
Proc
IFT-2001 Systèmes d'exploitation 11
Autre exemple condition concurrence
Fichier CountThread.c
#define N_ITER 1000000
int count = 0; // variable globale (donc partagée entre threads)
void *CodeThread(void * a) {
int i, tmp;
for(i = 0; i < N_ITER; i++) {
tmp = count; // copie locale de variable globale
tmp = tmp + 1; // incrémente la copie locale
count = tmp; // écrit dans globale
}
}
int main(int argc, char **argv) {
pthread_t Count1, Count2;
pthread_create(&Count1, 0, CodeThread, 0);
pthread_create(&Count2, 0, CodeThread, 0);
pthread_join(Count2, 0);
pthread_join(Count1, 0);
printf("Le total est %d\n",count);
}
Que sera la valeur finale affichée de count? 12
Autre exemple condition concurrence
Fichier CountThread.c
#define N_ITER 1000000
int count = 0; // variable globale (donc partagée entre threads)
void *CodeThread(void * a) {
int i, tmp;
for(i = 0; i < N_ITER; i++) {
tmp = count; // copie locale de variable globale
section
tmp = tmp + 1; // incrémente la copie locale
critique
count = tmp; // écrit dans globale
}
}
Avec 2 thread, valeur finale :
N_ITER < count < 2*N_ITER
valeurs
différentes
13
Northeast Blackout de 2003
• 14 Août 2003, 4:11 PM
• 55 millions de gens plongés dans le noir
• Une partie du problème : condition de
concurrence dans un serveur d’alerte de
FirstEnergy Corp.
• Une ligne électrique tombe en panne
• Deux processus ont écrit en même temps
dans une structure de données
• Système d’alarme tombe en boucle infinie
• Effet cascade… les lignes de transmissions
tombent une après l’autre
• 11 morts*, 6 milliards $ de pertes
*crise cardiaque, CO, incendies (chandelles) 14
Section critique : définition
• Section qui modifie/lit données communes
Un seul processus ou thread à la fois peut
exécuter son code de section critique
15
Sections critiques entre processus
• Empêcher l’accès par plus d’un processus en
même temps
(ou thread)
16
4 critères à respecter pour partage données
• Exclusion mutuelle : 2 processus ne peuvent pas
être dans la section critique en même temps
• Pas d’interblocage : Aucun processus ne doit
bloquer les autres à l’entrée de leur section
critique s’il est hors de sa section critique
• Pas de famine : Aucun processus ne doit attendre
indéfiniment pour entrer dans la section critique
• Aucune hypothèse : Pas de supposition sur le
temps d’exécution ou le nombre de CPU
17
Solutions?
18
Variable de verrou?
• Une variable verrou qui empêche un thread
d’exécuter certaines tâches.
– Verrouiller avant d’entrer en section critique et
accéder à de l’information partagée.
– Déverrouiller en quittant, après l’accès aux données
partagées
– Attendre, si c’est verrouillé
19
Variable de verrou?
• Une variable verrou verrou == 1 signifie occupé
while (verrou==1); // on attend la libération du verrou
verrou = 1; // vérouille
section_critique();
verrou = 0; // dévérouille
Est-ce qu’il y a un problème?
20
Variable de verrou?
• Une variable verrou verrou == 1 signifie occupé
while (verrou==1); // on attend la libération du verrou
verrou = 1; // vérouille
section_critique();
verrou = 0; // dévérouille
• Si changement de contexte à la flèche ?
21
Variable de verrou?
• Une variable verrou verrou == 1 signifie occupé
while (verrou==1); // on attend la libération du verrou
verrou = 1; // vérouille
section_critique();
verrou = 0; // dévérouille
• Si changement de contexte à la flèche ?
– Peut ne pas fonctionner
– (voir spoule d’impression)
22
Solutions possibles pour synchroniser
• Solution de Peterson
• Verrou pivotant (spinlock)
• Sémaphore
• Mutex
• Variables de conditions
• Barrières
• Solutions « propriétaires » (Windows)
– CriticalRegion
– Interlocked
23
Solution de Peterson (logicielle)
• Deux processus avec une section critique
Processus/thread 0 Processus/thread 1
… …
enter_region(0); enter_region(1);
CodeCritique(); CodeCritique();
leave_region(0); leave_region(1);
… …
s’identifier
24
Attente active (Busy Waiting)
• Les solutions comme celle de Peterson sont des
verrous pivotants : spinlock
• Font appel à l’attente active (busy waiting) :
– consomme CPU/énergie
• Néanmoins, peut être efficace si le blocage est
court :
– ne force pas un changement de contexte
25
Sémaphore
• Moyen de communiquer à distance
• Synchroniser des processus/threads en les
bloquant 26
Sémaphore
• Contient :
– liste L des processus/thread en attente
– compteur K
• peut représenter le nombre de ressources libres, par exemple
• Fonction down : (peut bloquer)
– si K > 0, décrémente K et retourne immédiatement
– si K == 0, se place dans la liste L et fait un sleep();
• Fonction up : (ne bloque jamais)
– si L n’est pas vide : wakeup(retire(L));
– si L est vide : K=K+1; ordre de retrait : non-spécifié
• Fonctions up et down sont atomiques
27
Prod./consomm. avec sémaphores
• N: nombre de place disponible dans la file
semaphore mutex=1; pour section critique
pseudo-code, où la valeur
semaphore empty=N; capacité file
assignée initialise K
semaphore full =0;
void producer(void) { void consumer(void) {
int item; int item;
while (TRUE) { while (TRUE) { bloque si
bloque
item=produce(); vide
down(&empty); down(&full);
si plein down(&mutex); down(&mutex); section
[Link](item); item = [Link](); critique
up(&mutex); up(&mutex);
up(&full); up(&empty);
} consume(item);
} }
}
Fonctionne! 28
mutex : mutuellement exclusif
• Sorte de sémaphore spécialisé : binaire
– 0 : verrouillé
– 1 : déverrouillé (ou libre)
• mutex_lock(mutex)
– verrouille le mutex si déverrouillé,
– sinon bloque.
• mutex_unlock(mutex)
– libère le mutex. Si autres threads bloqués sur mutex,
l’un d’eux est choisis.
29
Retour sur l’exemple condition concurrence
#define N_ITER 1000000
int count = 0; // variable globale (donc partagée entre threads)
void *CodeThread(void * a)
{
int i, tmp;
for(i = 0; i < N_ITER; i++)
{
tmp = count; // copie locale de variable globale
tmp = tmp + 1; // incrémente la copie locale
count = tmp; // écrit dans globale
}
}
• Avec 2 thread :
Valeur finale : N_ITER < count < 2*N_ITER
30
POSIX : pthreads mutex
• Interface standard pour mutex sur UNIX
pthread_mutex_init Crée un nouveau mutex
pthread_mutex_destroy Détruit un mutex
pthread_mutex_lock Verrouille un mutex ou bloque
pthread_mutex_trylock Verrouille un mutex ou échoue
pthread_mutex_unlock Déverrouille un mutex
31
Exemple condition concurrence corrigé
#define N_ITER 1000000
// variables globales (donc partagées entre threads)
int count = 0;
pthread_mutex_t monMutex; // Il reste a l’initialiser...
void *CodeThread(void * a)
{
int i, tmp;
for(i = 0; i < N_ITER; i++)
{
pthread_mutex_lock(&monMutex);
tmp = count; // copie locale de variable globale
section tmp = tmp + 1; // incrémente la copie locale
critique count = tmp; // écrit dans globale
pthread_mutex_unlock(&monMutex);
}
}
32
Types de mutex sur Linux
Détermine le comportement lors du pthread_mutex_lock()
• PTHREAD_MUTEX_NORMAL (par défaut)
– appel pthread_mutex_lock est bloquant si mutex est occupé
• PTHREAD_MUTEX_RECURSIVE
– concept de compteur inclus
– pour appels récursifs par le même thread
– doit faire pthread_mutex_unlock autant de fois que
pthread_mutex_lock
• PTHREAD_MUTEX_ERRORCHECK
– retourne erreur si thread essaie de faire un deuxième appel
pthread_mutex_lock sans avoir libéré le mutex
33
Barrières
• Pour synchroniser un groupe de threads ensemble
• Exemple : - calcul sur une matrice dans itération
- traitement d’une image
34
POSIX : Barrières
pthread_barrier_init Crée une barrière
pthread_barrier_destroy Détruit une barrière
pthread_barrier_wait Attend à une barrière
35
POSIX : exemple code barrières
pthread_barrier_t Barriere; // variable globale
int main() {
…
pthread_barrier_init(&Barriere, NULL, N_THREADS);
…
nombre de thread
démarrer les threads
à attendre
}
void *FonctionThread(void *Arg) {
TacheA();
pthread_barrier_wait(&Barriere);
TacheB();
}
36
Windows API : Threads
créer un thread
taille de la pile
attendre après des objets
(équivalent d’un
wait/barrière)
détruire un thread
37
Windows API : Mutex
(globale pour être visible
de tous les threads)
un nom permet de partager
un mutex entre processus
attendre après un
objet (équivalent d’un
lock/down)
38
Windows API : CriticalSection
(globale pour être visible de toutes les threads)
(quelque part dans votre code)
39
Variables de conditions
• mutex : permet de limiter l’accès aux zones
critiques.
• sémaphores : permet à K threads d’accéder à
une ressource.
• variables de conditions : pour qu’un thread se
bloque, le temps qu’une condition soit remplie.
Par exemple, attendre qu’un buffer ne soit pas
vide.
40
POSIX : pthreads cond
pthread_cond_init Crée une variable de condition
pthread_cond_destroy Détruit une variable de condition
pthread_cond_wait Attend une variable de condition
pthread_cond_signal Signale un thread en attente
pthread_cond_broadcast Signale tous les threads en attente
41
POSIX : pthreads cond
• pthread_cond_signal sans mémoire
• pthread_cond_wait bloque toujours le
thread appelant
• pthread_cond_wait se fait toujours à
l’intérieur d’une section critique
– pour que lorsqu’on
a) teste la condition
b) bloque si la condition n’est pas remplie
– il n’y ait pas de condition de concurrence (autre
thread qui s’exécute entre a) et b) )
42
Prod. consomm. avec condition
Condition : buffer plein (buf!=0) ou vide (buf==0)
int buf = 0; // buffer avec une seule case
void *producer(void *ptr) { void *consumer(void *ptr) {
int i; int i;
for (i=1; i<=MAX; i++) { for (i=1; i<=MAX; i++) {
pthread_mutex_lock(&mutex); pthread_mutex_lock(&mutex);
while (buf!=0) { while (buf==0) {
sec. crit.
pthread_cond_wait(&condp,&mutex); pthread_cond_wait(&condc,&mutex);
} }
buf = i; buf = 0;
pthread_cond_signal(&condc) pthread_cond_signal(&condp)
pthread_mutex_unlock(&mutex); pthread_mutex_unlock(&mutex);
} }
phthread_exit(0); pthread_exit(0);
} }
pthread_cond_wait libère automatiquement le mutex. Au retour, mutex est
acquis de nouveau.
43
Exemple exécution Prod. consomm.
PRODUCTEUR CONSOMMATEUR
buf = 0;
iteration i = 1
pthread_mutex_lock(&mutex);
while (buf!=0)
buf = 1;
pthread_cond_signal(&condc)
pthread_mutex_unlock(&mutex);
iteration i = 2
pthread_mutex_lock(&mutex);
while (buf!=0) {
pthread_cond_wait(&condp,&mutex);
extrait de
iteration i=1
pthread_cond_wait() : pthread_mutex_lock(&mutex);
while (buf==0) buf est 1
buffer = 0;
pthread_cond_signal(&condp)
pthread_mutex_unlock(&mutex);
...
44
sémaphore vs. condition
SÉMAPHORE
K=1 K déjà à 0
K=0 up() down()
thread 0
thread 1
down() up()
K=0
CONDITION temps
signal sans effet
signal() signal()
[Link]() [Link]() [Link]() [Link]()
thread 0
thread 1
[Link]() wait() [Link]()
temps
note: 2 processeurs
section critique 45
Règle de codage
• Essaie d’avoir les zones critiques les plus
courtes possibles en temps d’exécution.
• Minimise la probabilité d’avoir mutex/spinlock
bloquée → minimise temps d’attente.
• Faire le traitement des données en dehors du
mutex.
46
Résumé
• Quand on a plus d’un thread, on doit contrôler l’accès
aux variables partagées
• Section critique : code qui accède à ces variables
• Façons de synchroniser l’exécution entre thread :
– solution de Peterson (solution logicielle)
– TSL, XCHG (solution matérielle)
– sémaphore (K à la fois)
– mutex (1 à la fois) solutions que vous
– variables de conditions allez employer la
– barrières plupart du temps
– CriticalSection (Windows API)
47