INF2610 Examen final
Automne 2010
cole Polytechnique de Montr al
D partement de G nie Informatique et de G nie Logiciel
Cours INF2610
Examen final
Automne 2010
Date : 16 d cembre 2010 de 9h30 12h00
Pond ration : 40 %
Professeur : Boucheneb Hanifa
Nbre. de questions : 5
Documentation permise : Polycopi du cours
Total : 20 points
Calculatrices programmables et cellulaires non permis
Page 1 sur 12
INF2610 Examen final
Automne 2010
Question 1 (4 pts) : G n ralit s
R pondez aux questions suivantes (les r ponses doivent tre justifi es, concises
et claires) :
a) [1.5 pt] Donnez larborescence des processus cr s par le bout de code suivant
(supposez que lappel fork ne retourne pas derreur) :
int i, pid, n=0;
for (i=0; i<3; i++)
{
pid = fork();
if (pid != 0) break;
else n=n+i;
}
printf("n = %d pour processus %d\n", n, pid);
Donnez, pour chaque processus (y compris le processus principal), la (ou les)
valeur(s) de la variable n affich es l cran.
b) [1 pt] Sous Windows, deux processus p re et fils peuvent-ils partager le m me
pointeur de fichier ? Justifiez votre r ponse.
c) [1.5 pt] Expliquez bri vement comment le langage Java impl mente les
moniteurs. Cette impl mentation de moniteurs correspond-elle un probl me
classique de synchronisation (vu en classe) ? Justifiez votre r ponse.
Page 2 sur 12
INF2610 Examen final
Automne 2010
Question 2 (4 pts) : Moniteurs et variables de condition
On veut synchroniser 3 threads th1, th2 et th3 dun m me processus en utilisant un
moniteur et des variables de condition. La fonction Fi, i=1,3, ex cut e par chaque
thread thi, consiste en une infinit de cycles. Chaque cycle est une section critique
qui doit tre ex cut e en exclusion mutuelle. De plus, chaque cycle de th3 doit tre
pr c d dun cycle de th1 et dun cycle de th2.
Compl tez le pseudocode suivant pour synchroniser, en utilisant les variables de
condition, les cycles des threads th1, th2 et th3.
Moniteur SynCycles
{
/0/
Function F1() // fonction de th1
{ while (1) { /1/
Sc1(); // section critique de th1
/2/
}
}
Function F2() // fonction de th2
{ while (1) { /3/
Sc2(); // section critique de th2
/4/
}
}
Function F3() // fonction de th3
{ while (1) { /5/
Sc3(); // section critique de th3
/6/
}
}
}
Page 3 sur 12
INF2610 Examen final
Automne 2010
Question 3 (5 pts) : S maphore
On veut implanter une pile partag e entre plusieurs threads dun m me processus.
Les fonctions empiler et depiler peuvent tre appel es simultan ment par plusieurs
threads du processus. La fonction empiler bloque jusqu ce quun espace soit libre
dans la pile. De son c t , la fonction depiler bloque jusqu ce quune donn e soit
disponible dans la pile.
a) [2 pts] Compl tez, en utilisant les s maphores, le code suivant de mani re
satisfaire les contraintes de synchronisation des fonctions empiler et d piler.
int sommet = 0;
int pile [ Size ];
/ 0 / Semaphore & // Utilisez la structure Semaphore et les fonctions P et V.
void empiler (int a)
{
/ 1 /
pile[ sommet ] = a;
sommet++;
/ 2 /
}
int depiler()
{
/ 3 /
sommet--;
int tmp = pile[ sommet ];
/ 4 /
return tmp;
}
b) [3 pts] On veut maintenant permettre aux threads de partager une file circulaire,
denfiler et de d filer un ou plusieurs l ments de la file. La fonction enfiler
ins re en queue de file, lun la suite de lautre, les l ments dun tableau. La
fonction defiler r cup re, dans un tableau, un ou plusieurs l ments de la file.
Les fonctions enfiler et defiler peuvent tre appel es simultan ment par
plusieurs threads du processus. La fonction enfiler (int A[], int m) bloque jusqu
ce que lespace n cessaire pour ins rer les l ments du tableau A soit libre
dans la file. De son c t , la fonction defiler (int A[], int m) bloque jusqu ce quil
y ait au moins m l ments dans la file. Pour les deux fonctions, m est la
dimension du tableau A. Sa valeur est suppos e inf rieure ou gale la taille de
la file. Elle est la m me pour tous les appels aux fonctions enfiler et defiler.
Compl tez, en utilisant les s maphores, le code suivant de mani re satisfaire
les contraintes de synchronisation des fonctions enfiler et defiler.
Page 4 sur 12
INF2610 Examen final
Automne 2010
int t = 0, q=0;
int file [ Size ];
/ 0 / Semaphore & // Utilisez la structure Semaphore et les fonctions P et V.
void enfiler (int A[], int m)
{
int i;
/ 1 /
Publicité
for(i=0; i<m;i++)
{
file = A ;
q=(q+1)%Size;
}
/ 2 /
}
void defiler (int A[], int m)
{ int i;
/ 3 /
for(i=0; i<m;i++)
{
A = file ;
t=(t+1)%Size;
}
/ 4 /
}
Page 5 sur 12
INF2610 Examen final
Automne 2010
Question 4 (3.5 pts) : Interblocage
Soient 3 processus concurrents P1, P2 et P3 qui utilisent en exclusion mutuelle 6
ressources diff rentes (de R1 R6). Les processus ex cutent respectivement les
codes suivants :
P1()
{
P2()
{
P3()
{
while(1){
while(1){
while(1){
prendre (R4);
prendre (R5);
prendre (R3);
// Utiliser R4, R5, R3
liberer(R4);
liberer(R5);
liberer(R3);
prendre (R3);
prendre (R2);
prendre (R6);
//Utiliser R3, R2, R6
liberer(R6);
liberer(R2);
liberer(R3);
prendre (R1);
prendre (R2);
prendre (R5);
// Utiliser R1, R2, R5
liberer(R5);
liberer(R2);
liberer(R1);
}
}
}
}
}
}
La fonction prendre permet dallouer une ressource au processus appelant, si cette
derni re est libre. Dans le cas contraire, elle bloque le processus appelant jusqu
lobtention de la ressource demand e. Une ressource allou e est lib r e par le
processus d tenteur lorsquil invoquera la fonction liberer.
Ces processus peuvent-ils entrer en interblocage ? Si oui, peut-on pr venir les
interblocages ? Peut-on les viter ? Justifiez vos r ponses.
Page 6 sur 12
INF2610 Examen final
Automne 2010
Question 5 (3.5 pts) : Ordonnancement de processus
a) [1.5 pts] Consid rez un syst me monoprocesseur et les 5 processus P1, P2,
P3, P4 et P5 d crits dans le Tableau 1 :
Processus Date darriv e
Priorit
Temps dex cution
P1
P2
P3
P4
P5
0
1
2
4
5
3
3
2
1
2
Tableau 1
5 (2) 3
6
2 (3) 2
2
2
Supposez que :
le syst me dispose dun seul p riph rique dE/S partag entre les
processus,
le temps de commutation est gal 0, et
la priorit 1 est la plus basse.
Donnez
le diagramme de Gantt montrant
lordonnancement des
processus dans le cas dun ordonnancement pr emptif priorit s fixes.
Lordonnancement des processus de m me priorit est circulaire avec un
quantum gal 3.
b)
[2 pts] Consid rez les t ches d crites par les caract ristiques suivantes,
partageant la m me ressource R :
Processus Date darriv e Temps dex cution Deadline = P riode
P1
P2
P3
3 ERE
2 EE
4 ERRE
6
8
Publicité
12
3
2
0
Ces processus sont-ils ordonnan ables RMA dans le cas o PIP (protocole
dh ritage de priorit s) est utilis pour traiter les inversions de priorit ?
Lintervalle d tude consid rer est [0,27].
Page 7 sur 12
INF2610 Examen final
Automne 2010
Le corrig
Question 1 :
a)
P0 cr e un processus F1 puis affiche n=0
F1 cr e un processus F11 puis affiche n=0
F11 cr e un processus F111 puis affiche n=1
F111 ne cr e pas de processus mais affiche n=3
b)
Oui, il suffit, dune part, de sp cifier lors de la cr ation ou louverture du
fichier que le handle est h ritable par les processus fils et, dautre part,
dindiquer lors de la cr ation du fils quil h rite tous les objets marqu s
h ritables.
c)
II permet dex cuter en exclusion mutuelle certaines m thodes (les
m thodes de type synchronized) dun m me objet. Il associe un chaque
objet une variable de condition et deux files dattente : Entry queue et
wait queue. La premi re file sert g rer les demandes dacc s aux
m thodes de lobjet alors que la seconde est utilis e pour se mettre en
attente de
la variable de condition de
lobjet. Le mod le de
synchronisation utilis est similaire celui des lecteurs / r dacteurs
dune base de donn es. Lobjet repr sente la base de donn es. Ses
m thodes de type Synchronized sont
les r dacteurs. Ses autres
m thodes sont des lecteurs.
Question 2 : (4pts)
Moniteur SynCycles
{
/0/ boolc c1, c2, c3;
bool t1=1, t2=1, t3=0; // ti =0 si ce nest pas le tour de thi, ti=1 sinon.
Function F1() // fonction de th1
Page 8 sur 12
INF2610 Examen final
Automne 2010
{ while (1)
{
/1/ while (t1!=1) c1.wait();
Sc1(); // section critique de th1
/2/
t1=0;
if (t2==0) {
t3=1;
c3.signal();
}
}
}
Function F2() // fonction de th2
{ while (1)
{
/3/ while(t2!=1) c2.wait();
Sc2(); // section critique de th2
/4/ t2=0;
if( t1==0) { t3 =1;
c3.signal();
}
}
}
Function F3() // fonction de th3
{ while (1)
{
/5/ while (t3!=1) c3.wait();
Sc3(); // section critique de th3
/6/ t3=0; t1=1; t2=1; c1.signal(); c2.signal();
}
}
}
Page 9 sur 12
INF2610 Examen final
Automne 2010
Question 3 :
a)
int sommet = 0;
int pile [ Size ];
/ 0 / Semaphore libre= Size, Occupe=0, mutex =1;
void empiler (int a)
{
/ 1 /
P(libre);
P(mutex);
pile[ sommet ] = a;
sommet++;
/ 2 /
V(mutex);
V(occupe);
}
int depiler()
{
/ 3 /
P(occupe);
P(mutex);
sommet--;
int tmp = pile[ sommet ];
/ 4 /
V(mutex);
V(libre);
return tmp;
}
b)
int t = 0, q=0;
int file [ Size ];
/ 0 / Semaphore libre = Size, occupe=0, mutex1=1, mutex2=1;
void enfiler (int A[], int m)
{
int i;
/ 1 / P(mutex1);
for(i=0; i<m; i++) P(libre);
for(i=0; i<m;i++)
{
file[ q ] = A ;
q=(q+1)%Size;
}
Publicité
/ 2 / V(mutex1);
Page 10 sur 12
INF2610 Examen final
Automne 2010
for(i=0; i<m; i++) V(occupe);
}
void defiler (int A[], int m)
{
/ 3 / P(mutex2);
for(i=0; i<m; i++) P(occupe);
for(int i=0; i<m;i++)
A = file[ t ];
{
t=(t+1)%Size;
}
/ 4 /
V(mutex2);
for(i=0; i<m;i++) V(libre);
}
Question 4 : 3.5 pts
Oui, le sc nario suivant m ne vers un interblocage :
P1 prend R4 et R5;
P3 prend R1 et R2;
P2 prend R3;
P1 attend R3; (d tenue par P2)
P3 attend R5; (d tenue par P1)
P2 attend R2; (d tenue par P3)
Oui, on peut les pr venir en ordonnant les ressources R1<R2<R3<R4<R5<R6
et en modifiant le code de mani re demander les ressources dans un ordre
croissant :
P1()
{
P2()
{
P3()
{
while(1){
while(1){
while(1){
prendre (R3);
prendre (R4);
prendre (R5);
// Utiliser R4, R5,
R3
prendre (R2);
prendre (R3);
prendre (R6);
//Utiliser R3, R2,
R6
prendre (R1);
prendre (R2);
prendre (R5);
//Utiliser R1, R2,
R5
liberer(R4);
liberer(R5);
liberer(R3);
liberer(R6);
liberer(R2);
liberer(R3);
liberer(R5);
liberer(R2);
liberer(R1);
}
}
}
}
}
}
Oui, on peut les viter en appliquant lalgorithme du banquier car on connait
les besoins maximaux des processus. Au d part toutes les ressources sont
libres et la matrice Alloc est nulle :
Page 11 sur 12
INF2610 Examen final
Automne 2010
A = (1,1,1,1,1,1),
0 0 0 0 0 0
Alloc = 0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 1 1 0
Req = 0 1 1 0 0 1
1 1 0 0 1 0
Question 5 :
a)
P
1
0
P
1
1
b)
P
1
2
P
2
3
P
2
4
P
2
5
P
1
6
P
1
7
P
2
8
P
2
9
P
2
1
0
P
1
1
Publicité
1
P
1
1
2
P
1
1
3
P
3
1
4
P
3
1
5
P
5
1
6
P
5
1
7
P
4
1
8
P
3
1
9
P
3
2
0
P
4
2
1
E
R E
E R E
E R E
E R E
E
E
E E
E E
R R
2
1
2
9
2
0
2
1
P
1
2
5
X
2
2
4
3
P
3
2
6
P
2
2
7
P
1
E
R
E R
0 1 2 3 4 5 6 7 8 9 1
0
P
2
P
2
P
1
P
3
P
1
1
1
1
3
1
2
P
3
E
1
1
5
4
P
1
1
6
1
7
1
8
P
2
Page 12 sur 12