Metody alokace, Management volneho prostoru

8.2.3. Indexova alokace diskoveho prostoru

Spojovana alokace resi problem vnejsi fragmentace a problem deklarace velikosti, ktery je u alokace souvisle. Spojovana alokace ovsem spatne podporuje primy pristup k souboru, protoze ukazatel na nasledujici blok je soucasti bloku predchazejiciho, z cehoz nutne plyne sekvencni pristup k souboru.
Indexovana alokace resi tento problem tak, ze vsechny ukazatele ulozi do jednoho zvlastniho bloku - bloku indexu. Kazdy soubor ma svuj vlastni indexovy blok, ktery obsahuje seznam adres diskovych bloku. I-ta polozka v indexovem bloku ukazuje na i-ty blok souboru. Adresarova polozka potom obsahuje adresu indexoveho bloku (viz. nasledujici obrazek).

Obr. 86 Indexova alokace diskoveho prostoru

Pro nacteni i-teho bloku uzijeme adresu ulozenou v i-te polozce indexoveho bloku. Jedna se zde prakticky o ekvivalent strankovani pameti.
Pri vytvoreni noveho souboru jsou vsechny ukazatele v jeho indexovem bloku nastaveny na hodnotu nil. Jestlize je i-ty blok poprve ukladan na disk, doda manazer volneho prostoru neobsazeny blok, do nejz se pak provede zapis a jeho adresa se ulozi jako i-ta polozka indexoveho bloku.
Indexova alokace podporuje primy pristup bez nebezpeci vnejsi fragmentace, nebot pozadavek na volny blok muze uspokojit kterykoliv volny.
Moznym nebezpecim je tu ale interni fragmentace. Diskovy prostor nutny pro indexovy blok je obecne vetsi nez prostor potrebny pro ukazatele pri spojovane alokaci. Uvazujme pomerne casty pripad, kdy mame soubor sestavajici z jednoho ci dvou bloku. Pri spojovane alokaci zahrnuje rezie prostor potrebny pro dva ukazatele. Pri indexovane alokace musime alokovat cely blok, i kdyz v nem bude pouze jeden ci dva ukazatele ruzne od nil.
Predchazejici uvaha vede k zamysleni nad velikosti indexoveho bloku. Kazdy soubor musi mit svuj indexovy blok, takze nasi logickou snahou je, aby tento blok byl co nejmensi. Pokud bude ale indexovy blok prilis maly, nebude schopen drzet vsechny ukazatele na vsechny bloky velkeho souboru. Reseni tohoto problemu mohou byt nasledujici:

Spojova struktura - indexovy blok je bezne jeden diskovy blok. Pro umozneni existence velkych souboru je mozno spojit nekolik diskovych bloku dohromady. Indexovy blok muze obsahovat napr. malou hlavicku, kde je zaznamenano jmeno souboru a pak nasleduje seznam prvnich 100 ukazatelu na diskove bloky. Nasledujici adresa (posledni slovo v indexovem bloku) je nil pro maly soubor nebo ukazatel na dalsi indexovy blok (u velkeho souboru).
Viceurovnovy index - variantou spojove struktury je uzit indexovy blok pouze jako seznam odkazu na dalsi indexove bloky, ktere potom ukazuji na diskove bloky souboru. Pri odkazu na nejaky blok souboru OS uzije index prvni urovne k tomu, aby nalezl index druhe urovne, kde pak najde adresu pozadovaneho bloku dat. Tento pristup muze potom pokracovat indexem trojurovnovym, ctyrurovnovym atd. podle toho, jak maximalne veliky soubor se muze na disku objevit. Mame-li blok velikosti 2048 B, muzeme v nem ulozit 512 4B ukazatelu na diskove bloky. Index dvou urovni umozni adresovat 4 194 304 bloku, coz predstavuje soubor o velikosti 8.5 GB. Tato velikost by mela presahovat kapacitu daneho disku.
Kombinovany pristup - BSD Unix pouziva kombinaci obou vyse zminovanych pristupu. Indexovy blok (nebo inode) obsahuje rekneme 15 ukazatelu. Z nich prvnich 12 ukazuje primo na prvnich 12 bloku souboru. Z toho plyne, ze male soubory (pri blocich velikosti 4 kB soubory do 48 kB) nepotrebuji vlastni indexovy blok a vystaci si s inodem. Inody vsech souboru jsou uchovavany ve vyhrazene oblasti na disku tak, jak ukazuje nasledujici nakres:

boot block - zabira zacatek systemu souboru, nejcasteji prvni sektor a muze obsahovat bootstrap code, ktery je uzit pri bootovani pocitace. Ackoli je potreba pouze jeden boot block, ma ho kazdy disk (treba i prazdny).
super block - popisuje system souboru na disku - jak je velky, kolik souboru muze maximalne uchovavat, jak a kde bude udrzovan volny prostor a dalsi informace.
inods list - prostor pro inody souboru nasleduje za super blockem. Velikost tohoto prostoru specifikuje administrator pri vytvareny systemu souboru na disku. Jedna inoda je tzv. root inode systemu souboru. To je inoda, ktera zpristupnuje adresarovou strukturu pro nasledne volani mount.
data blocks - obsahuji soubory a administrativni data. Alokovany blok patri jednomu jedinemu souboru.
Dalsi tri ukazatele ukazuji na viceurovnove indexy. Prvni z nich ukazuje na index druhe urovne, ktery obsahuje adresy dalsich bloku souboru pocinaje trinactym. Druhy odkazuje na trojurovnovy index a posledni pripadne u extremne velkych souboru i na ctyrurovnovy index bloku.
Uzitim teto metody je pocet odkazovatelnych bloku vetsi nez pocet bloku, ktere je mozno adresovat pomoci 4 B. Inode je videt na nasledujicim obrazku.

Poznamenejme, ze indexova alokace trpi nekterymi vykonnostnimi problemy stejne jako spojovana alokace. Indexove bloky pouzivanych souboru mohou a take byvaji cacheovany v pameti, ale jednotlive bloky souboru mohou byt rozptyleny ruzne po disku, coz predstavuje problemy s posunem hlav a otacenim disku.

Obr. 87 Inode v Unixu

8.2.4. Vykon

Popisovane alokacni metody se lisi jak v efektivite ukladani bloku, tak i v dobe pristupu k bloku souboru. Obe tato kriteria jsou dulezita pri vyberu vhodne metody ci metod, ktere implementovat do operacniho systemu.
Problem porovnavani vykonu ruznych systemu spociva v urceni toho, jak bude system se soubory pracovat. System, ve kterem bude vetsina operaci se soubory sekvencniho charakteru potrebuje jinou alokacni metodu nez system s prevazne nahodnym pristupem k jednotlivym blokum souboru.
V jakemkoliv typu pristupu, souvisla alokace vyzaduje pouze jediny pristup k disku, aby byl ziskan pozadovany blok. Adresu prvniho bloku muzeme uchovavat v pameti a adresu bloku i-teho z ni muzeme jednoduse spocitat a pristoupit primo k pozadovanemu bloku.
U spojovane alokace uchovavame v pameti adresu nasledujiciho bloku a ten muzeme precist take primo. Tato metoda je vhodna pro sekvencni pristup k souborum. Primy pristup k i-temu bloku muze pri nejhorsim vyvolat i cteni z disku. Z toho je zrejme, ze spojovana alokace by nemela byt uzivana tam, kde je treba nahodny pristup k blokum souboru.
Nektere OSy potom podporuji soubory s primym pristupem souvislou alokaci a soubory se sekvencnim pristupem alokaci spojovanou. V takovych systemech musi byt typ pristupu k souboru deklarovan v okamziku jeho vytvareni. Soubor vytvoreni pro sekvencni pristup bude potom na disku organizovan spojove a nebude k nemu mozny pristup primy. Soubor vytvoreny pro primy pristup bude alokovan souvisle a bude k nemu mozny pristup jak primy, tak i sekvencni. V okamziku jeho vytvareni je vsak treba deklarovat take maximalni velikost souboru.
Poznamenejme, ze pri vyse zminovanem reseni musi OS obsahovat kod datove struktury pro podporu obou alokacnich metod. Soubor muze byt konvertovan z jednoho typu do druheho vytvorenim noveho souboru opacneho typu a prekopirovani obsahu souboru puvodniho. Puvodni soubor muze byt potom smazan a nove vzniknuvsi prejmenovan.
Indexovana alokace je komplikovanejsi. Jestlize je indexovy blok souboru jiz v pameti, potom jsou vsechny pristupy prime. Uchovavani indexoveho bloku v pameti vsak vyzaduje volny pametovy prostor. Pokud se tohoto prostoru nedostava, potom muze dojit k potrebe dvojiho pristupu ne disk: jednou kvuli zjisteni adresy pozadovaneho bloku v indexu a podruhe pro nacteni tohoto bloku. Pri uziti dvouurovnove indexace je treba nacist dva indexove bloky a az potom hledana data. U extremne velkeho souboru muze vyvolat pristup k bloku nedaleko konce souboru nacteni vsech indexovych bloku, jez na soubor ukazuji, nez je nalezena adresa pozadovaneho bloku. Vykon indexove alokace je tudiz podminen indexovaci strukturou, velikosti souboru a pozici pozadovaneho bloku v souboru.
Nektere OSy kombinuji souvislou a indexovou alokaci tak, ze kontinualne alokuji diskovy prostor pro male soubory (do velikosti tri nebo ctyr bloku) a automaticky prejdou k indexove alokaci, preroste-li velikost souboru tuto hranici. Nebot mnoho souboru je malych a kontinualni alokace je pro male soubory velmi efektivni, dosahuji tyto systemy dosti dobrych vykonu.
Napriklad verze Unixu pro pocitace Sun zmenila v roce 1991 alokacni mechanismy, aby zvysila vykonnost systemu souboru. Kvuli zvyseni vykonnosti Sun definoval extremne velke clustery (56KB) a uzil jich vsude, kde to bylo mozne. Tak snizili vnejsi fragmentaci a tim i cas potrebny pro pruchody diskem. Pro cteni takto velkych clusteru byly take optimalizovani rutiny OSu. System Inodu byl ponechan beze zmen. O dalsich zmenach, ktere vedli ke zvyseni vykonnosti systemu souboru se jeste zminime pozdeji.

8.3. Management volneho prostoru

Protoze velikost celkoveho diskoveho prostoru je omezena, je nutno opetovne vyuzivat vsechen prostor, ktery je uvolnen pri smazani souboru (je-li to mozne). U optickych disku, na ktere lze provest zapis pouze jednou tato starost odpada.
Kvuli prehledu o volnem diskovem prostoru udrzuje OS seznam volnych bloku (free-space list). Seznam volnych bloku obsahuje vsechny bloky , ktere jsou volne, tj. nejsou alokovany pro nejaky soubor nebo adresar.
Pri vytvareni noveho souboru vyhledame v seznamu volnych bloku pozadovane mnozstvi diskoveho prostoru a tento prostor novemu souboru alokujeme. Nove alokovane bloky jsou potom odebrany ze seznamu volnych bloku. Jestlize je soubor smazan, bloky mu alokovane se do seznamu volnych bloku pridaji.

8.3.1. Vektor bitu

Casto je seznam volneho prostoru implementovan jako bitova mapa nebo vektor bitu. Kazdy blok je tu reprezentovan jednim bitem. Jestlize je blok volny, hodnota bitu je 1, jestlize je alokovan, je jeho hodnota 0.
Uvazujme napr. disk, kde volne jsou bloky 2, 3, 4, 5, 8, 9, 10, 11, 12, 13, 17, 18, 25, 26, 27 a zbytek disku tvori bloku alokovane. Bitova mapa volneho prostoru potom bude vypadat nasledovne:
0011110011111100011000000111000000000...
Hlavni vyhodou tohoto reseni je mala velikost bitove mapy a jeji jednoduche prohledavani, pokud chci najit prvni volny blok. Mnoho pocitacu ma navic implementovany operace pro manipulaci s bity, ktere mohou byt efektivne vyuzity k implementaci tohoto seznamu volnych bloku.
Napr. procesory Intel 386 a 486 a Motorola 68020 az po 68040 (tedy procesory uzivane na pocitacovych platformach IBM PC kompatibilni a Macintosh) maji implementovany instrukce, ktere vraci offset prvniho nenuloveho bitu ve slove. Proto take pocitace Apple Macintosh uzivaji pro management volneho prostoru metodu vektrou bitu. K nalezeni prvniho volneho bloku potom MacOS prochazi sekvencne kazde slovo v bitove mape a hleda prvni nenulove, nebot slovo s hodnotou 0 znaci vsechny bloky alokovane.
V prvnim slove s nenulovou hodnotou je vyhledan vzpominanou instrukci prvni nenulovy bit, ktery svou pozici udava adresu volneho bloku. Vypocet cisla bloku je:
"pocet bitu ve slove" * "pocet slov s hodnotou 0" + offset prvniho 1 bitu
Nevyhodou implementace seznamu volnych bloku pomoci bitoveho vektoru je, ze cely vektor musi byt uchovavan v operacni pameti. To je mozne u mensich disku, jake maji napr. mikropocitace, ale u disku s vetsi kapacitou to predstavuje urcity problem. Pokud by jsme timto algoritmem mapovali volny prostor disku s kapacitou 1,3 GB, potrebovali bychom v pameti pro vektor bitu 310 KB pri 512 B blocich.

8.3.2. Spojovy seznam

Dalsim moznym resenim je vytvorit spojovy seznam vsech volnych bloku a uchovavat v pameti pouze ukazatel na prvni volny. Prvni volny blok v sobe obsahuje ukazatel na druhy volny atd. Disk obsazeny stejne jako v predchazejici kapitole by pri managementu volneho prostoru spojovym seznamem vypadal tak, jak ukazuje nasledujici obrazek.

Obr. 88 Spojovy seznam volnych bloku disku

Toto schema, stejne jako kazda spojova struktura, je nevhodne pro pruchody seznamem. Pri pruchodu je treba nacitat kazdy blok, coz stoji hodne casu, nicmene prochazeni seznamem volnych bloku neni prave casta operace. Nejcaste OS potrebuje volny blok, ktery muze alokovat souboru, a tak uzije prvni blok seznamu.
Zaverem pouze pri pripomenme, ze FAT v soube zahrnuje i seznam volnych bloku a neni tudiz potreba uzivat vlastni metodu na spravu volneho prostoru disku.

8.3.3. Seskupovani

Dalsim moznym resenim seznamu volnych bloku je uchovavat v prvnim volnem bloku adresy n dalsich volnych bloku. Prvnich n - 1 bloku je skutecne volnych, n-ty obsahuje adresy dalsich n volnych bloku atd. Vyhodou tohoto reseni je, ze je mozno rychle a jednoduse ziskat najednou adresy vice volnych bloku, narozdil od reseni pomoci spojoveho seznamu.

8.3.4. Pocitani

Dalsi pristup vyuziva toho, ze na disku obecne existuji spojite useky volnych bloku. Napr., pokud je diskovy prostor alokovan spojite nebo diky klasterum. Potom je vyhodnejsi, spise nez uchovavat seznam n volnych diskovych adres, ulozit poze adresu prvniho bloku a pocet dalsich volnych bloku, ktere tvori s prvnim souvisly usek. Presto, ze kazda polozka takovehoto seznamu vyzaduje vetsi prostor, nez je treba pro adresu diskoveho bloku, vysledny prostor obsazeny tabulkou je mensi nez pri bezne metode, protoze pocet dalsich volnych bloku je temer vzdy vetsi nez 1.

Zpet

Obsah

Vpred