Devoir Surveillé Systèmes d’Exploitation & Programmation Concurrente

Date

d’arrivée

0

12

28

36

46

Temps

estimé (ms)

17

25

8

32

18

a) En considérant les données ci-dessus, et négligeant le temps de commutation, donnez

le diagramme de GANTT montrant l’exécution de l’algorithme d’ordonnancement

MLFQ. En déduire le nombre de commutation de contexte.

b) En donnez les temps de traitement et d’attente de chaque processus ?

c) (optionnelle +1 pt) Quel est l’intérêt de ce type d’ordonnancement multi-niveaux ?.

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

Supposons disposer d’un nombre fini, MAX_RES, d’exemplaires de ressources d’un seul type.

Les processus peuvent demander un certain nombre, count, d’exemplaires parmi les

ressources disponibles (count <=MAX RES) pour les utiliser en exclusivité ; et puis une fois

terminé, ils doivent les retourner. Si, lors d’une demande d’allocation, le nombre d'exemplaires

demandés n’est pas disponible, le processus doit attendre qu'un nombre suffisant d'exemplaires

aient été libérés.

3/11

L’extrait de code C suivant est utilisé afin de gérer l’allocation et la libération d’un nombre

donné d’exemplaires de ressource disponible.

//The maximum number of resources

#define MAX_RES 10

//the number of available resources

int available_res = MAX_RES;

//Allocate_Res decreases available resources by count resources

int Allocate_Res(int count) {

if (available_res < count)

return -1;

else {

available_res -= count;

return 0;

}

}

/ Free_Res increases available resources by count /

int Free_Res(int count) {

available_res += count;

return 0;

}

1) Dire si ces fonctions peuvent être appelées par plusieurs processus concurrents? Identifier

la section critique et dire que peut-on risquer ?

2) Proposez une solution de synchronisation par variables conditionnelles (pthread) qui

réalise cela en modifiant les fonctions d’allocation (Alloc_Res) et de libération

(Free_Res). Peut-on réveiller tous les processus en attente dans la fonction Free_Res,?

Justifiez.

Indications : Déclarez clairement vos variables globales et précisez leurs initialisations.

3) Donnez le code qui doit être exécuté par les processus pour réaliser l'équivalent des

fonctions Alloc_Res et Free_Res. On introduira tous les sémaphores et variables nécessaires,

en précisant leur valeur initiale. Pourquoi ne peut-on pas pratiquer le réveil en cascade

avec des sémaphores ?

4) Peut-on risquer une famine pour la solution proposée en 2)? Justifiez ? Si oui, proposez une

solution textuelle (sans écrire de code) afin de l’éviter.

Bonne Réflexion

4/11

Proposition de correction

1) Que signifient les termes suivants :

a) Mode d’exécution

0,5 pt

un dispositif matériel qui permet au système d'exploitation la protection des

processus en exécution. Mode d’exécution <user, système>

b) Commutation de contexte

0,5 pt

La commutation de contexte invoque au moins trois étapes. Par exemple, en

présumant que l'on veut commuter l'utilisation du processeur par le processus P1

vers le processus P2, cela se traduira par :

 Sauvegarder le contexte du processus P1 quelque part en mémoire (usuellement

sur la pile de P1).

 Retrouver le contexte de P2 en mémoire (usuellement sur la pile de P2).

 Restaurer le contexte de P2 dans le processeur, la dernière étape de la

restauration consistant à reprendre l'exécution de P2 à son point de dernière

exécution

c) PCB

0,25 pt

PCB –Process Control Bloc c’est le contexte de processus

2) Lequel (lesquels) des algorithmes d’ordonnancement, vu en cours, ne génère(nt) pas le

problème de famine ? justifiez brièvement.

a) Algorithme avec critère d’équité ; FCFS et Round Robin

1 pt

3) Quelle est la différence fondamentale entre une synchronisation par moniteur et celle

avec variables conditionnelles ?

0,75 pt

Les moniteurs sont utilisés par les processus et l’exclusion mutuelle est offerte

implicitement par l’API ; alors les variables conditionnelles sont utilisées par les

threads et l’exclusion mutuelle est favorisée explicitement par le développeur.

Exercice 1. Fork (4 points –2(2*1)+2)

Ind. Les deux parties suivantes sont indépendantes

Partie I.

Soit le programme suivant. On suppose que la primitive forkO ne retourne pas d’erreur.

#include <unistd.h>

int main(void)

{

if ( fork() && fork() )

5/11

fork();

exit(EXIT_SUCCESS);

}

1) Donner l'arborescence des processus créés. En déduire le nombre total de processus

(en comptant le processus père) créés après lancement de ce programme.

1 pt

A&&B est évaluée à 0 (FAUX) si A==0 Sinon si B est aussi évaluée à 1 alors

A&&B est évaluée à 1.

2) Quelle arborescence obtient-on si l’on remplace

1 pt

if ( fork() && fork() ) par if (!fork() && !fork() )

Partie II

Écrire un programme qui crée N processus fils. Chacun d’entre eux devra afficher N fois d’affilé

2 pts

son numéro d’ordre entre 0 et N-1 ainsi que son PID.

#define N 5

#include <unistd.h>

#include <stdlib.h>

int main() {

int i,j;

for (i=0; i<N; i++)

{ switch (fork()) {

-1: printf(“ erreur de creation dans fork ….\n’’) ;

exit(1) ;

0 : for (j=0 ; j<N-1 ;j++)

printf(‘’%d je suis de pid %d\n”,j,getpid());

exit(0) ; //Afin de ne pas boucler n !

default : wait() ;

}

6/11

}

exit(0) ;

}

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

1) Algorithme d’ordonnancement avec priorité

a) Priorité non préemptive et priorité préemptive

b) Pour chaque processus, Indiquez le temps de réponse et le temps d’attente et puis

le temps de réponse moyen pour chaque algorithme d’ordonnancement.

a) Priorité non préemptive

D. Gantt pour priorité non préemptive (1-- 0,25 commutation 1 + 4*0,125 + 0,25 FA)

P1

P2

P5

P3

P4

0 3 4 5 6 10 11 16 18 19

FACPU

P2

P2

P3

P4

P2

P5

P3

P4

P5

P3

P4

P4

P3

P4

Processus

P1

P2

P3

P4

P5

TT

10

9

15

15

10

Moyenne

11,8

TA

0

8

13

14

15

(0,75)

b) Priorité préemptive.

D. Gantt pour priorité préemptive (1-- 0,25 commutation 1 + 4*0,125 + 0,25 FA)

P1

P2

P1

P5

P3

P1

P4

0 2 3 4 6 11 13 18 19

FACPU

P2

P1

P3

P3

P4

P4

P1

P4

P3

P1

7/11

P4

P5

P3

P1

P4

Processus

P1

P2

P3

P4

P5

TT

18

1

10

15

5

Moyenne

9,8

TA

8

0

8

14

0

(0,75)

2) Algorithme d’ordonnancement multi-niveaux MLFQ avec les trois files d’attente (ou

queues)

Q0 (Priorité 0)

Q1 (Priorité 1)

Q2 (Priorité 2)

D. Gantt MLFQ (1,75-- 0,25 commutation 1 + 12*0,125 + 0,25 FA)

P01

P11

P02

P11

P12

P03

P04

P12

P05

P12

P14

P15

P22

P4

0 8 12 20 25 28 36 44 46 54 65 81 91 92 100

FAQ0

P2

P3

P4

P5

FAQ1

FAQ2

P1

P2

P2

P2

P2 ; P4

P4 ; P5

P4

P2

P2 ; P4

Nombre de commutation : 14

(0,125 pt)

8/11

Processus

P1

P2

P3

P4

P5

TT

25

80

8

64

45

TA

8

55

0

32

27

(0,5)

Moyenne

44,4

(0,125)

C) Quel est l’intérêt de ce type d’ordonnancement multi-niveaux ?

Question optionnelle (+1pt)

Dans le scheduling multi-niveaux, la file d’attente des processus prêts n’est pas unique :

elle est divisée en plusieurs files (queues) devant contenir chacune un type de processus

donné. L’intérêt de cette méthode est que les processus (du système et des utilisateurs,

par exemple) n’ont pas les mêmes besoins (mémoire et temps processeur) et doivent donc

être ordonnancés différemment.

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

L’extrait de code C suivant est utilisé afin de gérer l’allocation et la libération d’un nombre

donné d’exemplaires de ressource disponible.

//The maximum number of resources

#define MAX_RES 10

//the number of available resources

int available_res = MAX_RES;

//Allocate_Res decreases available resources by count resources

int Allocate_Res(int count) {

if (available_res < count)

return -1;

else {

available_res -= count;

return 0;

}

}

/ Free_Res increases available resources by count /

int Free_Res(int count) {

available_res += count;

return 0;

}

9/11

1) Dire si ces fonctions peuvent être appelées par plusieurs processus concurrents? Identifier

la section critique et dire que peut-on risquer ?

available_res est une variable partagée accédée en ‘’write’’ (available_res++/

available_res--) risque d’incohérence de résultat.

2) Proposez une solution de synchronisation par variables conditionnelles (pthread) qui

réalise cela en modifiant les fonctions d’allocation (Alloc_Res) et de libération

(Free_Res). Peut-on réveiller tous les processus en attente dans la fonction Free_Res,?

Justifiez.

Indications : Déclarez clairement vos variables globales et précisez leurs initialisations.

#define MAX_RES 10

//the number of available resources

int available_res = MAX_RES;

// 0,5 pt

pthread_mutex_t mutex = PTHREAD_MUTEX_INITIALIZER;

pthread_cond_t cond = PTHREAD_COND_INITIALIZER;

//Allocate_Res decreases available resources by count

resources

int Allocate_Res(int count) {

// 1,25 pt

pthread_mutex_lock (&mutex);

while (available_res < count)

pthread_cond_wait(&cond, &mutex);

available_res -= count;

pthread_mutex_unlock (&mutex);

}

/ Free_Res increases available resources by count /

int Free_Res(int count) {

// 0,75 pt

pthread_mutex_lock (&mutex);

available_res += count;

pthread_mutex_lock (&mutex);

pthread_cond_broadcast(&cond);

}

10/11

3) Donnez le code qui doit être exécuté par les processus pour réaliser l'équivalent des

fonctions Alloc_Res et Free_Res. On introduira tous les sémaphores et variables nécessaires,

en précisant leur valeur initiale. Pourquoi ne peut-on pas pratiquer le réveil en cascade

avec des sémaphores ?

#define MAX_RES 10

//the number of available resources

int available_res = MAX_RES;

// 0,5 pt

Sem mutex=1; //Protection de available_res

Sem stop=0 ; //blocage si #res non dispo.

Processus i {

int count = ……..; //à entrer/récupérer

// 1 pt

P(mutex);

while (available_res < count) {

V(mutex);

P(stop);

P(mutex);

}

available_res -= count;

V(mutex);

}

Utiliser Ressources

// 1 pt

P(mutex);

available_res += count;

V(mutex);

V(stop);

4) Peut-on risquer une famine pour la solution proposée en 2)? Justifiez ? Si oui, proposez une

solution textuelle (sans écrire de code) afin de l’éviter.

Risque de famine exp. Available_res =10 ; 1) P1(8) 2) P2(4) ; P3(5) ;P4(3). P1 actif

et P2 ; P3 ; P4 bloqués. Quand P1 termine réveille P2 ; P3 ; P4 ; il y a arrivée de

P5(7) ; …

Solution possible : Trier les processus par demande en ordre croissant

11/11