Metody pristupu k souborum, Adresarova struktura

7.2. Metody pristupu k souborum

Soubory uchovavaji informace. Jestlize ma byt takova informace uzita, musi byt pristoupeno k souboru, ktery ji obsahuje a tento soubor musi byt zaveden do pameti. Existuji nejruznejsi cesty, jak ziskat informaci ulozenou v souboru. Nektere systemy podporuji pouze jednu metodu pristupu, zatimco jine, jako napr. systemy IBM podporuji vetsi pocet ruznych pristupovych metod a vyber te prave pri pristupu k souboru je zavazny problem.

7.2.1. Sekvencni pristup

Sekvencni pristup je nejjednodussi metoda pristupu. Informace v souboru jsou zpracovavany jeden zaznam za druhym. Tento pristup je velice casty. Uzivaji napr. prekladace, editory apod.
Operace provadene na souboru jsou cteni a zapis. Operace cteni cte nasledujici cast souboru a automaticky posune ukazatel nasledujici I/O operace. Stejne tak append, operace zapis provede zapis informaci na konec souboru a automaticky posune ukazatel nasledujici I/O operace na novy konec souboru. V nekterych systemech program muze preskocit dopredu nebo dozadu n zaznamu, pro nejake celociselne n (nejcasteji pro n = 1). Sekvencni pristup je videt na nasledujicim obrazku. Je zalozen na modelu pasky se souborem, ktera pracuje jako zarizeni se sekvencnim pristupem

Obr. 73 Sekvencni pristup k souboru

7.2.2. Primy pristup k souboru

Jinou metodou je primy pristup (nebo relativni pristup). Soubor sestava z logickych zaznamu pevne delky, coz umoznuje programu cist nebo zapisovat zaznamy rychle, ne v castecnem poradi. Metoda primeho pristupu je zalozena na diskovem modelu souboru, protoze disky umoznuji nahodny pristup k libovolnemu bloku souboru. Pri primem pristupu je soubor predstavovan ocislovanou sekvenci bloku nebo zaznamu.

Primy pristup k souboru umoznuje cist nebo zapisovat libovolny blok souboru. Tzn. muzeme precist blok 14, potom blok 53 a na zaver zapsat blok 7. Nejsou tu zadna omezeni na poradi cteni nebo zapisu.

Soubory s primym pristupem umoznuji rychly pristup k velkemu mnozstvi informaci. Databaze jsou takto casto implementovany. Kdyz dorazi dotaz na nejakou polozku databaze, vypocitame, ktery blok obsahuje pozadovanou informaci a potom precteme primo pozadovany blok pro zjisteni dotazovaneho udaje.

Uvazujme napriklad system rezervace letenek. Muzeme ulozit vsechny informace o urcitem letu (napr. letu 713) do bloku identifikovaneho cislem letu. Potom, pocet volnych sedadel v letu 713 je ulozen v bloku 713. K ulozeni dalsich informaci vetsiho rozsahu, jako napr. jmen cestujicich, muzeme uzit hashovaci funkci na jmena cestujicich nebo uzit nejake indexovani k urceni cisla bloku pro zapis a vyhledavani.

Operace se soubory musi byt modifikovany tak, aby obsahovaly cislo bloku jako svuj parametr. Tj. uzivame funkci read n, kde n je cislo nacitaneho bloku spise nez read next a stejne tak write n namisto write next. Alternativni reseni je ponechat operace read next a write next s jejich puvodnim vyznamem a pridat operaci position file to n, kde n je cislo bloku. Potom ma sekvence prikazu position file to n, read next stejny vyznam jako operace read n.

Cislo bloku, ktere pouziva uzivatel v interakci s OSem se nazyva relativni cislo bloku. Relativni cislo bloku je relativni index bloku od zacatku souboru. Relativni cislo prvniho bloku souboru je tedy 0, dalsiho 1 atd., zatimco absolutni adresa prvniho bloku na disku muze byt 14703 a druheho 3192. Uziti relativnich cisel bloku umoznuje operacnimu systemu rozhodnout, kde bude soubor na disku fyzicky ulozen (alokacni problem) a pomaha zamezit uzivateli pristupovat k blokum disku, ktere neobsahuji cast jeho souboru. Nektere OSy definuji relativni cislo prvniho bloku 0, jine 1.
Je-li logicky zaznam delky D, potom zadost o zaznam N je preveden na I/O zadost o D bytu od mista D*(N-1) od zacatku souboru. Nebot jsou logicke zaznamy pevne delky, je velmi jednoduche zapsat, precist nebo vymazat zaznam.
Ne vsechny OSy podporuji jak sekvencni, tak primy pristup k souboru. Nektere umoznuji pouze sekvencni, jine pouze primy pristup. Jine systemy vyzaduji, aby v okamziku vytvoreni souboru bylo dopredu definovano, zda se bude jednat o soubor s primym nebo sekvencnim pristupem a potom je mozno pristupovat k souboru pouze zpusobem definovanym v okamziku jeho vytvoreni.
Poznamenejme, ze je velmi jednoduche simulovat sekvencni pristup na soubor s primym pristupem. Jestlize jednoduse definujeme promennou ap, ktera udava aktualni pozici v souboru, potom je mozno simulovat sekvencni operace tak, jak ukazuje nasledujici tabulka:

Sekvencni operace	Implementace pri primem pristupu
reset	ap := 0;
read next	read ap ap := ap + 1;
write next	write ap ap := ap + 1;

7.2.3. Dalsi metody pristupu

Dalsi metody pristupu k souboru mohou byt vytvoreny na zaklade metody primeho pristupu. Tyto metody vetsinou spocivaji v konstrukci indexu pro kazdy soubor. Index, stejne jako rejstrik na konci knihy obsahuje ukazatele na ruzne bloky. Pro nalezeni nejake polozky v souboru nejdrive prohledame index a potom uzijeme ukazatel pro primy pristup vedouci k nalezeni polozky.
Napriklad, soubor maloobchodnich cen knih muze obsahovat ISBN kod knihy a k nemu asociovanou cenu. Kazda polozka sestava z 13-ti mistneho ISBN kodu a trimistne ceny. Celkem kazda polozka zabira 16 bytu. Jestlize nas disk ma blok velikost 1024 bytu, muzeme do bloku ulozit 64 polozek. Soubor o 120 000 polozkach zabere 2 000 bloku (tedy 2 miliony bytu. K ulozeni souboru usporadaneho podle ISBN, muzeme sestavit index, obsahujici ISBN prvni polozky v kazdem bloku. Tento index bude mit 2 000 polozek po 13-ti cislech tj, 26 000 bytu a bude ulozen v pameti.
K nalezeni ceny urcite knihy staci prohledat index, potom budeme presne vedet, ve kterem bloku se informace o cene nachazi, a tento blok uzit. Popisovana struktura umoznuje prohledavat velke soubory dat s malym poctem I/O operaci.
U velkych souboru, muze byt i sam index prilis velky na to, aby byl uchovavan v pameti. Moznym resenim je vytvoreni indexoveho souboru. Primarni indexovy soubor potom obsahuje ukazatele do sekundarniho indexu v souboru s daty.
Napr. IBM indexuje souboru metodou ISAM (Indexed Sequential Access Method), ktera uziva maly master index, ktery ukazuje na diskove bloky sekundarniho indexu. Sekundarni index ukazuje na konkretni bloky dat. Soubory jsou ukladany usporadane podle definovaneho klice. K nalezeni urcite polozky je treba nejprve binarne prohledat master index, ktery ukaze cislo bloku sekundarniho indexu. Tento blok je nacten, opet binarne prohledan a je nalezeno cislo bloku, ktery je sekvencne prohledan. Pri teto organizaci pristupu k souboru je jeho libovolna polozka nalezena maximalne po dvou primych ctenich. Nasledujici obrazek ukazuje obdobnou situaci, jak je implementovana v OSu VMS.

Obr. 74 Priklad indexoveho a realtivniho souboru

7.3. Adresarova struktura

System souboru pocitace muze byt znacne rozsahly. Velke systemy uchovavaji tisice souboru na mnohasetgygabytovych discich. Pro management takoveho mnozstvi souboru je treba je nejak organizovat.
Organizace souboru je vetsinou provadena ve dvou urovnich. V prvni urovni je system souboru rozdelen na partitions, znamych ve svete IBM jako minidisks, ci jako volumes na pocitacich PC ci Macintosh.
Nejcasteji obsahuje kazdy disk v systemu minimalne jednu partition, ve ktere jsou ulozeny soubory a adresare. Nekdy jsou partitions uzity k rozdeleni vetsiho disku na nekolik nezavislych oblasti. S kazdou oblasti system zachazi jako se samostatnym odkladacim zarizenim. Jine systemy umoznuji vytvaret vetsi partitions nez je fyzicky rozsah disku a seskupovat nekolik disku do jednoho logickeho zarizeni.
Z vyse uvedenych duvodu uzivatel pracuje vzdy jen s logickou adresarovou strukturou a logickym systemem souboru a zcela ignoruje problemy fyzicke alokace disku souborem. Z tohoto pohledu predstavuji partitions virtualni disky.
Kazda partition obsahuje informace o souborech na ni ulozenych, coz je druha uroven systemu souboru. Tyto informace jsou ulozeny v zaznamech adresare zarizeni (device directory) nebo volume table.
Adresar zarizeni (casteji oznacovan pouze slovem adresar) uchovava informace jako jmeno, lokace, velikost a typ pro vsechny soubory na zarizeni. Nasledujici obrazek ukazuje typickou strukturu systemu souboru.

Obr. 75 Typicka organizace systemu souboru

Na adresar je mozno pohlizet jako na tabulku symbolu, ktera prevadi jmena souboru na odpovidajici zaznamy. Musime byt schopni vlozit do adresare novou polozku, smazat nekterou stavajici, vyhledat zaznam v adresari odpovidajici souboru daneho jmena.
V nasledujici kapitole rozebereme datove struktury, ktere mohou byt uzity pri implementaci adresarove struktury. Nyni si popiseme ruzna schemata definice logicke struktury systemu adresaru.
Definujme nejdrive operace, ktere potrebujeme s adresarem provadet:

Vyhledani souboru. Musime byt schopni prohledavat adresarovou strukturu a kazdy soubor v ni. Protoze soubory maji symbolicka jmena a podobna jmena mohou oznacovat soubory, ktere jsou si blizke, je treba mit moznost vyhledat vsechny soubory jejichz jmeno obsahuje zadany retezec.
Vytvoreni souboru. Musime mit moznost vytvorit novy soubor a ulozit ho do adresare.
Smazani souboru. Jestlize uz neni soubor vice zapotrebi, je treba mit moznost odstranit ho z adresare.
Vypis adresare. Musime mit moznost ziskat seznam souboru, ktere jsou v adresari a take vypsat vsechny informace v zaznamu kazdeho souboru adresare.
Prejmenovat soubor. Protoze jmeno souboru reprezentuje jeho uzivatele obsah souboru, musi existovat moznost zmenit jmeno souboru, jestlize se zmeni jeho obsah nebo zpusob uziti.
Pohyb systemu souboru. Je uzitecne mit moznost pristupu do kazdeho adresare a ke kazdemu souboru v nem ulozenemu. Pro bezpecnost systemu souboru je take vhodne ukladat v pravidelnych intervalech obsah a strukturu celeho systemu souboru. Toto ukladani casto spociva v kopirovani vsech souboru na magnetickou pasku. Touto technikou se vytvori zalozni kopie pro pripad havarie systemu, nebo proste proto, ze soubory uz dale nebudou pouzivany. V tomto pripade mohou byt soubory zkopirovany na pasku, smazany z disku, cimz vznikne prostor pro soubory jine.

7.3.1. Adresar jedne urovne

Nejednodussi adresarova struktura je jednourovnova. Vsechny soubory jsou ulozeny v jednom adresari. Tato struktura vyzaduje minimalni podporu a je dobre pochopitelna (viz nasledujici obrazek).

Obr. 76 Jednourovnova adresarova struktura

Jednourovnova struktura adresare ma zrejme nevyhody v pripade, kdyz je v systemu velke mnozstvi souboru, pripadne ma system vice uzivatelu. Protoze vsechny soubory jsou ulozeny ve stejnem adresari, musi mit ruzna jmena. Jestlize dva ruzni uzivatele nazvou sve soubory test, je toto pravidlo jedinecnosti jmena poruseno.
Presto, ze jsou jmena souboru volen tak, aby vystihovala jejich obsah, jsou casto limitovana delkou. MS DOS umoznuje jmeno soubor maximalne 11-ti znakove, Unix pripousti maximalne 255 znaku pro jmeno souboru.
I v pripade, ze system bude mit pouze jednoho uzivatele a pomerne maly pocet souboru, nastanou potize se zapamatovanim vsech jmen vsech souboru, aby novy soubor mel vzdy jedinecne jmeno. Neni neobvykle, ze uzivatel ma v systemu stovky souboru a stejne mnoho v jinem systemu. Sledovat v teto adresarove strukture vsechny soubory je zrejme nemozne.

7.3.2. Dvouurovnovy adresar

Hlavni nevyhodou adresare jedne urovne je zmatek mezi soubory a jejich jmeny od vice uzivatelu. Resenim tohoto problemu je vytvorit samostatny adresar pro kazdeho uzivatele.
Ve dvouurovnove adresarove strukture ma kazdy uzivatel svuj vlastni uzivatelsky adresar souboru (user file directory - UFD). Kazdy UFD ma stejnou strukturu, ale obsahuje pouze soubory patrici danemu uzivateli.
Kdyz se spusti uzivatelska uloha nebo se uzivatel prihlasi do systemu, je prohledan hlavni adresar souboru (master file directory - MFD). MFD indexuje podle uzivatelskeho jmena nebo cisla uctu a kazda jeho polozka ukazuje na patricny UFD hledaneho uzivatele.

Obr. 77 Dvouurovnova adresarova struktura

Jestlize uzivatel pozaduje nejaky soubor, je prohledan pouze jeho UFD. Ruzni uzivatele mohou tedy mit soubory stejnych jmen (viz soubor a nebo data).
Vytvori-li uzivatel novy soubor, je prohledan pouze jeho uzivatelsky adresar, neni-li v nem soubor stejneho jmena. Pri mazani souboru OS prohledava pouze aktualni UFD, takze neni mozno smazat soubor stejneho jmena jineho uzivatele.
Uzivatelske adresare musi byt mozno vytvaret i mazat. Noveho uzivatele pocitace vytvari specialni systemovy program, ktery vytvori novy uzivatelsky adresar prida ukazatel na nej do hlavniho adresare. Spoustet tento program smi pouze administrator systemu. Zpusob alokace diskoveho prostoru pro uzivatelsky adresar bude jeste diskutovan.
Dvouurovnova struktura adresaru resi problem kolize jmen, nicmene ma stale mnoho nedostatku. Tato struktura naprosto izoluje uzivatele od vsech ostatnich. To je vyhoda, jsou-li jednotlivy uzivatele systemu na sobe naprosto nezavisli. Je to vsak vazny nedostatek, pokud uzivatele chteji spolupracovat na nejake uloze a pristupovat spolecne k nejakym souborum. To u nekterych systemu proste neni mozne a tyto systemy neumoznuji jakykoliv pristup k souborum jineho uzivatele.
Jestlize OS pripousti pristup k souborum jineho uzivatele, uzivatel musi mit moznost pojmenovat soubor v jinem uzivatelskem adresari. K jednoznacne identifikaci souboru ve dvouurovnove strukture adresaru slouzi jmeno uzivatel a jmeno souboru.
Dvouurovnova struktura adresaru predstavuje strom vysky 2. Korenem toho stromu je hlavni adresar. Jeho potomkem jsou uzivatelske adresare a jejich potomky pak jednotlive soubory. Soubory tvori listy stromu. Specifikujeme-li jmeno uzivatele a jmeno souboru, specifikujeme cestu stromem od korene (hlavni adresar) k listu (specifikovany soubor). Jmeno uzivatele a jmeno souboru tvori tedy uplnou cestu. Ke kazdemu souboru vede uplna cesta. K adresovani souboru z jineho adresare je treba znat plnou cest k nemu.
Jestlize napr. uzivatel A chce pristoupit k souboru jmena test, ktery ma ve svem uzivatelskem adresari, muze se na nej odkazovat pouze jmenem souboru test. Chce-li pristoupit k souboru test uzivatele B (s uzivatelskym adresarem userb), musi se na nej odkazovat plnou cestou /userb/test. Kazdy system ma svou vlastni syntaxi k pojmenovavani souboru ulozenych jinde nez v uzivatelove adresari.
Syntakticky musi byt take upravena specifikace partition, na ktere se soubor nachazi. V OS MS DOS je partition specifikovana pismenem nasledovanym dvojteckou. Zde by vyse diskutovany odkaz mohl vypadat napr.: 'C:\userb\test'. Jine systemy uzivaji i mnohem komplikovanejsi zpusoby odkazovani na soubory. V OSu VMS muze napr. odkaz na soubor login.com vypadat nasledovne: 'u:(sst.jdeck)login.com;1', kde 'u' je jmeno partition, 'sst' je jmeno adresare, 'jdeck' jmeno podadresare a 1 je cislo verze.
Dalsi systemy vkladaji jmeno partition do plne cesty. Prvni polozka v ceste je jmeno partition, za kterym nasleduje jmeno adresare a souboru, napr. '/u/pbg/test', kde 'u' specifikuje partition, 'pbg' adresar a 'test' jmeno souboru.
Specialni situace nastava v pripade systemovych souboru. Tyto soubory, predstavujici cast OSu (zavadece, linkery, prekladace, knihovny atd.) jsou take definovany jako soubory. Jestlize je OSu zadan nejaky prikaz, soubor je nacten zavadecem do pameti a spusten. Mnoho prikazu predstavuje jmeno souboru, ktery ma byt spusten. Protoze jeste nemame zavedeny zadne systemove adresare, bude spousteny soubor vyhledavan v uzivatelskem adresari. Nyni muzeme resit tento problem pouze tim, ze nakopirujeme veskere systemove soubory do kazdeho uzivatelskeho adresare, coz vsak predstavuje obrovske naroky na diskovy prostor. (Jestlize by systemove soubory zabirali 5 MB, tak pri 12 uzivatelich, by na jejich rozkopirovani padlo 5 * 12 = 60 MB diskoveho prostoru).
Standardni reseni spociva v jemne modifikaci vyhledavaci procedury. Jeden specialni uzivatelsky adresar je definovan tak, ze obsahuje systemove soubory (napr. user 0). Kdykoliv je pristupovano k nejakemu souboru, OS prohleda uzivatelsky adresar. Jestlize je soubor nalezen, je uzit. Pokud nalezen neni, OS automaticky prohleda specialni uzivatelsky adresar systemovych souboru. Poradi prohledavanych adresaru pri hledani souboru se nazyva vyhledavaci cesta (search path). Rozsirenim teto myslenky muze byt, ze vyhledavaci cesta obsahuje neomezeny seznam adresaru. Toho vyuziva Unix a MS DOS.

Zpet

Obsah

Vpred