nyh blokov v superbloke; | | esli (iz spiska udalen poslednij blok) | | { | | zablokirovat' superblok; | | prochitat' blok, tol'ko chto vzyatyj iz spiska svobod- | | nyh (algoritm bread); | | skopirovat' nomera blokov, hranyashchiesya v dannom blo- | | ke, v superblok; | | osvobodit' blochnyj bufer (algoritm brelse); | | snyat' blokirovku s superbloka; | | vozobnovit' vypolnenie processov (posle snyatiya blo- | | kirovki s superbloka); | | } | | poluchit' bufer dlya bloka, udalennogo iz spiska (algo- | | ritm getblk); | | obnulit' soderzhimoe bufera; | | umen'shit' obshchee chislo svobodnyh blokov; | | pometit' superblok kak "izmenennyj"; | | vozvratit' bufer; | | } | +------------------------------------------------------------+ Risunok 4.19. Algoritm vydeleniya diskovogo bloka 81 4.20(g) pokazan zapolnennyj spisok v superbloke i sleduyushchij svyaznoj blok s nomerom 211. Algoritmy naznacheniya i osvobozhdeniya indeksov i diskovyh blokov shodyatsya v tom, chto yadro ispol'zuet superblok v kachestve kesha, hranyashchego ukazateli na svobodnye resursy - nomera blokov i nomera indeksov. Ono podderzhivaet spisok nomerov blokov s ukazatelyami, takoj, chto kazhdyj nomer svobodnogo bloka v fajlovoj sisteme poyavlyaetsya v nekotorom elemente spiska, no yadro ne podder- zhivaet takogo spiska dlya svobodnyh indeksov. Tomu est' tri prichiny. 1. YAdro ustanavlivaet, svoboden li indeks ili net, proveryaya: esli pole tipa fajla ochishcheno, indeks svoboden. YAdro ne nuzhdaetsya v drugom mehanizme opi- saniya svobodnyh indeksov. Tem ne menee, ono ne mozhet opredelit', svoboden li blok ili net, tol'ko vzglyanuv na nego. YAdro ne mozhet ulovit' razlichiya mezhdu maskoj, pokazyvayushchej, chto blok svoboden, i informaciej, sluchajno imeyushchej shodnuyu masku. Sledovatel'no, yadro nuzhdaetsya vo vneshnem mehanizme identifikacii svobodnyh blokov, v kachestve nego v tradicionnyh realizaci- yah sistemy ispol'zuetsya spisok s ukazatelyami. 2. Sama konstrukciya diskovyh blokov navodit na mysl' ob ispol'zovanii spis- kov s ukazatelyami: v diskovom bloke legko razmestit' bol'shie spiski nome- rov svobodnyh blokov. No indeksy ne imeyut podhodyashchego mesta dlya massovogo hraneniya spiskov nomerov svobodnyh indeksov. 3. Pol'zovateli imeyut sklonnost' chashche rashodovat' diskovye bloki, nezheli in- deksy, poetomu kazhushcheesya zapazdyvanie v rabote pri prosmotre diska v po- iskah svobodnyh indeksov ne yavlyaetsya takim kriticheskim, kak esli by ono imelo mesto pri poiskah svobodnyh diskovyh blokov. spisok v superbloke +-----+-----+-----+-----+---------------------+ | 109 | 106 | 103 | 100 | ------------------- | +--+--+-----+-----+-----+---------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +-----+-----+-----+-----+---------------+-----+ (a) Pervonachal'naya konfiguraciya spisok v superbloke +-----+-----+---------------------------------+ | 109 | 949 | ------------------------------- | +--+--+-----+---------------------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +-----+-----+-----+-----+---------------+-----+ (b) Posle osvobozhdeniya bloka s nomerom 949 spisok v superbloke +-----+-----+-----+-----+---------------------+ | 109 | 106 | 103 | 100 | ------------------- | +--+--+-----+-----+-----+---------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +-----+-----+-----+-----+---------------+-----+ (v) Posle naznacheniya bloka s nomerom 949 82 spisok v superbloke +-----+-----+-----+-----+---------------+-----+ | 211 | 208 | 205 | 202 | ------------- | 112 | +--+--+-----+-----+-----+---------------+-----+ +-----+ | 211 | +-----+-----+-----+-----+---------------+-----+ +->| 344 | 341 | 338 | 335 | ------------- | 243 | +-----+-----+-----+-----+---------------+-----+ (g) Novoe zapolnenie spiska v superbloke posle naznacheniya bloka s nomerom 109 Risunok 4.20. Zaprashivanie i osvobozhdenie diskovyh blokov 4.8 DRUGIE TIPY FAJLOV V sisteme UNIX podderzhivayutsya i dva drugih tipa fajlov: kanaly i speci- al'nye fajly. Kanal, inogda nazyvaemyj fifo (sokrashchenno ot "first-in-first-out" - "pervym prishel - pervym vyshel" - poskol'ku obsluzhiva- et zaprosy v poryadke postupleniya), otlichaetsya ot obychnogo fajla tem, chto so- derzhit vremennye dannye: informaciya, odnazhdy schitannaya iz kanala, ne mozhet byt' prochitana vnov'. Krome togo, informaciya chitaetsya v tom poryadke, v koto- rom ona byla zapisana v kanale, i sistema ne dopuskaet nikakih otklonenij ot dannogo poryadka. Sposob hraneniya yadrom informacii v kanale ne otlichaetsya ot sposoba ee hraneniya v obychnom fajle, za isklyucheniem togo, chto zdes' ispol'- zuyutsya tol'ko bloki pryamoj, a ne kosvennoj, adresacii. Konkretnoe predstav- lenie o kanalah mozhno budet poluchit' v sleduyushchej glave. Poslednim tipom fajlov v sisteme UNIX yavlyayutsya special'nye fajly, k ko- torym otnosyatsya special'nye fajly ustrojstv vvoda-vyvoda blokami i special'- nye fajly ustrojstv posimvol'nogo vvoda-vyvoda. Oba podtipa oboznachayut ust- rojstva, i poetomu indeksy takih fajlov ne svyazany ni s kakoj informaciej. Vmesto etogo indeks soderzhit dva nomera - starshij i mladshij nomera ustrojst- va. Starshij nomer ustrojstva ukazyvaet ego tip, naprimer, terminal ili disk, a mladshij nomer ustrojstva - chislovoj kod, identificiruyushchij ustrojstvo v gruppe odnorodnyh ustrojstv. Bolee podrobno special'nye fajly ustrojstv ras- smatrivayutsya v glave 10. 4.9 VYVODY Indeks predstavlyaet soboj strukturu dannyh, v kotoroj opisyvayutsya atri- buty fajla, v tom chisle raspolozhenie informacii fajla na diske. Sushchestvuet dve raznovidnosti indeksa: kopiya na diske, v kotoroj hranitsya informaciya in- deksa, poka fajl nahoditsya v rabote, i kopiya v pamyati, gde hranitsya informa- ciya ob aktivnyh fajlah. Algoritmy ialloc i ifree upravlyayut naznacheniem fajlu diskovogo indeksa vo vremya vypolneniya sistemnyh operacij creat, mknod, pipe i unlink (sm. sleduyushchuyu glavu), a algoritmy iget i iput upravlyayut vydeleniem indeksov v pamyati v moment obrashcheniya processa k fajlu. Algoritm bmap oprede- lyaet mestonahozhdenie diskovyh blokov, prinadlezhashchih fajlu, ispol'zuya predva- ritel'no zadannoe smeshchenie v bajtah ot nachala fajla. Katalogi predstavlyayut soboj fajly, kotorye ustanavlivayut sootvetstvie mezhdu komponentami imen faj- lov i nomerami indeksov. Algoritm namei preobrazuet imena fajlov, s kotorymi rabotayut processy, v identifikatory indeksov, s kotorymi rabotaet yadro. Na- konec, yadro upravlyaet naznacheniem fajlu novyh diskovyh blokov, ispol'zuya al- goritmy alloc i free. 83 Struktury dannyh, rassmotrennye v nastoyashchej glave, sostoyat iz svyazannyh spiskov, hesh-ocheredej i linejnyh massivov, i poetomu algoritmy, rabotayushchie s rassmotrennymi strukturami dannyh, dostatochno prosty. Slozhnosti poyavlyayutsya togda, kogda voznikaet konkurenciya, vyzyvaemaya vzaimodejstviem algoritmov mezhdu soboj, i nekotorye iz etih problem sinhronizacii rassmotreny v tekste. Tem ne menee, algoritmy ne nastol'ko detal'no razrabotany i mogut sluzhit' illyustraciej prostoty konstrukcii sistemy. Vysheopisannye struktury i algoritmy rabotayut vnutri yadra i nevidimy dlya pol'zovatelya. S tochki zreniya obshchej arhitektury sistemy (Risunok 2.1), algo- ritmy, rassmotrennye v dannoj glave, imeyut otnoshenie k nizhnej polovine pod- sistemy upravleniya fajlami. Sleduyushchaya glava posvyashchena razboru obrashchenij k operacionnoj sisteme, obespechivayushchih funkcionirovanie pol'zovatel'skogo in- terfejsa, i opisaniyu verhnej poloviny podsistemy upravleniya fajlami, iz ko- toroj vyzyvaetsya vypolnenie rassmotrennyh zdes' algoritmov. 8. V versii V sistemy UNIX razreshaetsya ispol'zovat' ne bolee 14 simvolov na kazhduyu komponentu imeni puti poiska. Algoritm namei otsekaet lishnie sim- voly v komponente. CHto nuzhno sdelat' v fajlovoj sisteme i v sootvetstvuyu- shchih algoritmah, chtoby stali dopustimymi imena komponent proizvol'noj dli- ny ? 9. Predpolozhim, chto pol'zovatel' imeet zakrytuyu versiyu sistemy UNIX, prichem on vnes v nee takie izmeneniya, chto imya komponenty teper' mozhet sostoyat' iz 30 simvolov; zakrytaya versiya sistemy obespechivaet tot zhe sposob hrane- niya zapisej katalogov, kak i standartnaya operacionnaya sistema, za isklyu- cheniem togo, chto zapisi katalogov imeyut dlinu 32 bajta vmesto 16. Esli pol'zovatel' smontiruet zakrytuyu fajlovuyu sistemu v standartnoj operaci- onnoj srede, chto proizojdet vo vremya raboty algoritma namei, kogda pro- cess obratitsya k fajlu ? *10. Rassmotrim rabotu algoritma namei po preobrazovaniyu imeni puti poiska v identifikator indeksa. V techenie vsego prosmotra yadro proveryaet sootvets- tvie tekushchego rabochego indeksa indeksu kataloga. Mozhet li drugoj process udalit' (unlink) katalog ? Kakim obrazom yadro preduprezhdaet takie dejst- viya ? V sleduyushchej glave my vernemsya k etoj probleme. *11. Razrabotajte strukturu kataloga, povyshayushchuyu effektivnost' poiska imen fajlov bez ispol'zovaniya linejnogo prosmotra. Rassmotrite dva sposoba: heshirovanie i n-arnye derev'ya. *12. Razrabotajte algoritm sokrashcheniya kolichestva prosmotrov kataloga v pois- kah imeni fajla, ispol'zuya zapominanie chasto upotreblyaemyh imen. *13. V ideal'nom sluchae v fajlovoj sisteme ne dolzhno byt' svobodnyh indeksov s nomerami, men'shimi, chem nomer "zapomnennogo" indeksa, ispol'zuemyj al- goritmom ialloc. Kak sluchaetsya, chto eto utverzhdenie byvaet lozhnym ? 14. Superblok yavlyaetsya diskovym blokom i soderzhit krome spiska svobodnyh blokov i druguyu informaciyu, kak pokazano v dannoj glave. Poetomu spisok svobodnyh blokov v superbloke ne mozhet soderzhat' bol'she nomerov svobodnyh blokov, chem mozhet pomestit'sya v odnom diskovom bloke v svyazannom spiske svobodnyh diskovyh blokov. Kakoe chislo nomerov svobodnyh blokov bylo by optimal'nym dlya hraneniya v odnom bloke iz svyazannogo spiska ? 84