int j;

i=k;

i=i+1;

k=i;

printf("k=%d\n",k);

...

}

j=k;

j=j+4;

k=j;

printf("k=%d\n",k);

...

}

2

1) Les résultats suivants sont-ils possibles, oui ou non ? Justifiez vos réponses ?

Processus PA Processus PB

R1

R2

R3

K=2

K=2

K=5

K=2

K=6

K=2

2) (Bonus –1 point) En donnez deux autres possibilités correctes d’exécutions

concurrentes?

Exercice 3. – Reader/Writer Multithread (7 points –1 + 1,5 + 1,5 + 2 +1)

Considérez les deux morceaux de code suivants. Deux threads exécutent respectivement les

fonctions writer_thread() et reader_thread(), et partagent la variable pointer.

int *pointer = NULL;

void * writer_thread() {

while (1) {

if (pointer == NULL) {

pointer = malloc(sizeof(int));

*pointer = rand();

//fonction dans stdlib.h pour recevoir une valeur aléatoire

}

}

}

void *reader_thread() {

while (1) {

if (pointer != NULL) {

printf("pointer = %d\n", *pointer);

free(pointer);

pointer = NULL;

}

}

}

1) En exécutant le programme qui crée deux threads ayant les fonctions précédentes, une

erreur “Erreur de segmentation” apparaît au bout d’un certain temps. D’où provient cette

erreur ? Expliquer.

2) Résolvez ce problème en modifiant le programme par l’ajout d’un sémaphore. On

supposera que le sémaphore est initialisé dans le thread principal.

3) Peut-on résoudre ce problème sans utilisation d’un sémaphore ou de tout autre

mécanisme de synchronisation? Même question si on exécute plusieurs paires écrivain

(fonction writer_thread()) et lecteur (fonction reader_thread()) ?

3

4) Nous proposons d’utiliser une variable conditionnelle pour régler ce problème. La

variable conditionnelle doit servir, d’une part à garantir l’exclusion mutuelle entre les

accès à pointer (rôle joué par le sémaphore utilisé dans les questions précédentes), et

d’autre-part à alerter l’autre thread d’une modification de la variable pointer. Modifiez les

fonctions en conséquence.

5) Ecrire le thread principal, en se basant sur ce qui précède.

Annexe: Prototype de quelques fonctions manipulant les Posix threads

Thread :

int pthread_create(pthread_t tid, const pthread_attr_t attr, void (routine)(void), void arg);

-

• void pthread_exit(void* status);

-

• pthread_t pthread_self(void);

Verrou :

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

int pthread_mutex_init(pthread_mutex_t mutex, const pthread_mutex_attr attr);

int pthread_mutex_destroy(pthread_mutex_t *mutex);

int pthread_mutex_lock(pthread_mutex *mutex);

int pthread_mutex_unlock(pthread_mutex *mutex);

-

-

-

-

Sémaphore:

-

-

-

-

int sem_init(sem_t *sem, int pshared, unsigned int valeur) ;

int sem_wait(sem_t *sem) ;

int sem_post(sem_t *sem) ;

int sem_destroy(sem_t *sem) ;

Condition :

-

-

-

-

-

int pthread_cond_init(pthread_cond_t cond, pthread_cond_attr 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);

int pthread_cond_destroy((pthread_cond_t *cond);

4

Proposition de correction

DS SE&PC

Du 16/11/2012

Questions de cours (8 points – 8*1point/question)

1) Multithreading : exécution concurrente/parallèle de plusieurs

l’intérieur d’un même processus alors que

l’exécution concurrente de plusieurs processus sur un monoprocesseur.

threads à

la multiprogrammation c’est

2) Un processus est une unité de structuration, défini techniq. par un seg. Code, un

seg. Data et un seg. Pile d’exécution et un contexte alors qu’un thread (ou encore

processus léger) est une unité d’exécution qui partage avec tous les autres

threads d’un même processus l’espace d’adressage mémoire mais il ne contient

que sa pile d’exécution, son CO, … On privilégie les threads par rapport aux

processus afin de gagner en performance en particulier la commutation est moins

coûteuse.

3) TCB :

4) Lors de la création d’un processus

5) RC est une ressource partagée où le nombre de points d’accès est égal { un et

donc à accès exclusif . Un SE doit assurer le contrôle d’accès exclusif via par eg. les

mutex.

6) Quatre moyens de synchronisation pour les threads : 1) pthread_join(), 2) les

mutex, 3) les sémaphores, et 4) les variables conditionnelles (l’équiv. De

moniteur)

Programmation concurrente

Exercice 1 (2 points)

Le processus père engendre dans l’ensemble 3 autres processus. En effet, comme dans une

instruction (a && b), b n’est évaluée que si l’´evaluation de a donne Faux (c-à-d 0), de même,

dans une instruction (a || b), b n’est évaluée que si l’´evaluation de a ne donne pas 0. Donc,

dans fork() && b seulement le père exécute b, et dans fork() || b seulement le fils exécute b.

Exercice 2 (3 points + 1 point bonus)

5

1) Si on numérote : I1, I2,I3,I4 les instructions du Processus PA et J1, J2,J3, J4

instructions du Processus PB : I1, J1, I2, J2, J3, I3, I4, J4 -> R1 possible (et

non correcte car n’appartient pas à l’ens. Des résultats générés par PA ; PB

(2, 6) ou encore PB ;PA (6, 5)).

(entrelacements se terminant par : J3, I3, I4, J4 ou , J3, I3,J4,I4) I1, J1, I2, I3,

I4, J2, J3, J3, J4 -> R2

R3aucun entrelacement possible !!

2) PB ;PA  K= 6 (PA) K=5 (PB) possible et correcte et une autre possible (non correcte) (5, 5) c-

à-d I1 ; I2 ; I3 ; J1 ;J2 ;J3 ;J4 ; I4.

Exercice 3: (7 points –1+1,5+1,5+2+1)

Question 1

En exécutant ce programme, une erreur “Erreur de segmentation” apparaît au bout d’un certain

temps. D’où provient cette erreur ?

Réponse 1

Le lecteur peut effectuer l’appel à free() pendant que l’écrivain est bloqué dans random().

Question 2

Résolvez ce problème en modifiant le programme par l’ajout d’un sémaphore. En dire la valeur

initiale de ce sémaphore dans le programme principal .

Réponse 2

void writer_thread() {

while (1) {

sem_wait();

if (pointer == NULL) {

pointer = malloc(sizeof(int));

*pointer = random();

}

sem_post();

}

}

void reader_thread() {

while (1) {

sem_wait();

if (pointer != NULL) {

printf("pointer = %d\n", *pointer);

free(pointer);

pointer = NULL;

6

}

sem_post();

}

}

Question 3

Peut-on résoudre ce problème sans utilisation d’un sémaphore ou de tout autre mécanisme

d’exclusion mutuelle? Même question si on exécute plusieurs paires écrivain (fonction

writer_thread()) et lecteur (fonction reader_thread()) ?

Réponse 3

Oui, l’écrivan peut utiliser une variable locale pour l’allocation et l’initialisation, puis

modifier pointer en une instruction (l’écriture en mémoire étant atomique).

Non dans le cas de plusieurs paires écrivain-lecteur (fuite mémoire), une exclusion

mutuelle pour séquentialiser et séparer les allocations/libérations est nécessaire, car la

communication de l’adresse à libérer se fait via une unique variable pointer.

Question 4

Nous proposons d’utiliser une variable de condition pour régler ce problème. La variable de

condition doit servir, d’une part à garantir l’exclusion mutuelle entre les accès à pointer (rôle joué

par le sémaphore utilisé dans les question précédentes), et d’autre-part à alerter l’autre thread

d’une modification de la variable pointer. Modifiez le programme en conséquence.

Réponse 4

void writer_thread(){ //Le producteur

while (1){

pthread_mutex_lock(&mut);

if (pointer != NULL)

pthread_cond_wait(cond, mut);

pointer = malloc(sizeof(int));

*pointer = random();

pthread_cond_signal(cond);

pthread_mutex_unlock(&mut);

}

}

void reader_thread(){ //Le consommateur

while (1) {

pthread_mutex_lock(&mut);

if (pointer == NULL)

pthread_cond_wait(cond, mut);

printf("Valeur: %d\n", *pointer);

free(pointer);

pointer = NULL;

condition_signal(cond);

pthread_mutex_unlock(&mut);

}

}

7