Système D’exploitation 1
Système D’exploitation 1
Système de Gestion de Fichier, FAT, Programmation, Mathématiques · exam
Fiche de révisionCorrigé
Rédigée à partir de ce document, puis vérifiée avant publication.
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).
Le disque dur contient 2^24 blocs (soit 16 777 216 blocs).
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).
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).
La méthode bitmap utilise 1 bit pour représenter l'état (libre ou occupé) de chaque bloc physique.
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.
La table FAT peut avoir autant d'entrées que ce que l'adressage sur 32 bits permet.
La taille minimale dépend du nombre réel de blocs présents sur cette partition de 16 Go.
L'énoncé précise qu'un i-node est composé uniquement de 10 adresses directes.
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.
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.
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.
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.
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 |
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 |
Avantages :
Inconvénients :
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 |
(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).
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.
Ces questions sont identiques à l'Exercice 3.
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).
Hypothèse de premier ajustement (F1 sur les blocs 1 à 4). Les fichiers F2, F3 et F4 utiliseront les blocs suivants.
| 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 |
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 |
La taille du bloc physique de 4 octets engendre une perte d'espace due à la fragmentation interne à la fin de chaque fichier.
Evaluons l'impact avec des blocs de 2 octets :
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.
Pour réussir un examen sur la gestion des systèmes de fichiers, il faut maitriser quelques règles mathématiques simples :
@ début) et s'arrête à la balise de fin de fichier (EOF, -1 ou FFFF).