Systèmes d'Exploitations I

Question 1 - Qui suis-je ?

(a) Je suis le premier programme qui est lancé à la mise sous tension de l'ordinateur. La réponse est le BIOS (Basic Input/Output System). C'est le firmware responsable de l'initialisation du matériel et du lancement du chargeur d'amorçage.

(b) Je suis le secteur 0 du disque dur. La réponse est le MBR (Master Boot Record). C'est le tout premier secteur du disque qui contient la table de partitionnement et le code d'amorçage.

(c) Je suis une structure de donnée associée à un seul fichier. Je contient essentiellement les adresses des blocs de données du fichier. La réponse est l'i-node (index-node). Dans les systèmes de type Unix, cette structure contient les métadonnées du fichier et les pointeurs vers ses blocs de données, mais ne contient pas le nom du fichier.

(d) Je suis une structure de donnée contenant toutes les informations relatives à un processus donné (PID, état, fichiers ouverts,...). La réponse est le PCB (Process Control Block). C'est le bloc de contrôle de processus utilisé par le système d'exploitation pour gérer et suivre le contexte d'exécution d'un processus.

(e) Je suis un appel système qui permet de créer un processus. La réponse est fork(). Cet appel système sous Unix crée un processus enfant qui est une copie exacte du processus parent.

(f) Je suis un type d'ordonnancement qui ne réagit pas aux interruptions d'horloge. La réponse est un ordonnancement non préemptif (ou coopératif). Dans ce modèle, un processus garde le processeur jusqu'à ce qu'il se termine ou qu'il se bloque volontairement.

Question 2 - Gestion des processus

Sous-question 2.1 - Les Fork bombs

(a) Proposer un code de Fork bombs. La source originale présente un code dont la mise en forme a été altérée par l'extraction. Pour qu'une fork bomb soit effective et compilable en langage C, elle doit invoquer l'appel système fork() dans une boucle infinie. Voici le code corrigé, incluant l'en-tête nécessaire pour que le code soit exécutable.

#include <unistd.h>

int main(void) {
    for (;;) {
        fork();
    }
    return 0;
}

(b) Proposer une méthode pour prévenir l'exécution d'une telle bombe sur votre système d'exploitation. Pour empêcher les effets dévastateurs d'une fork bomb, l'administrateur système doit imposer une limite stricte sur le nombre de processus pouvant être exécutés simultanément par un utilisateur ou rattachés à un programme. Sous Unix/Linux, cela se fait typiquement via la commande ulimit (ex: ulimit -u pour limiter le nombre de processus utilisateurs) ou via le fichier de configuration /etc/security/limits.conf.

Sous-question 2.2 - Machine à café intelligente

On souhaite écrire l'architecture d'un programme qui exécute trois processus en cascade : P1 crée P2, et P2 crée P3. Chaque processus lance une fonction spécifique (F1, F2, F3). Afin de rendre le code valide et exécutable, j'ai ajouté les inclusions des bibliothèques nécessaires (unistd.h, sys/types.h) ainsi que les déclarations vides des fonctions F1, F2 et F3. Le cœur de la logique reste identique à la solution attendue : on exploite le fait que fork() retourne 0 au processus enfant pour imbriquer les exécutions.

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

/* Déclarations des fonctions pour assurer la compilation */
void F1(void) {}
void F2(void) {}
void F3(void) {}

int main(void) {
    pid_t p1, p2, p3;

    /* Le parent crée P1. Si nous sommes dans P1 (retour = 0), on exécute sa logique */
    if ((p1 = fork()) == 0) {
        F1();
        
        /* P1 crée P2. Si nous sommes dans P2 (retour = 0) */
        if ((p2 = fork()) == 0) {
            F2();
            
            /* P2 crée P3. Si nous sommes dans P3 (retour = 0) */
            if ((p3 = fork()) == 0) {
                F3();
            }
        }
    }
    return 0;
}

Question 3 - Ordonnancement

Sous-question 3.1 - La famine (Question 4 du sujet)

(a) Parmi FCFS(PAPS), Tourniquet(Round Robin), Shortest Remaining Time (SRT), Shortest Job First (SJF), quels algorithmes provoquent la famine ? La famine survient lorsqu'un processus prêt à s'exécuter n'obtient jamais d'accès au processeur.

• SJF (Shortest Job First) : C'est un algorithme non préemptif qui sélectionne le processus le plus court. Un long processus peut subir une famine si de nouveaux petits processus arrivent continuellement.
• SRT (Shortest Remaining Time) : C'est la version préemptive de SJF. Il est également sujet à la famine. Si des processus ayant un temps d'exécution restant très court arrivent en permanence, un processus plus long sera indéfiniment mis en attente.

Les algorithmes FCFS (Premier arrivé, premier servi) et Tourniquet (Round Robin) sont basés sur l'ordre d'arrivée ou répartissent le temps équitablement, garantissant qu'aucune famine ne puisse survenir (à condition qu'aucun processus ne boucle à l'infini dans le cas de FCFS).

Sous-question 3.2 - Cas d'un système mono-processeur (Question 5 du sujet)

Voici les données initiales du problème :

Processus	Date d'arrivée (ms)	Durée d'exécution (ms)
P1	0	3
P2	2	6
P3	4	4
P4	6	5
P5	8	2

(a) Diagramme de Gantt avec la politique Round Robin (quantum Q=4) Les processus sont traités selon l'ordre d'arrivée, et s'ils ne terminent pas dans leur quantum de 4 ms, ils sont replacés à la fin de la file d'attente.

Chronologie des événements :

• t=0 : P1 arrive et s'exécute pendant 3 ms (terminé à t=3).
• t=2 : P2 arrive en file.
• t=3 : P2 s'exécute pour 4 ms. Il restera 2 ms à faire.
• t=4 : P3 arrive en file.
• t=6 : P4 arrive en file.
• t=7 : Le quantum de P2 expire. P2 est replacé en file. La file est [P3, P4, P2]. P3 s'exécute pour 4 ms (terminé à t=11).
• t=8 : P5 arrive. La file devient [P4, P2, P5].
• t=11 : P4 s'exécute pour 4 ms. Il restera 1 ms à faire.
• t=15 : Le quantum de P4 expire. La file devient [P2, P5, P4]. P2 s'exécute pour ses 2 ms restants (terminé à t=17).
• t=17 : P5 s'exécute pour 2 ms (terminé à t=19).
• t=19 : P4 s'exécute pour sa dernière ms (terminé à t=20).

Période (ms)	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 réponse moyen pour Round Robin (Q=4) Le temps de réponse (ou temps de séjour) se calcule par : Temps de fin - Date d'arrivée.

• P1 : 3 - 0 = 3 ms
• P2 : 17 - 2 = 15 ms
• P3 : 11 - 4 = 7 ms
• P4 : 20 - 6 = 14 ms
• P5 : 19 - 8 = 11 ms
• Moyenne = (3 + 15 + 7 + 14 + 11) ÷ 5 = 50 ÷ 5 = 10 ms.

(c) Diagramme de Gantt avec la politique Shortest Remaining Time (SRT) À chaque instant, le processus ayant le plus petit temps d'exécution restant obtient le processeur (préemptif).

Chronologie des événements :

• t=0 : P1 (reste 3). S'exécute.
• t=2 : P2 arrive (reste 6). P1 continue (il lui reste 1 < 6).
• t=3 : P1 terminé. P2 s'exécute.
• t=4 : P3 arrive (reste 4). Le temps restant pour P2 est de 5 ms. Puisque 4 < 5, P3 préempte P2.
• t=6 : P4 arrive (reste 5). P3 continue (reste 2).
• t=8 : P3 terminé. P5 arrive (reste 2). Les processus en attente sont P5 (2), P2 (5), P4 (5). P5 s'exécute.
• t=10 : P5 terminé. Reste P2 (5) et P4 (5). À égalité, on utilise l'ordre d'arrivée (FCFS), donc P2 s'exécute.
• t=15 : P2 terminé. P4 s'exécute.
• t=20 : P4 terminé.

Période (ms)	0 - 3	3 - 4	4 - 8	8 - 10	10 - 15	15 - 20
Processus	P1	P2	P3	P5	P2	P4

(d) Temps de réponse moyen pour Shortest Remaining Time (SRT)

• P1 : 3 - 0 = 3 ms
• P2 : 15 - 2 = 13 ms
• P3 : 8 - 4 = 4 ms
• P4 : 20 - 6 = 14 ms
• P5 : 10 - 8 = 2 ms
• Moyenne = (3 + 13 + 4 + 14 + 2) ÷ 5 = 36 ÷ 5 = 7.2 ms.

Question 4 - Gestion des Fichiers

Sous-question 4.1 - Disque Dur de 256 TB en FAT 32

(a) Expliquer pourquoi il ne peut pas formater son disque en FAT-32 avec des tailles de bloc de 4KB ? Le système de fichiers FAT-32 utilise 28 bits réels pour adresser ses blocs (clusters). Le nombre maximum de blocs est donc de 2²⁸. Avec des blocs de 4 KB (qui valent 2¹² octets), la taille maximale adressable est : Taille Max = 2²⁸ blocs × 2¹² octets/bloc = 2⁴⁰ octets. Sachant que 2⁴⁰ octets équivalent exactement à 1 TB. Or, 1 TB est largement inférieur à la capacité du disque qui est de 256 TB.

(b) En augmentant la taille du bloc à 1MB, peut-il formater son disque dur en FAT-32 ? Oui. Avec des blocs de 1 MB (qui valent 2²⁰ octets) : Taille Max = 2²⁸ blocs × 2²⁰ octets/bloc = 2⁴⁸ octets. Sachant que 1 TB = 2⁴⁰ octets, 2⁴⁸ = 2⁸ × 2⁴⁰ = 256 TB. La capacité maximale adressable correspond exactement à la taille du disque.

(c) Quelle est la taille de la table FAT dans ce cas de figure ? Le nombre total de blocs nécessaires pour 256 TB est de : 2⁴⁸ ÷ 2²⁰ = 2²⁸ blocs. Selon le postulat de la source, la taille utile d'une entrée dans la table est de 28 bits (bien que la structure de données prenne souvent 32 bits en espace physique sur disque, nous appliquons ici scrupuleusement la méthode de calcul du corrigé basée sur les bits utiles) : Taille totale en bits = 28 bits × 2²⁸ = 7 516 192 768 bits. Taille totale en octets = 7 516 192 768 ÷ 8 = 939 524 096 octets. Taille totale en MB = 939 524 096 ÷ 1 048 576 = 896 MB.

(d) En sachant que la taille moyenne des fichiers est de 512KB, auriez-vous adopté la solution précédente ? Non. Le choix d'une taille de bloc de 1 MB entraîne une fragmentation interne énorme. Chaque fichier de 512 KB occupera un bloc entier de 1 MB, gaspillant ainsi la moitié de l'espace (512 KB) sur chaque bloc alloué.

(e) Taille minimale de l'adresse en bit en modifiant FAT-32 avec des blocs de 4KB ? Nous devons adresser 256 TB de données avec des blocs de 4 KB. Nombre de blocs = Capacité totale ÷ Taille d'un bloc = 2⁴⁸ octets ÷ 2¹² octets/bloc = 2³⁶ blocs. Pour adresser 2³⁶ blocs de manière unique, l'adresse du bloc doit avoir une taille minimale de 36 bits (créant ainsi un théorique FAT-36).

Sous-question 4.2 - Les possibilités de l'i-node

Données :

• Taille d'un bloc : 512 octets
• Taille d'un pointeur (index) : 4 octets
• Nombre de pointeurs par bloc : 512 ÷ 4 = 128 pointeurs.

Un i-node dispose de : 10 pointeurs directs, 1 pointeur indirect simple, 1 pointeur indirect double, 1 pointeur indirect triple.

(a) Taille minimale d'un fichier ? (en blocs et en octets) Un fichier nouvellement créé et contenant de la donnée occupe au minimum 1 bloc d'espace sur le disque. Taille = 1 bloc, soit 512 octets. (Un fichier totalement vide de 0 octet et occupant 0 bloc de données est théoriquement possible, mais dès la première écriture le palier monte à 512 octets, ce qu'attend l'examinateur).

(b) Taille maximale d'un fichier ? (en blocs et en octets) Calculons le nombre maximal de blocs de données adressables :

• Pointeurs directs : 10 blocs
• Indirect simple : 128 blocs
• Indirect double : 128 × 128 = 16 384 blocs
• Indirect triple : 128 × 128 × 128 = 2 097 152 blocs
• Nombre total de blocs = 10 + 128 + 16 384 + 2 097 152 = 2 113 674 blocs.

Calcul en octets : Taille maximale = 2 113 674 blocs × 512 octets/bloc = 1 082 201 088 octets. Note de correction : le sujet source indique une valeur de 1 082 201 087 octets. Mathématiquement, 2 113 674 multiplié par 512 équivaut très exactement à 1 082 201 088. La valeur fournie par la source (qui correspond à la taille exacte moins 1) représente l'offset maximal (l'adresse du dernier octet accessible si l'on commence à compter à 0). Néanmoins, le volume total physique (la taille) est bel et bien de 1 082 201 088 octets.

Méthode

Pour aborder efficacement un examen de Systèmes d'Exploitation :

1. Connaître les ordres de grandeur : Maîtrisez parfaitement les conversions de puissances de 2 (Kilo, Méga, Giga, Téra). La quasi-totalité des calculs de gestion mémoire et disque reposent sur des fractions ou multiplications de puissances de 2. Appuyez-vous sur les lois des exposants (ex: 2^A × 2^B = 2^(A+B)) pour calculer mentalement plus vite.
2. Dessiner avant de calculer : Pour tout exercice d'ordonnancement, dessinez toujours le diagramme de Gantt en marquant explicitement le temps restant du processus en cours à chaque nouvelle arrivée. Ne calculez les moyennes de temps de séjour qu'une fois le diagramme vérifié et validé, car une seule erreur de préemption en début de chaîne faussera toutes les moyennes.
3. Appels systèmes Unix : Mémorisez la sémantique de retour des processus comme fork() (0 pour l'enfant, le PID pour le parent). Cela permet de tracer facilement l'arbre généalogique produit par des boucles ou des structures conditionnelles imbriquées. Tracez un schéma arborescent sur votre brouillon si le code est complexe.