Historie diskových souborových systémů

Zdeněk Hrnčíř, 2005

Motivace zavádění souborových systémů

V počátcích výpočetní techniky byly programy nahrávány do počítače prostřednictvím děrných štítků, zadávány přímo z klávesnice či zaváděny jiným, z dnešního pohledu bizardním, způsobem. Ovšem už tehdejší program vyděrovaný na děrné pásce bychom mohli nazývat souborem. Souborem totiž rozumíme kolekci bytů, která je uchovávána jako samostatná, zpravidla pojmenovaná, entita na nějakém záznamovém médiu [1]. O správu souborů - programů se tehdy starala obsluha výpočetního střediska. Její úlohou bylo vyhledávat v archivech příslušné děrné pásky či texty strojových kódů, zajistit jejich spuštění, třídit do archivů a v neposlední řadě zajistit jejich fyzické odstranění, pokud přestaly být potřebné.

S klesající cenou strojového času začaly postupně přebírat roli obsluhy specializované programy - monitory - zárodky dnešních operačních systémů. Mezi úlohy monitorů patřila i automatizace I/O operací. I/O operacemi byly zpočátku výhradně čtení a zápis z/na děrnou pásku či štítek. Což samozřejmě nikterak neoprostilo obsluhu od povinnosti ručně zakládat pásky a spravovat jejich archiv.

Lineární souborové systémy

Teprve s možností uložit na médium větší množství dat a tedy i větší počet souborů se začaly objevovat první souborové struktury - souborové systémy (file systems - FS). Jejich hierarchie byla zprvu lineární. Jinými slovy nebylo možné vytvářat adresářovou stromovou strukturu. Označujeme je jako ploché souborové systémy. Takový způsob ukládání dat odpovídal lineárnímu zápisu na pásková záznamová média.

Hierarchické souborové systémy

Myšlenka strukturovat data hierarchicky je pravděpodobně velice stará. Za první implementaci je považován FS operačního systému Multics. Jeho vlastnosti vycházejí z článku z roku 1965 [2]. Podívejme se na některé z nich podrobněji:

FS Multicsu tedy zavádí hierarchickou stromovou strukturu. Vnitřními uzlu stromu jsou speciální soubory, označované jako adresáře (directory), které obsahují adresářové položky (directory entry). Ty buď odkazují přímo na podřazené soubory (adresáře), nebo na jiné adresářové položky. FS tak umožňuje vytvářet spoje (links), které mohou odkazovat soubory umístěné v jiných adresářích. Tyto spoje lze pojmenovávat různými názvy. Jedna a tatáž data tak lze zpřístupnit z různých částí stromové struktury pod různými jmény. Tato vlastnost je důležitá pro víceuživatelské prostředí, jakým byl právě OS Multics. Proto také Multics zavádí řízení přístupu na úrovni souborů v podobě seznamů řízení přístupu (Access Control Lists). Každý soubor má přidružen seznam, krerý uděluje jednotlivým uživatelům práva pro různé způsoby zacházaní se souborem. Rozlišované způsoby práce se souborem jsou:

Krom toho je možné aktivovat past (trap), která je volána pokaždé, když se uživatel pokusí přistoupit k souboru, a na základě jejího vyhodnocení je přístup udělen, či nikoli. Jako past lze volat libovolnou proceduru. Jedná se tedy o univerzální nástroj pro řízení přístupu.

FS Multicsu byl velice pokrokový a jeho principy převzal Unix a jeho následníci.

Unix FS (1970)

První implementace Unixu byla ve verzi pro stroje PDP-7 a je proto označováma jako PDP-7 Unix [3]. Jeho FS byl strukturálně velmi podobný dnešnímu Unixu. Základem byl seznam i-uzlů (i-nodes), které obsahovaly záznamy o typu, velikosti, ochranném módu souboru a seznam bloků (datových jednotek) s vlastním obsahem souboru. Adresáře byly, podobně jako u Multicsu, speciální soubory obsahující čísla i-uzlů podřazených souborů s jejich názvy. Taktéž bylo možné vytvářet spoje. Hlavním podstatným rozdílem byla nemožnost specifikovat soubory pomocí cest (path names) ve stromové struktuře. Tento nedostatek mohl být teoreticky obcházen pomocí spojů spolu s existencí domácího adresáře (home directory) přístupného odkudlkoli pod názvem „dd“. V praxi byl tento způsob natolik neobratný, že uživatelé raději možnost vytváření podadresářů nepoužívali. Hned v další verzi Unixu pro PDP-11 byla adresace pomocí cest přidána. Zajímavostí také je maximální velikost souborů, která činila 64KB.

Pokročilejší verze Unixu - Unix Systém V obsahovala S5FS, někdy označovaný jako FS [4]. Objevily se dodnes používané termíny superblok a mounting. Superblok obsahuje základní charakteristiky FS. Mounting zase poskytuje mechanismus pro jednotnou hierarchii obsahující všechna připojená paměťová zařízení. S5FS byl z aplikačního pohledu téměř identický s novějšími FS Unixu. Obsahoval architekturu pro spojování i-uzlů do vrstev. V podstatě se jedná o vytváření stromové hierarchie i-uzlů na úrovni jednoho souboru. To vedlo k navýšení maximální velikost souborů - na tehdy neuvěřitelných 1GB. Jeho následovníci: FFS - Fast File System (1983), UFS1 (1994), UFS2 (2002) - Unix File System přinesli postupně podporu větších souborů a disků a zvýšili rychlost přístupu k datům. Toho bylo docíleno především umístěním dat a příslušných i-uzlů na blízké válce disku, aby byla minimalizována doba vystavení diskových hlav.

CP/M (1974)

Operační systém CP/M (control program/ monitor) ovládl éru prvních osobních počítačů. Jeho primární vlastností proto byla co nejmenší paměťová náročnost při poskytování základních uživatelských funkcí. Jeho součástí byla vlastní organiace souborů [5] určená pro pružné disky o kapacitě 180 KB. I proto byl souborový systém podstatně jednodušší než tou dobou existující FS Unixu. Systém měl pouze kořenový adresář, který obsahoval záznamy popisující jednotlivé soubory. Součástí záznamů byly:

Jména souborů byla omezena na schéma 8.3 (název 8 znaků, přípona 3 znaky), které později převzal MS-DOS. Vzhledem k velikosti bloku 1KB, byla maximální velikost souboru 16KB. Toto omezení bylo později překročeno tak, že větší soubory obsadily více záznamů v kořenovém adresáři. Systém nebyl schopen určit přesně velikost souboru. Bylo na zodpovědnosti aplikačního programátora, aby zajistil svůj soubor zvolenou značkou End Of File.

I přes svoji jednoduchost, a možná právě proto, se CP/M těšil velké oblibě.

File Allocation Table (1980)

FAT (File Allocation Table) se objevil spolu s operačním systémem DOS firmy Microsoft a stal se přímým nástupcem CP/M z něhož vycházel. První verze proto zachovávají formát názvů 8.3.

Základem všech verzí FS je alokační tabulka souborů (File Allocation Table). Ta obsahuje tolik záznamů, kolik je v systému alokačních jednotek (clusterů). Alokační jednotka může být přidělena nejvýše jednomu souboru. Její velikost je závislá na velikosti média a použité verzi FAT. Soubory, které přesahují velikost jedné alokační jednotky jsou rozděleny mezi více jednotek (ne nutně následujících) a v alokační tabulce jsou odpovídající záznamy zřetězeny. Záznamy v alokační tabulce obsahují jednu z následujícíh položek:

Krom toho je součástí souborového systému:

FAT12 (1980)

Takto je označována první verze FAT. Jelikož systém FAT12 byl primárně určen pro pružné disky, obsahoval řadu omezení. Stejně jako CP/M měl pouze kořenový adresář bez podadresářů. Velikost disku v počtech sektorů byla uložena na 16 bitech. Při standardní velikosti sektoru 512B to znamenalo omezení na 32MB.

S novější verzí MS-DOSu byl rozšířen počet alokočních jednotek, což vedlo ke zmenšení jejich velikosti a lepšímu využití prostoru (snížení vnitřní fragmentace). Také byla zavedena hierarchická struktura pomocí podadresářů. Té bylo docíleno specifikací adresářových tabulek (directory table), což jsou speciální soubory analogické i-uzlům v Unix FS. Jsou uloženy v datové oblasti a obsahují především záznamy se jmény, atributy a odkaz na prví článek řetězu v alokační tabulce. Podstatnou nevýhodou této koncepce oproti i-uzlům je skutečnost, že pro zpřístupnění dat souboru v podadresáři je vždy nutné nejprve zpřístupnit záznamy v alokační tabulce.

FAT16 (1983)

Pouze rozšířil maximální velikost disku tím, že byla uváděna počtem alokačních jednotek nikoli počtem sektorů. Současné zvětšení maximální velikosti alokační jednotky na 32KB odpovídalo nejvýše 2GB diskům.

FAT32 (1996)

Opět přinesl pouze navýšení maximální kapacity disku zvětšením počtu alokačních jadnotek na 4 177 920 (< 224), což odpovídá 124, 55 GB.

Macintosh File System (1984), Hierarchical File System (1985)

MFS byl vytvořen firmou Applle Computer pro jejich první počítače řady Macintosh. Byl určen pro použití s 400KB pružnými disky. Podobně jako CP/M a první verze FAT12 nevytvářel hierarchickou adresářovou strukturu. Zato bylo možné používat dlouhé názvy souborů (255 znaků) a operační systém využíval ukládání metadat pro běh grafického rozhraní. O rok pozdeji byl nahrazen systémem HFS (Hierarchical File System). Jak název napovídá přinesl hierarchickou adresářovou strukturu implementovanou pomocí B+ stromu.

Amiga Old File System (1985), Fast File System (1987)

Amiga přišla s vlastním souborovým systémem, který byl určen pro pružné disky. Označení „ old “ mu bylo přiřknuto po uvedení FFS (Fast File Fystem). OFS pracoval s podadresáři a dovoloval vytvářet spoje na soubory. Jeho architektura je poměrně zajímavá. Používal atypické kódování dat na záznamové vrstvě, takže na pružné disky s vysokou hustotou (HD floppy) se vešlo 1 760KB. Záznam s kořenovým adresářem byl umístěn uprostřed disku, což ztěžovalo použití systému pro jiné než pružné disky. Zajímavou koncepcí bylo použití hashovací tabulky pro adresářové položky. Pro zpřístupnění souboru byl nejprve spočítán hash z jeho názvu. V příslušném bloku popisujícím adresář byla na základě hashe zpřístupněna adresa, na které se nacházel blok popisující žádaný soubor (resp. adresář). V případě, že dva soubory v adresáři měly stejný hash, byly zřetězeny jejich popisující bloky [6].

FFS přinesl především podporu pevných disků a výrazné zrychlení. Toho docílil zavedením vyrovnávací paměti pro adresáře a odstraněním redundantních informací.

Novodobé Souborové Systémy

Výše uvedené souborové systémy jsou průřezem historicky významných nebo zajímavých koncepcí. Pro moderní, dnes nejrozšířenější, souborové systémy lze nalézt jeden spojující charakter - žurnálování. Žurnálový souborový systém obsahuje speciální datové struktury, do kterých zapisuje prováděné změny. Přibližuje se tak více databázovému systému, který zajišťuje bezvadnou konzistenci dat i při výpadku systému. Jelikož tyto systémy jsou současností a nikoli historií, uvedu na závěr pouze několik názvů: JFS (Journaling File System), ReiserFS, ext3, NTFS (New Technology FS).


Použité zdroje

Odkazované z textu

[1] Answers.com, http://www.answers.com/file
[2] R. C. Daley, P. G. Neumann, "A General-Purpose File System For Secondary Storage", http://www.multicians.org/fjcc4.html
[3] Dennis M. Ritchie, "The Evolution of the Unix Time-sharing System", http://cm.bell-labs.com/cm/cs/who/dmr/hist.html
[4] "Beginnings of the UNIX filesystem", http://cs-exhibitions.uni-klu.ac.at/index.php?id=216
[5] Andrew Tanenbaum, "Example File Systems" http://www.phptr.com/articles/article.asp?p=25878&seqNum=3&rl=1
[6] Laurent Clévy, The ADF (Amiga Disk File) format FAQ, http://lclevy.club.fr/adflib/adf_info.html

Další zdroje