Exam on Operating Systems I

Question 1 - Commandes système (Qui suis-je ?)

Dans cette section, nous identifions les commandes Linux classiques d'administration et de gestion des processus. Note : le sujet original contient quelques erreurs typographiques sur le nom des commandes (lsmode, insmode), que nous avons corrigées ici avec leur orthographe exacte pour qu'elles fonctionnent dans votre terminal.

(a) Je suis une commande qui affiche une liste de tous les modules intégrés dans le noyau : lsmod (le sujet indique lsmode, mais la commande correcte sous Linux est lsmod). (b) Je suis une commande qui affiche des informations sur un module : modinfo. (c) Je suis une commande qui permet de charger un module : insmod (ou modprobe -a). (d) Je suis une commande qui permet de décharger un module : rmmod (ou modprobe -r). (e) Je construit automatiquement des fichiers ou des bibliothèques à partir de code source : make. (f) Je suis une commande qui affiche les messages de debug du noyau : dmesg. (g) Je suis une commande qui liste les processus actifs : ps aux. (h) Je suis une commande qui affiche le PID d'un processus : pidof. (i) Je suis une commande qui envoie un signal au processus : kill. (j) Je suis une commande qui affiche les processus en cours d'exécution sous forme d'arbre : pstree.

Question 2 - Gestion des Processus

Le code fourni dans le sujet a subi des problèmes de formatage. Voici le code C corrigé et rendu exécutable, incluant les bibliothèques standard nécessaires pour fork, getpid et printf :

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

int main(void) {
    pid_t p1, p2;
    p1 = fork();
    p2 = fork();
    if ((p1 - p2) > 0) {
        fork();
    }
    printf("Je suis %d, p1=%d, p2=%d\n", getpid(), p1, p2);
    return 0;
}

Règle importante donnée par l'énoncé : les PID sont strictement croissants. Si un processus crée un fils, le PID du fils (m) est supérieur à celui du père (n), soit m > n.

Question 2.a - Nombre et arborescence des processus créés

Pour déterminer l'arborescence, il faut tracer l'exécution séquentiellement. Appelons le processus initial P1.

1. Premier fork : P1 exécute p1 = fork().
   • P1 crée P2. Dans P1, p1 prend la valeur PID-P2. Dans P2, p1 prend la valeur 0.
2. Deuxième fork : P1 et P2 exécutent p2 = fork().
   • P1 crée P3. Dans P1, p2 prend la valeur PID-P3.
   • P2 crée P4. Dans P2, p2 prend la valeur PID-P4.
3. Condition if ((p1 - p2) > 0) :
   • Pour P1 : p1 vaut PID-P2 et p2 vaut PID-P3. Puisque les PID sont croissants, PID-P2 < PID-P3. La soustraction donne un résultat négatif. Condition fausse.
   • Pour P2 : p1 vaut 0 et p2 vaut PID-P4. 0 - PID-P4 est négatif. Condition fausse.
   • Pour P3 : P3 est le fils créé par P1 lors du 2ème fork. Il hérite de la variable p1 de P1 (donc p1 = PID-P2). La valeur de retour de son propre fork() est 0, donc p2 = 0. La condition devient (PID-P2 - 0) > 0. C'est vrai !
   • Pour P4 : P4 est le fils créé par P2 au 2ème fork. Il hérite de p1 = 0. Son p2 vaut 0. (0 - 0) n'est pas supérieur à 0. Condition fausse.
4. Troisième fork :
   • Seul P3 entre dans le bloc "if" et exécute ce troisième fork().
   • P3 crée P5. Dans P3, ce fork renvoie le PID de P5 (bien qu'il ne soit stocké dans aucune variable). Dans P5, les variables héritées de P3 restent p1 = PID-P2 et p2 = 0.

Il y a donc 5 processus au total. L'arborescence est la suivante :

P1 ├──> P2 │ └──> P4 └──> P3 └──> P5

Question 2.b - Affichage à l'écran pour chaque processus

En reprenant les valeurs de p1 et p2 calculées à l'étape précédente pour chaque processus qui arrive à l'instruction printf :

• P1 : possède les PID de ses deux fils directs. Affichage : Je suis PID-P1, p1=PID-P2, p2=PID-P3
• P2 : a reçu 0 du premier fork, et a stocké le PID de son fils P4. Affichage : Je suis PID-P2, p1=0, p2=PID-P4
• P3 : a hérité la valeur p1 de P1 (PID-P2), et a reçu 0 au moment de sa création (2ème fork). Le 3ème fork ne modifie pas la variable p2. Affichage : Je suis PID-P3, p1=PID-P2, p2=0
• P4 : a hérité p1 = 0 de P2, et a reçu 0 à sa création. Affichage : Je suis PID-P4, p1=0, p2=0
• P5 : a été créé par P3. Il hérite des variables de P3, à savoir p1 = PID-P2 et p2 = 0. Affichage : Je suis PID-P5, p1=PID-P2, p2=0

Question 3 - Boucle while et fork

Voici le code réparé pour cette question :

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

int main(void) {
    pid_t p=1;
    while (p>0) {
        p = fork();
    }
    printf("Je suis %d\n", getpid());
    return 0;
}

Résultat de l'exécution : Le processus père initialise la variable p à 1. Puisque 1 > 0, il entre dans la boucle while et exécute fork(). Pour le père, fork() renvoie le PID du fils créé (un entier strictement positif). La condition p > 0 reste donc vraie en permanence pour le père. Le père génère une infinité de fils (comportement de "fork bomb" qui finira par saturer la table des processus du système). Pour chaque processus fils créé, la fonction fork() renvoie 0. La condition p > 0 devient fausse immédiatement. Chaque fils sort donc de la boucle, affiche "Je suis [Son PID]" grâce au printf, puis se termine.

Question 4 - Arborescence avec conditions imbriquées

Code C réparé :

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

int main(void) {
    pid_t p1, p2, p3, p4;
    int i;
    
    if ((p1 = fork()) == 0) {
        if ((p2 = fork()) == 0) {
            if ((p3 = fork()) == 0) {
                if ((p4 = fork()) == 0) {
                    printf("Alea jacta est\n");
                }
            }
        }
    }
    return 0;
}

Dessin de l'arborescence : Dans cette structure, un processus n'entre dans le bloc if que si la valeur de retour de fork() est 0, c'est-à-dire seulement s'il est le processus enfant nouvellement créé.

• P1 fait un fork (crée P2). P1 reçoit PID-P2, n'entre pas dans le if et se termine.
• P2 reçoit 0, entre dans le if, fait un fork (crée P3). P2 n'entre pas dans le deuxième if et se termine.
• P3 reçoit 0, entre, crée P4, puis se termine.
• P4 reçoit 0, entre, crée P5, puis se termine.
• P5 reçoit 0, entre, affiche le texte, et se termine.

C'est une création en cascade (chaque fils crée un unique fils à son tour). L'arborescence est strictement linéaire : P1 -> P2 -> P3 -> P4 -> P5

Question 5 - Ordonnancement des Processus (SJF)

Les processus arrivent tous à l'instant 0 dans l'ordre P1, P2, P3, P4, P5. Leurs durées respectives sont : P1(10), P2(1), P3(2), P4(1), P5(5). L'algorithme est SJF (Shortest Job First - le plus court d'abord). Le processus ayant le temps d'exécution le plus court est choisi en premier. En cas d'égalité (même durée), le sujet précise que l'ordonnanceur choisit le processus avec le plus petit identifiant (PID).

Tions les processus par ordre de priorité SJF :

1. P2 (durée 1, PID le plus petit parmi ceux de durée 1)
2. P4 (durée 1)
3. P3 (durée 2)
4. P5 (durée 5)
5. P1 (durée 10)

Question 5.a - Diagramme de GANTT

L'exécution n'est pas préemptive, un processus lancé s'exécute jusqu'à sa fin.

Temps	0 - 1	1 - 2	2 - 4	4 - 9	9 - 19
Processus actif	P2	P4	P3	P5	P1

Question 5.b - Temps de séjour moyen

Le temps de séjour (Turnaround Time) est le délai entre la soumission du processus (instant 0 pour tous) et sa date de fin d'exécution.

• Date de fin P2 : 1 ms
• Date de fin P4 : 2 ms
• Date de fin P3 : 4 ms
• Date de fin P5 : 9 ms
• Date de fin P1 : 19 ms

Moyenne = (1 + 2 + 4 + 9 + 19) ÷ 5 = 35 ÷ 5 = 7 ms

Question 5.c - Temps d'attente moyen

Le temps d'attente est le temps passé par le processus dans la file des prêts (Date de début - Date d'arrivée).

• Attente P2 : 0 ms
• Attente P4 : 1 ms
• Attente P3 : 2 ms
• Attente P5 : 4 ms
• Attente P1 : 9 ms

Moyenne = (0 + 1 + 2 + 4 + 9) ÷ 5 = 16 ÷ 5 = 3.2 ms

Question 6 - Efficacité d'utilisation du CPU

La formule de l'efficacité ρ est donnée par : ρ = τ ÷ (τ + σ) où τ est le temps d'exécution utile et σ le coût de la commutation de contexte.

Question 6.a - Cas où σ >> τ

Si le temps de commutation (σ) est infiniment plus grand que le temps de calcul (τ), le dénominateur devient immense par rapport au numérateur. La quasi-totalité du temps CPU est gaspillée à changer de contexte. Mathématiquement, la limite de la fraction quand σ tend vers l'infini est 0. Solution : ρ ≈ 0

Question 6.b - Cas où σ << τ

Si la commutation de contexte (σ) est négligeable face au temps de calcul (τ), l'addition (τ + σ) au dénominateur est pratiquement égale à τ. L'équation devient ρ ≈ τ ÷ τ. Le CPU consacre tout son temps au travail utile. Solution : ρ ≈ 1

Méthode

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

1. Appels système : Face à des questions impliquant fork(), ne tentez jamais de deviner le résultat de tête. Dessinez toujours les variables sur un brouillon. Écrivez chaque processus avec ses propres variables locales. C'est la seule façon de ne pas se perdre lors de l'évaluation des conditions if.
2. Héritage : Souvenez-vous qu'un processus fils reçoit une copie exacte des variables de son père à l'instant de sa création (ici, l'héritage de la variable p1 a été la clé de la question 2).
3. Ordonnancement : Lors du calcul des temps, soyez extrêmement rigoureux avec les règles de départage (ici, l'identifiant). Écrivez votre liste de processus ordonnée avant de tracer le diagramme de Gantt. Les temps de séjour et d'attente découlent ensuite naturellement d'une simple lecture du diagramme.