GLAVA 4. VNUTRENNEE PREDSTAVLENIE FAJLOV Kak uzhe bylo zamecheno v glave 2, kazhdyj fajl v sisteme UNIX imeet uni- kal'nyj indeks. Indeks soderzhit informaciyu, neobhodimuyu lyubomu processu dlya togo, chtoby obratit'sya k fajlu, naprimer, prava sobstvennosti na fajl, prava dostupa k fajlu, razmer fajla i raspolozhenie dannyh fajla v fajlovoj siste- me. Processy obrashchayutsya k fajlam, ispol'zuya chetko opredelennyj nabor sistem- nyh vyzovov i identificiruya fajl strokoj simvolov, vystupayushchih v kachestve sostavnogo imeni fajla. Kazhdoe sostavnoe imya odnoznachno opredelyaet fajl, blagodarya chemu yadro sistemy preobrazuet eto imya v indeks fajla. |ta glava posvyashchena opisaniyu vnutrennej struktury fajlov v operacionnoj sisteme UNIX, v sleduyushchej zhe glave rassmatrivayutsya obrashcheniya k operacionnoj sisteme, svyazannye s obrabotkoj fajlov. Razdel 4.1 kasaetsya indeksa i raboty s nim yadra, razdel 4.2 - vnutrennej struktury obychnyh fajlov i nekotoryh mo- mentov, svyazannyh s chteniem i zapis'yu yadrom informacii fajlov. V razdele 4.3 issleduetsya stroenie katalogov - struktur dannyh, pozvolyayushchih yadru organizo- vyvat' fajlovuyu sistemu v vide ierarhii fajlov, razdel 4.4 soderzhit algoritm preobrazovaniya imen pol'zovatel'skih fajlov v indeksy. V razdele 4.5 daetsya struktura superbloka, a v razdelah 4.6 i 4.7 predstavleny algoritmy naznache- niya fajlam diskovyh indeksov i diskovyh blokov. Nakonec, v razdele 4.8 idet rech' o drugih tipah fajlov v sisteme, a imenno o kanalah i fajlah ustrojstv. Algoritmy, opisannye v etoj glave, urovnem vyshe po sravneniyu s algorit- mami upravleniya bufernym keshem, rassmotrennymi v predydushchej glave (Risunok 4.1). Algoritm iget vozvrashchaet poslednij iz identificirovannyh indeksov s vozmozhnost'yu schityvaniya ego s diska, ispol'zuya bufernyj kesh, a algoritm iput osvobozhdaet indeks. Algoritm bmap ustanavlivaet parametry yadra, svyazannye s obrashcheniem k fajlu. Algoritm namei preobrazuet sostavnoe imya pol'zovatel'- skogo fajla v imya indeksa, ispol'zuya algoritmy iget, iput i Algoritmy raboty s fajlovoj sistemoj na nizhnem urovne +--------------------+------------------+-----------------+ | namei | | | +--------------------+ alloc free | ialloc ifree | | iget iput bmap | | | +--------------------+------------------+-----------------+ +---------------------------------------------------------+ | algoritmy raboty s buferami | +---------------------------------------------------------+ | getblk brelse bread breada bwrite | +---------------------------------------------------------+ Risunok 4.1. Algoritmy fajlovoj sistemy bmap. Algoritmy alloc i free vydelyayut i osvobozhdayut diskovye bloki dlya faj- lov, algoritmy ialloc i ifree naznachayut i osvobozhdayut dlya fajlov indeksy. 4.1 INDEKSY 4.1.1 Opredelenie Indeksy sushchestvuyut na diske v staticheskoj forme i yadro schityvaet ih v 59 pamyat' prezhde, chem nachat' s nimi rabotat'. Diskovye indeksy vklyuchayut v sebya sleduyushchie polya: * Identifikator vladel'ca fajla. Prava sobstvennosti razdeleny mezhdu indi- vidual'nym vladel'cem i "gruppovym" i tem samym pomogayut opredelit' krug pol'zovatelej, imeyushchih prava dostupa k fajlu. Superpol'zovatel' imeet pravo dostupa ko vsem fajlam v sisteme. * Tip fajla. Fajl mozhet byt' fajlom obychnogo tipa, katalogom, special'nym fajlom, sootvetstvuyushchim ustrojstvam vvoda-vyvoda simvolami ili blokami, a takzhe abstraktnym fajlom kanala (organizuyushchim obsluzhivanie zaprosov v poryadke postupleniya, "pervym prishel - pervym vyshel"). * Prava dostupa k fajlu. Sistema razgranichivaet prava dostupa k fajlu dlya treh klassov pol'zovatelej: individual'nogo vladel'ca fajla, gruppovogo vladel'ca i prochih pol'zovatelej; kazhdomu klassu vydeleny opredelennye prava na chtenie, zapis' i ispolnenie fajla, kotorye ustanavlivayutsya in- dividual'no. Poskol'ku katalogi kak fajly ne mogut byt' ispolneny, raz- reshenie na ispolnenie v dannom sluchae interpretiruetsya kak pravo proiz- vodit' poisk v kataloge po imeni fajla. * Kalendarnye svedeniya, harakterizuyushchie rabotu s fajlom: vremya vneseniya poslednih izmenenij v fajl, vremya poslednego obrashcheniya k fajlu, vremya vneseniya poslednih izmenenij v indeks. * CHislo ukazatelej na fajl, oznachayushchee kolichestvo imen, ispol'zuemyh pri poiske fajla v ierarhii katalogov. Ukazateli na fajl podrobno rassmatri- vayutsya v glave 5. * Tablica adresov na diske, v kotoryh raspolagaetsya informaciya fajla. Hotya pol'zovateli traktuyut informaciyu v fajle kak logicheskij potok bajtov, yadro raspolagaet eti dannye v nesoprikasayushchihsya diskovyh blokah. Disko- vye bloki, soderzhashchie informaciyu fajla, ukazyvayutsya v indekse. * Razmer fajla. Dannye v fajle adresuyutsya s pomoshch'yu smeshcheniya v bajtah ot- nositel'no nachala fajla, nachinaya so smeshcheniya, ravnogo 0, poetomu razmer fajla v bajtah na 1 bol'she maksimal'nogo smeshcheniya. Naprimer, esli pol'- zovatel' sozdaet fajl i zapisyvaet tol'ko 1 bajt informacii po adresu so smeshcheniem 1000 ot nachala fajla, razmer fajla sostavit 1001 bajt. V in- dekse otsutstvuet sostavnoe imya fajla, neobhodimoe dlya osushchestvleniya dostupa k fajlu. +---------------------------------------+ | vladelec mjb | | gruppa os | | tip - obychnyj fajl | | prava dostupa rwxr-xr-x | | poslednee obrashchenie 23 Okt 1984 13:45 | | poslednee izmenenie 22 Okt 1984 10:30 | | korrekciya indeksa 23 Okt 1984 13:30 | | razmer 6030 bajt | | diskovye adresa | +---------------------------------------+ Risunok 4.2. Primer diskovogo indeksa Na Risunke 4.2 pokazan diskovyj indeks nekotorogo fajla. |tot indeks prinadlezhit obychnomu fajlu, vladelec kotorogo - "mjb" i razmer kotorogo - 6030 bajt. Sistema razreshaet pol'zovatelyu "mjb" proizvodit' chtenie, zapis' i ispolnenie fajla; chlenam gruppy "os" i vsem ostal'nym pol'zovatelyam razresha- etsya tol'ko chitat' ili ispolnyat' fajl, no ne zapisyvat' v nego dannye. Pos- lednij raz fajl byl prochitan 23 oktyabrya 1984 goda v 13:45, zapis' poslednij raz proizvodilas' 22 oktyabrya 1984 goda v 10:30. Indeks izmenyalsya poslednij raz 23 oktyabrya 1984 goda v 13:30, hotya nikakaya informaciya v eto vremya v fajl ne zapisyvalas'. YAdro kodiruet vse vysheperechislennye dannye v indekse. Obra- 60 tite vnimanie na razlichie v zapisi na disk soderzhimogo indeksa i soderzhimogo fajla. Soderzhimoe fajla menyaetsya tol'ko togda, kogda v fajl proizvoditsya za- pis'. Soderzhimoe indeksa menyaetsya kak pri izmenenii soderzhimogo fajla, tak i pri izmenenii vladel'ca fajla, prav dostupa i nabora ukazatelej. Izmenenie soderzhimogo fajla avtomaticheski vyzyvaet korrekciyu indeksa, odnako korrekciya indeksa eshche ne oznachaet izmeneniya soderzhimogo fajla. Kopiya indeksa v pamyati, krome polej diskovogo indeksa, vklyuchaet v sebya i sleduyushchie polya: * Sostoyanie indeksa v pamyati, otrazhayushchee - zablokirovan li indeks, - zhdet li snyatiya blokirovki s indeksa kakoj-libo process, - otlichaetsya li predstavlenie indeksa v pamyati ot svoej diskovoj kopii v rezul'tate izmeneniya soderzhimogo indeksa, - otlichaetsya li predstavlenie indeksa v pamyati ot svoej diskovoj kopii v rezul'tate izmeneniya soderzhimogo fajla, - nahoditsya li fajl v verhnej tochke (sm. razdel 5.15). * Logicheskij nomer ustrojstva fajlovoj sistemy, soderzhashchej fajl. * Nomer indeksa. Tak kak indeksy na diske hranyatsya v linejnom massive (sm. razdel 2.2.1), yadro identificiruet nomer diskovogo indeksa po ego mesto- polozheniyu v massive. V diskovom indekse eto pole ne nuzhno. * Ukazateli na drugie indeksy v pamyati. YAdro svyazyvaet indeksy v hesh-oche- redi i vklyuchaet ih v spisok svobodnyh indeksov podobno tomu, kak svyazy- vaet bufery v bufernye hesh-ocheredi i vklyuchaet ih v spisok svobodnyh bu- ferov. Hesh-ochered' identificiruetsya v sootvetstvii s logicheskim nomerom ustrojstva i nomerom indeksa. YAdro mozhet raspolagat' v pamyati ne bolee odnoj kopii dannogo diskovogo indeksa, no indeksy mogut nahodit'sya od- novremenno kak v hesh-ocheredi, tak i v spiske svobodnyh indeksov. * Schetchik ssylok, oznachayushchij kolichestvo aktivnyh ekzemplyarov fajla (takih, kotorye otkryty). Mnogie polya v kopii indeksa, s kotoroj yadro rabotaet v pamyati, analo- gichny polyam v zagolovke bufera, i upravlenie indeksami pohozhe na upravlenie buferami. Indeks tak zhe blokiruetsya, v rezul'tate chego drugim processam zap- reshchaetsya rabota s nim; eti processy ustanavlivayut v indekse special'nyj flag, vozveshchayushchij o tom, chto vypolnenie obrativshihsya k indeksu processov sleduet vozobnovit', kak tol'ko blokirovka budet snyata. Ustanovkoj drugih flagov yadro otmechaet protivorechiya mezhdu diskovym indeksom i ego kopiej v pa- myati. Kogda yadru nuzhno budet zapisat' izmeneniya v fajl ili indeks, yadro pe- repishet kopiyu indeksa iz pamyati na disk tol'ko posle proverki etih flagov. Naibolee razitel'nym razlichiem mezhdu kopiej indeksa v pamyati i zagolov- kom bufera yavlyaetsya nalichie schetchika ssylok, podschityvayushchego kolichestvo ak- tivnyh ekzemplyarov fajla. Indeks aktiven, kogda process vydelyaet ego, napri- mer, pri otkrytii fajla. Indeks nahoditsya v spiske svobodnyh indeksov, tol'- ko esli znachenie ego schetchika ssylok ravno 0, i eto znachit, chto yadro mozhet perenaznachit' svobodnyj indeks v pamyati drugomu diskovomu indeksu. Takim ob- razom, spisok svobodnyh indeksov vystupaet v roli kesha dlya neaktivnyh indek- sov. Esli process pytaetsya obratit'sya k fajlu, chej indeks v etot moment ot- sutstvuet v indeksnom pule, yadro perenaznachaet svobodnyj indeks iz spiska dlya ispol'zovaniya etim processom. S drugoj storony, u bufera net schetchika ssylok; on nahoditsya v spiske svobodnyh buferov togda i tol'ko togda, kogda on razblokirovan. 4.1.2 Obrashchenie k indeksam YAdro identificiruet indeksy po imeni fajlovoj sistemy i nomeru indeksa i vydelyaet indeksy v pamyati po zaprosam sootvetstvuyushchih algoritmov. Algoritm iget naznachaet indeksu mesto dlya kopii v pamyati (Risunok 4.3); on pochti identichen algoritmu getblk dlya poiska diskovogo bloka v bufernom keshe. YAdro preobrazuet nomera ustrojstva i indeksa v imya hesh-ocheredi i prosmatrivaet etu hesh-ochered' v poiskah indeksa. Esli indeks ne obnaruzhen, yadro vydelyaet 61 +------------------------------------------------------------+ | algoritm iget | | vhodnaya informaciya: nomer indeksa v fajlovoj sisteme | | vyhodnaya informaciya: zablokirovannyj indeks | | { | | vypolnit' | | { | | esli (indeks v indeksnom keshe) | | { | | esli (indeks zablokirovan) | | { | | priostanovit'sya (do osvobozhdeniya indeksa); | | prodolzhit'; /* cikl s usloviem prodolzheniya */ | | } | | /* special'naya obrabotka dlya tochek montirovaniya | | (glava 5) */ | | esli (indeks v spiske svobodnyh indeksov) | | ubrat' iz spiska svobodnyh indeksov; | | uvelichit' schetchik ssylok dlya indeksa; | | vozvratit' (indeks); | | } | | /* indeks otsutstvuet v indeksnom keshe */ | | esli (spisok svobodnyh indeksov pust) | | vozvratit' (oshibku); | | ubrat' novyj indeks iz spiska svobodnyh indeksov; | | sbrosit' nomer indeksa i fajlovoj sistemy; | | ubrat' indeks iz staroj hesh-ocheredi, pomestit' v novuyu;| | schitat' indeks s diska (algoritm bread); | | inicializirovat' indeks (naprimer, ustanoviv schetchik | | ssylok v 1); | | vozvratit' (indeks); | | } | | } | +------------------------------------------------------------+ Risunok 4.3. Algoritm vydeleniya indeksov v pamyati ego iz spiska svobodnyh indeksov i blokiruet ego. Zatem yadro gotovitsya k chteniyu s diska v pamyat' indeksa, k kotoromu ono obrashchaetsya. YAdro uzhe znaet nomera indeksa i logicheskogo ustrojstva i vychislyaet nomer logicheskogo bloka na diske, soderzhashchego indeks, s uchetom togo, skol'ko diskovyh indeksov pome- shchaetsya v odnom diskovom bloke. Vychisleniya proizvodyatsya po formule nomer bloka = ((nomer indeksa - 1) / chislo indeksov v bloke) + + nachal'nyj blok v spiske indeksov gde operaciya deleniya vozvrashchaet celuyu chast' chastnogo. Naprimer, predpolozhim, chto blok 2 yavlyaetsya nachal'nym v spiske indeksov i chto v kazhdom bloke pomeshcha- yutsya 8 indeksov, togda indeks s nomerom 8 nahoditsya v bloke 2, a indeks s nomerom 9 - v bloke 3. Esli zhe v diskovom bloke pomeshchayutsya 16 indeksov, tog- da indeksy s nomerami 8 i 9 raspolagayutsya v diskovom bloke s nomerom 2, a indeks s nomerom 17 yavlyaetsya pervym indeksom v diskovom bloke 3. Esli yadro znaet nomera ustrojstva i diskovogo bloka, ono chitaet blok, ispol'zuya algoritm bread (glava 2), zatem vychislyaet smeshchenie indeksa v baj- tah vnutri bloka po formule: ((nomer indeksa - 1) modul' (chislo indeksov v bloke)) * * razmer diskovogo indeksa 62 Naprimer, esli kazhdyj diskovyj indeks zanimaet 64 bajta i v bloke pomeshchayutsya 8 indeksov, togda indeks s nomerom 8 imeet adres so smeshcheniem 448 bajt ot nachala diskovogo bloka. YAdro ubiraet indeks v pamyati iz spiska svobodnyh in- deksov, pomeshchaet ego v sootvetstvuyushchuyu hesh-ochered' i ustanavlivaet znachenie schetchika ssylok ravnym 1. YAdro perepisyvaet polya tipa fajla i vladel'ca faj- la, ustanovki prav dostupa, chislo ukazatelej na fajl, razmer fajla i tablicu adresov iz diskovogo indeksa v pamyat' i vozvrashchaet zablokirovannyj v pamyati indeks. YAdro manipuliruet s blokirovkoj indeksa i schetchikom ssylok nezavisimo odin ot drugogo. Blokirovka - eto ustanovka, kotoraya dejstvuet na vremya vy- polneniya sistemnogo vyzova i imeet cel'yu zapretit' drugim processam obra- shchat'sya k indeksu poka tot v rabote (i vozmozhno hranit protivorechivye dan- nye). YAdro snimaet blokirovku po okonchanii obrabotki sistemnogo vyzova: blo- kirovka indeksa nikogda ne vyhodit za granicy sistemnogo vyzova. YAdro uveli- chivaet znachenie schetchika ssylok s poyavleniem kazhdoj aktivnoj ssylki na fajl. Naprimer, v razdele 5.1 budet pokazano, kak yadro uvelichivaet znachenie schet- chika ssylok togda, kogda process otkryvaet fajl. Ono umen'shaet znachenie schetchika ssylok tol'ko togda, kogda ssylka stanovitsya neaktivnoj, naprimer, kogda process zakryvaet fajl. Takim obrazom, ustanovka schetchika ssylok soh- ranyaetsya dlya mnozhestva sistemnyh vyzovov. Blokirovka snimaetsya mezhdu dvumya obrashcheniyami k operacionnoj sisteme, chtoby pozvolit' processam odnovremenno proizvodit' razdelennyj dostup k fajlu; ustanovka schetchika ssylok dejstvuet mezhdu obrashcheniyami k operacionnoj sisteme, chtoby predupredit' perenaznachenie yadrom aktivnogo v pamyati indeksa. Takim obrazom, yadro mozhet zablokirovat' i razblokirovat' vydelennyj indeks nezavisimo ot znacheniya schetchika ssylok. Vy- deleniem i osvobozhdeniem indeksov zanimayutsya i otlichnye ot open sistemnye operacii, v chem my i ubedimsya v glave 5. Vozvrashchayas' k algoritmu iget, zametim, chto esli yadro pytaetsya vzyat' in- deks iz spiska svobodnyh indeksov i obnaruzhivaet spisok pustym, ono soobshchaet ob oshibke. V etom otlichie ot ideologii, kotoroj sleduet yadro pri rabote s diskovymi buferami, gde process priostanavlivaet svoe vypolnenie do teh por, poka bufer ne osvoboditsya. Processy kontroliruyut vydelenie indeksov na pol'- zovatel'skom urovne posredstvom zapuska sistemnyh operacij open i close i poetomu yadro ne mozhet garantirovat' moment, kogda indeks stanet dostupnym. Sledovatel'no, process, priostanavlivayushchij svoe vypolnenie v ozhidanii osvo- bozhdeniya indeksa, mozhet nikogda ne vozobnovit'sya. YAdro skoree prervet vypol- nenie sistemnogo vyzova, chem ostavit takoj process v "zavisshem" sostoyanii. Odnako, processy ne imeyut takogo kontrolya nad buferami. Poskol'ku process ne mozhet uderzhat' bufer zablokirovannym v techenie vypolneniya neskol'kih sistem- nyh operacij, yadro zdes' mozhet garantirovat' skoroe osvobozhdenie bufera, i process poetomu priostanavlivaetsya do togo momenta, kogda on stanet dostup- nym. V predshestvuyushchih paragrafah rassmatrivalsya sluchaj, kogda yadro vydelyaet indeks, otsutstvuyushchij v indeksnom keshe. Esli indeks nahoditsya v keshe, pro- cess (A) obnaruzhit ego v hesh-ocheredi i proverit, ne zablokirovan li indeks drugim processom (B). Esli indeks zablokirovan, process A priostanavlivaetsya i vystavlyaet flag u indeksa v pamyati, pokazyvaya, chto on zhdet osvobozhdeniya indeksa. Kogda pozdnee process B razblokiruet indeks, on "razbudit" vse pro- cessy (vklyuchaya process A), ozhidayushchie osvobozhdeniya indeksa. Kogda zhe nakonec process A smozhet ispol'zovat' indeks, on zablokiruet ego, chtoby drugie pro- cessy ne mogli k nemu obratit'sya. Esli pervonachal'no schetchik ssylok imel znachenie, ravnoe 0, indeks takzhe poyavitsya v spiske svobodnyh indeksov, poe- tomu yadro uberet ego ottuda: indeks bol'she ne yavlyaetsya svobodnym. YAdro uve- lichivaet znachenie schetchika ssylok i vozvrashchaet zablokirovannyj indeks. Esli summirovat' vse vysheskazannoe, mozhno otmetit', chto algoritm iget imeet otnoshenie k nachal'noj stadii sistemnyh vyzovov, kogda process vpervye obrashchaetsya k fajlu. |tot algoritm vozvrashchaet zablokirovannuyu indeksnuyu strukturu so znacheniem schetchika ssylok, na 1 bol'shim, chem ono bylo ran'she. Indeks v pamyati soderzhit tekushchuyu informaciyu o sostoyanii fajla. YAdro snimaet 63 blokirovku s indeksa pered vyhodom iz sistemnoj operacii, poetomu drugie sistemnye vyzovy mogut obratit'sya k indeksu, esli pozhelayut. V glave 5 rass- matrivayutsya eti sluchai bolee podrobno. +------------------------------------------------------------+ | algoritm iput /* razreshenie dostupa k indeksu v pamyati */| | vhodnaya informaciya: ukazatel' na indeks v pamyati | | vyhodnaya informaciya: otsutstvuet | | { | | zablokirovat' indeks esli on eshche ne zablokirovan; | | umen'shit' na 1 schetchik ssylok dlya indeksa; | | esli (znachenie schetchika ssylok == 0) | | { | | esli (znachenie schetchika svyazej == 0) | | { | | osvobodit' diskovye bloki dlya fajla (algoritm | | free, razdel 4.7); | | ustanovit' tip fajla ravnym 0; | | osvobodit' indeks (algoritm ifree, razdel 4.6); | | } | | esli (k fajlu obrashchalis' ili izmenilsya indeks ili | | izmenilos' soderzhimoe fajla) | | skorrektirovat' diskovyj indeks; | | pomestit' indeks v spisok svobodnyh indeksov; | | } | | snyat' blokirovku s indeksa; | | } | +------------------------------------------------------------+ Risunok 4.4. Osvobozhdenie indeksa 4.1.3 Osvobozhdenie indeksov V tom sluchae, kogda yadro osvobozhdaet indeks (algoritm iput, Risunok 4.4), ono umen'shaet znachenie schetchika ssylok dlya nego. Esli eto znachenie stanovitsya ravnym 0, yadro perepisyvaet indeks na disk v tom sluchae, kogda kopiya indeksa v pamyati otlichaetsya ot diskovogo indeksa. Oni razlichayutsya, es- li izmenilos' soderzhimoe fajla, esli k fajlu proizvodilos' obrashchenie ili es- li izmenilis' vladelec fajla libo prava dostupa k fajlu. YAdro pomeshchaet in- deks v spisok svobodnyh indeksov, naibolee effektivno raspolagaya indeks v keshe na sluchaj, esli on vskore ponadobitsya vnov'. YAdro mozhet takzhe osvobo- dit' vse svyazannye s fajlom informacionnye bloki i indeks, esli chislo ssylok na fajl ravno 0. 4.2 STRUKTURA FAJLA OBYCHNOGO TIPA Kak uzhe govorilos', indeks vklyuchaet v sebya tablicu adresov raspolozheniya informacii fajla na diske. Tak kak kazhdyj blok na diske adresuetsya po svoemu nomeru, v etoj tablice hranitsya sovokupnost' nomerov diskovyh blokov. Esli by dannye fajla zanimali nepreryvnyj uchastok na diske (to est' fajl zanimal by linejnuyu posledovatel'nost' diskovyh blokov), to dlya obrashcheniya k dannym v fajle bylo by dostatochno hranit' v indekse adres nachal'nogo bloka i razmer fajla. Odnako, takaya strategiya razmeshcheniya dannyh ne pozvolyaet osushchestvlyat' prostoe rasshirenie i szhatie fajlov v fajlovoj sisteme bez riska fragmentacii svobodnogo prostranstva pamyati na diske. Bolee togo, yadru prishlos' by vyde- lyat' i rezervirovat' nepreryvnoe prostranstvo v fajlovoj sisteme pered vy- 64 polneniem operacij, mogushchih privesti k uvelicheniyu razmera fajla. -------------+----------+----------+----------+------------- ---------- | Fajl A | Fajl B | Fajl C | ----------- -------------+----------+----------+----------+------------- 40 50 60 70 Adresa blokov -------------+----------+----------+----------+---------+--- ---------- | Fajl A | Svobodny | Fajl C | Fajl B | -- -------------+----------+----------+----------+---------+--- 40 50 60 70 81 Adresa blokov Risunok 4.5. Razmeshchenie nepreryvnyh fajlov i fragmentaciya svobodnogo prostranstva Predpolozhim, naprimer, chto pol'zovatel' sozdaet tri fajla, A, B i C, kazhdyj iz kotoryh zanimaet 10 diskovyh blokov, a takzhe chto sistema vydelila dlya razmeshcheniya etih treh fajlov nepreryvnoe mesto. Esli potom pol'zovatel' zahochet dobavit' 5 blokov s informaciej k srednemu fajlu, B, yadru pridetsya skopirovat' fajl B v to mesto v fajlovoj sisteme, gde najdetsya okno razmerom 15 blokov. V dopolnenie k zatratam resursov na provedenie etoj operacii dis- kovye bloki, zanimaemye informaciej fajla B, stanut neispol'zuemymi, esli tol'ko oni ne ponadobyatsya fajlam razmerom ne bolee 10 blokov (Risunok 4.5). YAdro moglo by minimizirovat' fragmentaciyu prostranstva pamyati, periodicheski zapuskaya procedury chistki pamyati, uplotnyayushchie imeyushchuyusya pamyat', no eto pot- rebovalo by dopolnitel'nogo rashoda vremennyh i sistemnyh resursov. V celyah povysheniya gibkosti yadro prisoedinyaet k fajlu po odnomu bloku, pozvolyaya informacii fajla byt' razbrosannoj po vsej fajlovoj sisteme. No ta- kaya shema razmeshcheniya uslozhnyaet zadachu poiska dannyh. Tablica adresov soder- zhit spisok nomerov blokov, soderzhashchih prinadlezhashchuyu fajlu informaciyu, odnako prostye vychisleniya pokazyvayut, chto linejnym spiskom blokov fajla v indekse trudno upravlyat'. Esli logicheskij blok zanimaet 1 Kbajt, to fajlu, sostoyashche- mu iz 10 Kbajt, potrebovalsya by indeks na 10 nomerov blokov, a fajlu, sosto- yashchemu iz 100 Kbajt, ponadobilsya by indeks na 100 nomerov blokov. Libo pust' razmer indeksa budet var'irovat'sya v zavisimosti ot razmera fajla, libo prishlos' by ustanovit' otnositel'no zhestkoe ogranichenie na razmer fajla. Dlya togo, chtoby nebol'shaya struktura indeksa pozvolyala rabotat' s bol'shi- mi fajlami, tablica adresov diskovyh blokov privoditsya v sootvetstvie so strukturoj, predstavlennoj na Risunke 4.6. Versiya V sistemy UNIX rabotaet s 13 tochkami vhoda v tablicu adresov indeksa, no principial'nye momenty ne za- visyat ot kolichestva tochek vhoda. Blok, imeyushchij pometku "pryamaya adresaciya" na risunke, soderzhit nomera diskovyh blokov, v kotoryh hranyatsya real'nye dan- nye. Blok, imeyushchij pometku "odinarnaya kosvennaya adresaciya", ukazyvaet na blok, soderzhashchij spisok nomerov blokov pryamoj adresacii. CHtoby obratit'sya k dannym s pomoshch'yu bloka kosvennoj adresacii, yadro dolzhno schitat' etot blok, najti sootvetstvuyushchij vhod v blok pryamoj adresacii i, schitav blok pryamoj ad- resacii, obnaruzhit' dannye. Blok, imeyushchij pometku "dvojnaya kosvennaya adresa- ciya", soderzhit spisok nomerov blokov odinarnoj kosvennoj adresacii, a blok, imeyushchij pometku "trojnaya kosvennaya adresaciya", soderzhit spisok nomerov blo- kov dvojnoj kosvennoj adresacii. V principe, etot metod mozhno bylo by rasprostranit' i na podderzhku blo- kov chetvernoj kosvennoj adresacii, blokov pyaternoj kosvennoj adresacii i tak dalee, no na praktike okazyvaetsya dostatochno imeyushchejsya struktury. Predpolo- zhim, chto razmer logicheskogo bloka v fajlovoj sisteme 1 Kbajt i chto nomer bloka zanimaet 32 bita (4 bajta). Togda v bloke mozhet hranit'sya do 256 nome- rov blokov. Raschety pokazyvayut (Risunok 4.7), chto maksimal'nyj razmer fajla 65 prevyshaet 16 Gbajt, esli ispol'zovat' v indekse 10 blokov pryamoj adresacii i 1 odinarnoj kosvennoj adresacii, 1 dvojnoj kosvennoj adresacii i 1 trojnoj kosvennoj adresacii. Esli zhe uchest', chto dlina polya "razmer fajla" v indekse - 32 bita, to razmer fajla v dejstvitel'nosti ogranichen 4 Gbajtami (2 v ste- peni 32). Processy obrashchayutsya k informacii v fajle, zadavaya smeshchenie v bajtah. Oni rassmatrivayut fajl kak potok bajtov i vedut podschet bajtov, nachinaya s nule- vogo adresa i zakanchivaya adresom, ravnym razmeru fajla. YAdro perehodit ot bajtov k blokam: fajl nachinaetsya s nulevogo logicheskogo bloka i zakanchivaet- sya blokom, nomer kotorogo opredelyaetsya ishodya iz razmera fajla. YAdro obrashcha- etsya k indeksu i prevrashchaet logicheskij blok, prinadlezhashchij fajlu, v sootvet- Informacion- Indeks nye bloki +-------------+ +-----+ | pryamoj adr. +----------------------------------->| | | 0| | | +-------------+ +-----+ | pryamoj adr. +-----------------+ +-----+ | 1| +----------------->| | +-------------+ | | | pryamoj adr. +-----------------+ +-----+ | 2| | +-----+ +-------------+ +----------------->| | | pryamoj adr. +-----------------+ | | | 3| | +-----+ +-------------+ | +-----+ | pryamoj adr. | +----------------->| | | 4| | | +-------------+ +-----+ | pryamoj adr. | - | 5| - +-------------+ - | pryamoj adr. | - | 6| - +-------------+ +-----+ | pryamoj adr. | +----------------->| | | 7| | | | +-------------+ +--------------+ +-----+ | pryamoj adr. | | +-----+ | 8| | +----------------->| | +-------------+ | | | | | pryamoj adr. +--+ +------+ | +-----+ | 9| +------+----+ +-----+ +-------------+ +->+------+ +------>| | | odinarnoj +--+ +------+ | | | |kosvennoj adr| +------+ | +-----+ +-------------+ +->+------+ +->+------+ | +-----+ | dvojnoj +--+ +------+ | +------+ | +->| | |kosvennoj adr| +------+ | +------+ | | | | +-------------+ +------+-+ +------+---+ | +-----+ | trojnoj +--+ +------+ +------+ +---+ |kosvennoj adr| +->+------+ +->+------+ +>+------+-+ +-------------+ +------+ | +------+ | +------+ +------+-+ +------+ | +------+ +------+ +------+-+ +------+ +------+ +------+ +------+ Risunok 4.6. Bloki pryamoj i kosvennoj adresacii v indekse 66 +----------------------------------------------------------+ | 10 blokov pryamoj adresacii po 1 Kbajtu kazhdyj = 10 Kbajt | | 1 blok kosvennoj adresacii s 256 blokami pryamoj | | adresacii = 256 Kbajt | | 1 blok dvojnoj kosvennoj adresacii s 256 blokami | | kosvennoj adresacii = 64 Mbajta| | 1 blok trojnoj kosvennoj adresacii s 256 blokami | | dvojnoj kosvennoj adresacii = 16 Gbajt | +----------------------------------------------------------+ Risunok 4.7. Ob®em fajla v bajtah pri razmere bloka 1 Kbajt +------------------------------------------------------------+ | algoritm bmap /* otobrazhenie adresa smeshcheniya v bajtah ot | | nachala logicheskogo fajla na adres bloka | | v fajlovoj sisteme */ | | vhodnaya informaciya: (1) indeks | | (2) smeshchenie v bajtah | | vyhodnaya informaciya: (1) nomer bloka v fajlovoj sisteme | | (2) smeshchenie v bajtah vnutri bloka | | (3) chislo bajt vvoda-vyvoda v blok | | (4) nomer bloka s prodvizheniem | | { | | vychislit' nomer logicheskogo bloka v fajle ishodya iz | | zadannogo smeshcheniya v bajtah; | | vychislit' nomer nachal'nogo bajta v bloke dlya vvoda- | | vyvoda; /* vyhodnaya informaciya 2 */ | | vychislit' kolichestvo bajt dlya kopirovaniya pol'zova- | | telyu; /* vyhodnaya informaciya 3 */ | | proverit' vozmozhnost' chteniya s prodvizheniem, pometit' | | indeks; /* vyhodnaya informaciya 4 */ | | opredelit' uroven' kosvennosti; | | vypolnit' (poka uroven' kosvennosti drugoj) | | { | | opredelit' ukazatel' v indekse ili blok kosvennoj | | adresacii ishodya iz nomera logicheskogo bloka v | | fajle; | | poluchit' nomer diskovogo bloka iz indeksa ili iz | | bloka kosvennoj adresacii; | | osvobodit' bufer ot dannyh, poluchennyh v rezul'- | | tate vypolneniya predydushchej operacii chteniya s | | diska (algoritm brelse); | | esli (chislo urovnej kosvennosti ischerpano) | | vozvratit' (nomer bloka); | | schitat' diskovyj blok kosvennoj adresacii (algo- | | ritm bread); | | ustanovit' nomer logicheskogo bloka v fajle ishodya | | iz urovnya kosvennosti; | | } | | } | +------------------------------------------------------------+ Risunok 4.8. Preobrazovanie adresa smeshcheniya v nomer bloka v fajlovoj sisteme 67 stvuyushchij diskovyj blok. Na Risunke 4.8 predstavlen algoritm bmap perescheta smeshcheniya v bajtah ot nachala fajla v nomer fizicheskogo bloka na diske. Rassmotrim format fajla v blokah (Risunok 4.9) i predpolozhim, chto disko- vyj blok zanimaet 1024 bajta. Esli processu nuzhno obratit'sya k bajtu, imeyu- shchemu smeshchenie ot nachala fajla, ravnoe 9000, v rezul'tate vychislenij yadro prihodit k vyvodu, chto etot bajt raspolagaetsya v bloke pryamoj adresacii s nomerom 8 (nachinaya s 0). Zatem yadro obrashchaetsya k bloku s nomerom 367; 808-j bajt v etom bloke (esli vesti otschet s 0) i yavlyaetsya 9000-m bajtom v fajle. Esli proces- su nuzhno obratit'sya po adresu, ukazannomu smeshcheniem 350000 bajt ot nachala fajla, on dolzhen schitat' blok dvojnoj kosvennoj adresacii, kotoryj na risun- ke imeet nomer 9156. Tak kak blok kosvennoj adresacii imeet mesto dlya 256 nomerov blokov, pervym bajtom, k kotoromu budet poluchen dostup v rezul'tate obrashche- +-------------+ | 4096 | +-------------+ | 228 | +-------------+ | 45423 | +-------------+ | 0 | +-------------+ | 0 | +-------------+ +----------->+------+ | 11111 | | | | +-------------+ | | | | 0 | | | | +-------------+ | +------+ | 101 | | 367 +-------------+ | informaci- | 367 +----------------------+ onnyj +-------------+ blok | 0 | +->+------+ +-------------+ +---->+------+ | | | +-->+------+ | 428 | | | 331 +--+ | | | | | +-------------+ | 0+------+ 75+------+ | | | | 9156 +--+ | | | 3333 +--+ | | +-------------+ +------+ +------+ +------+ | 824 | 9156 | | 3333 +-------------+ dvojnaya +------+ informaci- adresaciya 331 onnyj odinarnaya blok adresaciya Risunok 4.9. Razmeshchenie blokov v fajle i ego indekse niya k bloku dvojnoj kosvennoj adresacii, budet bajt s nomerom 272384 (256K + 10K); takim obrazom, bajt s nomerom 350000 budet imet' v bloke dvojnoj kos- vennoj adresacii nomer 77616. Poskol'ku kazhdyj blok odinarnoj kosvennoj ad- resacii pozvolyaet obrashchat'sya k 256 Kbajtam, bajt s nomerom 350000 dolzhen raspolagat'sya v nulevom bloke odinarnoj kosvennoj adresacii dlya bloka dvoj- noj kosvennoj adresacii, a imenno v bloke 331. Tak kak v kazhdom bloke pryamoj adresacii dlya bloka odinarnoj kosvennoj adresacii hranitsya 1 Kbajt, bajt s nomerom 77616 nahoditsya v 75-m bloke pryamoj adresacii dlya bloka odinarnoj kosvennoj adresacii, a imenno v bloke 3333. Nakonec, bajt s nomerom v fajle 350000 imeet v bloke 3333 nomer 816. 68 Pri blizhajshem rassmotrenii Risunka 4.9 obnaruzhivaetsya, chto neskol'ko vhodov dlya bloka v indekse imeyut znachenie 0 i eto znachit, chto v dannyh zapi- syah informaciya o logicheskih blokah otsutstvuet. Takoe imeet mesto, esli v sootvetstvuyushchie bloki fajla nikogda ne zapisyvalas' informaciya i po etoj prichine u nomerov blokov ostalis' ih pervonachal'nye nulevye znacheniya. Dlya takih blokov prostranstvo na diske ne vydelyaetsya. Podobnoe raspolozhenie blo- kov v fajle vyzyvaetsya processami, zapuskayushchimi sistemnye operacii lseek i write (sm. sleduyushchuyu glavu). V sleduyushchej glave takzhe ob®yasnyaetsya, kakim ob- razom yadro obrabatyvaet sistemnye vyzovy operacii read, s pomoshch'yu kotoroj proizvoditsya obrashchenie k blokam. Preobrazovanie adresov s bol'shimi smeshcheniyami, v chastnosti s ispol'zova- niem blokov trojnoj kosvennoj adresacii, yavlyaetsya slozhnoj proceduroj, trebu- yushchej ot yadra obrashcheniya uzhe k trem diskovym blokam v dopolnenie k indeksu i informacionnomu bloku. Dazhe esli yadro obnaruzhit bloki v bufernom keshe, ope- raciya ostanetsya dorogostoyashchej, tak kak yadru pridetsya mnogokratno obrashchat'sya k bufernomu keshu i priostanavlivat' svoyu rabotu v ozhidanii snyatiya blokirovki s buferov. Naskol'ko effektiven etot algoritm na praktike ? |to zavisit ot togo, kak ispol'zuetsya sistema, a takzhe ot togo, kto yavlyaetsya pol'zovatelem i kakov sostav zadach, vyzyvayushchij potrebnost' v bolee chastom obrashchenii k bol'shim ili, naoborot, malen'kim fajlam. Odnako, kak uzhe bylo zamecheno [Mullender 84], bol'shinstvo fajlov v sisteme UNIX imeet razmer, ne prevyshayu- shchij 10 Kbajt i dazhe 1 Kbajta ! (*) Poskol'ku 10 Kbajt fajla raspolagayutsya v blokah pryamoj adresacii, k bol'shej chasti dannyh, hranyashchihsya v fajlah, dostup mozhet proizvodit'sya za odno obrashchenie k disku.Poetomu v otlichie ot obrashcheniya k bol'shim fajlam, rabota s fajlami standartnogo razmera protekaet bystro. V dvuh modifikaciyah tol'ko chto opisannoj struktury indeksa predprinima- etsya popytka ispol'zovat' razmernye harakteristiki fajla. Osnovnoj princip v realizacii fajlovoj sistemy BSD 4.2 [McKusick 84] sostoit v tom, chto chem bol'she ob®em dannyh, k kotorym yadro mozhet poluchit' dostup za odno obrashchenie k disku, tem bystree protekaet rabota s fajlom. |to svidetel'stvuet v pol'zu uvelicheniya razmera logicheskogo bloka na diske, poetomu v sisteme BSD razre- shaetsya imet' logicheskie bloki razmerom 4 ili 8 Kbajt. Odnako, uvelichenie razmera blokov na diske privodit k uvelicheniyu fragmentacii blokov, pri koto- roj znachitel'nye uchastki diskovogo prostranstva ostayutsya neispol'zuemymi. Naprimer, esli razmer logicheskogo bloka 8 Kbajt, togda fajl razmerom 12 Kbajt zanimaet 1 polnyj blok i polovinu vtorogo bloka. Drugaya polovina vto- rogo bloka (4 Kbajta) fakticheski teryaetsya; drugie fajly ne mogut ispol'zo- vat' ee dlya hraneniya dannyh. Esli razmery fajlov takovy, chto chislo bajt, po- pavshih v poslednij blok, yavlyaetsya ravnomerno raspredelennoj velichinoj, to srednie poteri diskovogo prostranstva sostavlyayut polbloka na kazhdyj fajl; ob®em teryaemogo diskovogo prostranstva dostigaet v fajlovoj sisteme s logi- cheskimi blokami razmerom 4 Kbajta 45% [McKusick 84]. Vyhod iz etoj situacii v sisteme BSD sostoit v vydelenii tol'ko chasti bloka (fragmenta) dlya razme- shcheniya ostavshejsya informacii fajla. Odin diskovyj blok mozhet vklyuchat' v sebya fragmenty, prinadlezhashchie neskol'kim fajlam. Nekotorye podrobnosti etoj rea- lizacii issleduyutsya na primere uprazhneniya v glave 5. Vtoroj modifikaciej rassmotrennoj klassicheskoj struktury indeksa yavlyaet- sya ideya hraneniya v indekse informacii fajla (sm. [Mullender 84]). Esli uve- lichit' razmer indeksa tak, chtoby indeks zanimal ves' diskovyj blok, nebol'- shaya chast' bloka mozhet byt' ispol'zovana dlya sobstvenno indeksnyh struktur, a ostavshayasya chast' - dlya hraneniya konca fajla i dazhe vo mnogih sluchayah dlya hraneniya fajla celikom. Osnovnoe preimushchestvo takogo podhoda zaklyuchaetsya v tom, chto neobhodimo tol'ko odno obrashchenie k disku dlya schityvaniya indeksa i vsej informacii, esli fajl pomeshchaetsya v indeksnom bloke. --------------------------------------- (*) Na primere 19978 fajlov Mallender i Tannenbaum govoryat, chto priblizi- tel'no 85% fajlov imeyut razmer menee 8 Kbajt i 48% - menee 1 Kbajta. Nesmotrya na to, chto eti dannye var'iruyutsya ot odnoj realizacii sistemy k drugoj, dlya mnogih realizacij sistemy UNIX oni pokazatel'ny. 69