8. Implementace systemu souboru

Jak jiz jsme rekli, system souboru provadi mechanismy on-line ukladani a pristupu k datum i programum. System souboru je ulozen na odkladacim zarizeni, jehoz hlavnim ukolem je neustale uchovavat velke mnozstvi dat. Nyni si vysvetlime aspekty tykajici se uchovavani a pristupu k souborum na zatim nejpouzivanejsim mediu, magnetickem disku. Ukazeme si postupy, jak alokovat diskovy prostor, jak ho uvolnovat, jake jsou navaznosti ostatnich casti vypocetniho systemu na odkladaci prostor.

8.1. Struktura systemu souboru

Disky predstavuji plochu, na ktere je udrzovana odkladaci pamet. Aby I/O prenos mezi diskem a pameti byl co nejefektivnejsi, je organizovan do bloku. Blok je jednotka I/O prenosu mezi diskem a pameti a predstavuje jeden nebo vice diskovych sektoru. Diskovy sektor muze byt velikosti 32 - 4096B, vetsinou byva 512B. Disk ma dve hlavni charakteristiky, ktere z nej delaji vhodne medium pro odkladaci prostor:

Muze byt prepsan na konkretnim miste - je mozno nacist blok do pameti, modifikovat a pak vratit zpet na totez misto
Je mozno adresovat kterykoliv konkretni blok informaci na disku. K souboru je tedy mozno pristupovat jak sekvencne, tak i nahodne a prepinat mezi ruznymi soubory pouhym presunem cteci hlavy a pockat az se disk ototci.

8.1.1. Organizace systemu souboru

Pri tvorbe systemu souboru je treba vyresit dva hlavni problemy. Prvni problem je definovat, jak bude vypadat system souboru z hlediska uzivatele. Tato uloha vyzaduje definovat soubor, jeho atributy, operace se souborem a adresarovou strukturu potrebnou k organizovani souboru. Za druhe je treba vytvorit algoritmy a datove struktury, ktere umozni mapovani teto logicke struktury na fyzicke zarizeni.
System souboru byva obecne definovan do nekolika urovni. Priklad takove struktury je na nasledujicim obrazku. Kazda uroven na obrazku vyuziva vlastnosti urovne nizsi k vytvoreni vlastnosti vyuzitelnych na urovni vyssi.

Obr. 81 Urovne systemu souboru

Nejnizsi uroven - I/O rizeni - tvori ovladace jednotlivych zarizeni (device drivers) a obsluha preruseni zajistujicich prenos mezi pameti a diskem. Ovladac zarizeni muze byt chapan jako prekladac. Jeho vstupem je prikaz vyssi urovne (napr. nacti blok 123) a vystupem sekvence hardwarovych instrukci, ktere uzije hardwarovy ovladac, ktery tvori rozhrani mezi diskem a vypocetnim systemem.

Ovladac zarizeni vetsinou zapise specificky sled bitu na specialni misto v pameti hardwaroveho I/O ovladace a tim mu sdeli typ operace a misto na zarizeni, kde bude dit operace provedena.

Zakladni system souboru je zapotrebi na to, aby prevedl I/O pozadavek do tvaru pochopitelnemu ovladaci zarizeni (kazdy fyzicky blok je identifikovan svou numerickou adresou, napr. drive 1, cylinder 73, surface 2, sector 10).

Modul organizace souboru provadi rozhrani mezi logickym a fyzickym systemem soubor. Ma informace o souborech a jejich logickych blocich, stejne jako o fyzickych blocich. Podle pouziteho mechanismu alokce a pri znalosti o ulozeni souboru je modul organizace souboru schopen prevest logickou adresu bloku na fyzickou, kterou potrebuje zakladni system souboru k zajisteni I/O operace. Kazdy logicky blok souboru ma sve cislo od 0 (resp. 1) po N, zatimco fyzicke bloky vetsinou neobsahuji data v tomto logickem usporadani, takze je treba prevod cisla bloku z logickeho na fyzicke.

Modul organizace souboru v sobe zahrnuje manazer volneho prostoru, ktery prochazi nealokovane bloky a dava je na pozadani k dispozici modulu organizace souboru.

Logicky system souboru uziva adresarovou strukturu a symbolickych jmen souboru k tomu, aby modulu organizace souboru podaval zminene informace. Logicky system souboru take zajistuje ochranu a zabezpeceni.
Chce-li aplikacni program vytvorit novy soubor, zavola logicky system souboru. Logicky system souboru zna format adresarove struktury. Pro vytvoreni noveho souboru nacte do pameti obsah patricneho adresare, zapise do nej novou polozku a ulozi ho zpet na disk. S adresarem muze byt nakladano jako se souborem, ktery ma indikacni polozku definujici, ze se jedna o adresar. Po aktualizaci adresare tedy muze logicky system souboru zavolat modul organizace souboru aby namapoval adresar na cisla diskovych bloku, ktera mu patri v zakladnim systemu souboru a v systemu I/O operaci.
Jakmile je adresar aktualizovan, muze ho vyuzit logicky system souboru k vykonani I/O operaci. Je-li soubor otviran, je v nem treba nalezt polozku patrici otviranemu souboru. Aby nemuselo byt toto prohledavani vykonavano pred kazdou I/O operaci, OS vetsinou uklada adresarove polozky otevrenych souboru do pameti do tabulky otevrenych souboru (urychleni, zjednoduseni).
Prvni odkaz na soubor (vetsinou operace open) vyvola prohledani adresare a zkopirovani patricne polozky do tabulky otevrenych souboru v pameti. Ukazatel do teto tabulky (file deskriptor nebo file control block) vrati operace open a vsechny operace se souborem po ni nasledujici se odvolavaji prostrednictvim ukazatele na tuto polozku. Kdyz je soubor uzavren vsemi uzivateli, kteri ho otevreli je adresarova polozka z tabulky opet zkopirovana na sve misto na disku.

Obr. 82 Typicka tabulka otevrenych souboru

Nektere systemy rozvijeji toto schema uzitim viceurovnovych tabulek. Napr. v BSD Unix ma kazdy proces svou vlastni tabulku otevrenych souboru, ktera pouze ukazuje do systemove tabulky otevrenych souboru, ktera ukazuje do tabulky aktivnich inods. Tabulka aktivnich inods je cache prave uzivanych inods v pameti a obsahuje polozky odkazujici na diskove bloky. BSD Unix je typicky svym uzitim cache kdekoliv je to mozne. Uziti teto cache miva az 85% ucinnost.

8.1.2. Pripojovani (Mounting) systemu souboru

Stejne jako musi byt soubor nejdrive otevren (volanim open), musi byt i system souboru nejdrive pripojen, nez budou soubory na nem ulozene pristupne procesum. OS zna jmeno kazdeho zarizeni a jeho umisteni v celkove strukture souboru tzv. bod pripojeni (mounting point). V Unixu napr. system souboru obsahujici domaci adresare uzivatelu muze byt pripojen do adresare /home. V adresovani vsech souboru na nem ulozenych je treba na prvnim miste uvest adresar /home (napr. /home/sarka/book. Pokud by tento system souboru byl pripojen do adresare /user, byla by cesta k temuz souboru /user/sarka/book.
Nejdrive system zkontroluje, jestli zarizeni obsahuje korektni system souboru. Udela to tak, ze vyzada od ovladace zarizeni adresar zarizeni a zkontroluje ho, jestli ma predpokladany format. Na zaver OS zaznamena ve sve adresarove strukture, ze system souboru je pripojen na bode pripojeni. Toto schema umoznuje OSu prenaset systemy souboru v adresarove strukture jak je zapotrebi.
Jak je to u MacOSu? Jakmile tam OS poprve zaznamena disk (pevne disky jsou zaznamenany pri bootovani systemu, floppy disky kdyz je do nich poprve vlozena disketa), MacOS hleda na tomto zarizeni system souboru. Pokud ho najde, automaticky pripoji disk na koren adresaroveho stromu a zobrazi ikonu tohoto disku se jmenem systemu souboru (to je ulozeno v adresari zarizeni) na pracovni plose. Uzivatel potom muze kliknutim na ikonu zobrazit nove pripojeny system souboru.

8.2. Metody alokace

Moznost primeho pristupu k disku dava siroke moznosti v implementaci souboru.Zasadnim problemem je, jak alokovat diskovy prostor pro tyto soubory, aby disk byl vyuzit co nejefektivneji a pristup k souborum co nejrychlejsi. Existuji tri hlavni metody alokace diskoveho prostoru: souvisla (contiguous), spojovana (linked) a indexovana (indexed) alokace. Kazda metoda ma sve vyhody i nevyhody. Jsou OSy, ktere implementuji vsechny tri metody, ve valne vetsine vsak system uziva metodu jednu.

8.2.1. Souvisla alokace

V souvisle alokaci kazdy soubor obsazuje sled za sebou jdoucich diskovych bloku. Adresovani na takovem disku je linearni. Poznamenejme, ze pristup k bloku b+1, bylo-li pred tim pristupovano k bloku b nevyvola vetsinou posun cteci hlavy. Kdyz je presun hlavy nutny (z posledniho sektory predchazejiciho cylindru na prvni sektor nasledujiciho cylindru, je to posun pouze o jednu stopu.
Pocet nutnych vyhledavani k alokovani souboru je tedy minimalni. Tato metoda alokace vede k dobrym vykonum napr. OSu fy IBM - VM/CMS.
Souvisla alokace souboru je dana diskovou adresou prvniho bloku a delkou soboru v blocich. Jestlize je soubor dlouhy n bloku a adresa prvniho bloku je b, potom tento soubor zabira bloky b, b + 1, b + 2, ..., b + n - 1. Adresarova polozka kazdeho souboru potom obsahuje adresu prvniho bloku a delku prostoru alokovaneho tomuto souboru (viz. nasledujici obrazek).
Pristup k souboru, ktery byl alokovan souvisle je jednoduchy. Pri sekvencnim pristupu si system pamatuje adresu naposledy cteneho bloku a pokud je treba, nacte blok nasledujici. Pri primem pristupu k bloku i souboru, ktery je ulozen od bloku b je treba nacist blok i + b. Souvisla alokace tedy podporuje jak sekvencni, tak i primy pristup k souboru.

Obr. 83 Souvisla alokace diskoveho prostoru

Potiz souvisle alokace spociva v nalezeni dostatecne velkeho souvisleho prostoru k ulozeni noveho souboru. Je treba uzit nejakeho mechanismu managementu volneho diskoveho prostoru.
Uziti kontinualni alokace s sebou prinasi take znacnou vnejsi fragmentaci disku. Tak, jak je diskovy prostor alokovan pro jednotlive soubory a tyto soubory jsou potom opet mazany, rozpada se disk do malych volnych oblasti. Problem nastava v okamziku, kdy ani nejvetsi mala oblast nestaci na vyplneni pozadavku o ulozeni souboru. V zavislosti na velikosti diksoveho prostoru a prumerne velikosti souboru muze byt fragmentace velkym ci malym problemem.
Nektere starsi mikropocitacove systemy uzivaly kontinualni alokaci na floppy discich. Aby zabranil mozne fragmentaci, pouzivali preskupovaci rutinu, ktera cely system souboru z diskety nakopirovala na jinou nebo na magnetickou pasku. Puvodni disk byl tedy cely uvolnen a vytvorila se na nem jedna velka souvisla volna oblast. Potom byly soubory na disketu nakopirovany zpatky a tvorily na ni souvislou oblast. Tak byla zajistena celistvost prostoru s ulozenymi soubory a eliminovana fragmentace. Cenou za to byl ovsem cas. Cely proces realokce trval hodiny a mnohdy byl zapotrebi kazdy tyden. Behem casu, kdy system provadel realokaci nebylo mozno provadet nic jineho.
Kontinualni alokace s sebou prinasi i dalsi problemy. Jednim z nich je zjistit, kolik diskoveho prostoru bude pro ukladany soubor potreba. V okamziku vzniku souboru je treba nalezt a alokovat mu diskovy prostor pro jeho celou budouci velikost. Jaka ale bude? Pokud napr. pouze kopirujeme existujici soubor, je odpoved na tuto otazku jednoducha. Obecne vsak velikost nejakeho napr. vystupniho souboru lz jen velmi tezko dopredu urcit.
Pokud na zacatku alokujeme prilis maly prostor, muze se stat, ze od urciteho okamziku jiz nemuzeme soubor zvetsit. Reseni tohoto problemu je dvoji. Ukoncit program, ktery soubor vytvari s patricnou chybovou spravou. Potom musi uzivatel na pocatku alokovat pro soubor vetsi prostor a spustit program znovu. Tent postup muze byt velice drahy na vypocetni cas. Aby tomu uzivatele predesel, nadefinuje na pocatku veliky prostor pro soubor, coz ma potom za nasledek nevyuzite prostory uvnitr prirazenych diskovych bloku.
Druhym resenim drive uvedeneho problemu ja nalezt vetsi souvisly prostor na disku, soubor tam prekopirovat a uvolnit disk na jeho predesle lokaci. K teto operaci muze dochazet pomerne casto a bude spotrebovavat vypocetni cas systemu. Navzdory tomu, ze uzivatel v tomto pripade neni explicitne informovan o tom, co se deje, zjisti to velmi brzy z toho, ze vypocetni rychlost je stale mensi a mensi.
I kdyz je predem znama maximalni velikost souboru, muze byt tento mechanismus alokace velmi neucinny. Uvazme soubor, ktery muze dosahnout ohromne velikosti, ale jeho prirustky jsou male a pomale. V tom pripade sobour dlouhou dobu zabira zcela zbytecne diskovy prostor a dochazi k vnitrni fragmentaci.
Aby zabranily alespon nekterym ze zminovanych nedostatku, uzivaji nektere OSy modifikovany algoritmus souvisle alokace. Na zacitku naalokuji souboru urcity celistvy kus diskoveho prostoru. Pokud tento prostor casem neni dostatecny, je souboru pridelen dalsi souvisly usek jako extend. Udaje o blocich souboru potom obsahuji adresu prvniho bloku, pocet bloku a spojeni na nasledujici extend blok.

8.2.2. Spojovana alokace

Spojovana alokace resi vsechny problemy alokace kontinualni. Pri spojovane alokaci je kazdy soubor spojovym seznamem diskovych bloku a tyto bloky mohou byt rozmisteny kdekoliv na disku. Kazda adresarova polozka obsahuje ukazatel na prvni a posledni blok souboru. Napr. soubor obsahujici 5 bloku muze zacinat na bloku 9, pokracovat blokem 16, pak blokem 1, 10 a na zaver blokem 25 (viz nasledujici obrazek).

Obr. 84 Spojovana alokace diskoveho prostoru

Kazdy blok obsahuje ukazatel na nasledujici blok. Tuto ukazatele nejsou uzivateli pristupne. Tzn, ze jestlize velikost bloku je 512 B a adresa bloku zabira 4 B, je uzivatelsky pristupno pouze 508 B v kazdem bloku.

Chceme-li vytvori novy soubor, jednoduse vytvorime novou polozku v adresari, ukazatel na prvni diskovy blok inicializujeme na hodnotu nil. a velikost souboru je stanovena na 0. Zapis do souboru vyvola zadost o volny blok, ktery nalezne modul managementu volneho prostoru. Do tohoto bloku bude proveden zapis a bloku bude pripojen na konec souboru. Pri cteni souboru jednoduse nacitame jednotlive bloky, tak jak je na sebe vazi ukazatele.

Nedochazi tu k zadne vnejsi fragmentaci, nebot k vyplneni zadosti o novy blok muze byt pouzit kterykoliv z volnych. Neni zde take treba dopredu deklarovat velikost souboru pri jeho vytvareni. Soubor muze postupne narustat tak dlouho, dokud budou na disku volne bloky. Stejne tak neni treba provadet zadne zhustovani.

Presto ma spojovana alokace sva uskali. Hlavni problem je, ze efektivne muze byt uzita pouze pro sekvencni pristup k souboru. Chci-li ale najit i-ty blok souboru, musim sve hledani zacit na prvnim bloku a i krat se posunout po ukazeteli z bloku na blok. Kazdy takovy presun vyzaduje nacteni informace a nekdy posun po disku. Spojovana alokoce ma tedy spatnou podporu primeho pristupu k disku.

Dalsi nevyhodou je diskovy prostor nutny k ukladani ukazatelu. Jestlize je na ukazatel treba 4 B pri 512 B blocich, je 0.78% diskoveho prostoru uzita pro ukazatele a ne pro uzivatelske informace. Kazdy soubor tedy zabira vice mista nez pri jine metode alokace.
Castym resenim tohoto problemu je seskupeni bloku do vetsich celku zvanych clusters a alokovani clusteru, nikoli bloku. System souboru muze napr. definovat velikost klasteru na 4 bloky a tento klaster definovat jako jednotku prace s diskem. Ukazatele potom zaberou na disku mnohem mene mista. Tento pristup zajisti jednoduche mapovani logickych bloku na fyzicke a zvysi se vsak propustnost disku (neni treba tolik presunu po disku), zmensi prostor potrebny pro alokaci bloku a zjednodusi management volneho prostoru.
Cenou za vyhodu predesleho vylepseni je narust vnitrni fragmentace, nebot vice diskoveho prostoru je prideleno souboru a jimi nevyuzito. Klastery vsak mohou byt otpimalizovany radou dalsich algoritmu a jsou proto casto uzivany operacnimi systemy.
Dalsim problemem je spolehlivost. Protoze jsou bloky souboru navzajem spojeny ukazately uvazme, co by se stalo v pripade, ze by jeden ukazatel byl pozkozen. K tomu muze vest chyba operacniho systemu nebo hardwarova chyba. Takovy poskozeny ukazatel muze potom ukazovat nekam do volneho prostoru disku ci do uplne jineho souboru. Moznym resenim je zdvojeni ukazatelu nebo ulozeni jmena souboru spolu s cisly vsech bloku, ktere alokuje. To vse ovsem vyzaduje znacnou rezii systemu.
Prijatelnym resenim je uziti tabulky alokace souboru (file-allocation table). Tuto jednoduchou a efektivni metodu alokace diskoveho prostoru vyuzivaji MS DOS a OS/2. Urcita cast na zacatku kazde partition je ponechana stranou na tabulku souboru. V teto tabulce je polozkou zanesen kazdy diskovy blok a je v ni indexovan cislem bloku. FAT je potom uzita jako seznam linku. Kazda adresarova polozka obsahuje cislo prvniho bloku souboru. Polozka FAT indexovana timto blokem obsahuje cislo nasledujiciho bloku v souboru. Tento retez pokracuje az k poslednimu bloku, jahoz polozka ve FAT ma specialni odnotu EOF.

Obr. 85 Tabulka alokace souboru

Nevyuzite bloky ve FAT jsou indikovany hodnotou 0. Alokovani noveho bloku souboru potom predstavuje jednoduchou ulohu nalezeni prvni polozky tabulky, jejiz hodnota je 0 a nahradit hodnotu EOF drivejsiho posledniho bloku souboru odkazem na novy blok, jehoz hodnota je nastavena na EOF. Ilustrativni priklad uvadi nasledujici obrazek. Soubor sestava z bloku 217, 618 a 3311.
Pokud neni FAT cacheovana, vyvolava znacne mnozstvi pohybu po disku. Hlava se musi presunout na zacatek partition, aby nacetla polozku z FAT, potom nalezt lokaci bloku, ktery ma byt uzit a presunout se na toto misto. V nejhorsim pripade k tomuto muze dojit u kazdeho bloku.
FAT podporuje nahodny pristup k blokum souboru, protoze v tabulce lze nalezt vsechny potrebne informace.

Zpet

Obsah

Vpred