Examen final INF2610

} }

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 d’occurrences de l’événement associé. La valeur

Hiver 2011 Noyau du système d’exploitation

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 n’y 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*/ { 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 n’est 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 l’ordre 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 qu’il 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 d’exploitation

Page 4 sur 7

Examen final INF2610

consommer, il rentre également dans une attente active jusqu’à ce qu’un item soit inséré dans le tampon.

a) [2 pts] Donnez le nombre d’items 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 d’attente 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 d’items 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 d’exécution (temps de calcul) valent 2. Les périodes des tâches Bi valent 6, et leurs durées d’exé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 l’algorithme 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 d’ordonnancement est EDF.

Bonne fin de session.

Hiver 2011 Noyau du système d’exploitation

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 qu’ils 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 qu’un 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 c’est le tour de B,

l’ordonnanceur 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)=

e) Avantage : Avec une seule file d’exé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 d’utilisation des processeurs. Inconvénient : Il faut gérer la répartition des processus dans les différentes files d’exécution.

Solution 2 :

Barrier_t B14(2), B123(3), B234(3) /*0*/

Hiver 2011 Noyau du système d’exploitation

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() ; } }

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 d’exploitation

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