Ecole Nationale des Sciences de l’Informatique A. U. : 2014/2015
Systèmes d’exploitation & Programmation Concurrente II2
TP3- Synchronisation et Communication Inter-Processus ========================================================
Exercice 1 (DAG)
Soit le graphe de précédence (Directed Acyclic Graph DAG) suivant des processus P1, P2, P3, P4 et P5. Les nœuds représentent les processus et les liens (flèches) entre eux indiquent l’ordre dans lequel ces processus doivent être exécutés. En particulier un processus ne peut commencer à s’exécuter que si tous ses prédécesseurs ont terminé.
1. Donnez une implémentation qui permet l’exécution de ces processus dans l’ordre indiqué par le graphe en utilisant un nombre minimal de sémaphores.
Solution
Les sémaphores s1, s2, s3, s4 et s5 tous initialisés à zéro.
Processus P0 : [Code]; V(s1) ; V(s2) ;
Processus P1 : P(s1) ; [Code];
Processus P2 : P(s2) ; [Code]; V(s3) ; V(s4) ;
Processus P3 : P(s3) ; [Code]; V(s5) ;
Processus P4 : P(s4) ; [Code]; V(s5) ;
Processus P5 : P(s5) ; P(s5); [Code];
Note: la solution optimale avec un nombre minimal de semaphores a été traitée en classe.
Exercice 2
On considère le problème classique de synchronisation des Lecteurs/Rédacteurs implémenté ci-dessous. Nous donnons, aussi, pour les lecteurs (Readers –R) et rédacteurs (Writers –W) les temps d’arrivée et temps d’exécution estimé dans la table ci-dessous.
| | | | | | |
| --- | --- | --- | --- | --- | --- |
Publicité
| Processus Reader | | | | Processus Writer | |
| P(mutex); Nread++ ; if (Nread ==1) P(wrt); V(mutex); ……………. SC: Reading ………………. P(mutex) Nread-- ; if (!Nread) V(wrt); V(mutex); | | | | P(wrt); ………. SC: Writing …………… V(wrt); | |
| Reader –R ou Writer --W | Date d’arrivée | | Temps de traitement estimé | |
| W1 W2 W3 R1 R2 R3 | 1 2 5 0 1 4 | | 2 2 1 1 2 2 | |
1- Expliquez à quoi servent les sémaphores mutex et wrt et rappelez pour chacun sa valeur initiale?
2- En utilisant la table précédente, remplir le(s) diagramme(s) de Gantt suivant en précisant les processus en attente, les processus actifs (c’est-à-dire occupant la section critique) ?
Exercice 3
Proposez une solution multithreadée du problème « dîner des philosophes » en utilisant des verrous mutexs et des variables conditionelles. On suppose que chaque philosophe i est représenté par un thread Ti.
Note : Pour cet exercice, vous n’êtes pas autorisés à utiliser des sémaphores.
Solution:
#include <stdio.h>
#include <pthread.h>
#define NbTh 5 //Nombre de threads symbolisant les philosophes
#define LIBRE 0 // symbolise l'état libre d'une fourchette
#define OCCUPE 1 // symbolise l'état occupé d'une fourchette
pthread\_t tid[NbTh];
pthread\_mutex\_t mutex;
pthread\_cond\_t condManger;
int Fourchette[5];
Publicité
void Demande\_a\_manger (int i){
pthread\_mutex\_lock(&mutex);
while((Fourchette[i]==OCCUPE)||(Fourchette[(i+1)%5] == OCCUPE)){
pthread\_cond\_signal(&condManger); pthread\_cond\_wait(&condManger, &mutex);
}
Fourchette[i]=OCCUPE;
Fourchette[(i+1)%5] = OCCUPE;
printf("Le philosophe %d obtient les fourchettes F%d et F%d et mange \n", (int)i,(int)i, ((int)i+1)%5);
pthread\_mutex\_unlock(&mutex);
}
void Fini\_de\_Manger(int i){
pthread\_mutex\_lock(&mutex);
Fourchette[i]=LIBRE;
Fourchette[(i+1)%5] = LIBRE;
pthread\_cond\_signal(&condManger);
printf("Le philosope %d libere ses fourchettes F%d et F%d\n", i, i, (i+1)%5);
pthread\_mutex\_unlock(&mutex);
}
void \ fonc\_philosophe(void \ i){
int j;
Publicité
srand(pthread\_self());
for (j=0; j<10; j++) {
printf("Le philosophe %d pense ...\n",(int)i);
/\ temps de pensee \/
usleep(rand()%200000);
printf("Le philosophe %d veut manger \n", (int)i);
Demande\_a\_manger((int)i);
/\ temps de manger \/
usleep(rand()%1000000);
Fini\_de\_Manger((int)i);
}
}
int main(){
int num;
pthread\_mutex\_init(&mutex,0);
pthread\_cond\_init(&condManger,0);
// initialisation des Fourchettes
for(num=0;num<NbTh;num ++) Fourchette[num]=LIBRE;
//creation des threads
for(num=0;num<NbTh;num ++)
Publicité
pthread\_create(tid+num,0,(void \(\)())fonc\_philosophe,(void\*)num);
//attend la fin de toutes les threads
for(num=0;num<NbTh;num ++)
pthread\_join(tid[num],NULL);
pthread\_mutex\_destroy(&mutex);
pthread\_cond\_destroy(&condManger);
exit(0);
}
Exercice 4
Un stade d’athlétisme peut recevoir les athlètes de trois (3) clubs A, B et C qui viennent s’y entraîner. Pour organiser les entraînements, on impose la règle suivante :
A un instant donné, le stade peut recevoir un nombre quelconque d’athlètes mais de deux clubs au maximum. Par exemple, 5 athlètes du club B et 3 athlètes du Club C peuvent s’entraîner en même temps, mais si un athlète du club A veut accéder au stade, il doit attendre jusqu’à ce que tous les athlètes aient quitté le stade, soit du club B soit du club C.
1. On vous demande de proposer un schéma de synchronisation des processus: Processus A, Processus B et Processus C correspondant respectivement à des athlètes des clubs A, B et C, et ce en utilisant des sémaphores. Déclarez clairement vos variables et précisez leurs initialisations.
Réponse :
mut1, mut2 et mut3 sont trois sémaphores initialisés à 1. (pour l’exclusion mutuelle).
club est un sémaphore initialisé à 2 (pour la synchro conditionelle).
int NA=0 ; int NB=0 ; int NC=0 ; // indiquant d’athlètes de chaque club au stade.
| | | |
| --- | --- | --- |
| Processus PA { P(mut1) If(NA==0) P(club) ; NA++; V(mut1); Entrainement(); P(mut1) NA--; If(NA==0) V(club); V(mut1); } | Processus PB { P(mut2) If(NB==0) P(club) ; NB++; V(mut2); Entrainement(); P(mut2) NB--; If(NB==0) V(club); V(mut2); } | Processus PC { P(mut3) If(NC==0) P(club) ; NC++; V(mut3); Entrainement(); P(mut3) NC--; If(NC==0) V(club); V(mut3); } |