File Allocation table
Si simple et si rapide
F A T

Le tableau FAT (File Allocation Table) est à la base du système de fichiers FAT. Le répertoire indique le début du fichier sur le disque, mais ce système est insuffisant quand le fichier s'est aggrandi et se compose de plusieurs morceaux. Le tableau FAT permet de rechercher rapidement tous les morceaux d'un fichier. La structure FAT est maintenue en mémoire vive pour permettre un accès rapide.
-

-

Blocs et clusters (unités d'allocation)

Le disque dur contient des milliards d'octets. Mais ils ne sont pas addressables individuellement. 512 octets consécutifs forment un bloc (dans la préhistoire informatique on disait un secteur): c'est la plus petite structure adressable sur le disque (voir organisation physique). Les cartes de mémoire (et les disques les plus récents) travaillent avec des blocs de 4kB.

Il y a trop de blocs dans le cas d'un volume de grande capacité (par exemple 1GB: 2 million de blocs). Gérer tout ces blocs demande trop de temps et trop de place. Les blocs sont regroupés par unités d'allocation ou clusters. Un cluster contient par exemple 32 blocs consécufifs. Notre disque de 1GB contient 62.500 clusters de 16.384 octets. Un fichier ou répertoire utilise toujours un minimum de une unité d'allocation (donc 16.384 octets)

Attention: le groupement en clusters ne se fait que dans l'espace-données (répertoires et fichiers), pas dans la zone technique qui est accédée par bloc. Les autres formats (NTFS et EXT) utilisent également les unités d'allocation.

Contenu du volume
A droite un exemple d'organisation d'un volume. Les deux premiers blocs sont le boot sector et l'extended sector (qui contiennent le code pour démarrer l'ordinateur), et puis suit le FAT. La zone technique contient souvent une seconde copie du FAT et (dans le cas de FAT-16) également le répertoire de base (root ou racine). Le répertoire de base ne peut pas grandir s'il est repris dans la zone technique. C'est pour cela que les versions plus récentes du FAT placent le répertoire de base dans la zone de données.

La zone de donnée contient les fichiers et les répertoires. Dans cet exemple, il n'y a pas de groupement en unités d'allocation à cause du petit nombre de blocs disponibles.

Fonctionnement:

  • Nous formattons notre volume: le répertoire de base est créé.
  • Nous écrivons le fichier-1 qui se compose de 14 blocs. Le répertoire pointe vers le premier bloc du fichier, ce qui nous permet plus tard de lire le fichier.
  • Nous écrivons le fichier-2 qui utilise les blocs suivants.
  • Nous agrandissons le fichier-1 et le fichier-2. Comme il n'y a plus de place derrière le fichier, nous plaçons les morceaux au premier endroit de libre (E-1 et E-2). Les deux fichiers sont ainsi fragmentés.
  • Nous écrivons un fichier-3, mais dans notre exemple hypothétique il n'y a plus de place dans le répertoire qui doit être étendu (bloc E).

Comment est-il possible de lire ces morceaux? Grâce au FAT qui est une liste chainée (linked list). La liste chainée est une des structures de base en informatique. Contrairement aux listes chainées classiques, cette liste ne contient aucune valeur (donnée d'exploitation), mais uniquement un pointeur vers l'élément suivant. Si tu comprends cette phrase, tu as tout compris du système FAT: la valeur se trouve en effet dans l'unité d'allocation correspondante! L'accès à la valeur est implicite: la position d'un élément dans le tableau FAT correspond à la même position dans la série d'unités d'allocation.

Contenu du FAT
Notre répertoire a une longueur de 4 blocs et se compose de deux morceaux. La liste chainée du répertoire est 2-3-29-0 (chaque élément pointe vers l'élément suivant de la liste). Nous utilisons la valeur 0 pour indiquer la fin de la liste.

L'emplacement des différents fichiers correspond aux différentes listes chainées dans le tableau FAT.

Nous soulignons en rouge les points d'entrée de notre liste (le point d'entrée n'est pas indiqué dans la liste, c'est simplement une aide à la compréhension). Un champ de chaque enregistrement du répertoire contient un pointer vers l'adresse physique du début du fichier, et donc également vers le premier élement de la liste.

Implémentation pratique et exemples

Le tableau FAT se compose d'élements de 12 bits, donc un octet et demi, ce qui ne facilite pas les calculs... (FAT-12, utilisé avec des disquettes). FAT-16 utilise 16 bits (disques durs anciens et cartes de mémoire) et FAT-32 28 bits.

La zone de donnée peut donc contenir 4.096, 65.536 ou 268.435.456 unités d'allocation. C'est également la limite maximale du nombre de fichiers sur le volume. Dans notre exemple pratique, le volume de 1GB avec ses unités d'allocation de 32 blocs (16kB) a un FAT qui fait 125.000 octets, soit 0.125% de la capacité totale du volume, ce qui est une excellente valeur.

Un inconvénient est l'unité d'allocation de 16kB. Dans le cas extrème (un fichier d'un octet) on pert 16.383 octets. Si le volume est principalement utilisé pour des photos (cas d'une carte-mémoire), donc 500 photos de 2MB, on perd en moyenne 8.192 octets par 2MB, soit moins d'un demi pourcent, ce qui est très très bon.

Dans un vrai système, on n'utilise pas les deux premiers éléments du FAT, qui contiennent des informations techniques (housekeeping): une indication si le volume a été cloturé correctement (dirty bit) et l'adresse du premier bloc de libre.

Avantages

Ce système est particulièrement simple et pouvait être utilisé avec les tout premiers ordinateurs qui n'avaient qu'une puissance de calcul très limitée et très peu de mémoire vive. Les appareils les plus simples peuvent utiliser ce format. Les ordinateurs actuels chargent tout le FAT en mémoire, ce qui garantit un fonctionnement très rapide.

Le FAT (qui est la seule structure technique) prend très peu de place en mémoire et sur disque et permet de localiser rapidement tous les morceaux d'un fichier. Il y a une correspondance entre chaque élément du FAT et la position du fragment de données (cluster) dans la zone des données.

L'écriture est également très simple: écrire les données, modifier le FAT, modifier le répertoire. Un fichier est créé en trois opérations élémentaires.

De plus, le format FAT est libre de droits. Microsoft a essayé de le patenter, mais cela n'a réussi que pour une très petite partie du format, notament la fonction "noms longs" (qui utilise des éléments de répertoire consécutifs). C'est pour cela que les photos sur une carte flash ont toujours des noms au format 8.3 DSC-1234.JPG. L'appareil photo ne montrera pas la photo si tu changes son nom car l'appareil ne contient pas de code pour interpréter les noms longs.

Inconvénients

Le format est très simple et manque certaines fonctions:
  • L'indication du temps n'est pas très précise (à la seconde près, donc bien suffisant)
  • Pas de droits d'accès, tout le monde a accès à tous les fichiers
  • Il n'y a pas de système pour limiter la fragmentation des fichiers (mais NTFS n'est pas meilleur sur ce point). Les cartes de mémoire ne sont pas plus lentes quand on accède à un fichier fragmenté.
  • Il y a une limite quant à la longueur maximale des fichiers.
Quand le format FAT a été établi, la limite maximale de grandeur de fichier ne jouait pas, comme le montre ce tableau, puisqu'un disque dur pouvait stocker au mieux... 10 photos!:

Système
d'exploitation
Espace sur le disque
utilisé par le système
Mémoire vive
(minimum)
Capacité
disques durs
DOS 6.23.5MB640kB10MB
Windows 95100MB1MB4.3GB
Windows XP1GB128MB80GB
Vista4GB1GB (theorie)250GB

Links to relevant pages - Liens vers d'autres pages au contenu similaire - Links naar gelijkaardige pagina's

-