BCI Informatique - Concurrence
Langage C et sémaphores

Bertrand Dupouy

SOMMAIRE

Présentation du modèle lecteurs/écrivains
1.1 Rappel du modèle
1.2 Sémaphores Unix

Synchronisation des seuls lecteurs
2.1 Exercice

Synchronistion des lecteurs et des écrivains
3.1 Exercice
Eviter la famine pour les écrivains
4.1 Exercice

Gestion d'une barrièrre
5.1 Exercice

1. Présentation du modèle lecteurs/écrivains

Nous allons ici utliser des sémaphores pour synchroniser des processus en suivant la sémantique du modèle lecteurs/écrivains. Pour plus de détails, on trouvera ici le support de cours sur les processus(cf. pages 125 à 129).

1.1 Rappel du modèle

Le fonctionnement du modèle lecteurs/écrivains est le suivant :

Un écrivain en cours de modification interdit tout autre accès à la ressource, que ce soit en lecture ou en écriture,
Un lecteur en consultation interdit les accès en écriture, mais autorise d'autres consultations simultanées,

1.2 Sémaphores Unix

Les opérations P, V et Init sur les séamaphores sont ainsi implantées sous Unix :

Opération API POSIX C

Init(sem, compteur)
sem = sem_open(Nom, O_CREAT, 0644, compteur)
Signification des paramètres:
Nom : Nom du sémaphore, ce nom doit commencer par \
O_CREAT : création d un nouveau sémaphore
0644 : droits d'accès (lecture et écriture)

P(sem)
sem_wait(sem);

V(sem)
sem_post(sem);

Opération	API POSIX C
`Init(sem, compteur)`	`sem = sem_open(Nom, O_CREAT, 0644, compteur)` Signification des paramètres: `Nom` : Nom du sémaphore, ce nom doit commencer par `\` `O_CREAT` : création d un nouveau sémaphore `0644` : droits d'accès (lecture et écriture)
`P(sem)`	`sem_wait(sem);`
`V(sem)`	`sem_post(sem);`

2. Synchronisation des seuls lecteurs

On utilisera le programme se trouvant ici dans lequel aucune synchronisation n'est faite.

Remarques :

La variable nbre_lecteurs, partagée par les lecteurs est implantée dans le fichier lecteurs.dat

Création et initialisation des sémaphores

Les sémaphores sont créés de la façon suivante :
if ((verrou = sem_open("VERROU", O_CREAT, 0644, compteur)) == SEM_FAILED)
if ((verrou_lec = sem_open("VERROULEC", O_CREAT, 0644, compteur)) == SEM_FAILED)

Le fichier semaph.h est utilisé pour associer des noms aux sémaphores Unix, il contient :

semaph.h

/* Ce fichier sert pour : * 1-associer des noms aux semaphores Unix , * 2-donner le nom du fichier contenant la variable * nbre_lecteur utilisee dans les fonctions * premier et dernier. */ /* Les semaphores utilises */ #define VERROU "/sem55" #define VERROULEC "/sem66" #define COUPEFILE "/sem77" /* Le fichier contenant nbre_lecteur */ #define FICLEC "lecteurs.dat"

L'édition de liens doit se faire avec l'option -lpthread pour avoir accès à la bibliothèque contenant les sémaphores. Par exemple :
- gcc -Wall ecrlec-v0.c -o ecrlec-v0 -lpthread
En cas de probléme, ce programme permet de détruire les sémaphores. Sur une machine Linux, les sémaphores se trouvent dans /dev/shm, et on peut les supprimer en utilisant la commande rm.

2.1 Exercice

Compiler et exécuter le programme pour vérifier que la synchronisation n'est pas assurée, par exemple : ./ecrlec-v0 0 2 ./ecrlec-v0 2 1
Compléter la partie lecteur seule de ce programme et vérifier son bon fonctionnement. Pour ce faire, si l'exécutable s'appelle ecrlec, on doit obtenir ce type d'affichage :


$ ./ecrlec 0 0
main : ./ecrlec : fin 

$ ./ecrlec 4 0
========================= Lecteur 0 est le premier ->  sem_wait 
========================= Lecteur 0 dans SC --Date :  46:27 
========================= Lecteur 2 dans SC --Date :  46:27 
========================= Lecteur 3 dans SC --Date :  46:27 
========================= Lecteur 1 dans SC --Date :  46:27 
========================= Lecteur 0 va sortir de   SC --Date :  46:37 
main : fin de fils 0000 (hexa)
========================= Lecteur 1 va sortir de   SC --Date :  46:38 
main : fin de fils 0100 (hexa)
========================= Lecteur 2 va sortir de   SC --Date :  46:39 
main : fin de fils 0200 (hexa)
========================= Lecteur 3 va sortir de   SC --Date :  46:40 
========================= Lecteur 3 est le dernier ->  sem_post 
main : fin de fils 0300 (hexa)
main : ./ecrlec : fin

3. Synchronistion des lecteurs et des écrivains

3.1 Exercice

Compléter la partie écrivain de ce programme, pour le moment on ne traite pas le problème de la famine pour les écrivains.

Les tests à effectuer :

On vérifie d'abord que l'exclusion mutuelle est assurée pour les écrivains :


$ ./ecrlec 0 2
 ******************** Ecrivain 0 Debut :  04:59
 ******************** Ecrivain 0 entre SC -- Date :  04:59 (iteration : 0)
 ******************** Ecrivain 1 Debut :  04:59
 ******************** Ecrivain 0 va sortir SC  -- Date :  05:02 (iteration : 0)
 ******************** Ecrivain 1 entre SC -- Date :  05:02 (iteration : 0)
 ******************** Ecrivain 1 va sortir SC  -- Date :  05:06 (iteration : 0)
 ******************** Ecrivain 0 entre SC -- Date :  05:06 (iteration : 1)
 ******************** Ecrivain 0 va sortir SC  -- Date :  05:09 (iteration : 1)
 ******************** Ecrivain 1 entre SC -- Date :  05:09 (iteration : 1)
 ******************** Ecrivain 1 va sortir SC  -- Date :  05:13 (iteration : 1)
 ******************** Ecrivain 0 entre SC -- Date :  05:13 (iteration : 2)
 ******************** Ecrivain 0 va sortir SC  -- Date :  05:16 (iteration : 2)
 ******************** Ecrivain 1 entre SC -- Date :  05:16 (iteration : 2)
Ecrivain 0 : fin 
 ******************** Ecrivain 1 va sortir SC  -- Date :  05:20 (iteration : 2)
main : fin de fils 0000 (hexa)
Ecrivain 1 : fin 
main : fin de fils 0100 (hexa)
main : ./ecrlec : fin 
-sh-4.2$

On vérifie ensuite le bon fonctionnement global du modèle, par exemple :


$ ./ecrlec 6 2
 ******************** Ecrivain 0 Debut :  15:48
 ******************** Ecrivain 0 entre SC -- Date :  15:48 (iteration : 0)
 ******************** Ecrivain 1 Debut :  15:48
========================= Lecteur 0 est le premier ->  sem_wait 
 ******************** Ecrivain 0 va sortir SC  -- Date :  15:51 (iteration : 0)
 ******************** Ecrivain 1 entre SC -- Date :  15:51 (iteration : 0)
 ******************** Ecrivain 1 va sortir SC  -- Date :  15:55 (iteration : 0)
========================= Lecteur 0 dans SC --Date :  15:55 
========================= Lecteur 2 dans SC --Date :  15:55 
========================= Lecteur 3 dans SC --Date :  15:55 
========================= Lecteur 4 dans SC --Date :  15:55 
========================= Lecteur 5 dans SC --Date :  15:55 
========================= Lecteur 1 dans SC --Date :  15:55 
========================= Lecteur 0 va sortir de   SC --Date :  16:05 
main : fin de fils 0000 (hexa)
========================= Lecteur 4 va sortir de   SC --Date :  16:05 
main : fin de fils 0400 (hexa)
========================= Lecteur 5 va sortir de   SC --Date :  16:06 
========================= Lecteur 1 va sortir de   SC --Date :  16:06 
main : fin de fils 0100 (hexa)
main : fin de fils 0500 (hexa)
========================= Lecteur 2 va sortir de   SC --Date :  16:07 
main : fin de fils 0200 (hexa)
========================= Lecteur 3 va sortir de   SC --Date :  16:08 
========================= Lecteur 3 est le dernier ->  sem_post 
 ******************** Ecrivain 0 entre SC -- Date :  16:08 (iteration : 1)
main : fin de fils 0300 (hexa)
 ******************** Ecrivain 0 va sortir SC  -- Date :  16:11 (iteration : 1)
 ******************** Ecrivain 1 entre SC -- Date :  16:11 (iteration : 1)
 ******************** Ecrivain 1 va sortir SC  -- Date :  16:15 (iteration : 1)
 ******************** Ecrivain 0 entre SC -- Date :  16:15 (iteration : 2)
 ******************** Ecrivain 0 va sortir SC  -- Date :  16:18 (iteration : 2)
 ******************** Ecrivain 1 entre SC -- Date :  16:18 (iteration : 2)
Ecrivain 0 : fin 
 ******************** Ecrivain 1 va sortir SC  -- Date :  16:22 (iteration : 2)
main : fin de fils 0000 (hexa)
Ecrivain 1 : fin 
main : fin de fils 0100 (hexa)
main : ./ecrlec : fin

4. Eviter la famine pour les écrivains

4.1 Exercice

Pour éviter la famine pour les écrivains on va ajouter un sémaphore et vérifier le fonctionnement du programme.

Exemples de tests :

test 1 :


./ecrlec-2 12 6
 ******************** Ecrivain 2 Debut :  29:33
 ******************** Ecrivain 2 entre SC -- Date :  29:33 (iteration : 0)
...
...
******************** Ecrivain 5 entre SC -- Date :  29:41 (iteration : 0)
========================= Lecteur 0 est le premier ->  sem_wait 
 ******************** Ecrivain 5 va sortir SC  -- Date :  29:46 (iteration : 0)
========================= Lecteur 0 dans SC --Date :  29:46 
========================= Lecteur 2 dans SC --Date :  29:46 
========================= Lecteur 1 dans SC --Date :  29:46 
========================= Lecteur 3 dans SC --Date :  29:46 
========================= Lecteur 4 dans SC --Date :  29:46 
========================= Lecteur 5 dans SC --Date :  29:46 
========================= Lecteur 6 dans SC --Date :  29:46 
========================= Lecteur 7 dans SC --Date :  29:46 
========================= Lecteur 0 va sortir de   SC --Date :  29:56 
========================= Lecteur 4 va sortir de   SC --Date :  29:56 
========================= Lecteur 1 va sortir de   SC --Date :  29:57 
========================= Lecteur 5 va sortir de   SC --Date :  29:57 
========================= Lecteur 2 va sortir de   SC --Date :  29:58 
========================= Lecteur 6 va sortir de   SC --Date :  29:58 
========================= Lecteur 3 va sortir de   SC --Date :  29:59 
========================= Lecteur 7 va sortir de   SC --Date :  29:59 

  ICI LE FLOT DES LECTEURS  A ETE INTERROMPU 

========================= Lecteur 7 est le dernier ->  sem_post 
 ******************** Ecrivain 3 va sortir SC  -- Date :  30:06 (iteration : 0)
 ******************** Ecrivain 1 entre SC -- Date :  30:06 (iteration : 0)

 ICI LES LECTEURS SE METTENT EN FILE D ATTENTE

========================= Lecteur 8 est le premier ->  sem_wait 
...
 ******************** Ecrivain 2 va sortir SC  -- Date :  30:15 (iteration : 1)
 ******************** Ecrivain 1 entre SC -- Date :  30:54 (iteration : 2)
 ******************** Ecrivain 1 va sortir SC  -- Date :  30:58 (iteration : 2)

 UN DEUXIEME FLOT DE LECTEURS ENTRE EN SECTION CRITIQUE

========================= Lecteur 8 dans SC --Date :  30:58 
========================= Lecteur 9 dans SC --Date :  30:58 
========================= Lecteur 10 dans SC --Date :  30:58 
========================= Lecteur 11 dans SC --Date :  30:58 
========================= Lecteur 8 va sortir de   SC --Date :  31:08 
========================= Lecteur 9 va sortir de   SC --Date :  31:09 
========================= Lecteur 10 va sortir de   SC --Date :  31:10 
========================= Lecteur 11 va sortir de   SC --Date :  31:11 
========================= Lecteur 11 est le dernier ->  sem_post 
...

test 2 :

5. Gestion d'une barrièrre

On veut réaliser une barrière : tant que N participants ne sont pas arrivés devant la barrière, il faut que chacun d'eux attende qu'elle se lève.
Lorsque le participant numéro N arrive, il lève la barrière et débloque ainsi tous ceux qui attendaient.
Variables partagées :

Deux sémaphores S1 et S2 initialisés ainsi : Init(Sem1, 1), Init(S2, 0);
nb : compteur sur le nombre de participants en attente devant la barrière

Chaque processus participant va exécuter un programme dont le canevas est le suivant : P(S1); /* S1 gere l exclusion mutuelle sur nb */ nb = nb+1; if (nb == N){ /* le dernier est arrive : il leve la barriere */ nb = nb-1; while(nb > 0){ V(S2); nb = nb-1; } V(S1); } else { V(S1); /* attendre que la barriere se leve */ P(S2); }
5.1 Exercice

On utilisera le programme se trouvant ici dans lequel aucune synchronisation n'est faite. Il utilise barriere.h
- Constater son mauvais fonctionnement en l'exécutant
- Compléter (cf. commentaires : A COMPLETER) ce programme et vérifier son bon fonctionnement.
- En cas de probléme, ce programme permet de détruire les sémaphores. Sur une machine Linux, les sémaphores se trouvent dans /dev/shm, et on peut les supprimer en utilisant la commande rm.

Si l'exécutable s'appelle barriere, on doit obtenir ce type d'affichage :


./barriere 3
 ******************** Acteur 2 Debut :  21:35
 ******************** Acteur 1 Debut :  21:35
 ******************** Acteur 0 Debut :  21:35
========================= Acteur 0 dans SC1 : il a fait P(verrou)
========================= Acteur 0 va sortir de SC1 et faire V(verrou) 
************ Acteur 0 attend devant barriere
========================= Acteur 1 dans SC1 : il a fait P(verrou)
========================= Acteur 1 va sortir de SC1 et faire V(verrou) 
************ Acteur 1 attend devant barriere
========================= Acteur 2 dans SC1 : il a fait P(verrou)

========================= TOUS ARRIVES 

========================= Acteur 2 va faire V(barriere) (iteration 2 )
========================= Acteur 2 va faire V(barriere) (iteration 1 )
========================= Acteur 2 va sortir de SC1 et faire V(verrou) 
************ Acteur 0 passe la barriere !   21:43
 ******************** Acteur 2  : fin  21:43
************ Acteur 1 passe la barriere !   21:43
main : fin de fils 0200 (hexa)
 ******************** Acteur 0  : fin  21:44
main : fin de fils 0000 (hexa)
 ******************** Acteur 1  : fin  21:45
main : fin de fils 0100 (hexa)
main : ./barriere : fin

BCI Informatique - Concurrence Langage C et sémaphores

Présentation du modèle lecteurs/écrivains 1.1 Rappel du modèle 1.2 Sémaphores Unix Synchronisation des seuls lecteurs 2.1 Exercice Synchronistion des lecteurs et des écrivains 3.1 Exercice Eviter la famine pour les écrivains 4.1 Exercice Gestion d'une barrièrre 5.1 Exercice