Systèmes D'Exploitation I - Examen

Gestion des processus

Question 1 - Appels système et création de processus

Le but de cet exercice est de compléter un programme C utilisant l'appel système fork() afin que le père et le fils affichent correctement leurs identifiants de processus (PID).

Le code extrait du sujet d'examen a été réparé pour être un code C valide et compilable (ajout des bibliothèques nécessaires standard telles que <stdio.h> et <unistd.h>).

Code C complété et corrigé :

#include <stdio.h>
#include <unistd.h>
#include <sys/types.h>

int main() {
    pid_t pid;
    pid = fork();
    
    if (pid == 0) {
        /* (1) Code exécuté par le processus fils */
        printf("FILS : le PID du fils est %d, le PID du père %d\n", getpid(), getppid());
    } else {
        /* (2) Code exécuté par le processus père */
        printf("PERE : le PID du père est %d, le PID de mon fils %d\n", getpid(), pid);
    }
    
    return 0;
}

Explication :

• (1) Dans le bloc if (pid == 0), nous sommes dans le processus fils. L'appel à getpid() retourne le PID du fils (lui-même), et getppid() retourne le PID de son processus parent.
• (2) Dans le bloc else, nous sommes dans le processus père. La variable pid contient le retour du fork(), qui correspond au PID de l'enfant nouvellement créé. getpid() donne ici le PID du père.

Question 2 - Arborescence et évaluation de conditions

L'objectif est de déterminer combien de processus au total sont engendrés par le programme donné, en comprenant le mécanisme d'évaluation des opérateurs logiques && (ET) et || (OU) en C. Le code source original manquait de l'en-tête standard, que l'on suppose implicite.

Code analysé :

#include <unistd.h>

int main(void) {
    fork() && (fork() || fork());
    sleep(2);
    return 0;
}

Solution : Le processus père engendre au total 3 nouveaux processus, ce qui porte le nombre total de processus à 4 (le père initial + 3 enfants).

Explication détaillée (Arborescence) : En langage C, les opérateurs && et || utilisent une évaluation dite "de court-circuit" :

• Pour (A && B), l'expression B n'est évaluée que si A est vrai (différent de 0).
• Pour (A || B), l'expression B n'est évaluée que si A est faux (égal à 0).

Soit le processus initial Père (A) :

1. A exécute le premier fork(). Il crée un enfant B.
   • Pour B, ce fork() retourne 0 (Faux). À cause du &&, B n'évalue pas la suite de l'expression et passe directement au sleep(2).
   • Pour A, ce fork() retourne le PID de B (> 0, Vrai). Puisque la première partie du && est vraie, A doit évaluer la parenthèse (fork() || fork()).
2. A évalue le premier fork() dans la parenthèse. Il crée un enfant C.
   • Pour A, ce fork() retourne le PID de C (> 0, Vrai). À cause du ||, A n'évalue pas la suite, l'expression entière est vraie. Il passe au sleep(2).
   • Pour C, ce fork() retourne 0 (Faux). Puisque la première partie du || est fausse, C doit évaluer le second terme du ||, qui est un autre fork().
3. C exécute le dernier fork(). Il crée un enfant D.
   • C reçoit le PID de D, et D reçoit 0. Les deux terminent l'évaluation et passent au sleep(2).

Arborescence :

A (Père)
 ├── B (Fils de A, issu du premier fork)
 └── C (Fils de A, issu du deuxième fork)
     └── D (Fils de C, issu du troisième fork)

Ordonnancement des processus

Question 3 - Différence entre ordonnancement préemptif et non préemptif

• Ordonnancement non préemptif (sans réquisition) : Le système d'exploitation ne peut pas interrompre un processus en cours d'exécution. Le processus conserve le processeur jusqu'à ce qu'il se termine volontairement ou qu'il se bloque (par exemple, en attendant une opération d'entrée-sortie).
• Ordonnancement préemptif (avec réquisition) : Le système d'exploitation peut interrompre de force un processus en cours d'exécution (par exemple, à l'expiration d'un quantum de temps ou si un processus plus prioritaire arrive), l'obligeant à libérer le processeur et à retourner dans la file d'attente.

Question 4 - Exemples d'algorithmes

• Exemples non préemptifs :
  • FCFS (First-Come, First-Served) ou PAPS (Premier Arrivé, Premier Servi).
  • SJF (Shortest Job First - Le plus court d'abord, dans sa version sans réquisition).
• Exemples préemptifs :
  • Round Robin (Algorithme du tourniquet).
  • SRT (Shortest Remaining Time - Le temps restant le plus court).

Question 5 - Impact du quantum de temps sur le Tourniquet (Round Robin)

Soit q le quantum de temps, s le temps de changement de contexte, et t le temps moyen d'exécution d'un processus avant un blocage (avec t ≫ s et ε ≪ s). Le rendement se calcule par le ratio : (Temps utile) / (Temps total écoulé).

a) Cas où q = ∞ (infini)

• Effet : L'algorithme se comporte comme un simple FCFS (FIFO). Le processus n'est jamais interrompu par l'horloge ; il s'exécute jusqu'à se bloquer (pendant un temps t), après un changement de contexte initial s.
• Rendement : t / (t + s)

b) Cas où q = ε (très petit)

• Effet : Le processeur passe son temps à effectuer des changements de contexte. Le processus progresse très lentement car le temps utile ε est dérisoire face à la surcharge (overhead) système s.
• Rendement : ε / (ε + s). Comme ε est très inférieur à s, ce rendement est proche de 0.

c) Cas où q = s

• Effet : Le processus a droit à un temps d'exécution s qui est exactement égal au temps qu'il faut au système pour faire le changement de contexte s. La moitié du temps machine est gaspillée dans la gestion système.
• Rendement : s / (s + s) = s / 2s = 0.5 (ou 50%).

Système de gestion de fichier

Question 6 - Calcul de la taille d'un disque

Données :

• Nombre de cylindres = 36481
• Pistes par cylindre = 255
• Secteurs moyens par piste = 63
• Taille d'un secteur = 512 octets

Calcul en octets : Taille totale = 36481 × 255 × 63 × 512 = 300 066 439 680 octets.

Calcul en gigaoctets (Go) : Pour convertir des octets en gigaoctets au sens informatique usuel (GibiOctets, puissances de 2), on divise par 1024³. 300 066 439 680 ÷ (1024 × 1024 × 1024) = 300 066 439 680 ÷ 1 073 741 824 ≈ 279,45 Go. (Note : La correction indique 279,45 Gigaoctets, ce qui confirme l'utilisation de la base binaire où 1 Go = 2³⁰ octets, souvent noté Gio de nos jours).

Question 7 - Organisation du système : Rôle des composants

• a) Master Boot Record (MBR) : Situé sur le premier secteur du disque. Son rôle est d'amorcer l'ordinateur. Une fois lancé par le BIOS, le code du MBR cherche la partition marquée comme active, charge le premier bloc de cette partition (le boot block) en mémoire et lui passe la main.
• b) Boot block (Bloc d'amorçage) : Premier bloc de la partition active. Exécuté par le MBR, son programme charge le noyau du système d'exploitation spécifique installé sur cette partition.
• c) Superblock (Superbloc) : Contient toutes les métadonnées et paramètres globaux du système de fichiers de la partition (taille totale, nombre de blocs libres, type de système). Il comporte généralement un "nombre magique" qui permet d'identifier formellement le format du système de fichiers.

Question 8 - Méthodes de gestion des blocs libres

Données du problème :

• Disque = 500 GB.
• Taille d'un bloc = 1 KB.
• Numéro de bloc codé sur 32 bits (4 octets).

Remarque de calcul préalable : Le corrigé source calcule 500 GB comme 500 × 1024 × 1024 KB = 524 288 000 KB. Le disque est donc composé de 524 288 000 blocs de 1 KB.

a) Taille nécessaire avec des listes chaînées Un bloc faisant 1 KB (1024 octets), et un pointeur (numéro de bloc) faisant 4 octets, chaque bloc peut stocker 1024 ÷ 4 = 256 numéros de bloc. Si tous les blocs du disque sont libres, il faut pouvoir stocker 524 288 000 pointeurs. Nombre de blocs nécessaires pour stocker ces pointeurs = 524 288 000 ÷ 256 = 2 048 000 blocs.

b) Taille nécessaire avec une table de bits (bitmap) Dans une table de bits, chaque bloc du disque est représenté par 1 seul bit (0 pour libre, 1 pour occupé). Il faut donc 524 288 000 bits. En octets, cela fait : 524 288 000 ÷ 8 = 65 536 000 octets. En kilo-octets (Ko ou blocs) : 65 536 000 ÷ 1024 = 64 000 Ko (soit 64 000 blocs).

Question 9 - Taille maximale d'un fichier avec un i-node

Nous voulons calculer la taille théorique maximale d'un fichier adressable par cet i-node.

Données de l'architecture :

• Taille d'un secteur/bloc = 512 octets.
• Taille d'un index (pointeur) = 4 octets.
• Données stockées directement dans l'i-node = 200 octets.
• Adressage = 10 directs, 1 simple indirection, 1 double, 1 triple.

Calcul des pointeurs : Le nombre de pointeurs (index) stockables dans un bloc d'indirection est : 512 octets ÷ 4 octets = 128 pointeurs.

Capacité de chaque niveau :

• Direct dans l'i-node : 200 octets.
• Index directs : 10 pointeurs × 512 octets = 5 120 octets.
• Simple indirection : 1 bloc de 128 pointeurs = 128 × 512 = 65 536 octets.
• Double indirection : 128 blocs de 128 pointeurs = 128² × 512 = 16 384 × 512 = 8 388 608 octets.
• Triple indirection : 128 × 128 × 128 pointeurs = 128³ × 512 = 2 097 152 × 512 = 1 073 741 824 octets.

Addition totale : 200 + 5 120 + 65 536 + 8 388 608 + 1 073 741 824 = 1 082 201 288 octets.

Note pédagogique importante : Le corrigé imprimé dans le document source indique un total de 1 082 201 524 octets. C'est une erreur arithmétique de la part du concepteur du corrigé. La somme exacte des éléments formulés dans leur propre expression (200 + 10×512 + 128×512 + 128²×512 + 128³×512) donne bien 1 082 201 288 octets, soit une différence inexpliquée de 236 octets par rapport à la réponse officielle. Retenez la méthode de calcul exacte.

Méthode

Les examens de conception des Systèmes d'Exploitation exigent rigueur et attention aux détails d'implémentation. Voici comment approcher ce type de sujet :

1. Repérez la théorie de base : Une large part des questions teste vos définitions pures (préemptif, MBR, Superblock). Apprenez vos acronymes et le cycle de démarrage d'un ordinateur ; ce sont des points faciles qui ne requièrent aucun calcul.
2. Faites des schémas mentaux pour les appels fork() : Lors des questions de programmation C, dessinez l'arbre généalogique des processus. Soyez particulièrement vigilant face aux opérateurs logiques && et ||. En C, si la première condition d'un && est fausse, la seconde n'est même pas lue (et le sous-processus n'est jamais créé).
3. Maitrisez les unités : Les exercices sur les disques ou l'adressage (comme l'i-node) sont de simples additions et multiplications, mais l'erreur d'unité est très fréquente. Mettez tout au même dénominateur (souvent l'octet) avant d'additionner. Rappelez-vous qu'un secteur ou un bloc est un conteneur : s'il fait 512 octets et qu'une adresse fait 4 octets, il contient 128 adresses, ce qui devient votre multiplicateur d'indirection.
4. Vérifiez vos calculs en cascade : Une erreur à la simple indirection se répercute au carré puis au cube. Prenez le temps de poser la somme calmement, composant par composant, pour obtenir la taille finale.