FAT: File Allocation Table

La FAT (File Allocation Table) fu sviluppata da Bill Gates e Marc McDonald nel 1977 per il sistema operativo 86-DOS (originariamente chiamato QDOS, “Quick and Dirty Operating System”), che a sua volta era destinato a computer basati sull’architettura Intel 8086. Questo file system nacque come una soluzione semplice per organizzare i dati su dispositivi di archiviazione, come floppy disk e primi dischi rigidi.

Contesto Tecnico della Nascita

  • Problema iniziale: I sistemi di archiviazione necessitavano di una tabella che registrasse dove erano memorizzati i dati su disco. Prima della FAT, i file system erano più rudimentali e limitati a memorizzare file in modo sequenziale.
  • Obiettivo: Creare un sistema semplice, che richiedesse poca memoria e fosse facilmente implementabile sui primi microcomputer.

Timeline Specifica dello Sviluppo della FAT

  1. 1977 – Origini della FAT (FAT12):
    • La prima versione della FAT era parte del sistema operativo MDOS/MIDAS, utilizzato per i computer Altair 8800.
    • La tabella era strutturata con voci a 12 bit (da cui il nome FAT12), che consentivano di gestire fino a 4.096 cluster.
    • Pensata per floppy disk di piccole dimensioni (fino a circa 16 MB).
  2. 1980 – Microsoft acquisisce QDOS:
    • Microsoft acquista il sistema operativo QDOS, sviluppato da Tim Paterson della Seattle Computer Products, e lo trasforma in 86-DOS.
    • La FAT viene adottata come file system principale per l’86-DOS.
  3. 1981 – Lancio di MS-DOS 1.0:
    • La FAT12 viene utilizzata come file system per i computer IBM PC.
    • Supporta floppy disk e i primi hard disk, limitati a 16 MB di capacità totale.
  4. 1983 – MS-DOS 2.0 e primi miglioramenti:
    • Introduzione del supporto per directory gerarchiche.
    • Ampliamento della FAT per gestire dischi più grandi, senza cambiare la struttura a 12 bit.
  5. 1984 – MS-DOS 3.0 e FAT16:
    • La FAT viene espansa a 16 bit, permettendo di gestire fino a 216=65,5362^{16} = 65,536 cluster.
    • Supporto per dischi rigidi fino a 2 GB.
    • Necessità dettata dall’introduzione di hard disk più grandi nei PC.
  6. 1996 – Windows 95 OSR2 e FAT32:
    • La versione FAT32 introduce voci a 32 bit (utilizzando solo 28 bit effettivi), superando il limite di 2 GB imposto dalla FAT16.
    • Supporto per dischi fino a 8 TB e cluster di dimensioni più flessibili.
    • Questa versione viene progettata per tenere il passo con la crescita delle dimensioni dei dischi rigidi.

Struttura della FAT

La FAT è una tabella situata subito dopo il Boot Sector del volume. Essa contiene una voce per ciascun cluster del disco. Ogni voce registra lo stato di quel cluster o il collegamento al cluster successivo nel caso di file che si estendono su più cluster.

  • Cluster: È la minima unità di allocazione sul disco. Ogni file è memorizzato in uno o più cluster.
  • Voci nella FAT: Ogni voce ha un valore che può indicare:
    • 0: Cluster libero.
    • EOF (End of File): Indica che il cluster è l’ultimo di un file.
    • Cluster occupato: Indica il numero del cluster successivo appartenente allo stesso file.
    • Danno (bad sector): Indica un cluster inutilizzabile.

La FAT è organizzata in una struttura a catena:

  • Ogni cluster di un file punta al successivo.
  • Quando la catena finisce (EOF), il file termina.

Dimensione delle voci nella FAT

La dimensione di ciascuna voce dipende dal tipo di file system:

  1. FAT12:
    • Usa 12 bit per voce.
    • Supporta fino a 212=40962^{12} = 4096 cluster.
    • Adatto per volumi piccoli (fino a 32 MB).
  2. FAT16:
    • Usa 16 bit per voce.
    • Supporta fino a 216=65,5362^{16} = 65,536 cluster.
    • Adatto per volumi fino a 2 GB.
  3. FAT32:
    • Usa 32 bit per voce (solo i primi 28 sono utilizzati; i restanti 4 sono riservati).
    • Supporta fino a 2282^{28} cluster.
    • Adatto per volumi molto più grandi (fino a 8 TB con cluster di 32 KB).

Allocazione di un file nella FAT

Quando un file viene scritto su un volume FAT:

  1. Il file system individua il primo cluster libero nella FAT.
  2. Il cluster viene contrassegnato come occupato, e nella sua voce si inserisce il numero del cluster successivo (se il file occupa più di un cluster).
  3. L’ultima voce della catena è marcata come EOF.
  4. L’entry della directory del file punta al primo cluster della catena.

Ad esempio, un file che occupa tre cluster potrebbe essere rappresentato così nella FAT:

  • Cluster 2: Puntatore a cluster 3.
  • Cluster 3: Puntatore a cluster 4.
  • Cluster 4: EOF.

Frammentazione

Se un file viene diviso su cluster non contigui, si verifica frammentazione. Questo problema può rallentare l’accesso ai file, poiché il sistema deve seguire la catena di cluster nella FAT.

Esempio:

  • Cluster 10 -> Cluster 25 -> Cluster 30 -> EOF.

La frammentazione è comune nei file system FAT, soprattutto dopo molte operazioni di scrittura e cancellazione.

Doppia FAT

Per motivi di sicurezza, FAT12, FAT16 e FAT32 mantengono generalmente due copie della FAT:

  • Una è la tabella principale.
  • L’altra è una copia di backup in caso di errori o corruzione.

Limiti Tecnici

  1. Efficienza:
    • La gestione a catena nella FAT è semplice ma inefficiente per volumi grandi.
    • Con volumi di grandi dimensioni, la FAT può diventare molto grande, consumando memoria e tempo per le operazioni di ricerca.
  2. Overhead:
    • Con cluster di grandi dimensioni, file piccoli sprecano spazio (ad esempio, un file di 1 KB in un cluster da 32 KB occupa comunque 32 KB).
  3. Corruzione:
    • Se la FAT si danneggia, l’intero volume può diventare inaccessibile, dato che la FAT è essenziale per localizzare i file.

Vantaggi della FAT

  • Semplicità: La struttura è facile da implementare e leggere.
  • Compatibilità: Utilizzabile su quasi tutti i dispositivi e sistemi operativi.