Systèmes d’Exploitations I Exam

Exercice 1 - Qui suis-je ?

Question 1 - Identifications

Voici les correspondances pour chaque description, accompagnées d'une courte explication pour bien comprendre le concept :

• (a) BIOS (Basic Input/Output System) : Il s'agit du premier programme exécuté lors de la mise sous tension de l'ordinateur. Son rôle est d'initialiser le matériel et de chercher le chargeur d'amorçage.
• (b) MBR (Master Boot Record) : C'est le tout premier secteur (secteur 0) du disque dur, qui contient la table des partitions et le code d'amorçage principal.
• (c) i-node (Index Node) : C'est la structure de données fondamentale des systèmes de fichiers de type Unix. Elle contient les métadonnées d'un fichier (droits, propriétaire) et surtout les pointeurs vers les blocs de données physiques du fichier.
• (d) PCB (Process Control Block) : C'est le bloc de contrôle de processus, une structure maintenue par le système d'exploitation pour stocker tout le contexte d'un processus en cours d'exécution (état, PID, registres, fichiers ouverts).
• (e) fork : C'est l'appel système standard sous Unix/Linux permettant de créer un nouveau processus (le processus enfant) qui est une copie exacte du processus appelant (le processus parent).
• (f) Ordonnancement non préemptif : Dans ce type d'ordonnancement, une fois qu'un processus obtient le processeur, il le conserve jusqu'à ce qu'il se termine ou qu'il se bloque de lui-même. Il ne peut pas être interrompu par l'horloge système pour céder la place.

Exercice 2 - Gestion des processus

Question 2 - Les Fork bombs

(a) Code d'une Fork bomb

Le principe d'une "Fork bomb" est de créer des processus en boucle infinie afin de saturer la table des processus du système d'exploitation.

Voici le code corrigé avec les bibliothèques nécessaires pour qu'il puisse compiler et s'exécuter correctement en langage C.

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

int main(void)
{
    /* Boucle infinie qui duplique le processus indéfiniment */
    for(;;) {
        fork();
    }
    return 0;
}

Note pédagogique : La boucle for(;;) est une boucle infinie classique en C. À chaque itération, fork() double le nombre de processus existants, conduisant à une croissance exponentielle de la charge système.

(b) Prévention d'une Fork bomb

Pour prévenir cette attaque par déni de service, l'administrateur système doit limiter les ressources allouées. La méthode la plus efficace est de limiter le nombre maximum de processus pouvant être exécutés simultanément par un utilisateur ou par un programme. Sous Unix/Linux, cela se fait généralement via la commande ulimit (ex: ulimit -u pour restreindre le nombre de processus utilisateurs) ou via le fichier de configuration /etc/security/limits.conf.

Question 3 - Machine à café intelligente

Le programme doit lancer en cascade trois processus. Le processus initial crée P1 (qui exécute F1). Ensuite, P1 crée P2 (qui exécute F2), et enfin P2 crée P3 (qui exécute F3). L'appel fork() renvoie 0 dans le processus enfant.

Voici le code C complet et exécutable (incluant les bibliothèques et des fonctions factices F1, F2, F3 pour la compilation) :

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

/* Déclaration des fonctions de préparation */
void F1() { /* Verse 20ml d'eau */ }
void F2() { /* Ajoute le café */ }
void F3() { /* Porte à ébullition et sert */ }

int main(void)
{
    pid_t p1, p2, p3;
    
    /* Le processus parent crée P1 */
    if ((p1 = fork()) == 0)
    {
        /* Nous sommes dans P1 */
        F1();
        
        /* P1 crée P2 */
        if ((p2 = fork()) == 0)
        {
            /* Nous sommes dans P2 */
            F2();
            
            /* P2 crée P3 */
            if ((p3 = fork()) == 0)
            {
                /* Nous sommes dans P3 */
                F3();
            }
        }
    }
    
    return 0;
}

Exercice 3 - Ordonnancement

Question 4 - Problème de famine (Starvation)

Parmi les algorithmes cités (FCFS, Tourniquet/Round Robin, Shortest Remaining Time (SRT), Shortest Job First (SJF)), ceux susceptibles de provoquer la famine sont Shortest Job First (SJF) et Shortest Remaining Time (SRT).

Justification : L'algorithme SJF (non-préemptif) favorise systématiquement les processus ayant la durée d'exécution la plus courte. Si un flux continu de "petits" processus arrive dans le système, un processus nécessitant un long temps d'exécution sera indéfiniment repoussé et n'accédera jamais au processeur (c'est la famine). L'algorithme SRT (qui est la version préemptive de SJF) souffre de la même faille : un processus long en cours d'exécution se fera systématiquement interrompre par l'arrivée de nouveaux processus plus courts, menant à une attente infinie.

Les algorithmes FCFS et Round Robin sont équitables et garantissent qu'aucun processus n'attendra indéfiniment.

Question 5 - Diagrammes de Gantt et temps de séjour

Rappel des données de processus :

• P1 : Arrivée = 0 ms, Durée = 3 ms
• P2 : Arrivée = 2 ms, Durée = 6 ms
• P3 : Arrivée = 4 ms, Durée = 4 ms
• P4 : Arrivée = 6 ms, Durée = 5 ms
• P5 : Arrivée = 8 ms, Durée = 2 ms

(a) Diagramme de Gantt - Round Robin (Quantum Q = 4)

La politique Round Robin (Tourniquet) accorde à chaque processus un temps CPU maximum égal au quantum (ici 4 ms). S'il n'a pas terminé, il est remis à la fin de la file d'attente des processus prêts.

Déroulement détaillé :

• t=0: P1 s'exécute pour 3ms (il termine).
• t=3: P2 s'exécute pour son quantum de 4ms. (Reste 2ms). La file contient alors [P3, P4, P2].
• t=7: P3 s'exécute pour 4ms (il termine). La file contient [P4, P2, P5].
• t=11: P4 s'exécute pour son quantum de 4ms. (Reste 1ms). La file contient [P2, P5, P4].
• t=15: P2 s'exécute pour les 2ms restantes (il termine). La file contient [P5, P4].
• t=17: P5 s'exécute pour ses 2ms (il termine). La file contient [P4].
• t=19: P4 s'exécute pour sa milliseconde restante (il termine).

Temps	0 - 3	3 - 7	7 - 11	11 - 15	15 - 17	17 - 19	19 - 20
Processus	P1	P2	P3	P4	P2	P5	P4

(b) Temps de séjour moyen - Round Robin

Le temps de séjour (ou temps de réponse moyen selon la terminologie du corrigé source) correspond à l'intervalle entre la date d'arrivée et la date de fin d'exécution (Fin - Arrivée).

• P1 : termine à 3 ms. Temps de séjour = 3 - 0 = 3 ms.
• P2 : termine à 17 ms. Temps de séjour = 17 - 2 = 15 ms.
• P3 : termine à 11 ms. Temps de séjour = 11 - 4 = 7 ms.
• P4 : termine à 20 ms. Temps de séjour = 20 - 6 = 14 ms.
• P5 : termine à 19 ms. Temps de séjour = 19 - 8 = 11 ms.

Temps moyen = (3 + 15 + 7 + 14 + 11) / 5 = 50 / 5 = 10 ms.

(c) Diagramme de Gantt - Shortest Remaining Time (SRT)

À chaque instant (et particulièrement aux arrivées de processus), l'algorithme SRT alloue le processeur au processus ayant le temps d'exécution restant le plus court.

Déroulement détaillé :

• t=0 : P1 (3ms restantes) s'exécute.
• t=2 : Arrivée de P2 (6ms). P1 a 1ms restante. 1 < 6, P1 continue.
• t=3 : P1 termine. P2 s'exécute.
• t=4 : Arrivée de P3 (4ms). P2 a 5ms restantes. 4 < 5, P3 préempte P2 et s'exécute.
• t=6 : Arrivée de P4 (5ms). P3 a 2ms restantes. 2 < 5, P3 continue.
• t=8 : P3 termine. Arrivée de P5 (2ms). File d'attente : P2(5ms), P4(5ms), P5(2ms). P5 étant le plus court, il s'exécute.
• t=10: P5 termine. File : P2(5ms), P4(5ms). À durée égale, on utilise l'ordre d'arrivée (FCFS). P2 est arrivé avant P4. P2 s'exécute.
• t=15: P2 termine. P4 s'exécute jusqu'à la fin.

Temps	0 - 3	3 - 4	4 - 8	8 - 10	10 - 15	15 - 20
Processus	P1	P2	P3	P5	P2	P4

(d) Temps de séjour moyen - SRT

Calcul du temps de séjour (Fin - Arrivée) :

• P1 : termine à 3 ms. Temps de séjour = 3 - 0 = 3 ms.
• P2 : termine à 15 ms. Temps de séjour = 15 - 2 = 13 ms.
• P3 : termine à 8 ms. Temps de séjour = 8 - 4 = 4 ms.
• P4 : termine à 20 ms. Temps de séjour = 20 - 6 = 14 ms.
• P5 : termine à 10 ms. Temps de séjour = 10 - 8 = 2 ms.

Temps moyen = (3 + 13 + 4 + 14 + 2) / 5 = 36 / 5 = 7.2 ms.

Exercice 4 - Gestion des Fichiers

Question 6 - Disque Dur de 256 TB en FAT 32

Rappelons les unités : 1 TB = 2¹⁰ GB = 2²⁰ MB = 2³⁰ KB = 2⁴⁰ B. Dans une table FAT-32, l'adresse du bloc est codée sur 32 bits, mais 4 bits sont réservés. Il reste donc 28 bits utiles pour adresser les blocs. Le nombre maximum de blocs est donc de 2²⁸.

(a) Faisabilité avec des blocs physiques de 4 KB

Pour trouver la taille maximale gérable, on multiplie le nombre maximal de blocs par la taille d'un bloc.

• Taille maximale = 2²⁸ blocs × 4 KB = 2²⁸ × 2¹² Octets (Bytes)
• Taille maximale = 2⁴⁰ Octets = 1 TB.

Puisque 1 TB est largement inférieur à 256 TB (1 TB <<< 256 TB), Non, l'étudiant ne peut pas formater la totalité de son disque de cette manière.

(b) Faisabilité avec des blocs de 1 MB

Refaisons le calcul avec des blocs de 1 MB (soit 2²⁰ Octets).

• Taille maximale = 2²⁸ blocs × 1 MB = 2²⁸ × 2²⁰ Octets
• Taille maximale = 2⁴⁸ Octets = 256 TB.

Théoriquement oui, en augmentant la taille du bloc à 1 MB, FAT-32 peut couvrir exactement un espace de 256 TB.

(c) Taille de la table FAT en MB

Pour un disque de 256 TB avec des blocs de 1 MB, il faut utiliser la totalité des adresses possibles, soit 2²⁸ blocs. Dans ce sujet d'examen, on considère la taille stricte d'une entrée utile (28 bits) pour calculer l'espace requis (bien qu'en pratique, une entrée occupe 32 bits complets sur le disque). Nous appliquons ici scrupuleusement la formule du corrigé officiel :

• Nombre d'entrées = 2²⁸
• Taille d'une entrée = 28 bits
• Taille totale de la FAT (en bits) = 28 bits × 2²⁸ = 7 516 192 768 bits
• Conversion en MB (1 MB = 2²⁰ Octets = 2²³ bits) = 7 516 192 768 / 8 = 939 524 096 Octets = 896 MB.

(d) Pertinence face à des fichiers de 512 KB

Non, cette solution n'est pas recommandée à cause du phénomène de fragmentation interne (ou gaspillage d'espace). L'unité d'allocation la plus petite est le bloc de 1 MB. Si un fichier fait 512 KB, il occupera un bloc entier de 1 MB. Les 512 KB restants de ce bloc seront définitivement perdus et inutilisables par d'autres fichiers. Cela représente un gaspillage énorme de 50 % de l'espace de stockage pour la taille moyenne de ces fichiers.

(e) Extension vers un "FAT-36"

L'étudiant souhaite conserver une taille de bloc de 4 KB (2¹² Octets) pour un disque de 256 TB (2⁴⁸ Octets). Il faut calculer le nombre de blocs nécessaires pour couvrir cet espace :

• Nombre de blocs = Capacité du disque ÷ Taille d'un bloc = 2⁴⁸ ÷ 2¹² = 2³⁶ blocs. Pour adresser 2³⁶ blocs, l'adresse doit faire au minimum 36 bits. L'étudiant devrait donc créer un système "FAT-36".

Question 7 - Les possibilités de l'i-node

Données :

• Taille d'un bloc de données = 512 octets.
• Taille d'une adresse de bloc = 4 octets.
• Structure : 10 adresses directes, 1 pointeur indirect simple, 1 pointeur indirect double.

Nombre d'adresses que l'on peut stocker dans un bloc pointeur = Taille du bloc / Taille d'une adresse = 512 / 4 = 128 adresses.

(a) Taille minimale d'un fichier non vide

Dès qu'un fichier contient la moindre donnée, le système lui alloue un bloc entier. La taille minimale occupée sur le disque pour un fichier non vide est donc de 1 bloc, soit 512 octets.

(b) Taille maximale d'un fichier

Il faut additionner le nombre de blocs couverts par tous les niveaux d'indirection :

• 10 adresses directes pointent vers 10 blocs.
• 1 pointeur indirect simple pointe vers un bloc contenant 128 adresses directes, couvrant 128 blocs.
• 1 pointeur indirect double pointe vers un bloc contenant 128 pointeurs indirects simples, chacun pointant vers 128 adresses directes. Cela couvre 128 × 128 = 16 384 blocs.

Le nombre total de blocs accessibles est : 10 + 128 + 16 384 = 16 522 blocs. En multipliant par la taille du bloc, la taille maximale du fichier est de : 16 522 × 512 = 8 459 264 octets (soit un peu plus de 8 MB).

Méthode

Pour réussir ce type d'examen sur les systèmes d'exploitation :

1. Simulations d'ordonnancement : Ne tentez pas de calculer les temps de séjour de tête. Dessinez toujours un brouillon du diagramme de Gantt en gardant une trace claire de la "file d'attente des processus prêts" à chaque instant critique (notamment chaque arrivée d'un nouveau processus et chaque fin d'exécution).
2. Calculs de taille de fichiers et disques : Maîtrisez parfaitement les puissances de 2. L'astuce est de toujours tout convertir en puissances de 2 (par exemple 4 KB = 2² × 2¹⁰ = 2¹² octets) avant de faire des divisions ou des multiplications. Cela limite les erreurs de calcul mental.
3. Appels systèmes C (fork) : Rappelez-vous toujours de la condition essentielle du fork() : la fonction renvoie 0 dans le code du processus enfant et le PID de l'enfant dans le processus parent. C'est en imbriquant ou en juxtaposant les if (fork() == 0) que vous contrôlez l'arbre généalogique de vos processus.