Système D’exploitation 1

Exercice 1 - Paramètres du système de gestion de fichier

Question 1 - Nombre de blocs du disque

Pour déterminer le nombre de blocs physiques, on divise la capacité totale du disque par la taille d'un bloc. En informatique, on utilise généralement les puissances de 2 (1 Ko = 2^10 octets, 1 Mo = 2^20 octets, 1 Go = 2^30 octets).

• Capacité totale = 64 Go = 64 × 2^30 octets = 2^6 × 2^30 octets = 2^36 octets.
• Taille d'un bloc = 4 Ko = 4 × 2^10 octets = 2^2 × 2^10 octets = 2^12 octets.
• Nombre de blocs = (2^36) ÷ (2^12) = 2^24 blocs.

Le disque dur contient 2^24 blocs (soit 16 777 216 blocs).

Question 2 - Taille minimale d'une adresse

L'adresse doit permettre d'identifier chaque bloc de manière unique. Puisqu'il y a 2^24 blocs, l'adresse doit coder au minimum 2^24 valeurs différentes. Il faut donc réserver 24 bits pour adresser un bloc (puisque 2^24 correspond exactement à une combinaison de 24 bits).

Question 3 - Taille de la FAT en nombre de blocs

La table FAT contient une entrée par bloc de données. Il y a donc 2^24 entrées dans la table. Chaque entrée mémorise l'adresse du bloc suivant, ce qui nécessite, d'après la question précédente, une taille minimale de 24 bits (soit 3 octets).

• Taille totale de la FAT en octets = (Nombre d'entrées) × (Taille d'une entrée) = 2^24 × 3 octets = 50 331 648 octets (48 Mo).
• Nombre de blocs nécessaires pour la FAT = (Taille totale de la FAT) ÷ (Taille d'un bloc) = (3 × 2^24) ÷ 2^12 = 3 × 2^12 = 3 × 4096 = 12 288 blocs.

Question 4 - Taille de la table de bits (bitmap) en blocs

La méthode bitmap utilise 1 bit pour représenter l'état (libre ou occupé) de chaque bloc physique.

• Nombre total de bits = Nombre de blocs = 2^24 bits.
• Taille en octets = (2^24) ÷ 8 = 2^21 octets (soit 2 Mo).
• Taille de la bitmap en blocs = (2^21 octets) ÷ (2^12 octets par bloc) = 2^9 = 512 blocs.

Exercice 2 - Allocation et i-nodes sur une partition de 16 Go

Partie A - Système FAT

Question A.1 - Principe de la méthode FAT

La méthode FAT (File Allocation Table) est une méthode d'allocation chaînée gérée via une table d'index centralisée (la FAT). La table contient une entrée pour chaque bloc logique de la partition. L'entrée d'un bloc contient un pointeur (l'adresse) vers le bloc suivant du fichier, ou un marqueur spécial (comme EOF) si le bloc est le dernier du fichier. Le répertoire contient l'adresse du premier bloc du fichier.

Question A.2 - Taille maximale de la table FAT

La table FAT peut avoir autant d'entrées que ce que l'adressage sur 32 bits permet.

• Nombre maximum d'entrées = 2^32 entrées.
• Taille d'une entrée = 32 bits = 4 octets.
• Taille maximale théorique de la FAT = 2^32 × 4 octets = 2^34 octets = 16 Go. (Note: Dans ce cas théorique, la taille maximale de la FAT correspond à la taille de la partition entière).

Question A.3 - Taille minimale de la FAT pour gérer cette partition

La taille minimale dépend du nombre réel de blocs présents sur cette partition de 16 Go.

• Nombre de blocs de la partition = 16 Go ÷ 8 Ko = (2^34 octets) ÷ (2^13 octets) = 2^21 blocs.
• La table aura donc 2^21 entrées. En FAT32, chaque entrée occupe 32 bits (4 octets).
• Taille de la table FAT = 2^21 × 4 octets = 2^23 octets = 8 Mo.

Partie B - Système à base d'i-nodes

Question B.1 - Taille maximale d'un fichier

L'énoncé précise qu'un i-node est composé uniquement de 10 adresses directes.

• Taille maximale = (Nombre d'adresses) × (Taille d'un bloc) = 10 × 8 Ko = 80 Ko.

Question B.2 - Nombre de blocs pour un fichier de 2 Go

• Taille du fichier = 2 Go = 2^31 octets.
• Taille d'un bloc = 8 Ko = 2^13 octets.
• Nombre de blocs = (2^31) ÷ (2^13) = 2^18 = 262 144 blocs.

Question B.3 - Possibilité d'implanter ce fichier

Non, il est impossible d'implanter ce fichier avec le système d'i-nodes décrit dans l'énoncé. Le fichier nécessite 262 144 blocs (2 Go), or la structure de l'i-node avec 10 adresses directes ne permet de stocker que 80 Ko au maximum. Sans adresses indirectes, la capacité est insuffisante.

Question B.4 - Taille de la liste chaînée des blocs libres

• Espace libre = 7 Go.
• Nombre de blocs libres = 7 Go ÷ 8 Ko = (7 × 2^30) ÷ (2^13) = 7 × 2^17 = 917 504 blocs. Dans la méthode standard de "liste chaînée" pour l'espace libre, le pointeur vers le bloc libre suivant est stocké directement à l'intérieur de chaque bloc libre. Par conséquent, la structure de la liste elle-même occupe 0 bloc supplémentaire (les données de chaînage consomment de l'espace dans les blocs déjà considérés comme libres). Si la question demande le nombre de blocs constituant la liste, c'est 917 504 blocs.

Exercice 3 - Lecture et exploitation d'une table FAT16

Question 1 - Principe de la FAT et différence entre FAT16 et FAT32

Le principe de la méthode FAT a été expliqué dans l'Exercice 2 (A.1) : allocation chaînée via un tableau d'index.

• Différence FAT16 / FAT32 : La différence réside dans la taille des pointeurs pour adresser les clusters (blocs). FAT16 utilise 16 bits par entrée, ce qui limite le système à 2^16 clusters adressables. FAT32 utilise 32 bits par entrée (28 bits effectifs pour l'adresse), permettant d'adresser 2^28 clusters, ce qui autorise des partitions beaucoup plus grandes.

Question 2 - Capacité d'adressage maximale avec FAT16

• FAT16 utilise 16 bits, permettant d'adresser au maximum 2^16 = 65 536 blocs (clusters).
• Taille d'un cluster = 4 octets.
• Capacité maximale = 65 536 × 4 octets = 262 144 octets = 256 Ko.

Question 3 - Type d'allocation mémoire utilisée

La table FAT donnée illustre une allocation chaînée avec table d'index (ou allocation indexée via FAT). Explication : On observe que la valeur d'une case (bloc) pointe vers le numéro de la case suivante appartenant au même fichier. Par exemple, le bloc 1 contient la valeur 4 (le fichier continue au bloc 4), le bloc 4 contient 9, etc., jusqu'à rencontrer un marqueur de fin "FFFF". L'espace n'a pas besoin d'être contigu, le chaînage permet d'utiliser des blocs éparpillés.

Question 4 - Complétion du tableau des fichiers

Le tableau partiel de l'énoncé fournit "14, 15, 20", qui correspondent aux blocs finaux ("FFFF" dans la FAT). Nous devons retracer les chaînes pour trouver le début, le nombre de blocs et la taille de chaque fichier.

• Chaîne finissant par 14 : On cherche la suite aboutissant à 14. 6 → 7 → 16 → 14 → FFFF. (@ début = 6, Blocs = 4).
• Chaîne finissant par 15 : 1 → 4 → 9 → 10 → 15 → FFFF. (@ début = 1, Blocs = 5).
• Chaîne finissant par 20 : 11 → 17 → 13 → 20 → FFFF. (@ début = 11, Blocs = 4).

Associons F1, F2 et F3 à leurs adresses de fin respectives fournies par le tableau (F1 finit à 14, F2 à 15, F3 à 20) :

Fichier	@ début	@ Fin	Nombre de blocs	Taille logique en octets (Nb blocs × 4)
F1	6	14	4	16
F2	1	15	5	20
F3	11	20	4	16

Question 5 - Schéma des blocs physiques

En utilisant la table précédente, nous plaçons les fragments de F1, F2 et F3 dans les blocs 1 à 20 :

1	2	3	4	5	6	7	8	9	10
F2	vide	vide	F2	vide	F1	F1	vide	F2	F2

11	12	13	14	15	16	17	18	19	20
F3	vide	F3	F1	F2	F1	F3	vide	vide	F3

Question 6 - Allocation contiguë

Avantages :

• Temps d'accès très rapide (lecture séquentielle excellente) car il y a peu ou pas de mouvement de la tête de lecture.
• La gestion est simple (il suffit de connaître l'adresse de début et la longueur).

Inconvénients :

• Fragmentation externe (l'espace libre est morcelé en petits blocs inutilisables pour de grands fichiers).
• Impossibilité ou grande difficulté d'agrandir un fichier s'il n'y a pas d'espace libre immédiatement à sa suite.

Table FAT avec allocation contiguë : Pour une allocation contiguë, les fichiers doivent être stockés sur des blocs adjacents. F1 nécessite 4 blocs, F2 nécessite 5 blocs et F3 nécessite 4 blocs. En supposant que le système les écrit dans l'ordre aux premiers emplacements disponibles (1 à 4 pour F1, 5 à 9 pour F2, 10 à 13 pour F3) :

N°	Valeur		N°	Valeur
1	2		11	12
2	3		12	13
3	4		13	FFFF
4	FFFF		14	vide
5	6		15	vide
6	7		16	vide
7	8		17	vide
8	9		18	vide
9	FFFF		19	vide
10	11		20	vide

Exercice 4 - Structure de disque et optimisation d'espace

(Note préliminaire : L'énoncé ne précise pas explicitement l'emplacement visuel initial de F1, ni son niveau de morcellement. Pour l'exercice, F1 compte 15 octets et occupe donc nécessairement 4 blocs de 4 octets. Nous supposerons ici que l'allocation s'effectue dans les premiers blocs disponibles).

Question 1 - Type possible d'allocation

F1 occupe 15 octets, soit 4 blocs entiers (le dernier bloc subit une fragmentation interne de 1 octet). Si le schéma extrait du PDF original montrait ces 4 blocs placés de manière consécutive (ex: blocs 1, 2, 3, 4), l'allocation pourrait être contiguë. S'ils étaient dispersés (ex: blocs 1, 6, 11, 16), cela indiquerait une allocation chaînée ou indexée. L'existence d'une table FAT dans la suite de l'exercice indique que l'allocation du système de fichiers cible est chaînée via index.

Question 2 et 3 - Rappel FAT16

Ces questions sont identiques à l'Exercice 3.

• Différence FAT16/FAT32 : Taille des adresses (16 bits pour FAT16 limitant à 65 536 clusters, contre 32 bits pour FAT32).
• Capacité maximale FAT16 : 2^16 blocs × 4 octets = 256 Ko.

Question 4 - Taille occupée par les 3 nouveaux fichiers

• F2 (6 octets) nécessite 2 blocs.

• F3 (5 octets) nécessite 2 blocs.

• F4 (14 octets) nécessite 4 blocs.

• Taille logique occupée par les 3 fichiers : Somme des données = 6 + 5 + 14 = 25 octets.

Taille occupée (allouée) sur le disque : F2 (8 oct) + F3 (8 oct) + F4 (16 oct) = 32 octets (soit 8 blocs).

Question 5 - Structure de la table FAT (après ajout)

Hypothèse de premier ajustement (F1 sur les blocs 1 à 4). Les fichiers F2, F3 et F4 utiliseront les blocs suivants.

• F1 (15 octets) : blocs 1, 2, 3, 4 (chaîne : 1→2→3→4→FFFF).
• F2 (6 octets) : blocs 5, 6 (chaîne : 5→6→FFFF).
• F3 (5 octets) : blocs 7, 8 (chaîne : 7→8→FFFF).
• F4 (14 octets) : blocs 9, 10, 11, 12 (chaîne : 9→10→11→12→FFFF).

Bloc 1	Bloc 2	Bloc 3	Bloc 4	Bloc 5	Bloc 6	Bloc 7	Bloc 8
2	3	4	FFFF	6	FFFF	8	FFFF

Bloc 9	Bloc 10	Bloc 11	Bloc 12	Bloc 13	Bloc 14	Bloc 15	Bloc 16
10	11	12	FFFF	vide	vide	vide	vide

Question 6 - Schéma des blocs physiques

Représentation spatiale selon l'hypothèse de la question 5 :

1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
F1	F1	F1	F1	F2	F2	F3	F3	F4	F4	F4	F4	vide	vide	vide	vide

Question 7 - Taille optimale et pourcentage d'occupation

La taille du bloc physique de 4 octets engendre une perte d'espace due à la fragmentation interne à la fin de chaque fichier.

• Taille logique totale (4 fichiers) : 15 + 6 + 5 + 14 = 40 octets.
• Taille physique totale (allouée) : 16 + 8 + 8 + 16 = 48 octets.
• Pourcentage d'occupation : (40 ÷ 48) × 100 ≈ 83,33 %. La perte de 16,67% (fragmentation interne) montre que la taille n'est pas strictement optimale, mais elle demeure raisonnable.

Question 8 - Reformatage avec des blocs de 2 octets

Evaluons l'impact avec des blocs de 2 octets :

• F1 (15 o) nécessitera 8 blocs (16 octets alloués).
• F2 (6 o) nécessitera 3 blocs (6 octets alloués).
• F3 (5 o) nécessitera 3 blocs (6 octets alloués).
• F4 (14 o) nécessitera 7 blocs (14 octets alloués).
• Taille physique totale allouée : 16 + 6 + 6 + 14 = 42 octets.
• Nouveau pourcentage d'occupation : (40 ÷ 42) × 100 ≈ 95,23 %.

Conclusion : Je conseille ce reformatage uniquement si l'espace disque est critique et que la majorité des fichiers sont de très petite taille. En effet, réduire le bloc à 2 octets minimise fortement la fragmentation interne (gain d'espace de 6 octets sur ces 4 fichiers). Cependant, il faut avertir l'utilisateur des contreparties : le nombre de blocs double, ce qui double la taille de la table FAT et augmente considérablement le nombre d'opérations d'accès disque (lecture/écriture de plusieurs fragments) et ralentit donc le système.

Méthode

Pour réussir un examen sur la gestion des systèmes de fichiers, il faut maitriser quelques règles mathématiques simples :

1. Toujours aligner les unités : Avant tout calcul, convertissez l'ensemble des données dans une base commune de puissances de 2 (souvent les octets). Rappelez-vous que 1 Ko = 2^10 octets, 1 Mo = 2^20 octets, 1 Go = 2^30 octets.
2. Arrondi au plafond pour les blocs : Les fichiers ne remplissent jamais parfaitement un disque. Si un calcul donne 3,2 blocs nécessaires, le fichier prendra 4 blocs physiques entiers.
3. Le vocabulaire : "Table de bits" ou "Bitmap" veut dire 1 bloc = 1 bit de suivi. FAT = table de correspondances avec chaînage (une case par bloc sur le disque). i-nodes = des structures contenant directement les adresses limitant la taille d'un fichier en l'absence de chaînage indirect.
4. Lecture de table FAT : Dans un exercice de traçage de FAT, ne confondez pas le numéro du bloc (souvent en index de colonne/ligne) et le contenu de la case (qui est l'adresse du prochain bloc). Un parcours commence au pointeur donné par le répertoire (la @ début) et s'arrête à la balise de fin de fichier (EOF, -1 ou FFFF).