Hiver 2011
Noyau du syst me dexploitation
Page 1 sur 7
Examen final
INF2610
Question 1 (5.5 pts) : G n ralit s
R pondez, en 15 lignes maximum par sous-question (attention : les r ponses non justifi es
ne seront pas consid r es).
a) [1 pt] Expliquez comment le principe copy-on-write est utilis pour cr er un
clone dun processus.
b) [1 pt] Supposez que la file dattente dun s maphore binaire est g r e selon les
priorit s (lorsque le s maphore est lib r , il est allou au processus le plus prioritaire,
en attente du s maphore). Peut-on avoir, dans ce cas, des probl mes dinversion de
priorit s, dans le cas dun ordonnancement pr emptif priorit ?
c) [1 pt] Supposez deux processus A et B qui partagent une ressource R en exclusion
mutuelle :
Semaphore x=1 ;
A
P(x)
scA(R)
V(x)
B
P(x)
scB(R)
V(x)
Les processus A et B sont ex cut s dans un syst me temps partag avec un
ordonnancement circulaire. Le syst me peut-il suspendre le processus A durant
lex cution de sa section critique et lire ensuite le processus B ? Si oui, est-ce que B peut
se retrouver en section critique ?
d) [1.5 pt] Consid rez le probl me des philosophes. Peut-on utiliser lalgorithme du
banquier pour viter les interblocages ? Si oui, expliquez la d finition de l tat, les
traitements des demandes et des lib rations de ressources. Donnez l tat de d part
ainsi que l tat atteint suite la demande de fourchette suivante : le philosophe 4
demande la fourchette f4.
e) [1 pt] Pour g rer lallocation des processeurs, le syst me dexploitation Linux utilise
une file dex cution ( run queue ) par processeur. Donnez un avantage et un
inconv nient, par rapport lutilisation dune seule et m me file dex cution pour
tous les processeurs.
Question 2 (3.5 pts) : Barri res et compteurs d v nements
Les Barri res sont un m canisme tr s utile pour synchroniser les phases de traitement de
diff rents processus : aucun processus ne peut entamer la phase suivante tant que les autres
nont pas fini leurs phases courantes. Pour r aliser une telle synchronisation, une barri re est
Hiver 2011
Noyau du syst me dexploitation
Page 2 sur 7
Examen final
INF2610
plac e la fin de chaque phase. Lorsquun processus atteint une barri re, il est bloqu
jusqu ce que tous les autres processus atteignent la barri re. Les processus peuvent alors
ex cuter leurs phases suivantes et ainsi de suite.
Par exemple, le traitement de chacun des trois processus A, B et C suivants consistent en
deux phases acquisition et traitement de param tres. Avec la barri re X, il ne peut y
avoir un processus l tape acquisition de param tres et un autre l tape de traitement.
Cette barri re permet aux trois processus de se synchroniser avant dentamer une autre phase.
Barrier_t X (3) ; // 3 est le nombre de processus utilisant la barri re X.
Processus A
{ while (1)
{ AcquisParam(1) ;
Processus B
{ while (1)
{ AcquisParam(2) ;
Processus C
{ while (1)
{ AcquisParam(3) ;
X.Barriere( ) ;
TrtParam(1) ;
X.Barriere( ) ;
}
}
X.Barriere( ) ;
TrtParam(2) ;
X.Barriere( ) ;
X.Barriere( ) ;
TrtParam(3) ;
X.Barriere( ) ;
}
}
Publicité
}
}
a) [2 pts] On veut utiliser les barri res pour ex cuter les diff rents cycles des t ches T1, T2,
T3 et T4 en respectant les contraintes de pr c dence suivantes :
-
-
-
-
le premier cycle de T1 est ex cut en premier ;
les cycles de T2 et T3 sont ex cut s en concurrence apr s celui de T1 ;
le cycle de T4 commence lorsque ceux de T2 et T3 sont termin s ;
le second cycle de T1 est ex cut apr s celui de T4, et ainsi de suite.
Compl tez le pseudo-code suivant de chaque t che en ajoutant les barri res n cessaires la
synchronisation des diff rents cycles. Indiquez clairement les barri res utilis es, leurs valeurs
ainsi que leurs r les.
Barrier_t /0/ // CompteurEvenement /0/ pour b)
T1( )
{
while (1)
{
/1/
cycle(T1) ;
/2/
}
}
T2( )
{
while (1)
{
/3/
cycle(T2) ;
/4/
}
}
T3( )
{
while (1)
{
/5/
cycle(T3);
/6/
}
}
T4( )
{
while (1)
{
/7/
cycle(T4 ) ;
/8/
}
}
b) [1.5 pt] On veut maintenant refaire le m me exercice en utilisant les compteurs
d v nements. Un compteur d v nements est un compteur entier associ un
v nement. Sa valeur indique le nombre doccurrences de l v nement associ . La valeur
Hiver 2011
Noyau du syst me dexploitation
Page 3 sur 7
Examen final
INF2610
initiale du compteur est 0. Trois op rations atomiques sont d finies pour un compteur
d v nements E :
- E.Read() : retourne la valeur courante de E au processus appelant.
- E.Advance() : incr mente de 1 la valeur de E et d bloque tous les processus en attente
que l v nement E atteigne cette nouvelle valeur.
- E.Await(val) : bloque le processus appelant, si la valeur de E est strictement
inf rieure val. Il ny a pas de blocage du processus appelant si la valeur de E est
plus grande ou gale val.
Synchronisez les cycles des t ches pr c dentes en utilisant les compteurs d v nements.
Indiquez clairement les compteurs d v nements et variables utilis s et leurs r les.
Question 3 (5 pts) : Moniteurs
On veut utiliser les moniteurs et les variables de condition pour solutionner le probl me des
lecteurs-r dacteurs. Pour ce faire, on d cide de regrouper, dans un m me moniteur, les
fonctions ReadRequest(), WriteRequest(), ReadEnd() et WriteEnd(). Les fonctions
ReadRequest() et ReadEnd() encadrent toute op ration de lecture. De m me, les fonctions
WriteRequest() et WriteEnd() encadrent toute op ration d criture.
Moniteur AccesBD
/0/
Publicité
{
ReadRequest( ) { /1/}
WriteRequest( ) { /2/}
ReadEnd( ) { /3/}
WriteEnd( ) { /4/}
}
Compl tez le moniteur pr c dent de mani re permettre des acc s partag s en lecture et un
acc s exclusif en criture. Vous devez d finir et expliquez le r le de toute variable utilis e. Il
nest pas demand de g rer le probl me de famine des r dacteurs.
Question 4 (4 pts) : Ordonnancement
Consid rez un syst me monoprocesseur ordonnancement circulaire. Supposez que 3
producteurs P1, P2, P3 et un consommateur C1 arrivent dans le syst me et sont ins r s dans
la file d'attente du processeur dans lordre P1, P2, P3 et C1. Les producteurs et le
consommateur communiquent via un tampon. Les producteurs produisent des items et les
ins rent dans le tampon. Le consommateur retire ces items dans l'ordre FIFO. Chaque item
n cessite 1 quantum de temps pour le produire et 1 quantum de temps pour le consommer. Le
tampon est initialement vide et a une taille maximale de 3. Si le tampon est plein quand un
producteur veut produire, il rentre dans une attente active jusqu ce quil parvienne se
r server une entr e dans le tampon. Si le tampon est vide lorsque le consommateur veut
Hiver 2011
Noyau du syst me dexploitation
Page 4 sur 7
Examen final
INF2610
consommer, il rentre galement dans une attente active jusqu ce quun item soit ins r dans
le tampon.
a) [2 pts] Donnez le nombre ditems que chaque processus aura produit ou consomm la
fin de 10 quanta de temps. Pour r pondre, cette question, vous devez donner le
diagramme de Gantt.
b) [2 pts] Supposez maintenant que les attentes actives sont remplac es par des attentes
passives : si le tampon est plein quand un producteur veut produire, il passe l tat
bloqu (P(libre)). Si le tampon est vide lorsque le consommateur veut consommer, il
passe galement l tat bloqu (P(occupe)). Les files dattente des s maphores sont
g r es FIFO. Supposez aussi, que les temps n cessaires un producteur ou un
consommateur pour passer l tat bloqu ou l tat pr t sont n gligeables.
Donnez, dans ce cas, le nombre ditems produits ou consomm s par chacun des processus
la fin de 10 quanta de temps. Pour r pondre, cette question, vous devez aussi donner
le diagramme de Gantt.
Question 5 (2 pts) : Ordonnancement temps r el
Consid rez un syst me compos de n t ches p riodiques, A1, A2,&, An, et m=2*n t ches
p riodiques B1, B2,&, Bm. Les p riodes des t ches Ai valent 12, et leurs dur es dex cution
(temps de calcul) valent 2. Les p riodes des t ches Bi valent 6, et leurs dur es dex cution
valent 1. Les ch ances des t ches sont leurs p riodes.
a) [1 pt] Supposez que pour ordonnancer ces t ches, le syst me impl mente lalgorithme
EDF (Earliest Deadline First). Donnez le nombre maximal de t ches admettre dans le
syst me sans compromettre leur ordonnan abilit .
b) [1 pt] Donnez le diagramme de Gantt sur 14 unit s de temps, dans le cas o : n=1, les
t ches A1, B1 et B2 arrivent respectivement aux dates 0, 1 et 2, et la politique
dordonnancement est EDF.
Bonne fin de session.
Hiver 2011
Noyau du syst me dexploitation
Page 5 sur 7
Examen final
INF2610
Solution 1 :
a) La table (les tables) des pages du processus p re est (sont) dupliqu e(s). Le p re
et le fils partageront les m mes cadres m moire tant quils y acc dent en lecture.
Si le processus p re ou fils veut acc der en criture un de ces cadres partag s,
une copie du cadre est cr e pour le processus crivain.
b) Oui, car peu importe la discipline de gestion de la file du s maphore, si un
processus L, moins prioritaire quun autre processus H, demande un s maphore
binaire libre, il le verrouillera. Si le processus H demande par la suite le
s maphore, il passera et restera l tat bloqu jusqu la lib ration du
s maphore.
c) Oui, si par exemple, A a consomm tout son quantum et cest le tour de B,
lordonnanceur va lire B. Non, car il passera l tat bloqu dans P(x).
d) Oui, car on connait les besoins de chaque philosophe. E=A=(11111), Alloc(phi,
(00000), Req(ph0)=(10001), Req(ph1)=(11000), Req(ph2)=(01100),
i=0,4)=
Req(ph3)=(00110) et Req(ph4)=(00011).
Si le philosophe 4 demande f4, l tat atteint serait :
E=(11111), A=(11110) Alloc(phi,
(00000), Alloc(ph4)=(00001),
Req(ph0)=(10001), Req(ph1)=(11000), Req(ph2)=(01100), Req(ph3)=(00110) et
Req(ph4)=(00010).
i=0,3)=
Publicité
e) Avantage : Avec une seule file dex cution, si un processeur acc de la run
queue tous les autres processeurs vont attendre (acc s exclusive). Ce qui aura
un impact sur le taux dutilisation des processeurs.
Inconv nient : Il faut g rer la r partition des processus dans les diff rentes files
dex cution.
Solution 2 :
Barrier_t B14(2), B123(3), B234(3) /0/
Hiver 2011
Noyau du syst me dexploitation
Page 6 sur 7
Examen final
INF2610
T1( )
{ while (1)
{
/1/
cycle(T1) ;
/2/
B123.Barriere();
B14.Barriere() ;
}
}
T2( )
{ while (1)
{
/3/
B123.Barriere();
cycle(T2 ) ;
/4/
B234.Barriere();
}
}
T3( )
{ while (1)
{
/5/
B123.Barriere();
cycle(T3);
/6/
B234.Barriere();
}
}
T4( )
{ while (1)
{
/7/
B234.Barriere();
cycle(T4 ) ;
/8/
B14.Barriere() ;
}
}
//B123 permet de lancer un cycle de T2 et T3 apr s chaque cycle de T1. B14 permet de
lancer un cycle de T1 apr s un cycle de T4. B234 permet de lancer un cycle de T4
apr s les cycles de T2 et T3.
T3( )
{ int n=1 ;
while (1)
{
/5/
E.Await(n);
cycle(T3);
/6/ n=n+4;
E.Advance() ;
}
}
T4( )
{ int n=3;
while (1)
{
/7/
E.Await(n);
cycle(T4 ) ;
/8/ n=n+4;
E.Advance() ;
}
}
Publicité
CompteurEvenement E ;/0/
T1( )
{ int n=0 ;
while (1)
{
/1/
cycle(T1) ;
/2/ n=n+4 ;
E.Advance() ;
E.Await(n) ;
}
}
T2( )
{ int n=1;
while (1)
{
/3/
E.Await(n);
cycle(T2 ) ;
/4/
n=n+4;
E.Advance() ;
}
}
Solution 3 :
Moniteur AccesBD
{
/0/ int nbl=0, libre=0, nbwait=0;
boolc acces;
ReadRequest( )
{ /1/
if(nbl==0)
if(libre)
libre=0;
else { nbwait++, wait(acces);}
nbl++;
}
WriteRequest( )
{ /2/ if (libre) libre=0;
Hiver 2011
Noyau du syst me dexploitation
Page 7 sur 7
Examen final
INF2610
else { nbwait++, wait(acces);}
}
ReadEnd( )
{ /3/ nbl--;
if(nbl==0)
if(nbwait>0) { nbwait--; signal(acces);}
else libre=1;
if(nbwait>0) { nbwait--; signal(acces);}
else libre=1;
}
WriteEnd( )
{ /4/
}
}
Solution 4 :
P1 P2 P3 C1 P1 P2(AA) P3(AA) C1 P1 P2(AA)
P1 3 productions
P2 1 production
P3 1 production
C1 2 consommations
P1 P2 P3 C1 P1 P2(B) P3(B) C1 P1 P2(B) C1 P1 P3(B) C1
P1 4 productions
P2 1 production
P3 1 production
C1 4 consommations
Solution 5 : n (2/12) + 2n(1/6) <=1 => n <= 2
Au maximum, 2 t ches de type A et 4 t ches de type B.
A1B1B2A1---B1B2---A1B1