Système d’Exploitation 1 Exam

Exercice 1 : Répondre brièvement aux questions

Question 1 - Algorithmes et situation de famine

EXPLICATION : La famine (starvation) se produit lorsqu'un processus prêt à s'exécuter n'obtient jamais le processeur car d'autres processus sont continuellement choisis à sa place.

• FCFS (First-Come, First-Served) : Ne cause pas de famine. Chaque processus finit par obtenir le processeur dans l'ordre exact de son arrivée.
• SJF (Shortest Job First) : Peut causer une famine. Si un flux continu de processus très courts arrive dans le système, un processus long risque d'attendre indéfiniment.
• RR (Round Robin / Tourniquet) : Ne cause pas de famine. Tous les processus dans la file d'attente finissent par obtenir une tranche de temps de manière cyclique.
• Priorité : Peut causer une famine. Les processus de faible priorité peuvent ne jamais s'exécuter si le système est constamment chargé de processus de plus haute priorité.

Question 2 - Allocation de blocs et fragmentation

EXPLICATION : Bien que la question parle d'"allocation de blocs libres", il s'agit typiquement des méthodes d'allocation des blocs aux fichiers (l'espace libre en subissant les conséquences).

• Allocation contiguë : Conduit à une forte fragmentation externe. Au fur et à mesure que les fichiers sont créés et supprimés, l'espace libre est morcelé en petits blocs non contigus.
• Allocation chaînée : Élimine la fragmentation externe, mais génère un peu de fragmentation interne (dans le dernier bloc) et nécessite de l'espace pour les pointeurs.
• Allocation indexée : Élimine la fragmentation externe, mais peut conduire à de la fragmentation interne si les fichiers sont très petits par rapport au bloc d'indexation alloué.

(Note : Si la question fait spécifiquement référence aux méthodes de gestion de l'espace libre comme le Bitmap ou la Liste chaînée des blocs libres, aucune d'elles ne "cause" la fragmentation par elle-même ; ce sont les politiques d'allocation aux fichiers qui en sont responsables).

Question 3 - Structure et rôles d'un PCB

Le PCB (Process Control Block) est une structure de données maintenue par le système d'exploitation pour stocker toutes les informations nécessaires à la gestion d'un processus. Son rôle est de sauvegarder le contexte d'un processus lorsqu'il est interrompu afin de pouvoir reprendre son exécution exactement là où elle s'est arrêtée.

Schéma d'un PCB typique :

Structure du PCB
Identifiant (PID)
État du processus (Prêt, Élu, Bloqué...)
Compteur ordinal (PC) (Adresse de la prochaine instruction)
Registres du processeur
Informations d'ordonnancement (Priorité, etc.)
Informations de gestion de mémoire (Limites, tables de pages)
Informations sur les E/S (Fichiers ouverts, périphériques alloués)

Question 4 - Taille logique vs Taille sur le disque

• Taille logique : Représente la quantité réelle de données contenues dans le fichier, mesurée au niveau de l'utilisateur (le nombre exact d'octets de données).
• Taille sur le disque : Représente l'espace physique réellement alloué par le système de fichiers pour stocker ce fichier. L'espace disque étant alloué par blocs (ou clusters) entiers, la taille sur le disque est toujours un multiple de la taille d'un bloc. La différence entre les deux constitue la fragmentation interne.

Question 5 - Codage ASCII vs UTF-8

• ASCII : Codage historique sur 7 bits (parfois étendu à 8 bits).
  • Inconvénients : Limité à 128 (ou 256) caractères. Ne permet pas de coder des caractères internationaux (accents, alphabets non-latins, idéogrammes).

UTF-8 : Codage à longueur variable (de 1 à 4 octets par caractère), rétrocompatible avec l'ASCII.

• Inconvénients : La longueur variable des caractères rend l'accès direct (indexation) au n-ième caractère d'une chaîne plus complexe et plus lent. De plus, il consomme plus d'espace de stockage pour les alphabets asiatiques ou cyrilliques comparé à certains encodages locaux spécifiques.

Question 6 - Commandes Linux

Le répertoire courant étant /home/ubuntu, voici les commandes :

# Création du répertoire 1annee
mkdir 1annee

# Création des deux sous-répertoires
mkdir 1annee/SEM1 1annee/SEM2

# Copie du fichier
cp /home/ubuntu/Matieres/liste.txt 1annee/SEM1/

Exercice 2 : Ordonnancement de processus

Analyse de l'état initial (à 3h 30m 30s, noté t=0)

L'unité de temps du système correspond à des tranches de 30 secondes. Les processus P5 (En attente) et P7 (Bloqué) ne sont pas prêts à s'exécuter. L'énoncé ne donnant aucune date de réveil, nous ne considérerons que les processus à l'état "Prêt".

Processus prêts à t=0 avec leur durée restante et priorité :

• P1 : 18s (Prio 3, arrivé 3h28m10s)
• P2 : 22s (Prio 1, arrivé 3h27m10s)
• P3 : 17s (Prio 2, arrivé 3h26m40s)
• P4 : 9s (Prio 3, arrivé 3h28m12s)
• P6 : 10s (Prio 0, arrivé 3h25m10s)
• P8 : 14s (Prio 1, arrivé 3h25m10s)

Question 1 - Schéma d'exécution des processus

Phase 1 (t = 0 à t = 30) : SJF avec réquisition (SRTF) Puisqu'il n'y a pas de nouvelles arrivées, l'algorithme se comporte comme un SJF strict sur les durées restantes. L'ordre est P4 (9s), P6 (10s), P8 (14s), P3 (17s), P1 (18s), P2 (22s).

• 0 à 9 : exécution de P4 (Se termine).
• 9 à 19 : exécution de P6 (Se termine).
• 19 à 30 : exécution de P8 pendant 11s. Il reste à P8 : 14 - 11 = 3s. Fin de la phase 1. Restent : P8 (3s), P3 (17s), P1 (18s), P2 (22s).

Phase 2 (t = 30 à t = 60) : Tourniquet (RR, quantum = 5s) La file est constituée selon le critère d'arbitrage (le plus ancien servi en premier). L'ordre d'arrivée est P8 (3h25m10), P3 (3h26m40), P2 (3h27m10), P1 (3h28m10). La file RR est donc : [P8, P3, P2, P1].

• 30 à 33 : P8 s'exécute pendant 3s (Se termine).
• 33 à 38 : P3 s'exécute pendant 5s (Reste 12s).
• 38 à 43 : P2 s'exécute pendant 5s (Reste 17s).
• 43 à 48 : P1 s'exécute pendant 5s (Reste 13s).
• 48 à 53 : P3 s'exécute pendant 5s (Reste 7s).
• 53 à 58 : P2 s'exécute pendant 5s (Reste 12s).
• 58 à 60 : P1 s'exécute pendant 2s (Reste 11s). L'algorithme est interrompu par la fin de la période de 30 secondes. Fin de la phase 2. Restent : P1 (11s), P2 (12s), P3 (7s).

Phase 3 (t = 60 à t = 90) : Priorité préemptif La priorité la plus basse correspond au processus le plus prioritaire : P2 (1), P3 (2), P1 (3).

• 60 à 72 : P2 s'exécute pendant 12s (Se termine).
• 72 à 79 : P3 s'exécute pendant 7s (Se termine).
• 79 à 90 : P1 s'exécute pendant 11s (Se termine).

Question 2 - L'ordonnancement le plus performant

Le rendement est défini par le nombre de processus terminés par unité de temps (ici l'unité de temps du système est la fenêtre de 30 secondes).

• Phase 1 (SJF) : 2 processus terminés (P4, P6). Rendement = 2.
• Phase 2 (RR) : 1 processus terminé (P8). Rendement = 1.
• Phase 3 (Priorité) : 3 processus terminés (P2, P3, P1). Rendement = 3.

L'ordonnancement avec Priorité préemptif a le meilleur rendement sur ce segment (bien que ce soit circonstanciel, lié aux reliquats de temps laissés par les algorithmes précédents).

Question 3 - Temps de réponse et temps d'attente moyens

Tous les calculs démarrent à la date de référence (t=0). Pour chaque processus i, le Temps de Séjour (Ts) correspond à sa date de fin, et le Temps d'Attente (Ta) vaut Ts moins sa durée d'exécution restante à t=0.

Processus	Durée restante à t=0	Date de fin (Ts)	Temps d'attente (Ta = Ts - Durée)
P4	9	9	9 - 9 = 0
P6	10	19	19 - 10 = 9
P8	14	33	33 - 14 = 19
P2	22	72	72 - 22 = 50
P3	17	79	79 - 17 = 62
P1	18	90	90 - 18 = 72
Somme		302	212

• Temps de réponse (séjour) moyen = 302 ÷ 6 = 50,33 secondes.
• Temps d'attente moyen = 212 ÷ 6 = 35,33 secondes.

Question 4 - Le processus le plus sanctionné

Le processus le plus sanctionné en termes de temps d'attente est P1 avec un temps d'attente de 72 secondes.

Exercice 3 : Système de fichiers et I-nodes

Données :

• Taille du bloc = 1 Ko = 1024 octets.
• Pointeur = 4 octets.
• Nombre d'adresses dans un bloc indirect = 1024 ÷ 4 = 256 pointeurs. (L'énoncé confirme que l'i-node pointe sur 256 adresses directes via son pointeur indirect).

Question 1 - Taille maximale d'un fichier

L'i-node dispose de 12 pointeurs directs et d'un pointeur indirect (donnant accès à 256 blocs supplémentaires). Le nombre maximal de blocs de données pour un fichier est : 12 + 256 = 268 blocs.

• Taille maximale = 268 × 1 Ko = 268 Ko = 274 432 octets.

Question 2 - Espaces disque nécessaires

On s'intéresse ici à l'espace occupé par les blocs (données + éventuel bloc d'index) alloués sur le disque.

a. Fichier de 10 Ko

• 10 Ko correspondent à 10 blocs de données.
• Ces 10 blocs peuvent être adressés directement par les 12 pointeurs directs de l'i-node.
• Aucun bloc d'index supplémentaire n'est requis.
• Espace disque = 10 blocs = 10 Ko (ou 10 240 octets).

b. Fichier de 120 Ko

• 120 Ko correspondent à 120 blocs de données.
• Les 12 premiers blocs utilisent les pointeurs directs.
• Les 108 blocs restants nécessitent l'utilisation du pointeur indirect, ce qui impose d'allouer 1 bloc d'index sur le disque pour stocker ces pointeurs.
• Total des blocs sur le disque = 120 (données) + 1 (index) = 121 blocs.
• Espace disque = 121 Ko = 123 904 octets.

Question 3 - Espace pour la méthode d'allocation "bitmap"

Un disque de 10 Go doit être entièrement géré par le bitmap.

• 1 Go = 1024 Mo = 1024 × 1024 Ko.
• Disque total = 10 × 1024 × 1024 Ko = 10 485 760 Ko.
• Étant donné qu'un bloc fait 1 Ko, le disque contient 10 485 760 blocs. La méthode bitmap requiert 1 bit pour représenter l'état (libre/occupé) de chaque bloc.
• Nombre de bits nécessaires = 10 485 760 bits.
• Espace en octets = 10 485 760 ÷ 8 = 1 310 720 octets (soit 1280 Ko, ou 1,25 Mo).

Méthode

Pour réussir ce type d'épreuve (Systèmes d'Exploitation), la clé réside dans la rigueur des calculs et le respect chronologique des événements.

• Dans les problèmes d'ordonnancement multi-phases (comme l'Exercice 2), il est fondamental de tenir un journal d'exécution (souvent sous forme de diagramme de Gantt au brouillon) qui liste chaque processus, son reliquat de temps, son état et sa priorité à chaque basculement d'algorithme. Une erreur sur l'état de la file à la fin de la Phase 1 faussera inévitablement l'intégralité des phases suivantes.
• Pour la manipulation des i-nodes, convertissez systématiquement toutes vos unités dans la même base (octets, ou Ko) avant toute opération. Identifiez toujours si l'énoncé vous demande de calculer uniquement la taille des données ou la taille de l'espace alloué (qui inclut alors les blocs d'index).