GLAVA 3. BUFER SVERHOPERATIVNOJ PAMYATI (KESH)
Kak uzhe govorilos' v predydushchej glave, yadro operacionnoj sistemy podder-
zhivaet fajly na vneshnih zapominayushchih ustrojstvah bol'shchoj emkosti, takih kak
diski, i pozvolyaet processam sohranyat' novuyu informaciyu ili vyzyvat' ranee
sohranennuyu informaciyu. Esli processu neobhodimo obratit'sya k informacii
fajla, yadro vybiraet informaciyu v operativnuyu pamyat', gde process smozhet
prosmatrivat' etu informaciyu, izmenyat' ee i obrashchat'sya s pros'boj o ee pov-
tornom sohranenii v fajlovoj sisteme. Vspomnim dlya primera programmu copy,
privedennuyu na Risunke 1.3: yadro chitaet dannye iz pervogo fajla v pamyat' i
zatem zapisyvaet eti dannye vo vtoroj fajl. Podobno tomu, kak yadro dolzhno
zanosit' dannye iz fajla v pamyat', ono tak zhe dolzhno schityvat' v pamyat' i
vspomogatel'nye dannye dlya raboty s nimi. Naprimer, superblok fajlovoj sis-
temy soderzhit pomimo vsego prochego informaciyu o svobodnom prostranstve, dos-
tupnom fajlovoj sisteme. YAdro schityvaet superblok v pamyat' dlya togo, chtoby
imet' dostup k ego informacii, i vozvrashchaet ego opyat' fajlovoj sisteme, kog-
da zhelaet sohranit' ego soderzhimoe. Pohozhaya veshch' proishodit s indeksom, ko-
toryj opisyvaet razmeshchenie fajla. YAdro sistemy schityvaet indeks v pamyat',
kogda zhelaet poluchit' dostup k informacii fajla, i vozvrashchaet indeks vnov'
fajlovoj sisteme, kogda zhelaet skorrektirovat' razmeshchenie fajla. YAdro obra-
batyvaet takuyu vspomogatel'nuyu informaciyu, ne buduchi prezhde znakoma s nej i
ne trebuya dlya ee obrabotki zapuska kakih-libo processov.
YAdro moglo by proizvodit' chtenie i zapis' neposredstvenno s diska i na
disk pri vseh obrashcheniyah k fajlovoj sisteme, odnako vremya reakcii sistemy i
proizvoditel'nost' pri etom byli by nizkimi iz-za nizkoj skorosti peredachi
dannyh s diska. Po etoj prichine yadro staraetsya svesti k minimumu chastotu ob-
rashchenij k disku, zavedya special'nuyu oblast' vnutrennih informacionnyh bufe-
rov, imenuemuyu bufernym keshem (*) i hranyashchuyu soderzhimoe blokov diska, k ko-
torym pered etim proizvodilis' obrashcheniya.
Na Risunke 2.1 pokazano, chto modul' bufernogo kesha zanimaet v arhitektu-
re yadra mesto mezhdu podsistemoj upravleniya fajlami i drajverami ustrojstv
(vvoda-vyvoda blokami). Pered chteniem informacii s diska yadro pytaetsya schi-
tat' chto-nibud' iz bufera kesha. Esli v etom bufere otsutstvuet informaciya,
yadro chitaet dannye s diska i zanosit ih v bufer, ispol'zuya algoritm, kotoryj
imeet cel'yu pomestit' v bufere kak mozhno bol'she neobhodimyh dannyh. Analo-
gichno, informaciya, zapisyvaemaya na disk, zanositsya v bufer dlya togo, chtoby
nahodit'sya tam, esli yadro pozdnee popytaetsya schitat' ee. YAdro takzhe staraet-
sya svesti k minimumu chastotu vypolneniya operacij zapisi na disk, vyyasnyaya,
dolzhna li informaciya dejstvitel'no zapominat'sya na diske ili eto promezhutoch-
nye dannye, kotorye budut vskore zaterty. Algoritmy bolee vysokogo urovnya
pozvolyayut proizvodit' predvaritel'noe zanesenie dannyh v bufer kesha ili za-
derzhivat' zapis' dannyh s tem, chtoby usilit' effekt ispol'zovaniya bufera. V
etoj glave rassmatrivayutsya algoritmy, ispol'zuemye yadrom pri rabote s bufe-
rami v sverhoperativnoj pamyati.
-----------------------------------------
(*) Bufernyj kesh predstavlyaet soboj programmnuyu strukturu, kotoruyu ne sledu-
et putat' s apparatnymi keshami, uskoryayushchimi kosvennuyu adresaciyu pamyati.
39
Vo vremya inicializacii sistemy yadro vydelyaet mesto pod sovokupnost' bu-
ferov, potrebnost' v kotoryh opredelyaetsya v zavisimosti ot razmera pamyati i
proizvoditel'nosti sistemy. Kazhdyj bufer sostoit iz dvuh chastej: oblasti pa-
myati, v kotoroj hranitsya informaciya, schityvaemaya s diska, i zagolovka bufe-
ra, kotoryj identificiruet bufer. Poskol'ku sushchestvuet odnoznachnoe sootvets-
tvie mezhdu zagolovkami buferov i massivami dannyh, v nizhesleduyushchem tekste
ispol'zuetsya termin "bufer" v ssylkah kak na tu, tak i na druguyu ego sostav-
lyayushchuyu, i o kakoj iz chastej bufera idet rech' budet ponyatno iz konteksta.
Informaciya v bufere sootvetstvuet informacii v odnom logicheskom bloke
diska v fajlovoj sisteme, i yadro raspoznaet soderzhimoe bufera, prosmatrivaya
identificiruyushchie polya v ego zagolovke. Bufer predstavlyaet soboj kopiyu disko-
vogo bloka v pamyati; soderzhimoe diskovogo bloka otobrazhaetsya v bufer, no eto
otobrazhenie vremennoe, poskol'ku ono imeet mesto do togo momenta, kogda yadro
primet reshenie otobrazit' v bufer drugoj diskovyj blok. Odin diskovyj blok
ne mozhet byt' odnovremenno otobrazhen v neskol'ko buferov. Esli by dva bufera
soderzhali informaciyu dlya odnogo i togo zhe diskovogo bloka, yadro ne smoglo by
opredelit', v kakom iz buferov soderzhitsya tekushchaya informaciya, i, vozmozhno,
vozvratilo by na disk nekorrektnuyu informaciyu. Predpolozhim, naprimer, chto
diskovyj blok otobrazhaetsya v dva bufera, A i B. Esli yadro zapishet dannye
snachala v bufer A, a zatem v bufer B, diskovyj blok budet soderzhat' dannye
iz bufera B, esli v rezul'tate operacij zapisi bufer zapolnitsya do konca.
Odnako, esli yadro izmenit poryadok, v kotorom ono kopiruet soderzhimoe buferov
na disk, na protivopolozhnyj, diskovyj blok budet soderzhat' nekorrektnye dan-
nye.
Zagolovok bufera (Risunok 3.1) soderzhit pole "nomer ustrojstva" i pole
"nomer bloka", kotorye opredelyayut fajlovuyu sistemu i nomer bloka s informa-
ciej na diske i odnoznachno identificiruyut bufer. Nomer ustrojstva - eto lo-
gicheskij nomer fajlovoj sistemy
+------------------+
| nomer ustrojstva |
+------------------+ ukazatel' na
| nomer bloka | oblast' dannyh
+------------------+ +------------->
ukazatel' na | pole sostoyaniya | |
predydushchij bufer +------------------+ |
v hesh-ocheredi | ------+---+
<-------------+ +------------------+
| | ------+----------------->
| +------------------+ ukazatel' na
+---+------ | sleduyushchij bufer
+------------------+ v hesh-ocheredi
| ------+---+
+------------------+ |
<-----------------+------ | |
ukazatel' na +------------------+ +------------->
predydushchij bufer ukazatel' na
v spiske svobodnyh sleduyushchij bufer
v spiske svobodnyh
Risunok 3.1. Zagolovok bufera
(sm. razdel 2.2.1), a ne fizicheskij nomer ustrojstva (diska). Zagolovok bu-
fera takzhe soderzhit ukazatel' na oblast' pamyati dlya bufera, razmer kotoroj
dolzhen byt' ne men'she razmera diskovogo bloka, i pole sostoyaniya, v kotorom
summiruetsya informaciya o tekushchem sostoyanii bufera. Sostoyanie bufera preds-
tavlyaet soboj kombinaciyu iz sleduyushchih uslovij:
* bufer zablokirovan (terminy "zablokirovan (nedostupen)" i "zanyat" ravnoz-
40
nachny, tak zhe, kak i ponyatiya "svoboden" i "dostupen"),
* bufer soderzhit pravil'nuyu informaciyu,
* yadro dolzhno perepisat' soderzhimoe bufera na disk pered tem, kak perenazna-
chit' bufer; eto uslovie izvestno, kak "zaderzhka, vyzvannaya zapis'yu",
* yadro chitaet ili zapisyvaet soderzhimoe bufera na disk,
* process zhdet osvobozhdeniya bufera.
V zagolovke bufera takzhe soderzhatsya dva nabora ukazatelej, ispol'zuemye
algoritmami vydeleniya bufera, kotorye podderzhivayut obshchuyu strukturu oblasti
buferov (bufernogo pula), o chem podrobnee budet govorit'sya v sleduyushchem raz-
dele.
3.2 STRUKTURA OBLASTI BUFEROV (BUFERNOGO PULA)
YAdro pomeshchaet informaciyu v oblast' buferov, ispol'zuya algoritm poiska
buferov, k kotorym naibolee dolgo ne bylo obrashchenij: posle vydeleniya bufera
diskovomu bloku nel'zya ispol'zovat' etot
+----------------------------------------------------------------+
| ukazateli vpered |
| +-------------------+ +-------+ +-------+ +-------+ |
+->| zagolovok spiska |--->| bufer |--->| bufer |--->| bufer |--+
+--| svobodnyh buferov |<---| 1 |<---| 2 |<---| n |<-+
| +-------------------+ +-------+ +-------+ +-------+ |
| ukazateli nazad |
+----------------------------------------------------------------+
do
posle
+----------------------------------------------------------------+
| ukazateli vpered |
| +-------------------+ +-------+ +-------+ |
+->| zagolovok spiska |---------------->| bufer |--->| bufer |--+
+--| svobodnyh buferov |<----------------| 2 |<---| n |<-+
| +-------------------+ +-------+ +-------+ |
| ukazateli nazad |
+----------------------------------------------------------------+
Risunok 3.2. Spisok svobodnyh buferov
bufer dlya drugogo bloka do teh por, poka ne budut zadejstvovany vse ostal'-
nye bufery. YAdro upravlyaet spiskom svobodnyh buferov, kotoryj neobhodim dlya
raboty ukazannogo algoritma. |tot spisok predstavlyaet soboj ciklicheskij pe-
rechen' buferov s dvunapravlennymi ukazatelyami i s formal'nymi zagolovkami v
nachale i v konce perechnya (Risunok 3.2). Vse bufery popadayut v spisok pri
zagruzke sistemy. Esli nuzhen lyuboj svobodnyj bufer, yadro vybiraet bufer iz
"golovy" spiska, no esli v oblasti buferov ishchetsya opredelennyj blok, mozhet
byt' vybran bufer i iz serediny spiska. I v tom, i v drugom sluchae bufer
udalyaetsya iz spiska svobodnyh buferov. Esli yadro vozvrashchaet bufer bufernomu
pulu, etot bufer dobavlyaetsya v hvost spiska, libo v "golovu" spiska (v slu-
chae oshibki), no nikogda ne v seredinu. Po mere udaleniya buferov iz spiska
bufer s nuzhnoj informaciej prodvigaetsya vse blizhe i blizhe k "golove" spiska
(Risunok 3.2). Sledovatel'no, te bufery, kotorye nahodyatsya blizhe k "golove"
spiska, v poslednij raz ispol'zovalis' ran'she, chem bufery, nahodyashchiesya dal'-
she ot "golovy" spiska.
Kogda yadro obrashchaetsya k diskovomu bloku, ono snachala ishchet bufer s soot-
vetstvuyushchej kombinaciej nomerov ustrojstva i bloka. Vmesto togo, chtoby pros-
matrivat' vsyu oblast' buferov, yadro organizuet iz buferov osobye ocheredi,
41
heshirovannye po nomeru ustrojstva i nomeru bloka. V hesh-ocheredi yadro usta-
navlivaet dlya buferov ciklicheskuyu svyaz' v vide spiska s dvunapravlennymi
ukazatelyami, struktura kotorogo pohozha na strukturu spiska svobodnyh bufe-
rov. Kolichestvo buferov v hesh-ocheredi var'iruetsya v techenie vsego vremeni
funkcionirovaniya sistemy, v chem my eshche ubedimsya dal'she. YAdro vynuzhdeno pri-
begat' k funkcii heshirovaniya, chtoby edinoobrazno raspredelyat' bufery mezhdu
hesh-ocheredyami, odnako funkciya heshirovaniya dolzhna byt' neslozhnoj, chtoby ne
postradala proizvoditel'nost' sistemy. Administratory sistemy zadayut koli-
chestvo hesh-ocheredej pri generacii operacionnoj sistemy.
zagolovki hesh-ocheredej
+-----------------+
| | +----+ +----+ +----+
<----| blok 0 modul' 4 |------| 28 |-----| 4 |-----| 64 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| blok 1 modul' 4 |------| 17 |-----| 5 |-----| 97 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| blok 2 modul' 4 |------| 98 |-----| 50 |-----| 10 |---->
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
<----| blok 3 modul' 4 |------| 3 |-----| 35 |-----| 99 |---->
| | +----+ +----+ +----+
+-----------------+
Risunok 3.3. Bufery v hesh-ocheredyah
Na Risunke 3.3 izobrazheny bufery v hesh-ocheredyah: zagolovki hesh-ocheredej
pokazany v levoj chasti risunka, a kvadratikami v kazhdoj stroke pokazany bu-
fery v sootvetstvuyushchej hesh-ocheredi. Tak, kvadratiki s chislami 28, 4 i 64
predstavlyayut bufery v hesh-ocheredi dlya "bloka 0 modulya 4". Punktirnym liniyam
mezhdu buferami sootvetstvuyut ukazateli vpered i nazad vdol' hesh-ocheredi; dlya
prostoty na sleduyushchih risunkah etoj glavy dannye ukazateli ne pokazyvayutsya,
no ih prisutstvie podrazumevaetsya. Krome togo, na risunke bloki identifici-
ruyutsya tol'ko svoimi nomerami i funkciya heshirovaniya postroena na ispol'zova-
nii tol'ko nomerov blokov; odnako na praktike takzhe ispol'zuetsya nomer ust-
rojstva.
Lyuboj bufer vsegda nahoditsya v hesh-ocheredi, no ego polozhenie v ocheredi
ne imeet znacheniya. Kak uzhe govorilos', nikakaya para buferov ne mozhet odnov-
remenno soderzhat' dannye odnogo i togo zhe diskovogo bloka; poetomu kazhdyj
diskovyj blok v bufernom pule sushchestvuet v odnoj i tol'ko odnoj hesh-ocheredi
i predstavlen v nej tol'ko odin raz. Tem ne menee, bufer mozhet nahodit'sya v
spiske svobodnyh buferov, esli ego status "svoboden". Poskol'ku bufer mozhet
byt' odnovremenno v hesh-ocheredi i v spiske svobodnyh buferov, u yadra est'
dva sposoba ego obnaruzheniya. YAdro prosmatrivaet hesh-ochered', esli emu nuzhno
najti opredelennyj bufer, i vybiraet bufer iz spiska svobodnyh buferov, esli
emu nuzhen lyuboj svobodnyj bufer. V sleduyushchem razdele budet pokazano, kakim
obrazom yadro osushchestvlyaet poisk opredelennyh diskovyh blokov v bufernom ke-
she, a takzhe kak ono rabotaet s buferami v hesh-ocheredyah i v spiske svobodnyh
buferov. Eshche raz napomnim: bufer vsegda nahoditsya v hesh -ocheredi, a v spiske
svobodnyh buferov mozhet byt', no mozhet i otsutstvovat'.
42
3.3 MEHANIZM POISKA BUFERA
Kak pokazano na Risunke 2.1, algoritmy verhnego urovnya, ispol'zuemye yad-
rom dlya podsistemy upravleniya fajlami, iniciiruyut vypolnenie algoritmov up-
ravleniya bufernym keshem. Pri vyborke bloka algoritmy verhnego urovnya usta-
navlivayut logicheskij nomer ustrojstva i nomer bloka, k kotorym oni hoteli by
poluchit' dostup. Naprimer, esli process hochet schitat' dannye iz fajla, yadro
ustanavlivaet, v kakoj fajlovoj sisteme nahoditsya fajl i v kakom bloke faj-
lovoj sistemy soderzhatsya dannye, o chem podrobnee my uznaem iz glavy 4. Sobi-
rayas' schitat' dannye iz opredelennogo diskovogo bloka, yadro proveryaet, naho-
ditsya li blok v bufernom pule, i esli net, naznachaet dlya nego svobodnyj bu-
fer. Sobirayas' zapisat' dannye v opredelennyj diskovyj blok, yadro proveryaet,
nahoditsya li blok v bufernom pule, i esli net, naznachaet dlya etogo bloka
svobodnyj bufer. Dlya vydeleniya buferov iz pula v algoritmah chteniya i zapisi
diskovyh blokov ispol'zuetsya operaciya getblk (Risunok 3.4).
Rassmotrim v etom razdele pyat' vozmozhnyh mehanizmov ispol'zovaniya getblk
dlya vydeleniya bufera pod diskovyj blok.
1. YAdro obnaruzhivaet blok v hesh-ocheredi, sootvetstvuyushchij emu bufer svo-
boden.
2. YAdro ne mozhet obnaruzhit' blok v hesh-ocheredi, poetomu ono vydelyaet bu-
fer iz spiska svobodnyh buferov.
3. YAdro ne mozhet obnaruzhit' blok v hesh-ocheredi i, pytayas' vydelit' bufer
iz spiska svobodnyh buferov (kak v sluchae 2), obnaruzhivaet v spiske
bufer, kotoryj pomechen kak "zanyat na vremya zapisi". YAdro dolzhno pere-
pisat' etot bufer na disk i vydelit' drugoj bufer.
4. YAdro ne mozhet obnaruzhit' blok v hesh-ocheredi, a spisok svobodnyh bufe-
rov pust.
5. YAdro obnaruzhivaet blok v hesh-ocheredi, no ego bufer v nastoyashchij moment
zanyat.
Obsudim kazhdyj sluchaj bolee podrobno.
Osushchestvlyaya poisk bloka v bufernom pule po kombinacii nomerov ustrojstva
i bloka, yadro ishchet hesh-ochered', kotoraya by soderzhala etot blok. Prosmatrivaya
hesh-ochered', yadro priderzhivaetsya spiska s ukazatelyami, poka (kak v pervom
sluchae) ne najdet bufer s iskomymi nomerami ustrojstva i bloka. YAdro prove-
ryaet zanyatost' bloka i v tom sluchae, esli on svoboden, pomechaet bufer "zanya-
tym" dlya togo, chtoby drugie processy (**) ne smogli k nemu obratit'sya. Zatem
yadro udalyaet bufer iz spiska svobodnyh buferov, poskol'ku bufer ne mozhet od-
novremenno byt' zanyatym i nahodit'sya v ukazannom spiske. Esli drugie proces-
sy popytayutsya obratit'sya k bloku v to vremya, kogda ego bufer zanyat, oni pri-
ostanovyatsya do teh por, poka bufer ne osvoboditsya. Na Risunke 3.5 pokazan
pervyj sluchaj, kogda yadro ishchet blok 4 v hesh-ocheredi, pomechennoj kak "blok 0
modul' 4". Obnaruzhiv bufer, yadro udalyaet ego iz spiska svobodnyh buferov,
delaya bloki 5 i 28 sosedyami v spiske.
----------------------------------------
(**) Iz predydushchej glavy napomnim, chto vse operacii yadra proizvodyatsya v kon-
tekste processa, vypolnyaemogo v rezhime yadra. Takim obrazom, slova "dru-
gie processy" otnosyatsya k processam, tozhe vypolnyayushchimsya v rezhime yadra.
|ti slova my budem ispol'zovat' i togda, kogda budem govorit' o vzaimo-
dejstvii neskol'kih processov, rabotayushchih v rezhime yadra; i budem govo-
rit' "yadro", kogda vzaimodejstvie mezhdu processami budet otsutstvovat'.
43
+------------------------------------------------------------------+
| algoritm getblk |
| vhodnaya informaciya: nomer fajlovoj sistemy nomer bloka |
| vyhodnaya informaciya: bufer, kotoryj mozhno ispol'zovat' dlya bloka|
| { vypolnit' esli (bufer ne najden) |
| { esli (blok v hesh-ocheredi) |
| { esli (bufer zanyat) /* sluchaj 5 */ |
| { |
| priostanovit'sya (do osvobozhdeniya bufera); |
| prodolzhit'; /* cikl s usloviem prodolzheniya */ |
| } |
| pometit' bufer zanyatym; /* sluchaj 1 */ |
| udalit' bufer iz spiska svobodnyh buferov; |
| vernut' bufer; |
| } |
| v protivnom sluchae /* bloka net v hesh-ocheredi */ |
| { |
| esli (v spiske net svobodnyh buferov) /*sluchaj 4*/ |
| { |
| priostanovit'sya (do osvobozhdeniya lyubogo bufera); |
| prodolzhit'; /* cikl s usloviem prodolzheniya */ |
| } |
| udalit' bufer iz spiska svobodnyh buferov; |
| esli (bufer pomechen dlya otlozhennoj perepisi) |
| /* sluchaj 3 */ |
| { |
| asinhronnaya perepis' soderzhimogo bufera na disk; |
| prodolzhit'; /* cikl s usloviem prodolzheniya */ |
| } |
| /* sluchaj 2 -- poisk svobodnogo bufera */ |
| udalit' bufer iz staroj hesh-ocheredi; |
| vklyuchit' bufer v novuyu hesh-ochered'; |
| vernut' bufer; |
| } |
| } |
| } |
+------------------------------------------------------------------+
Risunok 3.4. Algoritm vydeleniya bufera
zagolovki hesh-ocheredej
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| blok 0 modul' 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
+-----------------+ +----+| +------+ +----+
| | +----+| +----+| +----+
| blok 1 modul' 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| blok 2 modul' 4 |---- | 98 |+---+| 50 | ++ 10 ++
+-----------------+ +----+| +----+ +----+|
| | +----+| +----+ +----+|
| blok 3 modul' 4 |----+>| 3 ++ | 35 | | 99 ||
+-----------------+ | +----+ +----+ +----+|
+-----------------+ | |
|zagolovok spiska +----+ |
|svobodnyh buferov|<---------------------------------+
+-----------------+
(a) Poisk bloka 4 v pervoj hesh-ocheredi
44
zagolovki hesh-ocheredej
+-----------------+ +--------------+
| | +----+| +----+ |+----+
| blok 0 modul' 4 |---- ++ 28 ++ | 4 | || 64 |
| | |+----+ +----+ |+----+
+-----------------+ +-----------------+ |
| | +----+ +----+| |+----+
| blok 1 modul' 4 |---- | 17 | ++ 5 ++ ++ 97 ++
| | +----+ |+----+ +----+|
+-----------------+ | +------+
| | +----+ |+----+ |+----+
| blok 2 modul' 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| blok 3 modul' 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|zagolovok spiska +----+ |
| | |
|svobodnyh buferov|<---------------------------------+
+-----------------+
(b) Udalenie bloka 4 iz spiska svobodnyh buferov
Risunok 3.5. Poisk bufera - sluchaj 1: bufer v hesh-ocheredi
+------------------------------------------------------------+
| algoritm brelse |
| vhodnaya informaciya: zablokirovannyj bufer |
| vyhodnaya informaciya: otsutstvuet |
| { |
| vozobnovit' vypolnenie vseh processov pri nastuplenii |
| sobytiya, svyazannogo s osvobozhdeniem lyubogo bufera; |
| vozobnovit' vypolnenie vseh processov pri nastuplenii |
| sobytiya, svyazannogo s osvobozhdeniem dannogo bufera; |
| podnyat' prioritet preryvaniya processora tak, chtoby |
| blokirovat' lyubye preryvaniya; |
| esli (soderzhimoe bufera verno i bufer ne staryj) |
| postavit' bufer v konec spiska svobodnyh buferov |
| v protivnom sluchae |
| postavit' bufer v nachalo spiska svobodnyh buferov |
| ponizit' prioritet preryvaniya processora s tem, chtoby |
| vnov' razreshit' preryvaniya; |
| razblokirovat' (bufer); |
| } |
+------------------------------------------------------------+
Risunok 3.6. Algoritm vysvobozhdeniya bufera
Pered tem, kak perejti k ostal'nym sluchayam, rassmotrim, chto proizojdet s
buferom posle togo, kak on budet vydelen bloku. YAdro sistemy smozhet chitat'
dannye s diska v bufer i obrabatyvat' ih ili zhe perepisyvat' dannye v bufer
i pri zhelanii na disk. YAdro ostavlyaet u bufera pometku "zanyat"; drugie pro-
45
cessy ne mogut obratit'sya k nemu i izmenit' ego soderzhimoe, poka on zanyat,
takim obrazom podderzhivaetsya celostnost' informacii v bufere. Kogda yadro za-
kanchivaet rabotu s buferom, ono osvobozhdaet bufer v sootvetstvii s algorit-
mom brelse (Risunok 3.6). Vozobnovlyaetsya vypolnenie teh processov, kotorye
byli priostanovleny iz-za togo, chto bufer byl zanyat, a takzhe te processy,
kotorye byli priostanovleny iz-za togo, chto spisok svobodnyh buferov byl
pust. Kak v tom, tak i v drugom sluchae, vysvobozhdenie bufera oznachaet, chto
bufer stanovitsya dostupnym dlya priostanovlennyh processov nesmotrya na to,
chto pervyj process, poluchivshij bufer, zablokiroval ego i zapretil tem samym
poluchenie bufera drugimi processami (sm. razdel 2.2.2.4). YAdro pomeshchaet bu-
fer v konec spiska svobodnyh buferov, esli tol'ko pered etim ne proizoshla
oshibka vvoda-vyvoda ili esli bufer ne pomechen kak "staryj" - moment, kotoryj
budet poyasnen dalee; v ostal'nyh sluchayah bufer pomeshchaetsya v nachalo spiska.
Teper' bufer svoboden dlya ispol'zovaniya lyubym processom.
YAdro vypolnyaet algoritm brelse v sluchae, kogda bufer processu bol'she ne
nuzhen, a takzhe pri obrabotke preryvaniya ot diska dlya vysvobozhdeniya buferov,
ispol'zuemyh pri asinhronnom vvode-vyvode s diska i na disk (sm. razdel
3.4). YAdro povyshaet prioritet preryvaniya raboty processora tak, chtoby zapre-
tit' vozniknovenie lyubyh preryvanij ot diska na vremya raboty so spiskom svo-
bodnyh buferov, preduprezhdaya iskazhenie ukazatelej bufera v rezul'tate vlo-
zhennogo vypolneniya algoritma brelse. Pohozhie posledstviya mogut proizojti,
esli programma obrabotki preryvanij zapustit algoritm brelse vo vremya vypol-
neniya processom algoritma getblk, poetomu yadro povyshaet prioritet preryvaniya
raboty processora i v strategicheskih momentah vypolneniya algoritma getblk.
Bolee podrobno eti sluchai my razberem s pomoshch'yu uprazhnenij.
Pri vypolnenii algoritma getblk imeet mesto sluchaj 2, kogda yadro pros-
matrivaet hesh-ochered', v kotoroj dolzhen byl by nahodit'sya blok, no ne naho-
dit ego tam. Tak kak blok ne mozhet byt' ni v kakoj drugoj hesh-ocheredi, pos-
kol'ku on ne dolzhen "heshirovat'sya" v
zagolovki hesh-ocheredej
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| blok 0 modul' 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| blok 1 modul' 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| blok 2 modul' 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| blok 3 modul' 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | |
+-----------------+ | |
|zagolovok spiska +----+ |
| | |
|svobodnyh buferov|<---------------------------------+
+-----------------+
(a) Poisk bloka 18 - otsutstvuet v keshe
46
zagolovki hesh-ocheredej
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| blok 0 modul' 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| blok 1 modul' 4 |---- | 17 || +->| 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +-|----------+ +------+
| | +----+ | +----+ |+----+ +----+
| blok 2 modul' 4 |---- | 98 | | | 50 | ++ 10 ++ | 18 |
| | +----+ | +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+|
| blok 3 modul' 4 |---- | | 35 | | 99 ||
+-----------------+ | +----+ +----+|
+-----------------+ | |
|zagolovok spiska +--------------+ |
|svobodnyh buferov|<---------------------------------+
+-----------------+
(b) Udalenie pervogo bloka iz spiska svobodnyh buferov, naznachenie bloka 18
Risunok 3.7. Vtoroj sluchaj vydeleniya bufera
drugom meste, sledovatel'no, ego net v bufernom keshe. Poetomu yadro udalyaet
pervyj bufer iz spiska svobodnyh buferov; etot bufer byl uzhe vydelen drugomu
diskovomu bloku i takzhe nahoditsya v hesh-ocheredi. Esli bufer ne pomechen dlya
otlozhennoj perepisi, yadro pomechaet bufer zanyatym, udalyaet ego iz hesh-ochere-
di, gde on nahoditsya, naznachaet v zagolovke bufera nomera ustrojstva i blo-
ka, sootvetstvuyushchie dannomu diskovomu bloku, i pomeshchaet bufer v hesh-ochered'.
YAdro ispol'zuet bufer, ne perepisav informaciyu, kotoruyu bufer prezhde hranil
dlya drugogo diskovogo bloka. Tot process, kotoryj budet iskat' prezhnij dis-
kovyj blok, ne obnaruzhit ego v pule i poluchit dlya nego tochno takim zhe obra-
zom novyj bufer iz spiska svobodnyh buferov. Kogda yadro zakanchivaet rabotu s
buferom, ono osvobozhdaet bufer vysheopisannym sposobom. Na Risunke 3.7, nap-
rimer, yadro ishchet blok 18, no ne nahodit ego v hesh-ocheredi, pomechennoj kak
"blok 2 modul' 4". Poetomu yadro udalyaet pervyj bufer iz spiska svobodnyh bu-
ferov (blok 3), naznachaet ego bloku 18 i pomeshchaet ego v sootvetstvuyushchuyu
hesh-ochered'.
Esli pri vypolnenii algoritma getblk imeet mesto sluchaj 3, yadro tak zhe
dolzhno vydelit' bufer iz spiska svobodnyh buferov. Odnako, ono obnaruzhivaet,
chto udalyaemyj iz spiska bufer byl pomechen dlya otlozhennoj perepisi, poetomu
prezhde chem ispol'zovat' bufer yadro dolzhno perepisat' ego soderzhimoe na disk.
YAdro pristupaet k asinhronnoj zapisi na disk i pytaetsya vydelit' drugoj bu-
fer iz spiska. Kogda asinhronnaya zapis' zakanchivaetsya, yadro osvobozhdaet bu-
fer i pomeshchaet ego v nachalo spiska svobodnyh buferov. Bufer sam prodvinulsya
ot konca spiska svobodnyh buferov k nachalu spiska. Esli posle asinhronnoj
perepisi yadru by ponadobilos' pomestit' bufer v konec spiska, bufer poluchil
by "zelenuyu ulicu" po vsemu spisku svobodnyh buferov, rezul'tat takogo pere-
meshcheniya protivopolozhen dejstviyu algoritma poiska buferov, k kotorym naibolee
dolgo ne bylo obrashchenij. Naprimer, esli obratit'sya k Risunku 3.8, yadro ne
smoglo obnaruzhit' blok 18, no kogda popytalos' vydelit' pervye dva bufera
(po ocheredi) v spiske svobodnyh buferov, to okazalos', chto oni oba pomecheny
dlya otlozhennoj perepisi. YAdro udalilo ih iz spiska, zapustilo operacii pere-
pisi na disk v sootvetstvuyushchie bloki, i vydelilo tretij bufer iz spiska,
blok 4. Dalee yadro prisvoilo novye znacheniya polyam bufera "nomer ustrojstva"
i "nomer bloka" i vklyuchilo bufer, poluchivshij imya "blok 18", v novuyu hesh-oche-
red'.
47
V chetvertom sluchae (Risunok 3.9) yadro, rabotaya s processom A, ne smoglo
najti diskovyj blok v sootvetstvuyushchej hesh-ocheredi i predprinyalo popytku vy-
delit' iz spiska svobodnyh buferov novyj bufer, kak v sluchae 2. Odnako, v
spiske ne okazalos' ni odnogo bufera, poetomu process A priostanovilsya do
teh por, poka drugim processom ne budet vypolnen algoritm brelse, vysvobozh-
dayushchij bufer. Planiruya vypolnenie processa A, yadro vynuzhdeno snova prosmat-
rivat' hesh-ochered' v poiskah bloka. Ono ne v sostoyanii nemedlenno vydelit'
bufer iz spiska svobodnyh buferov, tak kak vozmozhna situaciya, kogda svobod-
nyj bufer ozhidayut srazu neskol'ko processov i odnomu iz nih budet vydelen
vnov' osvobodivshijsya bufer, na kotoryj uzhe nacelilsya process A. Takim obra-
zom, algoritm poiska bloka snova garantiruet, chto tol'ko odin bufer vklyuchaet
soderzhimoe diskovogo bloka. Na Risunke 3.10 pokazana konkurenciya mezhdu dvumya
processami za osvobodivshijsya bufer.
Poslednij sluchaj (Risunok 3.11) naibolee slozhnyj, poskol'ku on svyazan s
kompleksom vzaimootnoshenij mezhdu neskol'kimi processami. Predpolozhim, chto
yadro, rabotaya s processom A, vedet poisk diskovogo bloka i vydelyaet bufer,
no priostanavlivaet vypolnenie processa pered osvobozhdeniem bufera. Napri-
mer, esli process A po-
pytaetsya schitat' diskovyj blok i vydelit' bufer, kak v sluchae 2, to on pri-
ostanovitsya do momenta zaversheniya peredachi dannyh s diska. Predpolozhim, chto
poka process A priostanovlen, yadro aktiviziruet vtoroj process, B, kotoryj
pytaetsya obratit'sya k diskovomu bloku, chej bufer byl tol'ko chto zablokirovan
processom A. Process B (sluchaj 5) obnaruzhit etot zahvachennyj blok v hesh-oche-
redi. Tak kak ispol'zovat' zahvachennyj bufer ne razreshaetsya i, krome togo,
nel'zya vydelit' dlya odnogo i togo zhe diskovogo bloka vtoroj bufer, process B
pomechaet bufer kak "zaproshennyj" i zatem priostanavlivaetsya do togo momenta,
kogda process A osvobodit dannyj bufer.
V konce koncov process A osvobozhdaet bufer i zamechaet, chto on zaproshen.
Togda process A "budit" vse processy, priostanovlennye po sobytiyu "bufer
stanovitsya svobodnym", vklyuchaya i process B. Kogda zhe yadro vnov' zapustit na
vypolnenie process B, process B dolzhen budet ubedit'sya v tom, chto bufer svo-
zagolovki hesh-ocheredej
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| blok 0 modul' 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| blok 1 modul' 4 |---- | 17 || +-+ 5 ++ ++ 97 ++
| | +----+| | +----+ +-++----+|
+-----------------+ +--|otsrochka-+ +------+
| | +----+ | +----+ |+----+
| blok 2 modul' 4 |---- | 98 |+--+ | 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| blok 3 modul' 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ |otsrochka |
+-----------------+ | |
|zagolovok spiska +----+ |
| | |
|svobodnyh buferov|<---------------------------------+
+-----------------+
(a) Pri poiske bloka 18 v spiske svobodnyh buferov obnaruzheny
bloki s otsrochennoj zapis'yu
48
zagolovki hesh-ocheredej
+-----------------+
| | +----+ +----+
| blok 0 modul' 4 |----+>| 28 +------------+ | 64 |
| | | +----+ | +----+
+-----------------+ | |
| | | +----+ +----+ | +----+
| blok 1 modul' 4 |----| | 17 | | 5 | +-->| 97 ++
| | | +----+ +----+ +----+|
+-----------------+ | zapis' +------+
| | | +----+ +----+ |+----+ +----+
| blok 2 modul' 4 |----| | 98 | | 50 | ++ 10 ++ | 18 |
| | | +----+ +----+ +----+| +----+
+-----------------+ | |
| | | +----+ +----+ +----+|
| blok 3 modul' 4 |----| | 3 | | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | zapis' |
+-----------------+ | |
|zagolovok spiska +----+ |
| | |
|svobodnyh buferov|<---------------------------------+
+-----------------+
(b) Perepis' blokov 3 i 5, perenaznachenie bloka 4 na blok 18
Risunok 3.8. Tretij sluchaj vydeleniya bufera
zagolovki hesh-ocheredej
+-----------------+
| | +----+ +----+ +----+
| blok 0 modul' 4 |---- | 28 | | 4 | | 64 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| blok 1 modul' 4 |---- | 17 | | 5 | | 97 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| blok 2 modul' 4 |---- | 98 | | 50 | | 10 |
| | +----+ +----+ +----+
+-----------------+
| | +----+ +----+ +----+
| blok 3 modul' 4 |---- | 3 | | 35 | | 99 |
| | +----+ +----+ +----+
+-----------------+
+-----------------+
|zagolovok spiska +---------+
| | |
|svobodnyh buferov|<--------+
+-----------------+
Poisk bloka 18, spisok svobodnyh buferov pust
Risunok 3.9. CHetvertyj sluchaj vydeleniya bufera
boden. Vozmozhno, chto tretij process, C, zhdal osvobozhdeniya etogo zhe bufera, i
49
yadro zaplanirovalo aktivizaciyu processa C ran'she B; pri etom process C mog
priostanovit'sya i ostavit' bufer zablokirovannym. Sledovatel'no, process B
dolzhen proverit' to, chto blok dejstvitel'no svoboden.
Process B takzhe dolzhen ubedit'sya v tom, chto v bufere soderzhitsya pervona-
chal'no zatrebovannyj diskovyj blok, poskol'ku process C mog vydelit' dannyj
bufer drugomu bloku, kak v sluchae 2. Pri vypolnenii processa B mozhet obnaru-
zhit'sya, chto on zhdal osvobozhdeniya bufera ne s tem soderzhimym, poetomu proces-
su B pridetsya vnov' zanimat'sya poiskami bloka. Esli zhe ego nastroit' na av-
tomaticheskoe vydelenie bufera iz spiska svobodnyh buferov, on mozhet upustit'
iz vidu vozmozhnost' togo, chto kakoj-libo drugoj process uzhe vydelil bufer
dlya dannogo bloka.
Process A Process B
+-------------------------------------------------------------
| Ne mozhet najti blok b -
| v hesh-ocheredi -
| -
| Spisok svobodnyh bufe- -
| rov pust -
| -
| Process priostanovlen -
| - Ne mozhet najti blok b
| - v hesh-ocheredi
| -
| - Spisok svobodnyh bufe-
| - rov pust
| -
| - Process priostanovlen
| - -
| +------------------------------------------------------+
| | Nekotoryj process osvobozhdaet bufer: operaciya brelse |
| +------------------------------------------------------+
| - Vybiraet bufer iz
| - spiska svobodnyh buferov
| -
| - Naznachaet etot bufer
| - bloku b
| -
v
Vremya
Risunok 3.10. Sostyazanie za svobodnyj bufer
V konce koncov, process B najdet etot blok, pri neobhodimosti vybrav no-
vyj bufer iz spiska svobodnyh buferov, kak v sluchae 2. Pust' nekotoryj pro-
cess, osushchestvlyaya poisk bloka 99 (Risunok 3.11), obnaruzhil etot blok v
hesh-ocheredi, odnako on okazalsya zanyatym. Process priostanavlivaetsya do mo-
menta osvobozhdeniya bloka, posle chego on zapuskaet ves' algoritm s samogo na-
chala. Na Risunke 3.12 pokazano soderzhimoe zanyatogo bufera.
Algoritm vydeleniya bufera dolzhen byt' nadezhnym; processy ne dolzhny "za-
sypat'" navsegda i rano ili pozdno im nuzhno vydelit' bufer. YAdro garantiruet
takoe polozhenie, pri kotorom vse processy, ozhidayushchie vydeleniya bufera, pro-
dolzhat svoe vypolnenie, blagodarya tomu, chto yadro raspredelyaet bufery vo vre-
mya obrabotki obrashchenij k operacionnoj sisteme i osvobozhdaet ih pered vozvra-
tom upravleniya processam (***). V rezhime zadachi processy neposreds-
----------------------------------------
(***) Isklyucheniem yavlyaetsya sistemnaya operaciya mount, kotoraya zah-
50
vatyvaet bufer do teh por, poka ne budet ispolnena operaciya
umount. |to isklyuchenie ne yavlyaetsya sushchestvennym, poskol'ku
obshchee kolichestvo buferov namnogo prevyshaet chislo aktivnyh
montirovannyh fajlovyh sistem.
zagolovki hesh-ocheredej
+-----------------+ +-----------------+
| | |+----+ +----+| +----+
| blok 0 modul' 4 |---- ++ 28 ++ ++ 4 ++ | 64 |
| | +----+| |+----+ +----+
+-----------------+ | +------+
| | +----+| +----+| +----+
| blok 1 modul' 4 |---- | 17 || ++ 5 ++ ++ 97 ++
| | +----+| |+----+ +-++----+|
+-----------------+ +---|--------+ +------+
| | +----+ |+----+ |+----+
| blok 2 modul' 4 |---- | 98 |+---+| 50 | ++ 10 ++
| | +----+| +----+ +----+|
+-----------------+ | |
| | +----+| +----+ +----+|
| blok 3 modul' 4 |----+>| 3 ++ | 35 | | 99 ||
| | | +----+ +----+ +----+|
+-----------------+ | zanyat|
+-----------------+ | |
|zagolovok spiska +----+ |
| | |
|svobodnyh buferov|<---------------------------------+
+-----------------+
Poisk bloka 99, blok zanyat
Risunok 3.11. Pyatyj sluchaj vydeleniya bufera
tvenno ne kontroliruyut vydelenie buferov yadrom sistemy, poetomu oni ne mogut
namerenno "zahvatyvat'" bufery. YAdro teryaet kontrol' nad buferom tol'ko tog-
da, kogda zhdet zaversheniya operacii vvoda-vyvoda mezhdu buferom i diskom. Bylo
zadumano tak, chto esli diskovod isporchen, on ne mozhet preryvat' rabotu cent-
ral'nogo processora, i togda yadro nikogda ne osvobodit bufer. Diskovod dol-
zhen sledit' za rabotoj apparatnyh sredstv v takih sluchayah i vozvrashchat' yadru
kod oshibki, soobshchaya o plohoj rabote diska. Koroche govorya, yadro mozhet garan-
tirovat', chto processy, priostanovlennye v ozhidanii bufera, v konce koncov
vozobnovyat svoe vypolnenie.
Mozhno takzhe predstavit' sebe situaciyu, kogda process "zavisaet" v ozhida-
nii polucheniya dostupa k buferu. V chetvertom sluchae, naprimer, esli neskol'ko
processov priostanavlivayutsya, ozhidaya osvobozhdeniya bufera, yadro ne garantiru-
et, chto oni poluchat dostup k buferu v toj ocherednosti, v kotoroj oni zapro-
sili dostup. Process mozhet priostanovit' i vozobnovit' svoe vypolnenie, kog-
da bufer stanet svobodnym, tol'ko dlya togo, chtoby priostanovit'sya vnov' iz
-za togo, chto drugoj process poluchil upravlenie nad buferom pervym. Teoreti-
cheski, tak mozhet prodolzhat'sya vechno, no prakticheski takoj problemy ne vozni-
kaet v svyazi s tem, chto v sisteme obychno zalozheno bol'shoe kolichestvo bufe-
rov.
3.4 CHTENIE I ZAPISX DISKOVYH BLOKOV
Teper', kogda algoritm vydeleniya buferov nami uzhe rassmotren, budet leg-
che ponyat' proceduru chteniya i zapisi diskovyh blokov. CHtoby schitat' diskovyj
51
Process A Process B Process C
+-------------------------------------------------------------
| Bufer vydelen bloku b - -
| - -
| Bufer zablokirovan - -
| - -
| Nachat vvod-vyvod - -
| - -
| Priostanovlen do - -
| zaversheniya vvoda-vyvoda - -
| - - -
| - Poisk bloka b -
| - v hesh-ocheredi -
| - -
| - Bufer zablokirovan, -
| - priostanovka -
| - - -
| - - Priostanovlen
| - - v ozhidanii osvobozhdeniya
| - - lyubogo bufera
| - - (sluchaj 4)
| +---------------------------+ - -
| | Vvod-vyvod zakonchen, | - -
| | vypolnenie vozobnovlyaetsya | - -
| +---------------------------+ - -
| brelse(): vozobnovlyayutsya - -
| drugie processy - -
| - - Poluchaet bufer,
| - - pervonachal'no
| - - naznachennyj
| - - bloku b
| - -
| - - Perenaznachenie
| - - bufera bloku b'
| - Bufer ne soderzhit -
| - blok b -
| - -
| - Poisk nachinaetsya -
| - snova -
| Vremya
v
Risunok 3.12. Sostyazanie za svobodnyj bufer
blok (Risunok 3.13), process ispol'zuet algoritm getblk dlya poiska bloka v
bufernom keshe. Esli on tam, yadro mozhet vozvratit' ego nemedlenno bez fizi-
cheskogo schityvaniya bloka s diska. Esli blok v keshe otsutstvuet, yadro prika-
zyvaet diskovodu "zaplanirovat'" zapros na chtenie i priostanavlivaet rabotu,
ozhidaya zaversheniya vvoda-vyvoda. Diskovod izveshchaet kontroller diska o tom,
chto on sobiraetsya schitat' informaciyu, i kontroller togda peredaet informaciyu
v bufer. Nakonec, diskovyj
kontroller preryvaet rabotu processora, soobshchaya o zavershenii operacii vo-
da-vyvoda, i programma obrabotki preryvanij ot diska vozobnovlyaet vypolnenie
priostanovlennogo processa; teper' soderzhimoe diskovogo bloka nahoditsya v
bufere. Moduli, zaprosivshie informaciyu dannogo bloka, poluchayut ee; kogda bu-
fer im uzhe ne potrebuetsya, oni osvobodyat ego dlya togo, chtoby drugie processy
52
+------------------------------------------------------------+
| algoritm bread /* chtenie bloka */ |
| vhodnaya informaciya: nomer bloka v fajlovoj sisteme |
| vyhodnaya informaciya: bufer, soderzhashchij dannye |
| { |
| poluchit' bufer dlya bloka (algoritm getblk); |
| esli (dannye v bufere pravil'nye) |
| vozvratit' bufer; |
| pristupit' k chteniyu s diska; |
| priostanovit'sya (do zaversheniya operacii chteniya); |
| vozvratit' (bufer); |
| } |
+------------------------------------------------------------+
Risunok 3.13. Algoritm chteniya diskovogo bloka
poluchili k nemu dostup.
V glave 5 budet pokazano, kak moduli bolee vysokogo urovnya (takie kak
podsistema upravleniya fajlami) mogut predchuvstvovat' potrebnost' vo vtorom
diskovom bloke, kogda process chitaet informaciyu iz fajla posledovatel'no.
|ti moduli formiruyut zapros na asinhronnoe vypolnenie vtoroj operacii vvo-
da-vyvoda, nadeyas' na to, chto informaciya uzhe budet v pamyati, kogda vdrug
vozniknet neobhodimost' v nej, i tem samym povyshaya bystrodejstvie sistemy.
Dlya etogo yadro vypolnyaet algoritm chteniya bloka s prodvizheniem breada (Risu-
nok 3.14). YAdro proveryaet, nahoditsya li v keshe pervyj blok, i esli ego tam
net, prikazyvaet diskovodu schitat' etot blok. Esli v bufernom keshe otsutst-
vuet i vtoroj blok, yadro daet komandu diskovodu schitat' asinhronno i ego.
Zatem process priostanavlivaetsya, ozhidaya zaversheniya operacii vvoda-vyvoda
nad pervym blokom. Kogda vypolnenie processa vozobnovlyaetsya, on vozvrashchaet
bufer pervomu bloku i ne obrashchaet vnimanie na to, kogda zavershitsya operaciya
vvoda-vyvoda dlya vtorogo bloka. Posle zaversheniya etoj operacii kontroller
diska preryvaet rabotu sistemy; programma obrabotki preryvanij uznaet o tom,
chto vvod-vyvod vypolnyalsya asinhronno, i osvobozhdaet bufer (algoritm brelse).
Esli by ona ne osvobodila bufer, bufer ostalsya by zablokirovannym i po etoj
prichine nedostupnym dlya vseh processov. Nevozmozhno zaranee razblokirovat'
bufer, tak kak operaciya vvoda-vyvoda, svyazannaya s buferom, aktivna i, sledo-
vatel'no, soderzhimoe bufera eshche ne adekvatno. Pozzhe, esli process pozhelaet
schitat' vtoroj blok, on obnaruzhit ego v bufernom keshe, poskol'ku k tomu vre-
meni operaciya vvoda-vyvoda zakonchitsya. Esli zhe, v nachale vypolneniya algorit-
ma breada, pervyj blok obnaruzhilsya v bufernom keshe, yadro tut zhe proveryaet,
nahoditsya tam zhe i vtoroj blok, i prodolzhaet rabotu po tol'ko chto opisannoj
sheme.
Algoritm zapisi soderzhimogo bufera v diskovyj blok (Risunok 3.15) pohozh
na algoritm chteniya. YAdro informiruet diskovod o tom, chto est' bufer, soder-
zhimoe kotorogo dolzhno byt' vyvedeno, i diskovod planiruet operaciyu vvoda-vy-
voda bloka. Esli zapis' proizvoditsya sinhronno, vyzyvayushchij process priosta-
navlivaetsya, ozhidaya ee
zaversheniya i osvobozhdaya bufer v moment vozobnovleniya svoego vypolneniya. Esli
zapis' proizvoditsya asinhronno, yadro zapuskaet operaciyu zapisi na disk, no
ne zhdet ee zaversheniya. YAdro osvobodit bufer, kogda zavershitsya vvod-vyvod.
Mogut vozniknut' situacii, i eto budet pokazano v sleduyushchih dvuh glavah,
kogda yadro ne zapisyvaet dannye nemedlenno na disk. Esli zapis' "otkladyva-
etsya", yadro sootvetstvuyushchim obrazom pomechaet bufer, osvobozhdaya ego po algo-
ritmu brelse, i prodolzhaet rabotu bez planirovaniya vvoda-vyvoda. YAdro zapi-
syvaet blok na disk pered tem, kak drugoj process smozhet perenaznachit' bufer
drugomu bloku, kak pokazano v algoritme getblk (sluchaj 3). Mezhdu tem, yadro
nadeetsya na to, chto process poluchaet dostup do togo, kak bufer budet perepi-
53
+------------------------------------------------------------+
| algoritm breada /* chtenie bloka s prodvizheniem */ |
| vhodnaya informaciya: (1) v fajlovoj sisteme nomer bloka dlya |
| nemedlennogo schityvaniya |
| (2) v fajlovoj sisteme nomer bloka dlya |
| asinhronnogo schityvaniya |
| vyhodnaya informaciya: bufer s dannymi, schitannymi nemedlenno|
| { |
| esli (pervyj blok otsutstvuet v keshe) |
| { |
| poluchit' bufer dlya pervogo bloka (algoritm getblk);|
| esli (dannye v bufere nevernye) |
| pristupit' k chteniyu s diska; |
| } |
| esli (vtoroj blok otsutstvuet v keshe) |
| { |
| poluchit' bufer dlya vtorogo bloka (algoritm getblk);|
| esli (dannye v bufere vernye) |
| osvobodit' bufer (algoritm brelse); |
| v protivnom sluchae |
| pristupit' k chteniyu s diska; |
| } |
| esli (pervyj blok pervonachal'no nahodilsya v keshe) |
| { |
| schitat' pervyj blok (algoritm bread); |
| vozvratit' bufer; |
| } |
| priostanovit'sya (do togo momenta, kogda pervyj bufer |
| budet soderzhat' vernye dannye); |
| vozvratit' bufer; |
| } |
+------------------------------------------------------------+
Risunok 3.14. Algoritm chteniya bloka s prodvizheniem
san na disk; esli etot process vposledstvii izmenit soderzhimoe bufera, yadro
proizvedet dopolnitel'nuyu operaciyu po sohraneniyu izmenenij na diske.
Otlozhennaya zapis' otlichaetsya ot asinhronnoj zapisi. Vypolnyaya asinhronnuyu
+------------------------------------------------------------+
| algoritm bwrite /* zapis' bloka */ |
| vhodnaya informaciya: bufer |
| vyhodnaya informaciya: otsutstvuet |
| { |
| pristupit' k zapisi na disk; |
| esli (vvod-vyvod sinhronnyj) |
| { |
| priostanovit'sya (do zaversheniya vvoda-vyvoda); |
| osvobodit' bufer (algoritm brelse); |
| } |
| v protivnom sluchae esli (bufer pomechen dlya otlozhennoj |
| zapisi) |
| pometit' bufer dlya posleduyushchego razmeshcheniya v |
| "golove" spiska svobodnyh buferov; |
| } |
+------------------------------------------------------------+
Risunok 3.15. Algoritm zapisi diskovogo bloka
54
zapis', yadro zapuskaet diskovuyu operaciyu nemedlenno, no ne dozhidaetsya ee za-
versheniya. CHto kasaetsya otlozhennoj zapisi, yadro otdalyaet moment fizicheskoj
perepisi na disk naskol'ko vozmozhno; zatem po algoritmu getblk (sluchaj 3)
ono pomechaet bufer
kak "staryj" i zapisyvaet blok na disk asinhronno. Posle etogo kontroller
diska preryvaet rabotu sistemy i osvobozhdaet bufer, ispol'zuya algoritm
brelse; bufer pomeshchaetsya v "golovu" spiska svobodnyh buferov, poskol'ku on
imeet pometku "staryj". Blagodarya nalichiyu dvuh vypolnyayushchihsya asinhronno ope-
racij vvoda-vyvoda - chteniya bloka s prodvizheniem i otlozhennoj zapisi - yadro
mozhet zapuskat' programmu brelse iz programmy obrabotki preryvanij. Sledova-
tel'no, yadro vynuzhdeno prepyatstvovat' vozniknoveniyu preryvanij pri vypolne-
nii lyuboj procedury, rabotayushchej so spiskom svobodnyh buferov, poskol'ku
brelse pomeshchaet bufery v etot spisok.
3.5 PREIMUSHCHESTVA I NEUDOBSTVA BUFERNOGO KESHA
Ispol'zovanie bufernogo kesha imeet, s odnoj storony, neskol'ko preimu-
shchestv i, s drugoj storony, nekotorye neudobstva.
* Ispol'zovanie buferov pozvolyaet vnesti edinoobrazie v proceduru obrashche-
niya k disku, poskol'ku yadru net neobhodimosti znat' prichinu vvoda-vyvo-
da. Vmesto etogo, yadro kopiruet dannye v bufer i iz bufera, nevziraya na
to, yavlyayutsya li dannye chast'yu fajla, indeksa ili superbloka. Buferizaciya
vvoda-vyvoda s diska povyshaet modul'nost' razrabotki programm, poskol'ku
te sostavnye chasti yadra, kotorye zanimayutsya vvodom-vyvodom na disk, ime-
yut odin interfejs na vse sluchai. Koroche govorya, uproshchaetsya proektirova-
nie sistemy.
* Sistema ne nakladyvaet nikakih ogranichenij na vyravnivanie informacii
pol'zovatel'skimi processami, vypolnyayushchimi vvod-vyvod, poskol'ku yadro
proizvodit vnutrennee vyravnivanie informacii. V razlichnyh apparatnyh
realizaciyah chasto trebuetsya vyravnivat' informaciyu dlya vvoda-vyvoda s
diska opredelennym obrazom, t.e. proizvodit' k primeru dvuhbajtnoe ili
chetyrehbajtnoe vyravnivanie dannyh v pamyati. Bez mehanizma buferizacii
programmistam prishlos' by zabotit'sya samim o pravil'nom vyravnivanii
dannyh. Po etoj prichine na mashinah s ogranichennymi vozmozhnostyami v vy-
ravnivanii adresov voznikaet bol'shoe kolichestvo oshibok programmirovaniya
i, krome togo, stanovitsya problemoj perenos programm v operacionnuyu sre-
du UNIX. Kopiruya informaciyu iz pol'zovatel'skih buferov v sistemnye bu-
fery (i obratno), yadro sistemy ustranyaet neobhodimost' v special'nom vy-
ravnivanii pol'zovatel'skih buferov, delaya pol'zovatel'skie programmy
bolee prostymi i mobil'nymi.
* Blagodarya ispol'zovaniyu bufernogo kesha, sokrashchaetsya ob®em diskovogo tra-
fika i vremya reakcii i povyshaetsya obshchaya proizvoditel'nost' sistemy. Pro-
cessy, schityvayushchie dannye iz fajlovoj sistemy, mogut obnaruzhit' informa-
cionnye bloki v keshe i im ne pridetsya pribegat' ko vvodu-vyvodu s diska.
YAdro chasto primenyaet "otlozhennuyu zapis'", chtoby izbezhat' lishnih obrashche-
nij k disku, ostavlyaya blok v bufernom keshe i nadeyas' na popadanie bloka
v kesh. Ochevidno, chto shansy na takoe popadanie vyshe v sistemah s bol'shim
kolichestvom buferov. Tem ne menee, chislo buferov, kotorye mozhno zalozhit'
v sisteme, ogranichivaetsya ob®emom pamyati, dostupnoj vypolnyayushchimsya pro-
cessam: esli pod bufery zadejstvovat' slishkom mnogo pamyati, to sistema
budet rabotat' medlennee v svyazi s tem, chto ej pridetsya zanimat'sya pod-
kachkoj i zameshcheniem vypolnyayushchihsya processov.
* Algoritmy buferizacii pomogayut podderzhivat' celostnost' fajlovoj siste-
my, tak kak oni sohranyayut obshchij, pervonachal'nyj i edinstvennyj obraz
diskovyh blokov, soderzhashchihsya v keshe. Esli dva processa odnovremenno po-
pytayutsya obratit'sya k odnomu i tomu zhe diskovomu bloku, algoritmy bufe-
55
rizacii (naprimer, getblk) parallel'nyj dostup preobrazuyut v posledova-
tel'nyj, predotvrashchaya razrushenie dannyh.
* Sokrashchenie diskovogo trafika yavlyaetsya vazhnym preimushchestvom s tochki zre-
niya obespecheniya horoshej proizvoditel'nosti ili bystroj reakcii sistemy,
odnako strategiya keshirovaniya takzhe imeet nekotorye neudobstva. Tak kak
yadro v sluchae otlozhennoj zapisi ne perepisyvaet dannye na disk nemedlen-
no, takaya sistema uyazvima dlya sboev, kotorye ostavlyayut diskovye dannye v
nekorrektnom vide. Hotya v poslednih versiyah sistemy i sokrashchen ushcherb,
nanosimyj katastroficheskimi sboyami, osnovnaya problema ostaetsya: pol'zo-
vatel', zaprashivayushchij vypolnenie operacii zapisi, nikogda ne znaet, v
kakoj moment dannye zavershat svoj put' na disk (****).
* Ispol'zovanie bufernogo kesha trebuet dopolnitel'nogo kopirovaniya infor-
macii pri ee schityvanii i zapisi pol'zovatel'skimi processami. Process,
zapisyvayushchij dannye, peredaet ih yadru i yadro kopiruet dannye na disk;
process, schityvayushchij dannye, poluchaet ih ot yadra, kotoroe chitaet dannye
s diska. Pri peredache bol'shogo kolichestva dannyh dopolnitel'noe kopiro-
vanie otricatel'nym obrazom otrazhaetsya na proizvoditel'nosti sistemy,
odnako pri peredache nebol'shih ob®emov dannyh proizvoditel'nost' povysha-
etsya, poskol'ku yadro buferizuet dannye (ispol'zuya algoritm getblk i ot-
lozhennuyu zapis') do teh por, poka eto predstavlyaetsya effektivnym s tochki
zreniya ekonomii vremeni raboty s diskom.
V dannoj glave byla rassmotrena struktura bufernogo kesha i razlichnye
sposoby, kotorymi yadro razmeshchaet bloki v keshe. V algoritmah buferizacii so-
chetayutsya neskol'ko prostyh idej, kotorye v summe obespechivayut rabotu meha-
nizma keshirovaniya. Pri rabote s blokami v bufernom keshe yadro ispol'zuet al-
goritm zameny buferov, k kotorym naibolee dolgo ne bylo obrashchenij, predpola-
gaya, chto k
blokam, k kotorym nedavno bylo obrashchenie, veroyatno, vskore obratyatsya snova.
Ocherednost', v kotoroj bufery poyavlyayutsya v spiske svobodnyh buferov, soot-
vetstvuet ocherednosti ih predydushchego ispol'zovaniya. Ostal'nye algoritmy obs-
luzhivaniya buferov, tipa "pervym prishel - pervym vyshel" i zameshcheniya redko is-
pol'zuemyh, libo yavlyayutsya bolee slozhnymi v realizacii, libo snizhayut procent
popadaniya v kesh. Ispol'zovanie funkcii heshirovaniya i hesh-ocheredej daet yadru
vozmozhnost' uskorit' poisk zadannyh blokov, a ispol'zovanie dvunapravlennyh
ukazatelej v spiskah oblegchaet isklyuchenie buferov.
YAdro identificiruet nuzhnyj emu blok po nomeru logicheskogo ustrojstva i
nomeru bloka. Algoritm getblk prosmatrivaet bufernyj kesh v poiskah bloka i,
esli bufer prisutstvuet i svoboden, blokiruet bufer i vozvrashchaet ego. Esli
bufer zablokirovan, obrativshijsya k nemu process priostanavlivaetsya do teh
por, poka bufer ne osvoboditsya. Mehanizm blokirovaniya garantiruet, chto tol'-
ko odin process v kazhdyj moment vremeni rabotaet s buferom. Esli v keshe blok
otsutstvuet, yadro naznachaet bloku svobodnyj bufer, blokiruet i vozvrashchaet
ego. Algoritm bread vydelyaet bloku bufer i pri neobhodimosti chitaet tuda in-
formaciyu. Algoritm bwrite kopiruet informaciyu v predvaritel'no vydelennyj
bufer. Esli pri vypolnenii ukazannyh algoritmov yadro ne uvidit neobhodimosti
v nemedlennom kopirovanii dannyh na disk, ono pometit bufer dlya "otlozhennoj
zapisi", chtoby izbezhat' izlishnego vvoda-vyvoda. K sozhaleniyu, procedura otk-
---------------------------------------
(****) Standartnyj nabor operacij vvoda-vyvoda v programmah na yazyke Si
vklyuchaet operaciyu fflush. |ta funkciya zanimaetsya podkachivaniem dannyh
iz buferov v pol'zovatel'skom adresnom prostranstve v rabochuyu oblast'
yadra. Tem ne menee pol'zovatelyu ne izvestno, kogda yadro zapishet dan-
nye na disk.
56
ladyvaniya zapisi soprovozhdaetsya tem, chto process nikogda ne uveren, v kakoj
moment dannye fizicheski popadayut na disk. Esli yadro zapisyvaet dannye na
disk sinhronno, ono poruchaet drajveru diska peredat' blok fajlovoj sisteme i
zhdet preryvaniya, soobshchayushchego ob okonchanii vvoda-vyvoda.
Sushchestvuet mnozhestvo sposobov ispol'zovaniya yadrom bufernogo kesha. Pos-
redstvom bufernogo kesha yadro obespechivaet obmen dannymi mezhdu prikladnymi
programmami i fajlovoj sistemoj, peredachu dopolnitel'noj sistemnoj informa-
cii, naprimer, indeksov, mezhdu algoritmami yadra i fajlovoj sistemoj. YAdro
takzhe ispol'zuet bufernyj kesh, kogda chitaet programmy v pamyat' dlya vypolne-
niya. V sleduyushchih glavah budet rassmotreno mnozhestvo algoritmov, ispol'zuyushchih
procedury, opisannye v dannoj glave. Drugie algoritmy, kotorye keshiruyut in-
deksy i stranicy pamyati, takzhe ispol'zuyut priemy, pohozhie na te, chto opisany
dlya bufernogo kesha.
1. Rassmotrim funkciyu heshirovaniya primenitel'no k Risunku 3.3. Nailuchshej
funkciej heshirovaniya yavlyaetsya ta, kotoraya edinym obrazom raspredelyaet
bloki mezhdu hesh-ocheredyami. CHto Vy mogli by predlozhit' v kachestve opti-
mal'noj funkcii heshirovaniya ? Dolzhna li eta funkciya v svoih raschetah is-
pol'zovat' logicheskij nomer ustrojstva ?
2. V algoritme getblk, esli yadro udalyaet bufer iz spiska svobodnyh buferov,
ono dolzhno povysit' prioritet preryvaniya raboty processora tak, chtoby
blokirovat' preryvaniya do proverki spiska. Pochemu ?
*3. V algoritme getblk yadro dolzhno povysit' prioritet preryvaniya raboty pro-
cessora tak, chtoby blokirovat' preryvaniya do proverki zanyatosti bloka.
(|to ne pokazano v tekste.) Pochemu ?
4. V algoritme brelse yadro pomeshchaet bufer v "golovu" spiska svobodnyh bufe-
rov, esli soderzhimoe bufera neverno. Esli soderzhimoe bufera neverno, dol-
zhen li bufer poyavit'sya v hesh-ocheredi ?
5. Predpolozhim, chto yadro vypolnyaet otlozhennuyu zapis' bloka. CHto proizojdet,
kogda drugoj process vyberet etot blok iz ego heshocheredi ? Iz spiska svo-
bodnyh buferov ?
*6. Esli neskol'ko processov osparivayut bufer, yadro garantiruet, chto ni odin
iz nih ne priostanovitsya navsegda, no ne garantiruet, chto process ne "za-
visnet" i dozhdetsya polucheniya bufera. Peredelajte algoritm getblk tak,
chtoby processu bylo v konechnom itoge garantirovano poluchenie bufera.
7. Peredelajte algoritmy getblk i brelse tak, chtoby yadro sledovalo ne sheme
zameshcheniya buferov, k kotorym naibolee dolgo ne bylo obrashchenij, a sheme
"pervym prishel - pervym vyshel". Povtorite to zhe samoe so shemoj zameshcheniya
redko ispol'zuemyh buferov.
8. Opishite situaciyu v algoritme bread, kogda informaciya v bufere uzhe verna.
*9. Opishite razlichnye situacii, vstrechayushchiesya v algoritme breada. CHto proi-
zojdet v sluchae sleduyushchego vypolneniya algoritma bread ili breada, kogda
tekushchij blok prochitan s prodvizheniem ? V algoritme breada, esli pervyj
ili vtoroj blok otsutstvuet v keshe, v dal'nejshem pri proverke pravil'nos-
ti soderzhimogo bufera predpolagaetsya, chto blok mog byt' v bufernom pule.
Kak eto mozhet byt' ?
10. Opishite algoritm, zaprashivayushchij i poluchayushchij lyuboj svobodnyj bufer iz
bufernogo pula. Sravnite etot algoritm s getblk.
11. V razlichnyh sistemnyh operaciyah, takih kak umount i sync (glava 5), tre-
buetsya, chtoby yadro perekachivalo na disk soderzhimoe vseh buferov, kotorye
pomecheny dlya "otlozhennoj zapisi" v dannoj fajlovoj sisteme. Opishite al-
goritm, realizuyushchij perekachku buferov. CHto proizojdet s ocherednost'yu
raspolozheniya buferov v spiske svobodnyh buferov v rezul'tate etoj opera-
cii ? Kak yadro mozhet garantirovat', chto ni odin drugoj process ne podbe-
retsya k buferu s pometkoj "otlozhennaya zapis'" i ne smozhet perepisat' ego
soderzhimoe v fajlovuyu sistemu, poka process perekachki priostanovlen v
57
ozhidanii zaversheniya operacii vvoda-vyvoda ?
12. Opredelim vremya reakcii sistemy kak srednee vremya vypolneniya sistemnogo
vyzova. Opredelim propusknuyu sposobnost' sistemy kak kolichestvo proces-
sov, kotorye sistema mozhet vypolnyat' v dannyj period vremeni. Ob®yasnite,
kak bufernyj kesh mozhet sposobstvovat' povysheniyu reakcii sistemy. Sposob-
stvuet li on s neizbezhnost'yu uvelicheniyu propusknoj sposobnosti sistemy ?
58