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

3, 2, 0, 12, 22, 33, 40. Les temps de passage à 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ête est a 0 et monte,

a 26ms pour 25, la tête est a 16 et monte, a 42ms pour 31, la tête 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.

École Polytechnique de Montréal

page 2 sur 4

Département de génie informatique et génie logiciel

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

Examen final - Hiver 2012

b) Il arrive à l’occasion que plusieurs périphériques doivent se partager le même numéro d’inter-

ruption. Comment le système d’exploitation et ses pilotes d’interface peuvent-ils gérer cela

puisqu’on ne peut savoir a priori lequel des périphériques partageant le même numéro a

effectué une demande d’interruption? (1 point)

Le système d’exploitation doit appeler chaque pilote d’interface qui partage le numéro d’interruption

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

une interruption a été demandée, auquel cas le pilote retourne la valeur IRQ HANDLED. Le

système d’exploitation peut ainsi vérifier que l’interruption demandée a été trouvée et prise

en charge.

c) Le système d’exploitation Windows contient une couche d’adaptation au matériel (HAL) qui

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

bas niveau puisqu’ils parlent directement avec le matériel et doivent connaˆıtre les spécificités

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

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

réseau PCI) peuvent être utilisés sans modification sur différents 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és pro-

pres à l’architecture comme comment réserver un numéro d’interruption ou des adresses

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

tions spécialisées versus E/S calquées sur la mémoire). Pour ce faire, la couche d’adaptation

offre un certain nombre de fonctions ou macros qui effectuent ce travail de manière appro-

priée pour chaque architecture différente.

Question 3 (3 points)

Soit le graphe des ressources de la figure 2.

a) Donnez une séquence d’exécution menant à 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

École Polytechnique de Montréal

page 3 sur 4

Département de génie informatique et génie logiciel

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

Examen final - Hiver 2012

Figure 2: Graphe des ressources de la question 3

b) Vous êtes responsable de l’assurance qualité d’un logiciel d’enchère en ligne. Vous de-

vez évaluer le logiciel produit par votre équipe de développement. Expliquez les stratégies

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

même si plusieurs utilisateurs tentent de miser en même temps. Nommez les avantages et

inconvénients de chacune. (1 point)

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

de requêtes simultanées sur le systeme, peu coûteux et facile a faire, mais n’est pas une

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

pour une section critique du code, stratégie plus coûteuse, mais qui apporte la preuve que le

logiciel ne permet pas d’interblocage.

École Polytechnique de Montréal

page 4 sur 4

Département de génie informatique et génie logiciel

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

Examen final - Hiver 2012

Question 4 (4 points)

Soit l’extrait de code suivant:

printf("CreatePipe a échoué (%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 échoué (%d).\n", GetLastError());

ExitProcess(1);

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

créé. (2 points)

Trois modifications sont nécessaires: saAttr.bInheritHandle = TRUE, CreatePipe(..., ..., &saAttr,

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

b) WinAPI définit la fonction WaitForMultipleObjects() pour attendre la fin de plusieurs

processus. Écrivez la fonction int multiwait(pid t *lst, int nb) équivalente

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

cas d’erreur. Pour simplifier, assumez que l’argument INFINITE est utilisé comme délai

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

la fonction multiwait(), outre l’option du délai 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;

}

École Polytechnique de Montréal

page 5 sur 4

Département de génie informatique et génie logiciel

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

Examen final - Hiver 2012

L’avantage est que la fonction WaitForMultipleObjects() prend en paramètre d’autres

types de handle (sémaphore, évènement, etc), donc est plus polyvalente que la fonction

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

École Polytechnique de Montréal

page 6 sur 4

Département de génie informatique et génie logiciel

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

Examen final - Hiver 2012

Question 5 (6 points)

a) Les processus suivants sont soumis à l’ordonnanceur aux temps indiqués avec la durée

et le niveau de priorité associés (0 la plus faible priorité).

Ils sont listés dans le format

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

chaque unité de temps, l’ordonnancement peut changer en fonction des nouvelles tâches ar-

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

d’ordonnancement suivants: i) tourniquet avec un quantum de 2 où une tâche nouvellement

arrivée est placée en début de tourniquet et obtient immédiatement la main lorsqu’un quan-

tum vient de se terminer, ii) selon les priorités, iii) la tâche 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 à P5) sont donc

36, 24, 32, 40, 20, les temps de séjour 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é 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 à P5) sont: 20, 8, 28, 40, 12, les temps

de séjour 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 à P5) sont 28, 8, 20, 40, 12, les temps de séjour 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ème temps réel doit supporter plusieurs tâches périodiques (période: durée): P1(25:10),

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

(priorité inversement proportionnelle à la période)? EDF? Démontrez-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érifier manuellement si un ordonnancement

est possible. Les priorités seront données 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éemption, à

25 P1 pour 10, à 35 P3 pour 10 et P2 a manqué son échéance! 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ère, avec EDF l’ordonnancement

est toujours possible lorsque le taux d’utilisation est inférieur ou égal à 1.

c) Comment se compare l’algorithme EDF (priorité a l’échéance la plus proche) a RMA? Dans

quel cas RMA serait-il préférable? (1 point)

L’algorithme EDF va toujours au plus pressé et ne ratera donc aucune échéance, si l’ordonnancement

est possible et en l’absence d’autres considérations comme le délai de changement de con-

École Polytechnique de Montréal

page 7 sur 4

Département de génie informatique et génie logiciel

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

Examen final - Hiver 2012

texte. Il est donc généralement préférable. L’intérêt de RMA est qu’il s’agit d’un calcul

statique de priorité, il n’est donc pas nécessaire de constamment mettre à jour la priorité en

fonction des échéances, qui se rapprochent au fur et à mesure du temps qui avance. RMA

peut donc être intéressant si l’ordonnancement est garanti, par exemple un système parfaite-

ment périodique qui satisfait la condition de Liu et Layland

Par: Michel Dagenais et Francis Giraldeau

École Polytechnique de Montréal

page 8 sur 4

Département de génie informatique et génie logiciel