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

Ce document présente un corrigé d’examen final du cours INF2610 sur le noyau d’un système d’exploitation. Il évalue des compétences en gestion de fichiers, ordonnancement de processus, gestion des interruptions, détection d’interblocages et programmation système.

Question 1

Cette question porte sur le choix de la taille des blocs pour le stockage des courriels et la gestion des fichiers creux.

1.a) Calcul des proportions de fichiers et perte d’espace selon la taille des blocs

On considère des blocs de 1024 ou 2048 octets. Les courriels ont une taille uniforme entre 3254 et 5254 octets.

Pour les blocs de 1024 octets :

• Nombre de blocs nécessaires pour un fichier de taille x : blocs = ceil(x / 1024)
• Les tailles varient entre 3254 et 5254 octets, donc entre 4 et 6 blocs (car 4×1024=4096, 5×1024=5120, 6×1024=6144)

Calcul de la proportion de fichiers nécessitant 4, 5 ou 6 blocs :

• 4 blocs : fichiers de 3254 à 4096 octets → intervalle de 842 octets
• 5 blocs : fichiers de 4097 à 5120 octets → intervalle de 1024 octets
• 6 blocs : fichiers de 5121 à 5254 octets → intervalle de 134 octets

La distribution étant uniforme, la proportion est la longueur de l’intervalle divisée par 2000 (5254-3254).

Calcul de la perte moyenne par fragmentation interne :

• Pour 4 blocs : perte varie de 842 à 0 octets, moyenne 421 octets
• Pour 5 blocs : perte varie de 1023 à 0 octets, moyenne 511.5 octets
• Pour 6 blocs : perte varie de 1023 à 894 octets, moyenne (1023+894)/2 = 958.5 octets

En pondérant par la proportion de fichiers dans chaque intervalle, on obtient une perte moyenne totale de 502.8 octets.

Le pourcentage de perte est donc :

502.8 / ((3254 + 5254) / 2) = 11.8%

Pour les blocs de 2048 octets :

• Les tailles des fichiers nécessitent 2, 3 ou 4 blocs (2×2048=4096, 3×2048=6144)
• La perte moyenne calculée est 1027.1 octets, soit 24.1% de perte.

Conclusion : Les deux tailles de blocs respectent la limite de 25% de perte maximale, mais la taille de 2048 octets est préférable pour maximiser le débit.

Réponse : choisir des blocs de 2048 octets pour maximiser le débit tout en gardant une perte d’espace inférieure à 25%.

1.b) Procédure pour transformer un fichier en fichier creux

On souhaite réduire l’espace disque occupé par un fichier contenant de nombreuses séquences de zéros.

Procédure proposée :

1. Copier le fichier original vers un nouveau fichier.
2. Lorsqu’une séquence continue de zéros est détectée (au moins de la taille d’un bloc), effectuer un seek (déplacement du pointeur) au lieu d’un write (écriture), ce qui évite d’allouer de l’espace disque pour ces zéros.
3. À la fin, supprimer le fichier original.

Cette méthode permet de créer un fichier creux qui économise de l’espace disque en ne stockant pas physiquement les blocs de zéros.

Réponse : copier le fichier en remplaçant les séquences de zéros par des déplacements (seek) dans le fichier creux.

Question 2

Cette question traite de l’ordonnancement des requêtes disque, de la gestion des interruptions partagées et de la couche d’adaptation matérielle.

2.a) Calcul du temps total pour servir les requêtes disque avec l’algorithme de l’ascenseur

Requêtes initiales : 22, 2, 33, 3, 12, 40, 0, 7

Requêtes arrivant en cours de route : 27 à 10ms, 25 à 26ms, 31 à 42ms

La tête est initialement sur le cylindre 10 et descend.

Ordonnancement initial descendant :

7, 3, 2, 0, puis remontée : 12, 22, 33, 40

Calcul des temps de passage (1 ms par cylindre) :

• De 10 à 7 : 3 ms
• 7 à 3 : 4 ms (total 7 ms)
• 3 à 2 : 1 ms (total 8 ms)
• 2 à 0 : 2 ms (total 10 ms)
• À 10 ms, requête 27 arrive, tête à 0 et commence à monter
• À 26 ms, requête 25 arrive, tête à 16 (en montée)
• À 42 ms, requête 31 arrive, tête à 32 (en montée)

Ordonnancement final avec intégration des nouvelles requêtes :

7 (3 ms), 3 (7 ms), 2 (8 ms), 0 (10 ms), 12 (22 ms), 22 (32 ms), 25 (35 ms), 27 (37 ms), 33 (43 ms), 40 (50 ms), 31 (59 ms)

Temps total requis : 59 ms.

2.b) Gestion des interruptions partagées

Plusieurs périphériques peuvent partager un même numéro d’interruption. Le système d’exploitation doit appeler successivement chaque pilote d’interface associé à ce numéro.

Chaque pilote sonde son matériel pour vérifier s’il a généré l’interruption. Si oui, il retourne IRQ HANDLED. Le système sait ainsi quel pilote a pris en charge l’interruption.

Réponse : le système appelle tous les pilotes partageant le numéro, chacun vérifie si l’interruption lui est destinée.

2.c) Rôle de la couche d’adaptation matérielle (HAL)

La couche d’adaptation isole les pilotes d’interface des spécificités propres à l’architecture matérielle (réservation des interruptions, adresses d’E/S, instructions spécifiques).

Elle fournit des fonctions ou macros qui réalisent ces opérations de façon appropriée selon l’architecture (Intel x86, MIPS, etc.).

Cette abstraction permet d’utiliser un même pilote sur différentes architectures sans modification.

Réponse : la couche d’adaptation fournit une interface uniforme aux pilotes, masquant les différences matérielles.

Question 3

Cette question porte sur l’interblocage (deadlock) dans un graphe de ressources.

3.a) Séquence d’exécution menant à l’interblocage

On considère les processus P1, P2, P3 et les ressources R1 à R5.

Séquence :

• P1 obtient R3
• P1 obtient R2
• P2 obtient R1
• P3 obtient R5
• P3 obtient R4
• P3 demande R1 et bloque (car détenu par P2)
• P2 demande R2 et bloque (car détenu par P1)
• P1 demande R4 et bloque (car détenu par P3)

On a un cycle d’attente circulaire, donc un interblocage.

Réponse : la séquence ci-dessus montre un interblocage entre P1, P2 et P3.

3.b) Stratégies pour assurer l’absence d’interblocage dans un logiciel d’enchère en ligne

Deux stratégies principales :

• Test de charge : simuler un grand nombre de requêtes simultanées pour détecter d’éventuels blocages. Avantage : peu coûteux et facile à mettre en œuvre. Inconvénient : ne garantit pas l’absence totale d’interblocage.
• Méthode formelle : analyser formellement le code critique pour prouver qu’aucun interblocage ne peut se produire. Avantage : preuve mathématique de l’absence d’interblocage. Inconvénient : coûteux et complexe à réaliser.

Réponse : utiliser des tests de charge pour détecter les problèmes, et une méthode formelle pour garantir l’absence d’interblocage dans les sections critiques.

Question 4

Cette question traite de la création d’un tube anonyme (pipe) et de la gestion des processus sous Windows et Linux.

4.a) Modifications pour que child.exe ait accès au tube créé

Trois modifications nécessaires :

• Définir saAttr.bInheritHandle = TRUE pour permettre l’héritage des handles.
• Passer &saAttr dans CreatePipe pour que le tube soit créé avec ces attributs.
• Passer TRUE dans CreateProcess pour l’argument bInheritHandles, afin que le processus enfant hérite des handles.

Réponse : mettre bInheritHandle à TRUE, utiliser saAttr dans CreatePipe, et passer TRUE dans CreateProcess.

4.b) Fonction multiwait() équivalente à WaitForMultipleObjects() sous Linux

Code proposé :

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

Différence avec WaitForMultipleObjects() :

• WaitForMultipleObjects() peut attendre sur différents types de handles (processus, sémaphores, événements, etc.), ce qui le rend plus polyvalent.
• multiwait() est spécifique à l’attente de la fin de plusieurs processus.

Réponse : multiwait() attend séquentiellement la fin de plusieurs PID, tandis que WaitForMultipleObjects() gère plusieurs types d’objets synchrones.

Question 5

Cette question porte sur l’ordonnancement des processus et les algorithmes temps réel.

5.a) Ordonnancement et temps d’attente moyen selon trois algorithmes

Processus : P1(0:10:3), P2(2:6:4), P3(4:8:2), P4(6:12:1), P5(8:4:5)

i) Tourniquet (quantum = 2), nouvelle tâche en tête

Ordonnancement :

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)

Temps de fin : P1=36, P2=24, P3=32, P4=40, P5=20

Temps de séjour (fin - arrivée) : P1=36, P2=22, P3=28, P4=34, P5=12

Temps d’attente (séjour - durée) : P1=26, P2=16, P3=20, P4=22, P5=8

Moyenne temps d’attente = 18.4

ii) Priorités (0 la plus faible)

Ordonnancement :

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

Temps de fin : P1=20, P2=8, P3=28, P4=40, P5=12

Temps d’attente moyen = 9.6

iii) Plus court temps restant (SRT)

Ordonnancement :

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

Temps de fin : P1=28, P2=8, P3=20, P4=40, P5=12

Temps d’attente moyen = 9.6

Réponse : les temps d’attente moyens sont 18.4 (tourniquet), 9.6 (priorités), 9.6 (SRT).

5.b) Ordonnancement temps réel avec RMA et EDF

Tâches périodiques : P1(25:10), P2(40:10), P3(35:10)

Avec RMA (priorité inversement proportionnelle à la période) :

• Condition de Liu et Layland non satisfaite → pas de garantie d’ordonnancement.
• Simulation : P1 exécute 0-10, P3 10-20, P2 20-25 (préemption), P1 25-35, P3 35-45, P2 rate son échéance.
• Conclusion : RMA ne garantit pas l’ordonnancement.

Avec EDF (priorité à l’échéance la plus proche) :

• Ordonnancement possible car taux d’utilisation ≤ 1.
• EDF garantit l’ordonnancement dans ce cas.

Réponse : RMA ne garantit pas l’ordonnancement ici, EDF oui.

5.c) Comparaison EDF et RMA

EDF :

• Priorité dynamique selon échéance la plus proche.
• Ne rate aucune échéance si ordonnancement possible.
• Plus complexe à gérer car priorité change en temps réel.

RMA :

• Priorité statique calculée à l’avance.
• Moins flexible, peut rater des échéances si conditions non satisfaites.
• Intéressant pour systèmes parfaitement périodiques respectant la condition de Liu et Layland.

Réponse : EDF est généralement préférable, RMA est utile pour des systèmes périodiques simples avec priorité statique.

Méthode

Ce corrigé récompense la rigueur dans le raisonnement, la présentation claire des étapes de calcul et la justification des réponses. Il est important de suivre les conventions données (notamment pour les calculs de perte d’espace et les algorithmes d’ordonnancement) et de ne pas inventer d’informations non fournies.

Les erreurs fréquentes sanctionnées sont :

• Omettre les étapes intermédiaires de calcul.
• Confondre les définitions ou les conventions propres au cours (ex. taille de blocs, priorité).
• Ne pas expliquer les choix ou les résultats.
• Ne pas respecter les consignes sur les formules ou le code.

Enfin, la capacité à relier théorie et pratique (ex. gestion des interruptions, interblocage, ordonnancement) est essentielle pour réussir ce type d’épreuve.