Multithreading et synchronisation
Guillaume Salagnac
Insa de Lyon – Informatique
2019–2020
Plan
1. Introduction : la notion de thread
2. Problème de l’exclusion mutuelle
3. Un mécanisme de synchro universel : le sémaphore
2/36
Rappel : la notion de processus
Définition : processus VPN
«un programme en cours 0
d’exécution» 1
• isolés les uns des autres 2
• en temps : CPU virtuel
• en espace : mémoire virtuelle
• Process Control Block
• numéro = PID
• environnement, répertoire
courant, fichiers ouverts...
• copie des registres CPU
• vue mémoire = Page Table
• Page Table
• instructions = .text
• variables globales = .data
• tas d’allocation = .heap
Virtual Address Space
• pile d’exécution = .stack
3/36
Notion de thread (VF fil d’exécution)
VPN
Définition : thread 0
«une tâche indépendante à 1
l’intérieur d’un processus» 2
• pourquoi les threads ?
• profiter de plusieurs CPU
• faciliter la programmation
• vue mémoire commune
• pas d’isolation matérielle
• variables globales partagées
• tas d’allocation commun
• ordonnancement indépendant
• un VCPU privé
TCB = Thread Control Block
• une pile d’exécution privée
• variables locales privées
Virtual Address Space
4/36
Notion de thread : remarques
• parfois appelé «processus léger» mais vision archaïque
• en vrai : un PCB = une PT et un/plusieurs TCB
• par ex : task_struct et mm_struct dans Linux
• un thread ne peut pas vivre en dehors d’un processus
• besoin d’une vue mémoire
• un processus vivant a toujours au moins un thread
• «main thread» = thread qui exécute main()
• lorsque zéro thread I processus terminé
5/36
Rappel : changement de contexte
Thread 1 Noyau Thread 2
T1 est actif
copier les
interruption registres CPU
vers TCB1
ou syscall
choisir T2
T2 est inactif
T1 est inactif ssi P1 6= P2:
vidanger cache
et adopter PT
charger les de P2
registres CPU
depuis TCB2 RETI T2 est actif
6/36
API POSIX : Threads
#include <pthread.h>
/* opaque typedefs */ pthread_t, pthread_attr_t;
// create and start a new thread
int pthread_create(pthread_t *thread,
pthread_attr_t *attr,
void * (*function) (void *),
void *arg);
// terminate the current thread
void pthread_exit(void *retval);
// terminate another thread
int pthread_cancel(pthread_t thread);
// wait for another thread to terminate
int pthread_join(pthread_t thread, void **retvalp);
7/36
Plan
1. Introduction : la notion de thread
2. Problème de l’exclusion mutuelle
3. Un mécanisme de synchro universel : le sémaphore
8/36
Accès concurrents à une variable partagée
Variable partagée
Thread A Thread B
int var = 5;
{ {
... ...
... ...
var = var+1; var = var-1;
... ...
... ...
} }
Question : que vaut var à la fin de l’exécution ?
• intuition : var==5
• réalité : var==5 ou var==4 ou var==6
9/36
Explication : code source 6= instructions du processeur
Variable partagée
Thread A Thread B
var: 00000005
... ...
... ...
LOAD REGa←[var] LOAD REGb←[var]
INCR REGa DECR REGb
STORE REGa →[var] STORE REGb →[var]
... ...
... ...
Remarque : A et B exécutés sur des (V)CPU distincts
I REGa et REGb (physiquement ou logiquement) distincts
10/36
Quelques exécutions possibles
TA var = 5 TB TA var = 5 TB TA var = 5 TB
LOAD REGa←[var] LOAD REGa←[var] LOAD REGa←[var]
INCR REGa context switch DECR REGb
STORE REGa→[var] LOAD REGb←[var] context switch
context switch DECR REGb LOAD REGb←[var]
LOAD REGb←[var] STORE REGb→[var] INCR REGa
DECR REGb context switch STORE REGa→[var]
STORE REGb→[var] INCR REGa context switch
STORE REGa→[var] STORE REGb→[var]
var = 5
var = 6 var = 4
Remarque : 1 CPU ou 2 CPU I problème semblable
11/36
Notion de «race condition»
VF «situation de concurrence», course critique, accès concurrents
Définition : race condition
Situation où le résultat du programme dépend de l’ordre dans
lequel sont exécutées les instructions des threads
Remarques
• plusieurs accès concurrents à une ressource partagée
• variable globale, fichier, réseau, base de données...
• écriture+écriture = problème
• écriture+lecture = problème
• concurrence : parallélisme et/ou entrelacement
• i.e. quand on ne maîtrise pas l’ordre temporel des actions
• risques : corruption de données et/ou crash
• mauvaise nouvelle : très difficile à débugger en pratique
• bonne nouvelle : des protections efficaces existent
12/36
Situation de concurrence : exemples
• deux écritures concurrentes = conflit
Thread A: x=10
Question : valeur finale de x ?
Thread B: x=20
• une lecture et une écriture concurrentes = conflit
Init: x=5
Thread A: x=10 Question : valeur affichée ?
Thread B: print(x)
Précepte : race condition = bug
Un programme dans lequel plusieurs tâches peuvent se retrouver
en situation de concurrence est un programme incorrect.
13/36
Objectif : garantir l’exclusion mutuelle
Définitions
• Action atomique : action au cours de laquelle aucun état
intermédiaire n’est visible depuis l’extérieur
• Ressource critique : objet partagé par plusieurs threads et
susceptible de subir une race condition
• Section critique : morceau de programme qui accède a
une ressource critique
Idée : on veut que chaque section critique soit atomique
Définition : exclusion mutuelle
Interdiction pour plusieurs threads de se trouver simultanément
à l’intérieur d’une section critique
Idée : «verrouiller» l’accès à une section critique déjà occupée
14/36
Exclusion mutuelle par verrouillage
Variables partagées
Thread A int var = 5; Thread B
lock_t L;
{ {
... ...
lock(L); lock(L);
var = var+1; var = var-1;
unlock(L); unlock(L);
... ...
} }
On voudrait ces deux méthodes atomiques :
• lock(L) pour prendre le verrou L en exclusivité
I un seul thread peut entrer en section critique
• unlock(L) pour relâcher le verrou L
I permet aux autres threads de le prendre à leur tour
15/36
Exclusion mutuelle : illustration
A entre en section critique A sort de la section critique
lock() unlock()
TA
lock() unlock()
TB temps
B attend
B veut entrer en B sort de la
B entre en
section critique section critique
section critique
16/36
Problème : comment garantir l’exclusion mutuelle ?
Autrement dit : comment implémenter lock() et unlock() ?
Propriétés souhaitables
• Exclusion mutuelle : à chaque instant, au maximum une seule
tâche est en section critique
• sinon risque de race condition
• Progression : si aucune tâche n’est en section critique, alors une
tâche exécutant lock() ne doit pas se faire bloquer
• sinon risque de deadlock, en VF interblocage
• Équité : aucune tâche ne doit être obligée d’attendre indéfiniment
avant de pouvoir entrer en section critique
• sinon risque de starvation, en VF famine, privation
• Généralité : pas d’hypothèses sur les vitesses relatives ou sur le
nombre des tâches en présence
• on veut une solution universelle
• Bonus : implem simple, algo prouvable, exécution efficace...
17/36
Solution naïve (et incorrecte)
partagé
int turn = 1;
Thread A Thread B
while(1) while(1)
{ ... { ...
while(turn==2) while(turn==1)
{/* attendre */ } {/* attendre */ }
// section critique // section critique
turn = 2; turn = 1;
... ...
} }
• Exclusion mutuelle : OK
• Attente active : exécution pas très efficace
• Problème : alternance stricte I progression non garantie
18/36
Solution naïve no 2 (incorrecte aussi)
partagé
Thread A bool occup = 0; Thread B
while(1) while(1)
{ ... { ...
while(occup != 0) while(occup != 0)
{/* rien */ } {/* rien */ }
occup = 1; occup = 1;
// section critique // section critique
occup = 0; occup = 0;
... ...
} }
• Progression : OK
• Exclusion mutuelle : non garantie
• Problème : consultation-modification non atomique
19/36
Solutions correctes
Masquer les interruptions
• idée : empêcher tout changement de contexte
I dangereux, et inapplicable sur machine multiprocesseur
Approche purement logicielle
• idée : programmer avec des instructions atomiques
• autrefois seulement LOAD et STORE I par ex. algo de Peterson
• de nos jours : TEST-AND-SET, COMPARE-AND-SWAP I spin-lock
I attente active = souvent inefficace à l’exécution
Approche noyau : intégrer synchronisation et ordonnancement
• idée : programmer avec des instructions atomiques
• mais les cacher dans le noyau (derrière des appels système)
I permet de bloquer / réveiller les threads au bon moment
20/36
Mutex : définition
Verrou exclusif, ou en VO mutex lock
• objet abstrait = opaque au programmeur
• deux états possibles : libre=unlocked ou pris=locked
• offre deux méthodes atomiques
• lock(L) : si le verrou est libre, le prendre
sinon, attendre qu’il se libère
• unlock(L) : relâcher le verrou,
c.à.d. le rendre libre à nouveau
Remarques
• lock() et unlock() implémentés comme appels système
• threads en attente = état BLOCKED dans l’ordonnanceur
• une file de threads suspendus pour chaque mutex
• invoquer unlock() réveille un thread suspendu (s’il y en a)
• attention : ordre de réveil non spécifié
21/36
API POSIX : Mutex locks
#include <pthread.h>
/* opaque typedefs */ pthread_mutex_t, pthread_mutexattr_t;
// create a new mutex lock
int pthread_mutex_init(pthread_mutex_t *mutex,
pthread_mutexattr_t *mutexattr);
int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);
// attempt to lock a mutex without blocking
int pthread_mutex_trylock(pthread_mutex_t *mutex);
22/36
Exclusion mutuelle : en résumé
Notion de «race condition»
• plusieurs accès concurrents à une même variable
• accès non atomique I données incohérentes
Section critique
• morceau de code qu’on veut rendre atomique
I exécution nécessairement en exclusion mutuelle
Solution : utiliser un mutex lock
• lock(L);
/* section critique */
unlock(L);
• nécessite que tous nos threads jouent le jeu
23/36
Plan
1. Introduction : la notion de thread
2. Problème de l’exclusion mutuelle
3. Un mécanisme de synchro universel : le sémaphore
24/36
Scénario producteur-consommateur : introduction
Deux threads communiquent via une file FIFO partagée
P C
Producteur Consommateur
while(1) while(1)
{ {
item=produce(); item = fifo_get();
fifo_put(item); consume(item);
} }
Remarques :
• file = tampon circulaire de taille constante
• producteur doit attendre tant que la file est pleine
• consommateur doit attendre tant que la file est vide
25/36
Prod.-consomm. : solution naïve (et incorrecte)
partagé
item_t buffer[N];
int count=0;
Producteur Consommateur
int in = 0; int out = 0;
while(1) while(1)
{ {
item=produce() while(count == 0) {}
while(count == N) {} item = buffer[out];
buffer[in] = item; out = (out+1) % N;
in = (in+1) % N; count = count - 1;
count = count + 1; consume(item);
} }
Observation : ce programme a des bugs de synchronisation
I Question : comment corriger le problème ?
26/36
Producteur-consommateur : remarques
• buffer partagé de taille N (constante) initialement vide
• buffer circulaire : x%N = x modulo N
• fonctions produce() et consume() non pertinentes
• supposées «purement séquentielles» AKA inoffensives
• variable partagée count pour la synchronisation
• indique le nombre d’éléments actuellement dans le buffer
• variables in et out : non partagées
• exemple avec N=10 :
count = 7
in = 5 out = 8
N J O U R B O
0 1 2 3 4 5 6 7 8 9
Mauvaise nouvelle
Cette synchro est irréalisable avec seulement lock()/unlock()
27/36
Quelques scénarios classiques de synchronisation
Exclusion mutuelle
Producteur consommateur, en VO bounded buffer problem
P C
Boucle parallèle, en VO fork-join
Rendez-vous, en VO barrier
28/36
Notion de sémaphore (Edsger W. Dijkstra 1930–2002)
• objet abstrait = opaque au programmeur
• contient une variable entière k
• initialisée avec k>0 lors de la création du sémaphore
• contient une file d’attente de threads bloqués
• offre deux méthodes atomiques P() et V()
P(S) V(S)
S.k = S.k - 1; S.k = S.k + 1;
if( S.k < 0 ) if( S.k <= 0 )
{ {
/* suspendre le thread /* ré veiller l’un des
appelant, et le threads de la file
mettre dans la file d’attente de S */
d’attente de S */ }
}
29/36
Sémaphore : remarques
• mécanisme de synchronisation très polyvalent
• permet de résoudre tous les scénarios ci-dessus
• implem : instructions atomiques dans appel système
• file d’attente = état BLOCKED dans l’ordonnanceur
• attention : ordre de réveil non spécifié
• cas général parfois appelé «sémaphore à compteur»
• k > 0 I nombre de «jetons disponibles» = k
• k 6 0 I nombre de tâches en attente = −k
• «sémaphore binaire» si k initialisée à 1
• équivalent à un mutex : P()=lock() et V()=unlock()
• attention : aucun moyen de consulter la valeur de k
• propriétés souhaitables : sûreté, progression, équité,
généralité, simplicité, prouvabilité, performance...
30/36
Producteur-consommateur avec sémaphores
partagé
item_t buffer[N];
sem_t emptyslots=N;
sem_t fullslots=0;
Producteur Consommateur
in = 0; out = 0;
while(1) while(1)
{ {
item=produce() P(fullslots);
P(emptyslots); item = buffer[out];
buffer[in] = item; out = (out+1) % N;
in = (in+1) % N; V(emptyslots);
V(fullslots); consume(item);
} }
31/36
Sémpahores POSIX
#include <semaphore.h>
/* opaque typedef */ sem_t;
// semaphore initialization and destruction
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_destroy(sem_t *sem);
// synchronization methods
int sem_wait(sem_t *sem); // wait = P = down
int sem_post(sem_t *sem); // post = V = up = signal
32/36
Semaphores : intuitions
k = −2
k=13 k=5 k=0
• P() = «essayer de prendre un jeton, me suspendre si aucun dispo»
• AKA wait, acquire, pend, down
• un example d’appel bloquant
• V() = «ajouter un jeton et peut-être réveiller un autre thread»
• AKA post, signal, release, post, up
• un exemple d’appel non-bloquant
33/36
Notion de «deadlock», en VF interblocage
Définition : interblocage, en VO deadlock
Situation dans laquelle deux (ou plusieurs) tâches concurrentes
se retrouvent suspendues car elles s’attendent mutuellement
I...pour toujours
Exemple :
Init: Semaphore X=1, Y=1
Thread A: P(X); P(Y); print("A"); Question : résultat ?
Thread B: P(Y); P(X); print("B");
Exemple de trace d’exécution menant à l’interblocage
1 Thread A : P(X)
2 Thread B : P(Y)
3 Thread A : P(Y) I bloque A
4 Thread B : P(X) I bloque B
34/36
Plan
1. Introduction : la notion de thread
2. Problème de l’exclusion mutuelle
3. Un mécanisme de synchro universel : le sémaphore
35/36
Threads et synchronisation : en résumé
Processus VS thread VS mémoire virtuelle
• unité d’ordonnancement = thread
• unité d’isolation mémoire = espace d’adressage virtuel
• un processus = un espace d’adressage + un/plusieurs threads
Exclusion mutuelle AKA mutex
• stratégie permettant d’éviter les «race conditions»
• mécanisme : méthodes lock() et unlock() atomiques
Sémaphore
• mécanisme de synchronisation universel
• P() = «essayer de prendre un jeton, me suspendre si aucun dispo»
• V() = «ajouter un jeton et peut-être réveiller un autre thread»
36/36
