FAT

FAT (File Allocation Table) on tiedostojärjestelmä, jonka Microsoft kehitti vuonna 1977 Microsoft Disk BASICia varten. Se on MS-DOSin ja Windows 95, 98 ja ME:n käyttämä tiedostojärjestelmä, ja sitä käytetään edelleen yksinkertaisuutensa vuoksi USB-muistien ja muistikorttien tiedostojärjestelmänä. Myös nykyisten PC-koneiden käynnistämistä hallitseva UEFI vaatii kiintolevyllä tallennustilakseen FAT32-osion.

FAT oli aiemmin yleisin käytössä oleva tiedostojärjestelmä. Se oli ainoa Microsoftin MS-DOS:in, 16-bittisten Windowsien ja Windows 95, Windows 98 ja Windows Me:n tukeva tiedostojärjestelmä. Sen yleisyyden vuoksi lähes kaikki tietokoneet ja käyttöjärjestelmät tukevat sitä jossain muodossa. FAT:issa on rajoituksia, eikä se ole enää yleisesti käytössä tietokoneissa kiintolevyillä.

FAT:sta on olemassa monta erilaista versiota, alla luettelo eri versioista ja käyttötarkoituksista:

• FAT12 on FAT:in ensimmäiselle versiolle jälkikäteen annettu nimi. Se tuki korkeintaan 32 MiB tiedostojärjestelmiä.
• FAT16 on sen DOS 3.31:ssä esitelty laajennus, joka tukee korkeintaan kahden, tai Windows NT:ssä neljän GiB tiedostojärjestelmiä.
• FAT32 on Windows 98/SE ja Windows Me -käyttöjärjestelmien oletustiedostojärjestelmä, joka tukee kahdeksan teratavun tiedostojärjestelmiä.
• VFAT tai LFN (Long File Names) on tekniikka, jolla Windows 95 ja uudemmat lisäsi FAT:iin tuen pitkille tiedostonimille.

Microsoft on kehittänyt FAT:ille joitain seuraajia, kuten xFAT, jota käyttää Xbox-pelikonsoli ja exFAT, jota Windows CE 6.0 käyttää flash-muisteilla. exFAT käyttää 64-bittisiä lukuja tiedoston koon ilmoittamiseen ja tukee siten yli 4 GB:n tiedostoja. Tiedostojärjestelmälle lisättiin tuki Windows XP:ssa optionaalisessa päivityspaketissa KB955704. Se lisättiin Windows Vistaan SP1-päivityksessä (2008). Samsung julkaisi Linuxille exFAT-ajurin vuonna 2013 ja sille oli tuki käyttäjätilan Filesystem in Userspace -levyajureissa (FUSE) 2009. Kuitenkin Microsoft julkaisi tiedostojärjestelmän spesifikaation ja luopui sen patenteista vasta 2019 osana Open Invention Network -aloitetta. exFAT lisättiin virallisesti Linux-kerneliin versiossa 5.4. Sille on nykyisin myös tuki macOS:ssa.

Tekninen katsaus

Käyttöjärjestelmän levyajurit muuntavat levykkeiden ja kiintolevyjen levypinnasta käyttämät sylinteri-, sektori- ja lukupäänumerot lineaariseksi, nollasta ylöspäin kasvavaksi luvuksi, jota MS-DOS-terminologialla nimitetään (loogiseksi) sektoriksi. Jokainen sektori on 512 tavua. Sektoreista kootaan lohkoja, jotka ovat kooltaan 2ⁿ×512 tavua. Yksi lohko tai varausyksikkö, jonka koko on 512, 1024, 2048, 4096, ..., 65536 tavua on pienin tila, joka voidaan varata tiedoston tallentamiseen.

Tiedostojärjestelmän ensimmäinen sektori, 512 tavua on varattu käynnistyslohkolle. Se sisältää myös tiedon lohkokoosta, FAT:ien määrästä ja koosta ja juurihakemiston sijainnista ja koosta (FAT12 ja FAT16). Käynnistyslohkon jälkeen voi olla varattuja sektoreita, joiden jälkeen välittömästi sijaitsevat FAT:it.

FAT (File Allocation Table), josta tiedostojärjestelmä on saanut nimensä, on yksiulotteinen taulukko lohkonumeroita. Luotettavuussyistä näitä on kaksi tiedostojärjestelmän alkupäässä. Taulukon jokainen indeksi vastaa 1:1 tiedostojärjestelmän lohkoa. Taulukon indeksiin talletettu luku on puolestaan seuraavan tiedostolle varatun lohkon numero. Osa taulukon arvoista on varattu muihin tarkoituksiin, kuten tiedoston lopun (0xFF8–0xFFF), vapaan lohkon (0), varatun (1) tai rikkinäisen lohkon (0xFF7) osoittamiseen. Huomaa että lohko 2 on ensimmäinen, jota voi käyttää.

FAT-tiedostojärjestelmässä hakemisto on taulukko 32:n tavun tietueita, joka sisältää tiedoston nimen (8+3 merkkiä), koon (4 tavua), luontiajan ja päivämäärän (+-2 sek.), sekä attribuutteja ja tiedoston ensimmäisen lohkon numeron. Tiedoston nimi tallennetaan välilyönneillä oikealta täydennettynä kenttä kerrallaan. Attribuuttikenttä sisältää tiedon siitä, onko tiedosto alihakemisto, kirjoitussuojattu, piilotettu, systeemitiedosto, osion nimi tai arkistoitu. Arkistobitti menee päälle aina tiedostoon kirjoitettaessa. MS-DOS jätti peräti 10 tavua joka hakemistomerkinnästä käyttämättä. Juurihakemisto sijaitsee yleensä FAT:ien jälkeen levyn osion alussa. FAT12 ja FAT16:n juurihakemiston koko on kiinteä ja se riippuu kiintolevyn koosta, ja on korkeintaan 512 tietuetta, mitä suuremmat määrät voivat rikkoa yhteensopivuuden.

Ensimmäisessä MS-DOSin käyttämässä FAT:in versiossa (FAT12) taulukossa oli korkeintaan 4096 (2¹²) arvoa, jotka osoittivat 512 tavun lohkoja. Tästä saatiin osion suurimmaksi osoitettavaksi kooksi 2¹²×512 tavua (tai oikeastaan 4086×512 tavua), kun 5¼"-levykkeen koko oli 160 kB. FAT12:n jokainen indeksi on 1,5 tavua. Niitä voi kätevästi selata kokonaislukuoperaatioilla jakamalla indeksi kahdella, kertomalla kolmella, hakemalla sana, ja jos indeksi oli pariton, siirtämällä lukua neljä bittiä oikealle. Ensimmäinen MS-DOSin versio ei tukenut alihakemistoja, ja juurihakemistolle oli varattu kiinteä määrä tilaa.

MS-DOS 2.0 julkaistiin maaliskuussa 1982 PC XT -koneen kanssa, jossa oli 10 MB kiintolevy. Tuossa käyttöjärjestelmäversiossa sektorin ja lohkon käsite erotettiin toisistaan. Koneen kiintolevyllä oli nyt 4 kB lohkoja. Tiedostojärjestelmä mahdollisti korkeintaan 16 MB:n kiintolevyn käytön. Vuonna 1984 PC AT -koneen yhteydessä, jossa oli 20 MB kiintolevy, julkaistiin MS-DOS 3.0. Sen myötä esiteltiin FAT16, joka laajensi FAT:in käyttämään 16-bittisiä lohkonumeroita ja salli 65 517 lohkoa. Sektorien suurin sallittua määrää osiolla ei kuitenkaan kasvatettu, mikä rajoitti osion koon 32 MB:een.

Marraskuussa 1987 julkaistiin Compaq DOS 3.31, jossa sektorien suurin määrä kasvatettiin 2³² kappaleeseen (DOS 3.31 Large File System). Se ei muuttanut merkittävästi tiedostojärjestelmää, mutta johti merkittäviin muutoksiin DOSissa, jonka oli käytettävä 32-bittisiä lukuja. Muutos oli kohtalaisen suuri, koska DOS oli kirjoitettu 16-bittisellä assemblyllä. Microsoftin MS-DOSiin tämä muutos tuli versiossa 4.0. Suurin lohkon koko oli 64 sektoria (32 kB), mikä rajoitti FAT16:n koon tulevissa DOS:in ja Windowsin versiossa 2 gigatavuun. Windows NT 4.0 tuki myös 64 kB lohkoja, joilla tiedostojärjestelmän suurin koko kaksinkertaistui. Suurempi lohkokoko aiheutti kuitenkin yhteensopivuusongelmia 16-bittisiä lukuja käyttävien ohjelmien kanssa.

Windows 95:n OSR2-päivitysversion ja Windows 98:n myötä tuli käyttöön FAT32, joka laajensi FAT:in lohkomäärän teoriassa 2²⁸:een (0x0FFFFFFF) ja tiedostojärjestelmän koon 2²⁸×32 kB (32:n kB lohkokokoolla). Nimestään huolimatta FAT32 käyttää korkeintaan 28-bitin lohkonumeroita. Tämä ei vaikuta tiedostojärjestelmän suurimpaan kokoon, jota rajoittaa sektorien määrän rajoitus 2³². Tiedoston suurin koko on edelleen 2³²−1 tavua, koska tiedoston koko tallennetaan hakemistoon neljään tavuun.

Pitkät tiedostonimet (LFN tai VFAT) on tallennettu hakkeroimalla ne useampaan hakemistotietueeseen. Nämä on merkitty hakemistolla osion nimeksi, joten MS-DOS jättää ne huomiotta. Yhteen hakemistotietueeseen saadaan ensimmäisen jälkeen tallennettua 13 UTF-16-merkkiä (26 tavua) rikkomatta yhteensopivuutta. Näitä ylimääräisiä tietueita voidaan ketjuttaa 20 kappaletta, jolloin saadaan tallennettua 255 merkkiä. VFAT tallentaa myös tarkempia tietoja tiedostosta, kuten muutospäivän ja viimeisen lukupäivän. Lisäksi luontipäivälle on varattu yksi tavu lisää, joka mahdollistaa 10 ms tarkkuuden kahden sekunnin sijaan. FAT tukee tiedostojen päivämääriä vuoteen 2107 asti.

Rajoitukset

FAT:ssä tiedoston muodostavien lohkojen luettelo on tallennettu linkitettynä listana. Tämän tietorakenteen läpikäynti vie aikaa O(n). Myös hakemiston käynti läpi on lineaarinen toimenpide. Erityisen raskas operaatio on tiedostojärjestelmän tyhjän tilan määrittäminen, jonka tekemiseksi on luettava koko FAT läpi. Tietoa tyhjän tilan määrästä ei tallenneta minnekään tiedostojärjestelmässä.

Historia

• Vuonna 1996 Microsoftille myönnettiin patentti FAT-tiedostojärjestelmään.
• Vuonna 2006 Microsoft alkoi periä rojalteja myymällä FAT-lisenssejä (englanniksi).
• Microsoft julkaisi exFATin dokumentaation elokuussa 2019.

Katso myös

• NTFS

Lähteet

• MS-DOS Partitioning Summary (Microsoft)
• An Inside Look at MS-DOS (Arkistoitu – Internet Archive) (Tim Paterson)
• Example File Systems (Andrew S. Tanenbaum; Modern Operating Systems 2nd Edition)
• Understanding FAT32 Filesystems (PJRC)