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.
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容m 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座asnyaetsya, 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容m 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容m 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
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容mom 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.
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座asneno, 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容m 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 svobodnyh 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
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.
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
Last-modified: Thu, 12 Feb 1998 07:18:58 GMT