Introduction à la programmation concurrente
Premiers pas
Yann Thoma
Institut REDS
Haute Ecole d’Ingénierie et de Gestion - VD
Février 2012
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 1 / 48
Plan
Programmation standard
Définition
Un processus est une entité active et exécutable
ou
Un processus est un programme en cours d’exécution
Un programme exécute des instructions séquentiellement
Le développeur maîtrise la suite des opérations
L’exécution est prévisible
L’exécution est reproductible
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 2 / 48
Plan
Qu’est-ce que la programmation concurrente?
Un processus est décomposé en threads
Un thread est une sorte de processus léger
Un thread correspond à une tâche qui s’exécute
Plus ou moins indépendamment des autres
Exemple:
Un jeu de F1: les voitures sont gérées par des processus différents
Un serveur FTP: chaque client est géré par un thread
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 3 / 48
Plan
Problèmes
Difficulté à synchroniser des tâches
Gestion des ressources partagées
Problème de predictibilité
Problème de reproductibilité
Concrètement:
Thérapie par radiation: Therac-25, entre 85 et 87
Blackout au Nord-Est des US en 2003
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 4 / 48
Plan
Problèmes - Blackout
Blackout au Nord-Est des US en 2003
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 5 / 48
Plan
Problèmes - Radiations
Thérapie par radiation: Therac-25, 6 accidents entre 85 et 87
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 6 / 48
Plan
Pourquoi utiliser la programmation concurrente?
Ca semble compliqué, alors pourquoi?
Optimiser l’utilisation du processeur
Augmenter le parallélisme (architecture multi-coeur)
Tout programme faisant du calcul devrait être développé de
manière concurrente
Attendre sur plusieurs entrées
Simplifier la structure d’un programme (ex. jeu vidéo)
Satisfaire des contraintes temporelles
Programmation Temps Réel
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 7 / 48
Plan
Programmation parallèle vs. concurrente
Programmation parallèle (ou répartie)
Des processus s’exécutent sur plusieurs processeurs
Programmation concurrente
Les tâches sont gérées par un même processeur
Les mécanismes de synchronisation sont différents
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 8 / 48
Plan
Anatomie d’un processus
Un processus possède entre autre
Un code à exécuter
Un espace d’adressage
Une priorité
Un identifiant
Un contexte d’exécution (PC + registres)
Les processus sont gérés par le système d’exploitation
Plusieurs processus peuvent s’exécuter en parallèle
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 9 / 48
Plan
Espace d’adressage d’un processus
Espace d'adressage
Processus
stack segment
data segment
text segment
(code)
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 10 / 48
Plan
Etats et transitions d’un processus Unix
réveil
prêt bloqué
préemption
attente
exécution
élu
création
terminaison
terminaison
jointure
terminé zombie
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 11 / 48
Plan
Anatomie d’un thread
Définition
Un thread est un fil d’exécution dans un processus
Les threads d’un même processus se partagent l’espace
d’adressage du processus
Ils sont ordonnancés
Ils possèdent
leur propre pile
leur propre contexte d’exécution (PC + registres)
Ils ont un cycle de vie semblable à celui d’un processus
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 12 / 48
Plan
Espace d’adressage d’un processus multi-thread
Espace d'adressage
Processus
stack segment
threadA Pile du threadA
Attributs Registres
Thread ID
________ ________
________ fonctionA()
priorité = 2 SP
212 i=100
taille = ... PC
... ...
threadB Pile du threadB
Attributs Registres
Thread ID
________ ________
________ fonctionB()
priorité = 2 SP
315 i=10
taille = ... PC
... ...
main()
data segment
ThreadA
threadB
x
y
text segment
pthread_t threadA;
pthread_t threadB;
int x;
int y;
void fonctionA(void *p)
{
int i=100;
}
void fonctionB(void *p)
{
int i=10;
}
main()
{
pthread_create(&threadA,NULL,fonctionA,NULL);
pthread_create(&threadB,NULL,fonctionB,NULL);
...
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 13 / 48
Plan
Thread-processus: en commun
possèdent un ID, un ensemble de registres, un état, et une priorité
possèdent un bloc d’information
partagent des ressources avec les processus parents
sont des entités indépendantes, une fois créés
les créateurs de processus et thread ont contrôle sur eux
peuvent changer leurs attributs après création, et créer de
nouvelles ressources
ne peuvent accéder aux ressources d’autres threads et processus
non reliés
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 14 / 48
Plan
Thread-processus: non commun
les processus ont un espace d’adressage; les threads non
les processus parents et enfants doivent utiliser les mécanismes
de communication inter-processus; les threads d’un même
processus communiquent en lisant et modifiant les variables de
leur processus
les processus enfants n’ont aucun contrôle sur les autres
processus enfants; les threads d’un processus sont considérés
comme des pairs, et peuvent exercer un contrôle sur les autres
threads du processus
les processus enfants ne peuvent pas exercer de contrôle sur le
processus parent; n’importe quel thread peut exercer un contrôle
sur le thread principal, et donc sur le processus entier
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 15 / 48
Plan
Flot d’exécution d’un processus multi-thread
Thread principal
create
ThreadA
create
ThreadB
com.
com.
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 16 / 48
Plan
Flot d’exécution d’un processus multi-thread sur un
processeur simple coeur
Thread principal
create
ThreadA
create
ThreadB
com.
com.
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 17 / 48
Implémentation
Implémentation
Comment implémenter la concurrence?
Grâce à des appels systèmes
Grâce à des mécanismes du langage de programmation
Solution intermédiaire
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 18 / 48
Implémentation
1. Grâce à des appels systèmes
Le système d’exploitation offre une bibliothèque appelée système
multi-tâche
Avantage:
Un langage quelconque peut profiter de la bibliothèque
Désavantages:
Un système multi-tâche doit être fourni par le système
La portabilité (dépendance au système cible)
Déboguage délicat
Pas de méthodologie de programmation imposée
Exemple: langage C avec bibliothèque Pthread
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 19 / 48
Implémentation
Grâce au langage
Les notions concurrentes sont données par le langage
De même que les constructions
Détection des erreurs à la compilation
Méthodologie de programmation imposée par le langage
Exemple: Ada
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 20 / 48
Implémentation
Solution intermédiaire
Un précompilateur gère l’implémentation des outils
Exemple: C++ avec librairie Qt
Code indépendant de la plateforme cible
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 21 / 48
Implémentation
Bibliothèque Pthread
Bibliothèque normalisée POSIX (ISO/IEC 9945-1:1996)
Existe sous Linux et ses dérivés, et sous Windows (installation
depuis [Link]
Fichier d’en-tête :
pthread.h
Compilation et édition des liens :
gcc app.c -lpthread
ou
gcc -D_REENTRANT app.c -lpthread
Déclaration d’un thread
pthread_t thread;
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 22 / 48
Implémentation
Création d’un thread
int pthread_create(
pthread_t *thread,
const pthread_attr_t *attr,
void *(*start_routine)(void *),
void *arg);
thread est un pointeur sur une variable de type pthread_t
attr permet de définir les attributs du thread
start_routine correspond à la fonction qui est exécutée par le
thread créé. La fonction exécutée par le thread créé devra avoir le
prototype suivant:
void *fonction(void *data);
arg est un pointeur passé à la fonction
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 23 / 48
Implémentation
Jointure
int pthread_join(
pthread_t thread,
void **value_ptr);
Attend que la tâche en paramètre se termine
value_ptr contient la valeur de retour de la tâche
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 24 / 48
Implémentation
Exemple (1)
typedef struct {
int main(int argc,char *argv[])
int a;
{
int b;
struct_t v;
} struct_t;
v.a = 1; v.b = 2;
pthread_t thread;
void *Tache1(void *arg) {
pthread_create(&thread,
struct_t *var;
NULL,
var = (struct_t *)arg;
Tache1,
printf("Tache1: a=%d, b=%d\n",
&v);
var->a,var->b);
pthread_join(thread,NULL);
return NULL;
pthread_create(&thread,
}
NULL,
Tache2,
void *Tache2(void *arg) {
(void *)2);
int i = (int)arg;
pthread_join(thread,NULL);
printf("Tache2: i=%d\n",i);
return EXIT_SUCCESS;
return NULL;
}
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 25 / 48
Implémentation
Exemple (2)
typedef struct {
int main(int argc,char *argv[])
int a;
{
int b;
struct_t v;
} struct_t;
v.a = 1; v.b = 2;
pthread_t thread1,thread2;
void *Tache1(void *arg) {
pthread_create(&thread1,
struct_t *var;
NULL,
var = (struct_t *)arg;
Tache1,
printf("Tache1: a=%d, b=%d\n",
&v);
var->a,var->b);
pthread_create(&thread2,
return NULL;
NULL,
}
Tache2,
(void *)2);
void *Tache2(void *arg) {
pthread_join(thread1,NULL);
int i = (int)arg;
pthread_join(thread2,NULL);
printf("Tache2: i=%d\n",i);
return EXIT_SUCCESS;
return NULL;
}
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 26 / 48
Séparation d’un programme en plusieurs threads
Séparation d’un programme en threads
Comment décomposer un programme en plusieurs threads?
Il existe plusieurs modèles
Le modèle délégation (boss-worker model ou delegation model en
anglais)
Le modèle pair (peer model en anglais)
Le modèle pipeline (pipeline model en anglais)
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 27 / 48
Séparation d’un programme en plusieurs threads
Modèle délégation
Un thread principal
Des threads travailleurs
tâche1
patron tâche2
entrée
tâche3
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 28 / 48
Séparation d’un programme en plusieurs threads
Modèle délégation: exemple 1
void *patron(void *) {
boucle infinie {
attend une requête
switch (requete) {
case requeteX: pthread_create( ... tacheX); break;
case requeteY: pthread_create( ... tacheY); break;
...
}
}
}
void *tacheX(void *) {
exécuter le travail demandé, puis se terminer
}
void *tacheY(void *) {
exécuter le travail demandé, puis se terminer
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 29 / 48
Séparation d’un programme en plusieurs threads
Modèle délégation: exemple 2
void *patron(void *) {
// crée tous les threads
pthread_create(...);
boucle infinie {
attend une requête;
place la requête dans la file d’attente
signale aux travailleurs qu’une requête est prête
}
}
void *travailleur(void *) {
boucle infinie {
bloque jusqu’à être activé par le patron
récupère la requête de la file d’attente
switch(requete){
case requeteX: tacheX();
case requeteY: tacheY();
...
}
}
}
Yann ThomatacheX()
void (HES-SO - HEIG-VD
{ - REDS) Introduction à la programmation concurrente Février 2012 30 / 48
exécuter le travail demandé
Séparation d’un programme en plusieurs threads
Modèle pair
Pas de thread principal
Tous égaux
Chacun s’arrange avec ses entrées/sorties
tâche1
tâche2
entrées
tâche3
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 31 / 48
Séparation d’un programme en plusieurs threads
Modèle pair: exemple
main() {
pthread_create( ... tache1);
pthread_create( ... tache2);
...
signale aux threads qu’ils peuvent commencer à travailler
}
tache1() {
attend le signal de commencement
effectue le traitement, et synchronise avec les autres threads
si nécessaire
}
tache2() {
attend le signal de commencement
effectue le traitement, et synchronise avec les autres threads
si nécessaire
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 32 / 48
Séparation d’un programme en plusieurs threads
Modèle pipeline
Appliqué lorsque:
L’application traite une longue chaîne d’entrée;
Le traitement à effectuer sur ces entrée peut être décomposé en
sous-tâches (étages de pipeline) au travers desquelles chaque
donnée d’entrée doit passer;
Chaque étage peut traiter une donnée différente à chaque instant.
Un thread attend les données du précédent
Et les transmet ensuite au suivant
tâche1 tâche2 tâche3
entrée sortie
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 33 / 48
Séparation d’un programme en plusieurs threads
Modèle pipeline: exemple (1)
etage1() {
boucle infinie {
récupérer une entrée du programme
traiter cette donnée
passer le résultat à l’étage suivant
}
}
etage2() {
boucle infinie {
récupérer une donnée de l’étage précédent
traiter cette donnée
passer le résultat à l’étage suivant
}
}
etageN() {
boucle infinie {
récupérer une donnée de l’étage précédent
traiter cette donnée
passer le résultat en sortie du programme
}
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 34 / 48
Séparation d’un programme en plusieurs threads
Modèle pipeline: exemple (2)
main() {
pthread_create( ... etage1);
pthread_create( ... etage2);
...
pthread_create( ... etageN);
...
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 35 / 48
Terminaison
Terminaison: options
La terminaison d’un thread peut être exécutée depuis:
Le thread lui-même:
return
pthread_exit()
Un autre thread:
pthread_cancel()
Mal terminer un thread peut laisser le système dans un état
incohérent!!
Plus spécifiquement depuis un autre thread
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 36 / 48
Terminaison
Auto-terminaison
return value;
Attention avec le thread principal: Terminaison du programme!!
void pthread_exit(void *value)
La fonction met fin au thread, et retourne value au thread
attendant grâce à une jointure (pthread_join()).
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 37 / 48
Terminaison
Auto-terminaison: exemple (1)
void *tache1(void *arg) {
printf("Tâche 1\n");
return 3;
}
void *tache2(void *arg) {
printf("Tâche 2\n");
pthread_exit(4); Dans quel état se trouve le thread ensuite?
}
int main(int argc,char *argv[]) {
pthread_t thread1;
pthread_t thread2;
pthread_create(&thread1,NULL,tache1,NULL);
pthread_create(&thread2,NULL,tache2,NULL);
void *statut1;
void *statut2;
pthread_join(thread1,&statut1);
pthread_join(thread2,&statut2);
printf("Statut1: %d, Status2: %d\n",
statut1,statut2);
return EXIT_SUCCESS; Attention
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 38 / 48
Terminaison
Auto-terminaison: exemple (2)
void *tache1(void *arg) {
printf("Tâche 1\n");
return 3;
}
void *tache2(void *arg) {
printf("Tâche 2\n");
pthread_exit(4);
}
int main(int argc,char *argv[]) {
pthread_t thread1;
pthread_t thread2;
pthread_create(&thread1,NULL,tache1,NULL);
pthread_create(&thread2,NULL,tache2,NULL);
void *statut1;
void *statut2;
pthread_join(thread1,&statut1);
pthread_join(thread2,&statut2);
printf("Statut1: %d, Status2: %d\n",
statut1,statut2);
pthread_exit(NULL); Attention
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 39 / 48
Terminaison
Annulation par un autre thread
int pthread_cancel(pthread_t thread);
thread est un pointeur sur une variable de type pthread_t
Cette fonction permet de faire se terminer un thread depuis un
autre
La terminaison s’effectue sur un point d’annulation
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 40 / 48
Terminaison
Politique d’annulation (1)
Le thread annulé peut définir sa politique d’annulation
int pthread_setcancelstate(
int state,
int *oldstate);
state peut prendre les valeurs:
PTHREAD_CANCEL_ENABLE: Autorise l’annulation
PTHREAD_CANCEL_DISABLE: Interdit l’annulation
oldstate contient ensuite l’ancienne valeur d’enable
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 41 / 48
Terminaison
Politique d’annulation (2)
Si le thread autorise l’annulation, il est possible de définir son type
d’annulation
int pthread_setcanceltype(
int type,
int *oldtype);
type peut prendre les valeurs:
PTHREAD_CANCEL_DEFERRED: Autorise l’annulation en des point
précis
PTHREAD_CANCEL_ASYNCHRONOUS: Autorise l’annulation
n’importe quand
oldtype contient ensuite l’ancien type d’annulation
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 42 / 48
Terminaison
Point d’annulation
Un thread peut placer ses points d’annulations
void pthread_testcancel(void);
L’annulation est donc permise en ces points
Attention, certains appels système sont des points
d’annulation
Exemple: write(), utilisé par printf()
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 43 / 48
Terminaison
Exemple (1)
int counter1 = 1;
void *tache1(void *arg) {
int ancien_etat, ancien_type;
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE,&ancien_etat);
pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED,&ancien_type);
while (true) {
counter1++;
if (counter1 % 100 == 0)
pthread_testcancel();
}
}
int main(int argc,char *argv[]) {
pthread_t thread1;
pthread_create(&thread1,NULL,tache1,NULL);
void *statut1;
usleep(50);
pthread_cancel(thread1);
pthread_join(thread1,&statut1);
printf("Counter1: %d\n",counter1);
return EXIT_SUCCESS;
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 44 / 48
Terminaison
Exemple (2)
int counter1 = 1;
void *tache1(void *arg) {
int ancien_etat, ancien_type;
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE,&ancien_etat);
pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED,&ancien_type);
while (true) {
counter1++;
}
}
int main(int argc,char *argv[]) {
pthread_t thread1;
pthread_create(&thread1,NULL,tache1,NULL);
void *statut1;
usleep(50);
pthread_cancel(thread1);
pthread_join(thread1,&statut1);
printf("Counter1: %d\n",counter1);
return EXIT_SUCCESS;
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 45 / 48
Terminaison
Exemple (3)
int counter1 = 1;
void *tache1(void *arg) {
int ancien_etat, ancien_type;
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE,&ancien_etat);
pthread_setcanceltype(PTHREAD_CANCEL_DEFERRED,&ancien_type);
while (true) {
counter1++;
printf("counter1: %d\n");
}
}
int main(int argc,char *argv[]) {
pthread_t thread1;
pthread_create(&thread1,NULL,tache1,NULL);
void *statut1;
usleep(50);
pthread_cancel(thread1);
pthread_join(thread1,&statut1);
printf("Counter1: %d\n",counter1);
return EXIT_SUCCESS;
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 46 / 48
Terminaison
Exemple (4)
int counter1 = 1;
void *tache1(void *arg) {
int ancien_etat, ancien_type;
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE,&ancien_etat);
pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS,&ancien_type);
while (true) {
counter1++;
}
}
int main(int argc,char *argv[]) {
pthread_t thread1;
pthread_create(&thread1,NULL,tache1,NULL);
void *statut1;
usleep(50);
pthread_cancel(thread1);
pthread_join(thread1,&statut1);
printf("Counter1: %d\n",counter1);
return EXIT_SUCCESS;
}
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 47 / 48
Terminaison
Exemple (5)
Soit le thread tache1 pouvant être annulé par un autre
void *tache1(void *arg) {
int ancien_etat, ancien_type;
pthread_setcancelstate(PTHREAD_CANCEL_ENABLE,&ancien_etat);
pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS,&ancien_type);
// traitement divers
FILE f=fopen(...);
fprintf(f, ...);
fprintf(f, ...);
fclose(f);
// traitement divers
}
Que peut-il se passer?
Que faire pour y remédier?
Yann Thoma (HES-SO - HEIG-VD - REDS) Introduction à la programmation concurrente Février 2012 48 / 48