Le système FAT16 est très simple et permet de comprendre le principe de la gestion des fichiers sur un disque dur. Bien entendu, des systèmes de gestion comme NTFS pour Windows ou XFS, EXT3, Reiserfs pour les GNU/Linux sont plus complexes, parfois même complètement différents.

Cependant FAT16 permet de comprendre un principe de base, qui est l'organisation des données par un système de gestion de mémoire de masse.

La FAT

La "File Allocation Table" est un tableau, indexé sur 16 bits (2¹⁶, 65 536 entrées au maximum).

Chaque entrée correspond à une unité de stockage sur la partition. Cette unité de stockage est constituée de 2ⁿ secteurs contigüs, n pouvant éventuellement être égal à 0. Cette plus petite unité s'appelle un "cluster".

Chaque entrée de la FAT peut contenir l'une des trois valeurs suivantes :

• cluster libre,
• cluster défectueux,
• cluster utilisé.

Cluster libre

Un tel cluster est considéré par le système comme vide et prêt à recevoir des données. Lorsque le système doit écrire des données sur la partition, il recherche le premier cluster disponible, pour commencer l'écriture. Nous verrons plus loin ce qu'il se passe si la taille des données à écrire est plus grande que celle d'un cluster.

Cluster défectueux

Un cluster est marqué comme défectueux lorsqu'il contient un secteur endommagé. Il y a souvent des secteurs endommagés sur un disque dur, c'est à dire que le système ne peut les repérer correctement, ou écrire correctement des données dessus.

Dans un tel cas, le cluster tout entier est marqué comme inutilisable.

Cluster utilisé

Lorsqu'un cluster est utilisé, son entrée dans la FAT peut prendre deux valeurs possibles, suivant que ce cluster est le dernier du fichier ou non.

Un fichier dans un seul cluster

Il peut très bien se faire qu'un fichier soit de taille suffisament petite pour tenir dans un seul cluster. Dans un tel cas, le cluster sera marqué dans la FAT comme étant la fin d'un fichier.

Un fichier dans plusieurs clusters

Si le fichier doit occuper plusieurs clusters, chaque cluster sera marqué dans la FAT avec l'index du cluster suivant, à l'exception du dernier cluster qui sera marqué comme étant le dernier.

Les clusters utilisés n'ont nul besoin d'être contigüs. En réalité, ce cas de figure ne se produit que lorsqu'on remplit une partition vierge pour la première fois.. Par la suite, suivant l'historique des effacements de fichiers et l'apport de nouveaux, les clusters disponibles ne seront plus contigüs. C'est ce que l'on appelle la fragmentation des fichiers.

Le catalogue

Bien entendu, la FAT ne suffit pas à gérer correctement les fichiers présents sur une partition. Il faut aussi un catalogue, qui contient, comme une table des matières, la liste des noms des fichiers présents sur la partition, avec quelques informations supplémentaires.

La structure arborescente des sous-répertoires est un peu compliquée et ne sert pas à grand chose pour l'explication qui suit, aussi nous allons simplifier le problème, en considérant qu'il n'y a pas de sous répertoires. C'était d'ailleurs le cas dans les versions DOS antérieures à la version 2. Nous ne nous intéresserons donc qu'au catalogue racine.

C'est également un tableau, qui contient :

• le nom des fichiers (au format 8.3 pour FAT16, c'est à dire un nom de 8 caractères, suivi d'un suffixe de 3 caractères),
• la date de création,
• la taille du fichier,
• un octet d'attributs, qui, pour l'instant, ne nous intéresse pas,
• et, c'est ici le plus important, l'index du premier cluster occupé par ce fichier.

Ainsi, lorsque l'on doit trouver un fichier, il suffit de suivre la procédure suivante :

• recherche dans le catalogue du fichier, en fonction de son nom,
• récupération de l'index du premier cluster,
• grâce à cette information, recherche dans la FAT du secteur suivant, jusqu'à ce que l'on arrive au cluster marqué comme fin de fichier.

Conclusions

La FAT est un répertoire qui permet d'obtenir, pour chaque cluster, les réponses aux questions suivantes :

• Le cluster est-il libre ?
• Le cluster est-il défectueux ?
• Le cluster est-il occupé ?
• Le contenu de ce cluster est-il poursuivi sur un autre cluster ?
• Ce cluster est-il le dernier secteur occupé par un fichier ?

Mais aucune réponse ne peut être donnée quant au nom des fichiers qui occupent ces clusters, de même qu'il n'est pas possible, simplement avec la FAT, de retrouver le premier cluster occupé par un fichier donné.

Pour retrouver la liste ordonnée des clusters qui contiennent un fichier donné

Il faut :

• trouver dans le catalogue l'index du premier cluster,
• consulter dans la FAT l'état de ce cluster qui doit soit :
  • indiquer l'index du cluster suivant,
  • indiquer que c'est le dernier cluster occupé par ce fichier.

Il faut donc avoir recours au services du catalogue ET de la FAT pour pouvoir lire l'intégralité des données contenues dans un fichier donné.

La démarche à suivre pour l'écriture d'un nouveau fichier est faclie à déduire, de même que celle qui est nécessaire pour l'ajout de données dans un fichier existant.

La fragmentation

Le problème de la fragmentation découle de ce type de gestion.

Lorsque la partition est vierge, les nouveaux fichiers vont naturellement occuper des clusters contigüs.

Par la suite, si un fichier est effacé, il se passe à peu près la chose suivante :

• l'entrée de ce fichier dans le catalogue est effacée (ce n'est pas tout à fait vrai, mais presque),
• tous les clusters qui étaient occupés par ce fichier sont re marqués comme disponibles dans la FAT.

Si, de suite après, un nouveau fichier est créé, de taille supérieure à celle du fichier fraîchement détruit, il occupera dans son début l'espace libéré par le fichier effacé. La fin de ce nouveau fichier sera, elle, écrite dans le premier cluster trouvé disponible dans la partition.

Ce nouveau fichier ne sera plus intégralement écrit sur des clusters contigüs.

Avec le temps, la FAT va de plus en plus ressembler à du gruyère et les fichiers seront de plus en plus fractionnés.

Le plus souvent, le fractionnement se traduit mécaniquement par des déplacements de têtes de plus en plus fréquents dans le disque, ce qui augmente le temps de transfert et augmente aussi l'usure.

Des systèmes de gestion plus évolués peuvent adopter des algorithmes de recherche de clusters libres plus complexes, afin d'éviter autant que possible la fragmentation, d'autres peuvent effectuer une défragmentation périodique, en tâche de fond (lorsque l'activité commanditée par l'utilisateur est faible).

Sur la FAT, la défragmentation, opération qui consiste à reconstruire les fichiers existants sur des clusters contigüs, doit être effectuée volontairement par l'utilisateur, avec un outil fourni dans l'OS. Cette opération peut être très longue et s'accomode mal d'un travail supplémentaire. Autrement dit, quand on défragmente, on ne fait rien d'autre sur sa machine.