« Return to Teaching
Système et Réseaux
Quelques notes par rapport à ce que j’ai vu en TP ou aux questions que j’ai eues.
Processus avec fork()
Mousse au chocolat commentée
Les points à retenir est que fork()
sépare l’exécution en deux. On a un processus père et un processus fils qui continuent tous les deux le code qui suit. On a donc besoin d’un switch
pour qu’ils exécutent des instructions différentes (sinon ils feraient la même chose). Ça marche car la commande fork()
a un résultat différent selon si on est le père ou le fils. Ensuite, la commande wait(NULL)
permet d’attendre la terminaison d’un fils. Si cela renvoie -1
alors il n’y a plus de fils disponible. L’instruction while (wait(NULL) != -1);
permet donc d’attendre la terminaison de tous les fils.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
| int main()
{
int i;
switch (fork())
{
/* ----------------------------------
Cas d'une erreur
---------------------------------- */
case -1:
perror("fork");
return 1;
/* ----------------------------------
Cas du premier fils qui en commande 6 autres
---------------------------------- */
case 0:
/* - Le fils "commandant" créé 6 autres fils
- Chaque fils va separer blanc et jaune en parallèle
- Le premier fils va attendre leur fin pour battre les blancs en neige */
for (i = 0; i < 6; ++i)
{
switch (fork())
{
case -1:
perror("fork");
return 1;
case 0:
separer_blanc_jaune(); // Chaque petit fils travaille en parallèle
return 0; // Chaque petit-fils termine
}
}
while (wait(NULL) != -1); // On attend la fin des petit-fils
battre_blancs_neige(); // Le premier fils peut travailler
return 0; // Le premier fils termine
/* ----------------------------------
Cas du père (qui renvoie son PID)
---------------------------------- */
default:
/* Le père créé un nouveau fils pour qu'il
s'occupe du chocolat puis il va attendre
la fin de son travail. Je crois que cette partie
n'est pas spécialement utile */
switch (fork())
{
case -1:
perror("fork");
return 1;
case 0:
casser_chocolat();
faire_fondre_chocolat();
return 0;
}
}
while (wait(NULL) != -1); // Le père attend la fin de ses deux fils
// Le père peut enfin travailler pour tout mettre ensemble
melanger_jaunes_choco();
incorporer_blancs_neige();
printf("PID %d : la mousse est terminée !\n", getpid());
return 0;
}
|
Ci-dessus, j’illustre ce qu’il se passe avec une arborescence. Il faut cliquer sur les flèches. Cela permet aussi de dessiner l’arbre de processus.
Père : fork()
Père : fork(), attend tous ses fils puis mélange tout puis termine
Fils 2 : travaille avec le chocolat
Termine
Fils 1 : 6 fois fork(), attend tous les fils puis bats les blancs en neige et termine
Petit-fils: sépare le blanc du jaune d'oeuf
Termine
Petit-fils: sépare le blanc du jaune d'oeuf
Termine
Petit-fils: sépare le blanc du jaune d'oeuf
Termine
Petit-fils: sépare le blanc du jaune d'oeuf
Termine
Petit-fils: sépare le blanc du jaune d'oeuf
Termine
Petit-fils: sépare le blanc du jaune d'oeuf
Termine
Threads
Il faut faire attention, ce n’est pas la même chose que les processus. Les processus sont vraiment comme deux programmes séparés et indépendants qu’on lance sur le terminal. Ils n’ont pas de mémoire partagée. Les threads existent dans un même programme donc ils ont une mémoire partagée (ils ont accès aux mêmes variables globales).
L’idée est que chaque thread va lancer une fonction particulière en parallèle d’autres threads. Une petite difficulté est que pour être générique, le résultat et les paramètres des fonctions de threads doivent être de type void*
. On manipule donc des adresses dans la mémoire partout et non directement des valeurs. La conséquence est que l’on doit faire des cast (conversion de types) pour pouvoir récupérer la valeur derrière et la manipuler.
Somme et produit en parallèle
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
| #include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#define N_DFT 8 // argument par défaut du programme
void *somme(void *n);
void *produit(void *n);
int main(int argc, char *argv[])
{
pthread_t th1, th2;
// si l'utilisateur lance le programme avec un argument alors on l'utilise, sinon on utilise N_DFT comme entrée
int n = argc < 2 ? N_DFT : atoi(argv[1]);
// Ces variables permettront de stocker les résultats de fonction
void *res_somme, *res_prod;
// On lance un premier thread avec la fonction 'somme' et on lui donne l'adresse de l'entier 'n'
if (pthread_create(&th1, NULL, somme, &n)) {
perror("pthread_create somme");
return 1;
}
// On fait pareil avec un second thread qui lance 'produit'
if (pthread_create(&th2, NULL, produit, &n)) {
perror("pthread_create produit");
return 1;
}
// On attend la fin des deux threads et on stocke leur résultat
pthread_join(th1, &res_somme);
pthread_join(th2, &res_prod);
// L'affichage doit utiliser des casts pour récupérer les valeurs aux adresses qu'on a utilisé
printf("n : %d, somme : %d, produit : %d\n", n,
*((int *) res_somme), *((int *) res_prod));
// On libère les variables utilisées pour stocker le résultat
free(res_somme);
free(res_prod);
return 0;
}
void *somme(void *n)
{
// On extrait un entier à partir de l'adresse vers void donnée en paramètre
int i, num = *((int *) n);
int *res = malloc(sizeof(int)); // On alloue de la mémoire pour stocker le résultat
*res = 0;
for (i = 1; i <= num; ++i)
*res += i;
return res;
}
void *produit(void *n)
{
int i, num = *((int *) n);
int *res = malloc(sizeof(int));
*res = 1;
for (i = 1; i <= num; ++i)
*res *= i;
return res;
}
|
Produit de matrices
Comme dans l’exercice 2 du TP2, il est possible de créer des tableaux ou matrices de threads, chacun lançant une fonction (on utilisera donc des boucles for pour lancer les threads ou faire des pthread_join
pour attendre la fin des threads et récupérer les résultats). Dans ce cas-là ça permet de diviser le travail pour chaque ligne. Une leçon à retenir de cet exercice est qu’on peut diviser le travail mais au bout d’un moment, la parellélisation aura des limites en efficacité (on n’est pas toujours plus efficace en rajoutant plus de threads).
Sémaphores et synchronisation
Il y a parfois des opérations qu’on ne veut pas faire en même temps. Pour gérer ça, on utilise des sémaphores pour poser des verrous et interdire/autoriser l’accès à la suite du code. Les zones du code qu’on veut protéger sont les sections critiques, on ne veut pas qu’il y ait un certain nombre de threads en même temps dessus (mais en réalité c’est plus compliqué, on peut voir ça comme prendre/libérer des places mais un seul thread peut prendre plusieurs places comme on le verra par la suite). La valeur d’un sémaphore représente la capacité maximale de threads dans la section critique.
- L’instruction
sem_wait
regarde la valeur d’un sémaphore en paramètre. Si elle est supérieure à 0, on continue (il y a une place libre) et on décrémente la valeur (pour prendre la place), sinon il n’y a pas de place libre et on est mis en attente.
- L’instruction
sem_post
augmente la valeur de 1 (pour dire qu’une place se libère). Cela permet en particulier de débloquer ceux qui étaient bloqués.
Dans le TD3, Exercice 1, on a un exercice avec des fonctions faire_des_trucs_de_hop();
et faire_des_trucs_de_plop();
. Le point clé est que ces deux opérations ne prennent pas le même temps. Le premier prend une unité de temps et le second deux. Les autres opérations ont un temps négligeable qu’on peut ignorer. On utilise un tableau de sémaphores. Cela nous permet de passer en paramètre plusieurs sémaphores en même temps. Il y a une alternance entre les deux : l’un débloque l’autre.
sem_tab+1
est de valeur de départ 3
sem_tab
est de valeur de départ 0
On se retrouve avec l’exécution parallèle suivante où je fais seulement les premières étapes.
Temps 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1); // <--------------------- continue et sem_tab+1 = 2
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab); // <--------------------- bloqué car sem_tab = 0
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Temps 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop(); // <---------------------
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab); // <--------------------- bloqué car sem_tab = 0
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Temps 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop();
printf("hop\n"); // <---------------------
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab); // <--------------------- bloqué car sem_tab = 0
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab); // <--------------------- on débloque plop
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab); // <--------------------- débloqué car sem_tab = 1
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1); // <--------------------- continue et sem_tab+1 = 1
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab); // <--------------------- débloqué car sem_tab = 1
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Temps 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop(); // <---------------------
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop(); // <---------------------
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Temps 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop();
printf("hop\n"); // <---------------------
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop(); // <---------------------
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab); // <--------------------- sem_tab = 2
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop(); // <---------------------
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1); // <--------------------- bloqué car sem_tab+1 = 0
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop(); // <---------------------
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Temps 5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1); // <--------------------- bloqué car sem_tab+1 = 0
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop();
printf("plop\n"); // <---------------------
sem_post(sem_tab + 1);
}
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1); // <--------------------- débloqué car sem_tab+1 = 1
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1); // <--------------------- réveille hop
}
return NULL;
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1); // <--------------------- débloqué car sem_tab+1 = 1
faire_des_trucs_de_hop();
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab); // <--------------------- continue car sem_tab = 1
faire_des_trucs_de_plop();
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Temps 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| void *hop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab + 1);
faire_des_trucs_de_hop(); // <---------------------
printf("hop\n");
sem_post(sem_tab);
}
return NULL;
}
void *plop(void *arg)
{
sem_t *sem_tab = arg;
int i;
for (i = 1; i <= 6; i = i + 1)
{
sem_wait(sem_tab);
faire_des_trucs_de_plop(); // <---------------------
printf("plop\n");
sem_post(sem_tab + 1);
}
return NULL;
}
|
Bon je m’arrête ici…
Million.c
Dans l’exercice 1 du TP3, on voulait incrémenter un compteur avec N threads.
On a la fonction suivante qui est lancée sur chaque thread :
1
2
3
4
5
6
7
8
9
10
| void *bosser(void *s)
{
int i;
for (i = 0; i < N; ++i) {
sem_wait(s);
++incremente_moi;
sem_post(s);
}
return NULL;
}
|
L’idée est qu’on veut que chaque thread incrémente une fois puis passe la main à un autre thread. Ainsi, tous les threads vont alterner l’incrémentation. On voit que le sem_wait
et sem_post
entourent la section critique. On aurait très bien pu mettre la boucle for dans la section critique mais du coup chaque thread aurait incrémenté N fois avant de passer la main. On aimerait quelque chose de plus fluide.
Synchronisation de tâches
Pour l’exercice 2 et 3 du TP3 sur Moodle, je pense que la correction n’est pas bonne.
L’idée, quand on veut synchroniser des tâches est d’avoir un sémaphore qui signale la fin d’une tâche pour :
- bloquer les threads qui ne peuvent commencer avant la fin de la tâche avec
sem_wait
- annoncer la fin de la tâche avec
sem_post
Si on regarde ces deux fonctions qui représentent deux blocs de tâches AC et BD :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void *threadAC(void *arg)
{
tache_a();
sem_wait(&b_fini);
tache_c();
return NULL;
}
void *threadBD(void *arg)
{
tache_b();
sem_post(&b_fini);
tache_d();
return NULL;
}
|
On voit que la tâche A se lance sans dépendance mais par contre, un sem_wait
bloque le lancement de la tâche C. On doit d’abord débloquer le verrou en terminant la tâche B. Dans l’autre fonction, on a la tâche puis un sem_post
juste après.
Mutex
Les mutex sont des cas particuliers de sémaphore à valeur 1 et ils sont donc exclusifs. Soit l’unique place est prise dans la section critique soit elle est libre.
Dans les exercices, on demande principalement de mettre les pthread_mutex_lock
et pthread_mutex_unlock
aux bons endroits.
Belmondo & Depardieu
Dans le premier exercice du TP4, on veut synchroniser un dialogue. Il y a deux sections critiques où on ne veut pas d’accès en même temps :
- l’incrémentation du compteur de phrase pour que l’un prépare son texte puis passe la main à l’autre pour une autre phrase
- la lecture du texte pour pas que les deux personnages parlent en même temps.
Le petit point subtil est que l’incrémentation est déplacée au début des fonctions. La raison est que l’on veut que les deux personnages préparent le bon texte.
- le premier personnage qui accède au lock bloque la section critique
- il récupère le compteur de phrase et le stocke
- il incrémente le compteur de phrase pour passer la main à l’autre personnage
- il sort de la section critique avec un lock
- l’autre personnage lit donc la phrase suivante et fait la même chose
Sans faire ça, on pourrait avoir les deux personnages qui préparent la même phrase au début.
Barrière
Dans l’exercice 2 du TP4, on a une fonction qui affiche un couple avec un chiffre puis une lettre. On veut d’abord afficher tous les chiffres puis toutes les lettres.
L’idée est de d’abord laisser l’affichage des lettres libre, puis ensuite on aura un sem_wait
qui va bloquer l’affichage de la lettre. On utilise un démare tous_finis
qui nous indique que toutes les threads ont affiché leur chiffre.
Pour faire ça, on a une section critique avec mutex où chaque thread va vérifier augmenter un compteur global pour dire qu’il a bien terminé d’afficher son chiffre puis vérifier si tout le monde a fini. Si c’est le cas on libère le sémaphore tous_finis
ce qui déclenche l’affichage de toutes les lettres.