9. Struktura odkladaciho zarizeni

9.1. Struktura disku

• Disk predstavuje v modernich pocitacich odkladaci zarizeni. Pred nim byvala k tomuto ucelu uzivana magneticka paska. Ta je vsak velmi pomala v porovnani s vybavovaci dobou operacni pameti a zejmena umoznuje pouze sekvencni pristup k souborum. V soucasne dobe jsou pasky uzivany prevazne jako zalohovaci zarizeni, pripadne pro ukladani informaci, ktere nejsou casto vyzadovany nebo jako transportni medium.

• Na informace ulozene na disku se odkazuje prostrednictvim adresy, ktera se sklada z nekolika casti: jednotka (drive), strana (surface), stopa (track) a sektor (sector). Vsechny stopy, ktere jsou v danem okamziku pristupne bez posunu hlavy (tj. ekvivalentni stopy na ruznych stranach) tvori cylinder.

• Uvnitr stopy jsou informace ukladany v sektorech. IBM mainframes umoznuji uzivateli vybrat si velikost sektoru, ale vetsina jinych disku ma velikost sektoru definovanou hardwarove. Sektor je nejmensi jednotka informace, ktera muze byt ctena nebo zapisovana na disk. Velikost sektoru se muze v zavislosti na typu disku pohybovat od 32 B po 4096 B, vetsinou byva 512 B. V jedne stope byva 4 az 32 sektoru a stop na jedne strane muze byt 20 az 1500.

• Chceme-li pristoupit ke konkretnimu sektoru, musime specifikovat celou adresu, tj. jednotku, stranu, stopu a sektor. Aby se bylo mozno snaze mezi sektory orientovat, jsou oddeleny specialni znackou.

• Pred ctenim sektoru se musi cteci-zapisovaci hlavy presunout na spravnou stopu (cas vyhledavani - seek time), elektronicky je vybrana spravna strana. Potom cekame (cekaci doba - latency time) nez se pozadovany sektor natoci pod hlavu. Seek time je podminen casem nutnym pro posun hlav, je-li hlava na vzdalene stope, je doba presunu delsi.

• I/O prenos mezi diskem a pameti je organizovan v jednotkach jednoho ci vice sektoru zvanych bloky, aby se presun maximalne zefektivnil. Adresa konkretniho bloku zahrnuje cislo stopy (nebo cylindru), cislo strany a cislo sektoru. Na kazdy disk lze tedy pohlizet jako na trojrozmerne pole bloku. Obvykle byva toto pole OSem zpracovavano jako jednorozmerne. Adresa bloku roste s bloky na jedne stope, potom se vsemi stopami v cylindru a na zaver od cylindru 0 k poslednimu na disku.

• Uzijeme-li s jako pocet sektoru v ramci stopy, t jako pocet stop v ramci cylindru, potom muzeme konvertovat diskovou adresu i-teho cylindru, j-te strany, k-teho sektoru na jednorozmerne cislo bloku b:
  b = k + s * ( j + i * t )

• Poznamenejme, ze pri tomto mapovani vyzaduje pristup k bloku b + 1, byl-li pred cten blok b presun hlavy pouze v pripade, ze b byl posledni blok jednoho cylindru a b + 1 je prvni blok dalsiho. Pouze v tomto pripade dojde k posunu hlavy, pouze vsak o jednu stopu.

9.2. Planovani disku

• Protoze mnoho uloh pozaduje od disku program a pripadne vstupni a vystupni souboru, je maximalne potrebne, aby disk byl tak rychly, jak je to jen mozne. OS muze zvysit prumernou vybavovaci dobu disku pomoci planovani pozadavku o pristup k disku.

• Rychlost disku sestava ze tri casti. Aby bylo mozno pristoupit k pozadovanemu bloku, je treba nejprve presunout hlavu na patricnou stopu nebo cylindr. Tato operace byva oznacovana jako vyhledavani - seek a cas pro ni potrebny jako doba vyhledavani - seek time. Je-li hlava na spravne stope, musime cekat, nez se pod ni otoci spravny sektor (doba cekani - latency time). Posledni slozkou je cas nutny pro prenos dat mezi diskem a pameti. Ta byva nazyvana cas prenosu - transfer time.

• Kazde I/O zarizeni ma svou frontu nevyrizenych dotazu. Jakmile proces pozaduje cteni nebo zapis na disk, provede volani OSu. Toto volani musi specifikovat nasledujici nutne informace:

• jedna-li se o cteni ci zapis

• jaka je diskova adresa (cislo bloku, prevedene modulem organizace souboru na jednotku, cylindr, stranu a sektor)

• jaka je pametova adresa od ktere ma dojit k ukladani nebo cteni

• jak velka informace ma byt prenesena (pocet bytu)

• Jestlize je pozadovany disk a jeho ovladac volny, muze byt zadosti okamzite vyhoveno. Jestlize vsak bud disk nebo ovladac obsluhuji jinou zadost, vetsinou zadost jineho procesu, musi byt novy pozadavek zarazen do fronty cekajicich.

• V multiprogramovem systemu s mnoha procesy nejsou prilis casto fronty pozadavku na disk prazdne. V tom pripade, je-li aktualni pozadavek vyplnen, je treba vybrat z fronty dalsi a ten obslouzit. Tato obsluha zahrnuje presunuti hlavy na patricnou stopu, cekani na otoceni disku a na zaver vlastni prenos dat.

9.2.1. Planovani FCFS

• Nejjednodussi metodou planovani disku je pochopitelne metoda First-Come First-Served (Prvni prisel, prvni dostal). Tento algoritmus je jednoduchy na naprogramovani, nepodava vsak vzdy optimalni vykony. Uvazujme napr. frontu pozadavku na nasledujici stopy:
  98, 183, 37, 122, 14, 124, 65, 67

• Jestlize je hlava na pocatku na stope 53, je treba ji presunout na stopu 98, potom na 183, 37, 122, 14, 124, 65 a na zaver na stopu 67, pricemz celkovy presun bude o 640 stop. Toto planovani je znazorneno na Obr. 90.

• Problem tohoto planovani jasne ilustruje napriklad divoky vykyv od stopy 122 ke 14 a potom opet na 124. Pokud by pozadavky na cteni ze sektoru 14 a 37 byly obslouzeny po sobe, pred nebo po pozadavcich na stopy 122 a 124, celkovy pocet presunutych sektoru by podstatne poklesl, cimz by se zkratila i vybavovaci doba disku a zvysil se tak jeho vykon.

Obr. 90 FCFS planovani disku

9.2.2. SSTF planovani

• Zda se tedy rozumne, obslouzit spolecne vsechny pozadavky, ktere se na disku odehravaji pobliz. Na tomto predpokladu je postaven planovaci algoritmus Shortest-Seek-Time-First (prvni s nejkratsi vyhledavaci dobou). Algoritmus SSTF vybere z pozadavku vzdy ten, ktery vyvola nejmensi presun hlavy od aktualni pozice.

• V nasem priklade je prvni nejmensi presun ze stopy 53 na stopu 65, dalsi na stopu 67 atd. viz Obr. 91. Toto planovani vyzaduje v nasem pripade celkovy presun hlav o 236 stop, coz je mene nez tretina presunu pri FCFS. Implementaci tohoto algoritmu dojde k podstatnemu zvyseni rychlosti disku.

• SSTF planovani disku je obdobou algoritmu shortest-job-first (SJF) pri planovani CPU a stejne jako algoritmus SJF muze vest k umoreni nekterych pozadavku. Pripomenme, ze v realnem systemu mohou I/O pozadavky na disk prichazet v libovolnem case.

• Mejme napr. ve fronte dva pozadavky na stopy 14 a 186. Jestlize v dobe, kdy je obsluhovan pozadavek 14 dorazi do fronty pozadavek na stopu blizko u 14-te, bude priste obslouzen tento a ne pozadavek na stopu 186. Pokud pri jeho zpracovavani opet dorazi pozadavek na blizky sektor, bude priste _ Teoreticky muze tato situace vest k umoreni pozadavku na stopu 186. Je to sice nepravdepodobne, lec mozne.

• SSTF algoritmus, i kdyz predstavuje vyznamne vylepseni oproti algoritmu FCFS, stale neni optimalni. Jestlize bychom napr. provedli presun hlavy ze stopy 53 na 37, ackoliv tento presun nepredstavuje nejmensi vzdalenost a potom na 14 a dale by jsme obslouzili pozadavky v poradi 65, 67, 98, 122, 124 a 183, redukovali by jsme celkovy pocet proslych stop na 208.

Obr. 91 SSTF planovani disku

9.2.3. SCAN planovani

• Dynamicka podstata planovani front vedla ke vzniku SCAN algoritmu. Cteci hlava zacina na jednom konci disku a presouva se smerem ke druhemu konci a obsluhuje jednotlive pozadavky v okamziku kdy dojede k patricne stope. Dobere-li se cteci hlava opacneho konce, obrati smer sveho pohybu a pokracuje dale. Cteci hlava soustavne projizdi (scans) disk od jednoho konce ke druhemu.

• Opet pouzijeme stejneho prikladu fronty pozadavku:
  98, 186, 37 122, 14, 124, 65, 67

• Pred tim, nez muzeme aplikovat SCAN algoritmus, musime znat smer pohybu hlavy. Hlava se opet nachazi na stope 53 a pohybuje-li se smerem k 0, budou nejprve obslouzeny pozadavky 37 a 14 a pri pohybu hlavy nazpatek potom pozadavky 65, 67, 98, 122, 124 a 183 tak, jak ukazuje Obr. 92.

Obr. 92 SCAN planovani disku

• Jestlize do fronty dorazi pozadavek na stopu "pred hlavou", bude obslouzen okamzite behem aktualniho pohybu, a pokud prijde pozadavek na cteni "za hlavou", musi cekat az se bude hlava pohybovat opet v opacnem smeru.

• SCAN algoritmus byva nekdy oznacovan jako elevator algoritmus, nebot je podobny chovani vytahu, ktery obsluhuje pozadavky na prepravu mezi patry budovy. Jinou analogii muze byt odhrnovani snehu z chodniku behem snehove vanice. Zacneme na jednom konci chodniku, odhrnujeme snih a v okamziku, kdy jsme dorazili na druhy konec, obratime smer a odhazujeme novy snih, ktery napadal za nas.

• Predpokladame-li rovnomerne rozlozeni dotazu na jednotlive stopy, uvazujme, jaka je hustota dotazu v situaci, kdy cteci hlava dosahla konce disku a meni smer. Nyni je obsluhovano casto velmi malo pozadavku, protoze stopy prez nez se hlava vraci byly prochazeny pred malym okamzikem. Nejvetsi hustota pozadavku je na stopy na druhem konci disku, nebot tyto pozadavky cekaji nejdele.

9.2.4. C-SCAN planovani

• Variantou SCAN planovaciho algoritmu, ktera je navrzena tak, aby cekaci doba vsech pozadavku byla co nejjednotnejsi je algoritmu C-SCAN (circular SCAN). Stejne jako algortimus SCAN i C-SCAN vyrizuje pozadavky na disk tak, ze posunuje cteci hlavu od jednoho konce disku k druhemu.

Obr. 93 C-SCAN algortimus planovani disku

• Jakmile cteci hlava dojde konce disku je okamzite presunuta opet na zacatek (aniz by vyrizovala jakekoliv pozadavky) a obsluhu zadosti provadi opet stejnym smerem (viz Obr. 93).

• C-SCAN algoritmus podstatne upravuje pohled na disk. V tomto pripade se zda, jako by byl disk cyklicky a posledni stopa navazovala na stopu prvni.

9.2.5. LOOK planovani

• Poznamnejme, ze u obou drive popisovanych algoritmu (SCAN i C-SCAN) dochazi k pohybu cteci hlavy od jednoho konce disku k druhemu. Timto zpusobem vsak ve skutecnosti neni zadny algoritmus implementovan. Nejcasteji je hlava pousunuta vzdy k posledni zadosti v danem smeru. Jakmile nejsou v aktualnim smeru dalsi pozadavky, smer pohybu hlavy se okamzite obrati. Tyto verze obou algoritmu jsou nazyvany LOOK planovani (algoritmus se podiva po pozadavku nez zmeni smer pohybu hlavy) a C- LOOK planovani.

Obr. 94 C-LOOK algortimus planovani disku

9.2.6. Vyber algoritmu pro planovani disku

• Mame-li k dispozici tolik algoritmu planovani disku, jak vybrat ten pro nas nejvhodnejsi? Algortimus SSTF je velmi prirozeny a casty. Algortimy SCAN a C-SCAN jsou vhodnejsi pro systemy s velkym vyuzitim disku. Je mozne definovat optimalni algoritmus, ale vypocty nutne pro optimalni planovani mohou byt narocnejsi nez planovani pomoci SSTF ci SCAN algoritmu.

• Pri uziti kterehokoliv planovaciho algortimu je vykon disku znacne podminen poctem a typem pozadavku. Je-li ve fronte pouze zridkakdy vice nez jeden pozadavek na disk jsou vsechny algoritmy stejne efektivni. Tehdy je vhodne vyuzit ten nejjednodussi z nich - algoritmus FCFS.

• Poznamenejme, ze pozadavky na disk jsou do znacne miry ovlivnovany pouzitou alokacni metodou. Program, ktery cte souvisle alokovany soubor vyvola nekolik pozadavku, ktere budou obslouzeny na jednom miste disku. naproti tomu spojovany nebo indexovany soubor obsahuje casto bloky, ktere jsou siroce roztristene po celem disku, coz zvysuje jeho vyuziti za cenu casovych ztrat pri castych pohybech hlav.

• Take umisteni adresaru a indexovych bloku ma velky vyznam. Protoze kazdy soubor musi byt nejdrive otevren a az potom uzit a otevreni souboru znamena prohledani adresarove struktury, je k adresarum pristupovano velmi casto. Nutne presuny ctecich hlav je mozno castecne minimalizovat umistenim adresaru doprostred disku, nez k nekteremu kraji. Je-li napr. adresarova polozka umistena na prvni stope a datovy blok na posledni, potom se hlava musi nutne presunout pres cely disk. Je-li adresarova polozka umistena pobliz stredu disku, snizi se tato vzdalenost na polovinu.

• Melo by byt jasno, ze vysledkem techto uvah je algoritmus planovani disku, ktery muze byt, stejne jako ostatni algoritmy, samostatnym modulem operacniho systemu a muze z nej byt odstranen a nahrazen jinym, je- li to zapotrebi.

• Jak FCFS tak SSTF algoritmus je vhodnou pocatecni volbou. Poznamenejme, ze hardwarovy ovladac disku napomaha tvurcum OSu pri planovani disku. OS posila hardwarovemu ovladaci pozadavky ve FCFS poradi a ten je pak provadi v ponekud optimalnejsim sledu.

• Bohuzel, jestlize si OS nevsima metody jakou ovladac pouziva, radi pozadavky do sledu, ktery se mu jevi jako optimalni, avsak hardwarovy ovladac toto poradi zmeni podle sveho a celkovym vysledkem muze byt i snizeni vykonu systemu.

9.3. Management disku

• Existuje mnoho ruznych aspektu spravy disku, ktere provadi OS. My se zde zminime o pocatecni inicializaci disku, bootovani z disku a o praci s vadnymi bloky disku.

9.3.1. Formatovani disku

9.3.2. Boot block

• Pro spusteni pocitace (napr. pri zapnuti nebo rebootovani) je treba spustit inicializacni program. Tento inicializacni programu (ci bootstrap program) musi byt maly. Inicializuje vsechny prvky systemu od registru procesoru pres ovladace zarizeni az po obsah pameti.

• Bootstrap pragram musi vedet, jak zavest a spustit OS. Aby to mohl provest, musi najit jadro OSu a zavest ho do pameti a skocit na inicializacni adresu.

• Jak vi pocitac o umisteni bootstrap programu, aby ho mohl spustit? Nektere systemy (jako napr. Apple Macintosh) uchovavaji vetsi cast bootstram programu v ROM pameti. Toto ulozeni je vyhovujici, nebot ROM pameti nepotrebuji zadnou inicializaci a jsou vzdy pristupne. Problem je v tom, ze zmena bootstrap programu vyzaduje hardwarovou vymenu cipu.

• To jine systemy resi tim, ze v ROM pameti uchovavaji jen minimalni cast bootstrap kodu a zbytek pak udrzuji v boot bloku, na pevne urcenem miste na disku. Disk, na kterem je ulozen boot blok se pak nazyva bootovaci (systemovy) disk a system bez nej nemuze fungovat.

• Kod ulozeny v ROM pameti pozada hardwarovy ovladac disku (softwarovy ovladac disku jeste neni zaveden v pameti) o nacteni boot bloku do pameti a spusti tento nacteny kod. Zmeny bootovaciho kodu se potom provadeji zmenami v boot sektoru.

Obr. 95 Casti disku pod OSem MS DOS

• Bootstrap program uchovavany na disku muze byt rozsahlejsi a dokonalejsi nez program uchovavany v ROM pameti a je schopen zavest cely OS z disku a spustit ho. Presto k tomu staci i velmy maly program (IBM PC uziva napr. pro bootstrap program 512 B velky blok, viz Obr. 96).

9.3.3. Vadne bloky

• Protoze disky obsahuji mechanicke pohyblive casti, byvaji velmi nachylne k chybam. Nekdy dochazi k absolutnim hardwarovym chybam, kdy musi byt disk vymenen a jeho obsah navracen ze zalozni pasky (viz. nas HDD v Amosu, jen s tim rozdilem, ze jsme ho na puasce nemeli). Mnohem casteji vsak dojde k chybe jednoho ci nekolika bloku, ktere jiz nejdou cist ani prepsat. Mnoho disku prichazi s vadnymi bloky jiz od vyrobce. V zavislosti na typu disku a jeho ovladace je s vadnymi bloku nakladano ruznymi zpusoby.

• U pocitacu IBM PC s IDE ovladaci musi byt vadne bloky oznaceny manualne. Prikaz format najde vadne bloky pri logickem formatovani disku a zapise specialni hodnotu do jejich FAT zaznamu, aby jich alokacni rutina nepouzivala. Jestlize se blok pokazi v prubehu pouzivani disku, je treba rucne spustit specialni program, ktery nove vadne bloky zjisti a oznaci. Data ulozena v chybnych blocich jsou obvykle ztracena.

• SCSI disky a ovladace uzivane v pocitacich vyssich trid jsou v obsluze vadnych bloku elegantnejsi. Ovladac udrzuje seznam vadnych bloku na disku, ktery inicializuje behem fyzickeho formatovani disku a obnovuje behem pouzivani disku. Ovladac ponechava stranou vsechny bloky nepouzitelne pro operacni system. Kazdy vadny sektor muze byt logicky nahrazen jinym z volnych. Tato technika je znama jako slipping nebo forwarding sektoru.

• Pokud prijde pozadavek na zapis do sektoru 10 ve stope 12, a kontroler zjisti, ze tento sektor je vadny, zapis se automaticky provede napr. do sektoru 27 ve stope 153. Typicka obsluha vadneho sektoru byva nasledujici:

• OS pozaduje sektor 5, stopu 20

• Ovladac disku vypocita EEC a zjisti, ze sektor je vadny. To oznami OSu.

• Pri nasledujicim rebootu pocitace, je spusten program, ktery SCSI ovladaci sdeli, aby zamelil vadny sektor jinym dobrym

• Az se bude priste OS odkazovat na sektor 5, stopu 20, dotaz je presmerovan ovladacem do jineho sektoru

• Poznamenejme, ze toto presmerovani sektoru ovladacem muze poskodit optimalizace algoritmu planovani disku! Jako reseni Umistuji nektere disky volne sektory pro premisteni do kazdeho cylindru. Potom pri slippingu sektoru je tento nahrazen jinym v temze cylindru. Nebot vadnych sektoru byva malo, dochazi tak ke ztratam diskoveho prostoru.

• Jinym resenim je presunout planovaci algoritmus na ovladac disku, protoze ten zna skutecnou polohu vsech bloku na disku.

• Duvodem, ze automaticky neni provadena take zachrana dat z vadnych bloku je to, ze data ve vadnych blocich byvaji nenavratne ztracena a soubory je treba zachranit bud manualne nebo restaurovat ze zalozniho media.