Cours INF2610 - Noyau d’un système d’exploitation

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

Question 2 (4 points)

a) Les requˆetes de lecture sur un disque pour les cylindres suivants sont en queue initialement:

22, 2, 33, 3, 12, 40, 0, 7. Les requˆetes suivantes s’ajoutent en cours de route: cylindre 27

a 10ms, 25 a 26ms et 31 a 42ms. Le systeme utilise l’algorithme de l’ascenseur et ins`ere

les nouvelles requˆetes au fur et `a mesure dans son ordonnancement. La tˆete est initialement

positionn´ee sur le cylindre 10 et se d´eplace en descendant. Le d´eplacement de la tˆete re-

quiert 1ms par cylindre de d´eplacement. Quel est le temps total requis pour servir toutes ces

requˆetes? (2 points)

Le syst`eme ordonnance les requˆetes ainsi, puisqu’il est rendu au cylindre 10 et descend: 7,

3, 2, 0, 12, 22, 33, 40. Les temps de passage `a chaque cylindre sont: 7 (3), 3 (7), 2 (8), 0

(10), 12 (22), 22 (32), 33 (43), 40 (50). Lorsque 27 s’ajoute a 10ms, la tˆete est a 0 et monte,

a 26ms pour 25, la tˆete est a 16 et monte, a 42ms pour 31, la tˆete est a 32, monte et devra

redescendre. Ceci donne donc au final: 7 (3), 3 (7), 2 (8), 0 (10), 12 (22), 22 (32), 25 (35),

27 (37), 33 (43), 40 (50), 31 (59). Le temps total est donc 59ms.

´Ecole Polytechnique de Montr´eal

page 2 sur 4

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

b) Il arrive `a l’occasion que plusieurs p´eriph´eriques doivent se partager le mˆeme num´ero d’inter-

ruption. Comment le syst`eme d’exploitation et ses pilotes d’interface peuvent-ils g´erer cela

puisqu’on ne peut savoir a priori lequel des p´eriph´eriques partageant le mˆeme num´ero a

effectu´e une demande d’interruption? (1 point)

Le syst`eme d’exploitation doit appeler chaque pilote d’interface qui partage le num´ero d’interruption

pour lui livrer la demande d’interruption. Le pilote sonde alors l’interface pour d´eterminer si

une interruption a ´et´e demand´ee, auquel cas le pilote retourne la valeur IRQ HANDLED. Le

syst`eme d’exploitation peut ainsi v´erifier que l’interruption demand´ee a ´et´e trouv´ee et prise

en charge.

c) Le syst`eme d’exploitation Windows contient une couche d’adaptation au mat´eriel (HAL) qui

est a un plus bas niveau que les pilotes d’interface. Pourtant, les pilotes d’interface sont a tr`es

bas niveau puisqu’ils parlent directement avec le mat´eriel et doivent connaˆıtre les sp´ecificit´es

de l’interface comme ses registres ou les codes requis pour effectuer diff´erentes commandes.

En Linux aussi, une couche semblable existe. En effet, certains pilotes d’interface (e.g. carte

r´eseau PCI) peuvent ˆetre utilis´es sans modification sur diff´erents systemes (e.g. systeme Intel

x86 ou MIPS). Expliquez en quoi consiste cette couche d’adaptation? (1 point)

La couche d’adaptation permet d’isoler le pilote d’interface de certaines particularit´es pro-

pres `a l’architecture comme comment r´eserver un num´ero d’interruption ou des adresses

d’E/S et comment interagir avec les interruptions ou lire et ´ecrire vers les E/S (e.g. instruc-

tions sp´ecialis´ees versus E/S calqu´ees sur la m´emoire). Pour ce faire, la couche d’adaptation

offre un certain nombre de fonctions ou macros qui effectuent ce travail de mani`ere appro-

pri´ee pour chaque architecture diff´erente.

Question 3 (3 points)

Soit le graphe des ressources de la figure 2.

a) Donnez une s´equence d’ex´ecution menant `a cet interblocage. (2 points)

• P1 obtient R3

• P1 obtient R2

• P2 obtient R1

• P3 obtient R5

• P3 obtient R4

• P3 demande R1 et bloque

• P2 demande R2 et bloque

• P1 demande R4 et bloque

´Ecole Polytechnique de Montr´eal

page 3 sur 4

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

Figure 2: Graphe des ressources de la question 3

b) Vous ˆetes responsable de l’assurance qualit´e d’un logiciel d’ench`ere en ligne. Vous de-

vez ´evaluer le logiciel produit par votre ´equipe de d´eveloppement. Expliquez les strat´egies

qu’il serait possible d’utiliser pour s’assurer que le logiciel ne pr´esente pas d’interblocage,

mˆeme si plusieurs utilisateurs tentent de miser en mˆeme temps. Nommez les avantages et

inconv´enients de chacune. (1 point)

La premiere ligne de d´efense est le test de charge, qui consiste a simuler un grand nombre

de requˆetes simultan´ees sur le systeme, peu coˆuteux et facile a faire, mais n’est pas une

preuve qu’il n’existe pas d’interblocage possible. Une m´ethode formelle serait envisageable

pour une section critique du code, strat´egie plus coˆuteuse, mais qui apporte la preuve que le

logiciel ne permet pas d’interblocage.

´Ecole Polytechnique de Montr´eal

page 4 sur 4

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

Question 4 (4 points)

Soit l’extrait de code suivant:

printf("CreatePipe a ´echou´e (%d).\n", GetLastError());

ExitProcess(1);

1 [...]

2 SECURITY_ATTRIBUTES saAttr;

3 saAttr.nLength = sizeof(SECURITY_ATTRIBUTES);

4 saAttr.bInheritHandle = FALSE;

5 saAttr.lpSecurityDescriptor = NULL;

6

7 if (!CreatePipe(&FD[0], &FD[1], NULL, 0)) {

8

9

10 } else

11

12

13

14 if (!CreateProcess("child.exe", buf, NULL,

15

16

17

18 }

19 [...]

printf("FD[0]= %d, FD[1]=%d\n", FD[0], FD[1]);

NULL, FALSE, 0, NULL, NULL, &si, &pi)) {

printf("CreateProcess a ´echou´e (%d).\n", GetLastError());

ExitProcess(1);

a) Indiquez les modifications a apporter pour que le processus child.exe ait acces au tube

cr´e´e. (2 points)

Trois modifications sont n´ecessaires: saAttr.bInheritHandle = TRUE, CreatePipe(..., ..., &saAttr,

0) et CreateProcess(..., ..., ..., ..., TRUE, ...);

b) WinAPI d´efinit la fonction WaitForMultipleObjects() pour attendre la fin de plusieurs

processus. ´Ecrivez la fonction int multiwait(pid t *lst, int nb) ´equivalente

pour Linux, qui prend en param`etre un tableau de PID et la taille du tableau. Retournez -1 en

cas d’erreur. Pour simplifier, assumez que l’argument INFINITE est utilis´e comme d´elai

d’attente. Que peut-on faire de plus avec WaitForMultipleObject() contrairement `a

la fonction multiwait(), outre l’option du d´elai d’attente? (2 points)

int multiwait(pid_t *lst, int nb) {

int i;

int status;

for (i=0; i<nb; i++) {

if (waitpid(lst[i], &status, 0) < 0);

return -1;

}

return 0;

}

´Ecole Polytechnique de Montr´eal

page 5 sur 4

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

L’avantage est que la fonction WaitForMultipleObjects() prend en param`etre d’autres

types de handle (s´emaphore, ´ev`enement, etc), donc est plus polyvalente que la fonction

multiwait() qui est sp´ecifique pour attendre la fin d’un groupe de processus.

´Ecole Polytechnique de Montr´eal

page 6 sur 4

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

Question 5 (6 points)

a) Les processus suivants sont soumis `a l’ordonnanceur aux temps indiqu´es avec la dur´ee

et le niveau de priorit´e associ´es (0 la plus faible priorit´e).

Ils sont list´es dans le format

(arriv´ee : dur´ee : priorit´e): P1(0:10:3), P2(2:6:4), P3(4:8:2), P4(6:12:1), P5(8:4:5). A

chaque unit´e de temps, l’ordonnancement peut changer en fonction des nouvelles tˆaches ar-

riv´ees. Donnez l’ordonnancement et le temps d’attente moyen pour chacun des algorithmes

d’ordonnancement suivants: i) tourniquet avec un quantum de 2 o`u une tˆache nouvellement

arriv´ee est plac´ee en d´ebut de tourniquet et obtient imm´ediatement la main lorsqu’un quan-

tum vient de se terminer, ii) selon les priorit´es, iii) la tˆache avec le plus court temps restant

en premier (SRT). (3 points)

L’ordonnancement sera le suivant avec le tourniquet: P1, P1, P2, P2, P3, P3, P4, P4, P5,

P5, P1, P1, P2, P2, P3, P3, P4, P4, P5, P5(fin), P1, P1, P2, P2(fin), P3, P3, P4, P4, P1, P1,

P3, P3(fin), P4, P4, P1, P1(fin), P4, P4, P4, P4(fin). Les temps de fin (P1 `a P5) sont donc

36, 24, 32, 40, 20, les temps de s´ejour 36, 24 - 2, 32 - 4, 40 - 6, 20 - 8 (moyenne 26.4) et

les temps d’attente 36 - 10, 24 - 2 - 6, 32 - 4 - 8, 40 - 6 - 12, 20 - 8 - 4 (moyenne 18.4).

L’ordonnancement par priorit´e est: P1, P1, P2, P2, P2, P2, P2, P2(fin), P5, P5, P5, P5(fin),

P1, P1, P1, P1, P1, P1, P1, P1(fin), P3, P3, P3, P3, P3, P3, P3, P3(fin), P4, P4, P4, P4, P4,

P4, P4, P4, P4, P4, P4, P4(fin). Les temps de fin (P1 `a P5) sont: 20, 8, 28, 40, 12, les temps

de s´ejour 20, 8 - 2, 28 - 4, 40 - 6, 12 - 8 (moyenne 17.6), et les temps d’attente 20 - 10, 8 -

2 - 6, 28 - 4 - 8, 40 - 6 - 12, 12 - 8 - 4 (moyenne 9.6). Avec le plus court en premier, on a:

P1, P1, P2, P2, P2, P2, P2, P2(fin), P5, P5, P5, P5(fin), P3, P3, P3, P3, P3, P3, P3, P3(fin),

P1, P1, P1, P1, P1, P1, P1, P1(fin), P4, P4, P4, P4, P4, P4, P4, P4, P4, P4, P4, P4(fin). Les

temps de fin (P1 `a P5) sont 28, 8, 20, 40, 12, les temps de s´ejour 28, 8 - 2, 20 - 4, 40 - 6, 12

• 8 (moyenne 17.6), et les temps d’attente 28 - 10, 8 - 2 - 6, 20 - 4 - 8, 40 - 6 - 12, 12 - 8 - 4

(moyenne 9.6).

b) Un syst`eme temps r´eel doit supporter plusieurs tˆaches p´eriodiques (p´eriode: dur´ee): P1(25:10),

P2(40:10), P3(35:10). Est-ce que l’ordonnancement peut se faire avec l’algorithme RMA

(priorit´e inversement proportionnelle `a la p´eriode)? EDF? D´emontrez-le. (2 points)

Avec RMA, la condition suffisante de Liu et Layland n’est pas satisfaite, ce qui ne permet

donc pas de conclure positivement. Il faut donc v´erifier manuellement si un ordonnancement

est possible. Les priorit´es seront donn´ees P1 puis P3 et enfin P2. Au temps 0, P1 obtient la

main pour 10, a 10 P3 obtient la main pour 10, a 20 P2 obtient la main pour 5, pr´eemption, `a

25 P1 pour 10, `a 35 P3 pour 10 et P2 a manqu´e son ´ech´eance! Nous pouvons donc conclure

que l’ordonnancement avec RMA n’est pas possible.

Avec EDF, on commence avec P1 pour 10, ensuite P3 pour 10, ensuite P2 pour 10, P1 pour

10, P3 pour 10, P1 pour 10, P2 pour 10 et etc. De toute mani`ere, avec EDF l’ordonnancement

est toujours possible lorsque le taux d’utilisation est inf´erieur ou ´egal `a 1.

c) Comment se compare l’algorithme EDF (priorit´e a l’´ech´eance la plus proche) a RMA? Dans

quel cas RMA serait-il pr´ef´erable? (1 point)

L’algorithme EDF va toujours au plus press´e et ne ratera donc aucune ´ech´eance, si l’ordonnancement

est possible et en l’absence d’autres consid´erations comme le d´elai de changement de con-

´Ecole Polytechnique de Montr´eal

page 7 sur 4

D´epartement de g´enie informatique et g´enie logiciel

Cours INF2610 - Noyau d’un syst`eme d’exploitation

Examen final - Hiver 2012

texte. Il est donc g´en´eralement pr´ef´erable. L’int´erˆet de RMA est qu’il s’agit d’un calcul

statique de priorit´e, il n’est donc pas n´ecessaire de constamment mettre `a jour la priorit´e en

fonction des ´ech´eances, qui se rapprochent au fur et `a mesure du temps qui avance. RMA

peut donc ˆetre int´eressant si l’ordonnancement est garanti, par exemple un syst`eme parfaite-

ment p´eriodique qui satisfait la condition de Liu et Layland

Par: Michel Dagenais et Francis Giraldeau

´Ecole Polytechnique de Montr´eal

page 8 sur 4

D´epartement de g´enie informatique et g´enie logiciel