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 3.1 ZAGOLOVKI BUFERA 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 yad