Multithreading et synchronisation

Question 1

Thread (fil d’exécution)

Answer 1

une tâche indépendante à l’intérieur d’un processus

Question 2

Pourquoi les threads ?

Answer 2

Performance : profiter de plusieurs CPU
Génie logiciel : faciliter la programmation

Question 3

Les threads ont une vue mémoire commune

Answer 3

Pas d’isolation matérielle
• variables globales partagées
• tas d’allocation commun

Question 4

Pour les threads, l’ordonnancement est indépendant

Answer 4

• un VCPU privé
  TCB = Thread Control Block

Une pile d’exécution privée
Des variables locales privées

Question 5

Qu’est que le TCB ?

Answer 5

Thread Control Block
= photo du processus, changer de contexte à l’intérieur d’un processus

Question 6

Que permettent les threads ?

Answer 6

Le multitâche à l’intérieur d’une même vue mémoire
( ≠ dupliquer plusieurs fois processus mais = cohabitation dans même espace virtuel )

Question 7

Qu’est-ce que le PCB ?

Answer 7

Structure de données qui décrit l’intégralité du processus en mémoire
= une PT + un/plusieurs TCB

Question 8

Un thread ne peut pas vivre en dehors d’un processus

Answer 8

besoin d’une vue mémoire

Question 9

Un processus vivant a toujours au moins un thread

Answer 9

main thread» = thread qui exécute main()
• lorsque zéro thread ▶ processus terminé

Question 10

L’ordonnanceur travaille avec des threads ou des processus ?

Answer 10

Des threads (unité d’ordonnancement)

Question 11

Problème à l’exécution

Answer 11

Code source ≠ instructions du processeur :
Ce qu’on lit n’est pas ce que la machine fait séquentiellement : différentes exécutions possibles

Question 12

Quels sont les risques liés aux accès concurrents à une ressource partagée ?

Answer 12

Corruption de données (le programme ne calcule pas ce que le programmeur voulait = bug) et/ou crash

Question 13

C’est quoi une data race (race condition, situation de concurrence) ?

Answer 13

Situation où le résultat du programme dépend de l’ordre dans lequel sont exécutées les instructions des threads

Question 14

Quels sont les différents types de race condition ?

Answer 14

Globalement, c’est quand on a plusieurs accès concurrents à une ressource partagée (variable globale, fichier, réseau, base de données…)

• deux écritures concurrentes = conflit
• une lecture et une écriture concurrentes = conflit

Question 15

Concurrence

Answer 15

parallélisme et/ou entrelacement
• i.e. quand on ne maîtrise pas l’ordre temporel des actions

Question 16

Précepte : data race = bug

Answer 16

Un programme dans lequel plusieurs tâches peuvent se retrouver en situation de concurrence est un programme incorrect.

Question 17

Objectif lors de situations de concurrence

Answer 17

Garantir l’exclusion mutuelle
- On veut que chaque section critique s’exécute de façon atomique

Question 18

Action atomique

Answer 18

Action au cours de laquelle aucun état
intermédiaire n’est visible depuis l’extérieur

Question 19

Ressource critique

Answer 19

Objet partagé par plusieurs threads et
susceptible de subir une data race

Question 20

Section critique

Answer 20

Morceau de programme qui accède a
une ressource critique

Question 21

Exclusion mutuelle

Answer 21

Interdiction pour plusieurs threads de se trouver simultanément à l’intérieur d’une section critique

Question 22

Idée derrière l’exclusion mutuelle

Answer 22

« Verrouiller » l’accès à une section critique déjà occupée

Question 23

Quelles sont les deux primitives pour l’exclusion mutuelle par verrouillage ?

Answer 23

lock(L) et unlock(L)
cf slide 16

Question 24

lock(L)

Answer 24

pour prendre le verrou L en exclusivité
▶ un seul thread peut entrer en section critique

Question 25

unlock(L)

Answer 25

pour relâcher le verrou L ▶ permet aux autres threads de le prendre à leur tour

Question 26

Solution naïve pour mettre en place l’exclusion mutuelle : partagé int turn = 1

Answer 26

• Exclusion mutuelle : OK Attente active : exécution pas très efficace • Problème : alternance stricte ▶ progression non garantie

Question 27

Quelles sont les propriétés souhaitables pour l’exclusion mutuelle ?

Answer 27

• Exclusion mutuelle : à chaque instant, au maximum une seule tâche est en section critique, sinon risque de data race • 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 • Généralité : pas d’hypothèses sur le nombre de tâches ou sur leurs vitesses relatives, on veut une solution universelle

Question 28

Seconde solution naïve pour mettre en place l’exclusion mutuelle - booléen occup partagé

Answer 28

•Progression : OK •Exclusion mutuelle : non garantie •Problème : consultation-modification non atomique

Question 29

Solutions correctes pour mettre en place l’exclusion mutuelle

Answer 29

Masquer les interruptions •idée : empêcher tout changement de contexte ▶ dangereux, et inapplicable sur machine multiprocesseur Approche purement logicielle •idée : programmer avec des instructions atomiques ▶ 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) ▶ permet de bloquer / réveiller les threads au bon moment

Question 30

Verrou exclusif (mutex lock)

Answer 30

objet abstrait = opaque au programmeur • deux états possibles : libre = unlocked ou pris = locked •offre deux méthodes atomiques lock() et unlock()

Question 31

Quelles sont les deux méthodes atomiques pour les verrous ?

Answer 31

lock() et unlock() Elles sont implémentées comme appels système

Question 32

lock(L)

Answer 32

Si le verrou L est libre, le prendre sinon, attendre qu’il se libère

Question 33

unlock(L)

Answer 33

Libérer le verrou L • invoquer unlock() réveille **un** thread suspendu (s’il y en a)

Question 34

Threads en attente

Answer 34

= état BLOCKED dans l’ordonnanceur • une file de threads suspendus pour chaque mutex

Question 35

Interblocage (deadlock)

Answer 35

Situation dans laquelle deux (ou plusieurs) tâches concurrentes se retrouvent suspendues car elles s’attendent mutuellement, pour toujours …

Question 36

Quelles sont les conditions de Coffman nécessaires à l’interblocage ?

Answer 36

•exclusion mutuelle •hold and wait •non-préemption •attente circulaire

Question 37

Condition de Coffman : exclusion mutuelle

Answer 37

Chaque ressource critique est non partageable entre plusieurs threads

Question 38

Condition de Coffman : hold and wait

Answer 38

Un thread possède déjà une ressource et attend pour en avoir une autre

Question 39

Condition de Coffman : non-préemption

Answer 39

Une ressource verrouillée ne peut pas être réquisitionnée, seulement libérée volontairement

Question 40

Condition de Coffman : attente circulaire

Answer 40

A attend que B libère une ressource, mais B attend que C libère une autre ressource, etc.

Question 41

Solutions aux problèmes d’interblocages

Answer 41

•Prévention : garantir leur absence, par conception •Détection : reconnaître le problème quand il arrive •Résolution : régler le blocage une fois qu’il est là

Question 42

Implémentation d’une file

Answer 42

Buffer/tampon circulaire (x%N) de taille constante N Pointeurs in et out [ e ] [ ] [ ] [ ] [ d ] in out

Question 43

Scénario du Producteur-Consommateur

Answer 43

Deux threads communiquent via une file FIFO partagée, avec un qui produit et un qui consomme

Question 44

Hypothèses du scénario du Producteur-Consommateur

Answer 44

•file partagée de taille constante •thread producteur doit attendre tant que la file est pleine •thread consommateur doit attendre tant que la file est vide

Question 45

Problèmes des solutions à base de mutex pour le scénario du Producteur-Consommateur

Answer 45

•mauvaise concurrence •risques de deadlock •attente active

Question 46

Le scénario Producteur-consommateur est insoluble avec seulement lock()/unlock()

Answer 46

besoin d’un mécanisme spécifique pour attendre et signaler des évènements quelconques : primitives supplémentaires (variable de condition)

Question 47

Variable de condition

Answer 47

objet abstrait = opaque au programmeur •contient une file d’attente de threads suspendus •et une référence à un verrou mutex L •offre trois méthodes atomiques : wait(), signal() et broadcast()

Question 48

Quelles sont les trois méthodes atomiques d’une variable de condition

Answer 48

wait(), signal() et broadcast()

Question 49

wait(cond_var C, mutex L)

Answer 49

1) atomiquement : déverrouiller L, et suspendre le thread courant 2) au réveil : re-verrouiller L, puis reprendre l’exécution Au moment de l’appel, L doit être verrouillé par le thread courant sinon c’est une erreur d’exécution

Question 50

signal(cond_var C)

Answer 50

Réveiller l’un des threads suspendus sur C (s’il y en a) utile quand les threads ont tous le même prédicat ▶ pas la peine de réveiller tout le monde à chaque fois (ordre de réveil non spécifié)

Question 51

broadcast(cond_var C)

Answer 51

Réveiller tous les threads suspendus sur C Utile quand les threads ont des prédicats distincts ▶ pour être sûr de réveiller aussi le bon thread

Question 52

Usage typique : la structure de moniteur

Answer 52

Structure de données qui offre sa propre synchronisation : permet à plusieurs threads d’accéder de manière sûre à des ressources partagées sans provoquer de conflits = mutex + variable de condition (pour la signalisation d’évènements)

Question 53

Bonne pratique avec les variables de conditions

Answer 53

Always hold the lock while signalling - simplifie l’analyse des comportements possibles Always re-check predicate on wake-up - protège contre les réveils intempestifs (spurious wake-up)

Question 54

•Pourquoi la primitive wait() est-elle atomique? vs deux notions distinctes de mutex et de CV,

Answer 54

Découpler mutex et CV causerait des risques à l’exécution :

Question 55

Quelques scénarios classiques de synchronisation

Answer 55

Exclusion mutuelle Producteur consommateur, en VO bounded buffer problem Boucle parallèle, en VO fork-join Rendez-vous, en VO barrier

Question 56

API POSIX et threads

Answer 56

#include /* opaque typedefs */ pthread_t, pthread_attr_t; int pthread_create(pthread_t *thread, pthread_attr_t *attr, void * (*function) (void *), void *arg); void pthread_exit(void *retval); int pthread_cancel(pthread_t thread); int pthread_join(pthread_t thread, void **retvalp);

Question 57

int pthread_create(pthread_t *thread, pthread_attr_t *attr, void * (*function) (void *), void *arg);

Answer 57

create and start a new thread

Question 58

void pthread_exit(void *retval);

Answer 58

terminate the current thread

Question 59

int pthread_cancel(pthread_t thread);

Answer 59

terminate another thread

Question 60

int pthread_join(pthread_t thread, void **retvalp);

Answer 60

wait for another thread to terminate

Question 61

API POSIX et Mutex locks

Answer 61

#include /* 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);

Question 62

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

Answer 62

Create a new mutex lock

Question 63

int pthread_mutex_trylock(pthread_mutex_t *mutex);

Answer 63

attempt to lock a mutex without blocking

Question 64

API POSIX et variables de condition

Answer 64

#include /* opaque typedefs */ pthread_cond_t, pthread_condattr_t; // create a new cond variable int pthread_cond_init(pthread_cond_t *cond, const pthread_condattr_t *attr); int pthread_cond_wait(pthread_cond_t *cond, pthread_mutex_t *mutex); int pthread_cond_signal(pthread_cond_t *cond); int pthread_cond_broadcast(pthread_cond_t *cond);