Root » Servers » » Harde schijf » » Onderverdeling » » FAT
File Allocation table
zo eenvoudig en zo goed
F A T
De FAT is de basisstruktuur van de gelijknamige bestandsorganisatie. De directory verwijst naar de eerst positie van een bestand, maar waar zitten de volgende delen van het bestand? In theorie zitten de stukken mooi achter elkaar (als het bestand in één keer geschreven wordt), maar vaak zitten de stukken her en der verspreid over de volume.
-

-

Blokken en clusters

Niet alle miljarden bytes zijn individueel adresseerbaar. 512 opeenvolgende bytes vormen een blok: dit is de kleinst mogelijke adresseerbare eenheid. Vroeger was de benaming een sector op de schijf en deze benaming blijft in gebruik terwijl die tegenwoordig verkeerd is). Bij geheugenkaartjes is een blok vaak 4k groot.

Bij een partitie met een grote capaciteit (bijvoorbeeld 1GB) is het aantal blokken te groot (2 miljoen) om een efficiente toegang mogelijk te maken. Het beheer van al die blokken zou te veel rekenwerk vergen. Daarom worden de blokken gegroepeerd tot clusters. Een cluster bevat bijvoorbeeld 32 opeenvolgende sectoren. Onze schijf van 1GB bevat 62.500 clusters, wat doenbaar is.

Opgelet: de onderverdeling in clusters is enkel van toepassing op de data-ruimte (directories en bestanden), maar het begin van de data-ruimte op de schijf moet op een cluster-boundary vallen. Een bestand (directory of data-bestand) gebruikt altijd minstens één cluster. Bij kleine opslagmedia komt een cluster overeen met een sector. Het groeperen van blokken tot clusters wordt ook in andere disk-formaten zoals NTFS gebruikt.

Inhoud van de volume
Rechts heeft u de onderverdeling van een partitie. De eerste twee sectoren zijn de boot-sector en de extended sector, dan volgt de FAT. In deze “technische ruimte” wordt er vaak een tweede copie van de bootsector en de FAT opgenomen. Bij FAT-12 en FAT-16 zit de root directory ook in de technische ruimte (en heeft dus een vaste lengte en een beperkt aantal links naar files).

De data-ruimte bevat de bestanden (zowel directories als gewone data-bestanden). De onderverdeling is clusters is hier niet gedaan wegens het klein aantal beschikbare blokken.

Bij het formateren wordt eerst de root directory geschreven. Later wordt bestand-1 geschreven, bestaande uit 14 blokken. De directory bevat een verwijzing naar het begin van het bestand, zodat achteraf het bestand gelezen kan worden. Dan wordt bestand-2 geschreven, en bestand-1 wordt uitgebreid. Het bijkomend stukje van bestand-1 wordt extend genoemd. Dan wordt bestand-2 ook langer gemaakt. Als laatste wordt bestand-3 geschreven, maar in dit hypothetisch voorbeeld blijkt dat de directory te klein is om de verwijzing naar bestand-3 te bevatten: eerst wordt de directory uitgebreid met een extend, en dan wordt bestand-3 geschreven.

Hoe kunnen nu de stukken bij elkaar geraapt worden bij het lezen van een bestand? Door de FAT. De fat is eigenlijk een linked list, één van de basisstrukturen bij bestandsorganisatie. De linked list bevat ENKEL een verwijzing naar het volgend element uit de lijst, de verwijzing naar de plaats van de data in de data-area is zuiver IMPLICIET. De positie van een element in de tabel komt overeen met de fysische plaats op de data-area van de volume.

Inhoud van de FAT
Onze directory is 4 blokken lang en bestaat uit twee stukken. De linked list van de directory is 2-3-29-0 (ieder element verwijst naar het volgend element uit de lijst). We gebruiken de waarde 0 om het einde van de lijst aan te geven (onze tabel heeft geen element nul, de telling begint bij 1)

De layout van de bestanden op de schijf komt overeen met de gelinkte lijsten in de FAT tabel.

We onderlijnen in het rood de entry points van onze linked list (verwijzingen vannuit de directory).

Praktische implementatie en voorbeeld

De tabel bestaan uit elementen van 12 bits bij FAT-12 (gebruikt met floppies), 16 bits bij FAT-16 (gebruikt bij kleine schijven en geheugenkaarten) en 28 bits bij FAT-32. Het data-gebied kan dus 4.096, 65.539 of 268.435.456 clusters bevatten. In ons praktisch voorbeeld, de schijf van 1GB met clusters van 32 sectoren (16kB) is de FAT 125.000 bytes groot, of 0.125% van de totale capaciteit, wat een uitstekende prestatie is.

Een minpunt is dat we met clusters van 16kB zitten. In het ergste geval (een bestand van één byte) verliezen we 16383 bytes per bestand (slack). In het geval de schijf gebruikt wordt voor foto's (500 foto's à 2MB) dan verliezen we gemiddeld 8.192 bytes per 2MB (minder dan een half percent), wat heel redelijk is.

Bij de praktische implementatie worden de eerste twee elementen van de FAT niet gebruikt als tabelelement, maar bevatten housekeeping-informatie: of de volume correct afgesloten werd en de plaats van de eerste vrije blok.

Voordelen

Het FAT systeem is bijzonder eenvoudig. Het kon worden gebruikt met de eerste computers die slecht over beperkte rekenkracht konden beschikken en maar weinig geheugen aan boord hadden. Ook embedded systemen en digitale fototoestellen gebruiken dit formaat. Bij de huidige computers wordt de volledige FAT in het geheugen geladen, wat een zeer snelle verwerking mogelijk maakt.

De overhead is zeer beperkt: de fat neemt weinig plaats in beslag en maakt het mogelijk de stukken van een bestand snel op te sporen. Ook bij het schrijven zijn er weinig operaties nodig: data schrijven, fat aanpassen, directory element schrijven (in die volgorde). Met slechts drie schrijfopdrachten wordt een bestand op schijf opgeslagen.

Daarbij komt nog dat het FAT filesysteem patent-vrij is. Microsoft heeft die willen breveteren, maar dat lukte enkel voor bepaalde specifieke extensies, namelijk de voorziening voor lange bestandsnamen. Daarom hebben de foto's op een geheugenkaart altijd een naam DSC-1234.JPG (8.3 naam) en kan het fototoestel de foto niet meer tonen indien je de foto een langere naam geeft: het fototoestel mag geen software aan boord hebben om die lange namen te herkennen.

Nadelen

Tja, het is tè eenvoudig! Het formaat werd in het leven geroepen toen de computers nog heel rudimentaire machines waren.
  • De tijdindicatie van bestanden is niet nauwkeurig op de milliseconde (maar dat kan niemand schelen).
  • ACL wordt niet ondersteund (Access Control List: dat wil zeggen toegangscontrole tot bepaalde bestanden) en ADS ook niet (Alternate Data Stream, een zeer gevaarlijke mogelijkheid van NTFS).
  • Er is geen systeem voorzien om fragmentatie van de bestanden te beperken: een nieuw bestand of een extend wordt geschreven op de eerste vrije plaats (maar geheugenkaarten hebben geen last van bestandsfragmentatie: ze kunnen even snel bestanden lezen die uit duizenden stukjes bestaan als bestanden die uit één stuk bestaan).
Die nadelen zijn allemaal dingen waarvan de mensen niet wakker van liggen. Maar het FAT heeft één groot naddel: de maximale bestandsgroote van 4GB. In het begin leek deze limiet onhaalbaar:

Operating
system
Schijfruimte
nodig voor OS
Werkgeheugen
(minimum)
Capaciteit
harde schijven
DOS 6.23.5MB640kB10MB
Windows 95100MB1MB4.3GB
Windows XP1GB128MB80GB
Vista4GB1GB (theorie)250GB

4GB, dat is te weinig voor een videofilm, te weinig voor een back up, te weinig,... te weinig,... te weinig,... weg met die rommel waarop wij geen patent hebben! Daarom ook dat microshit windows weigert een partitie als FAT te formateren als die meer dan 32GB capaciteit heeft. 32GB... dat is de capaciteit van de huidige geheugenkaarten! De geheugenkaarten zal je dan in het toestel zelf moeten formateren, of gebruik maken van linux (FAT-32 kan werken met volumes tot 2TB).

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