Synchronisation¶
Ressource critique¶
Problématique¶
Lorsque deux tâches (processus ou threads) accèdent à une même zone mémoire, elles peuvent interagir de manière indésirable,
- même si chaque tâche, prise indiduellement, se comporte correctement.
Concurence sans problème¶
Concurence problématique¶
Définitions¶
- Une ressource est dite ressource critique lorsque des accès concurrents à cette ressources peuvent résulter dans un état incohérent.
- On parle aussi de situation de compétition (race condition) pour décrire une situation dont l’issue dépend de l’ordre dans lequel les opérations sont effectuées.
- Une section critique est une section de programme manipulant une ressource critique.
Exclusion mutuelle¶
Une section de programme est dite atomique lorsqu’elle ne peut pas être interrompue par un autre processus manipulant les mêmes ressources critiques.
→ c’est donc une atomicité relative à la ressource
Un mécanisme d”exclusion mutuelle sert à assurer l’atomicité des sections critiques relatives à une ressource critique.
→ en anglais : mutual exclusion, ou mutex
Mise en œuvre abstraite¶
int compte; /* commun */
void entrer_SC_compte();
void sortir_SC_compte();
printf("ajout de 1000€\n"); /* tâche 1 */
entrer_SC_compte();
compte += 1000;
sortir_SC_compte();
printf("ajout effectué\n");
printf("retrait de 500€\n"); /* tâche 2 */
entrer_SC_compte();
compte -= 500;
sortir_SC_compte();
printf("retrait effectué\n");
Mutex: Critères d’évaluation¶
- Exclusion : deux tâches ne doivent pas se trouver en même temps en SC
- Progression : une tâche doit pouvoir entrer en SC si aucune autre ne s’y trouve
- Équité : une tâche ne devrait pas attendre indéfiniment pour entrer SC
- L’exclusion mutuelle doit fonctionner dans un contexte multi-cœurs
Mauvaise solution : attente active¶
On utilise un booléen partagé comme « verrou »
int verrou = 0;
void entrer_SC() { while (verrou) {}
verrou = 1; }
void sortir_SC() { verrou = 0; }
Défauts de l’attente active¶
Le processus qui attent consomme du temps processeur (d’où le nom d’attente active).
→ NB: on peut améliorer cela en mettant un
sleepou unyielddans la boucle.Cette approche n’assure par l’exclusion!
→ verrou est lui même une ressource critique.
Bonne solution¶
- On associe à la ressource un jeton, que les processus peuvent prendre et reposer
- Seul le processus possédant le jeton devrait manipuler la ressource
- Donc, si un processus souhaite manipuler la ressource et que le jeton est pris, il doit d’abord attendre que le jeton redevienne disponible
- Utilisation d’un sémaphore initialisé à 1
Mise en œuvre concrète¶
int compte; /* commun */
sem_t mutex_compte;
status = sem_init(&mutex_compte, 1, 1);
printf("ajout de 1000€\n"); /* tâche 1 */
status = sem_wait(&mutex_compte);
compte += 1000;
status = sem_post(&mutex_compte);
printf("ajout effectué\n");
printf("retrait de 500€\n"); /* tâche 2 */
status = sem_wait(&mutex_compte);
compte -= 500;
status = sem_post(&mutex_compte);
printf("retrait effectué\n");
Remarques¶
Certaines opérations sur la ressource critiques ne nécessitent pas forcément d’exclusion mutuelle.
→ exemple : lecture de la valeur du compte (si on accepte que la valeur lue devienne rapidement invalide…)
Le mécanisme d’exclusion mutuelle n’est pas une protection, mais une convention entre les processus souhaitant utiliser la ressource sans la corrompre.
→ il est toujours possible de manipuler la ressource sans « prendre le jeton »
Remarques (2)¶
Les sections critiques sont un mal nécessaire:
- un mal, parce qu’elles empêches le parallélisme qu’on a eu tant de mal à mettre en place… elles réduisent donc les performances.
- nécessaire, parce qu’elles garantissent l’intégrité des ressources critiques
Conséquence :
- les éviter lorsqu’on le peut (e.g. en concevant des structures de données toujours cohérentes)
Remarques (3)¶
- sinon, les réduire au strict minimum
/* n'écrivez PAS --------------------------------- */
status = sem_wait(&mutex_compte);
printf("ajout de 1000€\n");
compte += 1000;
printf("ajout effectué\n");
status = sem_post(&mutex_compte);
/* mais écrivez ---------------------------------- */
printf("retrait de 500€\n");
status = sem_wait(&mutex_compte);
compte -= 500;
status = sem_post(&mutex_compte);
printf("retrait effectué\n");
Inter-blocage¶
Un inter-blocage (deadlock) est une situation où plusieurs tâches sont bloquées car chacune attend un événement que doit produite une autre.
Un exemple classique se produit lorsque deux tâche attendent chacune un « jeton » détenu par l’autre :
/* tâche 1 */ /* tâche 2 */
sem_wait(&mutex_A); sem_wait(&mutex_B);
utilise(A); utilise(B);
sem_wait(&mutex_B); sem_wait(&mutex_A);
utilise(A, B); utilise(A, B);
/* ... */ /* ... */
Solution possible¶
Une manière d’éviter les inter-blocages consiste à toujours réclamer les ressources dans le même ordre (quitte à libérer une ressource avant de la réclamer à nouveau).
/* tâche 1 */ /* tâche 2 */
sem_wait(&mutex_A); sem_wait(&mutex_B);
utilise(A); utilise(B);
sem_wait(&mutex_B); sem_post(&mutex_B);
utilise(A, B); sem_wait(&mutex_A);
/* ... */ sem_wait(&mutex_B);
utilise(A, B);
/* ... */
Problèmes typiques de synchronisation¶
Pas une liste exhaustive, mais une source d’inspiration.
Producteurs/consommateurs¶
Un ensemble de processus, divisé en deux catégories, partage une zone mémoire.
Les premiers (producteurs) remplissent la mémoire partagée, avec des éléments.
→ la mémoire ne peut contenir qu’un nombre d’éléments limité et connu à l’avance
Les seconds (consommateurs) utilisent ces éléments et les retirent de la mémoire.
Exemple : file d’impression
Exemple¶
Problème¶
- Un producteur doit se bloquer lorsque la mémoire partagée est pleine
- Un consommateur doit se bloquer lorsque la mémoire partagée est vide
Principe de solution¶
- Utilisation de deux sémaphores, implémentant les deux critères de blocage
- l’un représente le nombre de cases libres
- l’autre représente le nombre de cases occupées
- Analogie : deux piles de jetons, avec une quantité de jetons constante
- les jetons passent d’une pile dans une autre lorsqu’une case change d’état
Principe de solution (2)¶
Si les opérations sur la zone mémoire partagée ne sont pas atomiques, il faut les protéger par une section critique
→ troisième sémaphore
Algorithme¶
elt_t tab[N]
sem_t libres, occupes, mutex;
sem_init(&libres, 1, N);
sem_init(&occupes, 1, 0);
sem_init(&mutex, 1, 1);
void producteur() {
elt_t e = produire();
sem_wait(&libres);
sem_wait(&mutex);
ajouter(e, tab);
sem_post(&mutex);
sem_post(&occupes);
}
|
void consommateur() {
sem_wait(&occupes);
sem_wait(&mutex);
elt_t e = retirer(tab);
sem_post(&mutex);
sem_post(&libres);
consommer(e);
}
|
Remarques¶
- « Passage » de jetons entre
libresetoccupes - Ordre emboitement correct des sémaphores (inter-blocage)
- Opérations de production/consommation hors de la section critique (paralélisme, cf. section précédente)…
- …mais également sans posséder de jeton
libres/occupes.
Lecteurs/rédacteurs¶
Un ensemble de processus, divisé en deux catégories, partage une zone mémoire.
Certains processus (les lecteurs) font des accès en lecture seule à cette zone.
D’autres processus (les rédacteurs) modifient le contenu de cette zone.
NB : on parle parfois d’écrivains plutôt que de rédacteurs
Problème¶
Lorsqu’un rédacteur accède à la mémoire partagée, aucune autre processus (qu’il soit lecteur ou rédacteur) ne doit y avoir accès.
→ problème d’exclusion mutuelle classique
En revanche, les lecteurs peuvent être plusieurs à utiliser la zone en même temps, cela ne pose pas de problème.
Principe de solution¶
- On protège la mémoire partagée par une exclusion mutuelle, mais…
- les lecteurs n’ont besoin de cette exclusion mutuelle que si aucun autre lecteur n’utilise la mémoire ;
- pour le vérifier, ils utilisent un compteur (nombre de lecteurs en train d’utiliser la zone), lui aussi protégé par une exclusion mutuelle.
Algorithme¶
int c = 0; //
sem_t mutex_m, mutex_c;
sem_init(&mutex_m, 1, 1);
sem_init(&mutex_c, 1, 1);
void redacteur() {
sem_wait(&mutex_m);
ecrire(e, tab);
sem_post(&mutex_m);
}
|
void lecteur() { //
sem_wait(&mutex_c);
if (c == 0)
sem_wait(&mutex_m);
c += 1;
sem_post(&mutex_c);
lire();
sem_wait(&mutex_c);
if (c == 1)
sem_post(&mutex_m);
c -= 1;
sem_post(&mutex_c);
}
|
Remarques¶
Le lecteur qui prend le jeton de mutex_m n’est pas forcément celui qui le rend
On note que les lecteurs peuvent parfois se bloquer dans la section critique du compteur c.
→ Cela peut-il créer un inter-blocage ?
L’algorithme proposé fonctionne, mais n’assure pas l’équité : un rédacteur peut attendre indéfiniment avant d’avoir accès à la mémoire (famine)
→ Comment le modifier pour assurer l’équité ?
Philosophes¶
Illustration : © Benjamin Esham
Problème proposé par Dijkstra.
Cinq philosophes passent leur vie à penser et manger autour d’une table.
Pour manger, ils ont besoin de deux fourchettes, mais il n’y a que cinq fourchettes.
Problème¶
Proposer un algorithme qui évite :
- les inter-blocages
- la famine
Mauvaise solution :
chaque philosophe, lorsqu’il a faim, prend la fourchette de gauche, puis celle de droite, mange, puis les repose
Principe de solution¶
Chaque philosophe a trois états :
« je pense », « j’ai faim », « je mange »
par lesquels il passe toujours dans cet ordre
Lorsqu’il a faim, un philosophe ne peut manger que si ses deux voisins ne mangent pas, sinon attend
Lorsqu’il termine de manger, le philosophe réveille ses voisins et se remet à penser
Algorithme¶
sem_t mutex; // init à 1
sem_t reveils[N];// init à 0
int etats[n]; // init à PENSE
void CommenceManger(int id) {
sem_wait(mutex);
etats[id] = FAIM;
bool ok = etat[id-1] != MANGE
&& etat[id+1] != MANGE;
if (ok) {
etat[id] = MANGE;
sem_post(mutex);
} else {
sem_post(mutex);
sem_wait(reveils[id]);
}
}
|
void FinitManger(int id) {
sem_wait(mutex);
etats[id] = PENSE;
/* voisin gauche */
if (etat[id-1] == FAIM
&& etat[id-2] != MANGE) {
etat[id-1] = MANGE;
sem_post(reveils[id-1]);
}
/* voisin droit */
if (etat[id+1] == FAIM
&& etat[id+2] != MANGE) {
etat[id+1] = MANGE;
sem_post(reveils[id+1]);
}
sem_post(mutex);
}
|
Remarques¶
- L’algorithme proposé prévient les inter-blocages, mais pas la famine.
- Pour l’améliorer, une solution consiste à ne réveiller un voisin que si son autre voisin (id±2) n’est pas dans l’état FAIM depuis trop longtemps / depuis plus longtemps que lui
Mutex internes au système¶
Motivation¶
Le système d’exploitation lui même peut avoir besoin d’exclusion mutuelle, pour toutes ses structures de données…
… et notamment pour les sémaphores eux-mêmes !
→ on ne peut pas utiliser de sémaphore pour implémenter un sémaphore…
Problème¶
Les procédures sem_wait et sem_post sont des sections critiques pour le sémaphore lui même…
proc sem_wait(sem): .
si sem.c = 0 alors
bloquer le processus courant
finsi
sem.c ← sem.c - 1
proc sem_post(sem)
sem.c ← sem.c + 1
si des processus sont bloqués
en attente du sémaphore
alors
débloquer un des processus
finsi
Sections critiques dans un sémaphore¶
proc sem_wait(sem): entrer_SC() si sem.c = 0 alors sortir_SC() bloquer le processus courant sinon sem.c ← sem.c - 1 sortir_SC() finsi |
proc sem_post(sem): entrer_SC() sem.c ← sem.c + 1 si des processus sont bloqués en attente du sémaphore alors débloquer un des processus sem.c ← sem.c - 1 finsi sortir_SC() |
Exclusion mutuelle de bas niveau¶
On utilise l’instruction test_and_set du langage machine: elle consulte et modifie une variable de manière atomique:
- si la variable vaut 1, elle retourne 1
- si la variable vaut 0, elle la met à 1 et retourne 0
Cela permet d’écrire une attente active qui assure l’exclusion:
void entrer_SC() { while (test_and_set(&verrou)) {} }
Autres solutions¶
- Il existe des solutions purement logicielles (i.e. qui ne nécessitent pas l’existence d’instruction atomique pour tester et modifier une variable)
- Mécanismes plus complexe qu’un simple verrou, pour
ne rien avoir à faire après l’attente active
- tableau de verrous
- notion de tour
Conclusion¶
À retenir¶
- Les signaux et les sémaphores permettent la synchronisation de processus.
- Problèmes typiques de synchronisation :
- exclusion mutuelle,
- problèmes plus complexes.
- À un plus bas niveau, on doit avoir recours à l’attente active :
- implémentation des sémaphores,
- mais aussi certains périphériques ne gérant pas les interruptions…