Systèmes D'Exploitation I - Rattrapage, Juin 2016

Gestion des processus

Question 1 - Remplissage du code C avec fork()

Pour répondre à cette question, il faut comprendre le fonctionnement de l'appel système fork(). Cet appel crée un nouveau processus (le fils) qui est une copie exacte du processus appelant (le père).

La fonction fork() retourne :

• 0 dans le processus fils.
• Le PID (Process ID) du fils dans le processus père.

Le document source comportait quelques erreurs de syntaxe dues à l'extraction. Voici le code C complet, corrigé pour être compilable, avec les champs (1), (2), (3) et (4) remplis selon la logique demandée :

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

int main() {
    pid_t pid;
    pid = fork();

    if (pid == 0) {
        /* (1) Le processus fils affiche son PID et celui de son père */
        printf("FILS: le PID du fils est %d, le PID du père %d\n", getpid(), getppid());
        
        /* (2) Le processus fils dort 100 secondes */
        sleep(100);
    } else {
        /* (3) Le processus père affiche son PID et celui de son fils */
        printf("PERE: le PID du père est %d, le PID de mon fils %d\n", getpid(), pid);
        
        /* (4) Le processus père évite que son fils ne reste à l'état Zombie */
        wait(NULL);
    }
    
    return 0;
}

Explications des appels :

• getpid() : Retourne l'identifiant du processus courant.
• getppid() : Retourne l'identifiant du processus parent.
• sleep(100) : Met le processus en pause pendant 100 secondes.
• wait(NULL) : Met le processus parent en attente jusqu'à ce que l'un de ses processus fils se termine. Cela permet au système de nettoyer la table des processus et d'éviter que le fils ne devienne un processus "zombie".

Question 2 - Exécution de processus en cascade

Solution : 8 étoiles (*) seront affichées.

Explication : Chaque appel à fork() dédouble le processus existant.

• Au départ, il y a 1 processus.
• Le 1er fork() donne : 1 × 2 = 2 processus.
• Le 2ème fork() donne : 2 × 2 = 4 processus.
• Le 3ème fork() donne : 4 × 2 = 8 processus.

Puisque l'instruction printf("*"); se trouve après les trois appels à fork(), elle sera exécutée indépendamment par chacun des 8 processus résultants.

Ordonnancement des processus

Question 3 - Ordonnancement préemptif vs non préemptif

(a) Différences principales

• Ordonnancement non préemptif (sans réquisition) : Le processus garde le contrôle du processeur (CPU) jusqu'à ce qu'il libère lui-même les ressources (soit parce qu'il a terminé son exécution, soit parce qu'il se bloque en attendant une entrée/sortie).
• Ordonnancement préemptif (avec réquisition) : Le système d'exploitation peut forcer l'interruption d'un processus en cours d'exécution. Le processus s'exécute pendant un délai déterminé (un quantum de temps), après quoi le processeur lui est retiré pour être alloué à un autre processus.

(b) Exemples

• Algorithmes non préemptifs : FCFS (First-Come, First-Served, ou PAPS en français) et SJF (Shortest Job First).
• Algorithmes préemptifs : Round Robin (Tourniquet) et SRT (Shortest Remaining Time).

Question 4 - Minimisation du temps moyen d'attente

Nous avons 5 processus avec des temps d'exécution respectifs de 9, 6, 3, 5 et X unités. L'ordonnancement est sans réquisition. Pour minimiser le temps moyen d'attente (et donc d'exécution globale), la stratégie mathématiquement optimale consiste toujours à ordonner les processus du plus court au plus long.

(a) Si X < 3 L'ordre d'exécution qui minimise le temps moyen est : X, 3, 5, 6, 9.

(b) Si X > 9 L'ordre d'exécution qui minimise le temps moyen est : 3, 5, 6, 9, X.

(c) Identification de la stratégie Cette stratégie s'appelle SJF (Shortest Job First). Les entités annoncent leur temps d'exécution requis à l'avance, et le système d'exploitation les trie par ordre croissant de durée. C'est la stratégie reconnue pour garantir le meilleur temps d'attente moyen.

Système de gestion de fichier

Question 5 - Calcul de la taille d'allocation d'une FAT

Nous devons calculer la taille minimale d'une unité d'allocation (un cluster/bloc) pour un disque de 32 Go géré par une table FAT dont les entrées font 24 bits.

Démarche et calcul :

1. Capacité totale du disque : 32 Go = 32 × 2³⁰ octets. Sachant que 32 = 2⁵, la capacité est de 2⁵ × 2³⁰ = 2³⁵ octets.
2. Nombre d'entrées possibles dans la FAT : Une entrée de 24 bits permet d'adresser 2²⁴ unités d'allocation distinctes.
3. Taille minimale d'une unité d'allocation : La taille d'une unité s'obtient en divisant la capacité totale du disque par le nombre maximum d'entrées possibles. Taille = 2³⁵ ÷ 2²⁴ = 2⁽³⁵⁻²⁴⁾ = 2¹¹ octets.

Sachant que 2¹⁰ octets = 1 Ko, 2¹¹ octets équivaut à 2 × 1024 octets = 2048 octets (ou 2 Ko).

Solution : La taille minimale d'allocation de fichier est de 2 Ko.

Question 6 - Structure d'un i-node et tailles de fichiers

Les données du système sont :

• Taille d'un secteur = 512 octets.
• Taille d'un index (pointeur) = 4 octets.
• L'i-node stocke directement les 436 premiers octets du fichier.
• Tables d'index : 13 directs, 1 simple indirection, 1 double indirection, 1 triple indirection.

(a) Taille maximale d'un fichier Commençons par déterminer combien d'index (pointeurs) un secteur peut contenir : Nombre d'entrées par secteur = 512 octets ÷ 4 octets = 128 entrées.

Calculons maintenant l'espace adressable par chaque niveau de pointeurs :

• Données internes (dans l'i-node) : 436 octets
• Index directs (13 pointeurs) : 13 × 512 = 6 656 octets
• Simple indirection (1 table de 128 pointeurs) : 1 × 128 × 512 = 65 536 octets
• Double indirection (1 table pointant sur 128 tables de 128 pointeurs) : 1 × 128 × 128 × 512 = 8 388 608 octets
• Triple indirection (128 tables de 128 tables de 128 pointeurs) : 1 × 128 × 128 × 128 × 512 = 1 073 741 824 octets

Taille maximale = 436 + 6 656 + 65 536 + 8 388 608 + 1 073 741 824 = 1 082 203 060 octets, ce qui représente environ 1 Go.

(b) Bénéfice d'inclure les 436 premiers octets dans l'i-node Oui, c'est très bénéfique. La grande majorité des fichiers sur un système d'exploitation typique sont de très petite taille. Si un fichier fait 436 octets ou moins, ses métadonnées (l'i-node) et ses données réelles peuvent être lues ou écrites en une seule opération disque. Cela évite un accès indépendant supplémentaire pour aller chercher un bloc de données externe, ce qui améliore considérablement les performances.

(c) Taille minimale d'un fichier dans ce système Selon le barème de correction du document source : Un fichier, une fois créé, va occuper au minimum 1 bloc physique sur le disque. Sa taille allouée est donc au moins égale à la taille d'un secteur, soit 512 octets. (Note pédagogique : Bien que les 436 premiers octets soient dans l'i-node, le système de fichiers comptabilise conventionnellement l'encombrement minimum d'un fichier créé comme étant d'un secteur standard).

Méthode

Pour aborder ce type d'examen portant sur les systèmes d'exploitation :

1. Code C et appels système : Assurez-vous de bien maîtriser le comportement de fork(). Dessiner un arbre généalogique des processus au brouillon est la méthode la plus sûre pour répondre aux questions de type "Combien de processus sont créés ?". N'oubliez pas la distinction entre la valeur de retour de fork() pour le père (le PID du fils) et pour le fils (0).
2. Algorithmique d'ordonnancement : Apprenez à distinguer clairement les approches préemptives (avec interruption temporelle, ex: Round Robin) des approches non préemptives (ex: FIFO, SJF). Pour les calculs de temps moyen, tracez un diagramme de Gantt rapide sur votre brouillon.
3. Systèmes de fichiers (Calculs de FAT et i-nodes) : Soyez très rigoureux avec les puissances de 2. La formule clé pour la FAT est Taille disque = Nombre d'entrées × Taille d'un cluster. Pour les i-nodes UNIX, la progression géométrique (direct, simple, double, triple indirection) nécessite de toujours commencer par calculer le nombre de pointeurs qu'un bloc peut contenir (Taille du bloc ÷ Taille du pointeur), puis de multiplier par la taille du bloc à chaque étape de l'arborescence.