4.3 KATALOGI Iz glavy 1 napomnim, chto katalogi yavlyayutsya fajlami, iz kotoryh stroitsya ierarhicheskaya struktura fajlovoj sistemy; oni igrayut vazhnuyu rol' v prevrashche- nii imeni fajla v nomer indeksa. Katalog - eto fajl, soderzhimym kotorogo yav- lyaetsya nabor zapisej, sostoyashchih iz nomera indeksa i imeni fajla, vklyuchennogo v katalog. Sostavnoe imya - eto stroka simvolov, zavershayushchayasya pustym simvo- lom i razdelyaemaya naklonnoj chertoj ("/") na neskol'ko komponent. Kazhdaya kom- ponenta, krome poslednej, dolzhna byt' imenem kataloga, no poslednyaya kompo- nenta mozhet byt' imenem fajla, ne yavlyayushchegosya katalogom. V versii V sistemy UNIX dlina kazhdoj komponenty ogranichivaetsya 14 simvolami; takim obrazom, vmeste s 2 bajtami, otvodimymi na nomer indeksa, razmer zapisi kataloga sos- tavlyaet 16 bajt. +-----------------------------------------------+ | Smeshchenie v bajtah Nomer indeksa Imya | | vnutri kataloga (2 bajta) fajla | +--------------------+---------------+----------+ | 0 | 83 | . | | 16 | 2 | .. | | 32 | 1798 | init | | 48 | 1276 | fsck | | 64 | 85 | clri | | 80 | 1268 | motd | | 96 | 1799 | mount | | 112 | 88 | mknod | | 128 | 2114 | passwd | | 144 | 1717 | umount | | 160 | 1851 | checklist| | 176 | 92 | fsdbld | | 192 | 84 | config | | 208 | 1432 | getty | | 224 | 0 | crash | | 240 | 95 | mkfs | | 256 | 188 | inittab | +--------------------+---------------+----------+ Risunok 4.10. Format kataloga /etc Na Risunke 4.10 pokazan format kataloga "etc". V kazhdom kataloge imeyutsya fajly, v kachestve imen kotoryh ukazany tochka i dve tochki ("." i "..") i no- mera indeksov u kotoryh sovpadayut s nomerami indeksov dannogo kataloga i ro- ditel'skogo kataloga, sootvetstvenno. Nomer indeksa dlya fajla "." v kataloge "/etc" imeet adres so smeshcheniem 0 i znachenie 83. Nomer indeksa dlya fajla ".." imeet adres so smeshcheniem 16 ot nachala kataloga i znachenie 2. Zapisi v kataloge mogut byt' pustymi, pri etom nomer indeksa raven 0. Naprimer, za- pis' s adresom 224 v kataloge "/etc" pustaya, nesmotrya na to, chto ona kog- da-to soderzhala tochku vhoda dlya fajla s imenem "crash". Programma mkfs ini- cializiruet fajlovuyu sistemu takim obrazom, chto nomera indeksov dlya fajlov "." i ".." v kornevom kataloge sovpadayut s nomerom kornevogo indeksa fajlo- voj sistemy. YAdro hranit dannye v kataloge tak zhe, kak ono eto delaet v fajle obychno- go tipa, ispol'zuya indeksnuyu strukturu i bloki s urovnyami pryamoj i kosvennoj adresacii. Processy mogut chitat' dannye iz katalogov takim zhe obrazom, kak 70 oni chitayut obychnye fajly, odnako isklyuchitel'noe pravo zapisi v katalog re- zerviruetsya yadrom, blagodarya chemu obespechivaetsya pravil'nost' struktury ka- taloga. Prava dostupa k katalogu imeyut sleduyushchij smysl: pravo chteniya daet processam vozmozhnost' chitat' dannye iz kataloga; pravo zapisi pozvolyaet pro- cessu sozdavat' novye zapisi v kataloge ili udalyat' starye (s pomoshch'yu sis- temnyh operacij creat, mknod, link i unlink), v rezul'tate chego izmenyaetsya soderzhimoe kataloga; pravo ispolneniya pozvolyaet processu proizvodit' poisk v kataloge po imeni fajla (poskol'ku "ispolnyat'" katalog bessmyslenno). Na primere Uprazhneniya 4.6 pokazana raznica mezhdu chteniem i poiskom v kataloge. 4.4 PREVRASHCHENIE SOSTAVNOGO IMENI FAJLA (PUTI POISKA) V IDENTIFIKATOR INDEKSA Nachal'noe obrashchenie k fajlu proizvoditsya po ego sostavnomu imeni (imeni puti poiska), kak v komandah open, chdir (izmenit' katalog) ili link. Pos- kol'ku vnutri sistemy yadro rabotaet s indeksami, a ne s imenami putej pois- ka, ono preobrazuet imena putej poiska v identifikatory indeksov, chtoby pro- izvodit' dostup k fajlam. Algoritm namei proizvodit poelementnyj analiz sos- tavnogo imeni, stavya v sootvetstvie kazhdoj komponente imeni indeks i katalog i v konce koncov vozvrashchaya identifikator indeksa dlya vvedennogo imeni puti poiska (Risunok 4.11). Iz glavy 2 napomnim, chto kazhdyj process svyazan s tekushchim katalogom (i protekaet v ego ramkah); rabochaya oblast', otvedennaya pod zadachu pol'zovate- lya, soderzhit ukazatel' na indeks tekushchego kataloga. Tekushchim katalogom pervo- go iz processov v sisteme, nulevogo processa, yavlyaetsya kornevoj katalog. Put' k tekushchemu katalogu kazhdogo novogo processa beret nachalo ot tekushchego kataloga processa, yavlyayushchegosya roditel'skim po otnosheniyu k dannomu (sm. raz- del 5.10). Processy izmenyayut tekushchij katalog, zaprashivaya vypolnenie sistem- noj operacii chdir (izmenit' katalog). Vse poiski fajlov po imeni nachinayutsya s tekushchego kataloga processa, esli tol'ko imya puti poiska ne predvaryaetsya naklonnoj chertoj, ukazyvaya, chto poisk nuzhno nachinat' s kornevogo kataloga. V lyubom sluchae yadro mozhet legko obnaruzhit' indeks kataloga, s kotorogo nachina- etsya poisk. Tekushchij katalog hranitsya v rabochej oblasti processa, a kornevoj indeks sistemy hranitsya v global'noj peremennoj (**). Algoritm namei ispol'zuet pri analize sostavnogo imeni puti poiska pro- mezhutochnye indeksy; nazovem ih rabochimi indeksami. Indeks kataloga, otkuda poisk beret nachalo, yavlyaetsya pervym rabochim indeksom. Na kazhdoj iteracii cikla algoritma yadro proveryaet sovpadenie rabochego indeksa s indeksom kata- loga. V protivnom sluchae, narushilos' by utverzhdenie, chto tol'ko fajly, ne yavlyayushchiesya katalogami, mogut byt' list'yami dereva fajlovoj sistemy. Process takzhe dolzhen imet' pravo proizvodit' poisk v kataloge (razresheniya na chtenie nedostatochno). Kod identifikacii pol'zovatelya dlya processa dolzhen sootvetst- vovat' kodu individual'nogo ili gruppovogo vla- del'ca fajla i dolzhno byt' predostavleno pravo ispolneniya, libo poisk nuzhno razreshit' vsem pol'zovatelyam. V protivnom sluchae, poisk ne poluchitsya. YAdro vypolnyaet linejnyj poisk fajla v kataloge, associirovannom s rabo- chim indeksom, pytayas' najti dlya komponenty imeni puti poiska podhodyashchuyu za- pis' v kataloge. Ishodya iz adresa smeshcheniya v bajtah vnutri kataloga (nachinaya s 0), ono opredelyaet mestopolozhenie diskovogo bloka v sootvetstvii s algo- ritmom bmap i schityvaet etot blok, ispol'zuya algoritm bread. Po imeni kompo- --------------------------------------- (**) CHtoby izmenit' dlya sebya kornevoj katalog fajlovoj sistemy, process mo- zhet zapustit' sistemnuyu operaciyu chroot. Novoe znachenie kornya sohranya- etsya v rabochej oblasti processa. 71 +------------------------------------------------------------+ | algoritm namei /* prevrashchenie imeni puti poiska v indeks */| | vhodnaya informaciya: imya puti poiska | | vyhodnaya informaciya: zablokirovannyj indeks | | { | | esli (put' poiska beret nachalo s kornya) | | rabochij indeks = indeksu kornya (algoritm iget); | | v protivnom sluchae | | rabochij indeks = indeksu tekushchego kataloga | | (algoritm iget); | | | | vypolnit' (poka put' poiska ne konchilsya) | | { | | schitat' sleduyushchuyu komponentu imeni puti poiska; | | proverit' sootvetstvie rabochego indeksa katalogu | | i prava dostupa; | | esli (rabochij indeks sootvetstvuet kornyu i kompo- | | nenta imeni "..") | | prodolzhit'; /* cikl s usloviem prodolzheniya */| | schitat' katalog (rabochij indeks), povtoryaya algo- | | ritmy bmap, bread i brelse; | | esli (komponenta sootvetstvuet zapisi v kataloge | | (rabochem indekse)) | | { | | poluchit' nomer indeksa dlya sovpavshej komponen-| | ty; | | osvobodit' rabochij indeks (algoritm iput); | | rabochij indeks = indeksu sovpavshej komponenty | | (algoritm iget); | | } | | v protivnom sluchae /* komponenta otsutstvuet v | | kataloge */ | | vozvratit' (net indeksa); | | } | | vozvratit' (rabochij indeks); | | } | +------------------------------------------------------------+ Risunok 4.11. Algoritm prevrashcheniya imeni puti poiska v indeks nenty yadro proizvodit v bloke poisk, predstavlyaya soderzhimoe bloka kak posle- dovatel'nost' zapisej kataloga. Pri obnaruzhenii sovpadeniya yadro perepisyvaet nomer indeksa iz dannoj tochki vhoda, osvobozhdaet blok (algoritm brelse) i staryj rabochij indeks (algoritm iput), i perenaznachaet indeks najdennoj kom- ponenty (algoritm iget). Novyj indeks stanovitsya rabochim indeksom. Esli yadro ne nahodit v bloke podhodyashchego imeni, ono osvobozhdaet blok, pribavlyaet k ad- resu smeshcheniya chislo bajtov v bloke, prevrashchaet novyj adres smeshcheniya v nomer diskovogo bloka (algoritm bmap) i chitaet sleduyushchij blok. YAdro povtoryaet etu proceduru do teh por, poka imya komponenty puti poiska ne sovpadet s imenem tochki vhoda v kataloge, libo do teh por, poka ne budet dostignut konec kata- loga. Predpolozhim, naprimer, chto processu nuzhno otkryt' fajl "/etc/ passwd". Kogda yadro nachinaet analizirovat' imya fajla, ono natalkivaetsya na naklonnuyu chertu ("/") i poluchaet indeks kornya sistemy. Sdelav koren' tekushchim rabochim indeksom, yadro natalkivaetsya na stroku "etc". Proveriv sootvetstvie tekushchego indeksa katalogu ("/") i nalichie u processa prava proizvodit' poisk v kata- loge, yadro ishchet v kornevom kataloge fajl s imenem "etc". Ono prosmatrivaet kornevoj katalog blok za blokom i issleduet kazhduyu zapis' v bloke, poka ne 72 obnaruzhit tochku vhoda dlya fajla "etc". Najdya etu tochku vhoda, yadro osvobozh- daet indeks, otvedennyj dlya kornya (algoritm iput), i vydelyaet indeks fajlu "etc" (algoritm iget) v sootvetstvii s nomerom indeksa v obnaruzhennoj zapi- si. Udostoverivshis' v tom, chto "etc" yavlyaetsya katalogom, a takzhe v tom, chto imeyutsya neobhodimye prava proizvodit' poisk, yadro prosmatrivaet katalog "etc" blok za blokom v poiskah zapisi, sootvetstvuyushchej fajlu "passwd". Esli posmotret' na Risunok 4.10, mozhno uvidet', chto zapis' o fajle "passwd" yavlya- etsya devyatoj zapis'yu v kataloge. Obnaruzhiv ee, yadro osvobozhdaet indeks, vy- delennyj fajlu "etc", i vydelyaet indeks fajlu "passwd", posle chego - pos- kol'ku imya puti poiska ischerpano - vozvrashchaet etot indeks processu. Estestvenno zadat' vopros ob effektivnosti linejnogo poiska v kataloge zapisi, sootvetstvuyushchej komponente imeni puti poiska. Richi pokazyvaet (sm. [Ritchie 78b], str.1968), chto linejnyj poisk effektiven, poskol'ku on ogra- nichen razmerom kataloga. Bolee togo, rannie versii sistemy UNIX ne rabotali eshche na mashinah s bol'shim ob®emom pamyati, poetomu znachitel'nyj upor byl sde- lan na prostye algoritmy, takie kak algoritmy linejnogo poiska. Bolee slozh- nye shemy poiska potrebovali by otlichnoj, bolee slozhnoj, struktury kataloga, i vozmozhno rabotali by medlennee dazhe v nebol'shih katalogah po sravneniyu so shemoj linejnogo poiska. 4.5 SUPERBLOK Do sih por v etoj glave opisyvalas' struktura fajla, pri etom predpola- galos', chto indeks predvaritel'no svyazyvalsya s fajlom i chto uzhe byli oprede- leny diskovye bloki, soderzhashchie informaciyu. V sleduyushchih razdelah opisyvaet- sya, kakim obrazom yadro naznachaet indeksy i diskovye bloki. CHtoby ponyat' eti algoritmy, rassmotrim strukturu superbloka. Superblok sostoit iz sleduyushchih polej: * razmer fajlovoj sistemy, * kolichestvo svobodnyh blokov v fajlovoj sisteme, * spisok svobodnyh blokov, imeyushchihsya v fajlovoj sisteme, * indeks sleduyushchego svobodnogo bloka v spiske svobodnyh blokov, * razmer spiska indeksov, * kolichestvo svobodnyh indeksov v fajlovoj sisteme, * spisok svobodnyh indeksov v fajlovoj sisteme, * sleduyushchij svobodnyj indeks v spiske svobodnyh indeksov, * zablokirovannye polya dlya spiska svobodnyh blokov i svobodnyh indeksov, * flag, pokazyvayushchij, chto v superblok byli vneseny izmeneniya. V ostavshejsya chasti glavy budet ob®yasneno, kak pol'zovat'sya massivami, ukazatelyami i zamkami blokirovki. YAdro periodicheski perepisyvaet superblok na disk, esli v superblok byli vneseny izmeneniya, dlya togo, chtoby obespechi- valas' soglasovannost' s dannymi, hranyashchimisya v fajlovoj sisteme. 4.6 NAZNACHENIE INDEKSA NOVOMU FAJLU Dlya vydeleniya izvestnogo indeksa, to est' indeksa, dlya kotorogo predva- ritel'no opredelen sobstvennyj nomer (i nomer fajlovoj sistemy), yadro is- pol'zuet algoritm iget. V algoritme namei, naprimer, yadro opredelyaet nomer indeksa, ustanavlivaya sootvetstvie mezhdu komponentoj imeni puti poiska i imenem v kataloge. Drugoj algoritm, ialloc, vypolnyaet naznachenie diskovogo indeksa vnov' sozdavaemomu fajlu. Kak uzhe govorilos' v glave 2, v fajlovoj sisteme imeetsya linejnyj spisok indeksov. Indeks schitaetsya svobodnym, esli pole ego tipa hranit nulevoe zna- chenie. Esli processu ponadobilsya novyj indeks, yadro teoreticheski moglo by proizvesti poisk svobodnogo indeksa v spiske indeksov. Odnako, takoj poisk oboshelsya by dorogo, poskol'ku potreboval by po men'shej mere odnu operaciyu 73 chteniya (dopustim, s diska) na kazhdyj indeks. Dlya povysheniya proizvoditel'nos- ti v superbloke fajlovoj sistemy hranitsya massiv nomerov svobodnyh indeksov v fajlovoj sisteme. Na Risunke 4.12 priveden algoritm ialloc naznacheniya novyh indeksov. Po prichinam, o kotoryh pojdet rech' nizhe, yadro snachala proveryaet, ne zablokiro- val li kakoj-libo process svoim obrashcheniem spisok svobodnyh indeksov v su- +------------------------------------------------------------+ | algoritm ialloc /* vydelenie indeksa */ | | vhodnaya informaciya: fajlovaya sistema | | vyhodnaya informaciya: zablokirovannyj indeks | | { | | vypolnit' | | { | | esli (superblok zablokirovan) | | { | | priostanovit'sya (poka superblok ne osvoboditsya); | | prodolzhit'; /* cikl s usloviem prodolzheniya */ | | } | | esli (spisok indeksov v superbloke pust) | | { | | zablokirovat' superblok; | | vybrat' zapomnennyj indeks dlya poiska svobodnyh | | indeksov; | | iskat' na diske svobodnye indeksy do teh por, poka| | superblok ne zapolnitsya, ili poka ne budut naj- | | deny vse svobodnye indeksy (algoritmy bread i | | brelse); | | snyat' blokirovku s superbloka; | | vozobnovit' vypolnenie processa (kak tol'ko super-| | blok osvoboditsya); | | esli (na diske otsutstvuyut svobodnye indeksy) | | vozvratit' (net indeksov); | | zapomnit' indeks s naibol'shim nomerom sredi naj- | | dennyh dlya posleduyushchih poiskov svobodnyh indek- | | sov; | | } | | /* spisok indeksov v superbloke ne pust */ | | vybrat' nomer indeksa iz spiska indeksov v superblo- | | ke; | | poluchit' indeks (algoritm iget); | | esli (indeks posle vsego etogo ne svoboden) /* !!! */| | { | | perepisat' indeks na disk; | | osvobodit' indeks (algoritm iput); | | prodolzhit'; /* cikl s usloviem prodolzheniya */ | | } | | /* indeks svoboden */ | | inicializirovat' indeks; | | perepisat' indeks na disk; | | umen'shit' schetchik svobodnyh indeksov v fajlovoj sis- | | teme; | | vozvratit' (indeks); | | } | | } | +------------------------------------------------------------+ Risunok 4.12. Algoritm naznacheniya novyh indeksov 74 perbloke. Esli spisok nomerov indeksov v superbloke ne pust, yadro naznachaet nomer sleduyushchego indeksa, vydelyaet dlya vnov' naznachennogo diskovogo indeksa svobodnyj indeks v pamyati, ispol'zuya algoritm iget (chitaya indeks s diska, esli neobhodimo), kopiruet diskovyj indeks v pamyat', inicializiruet polya v indekse i vozvrashchaet indeks zablokirovannym. Zatem yadro korrektiruet disko- vyj indeks, ukazyvaya, chto k indeksu proizoshlo obrashchenie. Nenulevoe znachenie polya tipa fajla govorit o tom, chto diskovyj indeks naznachen. V prostejshem sluchae s indeksom vse v poryadke, no v usloviyah konkurencii delaetsya neobho- dimym provedenie dopolnitel'nyh proverok, na chem my eshche kratko ostanovimsya. Grubo govorya, konkurenciya voznikaet, kogda neskol'ko processov vnosyat izme- neniya v obshchie informacionnye struktury, tak chto rezul'tat zavisit ot ochered- nosti vypolneniya processov, pust' dazhe vse processy budut podchinyat'sya proto- kolu blokirovki. Zdes' predpolagaetsya, naprimer, chto process mog by poluchit' uzhe ispol'zuemyj indeks. Konkurenciya svyazana s problemoj vzaimnogo isklyuche- niya, opisannoj v glave 2, s odnim zamechaniem: razlichnye shemy blokirovki re- shayut problemu vzaimnogo isklyucheniya, no ne mogut sami po sebe reshit' vse problemy konkurencii. Esli spisok svobodnyh indeksov v superbloke pust, yadro prosmatrivaet disk i pomeshchaet v superblok kak mozhno bol'she nomerov svobodnyh indeksov. Pri etom yadro blok za blokom schityvaet indeksy s diska i napolnyaet spisok nome- rov indeksov v superbloke do otkaza, zapominaya indeks s nomerom, naibol'shim sredi najdennyh. Nazovem etot indeks "zapomnennym"; eto poslednij indeks, zapisannyj v superblok. V sleduyushchij raz, kogda yadro budet iskat' na diske svobodnye indeksy, ono ispol'zuet zapomnennyj indeks v kachestve startovoj tochki, blagodarya chemu garantiruetsya, chto yadru ne pridetsya zrya tratit' vremya na schityvanie diskovyh blokov, v koto- ryh svobodnye indeksy navernyaka otsutstvuyut. Posle formirovaniya novogo nabo- ra nomerov svobodnyh indeksov yadro zapuskaet algoritm naznacheniya indeksa s samogo nachala. Vsyakij raz, kogda yadro naznachaet diskovyj indeks, ono umen'- shaet znachenie schetchika svobodnyh indeksov, zapisannoe v superbloke. Rassmotrim dve pary massivov nomerov svobodnyh indeksov (Risunok 4.13). Esli spisok svobodnyh indeksov v superbloke imeet vid pervogo massiva na Ri- sunke 4.13(a) pri naznachenii indeksa yadrom, to znachenie ukazatelya na sleduyu- shchij nomer indeksa umen'shaetsya do 18 i vybiraetsya indeks s nomerom 48. Esli zhe spisok vyglyadit kak pervyj massiv na Risunke 4.13(b), yadro zametit, chto massiv pust i obratitsya v poiskah svobodnyh indeksov k disku, pri etom poisk budet proizvodit'sya, nachinaya s indeksa s nomerom 470, kotoryj byl ranee za- pomnen. Kogda yadro zapolnit spisok svobodnyh indeksov v superbloke do otka- Spisok svobodnyh indeksov v superbloke +---------------------+------+------+-------------------+ | svobodnye indeksy | | | pustota | |<>| 83 | 48 |<>| +---------------------+------+------+-------------------+ 18 19 20 massiv 1 ^ | ukazatel' Spisok svobodnyh indeksov v superbloke +---------------------+------+------+-------------------+ | svobodnye indeksy | | | pustota | |<>| 83 | <|>| +---------------------+------+------+-------------------+ 18 19 20 massiv 1 ^ | ukazatel' (a) Naznachenie svobodnogo indeksa iz serediny spiska 75 Spisok svobodnyh indeksov v superbloke +------+------------------------------------------------+ | 470 | pustota | |<|>| +------+------------------------------------------------+ 0  massiv 1 ^  |ukazatel' (zapomnennyj indeks)   Spisok svobodnyh indeksov v superbloke +------+------------------------------+-----+-----+-----+ | 535 | svobodnye indeksy | 476 | 475 | 471 | |<||||>| +------+------------------------------+-----+-----+-----+ 0 48 49 50 ^ ukazatel' | (b) Naznachenie svobodnogo indeksa, kogda spisok v super- bloke pust Risunok 4.13. Dva massiva nomerov svobodnyh indeksov za, ono zapomnit poslednij indeks v kachestve nachal'noj tochki dlya posleduyushchih prosmotrov diska. YAdro proizvodit naznachenie fajlu tol'ko chto vybrannogo s diska indeksa (pod nomerom 471 na risunke) i prodolzhaet prervannuyu obrabot- ku. +------------------------------------------------------------+ | algoritm ifree /* osvobozhdenie indeksa */ | | vhodnaya informaciya: nomer indeksa v fajlovoj sisteme | | vyhodnaya informaciya: otsutstvuet | | { | | uvelichit' na 1 schetchik svobodnyh indeksov v fajlovoj | | sisteme; | | esli (superblok zablokirovan) | | vozvratit' upravlenie; | | esli (spisok indeksov zapolnen) | | { | | esli (nomer indeksa men'she nomera indeksa, zapom- | | nennogo dlya posleduyushchego prosmotra) | | zapomnit' dlya posleduyushchego prosmotra nomer | | vvedennogo indeksa; | | } | | v protivnom sluchae | | sohranit' nomer indeksa v spiske indeksov; | | vozvratit' upravlenie; | | } | +------------------------------------------------------------+ Risunok 4.14. Algoritm osvobozhdeniya indeksa Algoritm osvobozhdeniya indeksa postroen znachitel'no proshche. Uvelichiv na edinicu obshchee kolichestvo dostupnyh v fajlovoj sisteme indeksov, yadro prove- ryaet nalichie blokirovki u superbloka. Esli on zablokirovan, yadro, chtoby pre- dotvratit' konkurenciyu, nemedlenno soobshchaet: nomer indeksa otsutstvuet v su- perbloke, no indeks mozhet byt' najden na diske i dostupen dlya perenaznache- 76 niya. Esli spisok ne zablokirovan, yadro proveryaet, imeetsya li mesto dlya novyh nomerov indeksov i esli da, pomeshchaet nomer indeksa v spisok i vyhodit iz al- goritma. Esli spisok polon, yadro ne smozhet v nem sohranit' vnov' osvobozhden- nyj indeks. Ono sravnivaet nomer osvobozhdennogo indeksa s nomerom zapomnen- nogo indeksa. Esli nomer osvobozhdennogo indeksa men'she nomera zapomnennogo, yadro zapominaet nomer vnov' osvobozhdennogo indeksa, vybrasyvaya iz superbloka nomer starogo zapomnennogo indeksa. Indeks ne teryaetsya, poskol'ku yadro mozhet najti ego, prosmatrivaya spisok indeksov na diske. YAdro podderzhivaet struktu- ru spiska v superbloke takim obrazom, chto poslednij nomer, vybiraemyj im iz spiska, i est' nomer zapomnennogo indeksa. V ideale ne dolzhno byt' svobodnyh indeksov s nomerami, men'- +------+------------------------------+-----+-----+-----+ | 535 | svobodnye indeksy | 476 | 475 | 471 | |<||||>| +------+------------------------------+-----+-----+-----+ 0 ^ 48 49 50 | ^ zapomnennyj indeks ukazatel' | (a) Pervonachal'nyj vid spiska svobodnyh indeksov v super- bloke +------+------------------------------+-----+-----+-----+ | 499 | svobodnye indeksy | 476 | 475 | 471 | |<||||>| +------+------------------------------+-----+-----+-----+ 0 ^ 48 49 50 | ^ zapomnennyj indeks ukazatel' | (b) Osvobodilsya indeks nomer 499 +------+------------------------------+-----+-----+-----+ | 499 | svobodnye indeksy | 476 | 475 | 471 | |<||||>| +------+------------------------------+-----+-----+-----+ 0 ^ 48 49 50 | ^ zapomnennyj indeks ukazatel' | (v) Osvobodilsya indeks nomer 601 Risunok 4.15. Razmeshchenie nomerov svobodnyh indeksov v superb- loke shimi, chem nomer zapomnennogo indeksa, no vozmozhny i isklyucheniya. Rassmotrim dva primera osvobozhdeniya indeksov. Esli v spiske svobodnyh indeksov v superbloke eshche est' mesto dlya novyh nomerov svobodnyh indeksov (kak na Risunke 4.13(a)), yadro pomeshchaet v spisok novyj nomer, perestavlyaet ukazatel' na sleduyushchij svobodnyj indeks i prodolzhaet vypolnenie processa. No esli spisok svobodnyh indeksov zapolnen (Risunok 4.15), yadro sravnivaet no- mer osvobozhdennogo indeksa s nomerom zapomnennogo indeksa, s kotorogo nach- netsya prosmotr diska v sleduyushchij raz. Esli vnachale spisok svobodnyh indeksov imel vid, kak na Risunke 4.15(a), to kogda yadro osvobozhdaet indeks s nomerom 499, ono zapominaet ego i vytalkivaet nomer 535 iz spiska. Esli zatem yadro osvobozhdaet indeks s nomerom 601, soderzhimoe spiska svobodnyh indeksov ne izmenitsya. Kogda pozdnee yadro ispol'zuet vse indeksy iz spiska svobodnyh in- 77 deksov v superbloke, ono obratitsya v poiskah svobodnyh indeksov k disku, pri etom, nachav prosmotr s indeksa s nomerom 499, ono snova obnaruzhit indeksy 535 i 601. Process A Process B Process C +------------------------------------------------------------ | Naznachaet indeks I - - | iz superbloka - - | - - | Priostanavlivaetsya - - | na vremya schityvaniya - - | indeksa (a) - - | - - - | - Pytaetsya naznachit' - | - indeks iz superbloka - | - - | - Superblok pust (b) - | - - | - Prosmatrivaet disk v - | - poiskah svobodnyh in- - | - deksov, pomeshchenie in- - | - deksa I v superblok - | - (v) - | - - - | Indeks I v pamyati - - | Vypolnyayutsya obychnye - - | dejstviya - - | - - - | - Zakanchivaet prosmotr, - | - naznachaet drugoj indeks - | - (g) - | - - - | - - Naznachaet indeks I | - - iz superbloka | - - | - - Indeks I uzhe ispol'- | - - zuetsya ! | - - | - - Naznachaet drugoj | - - indeks (d) | - - v Vremya Risunok 4.16. Konkurenciya v naznachenii indeksov V predydushchem paragrafe opisyvalis' prostye sluchai raboty algoritmov. Te- per' rassmotrim sluchaj, kogda yadro naznachaet novyj indeks i zatem kopiruet ego v pamyat'. V algoritme predpolagaetsya, chto yadro mozhet i obnaruzhit', chto indeks uzhe naznachen. Nesmotrya na redkost' takoj situacii, obsudim etot slu- chaj (s pomoshch'yu Risunkov 4.16 i 4.17). Pust' u nas est' tri processa, A, B i C, i pust' yadro, dejstvuya ot imeni processa A (***), naznachaet indeks I, no priostanavlivaet vypolnenie processa pered tem, kak skopirovat' diskovyj in- deks v pamyat'. Algoritmy iget (vyzvannyj algoritmom --------------------------------------- (***) Kak i v predydushchej glave, zdes' pod "processom" imeetsya vvidu "yadro, dejstvuyushchee ot imeni processa". 78 |Vremya | +---+---+---+--------------------------------+ | (a) | | | | | | | | | I | ------------------------------ | | | | | | | | +---+---+---+--------------------------------+ | +--------------------------------------------+ | (b) | pusto | | | ----------------------------- | | | | | +--------------------------------------------+ | +---+---+---+--------------------+---+---+---+ | (v) | | | | | | | | | | | | | svobodnye indeksy | J | I | K | | | --|---|---|--------------------|---|---|-- | | +---+---+---+--------------------+---+---+---+ | +---+---+---+--------------------+---+---+---+ | (g) | | | | | | | | | | | | | svobodnye indeksy | J | I | | | | --|---|---|--------------------|---|---| | | +---+---+---+--------------------+---+---+---+ | +---+---+---+----------------+---+---+---+---+ | (d) | | | | svobodnye | | | | | | | | | | indeksy | L | | | | | | --|---|---|----------------|---| | | | | +---+---+---+----------------+---+---+---+---+ v Risunok 4.17. Konkurenciya v naznachenii indeksov (prodolzhenie) ialloc) i bread (vyzvannyj algoritmom iget) dayut processu A dostatochno voz- mozhnostej dlya priostanovleniya svoej raboty. Predpolozhim, chto poka process A priostanovlen, process B pytaetsya naznachit' novyj indeks, no obnaruzhivaet, chto spisok svobodnyh indeksov v superbloke pust. Process B prosmatrivaet disk v poiskah svobodnyh indeksov, i nachinaet eto delat' s indeksa, imeyushchego men'shij nomer po sravneniyu s indeksom, naznachennym processom A. Vozmozhno, chto process B obnaruzhit indeks I na diske svobodnym, tak kak process A vse eshche priostanovlen, a yadro eshche ne znaet, chto etot indeks sobirayutsya nazna- chit'. Process B, ne osoznavaya opasnosti, zakanchivaet prosmotr diska, zapol- nyaet superblok svobodnymi (predpolozhitel'no) indeksami, naznachaet indeks i uhodit so sceny. Odnako, indeks I ostaetsya v spiske nomerov svobodnyh indek- sov v superbloke. Kogda process A vozobnovlyaet vypolnenie, on zakanchivaet naznachenie indeksa I. Teper' dopustim, chto process C zatem zatreboval indeks i sluchajno vybral indeks I iz spiska v superbloke. Kogda on obratitsya k ko- pii indeksa v pamyati, on obnaruzhit iz ustanovki tipa fajla, chto indeks uzhe naznachen. YAdro proveryaet eto uslovie i, obnaruzhiv, chto etot indeks naznachen, pytaetsya naznachit' drugoj. Nemedlennaya perepis' skorrektirovannogo indeksa na disk posle ego naznacheniya v sootvetstvii s algoritmom ialloc snizhaet opasnost' konkurencii, poskol'ku pole tipa fajla budet soderzhat' pometku o tom, chto indeks ispol'zovan. Blokirovka spiska indeksov v superbloke pri chtenii s diska ustranyaet drugie vozmozhnosti dlya konkurencii. Esli superblok ne zablokirovan, process mozhet obnaruzhit', chto on pust, i popytat'sya zapolnit' ego s diska, vremya ot vremeni priostanavlivaya svoe vypolnenie do zaversheniya operacii vvoda-vyvoda. Predpolozhim, chto vtoroj process tak zhe pytaetsya naznachit' novyj indeks i ob- naruzhivaet, chto spisok pust. On tozhe popytaetsya zapolnit' spisok s diska. V luchshem sluchae, oba processa produbliruyut drug druga i potratyat energiyu cent- ral'nogo processora. V hudshem, uchastitsya konkurenciya, podobnaya toj, kotoraya 79 opisana v predydushchem paragrafe. Shodnym obrazom, esli process, osvobozhdaya indeks, ne proveril nalichie blokirovki spiska, on mozhet zateret' nomera in- deksov uzhe v spiske svobodnyh indeksov, poka drugoj process budet zapolnyat' etot spisok informaciej s diska. I opyat' uchastitsya konkurenciya vysheopisanno- go tipa. Nesmotrya na to, chto yadro bolee ili menee udachno upravlyaetsya s nej, proizvoditel'nost' sistemy snizhaetsya. Ustanovka blokirovki dlya spiska svo- bodnyh indeksov v superbloke ustranyaet takuyu konkurenciyu. 4.7 VYDELENIE DISKOVYH BLOKOV Kogda process zapisyvaet dannye v fajl, yadro dolzhno vydelyat' iz fajlovoj sistemy diskovye bloki pod informacionnye bloki pryamoj adresacii i inogda pod bloki kosvennoj adresacii. Superblok fajlovoj sistemy soderzhit massiv, ispol'zuemyj dlya hraneniya nomerov svobodnyh diskovyh blokov v fajlovoj sis- teme. Servisnaya programma mkfs ("make file system" - sozdat' fajlovuyu siste- mu) organizuet informacionnye bloki v fajlovoj sisteme v vide spiska s uka- zatelyami tak, chto kazhdyj element spiska ukazyvaet na diskovyj blok, v koto- rom hranitsya massiv nomerov svobodnyh diskovyh blokov, a odin iz elementov massiva hranit nomer sleduyushchego bloka dannogo spiska. Kogda yadru nuzhno vydelit' blok iz fajlovoj sistemy (algoritm alloc, Ri- sunok 4.19), ono vydelyaet sleduyushchij iz blokov, imeyushchihsya v spiske v superb- loke. Vydelennyj odnazhdy, blok ne mozhet byt' perenaznachen do teh por, poka ne osvoboditsya. Esli vydelennyj blok yavlyaetsya poslednim blokom, imeyushchimsya v keshe superbloka, yadro traktuet ego kak ukazatel' na blok, v kotorom hranitsya spisok svobodnyh blokov. YAdro chitaet blok, zapolnyaet massiv v superbloke no- vym spiskom nomerov blokov i posle etogo prodolzhaet rabotu s pervonachal'nym nomerom bloka. Ono vydelyaet bufer dlya bloka i ochishchaet soderzhimoe bufera (ob- nulyaet ego). Diskovyj blok teper' schitaetsya naznachennym i u yadra est' bufer dlya raboty s nim. Esli v fajlovoj sisteme net svobodnyh blokov, vyzyvayushchij process poluchaet soobshchenie ob oshibke. Esli process zapisyvaet v fajl bol'shoj ob®em informacii, on neodnokratno zaprashivaet u sistemy bloki dlya hraneniya informacii, no yadro naznachaet kazh- spisok v superbloke +-----+-----+-----+-----+---------------------+ | 109 | 106 | 103 | 100 | ------------------- | +--+--+-----+-----+-----+---------------------+ +-----+ | 109 | +-----+-----+-----+-----+---------------+-----+ +->| 211 | 208 | 205 | 202 | ------------- | 112 | +--+--+-----+-----+-----+---------------+-----+ +-----+ | 211 | +-----+-----+-----+-----+---------------+-----+ +->| 310 | 307 | 304 | 301 | ------------- | 214 | +--+--+-----+-----+-----+---------------+-----+ +-----+ | 310 | +-----+-----+-----+-----+---------------+-----+ +->| 409 | 406 | 403 | 400 | | 313 | +--+--+-----+-----+-----+---------------+-----+ | v Risunok 4.18. Spisok nomerov svobodnyh diskovyh blokov s ukazatelyami 80 dyj raz tol'ko po odnomu bloku. Programma mkfs pytaetsya organizovat' pervo- nachal'nyj svyazannyj spisok nomerov svobodnyh blokov tak, chtoby nomera blo- kov, peredavaemyh fajlu, byli ryadom drug s drugom. Blagodarya etomu povyshaet- sya proizvoditel'nost', poskol'ku sokrashchaetsya vremya poiska na diske i vremya ozhidaniya pri posledovatel'nom chtenii fajla processom. Na Risunke 4.18 nomera blokov dany v nastoyashchem formate, opredelyaemom skorost'yu vrashcheniya diska. K sozhaleniyu, ocherednost' nomerov blokov v spiske svobodnyh blokov pereputana v svyazi s chastymi obrashcheniyami k spisku so storony processov, vedushchih zapis' v fajly i udalyayushchih ih, v rezul'tate chego nomera blokov postupayut v spisok i pokidayut ego v sluchajnom poryadke. YAdro ne predprinimaet popytok sortiro- vat' nomera blokov v spiske. Algoritm osvobozhdeniya bloka free - obratnyj algoritmu vydeleniya bloka. Esli spisok v superbloke ne polon, nomer vnov' osvobozhdennogo bloka vklyucha- etsya v etot spisok. Esli, odnako, spisok polon, vnov' osvobozhdennyj blok stanovitsya svyaznym blokom; yadro perepisyvaet v nego spisok iz superbloka i kopiruet blok na disk. Zatem nomer vnov' osvobozhdennogo bloka vklyuchaetsya v spisok svobodnyh blokov v superbloke. |tot nomer stanovitsya edinstvennym no- merom v spiske. Na Risunke 4.20 pokazana posledovatel'nost' operacij alloc i free dlya sluchaya, kogda v ishodnyj moment spisok svobodnyh blokov soderzhal odin ele- ment. YAdro osvobozhdaet blok 949 i vklyuchaet nomer bloka v spisok. Zatem ono vydelyaet etot blok i udalyaet ego nomer iz spiska. Nakonec, ono vydelyaet blok 109 i udalyaet ego nomer iz spiska. Poskol'ku spisok svobodnyh blokov v su- perbloke teper' pust, yadro snova napolnyaet spisok, kopiruya v nego soderzhimoe bloka 109, yavlyayushchegosya sleduyushchej svyaz'yu v spiske s ukazatelyami. Na Risunke +------------------------------------------------------------+ | algoritm alloc /* vydelenie bloka fajlovoj sistemy */ | | vhodnaya informaciya: nomer fajlovoj sistemy | | vyhodnaya informaciya: bufer dlya novogo bloka | | { | | vypolnit' (poka superblok zablokirovan) | | priostanovit'sya (do togo momenta, kogda s superbloka| | budet snyata blokirovka); | | udalit' blok iz spiska svobod