7.3.3. Stromova struktura adresaru

• Pokud jsme ukazali dvouurovnovou strukturu adresaru jako dvouurovnovy strom, je jen prirozene rozsirit adresarovou strukturu na strom libovolne vysky. Tato generalizace umoznuje uzivatelum vytvaret sve vlastni podadresare a organizovat tak sve soubory. MS DOS je napr. strukturovan jako strom. Strom je velmi casta adresarova struktura. Strom ma korenovy adresar. Ke kazdemu souboru vede jednoznacna cesta od korenoveho adresare pres vsechny podadresare az k cilovemu souboru.

Obr. 78 Stromova adresarova struktura

• Adresar (nebo podadresar) obsahuje mnozinu souboru adresaru nebo podadresaru. Adresar je jednoduse soubor, se kterym OS naklada specialnim zpusobem. Vsechny adresare maji stejny vnitrni format. Jeden bit v kazde polozce adresare identifikuje, zda je dana polozka soubor (0) nebo podadresar (1). K vytvoreni a smazani adresare uziva system specialni volani.

• Pri bezne praci ma kazdy uzivatel definovan aktualni adresar (current directory). Aktualni adresar obsahuje vetsinou souboru tykajici aktualniho zajmu uzivatele. Jestlize se uzivatel odkazuje na soubor, je prohledan aktualni adresar. Jestlize potrebny soubor neni v aktualnim adresari, potom musi uzivatel, bud specifikovat vyhledavaci cestu, nebo zmenit aktualni adresar na adresar, ktery obsahuje pozadovany soubor.

• Zmena aktualniho adresare na jiny je provadena systemovym volanim, ktere vyzaduje jako parametr jmeno adresare a provede predefinovani aktualniho adresare. Uzivatel muze tedy zmenit svuj aktualni adresar kdykoliv potrebuje. Po provedenem volani change directory vsechna volani open hledaji specifikovany soubor v aktualnim adresari.

• K inicializaci aktualniho adresare uzivatele dojde, kdyz system spusti uzivatelovu ulohu, nebo kdyz se uzivatel prihlasi do systemu. Operacni system tehdy prohleda soubor uzivatelskych uctu, aby nalezl polozku tykajici daneho uzivatele (s informacemi o jeho uzivatelskem uctu). Mezi temito informacemi je i ukazatel do uzivatelova domaciho adresare. Tento ukazatel je zkopirovan do lokalni promenne uzivatele, ktera specifikuje uzivateluv aktualni adresar.

• Cesta k souboru muze byt dvojiho druhu: absolutni (absolute path name) nebo relativni (relative path name). Absolutni cesta zacina korenovym adresarem a pokracuje az k souboru. Relativni cesta definuje cestu z aktualniho adresare. Budeme-li uvazovat strukturu adresaru z minuleho obrazku a je-li aktualni adresar root/spell/mail, potom relativni cesta prt/first odkazuje na stejny soubor jako absolutni cesta root/spell/mail/prt/first.

• Umoznime-li uzivateli vytvaret podadresare, umoznime mu vytvorit strukturu jeho souboru. Tak muze vytvorit adresare pro ruzne typy souboru (napr. samostatny adresar si muze uzivatel vytvorit pro ulozeni textu teto prednasky, dalsi pro programy, ktery bude obsahovat zdrojove programy, adresar bin pro jejich spustitelne formy atd. atd.).

• Zajimavym problemem ve stromove strukture adresaru je problem smazani adresare. Je-li adresar prazdny, muzeme jednoduse smazat jeho polozku v nadrazenem adresari. Pokud ovsem mazany adresar prazdny neni a obsahuje nejake soubory nebo podadresare, je mozno s nim nalozit dvema zpusoby. Nektere systemy (napr. MS DOS) nedovoli smazat adresar, ktery neni prazdny - tj. uzivatel musi nejprve smazat vsechny soubory, ktere aktualni adresar obsahuje. Pokud adresar obsahuje podadresare, je treba tento algoritmus rekurzivne aplikovat i na ne. To muze znamenat pro uzivatele znacnou namahu.

• Druhe reseni, ktere umoznuje napr. Unix prikazem rm -r je, ze dojde ke smazani vsech souboru i podadresaru, ktere mazany adresar obsahuje. Toto reseni je na jedne strane prijemnejsi, nicmene predstavuje pro system i znacne nebezpeci, nebot jednim prikazem muze byt nechtene smazan cely strom adresaru. Dojde-li k tomu, nastava nudna operace kopirovani smazanych souboru z pasky na disk (pokud ovsem takovou pasku mame :-)

• Pri stromovem usporadani adresarove strukturu je velmi jednoduche uzit soubor jineho uzivatele. Napr. Pokud uzivatel B chce pracovat se souborem uzivatele A, jednoduse zada cestu k tomuto souboru, at uz relativni nebo absolutni. Pripadne muze zmenit svuj aktualni adresar na adresar uzivatele A a primo pristupovat ke vsem jeho souborum.

• Nektere systemy umoznuji uzivatelum vytvaret vlastni vyhledavaci cesty. Potom uzivatel B muze do teto cesty definovat 1. svuj adresar; 2. systemovy adresar; 3. adresar uzivatele A. Pokud se jmeno souboru v adresari uzivatele A neshoduje se jmenem nejakeho souboru v adresari uzivatele B nebo v systemovem adresari, muze se na tento soubor uzivatel B odkazovat jednoduse pouze prostrednictvim jeho jmena.

• Poznamenejme, ze u stromove usporadane struktury adresaru muze byt cesta k souboru (napr. spustitelnemu) velmi dlouha. Aby uzivatele mohli spoustet programy, aniz by si museli pamatovat cesty k spustitelnym souborum byva jejich vyhledavani automatizovano. MacOS napr. obhospodaruje soubory zvany 'Desktop File', ktery obsahuje jmeno a cestu ke vsem spustitelnym programum v systemu. Jestlize je k systemu pripojen novy disk (hard nebo floppy), nebo je pripojena sit, OS vyhleda v novych adresarich spustitelne soubory a aktualizuje patricne informace. To je podpora pro dvojklik, ktery je v MacOSu uzit, tak jak jiz bylo zminovano. Dvojklik na ikonu souboru vyvola nacteni jeho atributu creator a v 'Desktop File' je potom vyhledana cesta k programu, ktery je spusten a otevre soubor, na ktery byl proveden dvojklik.

7.3.4. Acyklicky graf adresaru

• Predstavme si dva programatory, kteri pracuji na spolecnem projektu. Soubory souvisejici s timto projektem necht jsou ulozeny ve specialnim podadresari, aby se nemichaly s ostatnimi soubory obou programatoru. Protoze jsou oba programatori za projekt odpovedni stejnou merou, oba chteji, aby podadresar s projektem byl v jejich adresari. Tento adresar musi byt sdilen (shared).

• Sdileny adresar nebo soubor existuje v systemu souboru na dvou nebo i vice mistech najednou. Poznamenejme, ze sdileny soubor nebo adresar neni totez co dve kopie souboru ci adresare. Pokud by programator provedl zmenu v jedne kopii, tato zmena by se neprojevila v kopii druhe.

Obr. 79 Acyklicky graf adresarove struktury

• Je-li soubor sdilen, fyzicky existuje pouze jednou, takze vsechny zmeny provedene libovolnym uzivatelem jsou okamzite viditelne i vsemi ostatnimi. Tento mechanismus je vhodny i pro sdileni adresaru. Nove vytvoreny soubor ve sdilenem adresari je viditelny i pro vsechny ostatni.

• Stromova struktura adresaru sdileni neumoznuje. Strukturou, ve ktere je sdileni mozne je acyklicky graf. Tyz soubor nebo podadresar muze byt ve dvou ruznych adresarich soucasne. Acyklicky graf (tedy graf, ve kterem nejsou zadne kruznice) je prirozenym rozsirenim stromove struktury adresaru.

• U pracovni skupiny lidi mohou byt potom vsechny spolecne soubory umisteny ve sdilenem adresari. Tento adresar je potom sdilen ve vsech uzivatelskych adresarich vsech clenu pracovni skupiny.

• Sdilene soubory a podadresare mohou byt implementovany nejruznejsimi zpusoby. Castou cestou, kterou jdou i mnohe Unixy je vytvoreni nove polozky v adresari, zvane link. Link je ve skutecnosti ukazatel na jiny soubor nebo adresar. Link muze byt implementovan pomoci absolutni nebo relativni cesty (symbolicky link).

• Kdyz dojde odkaz na soubor, prohledame adresar. patricna polozka je oznacena jako link a ziskame z ni odkaz na skutecny soubor nebo adresar. Link uzijeme k ziskani cesty ke skutecnemu souboru. Linky je mozno jednoduse identifikovat formatem polozky adresare, nebo je mozno definovat je jako specialni typ v OSu, ktery typy rozeznava.

• Linky jsou ignorovany pri prenosu stromu adresaru, aby byla zachovana acyklicka struktura systemu.

• Jina implementace sdilenych souboru spociva v duplikaci vsech informaci o souboru ve vsech adresarich, ktere soubor sdili (nebo adresar). Tam jsou vsechny polozky identicke. Tento pristup vede k identite mezi originalem a linkem a to s sebou prinasi urcite obtize pri sprave sdilenych dat.

• Acyklicky graf adresaru je flexibilnejsi struktura nez bezny strom adresaru, je vsak take mnohem komplexnejsi a je treba pri jeji implementaci vyresit mnohe problemy. V takove strukture muze vest k souboru vice absolutnich cest. V dusledku toho mohou ruzna jmena odkazovat na tentyz soubor. Jestlize potom chceme projit cely system souboru (kvuli vyhledavani, vytvoreni statistiky souboru nebo kvuli backupu systemu), nemame nejmensi zajem na tom, aby jsme sdilene struktury prochazeli vice nez jednou.

• Dalsi problem s sebou nese mazani. Kdy muzeme skutecne uvolnit prostor alokovany sdilenemu souboru? Jedna moznost je provest to vzdy, kdyz nektery uzivatel "smaze" sdileny soubor. Tento postup vsak za sebou muze zanechat ukazatele na neexistujici soubor. A jeste hure, jestlize zbyle ukazatele obsahuji diskove adresy na prostor, ktery uz obsadil jiny soubor, tyto ukazatele mohou odkazovat dovnitr uplne jineho souboru.

• V systemu, kde je sdileni implementovano pomoci symbolickych linku, je reseni tohoto problemu jednodussi. Smazani linku nijak neovlivni sdileny soubor, pouze je link odstranen z adresare. Jestlize je smazan sam soubor, je uvolnen prostor, ktery zabiral na disku a ponechany visici ukazatele. Mohli by jsme tyto ukazatele vyhledat a smazat, ovsem pokud neni udrzovan seznam techto ukazatelu, bylo by hledani velmi obtizne a zdlouhave. Stejne dobre muzeme tyto prazdne odkazy nechat byt do doby, nez bude proveden pokus o jejich uziti. V teto situace muzeme urcit, ze soubor, na ktery link odkazuje jiz neexistuje a ukoncit chybou rezoluci jmena souboru. S odkazem na link je potom nalozeno stejne jako s odkazem na neexistujici soubor. (V tomto pripade by mel tvurce systemu bezpecne vyresit co delat, je-li soubor smazan a jiny soubor tehoz jmena opetovne vytvoren a je uzit symbolicky odkaz na puvodni soubor.) V Unixu symbolicke linky pretrvavaji a je na uzivateli, jak se zaridi.

• Jiny pristup k mazani linku je zachovat soubor, dokud nejsou smazany vsechny linky na nej. Pro tento pristup musime mit implementovan mechanismu, ktery zjisti, zda prave mazany linky je ci neni posledni. Muzeme udrzovat seznam vsech odkazu na soubor. Jestlize je vytvoren novy link, prida se nova polozka do seznamu. Pokud se link maze, smazeme polozku ze souboru odkazu. K fyzickemu smazani souboru muze dojit, je-li jeho seznam linku prazdny.

• Potiz tohoto pristupu je v promenlive a potencialne znacne velikosti seznamu linku. Ve skutecnosti nemusime uchovavat cely seznam odkazu, staci znat jejich aktualni pocet. Novy odkaz inkrementuje citac linku, smazani odkazu ho dekrementuje. Je-li citac roven 0, je mozno fyzicky smazat soubor.

• Unix implementuje tento pristup u nesymbolickych linku (hard links), kde je citac referenci soucasti informacniho bloku souboru, tzv. Inodu.

• Aby se nektere operacni systemy vyhnuly vyse uvedenym problemum, proste sdileni souboru neimplementuji (napr. MS DOS).

7.3.5. Obecny graf adresaru

• Vazny problem pri uziti acyklickeho grafu adresaru je zajistit, ze se do nej nevetre zadna kruznice. Jestlize jsme zacali s dvojurovnovym adresarem a umoznili jsme uzivatelum vytvaret podadresare, vznikla stromova struktura adresaru. Je snadne nahlednout, ze vytvorenim podadresaru se nijak nenarusi podstata stromove struktury. V okamziku, kdy ale pridame linky, situace se zmeni velice vyznamne. System souboru tvori obecny graf, tak jak je videt na nasledujicim obrazku.

Obr. 80 Obecny graf adresaru

• Vyhodou acyklickych grafu je relativni jednoduchost algoritmu pruchodu grafem a snadne urceni poctu linku na soubor nebo adresar. Potrebujeme se vyhnout vicenasobnemu prochazeni sdilenych oblasti v acyklickem grafu zejmena z hlediska vykonu. Jestlize hledame soubor ve sdilenem adresari a nenalezneme ho, je zcela zbytecne, aby jsme ho diky dalsimu linku na nej prohledavali znovu. Byl by to ztraceny cas.

• Jestlize pripustime kruznice v grafu adresarove struktury, stejne tak chceme zabranit vicenasobne prohledavani sdilenych oblasti ze zminovanych duvodu. Spatne vytvoreny algoritmus pruchodu grafem vsak muze velmi jednoduse skoncit v neomezenem cyklu. Jednou z moznosti jak to resit je stanovit maximum moznych pruchodu adresarem behem prohledavani.

• Dalsi problem nastava, chceme-li zjistit, jestli je mozne soubor smazat. V acyklickem grafu je 0 v citaci odkazu nutnou i postacujici podminkou k tomu, aby mohl byt soubor smazan. Pokud se ovsem v grafu kruznice mohou objevit, citac odkazu muze byt ruzny od 0 a presto na soubor nepovede zadny jiny odkaz. Muze totiz dojit k tomu, ze adresar bude odkazovat sam na sebe. V tomto pripade je nutne uzit inventarizaci volnych mist (garbage collection) ke zjisteni, zda byl smazan posledni odkaz na soubor a soubor muze byt odstranen z disku.

• Garbage collection umoznuje prochazet systemem souboru a oznacit vse, co muze byt uzito. V dusledku toho oznaci vse co neni v prvnim seznamu jako volny prostor k uziti. Obdobneho mechanismu lze uzit i k tomu, aby libovolny pruchod ci hledani v systemu souboru navstivilo vse prave jednou. Garbage collection je ovsem velmi casove narocna a byva uzita jen velmi zridka.

• Garbage collection je nutna pouze v pripade, ze se v grafu mohou objevit kruznice. Acyklicka struktura je tedy pro management mnohem prijatelnejsi. Jediny problem u ni je, zabranit tomu, aby novy link nevnesl do grafu kruznici. Jak zjistime, ze novy link uzavira kruznici? Existuji algoritmy, ktere v grafu kruznici objevi. Ty jsou ale casove narocne. Obecne, stromova struktura adresaru je mnohem castejsi, nez struktura acyklickych grafu.

---

Zpet Obsah Vpred