SystŁmes d’Exploitation I - Examen Mai 2018

Gestion des Processus (6 points)

Question 1 - Qui suis-je ?

Voici les concepts et appels système correspondants à chaque définition :

• (a) Je suis un processus qui s'est terminé mais son père n'a pas encore lu son code de retour. Réponse : Processus Zombie
• (b) Je suis un processus dont le père s'est terminé avant lui. Réponse : Processus Orphelin
• (c) Je suis un appel système qui permet de créer un processus. Réponse : fork()
• (d) Je suis un appel système qui affiche le PID du processus père. Réponse : getppid()

Question 2 - Affichage d'un processus

Le code affiche : value = 5.

Explication : Lors de l'appel à fork(), le système d'exploitation crée un processus fils qui est une copie exacte du processus père, mais avec un espace mémoire distinct (mécanisme de Copy-On-Write). L'incrémentation value += 15 n'a lieu que dans la copie mémoire du processus fils. Le processus père, qui attend la fin de son fils grâce à wait(NULL), conserve sa propre variable value intacte à 5.

Note sur le code source : Le code fourni dans le sujet nécessite les bibliothèques <unistd.h>, <sys/wait.h> et <stdio.h> pour compiler correctement, mais la logique d'exécution reste celle décrite ci-dessus.

Question 3 - Arborescence des processus

Pour générer une arborescence linéaire stricte de type P1 → P2 → P3 → P4 → P5, chaque processus père doit créer exactement un processus fils, puis s'arrêter d'en créer d'autres.

Voici deux méthodes valides et corrigées pour obtenir ce résultat :

Méthode 1 : Utilisation de conditions imbriquées

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

int main() {
    // Chaque if (fork() == 0) s'exécute uniquement dans le processus fils
    if (fork() == 0) {
        if (fork() == 0) {
            if (fork() == 0) {
                if (fork() == 0) {
                    // Le processus P5 arrive ici
                }
            }
        }
    }
    
    // Tous les processus attendent leur enfant potentiel puis affichent leur identité
    wait(NULL);
    printf("%d --> %d\n", getppid(), getpid());
    
    return 0;
}

Méthode 2 : Utilisation d'une boucle

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

int main() {
    int i;
    for (i = 0; i < 4; i++) {
        // fork() renvoie le PID du fils (>0) au père, et 0 au fils.
        // Si c'est le père, la condition est vraie (différente de 0) et il quitte la boucle.
        // Le fils obtient 0 et continue à l'itération suivante pour forker à son tour.
        if (fork()) {
            break;
        }
    }
    
    wait(NULL);
    printf("%d --> %d\n", getppid(), getpid());
    
    return 0;
}

Ordonnancement des Processus (7 points)

Question 4 - Qui suis-je ?

• (a) Je suis la version avec réquisition de l'algorithme d'ordonnancement SJF. Réponse : SRT (Shortest Remaining Time)
• (b) Je suis la différence entre le temps de la première exécution et le temps d'entrée dans le système. Réponse : Temps d'attente (Note : La source utilise ce terme, bien que cette définition corresponde techniquement au "temps de réponse" dans d'autres littératures).
• (c) Je suis la différence entre le temps de terminaison et le temps d'entrée dans le système. Réponse : Temps de séjour (Turnaround time)
• (d) Je suis la version avec réquisition de l'algorithme d'ordonnancement PAPS (FCFS). Réponse : Round Robin ou Tourniquet

Question 5 - Ordonnancement Round Robin vs. SJF

Les processus ont les caractéristiques suivantes :

• P1 : Arrivée 0, Exécution 3
• P2 : Arrivée 2, Exécution 6
• P3 : Arrivée 4, Exécution 4
• P4 : Arrivée 6, Exécution 5
• P5 : Arrivée 8, Exécution 2

Question 5(a) - Diagramme de GANTT pour SJF

L'algorithme SJF (Shortest Job First) utilisé ici est sans réquisition. Une fois qu'un processus commence, il s'exécute jusqu'à la fin. À chaque fin d'exécution, on choisit le processus présent dans la file d'attente ayant le temps d'exécution le plus court.

Diagramme de GANTT :

P1	P2	P5	P3	P4
0 → 3	3 → 9	9 → 11	11 → 15	15 → 20

Question 5(b) - Diagramme de GANTT pour Round Robin

L'algorithme Round Robin alloue un quantum de temps maximum à chaque processus (ici 2 unités). Si le processus n'est pas terminé, il est replacé à la fin de la file d'attente.

Diagramme de GANTT :

P1	P2	P1	P3	P2	P4	P3	P5	P2	P4
0→2	2→4	4→5	5→7	7→9	9→11	11→13	13→15	15→17	17→20

(Note : À t=4, P1 se termine en n'utilisant qu'une unité sur son quantum. La fin de ce chronogramme montre que P4 termine son exécution avec un bloc de 3 unités, indiquant que son dernier passage couvre la période restante).

Question 5(c) - Famine

Réponse : L'ordonnancement SJF peut entraîner l'apparition de la famine. Justification : Puisque le SJF classique (sans réquisition) sélectionne toujours le processus le plus court, un processus très long pourrait attendre indéfiniment si des processus plus courts continuent d'arriver dans le système de manière ininterrompue.

Gestion des Fichiers (7 points)

Question 6 - Qui suis-je ?

• (a) Je suis une table stockée à la fin du MBR, je contiens des informations sur la subdivision logique du disque dur... Réponse : Table de partitions
• (b) Je suis la plus petite unité de stockage d'un système de fichiers... Réponse : Blocs (ou clusters/unités d'allocation)
• (c) Je suis une structure de donnée associée à un seul fichier. Je contiens essentiellement les adresses des blocs... Réponse : i-node
• (d) Je suis une structure de donnée qui contient les adresses des blocs de données... en utilisant une liste chaînée indexée. Réponse : FAT (File Allocation Table)

Question 7 - FAT pour un disque de 1 To

Données initiales :

• Taille du disque = 1 To = 2⁴⁰ octets.
• Système FAT-32 (le sujet précise qu'une entrée FAT-32 utilise ici 28 bits).
• Nombre maximum d'unités d'allocation (nombre d'entrées possibles) = 2²⁸.

Question 7(a) - Taille minimale de bloc physique

Pour pouvoir adresser l'ensemble des 2⁴⁰ octets avec un maximum de 2²⁸ blocs, il faut déterminer la taille de chaque bloc :

• Taille d'un bloc physique = (Taille du disque) ÷ (Nombre d'entrées FAT)
• Taille = 2⁴⁰ ÷ 2²⁸ = 2¹² octets. Sachant que 1 Koctet = 2¹⁰ octets :
• 2¹² octets = 4 Koctets.

Réponse : La taille minimale d'un bloc physique est de 4 Koctets.

Question 7(b) - Taille minimale d'un fichier

Dans un système de fichiers organisé en blocs, la plus petite unité d'espace pouvant être allouée à un fichier est un bloc entier, quelle que soit la taille réelle de ses données.

Réponse : La taille minimale allouée à un fichier est de 1 bloc physique, soit 4 Koctets.

Question 7(c) - Nombre de blocs nécessaires pour stocker la FAT

Il faut calculer la taille totale de la table FAT en bits, puis déterminer combien de blocs physiques sont requis pour la stocker.

1. La taille de la table FAT = (Nombre d'entrées) × (Taille d'une entrée) = 2²⁸ × 28 bits.
2. La taille d'un bloc physique de 4 Ko en bits = 4 × 2¹⁰ octets × 8 bits/octet = 2² × 2¹⁰ × 2³ = 2¹⁵ bits.
3. Nombre de blocs nécessaires = (2²⁸ × 28) ÷ 2¹⁵ = 28 × 2¹³ blocs.

Réponse : Il faut 28 × 2¹³ blocs pour stocker la table FAT sur le disque.

Question 7(d) - Taille de la table de bits (bitmap)

Dans une table de bits, 1 bloc de données est représenté par 1 bit.

1. Le disque contient 2²⁸ blocs, la table de bits nécessitera donc 2²⁸ bits.
2. Sachant qu'un bloc fait 2¹⁵ bits (calculé précédemment) :
3. Taille de la table en blocs = 2²⁸ ÷ 2¹⁵ = 2¹³ blocs.

Réponse : La taille de la table de bits est de 2¹³ blocs.

Question 7(e) - Problème du formatage en FAT-16

Si on formate ce disque en FAT-16 avec des blocs de 32 Koctets (soit 2¹⁵ octets) :

1. Le système FAT-16 ne peut adresser que 2¹⁶ blocs au maximum.
2. La taille maximale gérée par le système sera : (Nombre de blocs) × (Taille d'un bloc) = 2¹⁶ × 2¹⁵ octets = 2³¹ octets.
3. 2³¹ octets équivaut à 2 Go (Gigaoctets).

Réponse : Il est fortement déconseillé de le faire car la capacité maximale adressable serait de 2 Go. Cette capacité (2 Go) est infiniment plus petite que la taille réelle du disque (1 To). L'immense majorité de l'espace de stockage du disque dur deviendrait inutilisable.

Méthode

Face à ce type d'épreuve associant gestion des processus et de la mémoire, voici l'approche à privilégier :

1. Arbres et création de processus : Les questions impliquant fork() requièrent une trace manuelle. Dessinez l'arbre des processus sur un brouillon. Rappelez-vous toujours que le code qui suit un fork() sera exécuté par le père ET par le fils. Séparez bien le comportement du père (le retour est > 0) et celui du fils (le retour est 0).
2. Chronogrammes (GANTT) : Soyez très vigilants sur les dates d'arrivée. Une erreur fréquente est de planifier un processus court qui n'est pas encore entré dans la file d'attente. Mettez à jour une petite file d'attente à côté de votre chronogramme à chaque avancement du temps.
3. Calculs d'espace disque : Maîtrisez parfaitement les puissances de 2. Convertissez toujours vos unités logiquement : Kilo = 2¹⁰, Méga = 2²⁰, Giga = 2³⁰, Téra = 2⁴⁰. Pensez également à convertir les octets en bits (en multipliant par 8, soit 2³) lorsque vous évaluez l'espace occupé par des structures de contrôle (comme les entrées de la table FAT). Laissez les résultats sous forme de puissances de 2 pour minimiser le risque d'erreur de calcul.