GLAVA 9. ALGORITMY UPRAVLENIYA PAMYATXYU
Algoritm planirovaniya ispol'zovaniya processornogo vremeni, rassmotrennyj
v predydushchej glave, v sil'noj stepeni zavisit ot vybrannoj strategii uprav-
leniya pamyat'yu. Process mozhet vypolnyat'sya, esli on hotya by chastichno prisutst-
vuet v osnovnoj pamyati; CP ne mozhet ispolnyat' process, polnost'yu vygruzhennyj
vo vneshnyuyu pamyat'. Tem ne menee, osnovnaya pamyat' - chereschur deficitnyj re-
surs, kotoryj zachastuyu ne mozhet vmestit' vse aktivnye processy v sisteme.
Esli, naprimer, v sisteme imeetsya osnovnaya pamyat' ob®emom 8 Mbajt, to devyat'
processov razmerom po 1 Mbajtu kazhdyj uzhe ne smogut v nej odnovremenno pome-
shchat'sya. Kakie processy v takom sluchae sleduet razmeshchat' v pamyati (hotya by
chastichno), a kakie net, reshaet podsistema upravleniya pamyat'yu, ona zhe uprav-
lyaet uchastkami virtual'nogo adresnogo prostranstva processa, ne rezidentnymi
v pamyati. Ona sledit za ob®emom dostupnogo prostranstva osnovnoj pamyati i
imeet pravo periodicheski perepisyvat' processy na ustrojstvo vneshnej pamyati,
imenuemoe ustrojstvom vygruzki, osvobozhdaya v osnovnoj pamyati dopolnitel'noe
mesto. Pozdnee yadro mozhet vnov' pomestit' dannye s ustrojstva vygruzki v os-
novnuyu pamyat'.
V rannih versiyah sistemy UNIX processy perenosilis' mezhdu osnovnoj pa-
myat'yu i ustrojstvom vygruzki celikom i, za isklyucheniem razdelyaemoj oblasti
komand, otdel'nye nezavisimye chasti processa ne mogli byt' ob®ektami pereme-
shcheniya. Takaya strategiya upravleniya pamyat'yu nazyvaetsya svopingom (podkachkoj).
Takuyu strategiyu imelo smysl realizovyvat' na mashine tipa PDP-11, gde maksi-
mal'nyj razmer processa sostavlyal 64 Kbajta. Pri ispol'zovanii etoj strate-
gii razmer processa ogranichivaetsya ob®emom fizicheskoj pamyati, dostupnoj v
sisteme. Sistema BSD (versiya 4.0) yavilas' glavnym poligonom dlya primeneniya
drugoj strategii, strategii "podkachki po obrashcheniyu" (demand paging), v soot-
vetstvii s kotoroj osnovnaya pamyat' obmenivaetsya s vneshnej ne processami, a
stranicami pamyati; eta strategiya podderzhivaetsya i v poslednih redakciyah ver-
sii V sistemy UNIX. Derzhat' v osnovnoj pamyati ves' vypolnyaemyj process net
neobhodimosti, i yadro zagruzhaet v pamyat' tol'ko otdel'nye stranicy po zapro-
su vypolnyayushchegosya processa, ssylayushchegosya na nih. Preimushchestvo strategii pod-
kachki po obrashcheniyu sostoit v tom, chto blagodarya ej otobrazhenie virtual'nogo
adresnogo prostranstva processa na fizicheskuyu pamyat' mashiny stanovitsya bolee
gibkim: dopuskaetsya prevyshenie razmerom processa ob®ema dostupnoj fizicheskoj
pamyati i odnovremennoe razmeshchenie v osnovnoj pamyati bol'shego chisla proces-
sov. Preimushchestvo strategii svopinga sostoit v prostote realizacii i obleg-
chenii "nadstroechnoj" chasti sistemy. Obe strategii upravleniya pamyat'yu rass-
matrivayutsya v nastoyashchej glave.
Opisanie algoritma svopinga mozhno razbit' na tri chasti: upravlenie pros-
transtvom na ustrojstve vygruzki, vygruzka processov iz osnovnoj pamyati i
podkachka processov v osnovnuyu pamyat'.
9.1.1 Upravlenie prostranstvom na ustrojstve vygruzki
Ustrojstvo vygruzki yavlyaetsya ustrojstvom blochnogo tipa, kotoroe preds-
tavlyaet soboj konfiguriruemyj razdel diska. Togda kak obychno yadro vydelyaet
mesto dlya fajlov po odnomu bloku za odnu operaciyu, na ustrojstve vygruzki
253
prostranstvo vydelyaetsya gruppami smezhnyh blokov. Prostranstvo, vydelyaemoe
dlya fajlov, ispol'zuetsya staticheskim obrazom; poskol'ku shema naznacheniya
prostranstva pod fajly dejstvuet v techenie dlitel'nogo perioda vremeni, ee
gibkost' ponimaetsya v smysle sokrashcheniya chisla sluchaev fragmentacii i, sledo-
vatel'no, ob®emov neispol'zuemogo prostranstva v fajlovoj sisteme. Vydelenie
prostranstva na ustrojstve vygruzki, naprotiv, yavlyaetsya vremennym, v sil'noj
stepeni zavisyashchim ot mehanizma dispetcherizacii processov. Process, razmeshchae-
myj na ustrojstve vygruzki, v konechnom itoge vernetsya v osnovnuyu pamyat', os-
vobozhdaya mesto na vneshnem ustrojstve. Poskol'ku vremya yavlyaetsya reshayushchim fak-
torom i s uchetom togo, chto vvod-vyvod dannyh za odnu mul'tiblochnuyu operaciyu
proishodit bystree, chem za neskol'ko odnoblochnyh operacij, yadro vydelyaet na
ustrojstve vygruzki nepreryvnoe prostranstvo, ne berya vo vnimanie vozmozhnuyu
fragmentaciyu.
Tak kak shema vydeleniya prostranstva na ustrojstve vygruzki otlichaetsya
ot shemy, ispol'zuemoj dlya fajlovyh sistem, struktury dannyh, registriruyushchie
svobodnoe prostranstvo, dolzhny takzhe otlichat'sya. Prostranstvo, svobodnoe v
fajlovyh sistemah, opisyvaetsya s pomoshch'yu svyaznogo spiska svobodnyh blokov,
dostup k kotoromu osushchestvlyaetsya cherez superblok fajlovoj sistemy, informa-
ciya o svobodnom prostranstve na ustrojstve vygruzki sobiraetsya v tablicu,
imenuemuyu "karta pamyati ustrojstva". Karty pamyati, pomimo ustrojstva vygruz-
ki, ispol'zuyutsya i drugimi sistemnymi resursami (naprimer, drajverami neko-
toryh ustrojstv), oni dayut vozmozhnost' raspredelyat' pamyat' ustrojstva (v vi-
de smezhnyh blokov) po metodu pervogo podhodyashchego.
Kazhdaya stroka v karte pamyati sostoit iz adresa raspredelyaemogo resursa i
kolichestva dostupnyh edinic resursa; yadro interpretiruet elementy stroki v
sootvetstvii s tipom karty. V samom nachale karta pamyati sostoit iz odnoj
stroki, soderzhashchej adres i obshchee kolichestvo resursov. Esli karta opisyvaet
raspredelenie pamyati na ustrojstve vygruzki, yadro traktuet kazhduyu edinicu
resursa kak gruppu diskovyh blokov, a adres - kak smeshchenie v blokah ot nacha-
la oblasti vygruzki. Pervonachal'nyj vid karty pamyati dlya ustrojstva vygruz-
ki, sostoyashchego iz 10000 blokov s nachal'nym adresom, ravnym 1, pokazan na Ri-
sunke 9.1. Vydelyaya i osvobozhdaya resursy,
yadro korrektiruet kartu pamyati, zabotyas' o tom, chtoby v nej postoyanno soder-
zhalas' tochnaya informaciya o svobodnyh resursah v sisteme.
Na Risunke 9.2 predstavlen algoritm vydeleniya prostranstva s pomoshch'yu
kart pamyati (malloc). YAdro prosmatrivaet kartu v poiskah pervoj stroki, so-
derzhashchej kolichestvo edinic resursa, dostatochnoe dlya udovletvoreniya zaprosa.
Esli zapros pokryvaet vse kolichestvo edinic, soderzhashcheesya v stroke, yadro
udalyaet stroku i uplotnyaet kartu (to est' v karte stanovitsya na odnu stroku
men'she). V protivnom sluchae yadro pereustanavlivaet adres i chislo ostavshihsya
edinic v stroke v sootvetstvii s chislom edinic, vydelennyh po zaprosu. Na
Risunke 9.3 pokazano, kak menyaetsya vid karty pamyati dlya ustrojstva vygruzki
posle vydeleniya 100, 50 i vnov' 100 edinic resursa. V konechnom itoge karta
pamyati prinimaet vid, pokazyvayushchij, chto pervye 250 edinic resursa vydeleny
po zaprosam, i chto teper' ostalis' svobodnymi 9750 edinic, nachinaya s adresa
251.
Adres CHislo edinic resursa
+------------------------------------+
| 1 10000 |
+------------------------------------+
Risunok 9.1. Pervonachal'nyj vid karty pamyati dlya ustrojstva vygruzki
254
+------------------------------------------------------------+
| algoritm malloc /* algoritm vydeleniya prostranstva s is-|
| pol'zovaniem karty pamyati */ |
| vhodnaya informaciya: (1) adres /* ukazyvaet na tip is- |
| pol'zuemoj karty */ |
| (2) trebuemoe chislo edinic resursa |
| vyhodnaya informaciya: adres - v sluchae uspeshnogo zaversheniya |
| 0 - v protivnom sluchae |
| { |
| dlya (kazhdoj stroki karty) |
| { |
| esli (trebuemoe chislo edinic resursa raspolagaetsya v |
| stroke karty) |
| { |
| esli (trebuemoe chislo == chislu edinic v stroke) |
| udalit' stroku iz karty; |
| v protivnom sluchae |
| otregulirovat' startovyj adres v stroke; |
| vernut' (pervonachal'nyj adres stroki); |
| } |
| } |
| vernut' (0); |
| } |
+------------------------------------------------------------+
Risunok 9.2. Algoritm vydeleniya prostranstva s pomoshch'yu kart pamyati
Osvobozhdaya resursy, yadro ishchet dlya nih sootvetstvuyushchee mesto v karte po
adresu. Pri etom vozmozhny tri sluchaya:
Adres CHislo edinic resursa Adres CHislo edinic resursa
+------------------------------+ +------------------------------+
| 1 10000 | | 101 9900 |
+------------------------------+ +------------------------------+
(a) (b)
Adres CHislo edinic resursa Adres CHislo edinic resursa
+------------------------------+ +------------------------------+
| 151 9850 | | 251 9750 |
+------------------------------+ +------------------------------+
(v) (g)
Risunok 9.3. Vydelenie prostranstva na ustrojstve vygruzki
1. Osvobodivshiesya resursy polnost'yu zakryvayut probel v karte pamyati. Drugi-
mi slovami, oni imeyut smezhnye adresa s adresami resursov iz strok, ne-
posredstvenno predshestvuyushchej i sleduyushchej za dannoj. V etom sluchae yadro
ob®edinyaet vnov' osvobodivshiesya resursy s resursami iz ukazannyh strok v
odnu stroku karty pamyati.
2. Osvobodivshiesya resursy chastichno zakryvayut probel v karte pamyati. Esli
oni imeyut adres, smezhnyj s adresom resursov iz stroki, neposredstvenno
predshestvuyushchej ili neposredstvenno sleduyushchej za dannoj (no ne s adresami
iz obeih strok), yadro pereustanavlivaet znachenie adresa i chisla resursov
v sootvetstvuyushchej stroke s uchetom vnov' osvobodivshihsya resursov. CHislo
strok v karte pamyati ostaetsya neizmennym.
3. Osvobodivshiesya resursy chastichno zakryvayut probel v karte pamyati, no ih
255
adresa ne soprikasayutsya s adresami kakih-libo drugih resursov karty. YAd-
ro sozdaet novuyu stroku i vstavlyaet ee v sootvetstvuyushchee mesto v karte.
Vozvrashchayas' k predydushchemu primeru, otmetim, chto esli yadro osvobozhdaet 50
edinic resursa, nachinaya s adresa 101, v karte pamyati poyavitsya novaya stroka,
poskol'ku osvobodivshiesya resursy imeyut adresa, ne soprikasayushchiesya s adresami
sushchestvuyushchih strok karty. Esli zhe zatem yadro osvobodit 100 edinic resursa,
nachinaya s adresa 1, pervaya stroka karty budet rasshirena, poskol'ku osvobo-
divshiesya resursy imeyut adres, smezhnyj s adresom pervoj stroki. |volyuciya sos-
toyanij karty pamyati dlya dannogo sluchaya pokazana na Risunke 9.4.
Predpolozhim, chto yadru byl sdelan zapros na vydelenie 200 edinic (blokov)
prostranstva ustrojstva vygruzki. Poskol'ku pervaya stroka karty soderzhit in-
formaciyu tol'ko o 150 edinicah, yadro privlekaet dlya udovletvoreniya zaprosa
informaciyu iz vtoroj stroki (sm. Risunok 9.5). Nakonec, predpolozhim, chto yad-
ro osvobozhdaet 350
Adres CHislo edinic resursa Adres CHislo edinic resursa
+------------------------------+ +------------------------------+
| 251 9750 | | 101 50 |
+------------------------------+ +------------------------------+
| 251 9750 |
(a) +------------------------------+
(b)
Adres CHislo edinic resursa
+------------------------------+
| 1 150 |
+------------------------------+
| 251 9750 |
+------------------------------+
(v)
Risunok 9.4. Osvobozhdenie prostranstva na ustrojstve vygruzki
Adres CHislo edinic resursa Adres CHislo edinic resursa
+------------------------------+ +------------------------------+
| 1 150 | | 1 150 |
+------------------------------+ +------------------------------+
| 251 9750 | | 451 9550 |
+------------------------------+ +------------------------------+
(a) (b)
Risunok 9.5. Vydelenie prostranstva na ustrojstve vygruzki,
opisannogo vo vtoroj stroke karty pamyati
edinic prostranstva, nachinaya s adresa 151. Nesmotrya na to, chto eti 350 edi-
nic byli vydeleny yadrom v raznoe vremya, ne sushchestvuet prichiny, po kotoroj
yadro ne moglo by osvobodit' ih vse srazu. YAdro uznaet o tom, chto osvobodiv-
shiesya resursy polnost'yu zakryvayut razryv mezhdu pervoj i vtoroj strokami kar-
ty, i vmesto prezhnih dvuh sozdaet odnu stroku, v kotoruyu vklyuchaet i osvobo-
divshiesya resursy.
V tradicionnoj realizacii sistemy UNIX ispol'zuetsya odno ustrojstvo vyg-
ruzki, odnako v poslednih redakciyah versii V dopuskaetsya uzhe nalichie mnozhes-
256
tva ustrojstv vygruzki. YAdro vybiraet ustrojstvo vygruzki po sheme "kol'ce-
vogo spiska" pri uslovii, chto na ustrojstve imeetsya dostatochnyj ob®em nepre-
ryvnogo adresnogo prostranstva. Administratory mogut dinamicheski sozdavat' i
udalyat' iz sistemy ustrojstva vygruzki. Esli ustrojstvo vygruzki udalyaetsya
iz sistemy, yadro ne vygruzhaet dannye na nego; esli zhe dannye podkachivayutsya s
udalyaemogo ustrojstva, snachala ono oporozhnyaetsya i tol'ko posle osvobozhdeniya
prinadlezhashchego ustrojstvu prostranstva ustrojstvo mozhet byt' udaleno iz sis-
temy.
YAdro vygruzhaet process, esli ispytyvaet potrebnost' v svobodnoj pamyati,
kotoraya mozhet vozniknut' v sleduyushchih sluchayah:
1. Proizvedeno obrashchenie k sistemnoj funkcii fork, kotoraya dolzhna vydelit'
mesto v pamyati dlya processa-potomka.
2. Proizvedeno obrashchenie k sistemnoj funkcii brk, uvelichivayushchej razmer pro-
cessa.
3. Razmer processa uvelichilsya v rezul'tate estestvennogo uvelicheniya steka
processa.
4. YAdru nuzhno osvobodit' v pamyati mesto dlya podkachki ranee vygruzhennyh pro-
cessov.
Obrashchenie k sistemnoj funkcii fork vydeleno v osobuyu situaciyu, poskol'ku
eto edinstvennyj sluchaj, kogda prostranstvo pamyati, ranee zanyatoe processom
(roditelem), ne osvobozhdaetsya.
Kogda yadro prinimaet reshenie o tom, chto process budet vygruzhen iz osnov-
noj pamyati, ono umen'shaet znachenie schetchika ssylok, associirovannogo s kazh-
doj oblast'yu processa, i vygruzhaet te oblasti, u kotoryh schetchik ssylok stal
ravnym 0. YAdro vydelyaet mesto na ustrojstve vygruzki i blokiruet process v
pamyati (v sluchayah 1-3), zapreshchaya ego vygruzku (sm. uprazhnenie 9.12) do teh
por, poka ne zakonchitsya tekushchaya operaciya vygruzki. Adres mesta vygruzki ob-
lastej yadro sohranyaet v sootvetstvuyushchih zapisyah tablicy oblastej.
Za odnu operaciyu vvoda-vyvoda, v kotoroj uchastvuyut ustrojstvo vygruzki i
adresnoe prostranstvo zadachi i kotoraya osushchestvlyaetsya cherez bufernyj kesh,
yadro vygruzhaet maksimal'no-vozmozhnoe kolichestvo dannyh. Esli apparatura ne v
sostoyanii peredat' za odnu operaciyu soderzhimoe neskol'kih stranic pamyati,
pered programmami yadra vstaet zadacha osushchestvit' peredachu soderzhimogo pamyati
za neskol'ko shagov po odnoj stranice za kazhduyu operaciyu. Takim obrazom, toch-
naya skorost' i mehanizm peredachi dannyh opredelyayutsya, pomimo vsego prochego,
vozmozhnostyami diskovogo kontrollera i strategiej raspredeleniya pamyati. Nap-
rimer, esli ispol'zuetsya stranichnaya organizaciya pamyati, sushchestvuet veroyat-
nost', chto vygruzhaemye dannye zanimayut nesmezhnye uchastki fizicheskoj pamyati.
YAdro obyazano sobirat' informaciyu ob adresah stranic s vygruzhaemymi dannymi,
kotoruyu vposledstvii ispol'zuet diskovyj drajver, osushchestvlyayushchij upravlenie
processom vvoda-vyvoda. Pered tem, kak vygruzit' sleduyushchuyu porciyu dannyh,
programma podkachki (vygruzki) zhdet zaversheniya predydushchej operacii vvoda-vy-
voda.
Pri etom pered yadrom ne vstaet zadacha perepisat' na ustrojstvo vygruzki
soderzhimoe virtual'nogo adresnogo prostranstva processa polnost'yu. Vmesto
etogo yadro kopiruet na ustrojstvo vygruzki soderzhimoe fizicheskoj pamyati, ot-
vedennoj processu, ignoriruya neispol'zuemye virtual'nye adresa. Kogda yadro
podkachivaet process obratno v pamyat', ono imeet u sebya kartu virtual'nyh ad-
resov processa i mozhet perenaznachit' processu novye adresa. YAdro schityvaet
kopiyu processa iz bufernogo kesha v fizicheskuyu pamyat', v te yachejki, dlya koto-
ryh ustanovleno sootvetstvie s virtual'nymi adresami processa.
Na Risunke 9.6 priveden primer otobrazheniya obraza processa v pamyati na
adresnoe prostranstvo ustrojstva vygruzki (*). Process raspolagaet tremya ob-
lastyami: komand, dannyh i steka. Oblast' komand zakanchivaetsya na virtual'nom
257
---------------------------------------
(*) Dlya prostoty virtual'noe adresnoe prostranstvo processa na etom i na
vseh posleduyushchih risunkah izobrazhaetsya v vide linejnogo massiva tochek
vhoda v tablicu stranic, ne prinimaya vo vnimanie tot fakt, chto kazhdaya
oblast' obychno imeet svoyu otdel'nuyu tablicu stranic.
Raspolozhenie virtual'nyh adresov Ustrojstvo vygruzki
Virtual'nye, fizicheskie adresa
+----------------------+ +-----------------+
Oblast' | 0 278K ----+-------684--+---> |
komand +----------------------+ +-----------------+
| 1K 432K ----+------------+---> |
+----------------------+ +-----------------+
| pusto | +--------+---> |
+----------------------+ - +-----------------+
| - | -+-------+---> |
| - | -- +-----------------+
| - | --+------+---> |
+----------------------+ --- +-----------------+
Oblast' | 64K 573K ----+---+-- +----+---> |
dannyh +----------------------+ -- - +-----------------+
| 65K 647K ----+----+- 690 | |
+----------------------+ - - +-----------------+
| 66K 595K ----+-----+ -
+----------------------+ -
| pusto | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Oblast' |128K 401K ----+-------+
steka +----------------------+
| pusto |
+----------------------+
Risunok 9.6. Otobrazhenie prostranstva processa na ustrojstvo vygruzki
adrese 2K, a oblast' dannyh nachinaetsya s adresa 64K, takim obrazom v virtu-
al'nom adresnom prostranstve obrazovalsya propusk v 62 Kbajta. Kogda yadro
vygruzhaet process, ono vygruzhaet soderzhimoe stranic pamyati s adresami 0, 1K,
64K, 65K, 66K i 128K; na ustrojstve vygruzki ne budet otvedeno mesto pod
propusk v 62 Kbajta mezhdu oblastyami komand i dannyh, kak i pod propusk v 61
Kbajt mezhdu oblastyami dannyh i steka, ibo prostranstvo na ustrojstve vygruz-
ki zapolnyaetsya nepreryvno. Kogda yadro zagruzhaet process obratno v pamyat',
ono uzhe znaet iz karty pamyati processa o tom, chto process imeet v svoem
prostranstve neispol'zuemyj uchastok razmerom 62K, i s uchetom etogo sootvets-
tvenno vydelyaet fizicheskuyu pamyat'. |tot sluchaj proillyustrirovan s pomoshch'yu
Risunka 9.7. Sravnenie Risunkov 9.6 i 9.7 pokazyvaet, chto fizicheskie adresa,
zanimaemye processom do i posle vygruzki, ne
sovpadayut mezhdu soboj; odnako, na pol'zovatel'skom urovne process ne obrashcha-
et na eto nikakogo vnimaniya, poskol'ku soderzhimoe ego virtual'nogo prostran-
stva ostalos' tem zhe samym.
Teoreticheski vse prostranstvo pamyati, zanyatoe processom, v tom chisle ego
lichnoe adresnoe prostranstvo i stek yadra, mozhet byt' vygruzheno, hotya yadro i
mozhet vremenno zablokirovat' oblast' v pamyati na vremya vypolneniya kritiches-
koj operacii. Odnako prakticheski, yadro ne vygruzhaet soderzhimoe adresnogo
258
Raspolozhenie virtual'nyh adresov Ustrojstvo vygruzki
Virtual'nye, fizicheskie adresa
+----------------------+ +-----------------+
Oblast' | 0 401K <---+-------684--+---- |
komand +----------------------+ +-----------------+
| 1K 370K <---+------------+---- |
+----------------------+ +-----------------+
| pusto | +--------+---- |
+----------------------+ - +-----------------+
| - | -+-------+---- |
| - | -- +-----------------+
| - | --+------+---- |
+----------------------+ --- +-----------------+
Oblast' | 64K 788K <---+---+-- +----+---- |
dannyh +----------------------+ -- - +-----------------+
| 65K 492K <---+----+- 690 | |
+----------------------+ - - +-----------------+
| 66K 647K <---+-----+ -
+----------------------+ -
| pusto | -
+----------------------+ -
| - | -
| - | -
+----------------------+ -
Oblast' |128K 955K <---+-------+
steka +----------------------+
| pusto |
+----------------------+
Risunok 9.7. Zagruzka processa v pamyat'
prostranstva processa, esli v nem nahodyatsya tablicy preobrazovaniya adresov
(adresnye tablicy) processa. Prakticheskimi soobrazheniyami tak zhe diktuyutsya
usloviya, pri kotoryh process mozhet vygruzit' samogo sebya ili potrebovat'
svoej vygruzki drugim processom (sm. uprazhnenie 9.4).
9.1.2.1 Vygruzka pri vypolnenii sistemnoj funkcii fork
V opisanii sistemnoj funkcii fork (razdel 7.1) predpolagalos', chto pro-
cess-roditel' poluchil v svoe rasporyazhenie pamyat', dostatochnuyu dlya sozdaniya
konteksta potomka. Esli eto uslovie ne vypolnyaetsya, yadro vygruzhaet process
iz pamyati, ne osvobozhdaya prostranstvo pamyati, zanimaemoe ego (roditelya) ko-
piej. Kogda procedura vygruzki zavershitsya, process-potomok budet raspola-
gat'sya na ustrojstve vygruzki; process-roditel' perevodit svoego potomka v
sostoyanie "gotovnosti k vypolneniyu" (sm. Risunok 6.1) i vozvrashchaetsya v rezhim
zadachi. Poskol'ku process-potomok nahoditsya v sostoyanii "gotovnosti k vypol-
neniyu", programma podkachki v konce koncov zagruzit ego v pamyat', gde yadro
zapustit ego na vypolnenie; potomok zavershit tem samym svoyu rol' v vypolne-
nii sistemnoj funkcii fork i vernetsya v rezhim zadachi.
9.1.2.2 Vygruzka s rasshireniem
Esli process ispytyvaet potrebnost' v dopolnitel'noj fizicheskoj pamyati,
libo v rezul'tate rasshireniya steka, libo v rezul'tate zapuska funkcii brk, i
esli eta potrebnost' prevyshaet dostupnye rezervy pamyati, yadro vypolnyaet ope-
raciyu vygruzki processa s rasshireniem ego razmera na ustrojstve vygruzki. Na
ustrojstve vygruzki yadro rezerviruet mesto dlya razmeshcheniya processa s uchetom
259
Pervonachal'noe Rasshirennyj
raspolozhenie format
Virtual'nye, Virtual'nye, Ustrojstvo
fizicheskie adresa fizicheskie adresa vygruzki
+------------+ +------------+ +---------+
Oblast'| 0 278K | | 0 278K -+-----684--+---> |
komand +------------+ +------------+ +---------+
| 1K 432K | | 1K 432K -+----------+---> |
+------------+ +------------+ +---------+
| pusto | | pusto | +--------+---> |
+------------+ +------------+ - +---------+
| - | | - | -+-------+---> |
| - | | - | -- +---------+
| - | | - | --+------+---> |
+------------+ +------------+ --- +---------+
Oblast'| 64K 573K | | 64K 573K -+-+-- +----+---> |
dannyh +------------+ +------------+ -- - +---------+
| 65K 647K | | 65K 647K -+--+- 690 | |
+------------+ +------------+ - - +---------+
| 66K 595K | | 66K 595K -+---+ 691 +|---> |
+------------+ +------------+ - -+---------+
| pusto | | pusto | - -
+------------+ +------------+ - -
| - | | - | - -
| - | | - | - -
+------------+ +------------+ - -
Oblast'|128K 401K | |128K 401K -+-----+ -
steka +------------+ +------------+ -
| pusto | Novaya |129K ... -+---------+
+------------+ stranica+------------+
| pusto |
+------------+
Risunok 9.8. Perenastrojka karty pamyati v sluchae vygruzki s rasshireniem
rasshireniya ego razmera. Zatem proizvoditsya perenastrojka tablicy preobrazo-
vaniya adresov processa s uchetom dopolnitel'nogo virtual'nogo prostranstva,
no bez vydeleniya fizicheskoj pamyati (v svyazi s ee otsutstviem). Nakonec, yadro
vygruzhaet process, vypolnyaya proceduru vygruzki obychnym poryadkom i obnulyaya
vnov' vydelennoe prostranstvo na ustrojstve (sm. Risunok 9.8). Kogda nes-
kol'ko pozzhe yadro budet zagruzhat' process obratno v pamyat', fizicheskoe pros-
transtvo budet vydeleno uzhe s uchetom novogo sostoyaniya tablicy preobrazovaniya
adresov. V moment vozobnovleniya u processa uzhe budet v rasporyazhenii pamyat'
dostatochnogo ob®ema.
9.1.3 Zagruzka (podkachka) processov
Nulevoj process (process podkachki) yavlyaetsya edinstvennym processom, zag-
ruzhayushchim drugie processy v pamyat' s ustrojstv vygruzki. Process podkachki na-
chinaet rabotu po vypolneniyu etoj svoej edinstvennoj funkcii po okonchanii
inicializacii sistemy (kak uzhe govorilos' v razdele 7.9). On zagruzhaet pro-
cessy v pamyat' i, esli emu ne hvataet mesta v pamyati, vygruzhaet ottuda neko-
torye iz processov, nahodyashchihsya tam. Esli u processa podkachki net raboty
(naprimer, otsutstvuyut processy, ozhidayushchie zagruzki v pamyat') ili zhe on ne v
sostoyanii vypolnit' svoyu rabotu (ni odin iz processov ne mozhet byt' vygru-
zhen), process podkachki priostanavlivaetsya; yadro periodicheski vozobnovlyaet
260
ego vypolnenie. YAdro planiruet zapusk processa podkachki tochno tak zhe, kak
delaet eto v otnoshenii drugih processov, orientiruyas' na bolee vysokij prio-
ritet, pri etom process podkachki vypolnyaetsya tol'ko v rezhime yadra. Process
podkachki ne obrashchaetsya k funkciyam operacionnoj sistemy, a ispol'zuet v svoej
rabote tol'ko vnutrennie funkcii yadra; on yavlyaetsya arhetipom vseh processov
yadra.
Kak uzhe vkratce govorilos' v glave 8, programma obrabotki preryvanij po
tajmeru izmeryaet vremya nahozhdeniya kazhdogo processa v pamyati ili v sostoyanii
vygruzki. Kogda process podkachki vozobnovlyaet svoyu rabotu po zagruzke pro-
cessov v pamyat', on prosmatrivaet vse processy, nahodyashchiesya v sostoyanii "go-
tovnosti k vypolneniyu, buduchi vygruzhennymi", i vybiraet iz nih odin, kotoryj
nahoditsya v etom sostoyanii dol'she ostal'nyh (sm. Risunok 9.9). Esli imeetsya
dostatochno svobodnoj pamyati, process podkachki zagruzhaet vybrannyj process,
vypolnyaya operacii v posledovatel'nosti, obratnoj vygruzke processa. Snachala
vydelyaetsya fizicheskaya pamyat', zatem s ustrojstva vygruzki schityvaetsya nuzhnyj
process i osvobozhdaetsya mesto na ustrojstve.
Esli process podkachki vypolnil proceduru zagruzki uspeshno, on vnov'
prosmatrivaet sovokupnost' vygruzhennyh, no gotovyh k vypolneniyu processov v
poiskah sleduyushchego processa, kotoryj predpolagaetsya zagruzit' v pamyat', i
povtoryaet ukazannuyu posledovatel'nost' dejstvij. V konechnom itoge voznikaet
odna iz sleduyushchih situacij:
* Na ustrojstve vygruzki bol'she net ni odnogo processa, gotovogo k vypol-
neniyu. Process podkachki priostanavlivaet svoyu rabotu do teh por, poka ne
vozobnovitsya process na ustrojstve vygruzki ili poka yadro ne vygruzit
process, gotovyj k vypolneniyu. (Vspomnim diagrammu sostoyanij na Risunke
6.1).
* Process podkachki obnaruzhil process, gotovyj k zagruzke, no v sisteme ne-
dostatochno pamyati dlya ego razmeshcheniya. Process podkachki pytaetsya zagru-
zit' drugoj process i v sluchae uspeha perezapuskaet algoritm podkachki,
prodolzhaya poisk zagruzhaemyh processov.
Esli processu podkachki nuzhno vygruzit' process, on prosmatrivaet vse
processy v pamyati. Prekrativshie svoe sushchestvovanie processy ne podhodyat dlya
vygruzki, poskol'ku oni ne zanimayut fizicheskuyu pamyat'; takzhe ne mogut byt'
vygruzheny processy, zablokirovannye v pamyati, naprimer, vypolnyayushchie operacii
nad oblastyami. YAdro predpochitaet vygruzhat' priostanovlennye processy, pos-
kol'ku processy, gotovye k vypolneniyu, imeyut bol'she shansov byt' vskore vyb-
rannymi na vypolnenie. Reshenie o vygruzke processa prinimaetsya yadrom na os-
novanii ego prioriteta i prodolzhitel'nosti ego prebyvaniya v pamyati. Esli v
pamyati net ni odnogo priostanovlennogo processa, reshenie o tom, kakoj iz
processov, gotovyh k vypolneniyu, sleduet vygruzit', zavisit ot znacheniya,
prisvoennogo processu funkciej nice, a takzhe ot prodolzhitel'nosti prebyvaniya
processa v pamyati.
Process, gotovyj k vypolneniyu, dolzhen byt' rezidentnym v pamyati v teche-
nie po men'shej mere 2 sekund do togo, kak ujti iz nee, a process, zagruzhae-
myj v pamyat', dolzhen po men'shej mere 2 sekundy probyt' na ustrojstve vygruz-
ki. Esli process podkachki ne mozhet najti ni odnogo processa, podhodyashchego dlya
vygruzki, ili ni odnogo processa, podhodyashchego dlya zagruzki, ili ni odnogo
processa, pered vygruzkoj ne menee 2 sekund (**) nahodivshegosya v pamyati, on
priostanavlivaet svoyu rabotu po prichine togo, chto emu nuzhno zagruzit' pro-
cess v pamyat', a v pamyati net mesta dlya ego razmeshcheniya. V etoj situacii taj-
mer vozobnovlyaet vypolnenie processa podkachki cherez kazhduyu sekundu. YAdro
---------------------------------------
(**) V versii 6 sistemy UNIX process ne mozhet byt' vygruzhen iz pamyati s
cel'yu raschistki mesta dlya zagruzhaemogo processa do teh por, poka zagru-
zhaemyj process ne provedet na diske 3 sekundy. Uhodyashchij iz pamyati pro-
cess dolzhen provesti v pamyati ne menee 2 sekund. Vremennoj interval ta-
kim obrazom delitsya na chasti, v rezul'tate chego povyshaetsya proizvodi-
tel'nost' sistemy.
261
+------------------------------------------------------------+
| algoritm swapper /* zagruzka vygruzhennyh processov, |
| * vygruzka drugih processov s cel'yu |
| * raschistki mesta v pamyati */ |
| vhodnaya informaciya: otsutstvuet |
| vyhodnaya informaciya: otsutstvuet |
| { |
| loop: |
| dlya (vseh vygruzhennyh processov, gotovyh k vypolneniyu)|
| vybrat' process, nahodyashchijsya v sostoyanii vygruzhen-|
| nosti dol'she ostal'nyh; |
| esli (takih processov net) |
| { |
| priostanovit'sya (do momenta, kogda vozniknet neob-|
| hodimost' v zagruzke processov); |
| perejti na loop; |
| } |
| esli (v osnovnoj pamyati dostatochno mesta dlya razmeshche- |
| niya processa) |
| { |
| zagruzit' process; |
| perejti na loop; |
| } |
| /* loop2: syuda vstavlyayutsya ispravleniya, vnesennye v algo- |
| * ritm */ |
| dlya (vseh processov, zagruzhennyh v osnovnuyu pamyat', |
| krome prekrativshih sushchestvovanie i zablokirovannyh v |
| pamyati) |
| { |
| esli (est' hotya by odin priostanovlennyj process) |
| vybrat' process, u kotorogo summa prioriteta i|
| prodolzhitel'nosti nahozhdeniya v pamyati nai- |
| bol'shaya; |
| v protivnom sluchae /* net ni odnogo priostanov- |
| * lennogo processa */ |
| vybrat' process, u kotorogo summa prodolzhi- |
| tel'nosti nahozhdeniya v pamyati i znacheniya nice|
| naibol'shaya; |
| } |
| esli (vybrannyj process ne yavlyaetsya priostanovlennym |
| ili ne soblyudeny usloviya rezidentnosti) |
| priostanovit'sya (do momenta, kogda poyavitsya voz- |
| mozhnost' zagruzit' process); |
| v protivnom sluchae |
| vygruzit' process; |
| perejti na loop; /* na loop2 v ispravlennom algorit-|
| * me */ |
| } |
+------------------------------------------------------------+
Risunok 9.9. Algoritm podkachki
takzhe vozobnovlyaet rabotu processa podkachki v tom sluchae, kogda odin iz pro-
cessov perehodit v sostoyanie priostanova, tak kak poslednij mozhet okazat'sya
bolee podhodyashchim dlya vygruzki processom po sravneniyu s ranee rassmotrennymi.
Esli process podkachki raschistil mesto v pamyati ili esli on byl priostanovlen
po prichine nevozmozhnosti sdelat' eto, on vozobnovlyaet svoyu rabotu s pereza-
puska algoritma podkachki (s samogo ego nachala), vnov' predprinimaya popytku
262
zagruzit' ozhidayushchie vypolneniya processy.
Na Risunke 9.10 pokazana dinamika vypolneniya pyati processov s ukazaniem
momentov ih uchastiya v realizacii algoritma podkachki. Polozhim dlya prostoty,
chto vse processy intensivno ispol'zuyut resursy central'nogo processora i chto
oni ne proizvodyat obrashchenij k sistemnym funkciyam; sledovatel'no, pereklyuche-
nie konteksta proishodit tol'ko v rezul'tate vozniknoveniya preryvanij po
tajmeru s intervalom v 1 sekundu. Process podkachki ispolnyaetsya s naivysshim
prioritetom planirovaniya, poetomu on vsegda ukladyvaetsya v sekundnyj inter-
val, kogda emu est' chto delat'. Predpolozhim dalee, chto processy imeyut odina-
kovyj razmer i chto v osnovnoj pamyati mogut odnovremenno pomestit'sya tol'ko
dva processa. Snachala v pamyati nahodyatsya processy A i B, ostal'nye processy
vygruzheny. Process podkachki ne mozhet stronut' s mesta ni odin process v te-
chenie pervyh dvuh sekund, poskol'ku etogo trebuet uslovie nahozhdeniya pereme-
shchaemogo processa v techenie etogo intervala na odnom meste (v pamyati ili na
ustrojstve vygruzki), odnako po istechenii 2 sekund process podkachki vygruzha-
et processy A i B i zagruzhaet na ih mesto processy C i D. On pytaetsya takzhe
zagruzit' i process E, no terpit neudachu, poskol'ku v osnovnoj pamyati nedos-
tatochno mesta dlya etogo. Na 3-sekundnoj otmetke process E vse eshche goden dlya
zagruzki, poskol'ku on nahodilsya vse 3 sekundy na ustrojstve vygruzki, no
process podkachki ne mozhet vygruzit' iz pamyati ni odin iz processov, ibo oni
nahodyatsya v pamyati menee 2 sekund. Na 4-sekundnoj otmetke process podkachki
vygruzhaet processy C i D i zagruzhaet vmesto nih processy E i A.
Process podkachki vybiraet processy dlya zagruzki, osnovyvayas' na prodol-
zhitel'nosti ih prebyvaniya na ustrojstve vygruzki. V kachestve drugogo krite-
riya mozhet primenyat'sya bolee vysokij prioritet zagruzhaemogo processa po srav-
neniyu s ostal'nymi, gotovymi k vypolneniyu processami, poskol'ku takoj pro-
cess bolee predpochtitelen dlya zapuska. Praktika pokazala, chto takoj podhod
"neskol'ko" povyshaet propusknuyu sposobnost' sistemy v usloviyah sil'noj zag-
ruzhennosti (sm. [Peachey 84]).
Algoritm vybora processa dlya vygruzki iz pamyati s cel'yu osvobozhdeniya
mesta trebuemogo ob®ema imeet, odnako, bolee ser'eznye iz®yany. Vo-pervyh,
process podkachki proizvodit vygruzku na osnovanii prioriteta, prodolzhitel'-
nosti nahozhdeniya v pamyati i znacheniya nice. Nesmotrya na to, chto on proizvodit
vygruzku processa s edinstvennoj cel'yu - osvobodit' v pamyati mesto dlya zag-
ruzhaemogo processa, on mozhet vygruzit' i process, kotoryj ne osvobozhdaet
mesto trebuemogo razmera. Naprimer, esli process podkachki pytaetsya zagruzit'
v pamyat' process razmerom 1 Mbajt, a v sisteme otsutstvuet svobodnaya pamyat',
budet daleko ne dostatochno vygruzit' process, zanimayushchij tol'ko 2 Kbajta pa-
myati. V kachestve al'ternativy mozhet byt' predlozhena strategiya vygruzki grupp
processov pri uslovii, chto oni osvobozhdayut mesto, dostatochnoe dlya razmeshcheniya
zagruzhaemyh processov.|ksperimenty s ispol'zovaniem mashiny PDP 11/23 pokaza-
li,chto v usloviyah sil'noj zagruzhennosti takaya strategiya mozhet uvelichit' pro-
izvoditel'nost' sistemy pochti na 10 procentov (sm. [Peachey 84]).
Vo-vtoryh, esli process podkachki priostanovil svoyu rabotu izza togo, chto
v pamyati ne hvatilo mesta dlya zagruzki processa, posle vozobnovleniya on
vnov' vybiraet process dlya zagruzki v pamyat', nesmotrya na to, chto ranee im
uzhe byl sdelan vybor. Prichina takogo povedeniya zaklyuchaetsya v tom, chto za
proshedshee vremya v sostoyanie gotovnosti k vypolneniyu mogli perejti drugie
vygruzhennye processy, bolee podhodyashchie dlya zagruzki v pamyat' po sravneniyu s
ranee vybrannym processom. Odnako ot etogo malo utesheniya dlya ranee vybranno-
go processa, vse eshche pytayushchegosya zagruzit'sya v pamyat'. V nekotoryh realiza-
ciyah process podkachki stremitsya k tomu, chtoby pered zagruzkoj v pamyat' odno-
go krupnogo processa vygruzit' bol'shoe kolichestvo processov malen'kogo raz-
mera, eto izmenenie v bazovom algoritme podkachki otrazheno v kommentariyah k
algoritmu (Risunok 9.9).
V-tret'ih, esli process podkachki vybiraet dlya vygruzki process, nahodya-
shchijsya v sostoyanii "gotovnosti k vypolneniyu", ne isklyuchena vozmozhnost' togo,
chto etot process posle zagruzki v pamyat' ni razu ne byl zapushchen na ispolne-
nie. |tot sluchaj pokazan na Risunke 9.11, iz kotorogo vidno, chto yadro zagru-
263
zhaet process D na 2- sekundnoj otmetke, zapuskaet process C, a zatem na
3-sekundnoj otmetke process D vygruzhaetsya v pol'zu processa E (ustupaya pos-
lednemu v znachenii nice), nesmotrya na to, chto processu D tak i ne byl pre-
dostavlen CP. Ponyatno, chto takaya situaciya yavlyaetsya nezhelatel'noj.
Sleduet upomyanut' eshche ob odnoj opasnosti. Esli pri popytke vygruzit'
process na ustrojstve vygruzki ne budet najdeno svobodnoe mesto, v sisteme
mozhet vozniknut' tupikovaya situaciya, pri kotoroj: vse processy v osnovnoj
Vremya Process A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | vygruzhen | vygruzhen | vygruzhen
| zapushchen | | 0 | 0 | 0
| | | | |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | zapushchen | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| vygruzhen | vygruzhen | zagruzhen | zagruzhen |
| 0 | 0 | 0 | 0 |
| | | zapushchen | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | zapushchen |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 4
4| zagruzhen | | vygruzhen | vygruzhen | zagruzhen
| 0 | | 0 | 0 | 0
| | | | | zapushchen
| | | | |
| | | | |
--+- 1 | 3 | 1 | 1 | 1
5| zapushchen | | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 4 | 2 | 2 | 2
6| vygruzhen | zagruzhen | zagruzhen | | vygruzhen
| 0 | 0 | 0 | | 0
| | zapushchen | | |
| | | | |
v
Risunok 9.10. Posledovatel'nost' operacij, vypolnyaemyh
processom podkachki
264
Vremya Process A B C D E
--+--------------+-----------+-----------+-----------+-----------
0| 0 | 0 | vygruzhen | nice 25 | vygruzhen
| zapushchen | | 0 | vygruzhen | 0
| | | | 0 |
| | | | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 1
1| | zapushchen | | |
| | | | |
| | | | |
| | | | |
| | | | |
--+- 2 | 2 | 2 | 2 | 2
2| vygruzhen | vygruzhen | zagruzhen | zagruzhen |
| 0 | 0 | 0 | 0 |
| | | zapushchen | |
| | | | |
| | | | |
--+- 1 | 1 | 1 | 1 | 3
3| | | | vygruzhen | zagruzhen
| | | | 0 | 0
| | | | | zapushchen
| | | | |
| | | | |
--+- 2 | 2 | 2 | 1 | 1
4| zagruzhen | | vygruzhen | |
| 0 | | 0 | |
| zapushchen | | | |
| | | | |
| | | | |
--+- 1 | 3 | 1 | 2 | 2
5| | zagruzhen | | | vygruzhen
| | 0 | | | 0
| | zapushchen | | |
| | | | |
| | | | |
--+- 2 | 1 | 2 | 3 | 1
6| vygruzhen | | | zagruzhen |
| 0 | | | 0 |
| | | | zapushchen |
| | | | |
v
Risunok 9.11. Zagruzka processov v sluchae razbivki vremennyh
intervalov na chasti
pamyati nahodyatsya v sostoyanii priostanova, vse gotovye k vypolneniyu processy
vygruzheny, dlya novyh processov na ustrojstve vygruzki uzhe net mesta, net
svobodnogo mesta i v osnovnoj pamyati. |ta situaciya razbiraetsya v uprazhnenii
9.5. Interes k problemam, svyazannym s podkachkoj processov, v poslednie gody
spal v svyazi s realizaciej algoritmov podkachki stranic pamyati.
265
Algoritm podkachki stranic pamyati podderzhivaetsya na mashinah so stranichnoj
organizaciej pamyati i s CP, imeyushchim preryvaemye komandy (***). V sistemah s
podkachkoj stranic otsutstvuyut ogranicheniya na razmer processa, svyazannye s
ob®emom dostupnoj fizicheskoj pamyati. Naprimer, v mashinah s ob®emom fiziches-
koj pamyati 1 i 2 Mbajta mogut ispolnyat'sya processy razmerom 4 ili 5 Mbajt.
Ogranichenie na virtual'nyj razmer processa, svyazannoe s ob®emom adresuemoj
virtual'noj pamyati, ostaetsya v sile i zdes'. Poskol'ku process mozhet ne po-
mestit'sya v fizicheskoj pamyati, yadru prihoditsya dinamicheski zagruzhat' v pa-
myat' otdel'nye ego chasti i ispolnyat' ih, nesmotrya na otsutstvie ostal'nyh
chastej. V mehanizme podkachki stranic vse otkryto dlya pol'zovatel'skih prog-
ramm, za isklyucheniem razreshennogo processu virtual'nogo razmera.
Processy stremyatsya ispolnyat' komandy nebol'shimi porciyami, kotorye imenu-
yutsya programmnymi ciklami ili podprogrammami, ispol'zuemye imi ukazateli
gruppiruyutsya v nebol'shie podnabory, raspolagaemye v informacionnom prostran-
stve processa. V etom sostoit sut' tak nazyvaemogo principa "lokal'nosti".
Denningom [Denning 68] bylo sformulirovano ponyatie rabochego mnozhestva pro-
cessa kak sovokupnosti stranic, ispol'zovannyh processom v poslednih n ssyl-
kah na adresnoe prostranstvo pamyati; chislo n nazyvaetsya oknom rabochego mno-
zhestva. Poskol'ku rabochee mnozhestvo processa yavlyaetsya chast'yu ot celogo, v
osnovnoj pamyati mozhet pomestit'sya bol'she processov po sravneniyu s temi sis-
temami, gde upravlenie pamyat'yu baziruetsya na podkachke processov, chto v ko-
nechnom itoge privodit k uvelicheniyu proizvoditel'nosti sistemy. Kogda process
obrashchaetsya k stranice, otsutstvuyushchej v ego rabochem mnozhestve, voznikaet
oshibka, pri obrabotke kotoroj yadro korrektiruet rabochee mnozhestvo processa,
v sluchae neobhodimosti podkachivaya stranicy s vneshnego ustrojstva.
Na Risunke 9.12 privedena posledovatel'nost' ispol'zuemyh processom uka-
zatelej stranic, opisyvayushchih rabochie mnozhestva s oknami razlichnyh razmerov
pri uslovii soblyudeniya algoritma zameshcheniya "starikov" (zameshcheniya stranic pu-
tem otkachki teh, k kotorym naibolee dolgo ne bylo obrashchenij). Po mere vypol-
neniya processa ego rabochee mnozhestvo vidoizmenyaetsya v sootvetstvii s ispol'-
zuemymi processom ukazatelyami stranic; uvelichenie razmera okna vlechet za so-
boj uvelichenie rabochego mnozhestva i, s drugoj storony, sokrashchenie chisla oshi-
bok v vypolnenii processa. Ispol'zovanie neizmennogo rabochego mnozhestva ne
praktikuetsya, poskol'ku zapominanie ocherednosti sledovaniya ukazatelej stra-
nic potrebovalo by slishkom bol'shih zatrat. Priblizitel'noe sootvetstvie mezh-
du izmenyaemym rabochim mnozhestvom i prostranstvom processa dostigaetsya putem
ustanovki bita upominaniya (reference bit) pri obrashchenii k stranice pamyati, a
takzhe periodicheskim oprosom ukazatelej stranic. Esli na stranicu byla sdela-
na ssylka, eta stranica vklyuchaetsya v rabochee mnozhestvo; v protivnom sluchae
ona "dozrevaet" v pamyati v ozhidanii svoej ocheredi.
V sluchae vozniknoveniya oshibki iz-za obrashcheniya k stranice, otsutstvuyushchej
v rabochem mnozhestve, yadro priostanavlivaet vypolnenie processa do teh por,
poka stranica ne budet schitana v pamyat' i ne stanet dostupnoj processu. Kog-
da stranica budet zagruzhena, process perezapustit tu komandu, na kotoroj vy-
polnenie processa bylo priostanovleno iz-za oshibki. Takim obrazom, rabota
podsistemy zameshcheniya stranic raspadaetsya na dve chasti: otkachka redko ispol'-
zuemyh stranic na ustrojstvo vygruzki i obrabotka oshibok iz-za otsutstviya
nuzhnoj stranicy. Takoe obshchee tolkovanie mehanizma zameshcheniya stranic, konechno
zhe, vyhodit za predely odnoj konkretnoj sistemy. Ostavshuyusya chast' glavy my
posvyatim bolee detal'nomu rassmotreniyu osobennostej realizacii etogo meha-
nizma v versii V sistemy UNIX.
---------------------------------------
(***) Esli pri ispolnenii komandy voznikaet oshibka, svyazannaya s otsutstviem
stranicy, posle obrabotki oshibki CP obyazan perezapustit' komandu, pos-
kol'ku promezhutochnye rezul'taty, poluchennye k momentu vozniknoveniya
oshibki, mogut byt' utracheny.
266
9.2.1 Struktury dannyh, ispol'zuemye podsistemoj zameshcheniya stranic
Dlya podderzhki funkcij upravleniya pamyat'yu na mashinnom (nizkom) urovne i
dlya realizacii mehanizma zameshcheniya stranic yadro ispol'zuet 4 osnovnye struk-
tury dannyh: zapisi tablicy stranic, deskriptory diskovyh blokov, tablicu
soderzhimogo stranichnyh blokov (page frame data table - sokrashchenno: pfdata) i
tablicu ispol'zovaniya oblasti podkachki. Mesto dlya tablicy pfdata vydelyaetsya
odin raz na vse vremya zhizni sistemy, dlya drugih zhe struktur stranicy pamyati
vydelyayutsya dinamicheski.
Iz glavy 6 nam izvestno, chto kazhdaya oblast' raspolagaet svoimi tablicami
stranic, s pomoshch'yu kotoryh osushchestvlyaetsya dostup k fizicheskoj pamyati. Kazhdaya
zapis' tablicy stranic (Risunok 9.13) sostoit iz fizicheskogo adresa strani-
cy, koda zashchity, v razryadah kotorogo opisyvayutsya prava dostupa processa k
stranice (na chtenie, zapis' i ispolnenie), a takzhe sleduyushchih dvoichnyh polej,
ispol'zuemyh mehanizmom zameshcheniya stranic:
Posledovatel'-
nost' ukazate- Rabochie mnozhestva Razmery okon
lej stranic 2 3 4 5
+------------+ +-------+----------+-------------+----------------+
| 24 | | 24 | 24 | 24 | 24 |
+------------+ | | | | |
| 15 | | 15 24 | 15 24 | 15 24 | 15 24 |
+------------+ | | | | |
| 18 | | 18 15 | 18 15 24 | 18 15 24 | 18 15 24 |
+------------+ | | | | |
| 23 | | 23 18 | 23 18 15 | 23 18 15 24 | 23 18 15 24 |
+------------+ | | | - | - |
| 24 | | 24 23 | 24 23 18 | - | - |
+------------+ | | | - | - |
| 17 | | 17 24 | 17 24 23 | 17 24 23 18 | 17 24 23 18 15 |
+------------+ | | | - | - |
| 18 | | 18 17 | 18 17 24 | - | - |
+------------+ | | - | - | - |
| 24 | | 24 18 | - | - | - |
+------------+ | | - | - | - |
| 18 | | 18 24 | - | - | - |
+------------+ | | - | - | - |
| 17 | | 17 18 | - | - | - |
+------------+ | | - | - | - |
| 17 | | | - | - | - |
+------------+ | | - | - | - |
| 15 | | 15 17 | 15 17 18 | 15 17 18 24 | - |
+------------+ | | | - | - |
| 24 | | 24 15 | 24 15 17 | - | - |
+------------+ | | - | - | - |
| 17 | | 17 24 | - | - | - |
+------------+ | | - | - | - |
| 24 | | 24 17 | - | - | - |
+------------+ | | - | - | - |
| 18 | | 18 24 | 18 24 17 | - | - |
+------------+ +-------+----------+-------------+----------------+
Risunok 9.12. Rabochee mnozhestvo processa
* bit dostupnosti
* bit upominaniya
267
* bit modifikacii
* bit kopirovaniya pri zapisi
* "vozrast" stranicy
Ustanovka bita dostupnosti svidetel'stvuet o pravil'nosti soderzhimogo
stranicy pamyati, odnako iz togo, chto bit dostupnosti vyklyuchen, ne sleduet s
neobhodimost'yu to, chto ssylka na stranicu nedopustima, v chem my ubedimsya
pozzhe. Bit upominaniya ustanavlivaetsya v tom sluchae, esli process delaet
ssylku na stranicu, a bit modifikacii - v tom sluchae, esli process skorrek-
tiroval soderzhimoe stranicy. Ustanovka bita kopirovaniya pri zapisi, proizvo-
dimaya vo vremya vypolneniya sistemnoj funkcii fork, svidetel'stvuet o tom, chto
yadru v sluchae, kogda process korrektiruet soderzhimoe stranicy, sleduet soz-
davat' ee novuyu kopiyu. Nakonec, "vozrast" stranicy govorit o prodolzhitel'-
nosti ee prebyvaniya v sostave rabochego mnozhestva processa. Bity dostupnosti,
kopirovaniya pri zapisi i "vozrast" stranicy ustanavlivayutsya yadrom, bity upo-
minaniya i modifikacii - apparatnym putem; v razdele 9.2.4 rassmatrivayutsya
konfiguracii, v kotoryh eti vozmozhnosti ne podderzhivayutsya apparaturoj.
+--------+ +->+----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| | | | | |
| | | +----------------------+---------------------------+
| Oblast'| | | | |
| | | +----------------------+---------------------------+
| | | |Zapisi tablicy stranic|Deskriptory diskovyh blokov|
| ----+-+ +----------------------+---------------------------+
| | | | |
| | +----------------------+---------------------------+
| | | | |
+--------+ +----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
| | |
+----------------------+---------------------------+
Zapis' tablicy stranic
+-----------------------------+-------+-----+-----+----+-----+---+
| Adres stranicy (fizicheskij) |Vozrast|Kopi-|Modi-|Upo-|Do- |Za-|
| | |rova-|fika-|mi- |pus- |shchi-|
| | |nie |ciya |na- |ti- |ta |
| | |pri | |nie |most'| |
| | |zapi-| | | | |
| | |si | | | | |
+-----------------------------+-------+-----+-----+----+-----+---+
Deskriptor diskovogo bloka
+-----------------------+---------------+------------------------+
| Ustrojstvo vygruzki | Nomer bloka | Tip (nahoditsya na us- |
| | | trojstve vygruzki, v |
| | | fajle, pri obrashchenii |
| | | obnulyaetsya, zapolnyaet- |
| | | sya) |
+-----------------------+---------------+------------------------+
Risunok 9.13. Zapisi tablicy stranic i deskriptory diskovyh blokov
268
Kazhdaya zapis' tablicy stranic svyazana s deskriptorom diskovogo bloka,
opisyvayushchim diskovuyu kopiyu virtual'noj stranicy (Risunok 9.13). Poetomu pro-
cessy, ispol'zuyushchie razdelyaemuyu oblast', obrashchayutsya k obshchim zapisyam tablicy
stranic i k odnim i tem zhe deskriptoram diskovyh blokov. Soderzhimoe virtu-
al'noj stranicy raspolagaetsya libo v otdel'nom bloke na ustrojstve vygruzki,
libo v ispolnyaemom fajle, libo voobshche otsutstvuet na ustrojstve vygruzki.
Esli stranica nahoditsya na ustrojstve vygruzki, v deskriptore diskovogo blo-
ka soderzhitsya logicheskij nomer ustrojstva i nomer bloka, po kotorym mozhno
otyskat' soderzhimoe stranicy. Esli stranica soderzhitsya v ispolnyaemom fajle,
v deskriptore diskovogo bloka raspolagaetsya nomer logicheskogo bloka v fajle
s soderzhimym stranicy; yadro mozhet bystro preobrazovat' etot nomer v adres na
diske. V deskriptore diskovogo bloka takzhe imeetsya informaciya o dvuh usta-
navlivaemyh funkciej exec osobyh usloviyah: stranica pri obrashchenii k nej za-
polnyaetsya ("demand fill") ili obnulyaetsya ("demand zero"). Raz®yasneniya po
etomu povodu dayutsya v razdele 9.2.1.2.
V tablice pfdata opisyvaetsya kazhdaya stranica fizicheskoj pamyati. Zapisi
tablicy proindeksirovany po nomeru stranicy i sostoyat iz sleduyushchih polej:
* Status stranicy, ukazyvayushchij na to, chto stranica raspolagaetsya na ust-
rojstve vygruzki ili v ispolnyaemom fajle, chto k stranice proizvedeno ob-
rashchenie po pryamomu dostupu v pamyat' (putem schityvaniya informacii s ust-
rojstva vygruzki), ili na to, chto stranica mozhet byt' perenaznachena.
* Kolichestvo processov, ssylayushchihsya na stranicu. Schetchik ssylok hranit
chislo zapisej v tablice stranic, imeyushchih ssylku na tekushchuyu stranicu. |to
znachenie mozhet otlichat'sya ot kolichestva processov, ispol'zuyushchih razdelya-
emuyu oblast' s dannoj stranicej, v chem my ubedimsya chut' pozzhe, kogda bu-
dem snova obrashchat'sya k algoritmu funkcii fork.
* Logicheskij nomer ustrojstva (ustrojstva vygruzki ili fajlovoj sistemy) i
nomer bloka, ukazyvayushchie raspolozhenie soderzhimogo stranicy.
* Ukazateli na drugie zapisi tablicy pfdata v sootvetstvii so spiskom svo-
bodnyh stranic ili s hesh-ochered'yu stranic.
Po analogii s bufernym keshem yadro svyazyvaet zapisi tablicy pfdata v spi-
sok svobodnyh stranic i hesh-ochered'. Spisok svobodnyh stranic predstavlyaet
soboj bufer, kotoryj soderzhit stranicy, dostupnye dlya perenaznacheniya, odnako
process, obrativshijsya k etim stranicam, mozhet stolknut'sya s oshibkoj adresa-
cii, tak i ne poluchiv sootvetstvuyushchuyu stranicu iz spiska. |tot spisok daet
yadru vozmozhnost' sokratit' chislo operacij chteniya s ustrojstva vygruzki. YAdro
vydelyaet stranicy iz etogo spiska po vyshenazvannomu principu zameshcheniya "sta-
rikov". YAdro vystraivaet zapisi tablicy v hesh-ochered' v sootvetstvii s nome-
rom ustrojstva (vygruzki) i nomerom bloka. Ispol'zuya eti nomera, yadro mozhet
bystro otyskat' stranicu, esli ona nahoditsya v pamyati. Peredavaya fizicheskuyu
stranicu oblasti, yadro vybiraet sootvetstvuyushchuyu zapis' iz spiska svobodnyh
stranic, ispravlyaet ukazannye v nej nomera ustrojstva i bloka i pomeshchaet ee
v sootvetstvuyushchee mesto hesh-ocheredi.
Kazhdaya zapis' tablicy ispol'zovaniya oblasti podkachki sootvetstvuet stra-
nice, nahodyashchejsya na ustrojstve vygruzki. Zapis' soderzhit schetchik ssylok,
pokazyvayushchij kolichestvo zapisej tablicy stranic, v kotoryh imeetsya ssylka na
tekushchuyu stranicu.
Na Risunke 9.14 pokazana vzaimosvyaz' mezhdu zapisyami tablicy stranic,
deskriptorami diskovyh blokov, zapisyami tablicy pfdata i tablicy ispol'zova-
niya oblasti podkachki. Virtual'nyj adres 1493K otobrazhaetsya na zapis' tablicy
stranic, sootvetstvuyushchuyu stranice s fizicheskim nomerom 794; deskriptor dis-
kovogo bloka, svyazannyj s etoj zapis'yu, svidetel'stvuet o tom, chto soderzhi-
moe stranicy raspolagaetsya na ustrojstve vygruzki s nomerom 1 v diskovom
bloke s nomerom 2743. Zapis' tablicy pfdata, pomimo togo, chto ukazyvaet na
te zhe nomera ustrojstva i bloka, soobshchaet, chto schetchik ssylok na fizicheskuyu
stranicu imeet znachenie, ravnoe 1. O tom, pochemu nomer diskovogo bloka dub-
liruetsya v zapisi tablicy pfdata, vy uznaete iz razdela 9.2.4.1. Schetchik
ssylok na virtual'nuyu stranicu (v zapisi tablicy ispol'zovaniya oblasti pod-
kachki) svidetel'stvuet o tom, chto na kopiyu stranicy na ustrojstve vygruzki
269
ssylaetsya tol'ko odna zapis' tablicy stranic.
9.2.1.1 Funkciya fork v sisteme s zameshcheniem stranic
Kak uzhe govorilos' v razdele 7.1, vo vremya vypolneniya funkcii fork yadro
sozdaet kopiyu kazhdoj oblasti roditel'skogo processa i prisoedinyaet ee k pro-
cessu-potomku. V sisteme s zameshcheniem stra-
+-----------------------+--------------------------+
Virtual'nyj |Zapis' tablicy stranic|Deskriptor diskovogo bloka|
adres +-----------------------+--------------------------+
1493K | Nomer stranicy 794 | Ustrojstvo 1 Blok 2743 |
+---+-+-----------------+--------------------+-----+
| | |
| | Zapis' tablicy pfdata, |
| | sootvetstvuyushchaya stra- +------------+
+------------+ v nice s nomerom 794 |
| +------------+-----------------------+ |
| | | Schetchik ssylok 1 | | Zapis' tablicy
| | +-----------------------+ | ispol'zovaniya
| | | Nomer ustrojstva 1 | | oblasti podkachki
| | +-----------------------+ | +-----------------+
| | | Nomer bloka 2743 | | |Schetchik ssylok 1|
| | +-----------------+-----+ | +--------+--------+
| | | +-----+ |
| | | | +--------------+
v v v v v
+--------------------------+ +---------------------------+
| Fizicheskaya stranica 794 | | Nomer bloka 2743 |
+--------------------------+ +---------------------------+
Risunok 9.14. Vzaimosvyaz' mezhdu strukturami dannyh, uchastvuyushchimi v rea-
lizacii mehanizma zameshcheniya stranic po obrashcheniyu
nic yadro po tradicii sozdaet fizicheskuyu kopiyu adresnogo prostranstva proces-
sa-roditelya, chto v obshchem sluchae yavlyaetsya dovol'no rastochitel'noj operaciej,
poskol'ku process chasto posle vypolneniya funkcii fork obrashchaetsya k funkcii
exec i nezamedlitel'no osvobozhdaet tol'ko chto skopirovannoe prostranstvo.
Esli oblast' razdelyaemaya, v versii V vmesto kopirovaniya stranicy yadro prosto
uvelichivaet znachenie schetchika ssylok na oblast' (v tablice oblastej, v tab-
lice stranic i v tablice pfdata). Tem ne menee, dlya chastnyh oblastej, takih
kak oblast' dannyh i steka, yadro otvodit v tablice oblastej i tablice stra-
nic novuyu zapis', posle chego prosmatrivaet v tablice stranic vse zapisi pro-
cessa-roditelya: esli zapis' verna, yadro uvelichivaet znachenie schetchika ssylok
v tablice pfdata, otrazhayushchee kolichestvo processov, ispol'zuyushchih stranicu che-
rez raznye oblasti (v otlichie ot teh processov, kotorye ispol'zuyut dannuyu
stranicu cherez razdelyaemuyu oblast'). Esli stranica raspolagaetsya na ustrojs-
tve vygruzki, yadro uvelichivaet znachenie schetchika ssylok v tablice ispol'zo-
vaniya oblasti podkachki.
Teper' na stranicu mogut ssylat'sya obe oblasti, ispol'zuyushchie etu strani-
cu sovmestno, poka process ne vedet na nee zapis'. Kak tol'ko stranica pona-
dobitsya processu dlya zapisi, yadro sozdast ee kopiyu, s tem, chtoby u kazhdoj
oblasti byla svoya lichnaya versiya stranicy. Dlya etogo pri vypolnenii funkcii
fork v kazhdoj zapisi tablicy stranic, sootvetstvuyushchej chastnym oblastyam rodi-
telya i potomka, yadro ustanavlivaet bit "kopirovaniya pri zapisi". Esli odin
iz processov popytaetsya chto-to zapisat' na stranicu, on poluchit otkaz siste-
my zashchity, posle chego dlya nego budet sozdana novaya kopiya soderzhimogo strani-
cy. Takim obrazom, fizicheskoe kopirovanie stranicy otkladyvaetsya do togo mo-
270
menta, kogda v etom vozniknet real'naya potrebnost'.
V kachestve primera rassmotrim Risunok 9.15. Processy razdelyayut dostup k
tablice stranic sovmestno ispol'zuemoj oblasti komand T, poetomu znachenie
schetchika ssylok na oblast' ravno 2, a na stranicy oblasti edinice (v tablice
pfdata). YAdro naznachaet pro-
Process-roditel' Process-potomok
CHastnaya tablica CHastnaya tablica
oblastej processa oblastej processa
+--------------+ +--------------+
| - | | - |
+--------------+ +--------------+
| - - | | - - |
+--------------+ +--------------+
- + ---------------------+ -
- - - -
v v v v
+-------------------+ +-------------------+ +-------------------+
| Oblast' T | | Oblast' P1 | | Oblast' C1 |
| Schetchik ssylok 2 | | Schetchik ssylok 1 | | Schetchik ssylok 1 |
|+-----------------+| |+-----------------+| |+-----------------+|
|| Zapisi tablicy || || Zapisi tablicy || || Zapisi tablicy ||
|| stranic || || stranic || || stranic ||
|+-----------------+| |+-----------------+| |+-----------------+|
|| - || || - || || - ||
|| - || || - || || - ||
|+-----------------+| || - || || - ||
||Virtual'- Stra-|| || - || || - ||
||nyj adres nica || || - || || - ||
|| 24K 967 || || - || || - ||
|+-----------------+| |+-----------------+| |+-----------------+|
|| - - || ||Virtual'- Stra-|| ||Virtual'- Stra-||
|| - - || ||nyj adres nica || ||nyj adres nica ||
|| - - || || 97K 613 || || 97K 613 ||
|| - - || |+-----------------+| |+-----------------+|
|| - - || || - - || || - - ||
|| - - || || - - || || - - ||
|+-----------------+| |+-----------------+| |+-----------------+|
+-------------------+ +-------------------+ +-------------------+
- - -----------
v v v
+---------------------+ +---------------------+
| Stranichnyj blok 967 | | Stranichnyj blok 613 |
| Schetchik ssylok 1 | | Schetchik ssylok 2 |
+---------------------+ +---------------------+
Risunok 9.15. Adresaciya stranic, uchastvuyushchih v processe vy-
polneniya funkcii fork
cessu-potomku novuyu oblast' dannyh C1, yavlyayushchuyusya kopiej oblasti P1 proces-
sa-roditelya. Obe oblasti ispol'zuyut odni i te zhe zapisi tablicy stranic, eto
vidno na primere stranicy s virtual'nym adresom 97K. |toj stranice v tablice
pfdata sootvetstvuet zapis' s nomerom 613, schetchik ssylok v kotoroj raven 2,
ibo na stranicu ssylayutsya dve oblasti.
V hode vypolneniya funkcii fork v sisteme BSD sozdaetsya fizicheskaya kopiya
stranic roditel'skogo processa. Odnako, uchityvaya nalichie situacij, v kotoryh
sozdanie fizicheskoj kopii ne yavlyaetsya obyazatel'nym, v sisteme BSD sushchestvuet
271
takzhe funkciya vfork, kotoraya ispol'zuetsya v tom sluchae, esli process srazu
po zavershenii funkcii fork sobiraetsya zapustit' funkciyu exec. Funkciya vfork
ne kopiruet tablicy stranic, poetomu ona rabotaet bystree, chem funkciya fork
v versii V sistemy UNIX. Odnako process-potomok pri etom ispolnyaetsya v teh
zhe samyh fizicheskih adresah, chto i ego roditel', i mozhet poetomu zateret'
dannye i stek roditel'skogo processa. Esli programmist ispol'zuet funkciyu
vfork neverno, mozhet vozniknut' opasnaya situaciya, poetomu vsya otvetstven-
nost' za ee ispol'zovanie vozlagaetsya na programmista. Razlichie v podhodah k
rassmatrivaemomu voprosu v sistemah UNIX i BSD imeet filosofskij harakter,
oni dayut raznyj otvet na odin i tot zhe vopros: sleduet li yadru skryvat' oso-
bennosti realizacii svoih funkcij, prevrashchaya ih v tajnu dlya pol'zovatelej,
ili zhe stoit dat' opytnym pol'zovatelyam vozmozhnost' povysit' effektivnost'
vypolneniya sistemnyh operacij ?
+------------------------------------------------------------+
| int global; |
| main() |
| { |
| int local; |
| |
| local = 1; |
| if (vfork() == 0) |
| { |
| /* potomok */ |
| global = 2; /* zapis' v oblast' dannyh roditelya */|
| local = 3; /* zapis' v stek roditelya */ |
| _exit(); |
| } |
| printf("global %d local %d\n",global,local); |
| } |
+------------------------------------------------------------+
Risunok 9.16. Funkciya vfork i iskazhenie informacii processa
V kachestve primera rassmotrim programmu, privedennuyu na Risunke 9.16.
Posle vypolneniya funkcii vfork process-potomok ne zapuskaet funkciyu exec, a
pereustanavlivaet znacheniya peremennyh global i local i zavershaetsya (****).
Sistema garantiruet, chto process-roditel' priostanavlivaetsya do togo momen-
ta, kogda potomok ispolnit funkcii exec ili exit. Vozobnoviv v konechnom ito-
ge svoe vypolnenie, process-roditel' obnaruzhit, chto znacheniya dvuh ego pere-
mennyh ne sovpadayut s temi znacheniyami, kotorye byli u nih do obrashcheniya k
funkcii vfork ! Eshche bol'shij effekt mozhet proizvesti vozvrashchenie processa-po-
tomka iz funkcii, vyzvavshej funkciyu vfork (sm. uprazhnenie 9.8).
9.2.1.2 Funkciya exec v sisteme s zameshcheniem stranic
Kak uzhe govorilos' v glave 7, kogda process obrashchaetsya k sistemnoj funk-
cii exec, yadro schityvaet iz fajlovoj sistemy v pamyat' ukazannyj ispolnyaemyj
fajl. Odnako v sisteme s zameshcheniem stranic po zaprosu ispolnyaemyj fajl,
---------------------------------------
(****) Funkciya exit ispol'zuetsya v variante _exit, potomu chto ona "ochishchaet"
struktury dannyh, peredavaemye cherez standartnyj vvod-vyvod (na pol'-
zovatel'skom urovne), dlya oboih processov, tak chto operator printf,
ispol'zuemyj roditelem, ne dast pravil'nyj rezul'tat - eshche odin nezhe-
latel'nyj pobochnyj effekt ot primeneniya funkcii vfork.
272
imeyushchij bol'shoj razmer, mozhet ne umestit'sya v dostupnom prostranstve osnov-
noj pamyati. Poetomu yadro ne naznachaet emu srazu vse prostranstvo, a otvodit
mesto v pamyati po mere nadobnosti. Snachala yadro naznachaet fajlu tablicy
stranic i deskriptory diskovyh blokov, pomechaya stranicy v zapisyah tablic kak
"zapolnyaemye pri obrashchenii" (dlya vseh dannyh, krome imeyushchih tip bss) ili
"obnulyaemye pri obrashchenii" (dlya dannyh tipa bss). Schityvaya v pamyat' kazhduyu
stranicu fajla po algoritmu read, process poluchaet oshibku iz-za otsutstviya
(nedostupnosti) dannyh. Podprogramma obrabotki oshibok proveryaet, yavlyaetsya li
stranica "zapolnyaemoj pri obrashchenii" (togda ee soderzhimoe budet nemedlenno
zatirat'sya soderzhimym ispolnyaemogo fajla i poetomu ee ne nado ochishchat') ili
"obnulyaemoj pri obrashchenii" (togda ee sleduet ochistit'). V razdele 9.2.3 my
uvidim, kak eto proishodit. Esli process ne mozhet pomestit'sya v pamyati,
"sborshchik" stranic osvobozhdaet dlya nego mesto, periodicheski otkachivaya iz pa-
myati neispol'zuemye stranicy.
V etoj sheme vidny yavnye nedostatki. Vo-pervyh, pri chtenii kazhdoj stra-
nicy ispolnyaemogo fajla process stalkivaetsya s oshibkoj iz-za obrashcheniya k ot-
sutstvuyushchej stranice, pust' dazhe process nikogda i ne obrashchalsya k nej.
Vo-vtoryh, esli posle togo, kak "sborshchik" stranic otkachal chast' stranic iz
pamyati, byla zapushchena funkciya exec, kazhdaya tol'ko chto vygruzhennaya i vnov'
ponadobivshayasya stranica potrebuet dopolnitel'nuyu operaciyu po ee zagruzke.
CHtoby povysit' effektivnost' funkcii exec, yadro mozhet vostrebovat' stranicu
neposredstvenno iz ispolnyaemogo fajla, esli dannye v fajle sootvetstvuyushchim
obrazom nastroeny, chto opredelyaetsya znacheniem t.n. "magicheskogo chisla". Od-
nako, ispol'zovanie standartnyh algoritmov dostupa k fajlu (naprimer, bmap)
potrebovalo by pri obrashchenii k stranice, sostoyashchej iz blokov kosvennoj adre-
sacii, bol'shih zatrat, svyazannyh s mnogokratnym ispol'zovaniem bufernogo ke-
sha dlya chteniya kazhdogo bloka. Krome togo, funkciya bmap ne yavlyaetsya reentera-
bel'noj, otsyuda voznikaet opasnost' narusheniya celostnosti dannyh. Vo vremya
vypolneniya sistemnoj funkcii read yadro ustanavlivaet v prostranstve processa
znacheniya razlichnyh parametrov vvoda-vyvoda. Esli pri popytke skopirovat'
dannye v prostranstvo pol'zovatelya process stolknetsya s otsutstviem nuzhnoj
stranicy, on, schityvaya stranicu iz fajlovoj sistemy, mozhet zateret' soderzha-
shchie eti parametry polya. Poetomu yadro ne mozhet pribegat' k ispol'zovaniyu
obychnyh algoritmov obrabotki oshibok dannogo roda. Konechno zhe algoritmy dolzh-
ny byt' v obychnyh sluchayah reenterabel'nymi, poskol'ku u kazhdogo processa
svoe otdel'noe adresnoe prostranstvo i process ne mozhet odnovremenno ispol-
nyat' neskol'ko sistemnyh funkcij.
Dlya togo, chtoby schityvat' stranicy neposredstvenno iz ispolnyaemogo faj-
la, yadro vo vremya ispolneniya funkcii exec sostavlyaet spisok nomerov diskovyh
blokov fajla i prisoedinyaet etot spisok k indeksu fajla. Rabotaya s tablicami
stranic takogo fajla, yadro nahodit deskriptor diskovogo bloka, soderzhashchego
stranicu, i zapominaet nomer bloka vnutri fajla; etot nomer pozzhe ispol'zu-
Spisok blokov,
Oblast' +-> svyazannyj s indeksom
+---------------------------------+ | +----------------+
| Indeks-----------+-+ 0 | |
| | - | |
| | - | |
| Deskriptor diskovogo bloka | - | |
| +---------------------------+ | - | |
| | Logicheskij blok 84 | | - +----------------+
| +---------------------------+ | 84 | 279 |
| | +----------------+
+---------------------------------+ | |
| |
+----------------+
Risunok 9.17. Otobrazhenie fajla na oblast'
273
etsya pri zagruzke stranicy iz fajla. Na Risunke 9.17 pokazan primer, v koto-
rom stranica imeet adres raspolozheniya v logicheskom bloke s nomerom 84 ot na-
chala fajla. V oblasti imeetsya ukazatel' na indeks, v kotorom soderzhitsya no-
mer sootvetstvuyushchego fizicheskogo bloka na diske (279).
9.2.2 "Sborshchik" stranic
"Sborshchik" stranic (page stealer) yavlyaetsya processom, prinadlezhashchim yadru
operacionnoj sistemy i vypolnyayushchim vygruzku iz pamyati teh stranic, kotorye
bol'she ne vhodyat v sostav rabochego mnozhestva pol'zovatel'skogo processa.
|tot process sozdaetsya yadrom vo vremya inicializacii sistemy i zapuskaetsya v
lyuboj moment, kogda v nem voznikaet neobhodimost'. On prosmatrivaet vse ak-
tivnye nezablokirovannye oblasti i uvelichivaet znachenie "vozrasta" kazhdoj
prinadlezhashchej im stranicy (zablokirovannye oblasti propuskayutsya, no vposled-
stvii, po snyatii blokirovki, tozhe budut uchteny). Kogda process pri rabote so
stranicej, prinadlezhashchej oblasti, poluchaet oshibku, yadro blokiruet oblast',
chtoby "sborshchik" ne smog vygruzit' stranicu do teh por, poka oshibka ne budet
obrabotana.
Stranica v pamyati mozhet nahodit'sya v dvuh sostoyaniyah: libo "dozrevat'",
ne buduchi eshche gotovoj k vygruzke, libo byt' gotovoj k vygruzke i dostupnoj
dlya privyazki k drugim virtual'nym stranicam. Pervoe sostoyanie oznachaet, chto
process obratilsya k stranice i poetomu stranica vklyuchena v ego rabochee mno-
zhestvo. Pri obrashchenii k stranice v nekotoryh mashinah apparatno ustanavliva-
etsya bit upominaniya, esli zhe eta operaciya ne vypolnyaetsya, sootvetstvenno, i
programmnye metody skoree vsego ispol'zuyutsya drugie (razdel 9.2.4). Esli
stranica nahoditsya v pervom sostoyanii, "sborshchik" sbrasyvaet bit upominaniya v
nol', no zapominaet kolichestvo prosmotrov mnozhestva stranic, vypolnennyh s
momenta poslednego obrashcheniya k stranice so storony pol'zovatel'skogo proces-
sa. Takim obrazom, pervoe sostoyanie raspadaetsya na neskol'ko podsostoyanij v
sootvetstvii s tem, skol'ko raz "sborshchik" stranic obratilsya k stranice do
togo, kak stranica stala gotovoj dlya vygruzki (sm. Risunok 9.18). Kogda eto
chislo prevyshaet nekotoroe porogovoe znachenie, yadro perevodit stranicu vo
vtoroe sostoyanie - sostoyanie gotovnosti k vygruzke. Maksimal'naya prodolzhi-
tel'nost' prebyvaniya stranicy v pervom sostoyanii zavisit ot uslovij konkret-
noj realizacii i ogranichivaetsya chislom otvedennyh dlya etogo polya razryadov v
zapisi tablicy stranic.
Na Risunke 9.19 pokazano vzaimodejstvie mezhdu processami, rabotayushchimi so
stranicej, i "sborshchikom" stranic. Cifry oboznachayut nomer obrashcheniya "sborshchi-
Ssylka na stranicu
+------------+----------+----------+-----------------+
| ^ ^ ^ |
v | | | | Gotov-
+-------+ | | | | nost'
| Stra- | +-+-+ +-+-+ +-+-+ +-+-+ k
| nica v|----->| 1 +----->| 2 +----->| 3 +-------->| n | vy-
| pamyati| +---+ +---+ +---+ +-+-+ gruz-
+-------+ "Dozrevanie" stranicy --- otsutstvie | ke
^ ssylok |
| |
| +--------+ |
| | Strani-| |
Za- +-----------------------| ca vy- |<------------------+ Vygruz-
gruzka | gruzhena| ka
+--------+
Risunok 9.18. Diagramma sostoyanij stranicy
274
ka" k stranice s togo momenta, kak strani-
ca byla zagruzhena v pamyat'. Process, obrativshijsya k stranice posle vtorogo
prosmotra stranic "sborshchikom", sbrosil ee "vozrast" v 0. Posle kazhdogo pros-
motra pol'zovatel'skij process obrashchalsya k stranice vnov', no v konce koncov
"sborshchik" stranic osushchestvil tri prosmotra stranicy s momenta poslednego ob-
rashcheniya k nej so storony pol'zovatel'skogo processa i vygruzil ee iz pamyati.
Esli oblast' ispol'zuetsya sovmestno ne menee, chem dvumya processami, vse
oni rabotayut s bitami upominaniya v odnom i tom zhe nabore zapisej tablicy
stranic. Takim obrazom, stranicy mogut vklyuchat'sya v rabochie mnozhestva nes-
kol'kih processov, no dlya "sborshchika" stranic eto ne imeet nikakogo znacheniya.
Esli stranica vklyuchena v rabochee mnozhestvo hotya by odnogo iz processov, ona
ostaetsya v pamyati; v protivnom sluchae ona mozhet byt' vygruzhena. Nichego, chto
odna oblast', k primeru, imeet v pamyati stranic bol'she, chem imeyut drugie:
"sborshchik" stranic ne pytaetsya vygruzit' ravnoe kolichestvo stranic iz vseh
aktivnyh oblastej.
YAdro vozobnovlyaet rabotu "sborshchika" stranic, kogda dostupnaya v sisteme
svobodnaya pamyat' imeet razmer, ne dotyagivayushchij do nizhnej dopustimoj otmetki,
i togda "sborshchik" proizvodit otkachku stranic do teh por, poka ob®em svobod-
noj pamyati ne prevysit verhnyuyu otmetku. Pri ispol'zovanii dvuh otmetok koli-
chestvo proizvodimyh operacij sokrashchaetsya, ibo esli yadro ispol'zuet tol'ko
odno porogovoe znachenie, ono budet vygruzhat' dostatochnoe chislo stranic dlya
osvobozhdeniya pamyati svyshe porogovogo znacheniya, no v rezul'tate vozvrashcheniya
oshibochno vygruzhennyh stranic v pamyat' razmer svobodnogo prostranstva vskore
vnov' opustitsya nizhe etogo poroga. Ob®em svobodnoj pamyati pri etom postoyanno
by podderzhivalsya okolo porogovoj otmetki. Vygruzka stranic s osvobozhdeniem
pamyati v ob®eme, prevyshayushchem verhnyuyu otmetku, otkladyvaet moment, kogda ob®-
em svobodnoj pamyati v sisteme stanet men'she nizhnej otmetki, poetomu "sborshchi-
ku" stranic ne prihoditsya uzhe tak chasto vypolnyat' svoyu rabotu. Optimal'nyj
vybor urovnej verhnej i nizhnej otmetok administratorom povyshaet proizvodi-
tel'nost' sistemy.
Kogda "sborshchik" stranic prinimaet reshenie vygruzit' stranicu iz pamyati,
on proveryaet vozmozhnost' nahozhdeniya kopii etoj stranicy na ustrojstve vyg-
ruzki. Pri etom mogut imet' mesto tri sluchaya:
Sostoyanie stranicy Vremya (poslednego upominaniya)
+----------------------+-----------+
| V pamyati | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+
| | 2 |
+----------------------+-----------+ Ssylka na stranicu
| | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+ Ssylka na stranicu
| | 0 |
+----------------------+-----------+
| | 1 |
+----------------------+-----------+
| | 2 |
+----------------------+-----------+
| | 3 |
+----------------------+-----------+ Stranica vygruzhena
| Vne pamyati | |
+----------------------+-----------+
Risunok 9.19. Primer "sozrevaniya" stranicy
275
1. Esli na ustrojstve vygruzki est' kopiya stranicy, yadro "planiruet" vyg-
ruzku stranicy: "sborshchik" stranic pomeshchaet ee v spisok vygruzhennyh stra-
nic i perehodit dal'she; vygruzka schitaetsya logicheski zavershivshejsya. Kog-
da chislo stranic v spiske prevysit ogranichenie (opredelyaemoe vozmozhnos-
tyami diskovogo kontrollera), yadro perepisyvaet stranicy na ustrojstvo
vygruzki.
2. Esli na ustrojstve vygruzki uzhe est' kopiya stranicy i ee soderzhimoe ni-
chem ne otlichaetsya ot soderzhimogo stranicy v pamyati (bit modifikacii v
zapisi tablicy stranic ne ustanovlen), yadro sbrasyvaet v nol' bit dos-
tupnosti (v toj zhe zapisi tablicy), umen'shaet znachenie schetchika ssylok v
tablice pfdata i pomeshchaet zapis' v spisok svobodnyh stranic dlya budushchego
perenaznacheniya.
3. Esli na ustrojstve vygruzki est' kopiya stranicy, no process izmenil so-
derzhimoe ee originala v pamyati, yadro planiruet vygruzku stranicy i osvo-
bozhdaet zanimaemoe ee kopiej mesto na ustrojstve vygruzki.
"Sborshchik" stranic kopiruet stranicu na ustrojstvo vygruzki, esli imeyut
mesto sluchai 1 i 3.
CHtoby proillyustrirovat' razlichiya mezhdu poslednimi dvumya sluchayami, pred-
polozhim, chto stranica nahoditsya na ustrojstve vygruzki i zagruzhaetsya v os-
novnuyu pamyat' posle togo, kak process stolknulsya s otsutstviem neobhodimyh
dannyh. Dopustim, yadro ne stalo avtomaticheski udalyat' kopiyu stranicy na dis-
ke. V konce koncov, "sborshchik" stranic vnov' primet reshenie vygruzit' strani-
cu. Esli s momenta zagruzki v pamyat' v stranicu ne proizvodilas' zapis' dan-
nyh, soderzhimoe stranicy v pamyati identichno soderzhimomu ee diskovoj kopii i
v perepisi stranicy na ustrojstvo vygruzki neobhodimosti ne voznikaet. Odna-
ko, esli process uspel chto-to zapisat' na stranicu, staryj i novyj ee vari-
anty budut razlichat'sya, poetomu yadru sleduet perepisat' stranicu na ustrojs-
tvo vygruzki, osvobodiv predvaritel'no mesto, zanimaemoe na ustrojstve sta-
rym variantom. YAdro ne srazu ispol'zuet osvobozhdennoe prostranstvo na ust-
rojstve vygruzki, poetomu ono imeet vozmozhnost' podderzhivat' nepreryvnoe
razmeshchenie zanyatyh uchastkov, chto povyshaet effektivnost' ispol'zovaniya oblas-
ti vygruzki.
"Sborshchik" stranic zapolnyaet spisok vygruzhennyh stranic, kotorye v prin-
cipe mogut prinadlezhat' raznym oblastyam, i po zapolnenii spiska otkachivaet
ih na ustrojstvo vygruzki. Net neobhodimosti v tom, chtoby vse stranicy odno-
go processa nepremenno vygruzhalis': k primeru, nekotorye iz stranic, vozmozh-
no, nedostatochno "sozreli" dlya etogo. V etom viditsya razlichie so strategiej
vygruzki processov, soglasno kotoroj iz pamyati vygruzhayutsya vse stranicy od-
nogo processa, vmeste s tem metod perepisi dannyh na ustrojstvo vygruzki
identichen tomu metodu, kotoryj opisan dlya sistemy s zameshcheniem processov v
razdele 9.1.2. Esli na ustrojstve vygruzki nedostatochno nepreryvnogo prost-
ranstva, yadro vygruzhaet stranicy po otdel'nosti (po odnoj stranice za opera-
ciyu), chto v konechnom itoge obhoditsya nedeshevo. V sisteme s zameshcheniem stra-
nic fragmentaciya na ustrojstve vygruzki vyshe, chem v sisteme s zameshcheniem
processov, poskol'ku yadro vygruzhaet bloki stranic, no zagruzhaet v pamyat'
kazhduyu stranicu v otdel'nosti.
Kogda yadro perepisyvaet stranicu na ustrojstvo vygruzki, ono sbrasyvaet
bit dostupnosti v sootvetstvuyushchej zapisi tablicy stranic i umen'shaet znache-
nie schetchika ssylok v sootvetstvuyushchej zapisi tablicy pfdata. Esli znachenie
schetchika stanovitsya ravnym 0, zapis' tablicy pfdata pomeshchaetsya v konec spis-
ka svobodnyh stranic i zapominaetsya dlya posleduyushchego perenaznacheniya. Esli
znachenie schetchika otlichno ot 0, eto oznachaet, chto stranica (v rezul'tate vy-
polneniya funkcii fork) ispol'zuetsya sovmestno neskol'kimi processami, no yad-
ro vse ravno vygruzhaet ee. Nakonec, yadro vydelyaet prostranstvo na ustrojstve
vygruzki, sohranyaet ego adres v deskriptore diskovogo bloka i uvelichivaet
znachenie schetchika ssylok na stranicu v tablice ispol'zovaniya oblasti podkach-
ki. Esli v to vremya, poka stranica nahoditsya v spiske svobodnyh stranic,
process obnaruzhil ee otsutstvie, poluchiv sootvetstvuyushchuyu oshibku, yadro mozhet
276
vosstanovit' ee v pamyati, ne obrashchayas' k ustrojstvu vygruzki. Odnako, stra-
nica vse ravno budet schitat'sya vygruzhennoj, esli ona popala v spisok "sbor-
shchika" stranic.
Predpolozhim, k primeru, chto "sborshchik" stranic vygruzhaet 30, 40, 50 i 20
stranic iz processov A, B, C i D, sootvetstvenno, i chto za odnu operaciyu
vygruzki na diskovoe ustrojstvo otkachivayutsya 64 stranicy. Na Risunke 9.20
pokazana posledovatel'nost' imeyushchih pri etom mesto operacij vygruzki pri us-
lovii, chto "sborshchik" stranic osushchestvlyaet prosmotr stranic processov v oche-
rednosti: A, B, C, D. "Sborshchik" vydelyaet na ustrojstve vygruzki mesto dlya 64
stranic i vygruzhaet 30 stranic processa A i 34 stranicy processa B. Zatem on
vydelyaet mesto dlya sleduyushchih 64 stranic i vygruzhaet ostavshiesya 6 stranic
processa B, 50 stranic processa C i 8 stranic processa D. Vydelennye dlya
razmeshcheniya stranic za dve operacii uchastki oblasti vygruzki mogut byt' i
nesmezhnymi. "Sborshchik" sohranyaet ostavshiesya 12 stranic processa D v spiske
vygruzhaemyh stranic, no ne vygruzhaet ih do teh por, poka spisok ne budet za-
polnen do konca. Kak tol'ko u processov voznikaet potrebnost' v podkachke
stranic s ustrojstva vygruzki ili esli stranicy bol'she ne nuzhny ispol'zuyushchim
ih processam (processy zavershilis'), v oblasti vygruzki osvobozhdaetsya mesto.
CHtoby podvesti itog, vydelim v processe otkachki stranicy iz pamyati dve
fazy. Na pervoj faze "sborshchik" stranic ishchet stranicy, podhodyashchie dlya vygruz-
ki, i pomeshchaet ih nomera v spisok vygruzhaemyh stranic. Na vtoroj faze yadro
kopiruet stranicu na ustrojstvo vygruzki (esli na nem imeetsya mesto), sbra-
syvaet v nol' bit dopustimosti v sootvetstvuyushchej zapisi tablicy stranic,
umen'shaet znachenie schetchika ssylok v sootvetstvuyushchej zapisi tablicy pfdata
Stranicy vygruzhayutsya gruppami po 64 stranicy
+--------------------+ +-------------------+ +-------------------+
|Process A 30 str-c | |Process B 6 str-c | |Process D 12 str-c |
| | | | | - |
|Process B 34 str-cy| |Process C 50 str-c| | - |
+--------------------+ | | | - |
- - |Process D 8 str-c | +-------------------+
- -+-------------------+
- - - -
- - - -
- - - -
- - - -
- - - -
+-------+-------------------+-------+-----------------+----------+
| | A 30 B 34 | | B 6 C 50 D 8 | |
+-------+-------------------+-------+-----------------+----------+
Ustrojstvo vygruzki
Risunok 9.20. Vydelenie prostranstva na ustrojstve vygruzki v
sisteme s zameshcheniem stranic
i esli ono stanovitsya ravnym 0, pomeshchaet etu zapis' v konec spiska svobodnyh
stranic. Soderzhimoe fizicheskoj stranicy v pamyati ne izmenyaetsya do teh por,
poka stranica ne budet perenaznachena drugomu processu.
9.2.3 Otkazy pri obrashcheniyah k stranicam
V sisteme vstrechayutsya dva tipa otkazov pri obrashchenii k stranice: otkazy
iz-za otsutstviya (nedostupnosti) dannyh i otkazy sistemy zashchity. Poskol'ku
programmy obrabotki preryvanij po otkazu mogut priostanavlivat' svoe vypol-
nenie na vremya schityvaniya stranicy s diska v pamyat', eti programmy yavlyayutsya
isklyucheniem iz obshchego pravila, utverzhdayushchego nevozmozhnost' priostanova obra-
botchikov preryvanij. Tem ne menee, poskol'ku programma obrabotki preryvanij
277
po otkazu priostanavlivaetsya v kontekste processa, porodivshego fatal'nuyu
oshibku pamyati, otkaz otnositsya k tekushchemu processu; sledovatel'no, processy
priostanavlivayutsya ne proizvol'nym obrazom.
9.2.3.1 Obrabotka preryvanij po otkazu iz-za nedostupnosti dannyh
Esli process pytaetsya obratit'sya k stranice, bit dostupnosti dlya kotoroj
ne ustanovlen, on poluchaet otkaz iz-za otsutstviya (nedostupnosti) dannyh i
yadro zapuskaet programmu obrabotki preryvanij po otkazu dannogo tipa (Risu-
nok 9.21). Bit dostupnosti ne ustanavlivaetsya ni dlya teh stranic, kotorye
raspolagayutsya za predelami virtual'nogo adresnogo prostranstva processa, ni
dlya teh, kotorye vhodyat v sostav etogo prostranstva, no ne imeyut v nastoyashchij
moment fizicheskogo analoga v pamyati. Fatal'naya oshibka pamyati proizoshla v re-
zul'tate obrashcheniya yadra po virtual'nomu adresu stranicy, poetomu yadro vyho-
dit na sootvetstvuyushchuyu etoj stranice zapis' v tablice stranic i deskriptor
diskovogo bloka. CHtoby predotvratit' vzaimnuyu blokirovku, kotoraya mozhet pro-
izojti, esli "sborshchik" popytaetsya vygruzit' stranicu iz pamyati, yadro fiksi-
ruet v pamyati oblast' s sootvetstvuyushchej zapis'yu tablicy stranic. Esli v des-
kriptore diskovogo bloka otsutstvuet informaciya o stranice,
sdelannaya ssylka na stranicu yavlyaetsya nedopustimoj i yadro posylaet proces-
su-narushitelyu signal o "narushenii segmentacii" (sm. Risunok 7.25). Takoj po-
ryadok dejstvij sovpadaet s tem poryadkom, kotorogo priderzhivaetsya yadro, kogda
process obratilsya po nevernomu adresu, esli ne prinimat' vo vnimanie to obs-
toyatel'stvo, chto yadro uznaet ob oshibke nemedlenno, tak kak vse "dostupnye"
stranicy yavlyayutsya rezidentnymi v pamyati. Esli ssylka na stranicu sdelana
pravil'no, yadro vydelyaet fizicheskuyu stranicu v pamyati i schityvaet v nee so-
derzhimoe virtual'noj stranicy s ustrojstva vygruzki ili iz ispolnyaemogo faj-
la.
Stranica, vyzvavshaya otkaz, nahoditsya v odnom iz pyati sostoyanij:
1. Na ustrojstve vygruzki vne pamyati.
2. V spiske svobodnyh stranic v pamyati.
3. V ispolnyaemom fajle.
4. S pometkoj "obnulyaemaya pri obrashchenii".
5. S pometkoj "zapolnyaemaya pri obrashchenii".
Rassmotrim kazhdyj sluchaj v podrobnostyah.
Esli stranica nahoditsya na ustrojstve vygruzki, vne pamyati (sluchaj 1),
eto oznachaet, chto ona kogda-to raspolagalas' v pamyati, no byla vygruzhena ot-
tuda "sborshchikom" stranic. Obrativshis' k deskriptoru diskovogo bloka, yadro
uznaet iz nego nomera ustrojstva vygruzki i bloka, gde raspolozhena stranica,
i proveryaet, ne ostalas' li stranica v keshe. YAdro korrektiruet zapis' tabli-
cy stranic tak, chtoby ona ukazyvala na stranicu, kotoruyu predpolagaetsya schi-
tat' v pamyat', vklyuchaet sootvetstvuyushchuyu zapis' tablicy pfdata v hesh-ochered'
(oblegchaya posleduyushchuyu obrabotku otkaza) i schityvaet stranicu s ustrojstva
vygruzki. Dopustivshij oshibku process priostanavlivaetsya do momenta zavershe-
niya vvoda-vyvoda; vmeste s nim budut vozobnovleny vse processy, ozhidavshie
zagruzki soderzhimogo stranicy.
Obratimsya k Risunku 9.22 i v kachestve primera rassmotrim zapis' tablicy
stranic, svyazannuyu s virtual'nym adresom 66K. Esli pri obrashchenii k stranice
process poluchaet otkaz iz-za nedostupnosti dannyh, programma obrabotki otka-
za obrashchaetsya k deskriptoru diskovogo bloka i obnaruzhivaet to, chto stranica
nahoditsya na ustrojstve vygruzki v bloke s nomerom 847 (esli predpolozhit',
chto v sisteme tol'ko odno ustrojstvo vygruzki): sledovatel'no, virtual'nyj
adres ukazan verno. Zatem programma obrabotki otkaza obrashchaetsya k keshu, no
ne nahodit informacii o diskovom bloke s nomerom 847. Takim obrazom, kopiya
virtual'noj stranicy v pamyati otsutstvuet i programma obrabotki otkaza dolzh-
na zagruzit' ee s ustrojstva vygruzki. YAdro otvodit fizicheskuyu stranicu s
nomerom 1776 (Risunok 9.23), schityvaet v nee s ustrojstva vygruzki soderzhi-
moe virtual'noj stranicy i perenastraivaet zapis' tablicy stranic na strani-
cu s nomerom 1776. V zavershenie yadro korrektiruet deskriptor diskovogo blo-
278
+------------------------------------------------------------+
| algoritm vfault /* obrabotka otkaza iz-za otsutstviya |
| (nedostupnosti) dannyh */ |
| vhodnaya informaciya: adres, po kotoromu poluchen otkaz |
| vyhodnaya informaciya: otsutstvuet |
| { |
| najti oblast', zapis' v tablice stranic, deskriptor dis-|
| kovogo bloka, svyazannye s adresom, po kotoromu poluchen |
| otkaz, zablokirovat' oblast'; |
| esli (adres ne prinadlezhit virtual'nomu adresnomu prost-|
| ranstvu processa) |
| { |
| poslat' signal (SIGSEGV: narushenie segmentacii) pro- |
| cessu; |
| perejti na out; |
| } |
| esli (adres ukazan neverno) /* vozmozhno, process naho-|
| dilsya v sostoyanii pri- |
| ostanova */ |
| perejti na out; |
| esli (stranica imeetsya v keshe) |
| { |
| ubrat' stranicu iz kesha; |
| popravit' zapis' v tablice stranic; |
| vypolnyat' poka (soderzhimoe stranicy ne stanet dostup-|
| nym) /* drugoj process poluchil takoj zhe otkaz, |
| * no ran'she */ |
| priostanovit'sya; |
| } |
| v protivnom sluchae /* stranica otsutstvuet v keshe */|
| { |
| naznachit' oblasti novuyu stranicu; |
| |
| pomestit' novuyu stranicu v kesh, otkorrektirovat' za- |
| pis' v tablice pfdata; |
| esli (stranica ranee ne zagruzhalas' v pamyat' i imeet |
| pometku "obnulyaemaya pri obrashchenii") |
| ochistit' soderzhimoe stranicy; |
| v protivnom sluchae |
| { |
| schitat' virtual'nuyu stranicu s ustrojstva vygruz-|
| ki ili iz ispolnyaemogo fajla; |
| priostanovit'sya (do zaversheniya vvoda-vyvoda); |
| } |
| vozobnovit' processy (ozhidayushchie zagruzki soderzhimogo |
| stranicy); |
| } |
| ustanovit' bit dostupnosti stranicy; |
| sbrosit' bit modifikacii i "vozrast" stranicy; |
| pereschitat' prioritet processa; |
| out: snyat' blokirovku s oblasti; |
| } |
+------------------------------------------------------------+
Risunok 9.21. Algoritm obrabotki otkaza iz-za otsutstviya (ne-
dostupnosti) dannyh
279
ka, delaya ukazanie o tom, chto stranica zagruzhena, a takzhe zapis' tablicy
pfdata, otmechaya, chto na ustrojstve vygruzki v bloke s nomerom 847 soderzhitsya
dublikat virtual'noj stranicy.
Pri obrabotke otkazov iz-za nedostupnosti dannyh yadro ne vsegda pribega-
et k vypolneniyu operacii vvoda-vyvoda, dazhe kogda iz deskriptora diskovogo
bloka vidno, chto stranica zagruzhena (v sluchae 2). Mozhet sluchit'sya tak, chto
yadro posle vygruzki soderzhimogo fizicheskoj stranicy tak i ne pereprisvoilo
ee ili zhe kakoj-to inoj process v rezul'tate otkaza zagruzil soderzhimoe vir-
tual'noj stranicy v druguyu fizicheskuyu stranicu. V lyubom sluchae programma ob-
rabotki otkaza obnaruzhivaet stranicu v keshe, v kachestve klyucha ispol'zuya no-
mer bloka v deskriptore diskovogo bloka. Ona perenastraivaet sootvetstvuyushchuyu
zapis' v tablice stranic na tol'ko chto najdennuyu stranicu, uvelichivaet zna-
chenie schetchika ssylok na stranicu i v sluchae neobhodimosti ubiraet stranicu
iz spiska svobodnyh stranic. Predpolozhim, k primeru, chto process po-
Zapisi Deskriptory
tablicy stranic diskovyh blokov Stranichnye bloki
Fizi-
cheskaya Disko-
Virtual'- stra- Sosto- Sosto- Stra- vyj Schet-
nyj adres nica yanie yanie Blok nica blok chik
+-----+--------+++-------+---------+ +----+------+----+
0 | | ||| | | | | | |
+-----+--------+++-------+---------+ | | | |
1K | 1648| Nedo- |||V fajle| 3 | | | | |
| | stupna ||| | | | | | |
+-----+--------+++-------+---------+ | | | |
2K | | ||| | | | | | |
+-----+--------+++-------+---------+ | | | |
3K | Net | Nedo- |||Zapolnya| 5 | | | | |
| | stupna |||etsya | | | | | |
| | |||pri ob-| | | | | |
| | |||rashchenii| | | | | |
+-----+--------+++-------+---------+ +----+------+----+
4K | | ||| | | |1036| 387 | 0 |
+-----+--------+++-------+---------+ +----+------+----+
- | | ||| | | | - | | |
- | | ||| | | | - | | |
- | | ||| | | +----+------+----+
- | | ||| | | |1648| 1618 | 1 |
+-----+--------+++-------+---------+ +----+------+----+
64K | 1917| Nedo- |||Na dis-| 1206 | | - | | |
| | stupna |||ke | | | - | | |
+-----+--------+++-------+---------+ | - | | |
65K | Net | Nedo- |||Obnulya-| | | - | | |
| | stupna |||etsya | | | - | | |
| | |||pri ob-| | | - | | |
| | |||rashchenii| | | - | | |
+-----+--------+++-------+---------+ +----+------+----+
66K | 1036| Nedo- |||Na dis-| 847 | |1861| 1206 | 0 |
| | stupna |||ke | | +----+------+----+
+-----+--------+++-------+---------+ | | | |
67K | | ||| | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Risunok 9.22. Illyustraciya k otkazu iz-za nedostupnosti dannyh
280
luchil otkaz pri obrashchenii k virtual'nomu adresu 64K (Risunok 9.22). Prosmat-
rivaya kesh, yadro ustanavlivaet, chto stranichnyj blok s nomerom 1861 svyazan s
diskovym blokom 1206. YAdro perenastraivaet zapis' tablicy stranic s virtu-
al'nym adresom 64K na stranicu s nomerom 1861, ustanavlivaet bit dostupnosti
i peredaet upravlenie programme obrabotki otkaza. Takim obrazom, nomer dis-
kovogo bloka svyazyvaet vmeste zapisi tablicy stranic i tablicy pfdata, chem i
ob®yasnyaetsya ego zapominanie v obeih tablicah.
Kak i yadru, programme obrabotki otkaza ne nuzhno schityvat' stranicu v pa-
myat', esli kakoj-to inoj process uzhe poluchil otkaz po toj zhe samoj stranice,
no eshche ne polnost'yu zagruzil ee. Programma nahodit oblast' s zapis'yu tablicy
Zapisi Deskriptory
tablicy stranic diskovyh blokov Stranichnye bloki
Fizi-
cheskaya Disko-
Virtual'- stra- Sosto- Sosto- Stra- vyj Schet-
nyj adres nica yanie yanie Blok nica blok chik
+-----+--------+++-------+---------+ +----+------+----+
66K | 1776| Dostup-|||Na dis-| 847 | |1776| 847 | 1 |
| | na |||ke | | | | | |
+-----+--------+++-------+---------+ +----+------+----+
Risunok 9.23. Rezul'tat zagruzki stranicy v pamyat'
Process A Process B
+------------------------------------------------------------
| Otkaz pri obrashchenii k stra- - -
| nice - -
| Virtual'nyj adres stranicy - -
| veren - -
| Priostanov do zaversheniya - -
| schityvaniya stranicy - -
| - - Otkaz pri obrashchenii k stra-
| - - nice
| - - Virtual'nyj adres stranicy
| - - veren
| - - Zagruzka stranicy v pamyat'
| - - Priostanov do okonchaniya
| - - zagruzki
| - - -
| Vyhod iz priostanova -- - -
| stranica v pamyati - -
| Stranica pomechaetsya kak - -
| dostupnaya - -
| Vyhod iz priostanova drugih - -
| processov - -
| - Vyhod iz priostanova
| Vozobnovlenie vypolneniya - -
| - - -
| - - Vozobnovlenie vypolneniya
| - - -
| - - -
| Vremya -
v
Risunok 9.24. Dva otkaza na odnoj stranice
281
stranic, kotoruyu ona uzhe ranee zablokirovala. Ona dozhidaetsya, poka budet za-
konchen cikl obrabotki predydushchego otkaza, posle chego obnaruzhivaet, chto stra-
nica stala dostupnoj, i zavershaet svoyu rabotu. |ta procedura proslezhivaetsya
na Risunke 9.24.
Esli kopiya stranicy nahoditsya ne na ustrojstve vygruzki, a v ispolnyaemom
fajle (sluchaj 3), yadro zagruzhaet stranicu iz fajla. Programma obrabotki ot-
kaza obrashchaetsya k deskriptoru diskovogo bloka, ishchet sootvetstvuyushchij nomer
logicheskogo bloka vnutri fajla, soderzhashchego stranicu, i indeks, associiro-
vannyj s zapis'yu tablicy oblastej. Nomer logicheskogo bloka ispol'zuetsya
programmoj v kachestve smeshcheniya vnutri spiska nomerov diskovyh blokov, priso-
edinennogo k indeksu vo vremya vypolneniya funkcii exec. Po nomeru bloka na
diske programma schityvaet stranicu v pamyat'. Tak, naprimer, deskriptor dis-
kovogo bloka, svyazannyj s virtual'nym adresom 1K, pokazyvaet, chto soderzhimoe
stranicy raspolagaetsya v ispolnyaemom fajle, vnutri logicheskogo bloka s nome-
rom 3 (sm. Risunok 9.22).
Esli process poluchil otkaz pri obrashchenii k stranice, imeyushchej pometku
"zapolnyaemaya pri obrashchenii" ili "obnulyaemaya pri obrashchenii" (sluchai 4 i 5),
yadro vydelyaet svobodnuyu stranicu v pamyati i korrektiruet sootvetstvuyushchuyu za-
pis' tablicy stranic. Esli stranica "obnulyaemaya pri obrashchenii", yadro takzhe
ochishchaet ee soderzhimoe. V zavershenie obrabotki flagi "zapolnyaemaya pri obrashche-
nii" i "obnulyaemaya pri obrashchenii" sbrasyvayutsya. Teper' stranica nahoditsya v
pamyati, dostupna processam i ee soderzhimoe ne imeet analogov ni na ustrojst-
ve vygruzki, ni v fajlovoj sisteme. Tak proishodit, esli process obrashchaetsya
k stranicam s virtual'nymi adresami 3K i 65K (sm. Risunok 9.22): ni odin iz
processov ne obrashchalsya k etim stranicam s teh por, kak fajl byl zapushchen na
vypolnenie funkciej exec.
V zavershenie svoej raboty programma obrabotki otkazov iz-za otsutstviya
(nedostupnosti) dannyh ustanavlivaet bit dostupnosti stranicy i sbrasyvaet
bit modifikacii. Prioritet processa pri etom pereschityvaetsya, ibo vo vremya
vypolneniya programmy process mog priostanovit' svoe vypolnenie na urovne yad-
ra, poluchaya tem samym po vozvrashchenii v rezhim zadachi nezasluzhennoe preimushches-
tvo pered drugimi processami. I, nakonec, vozvrashchayas' v rezhim zadachi, prog-
ramma proveryaet, ne bylo li za vremya obrabotki otkaza postupleniya kakih-libo
signalov.
9.2.3.2 Obrabotka preryvanij po otkazu sistemy zashchity
Vtorym tipom otkaza, vstrechayushchegosya pri obrashchenii k stranice, yavlyaetsya
otkaz sistemy zashchity, kotoryj oznachaet, chto process obratilsya k sushchestvuyushchej
stranice pamyati, no sudya po razryadam, opisyvayushchim prava dostupa k stranice,
dostup k nej so storony tekushchego processa ne razreshen. (Vspomnim primer,
opisyvayushchij popytku processa proizvesti zapis' dannyh v oblast' komand; sm.
Risunok 7.22). Otkaz dannogo tipa imeet mesto takzhe togda, kogda process
predprinimaet popytku zapisat' chto-to na stranicu, dlya kotoroj vo vremya vy-
polneniya sistemnoj funkcii fork byl ustanovlen bit kopirovaniya pri zapisi.
YAdro dolzhno razlichat' mezhdu soboj situacii, kogda otkaz proizoshel po prichine
togo, chto stranica trebuet kopirovaniya pri zapisi, i kogda imelo mesto dejs-
tvitel'no chto-to nedopustimoe.
Programma obrabotki otkaza sistemy zashchity avtomaticheski poluchaet virtu-
al'nyj adres, po kotoromu proizoshel otkaz, i vedet poisk sootvetstvuyushchej ob-
lasti i zapisi tablicy stranic (Risunok 9.25). Ona blokiruet oblast', chtoby
"sborshchik" stranic ne mog vygruzit' stranicu, poka svyazannyj s nej otkaz ne
budet obrabotan. Esli programma obrabotki otkaza ustanavlivaet, chto prichinoj
otkaza posluzhila ustanovka bita kopirovaniya pri zapisi, i esli stranicu is-
pol'zuyut srazu neskol'ko processov, yadro vydelyaet v pamyati novuyu stranicu i
kopiruet v nee soderzhimoe staroj stranicy; ssylki drugih processov na staruyu
282
stranicu sohranyayut svoe znachenie. Posle kopirovaniya i vneseniya v zapis' tab-
licy stranic novogo nomera stranicy yadro umen'shaet znachenie schetchika ssylok
v zapisi tablicy pfdata, sootvetstvuyushchej staroj stranice. Vsya procedura po-
kazana na Risunke 9.26, gde tri processa sovmestno ispol'zuyut fizicheskuyu
stranicu s nomerom 828. Process B schityvaet stranicu, no poskol'ku bit kopi-
rovaniya pri zapisi ustanovlen, poluchaet otkaz sistemy zashchity. Programma ob-
rabotki otkaza vydelyaet stranicu s nomerom 786, kopiruet v nee soderzhimoe
stranicy 828, umen'shaet znachenie schetchika ssylok na skopirovannuyu stranicu i
perenastraivaet sootvetstvuyushchuyu zapis' tablicy stranic na stranicu s nomerom
786.
Esli bit kopirovaniya pri zapisi ustanovlen, no stranica ispol'zuetsya
tol'ko odnim processom, yadro daet processu vozmozhnost' vospol'zovat'sya fizi-
cheskoj stranicej povtorno. Ono otklyuchaet bit kopirovaniya pri zapisi i razry-
vaet svyaz' stranicy s ee kopiej na diske (esli takovaya sushchestvuet), poskol'-
ku ne isklyuchena vozmozhnost' togo, chto diskovoj kopiej pol'zuyutsya drugie pro-
cessy. Zatem yadro ubiraet zapis' tablicy pfdata iz ocheredi stranic, ibo no-
vaya
+------------------------------------------------------------+
| algoritm pfault /* obrabotka otkaza sistemy zashchity */ |
| vhodnaya informaciya: adres, po kotoromu poluchen otkaz |
| vyhodnaya informaciya: otsutstvuet |
| { |
| najti oblast', zapis' v tablice stranic, deskriptor dis-|
| kovogo bloka, svyazannye s adresom, po kotoromu poluchen |
| otkaz, zablokirovat' oblast'; |
| esli (stranica nedostupna v pamyati) |
| perejti na out; |
| esli (bit kopirovaniya pri zapisi ne ustanovlen) |
| perejti na out; /* programmnaya oshibka - signal */|
| esli (schetchik ssylok na stranichnyj blok > 1) |
| { |
| vydelit' novuyu fizicheskuyu stranicu; |
| skopirovat' v nee soderzhimoe staroj stranicy; |
| umen'shit' znachenie schetchika ssylok na staryj stra- |
| nichnyj blok; |
| perenastroit' zapis' tablicy stranic na novuyu fizi- |
| cheskuyu stranicu; |
| } |
| v protivnom sluchae /* ubrat' stranicu, poskol'ku ona |
| * nikem bol'she ne ispol'zuetsya */ |
| { |
| esli (kopiya stranicy imeetsya na ustrojstve vygruzki)|
| osvobodit' mesto na ustrojstve, razorvat' svyaz'|
| so stranicej; |
| esli (stranica nahoditsya v hesh-ocheredi stranic) |
| ubrat' stranicu iz hesh-ocheredi; |
| } |
| v zapisi tablicy stranic ustanovit' bit modifikacii, |
| sbrosit' bit kopirovaniya pri zapisi; |
| pereschitat' prioritet processa; |
| proverit', ne postupali li signaly; |
| out: snyat' blokirovku s oblasti; |
| } |
+------------------------------------------------------------+
Risunok 9.25. Algoritm obrabotki otkaza sistemy zashchity
283
kopiya virtual'noj stranicy raspolagaetsya ne na ustrojstve vygruzki. Krome
togo, yadro umen'shaet znachenie schetchika ssylok na stranicu v tablice ispol'-
zovaniya oblasti podkachki, i esli eto znachenie stanovitsya ravnym 0, osvobozh-
daet mesto na ustrojstve (sm. uprazhnenie 9.11).
Esli zapis' v tablice stranic ukazyvaet na to, chto stranica nedostupna,
i ee bit kopirovaniya pri zapisi ustanovlen, vystupaya povodom dlya otkaza sis-
temy zashchity, dopustim, chto sistema pri obrashchenii k stranice snachala obraba-
tyvaet otkaz iz-za nedostupnosti dannyh (obratnaya ocherednost' rassmatrivaet-
sya v uprazhnenii 9.17). Nesmotrya na eto, programma obrabotki otkaza sistemy
zashchity vse ravno obyazana ubedit'sya v dostupnosti stranicy, poskol'ku pri us-
tanovke blokirovki na oblast' programma mozhet priostanovit'sya, a "sborshchik"
stranic tem vremenem mozhet vygruzit' stranicu iz pamyati. Esli stranica ne-
dostupna (bit dostupnosti sbroshen), programma nemedlenno zavershit rabotu i
process poluchit otkaz iz-za nedostupnosti dannyh. YAdro obrabotaet etot ot-
kaz, no process vnov' poluchit otkaz sistemy zashchity. Bolee chem veroyatno, chto
zaklyuchitel'nyj otkaz sistemy zashchity budet obrabotan bez kakih-libo prepyatst-
vij i pomeh, poskol'ku projdet dovol'no znachitel'nyj period vremeni, prezhde
chem stranica dostatochno "sozreet" dlya vygruzki iz pamyati. Opisannaya posledo-
vatel'nost' sobytij pokazana na Risunke 9.27.
Zapis' tablicy stranic - Process A
+-----------------------------------------------+
| Stranica 828: dostupna, kopiruetsya pri zapisi +-+
+-----------------------------------------------+ |
|
Zapis' tablicy stranic - Process B | +-----------+
+-----------------------------------------------+ +->| Stranichnyj|
| Stranica 828: dostupna, kopiruetsya pri zapisi +--->| blok 828 |
+-----------------------------------------------+ +->| Schetchik |
| | ssylok 3 |
Zapis' tablicy stranic - Process C | +-----------+
+-----------------------------------------------+ |
| Stranica 828: dostupna, kopiruetsya pri zapisi +-+
+-----------------------------------------------+
(a) Pered tem, kak process B poluchil otkaz sistemy zashchity
Zapis' tablicy stranic - Process A
+-----------------------------------------------+ +-----------+
| Stranica 828: dostupna, kopiruetsya pri zapisi +-+ | Stranichnyj|
+-----------------------------------------------+ | | blok 828 |
+->| Schetchik |
Zapis' tablicy stranic - Process B +->| ssylok 2 |
+-----------------------------------------------+ | +-----------+
| Stranica 828: dostupna ++|
+-----------------------------------------------+|| +-----------+
+|->| Stranichnyj|
Zapis' tablicy stranic - Process C | | blok 786 |
+-----------------------------------------------+ | | Schetchik |
| Stranica 828: dostupna, kopiruetsya pri zapisi +-+ | ssylok 1 |
+-----------------------------------------------+ +-----------+
(b) Posle zapuska programmy obrabotki otkaza sistemy zashchity
dlya processa B
Risunok 9.26. Otkaz sistemy zashchity iz-za ustanovki bita kopi-
rovaniya pri zapisi
284
Pered zaversheniem programma obrabotki otkaza sistemy zashchity ustanavliva-
et bity modifikacii i zashchity, no sbrasyvaet bit kopirovaniya pri zapisi. Ona
pereschityvaet prioritet processa i proveryaet, ne postupali li za vremya ee
raboty signaly, prednaznachennye processu, v tochnosti povtoryaya to, chto dela-
etsya po zavershenii obrabotki otkaza iz-za nedopustimosti dannyh.
Process, poluchayushchij otkazy pri
obrashchenii k stranice "Sborshchik" stranic
+------------------------------------------------------------
| - -
| - Blokiruet oblast'
| - -
| Otkaz sistemy zashchity -
| Priostanov - oblast' -
| zablokirovana -
| - -
| - Vygruzka stranicy - bit
| - dopustimosti sbroshen
| - -
| - -
| - Vyvodit iz priostanova
| - processy, ozhidayushchie
| - snyatiya s oblasti
| - blokirovki
| Vyhod iz priostanova -
| - -
| - -
| Proverka bita dostup- -
| nosti - sbroshen -
| Vyhod iz programmy obra- -
| botki otkaza sistemy za- -
| shchity -
| - -
| - -
| Otkaz iz-za nedostup- -
| nosti dannyh -
v
Vremya
Risunok 9.27. Vzaimodejstvie otkaza sistemy zashchity i otkaza
iz-za nedostupnosti dannyh
9.2.4 Zameshchenie stranic na menee slozhnoj tehnicheskoj baze
Naibol'shaya dejstvennost' algoritmov zameshcheniya stranic po zaprosu (obra-
shcheniyu) dostigaetsya v tom sluchae, esli bity upominaniya i modifikacii ustanav-
livayutsya apparatnym putem i tem zhe putem vyzyvaetsya otkaz sistemy zashchity pri
popytke zapisi v stranicu, imeyushchuyu priznak "kopirovaniya pri zapisi". Tem ne
menee, ukazannye algoritmy vpolne primenimy dazhe togda, kogda apparatura
raspoznaet tol'ko bit dostupnosti i kod zashchity. Esli bit dostupnosti, usta-
navlivaemyj apparatno, dubliruetsya programmno-ustanavlivaemym bitom, pokazy-
vayushchim, dejstvitel'no li stranica dostupna ili net, yadro moglo by otklyuchit'
apparatno-ustanavlivaemyj bit i proimitirovat' ustanovku ostal'nyh bitov
programmnym putem. Tak, naprimer, v mashine VAX-11 bit upominaniya otsutstvuet
(sm. [Levy 82]). YAdro mozhet otklyuchit' apparatno-ustanavlivaemyj bit dostup-
nosti dlya stranicy i dal'she rabotat' po sleduyushchemu planu. Esli process ssy-
laetsya na stranicu, on poluchaet otkaz, poskol'ku bit dostupnosti sbroshen, i
285
v igru vstupaet programma obrabotki otkaza, issleduyushchaya stranicu. Poskol'ku
"programmnyj" bit dostupnosti ustanovlen, yadro znaet, chto stranica dejstvi-
tel'no dostupna i nahoditsya v pamyati; ono ustanavlivaet "programmnyj" bit
upominaniya i "apparatnyj" bit dostupnosti, no emu eshche predstoit uznat' o
tom, chto na stranicu byla sdelana ssylka. Posleduyushchie ssylki na stranicu uzhe
ne vstretyat otkaz, ibo "apparatnyj" bit dostupnosti ustanovlen. Kogda s nej
budet rabotat' "sborshchik" stranic, on vnov' sbrosit "apparatnyj" bit dostup-
nosti, vyzyvaya tem samym ot-
Apparat- Programm- Programm- Apparat- Programm- Programm-
nyj bit nyj bit nyj bit nyj bit nyj bit nyj bit
dostup- dostup- upomina- dostup- dostup- upomina-
nosti nosti niya nosti nosti niya
+---------+----------+---------+ +---------+----------+---------+
| Net | Da | Net | | Da | Da | Da |
+---------+----------+---------+ +---------+----------+---------+
(a) Do modificirovaniya (b) Posle modificirovaniya
stranicy stranicy
Risunok 9.28. Imitaciya ustanovki "apparatnogo" bita modifika-
cii programmnymi sredstvami
kazy na vse posleduyushchie obrashcheniya k stranice i vozvrashchaya sistemu k nachalu
cikla. |tot sluchaj pokazan na Risunke 9.28.
9.3 SISTEMA SMESHANNOGO TIPA SO SVOPINGOM I PODKACHKOJ PO ZAPROSU
Nesmotrya na to, chto v sistemah s zameshcheniem stranic po zaprosu obrashchenie
s pamyat'yu otlichaetsya bol'shej gibkost'yu po sravneniyu s sistemami podkachki
processov, vozmozhno vozniknovenie situacij, v kotoryh "sborshchik" stranic i
programma obrabotki otkazov iz-za nedostupnosti dannyh nachinayut meshat' drug
drugu iz-za nehvatki pamyati. Esli summa rabochih mnozhestv vseh processov pre-
vyshaet ob®em fizicheskoj pamyati v mashine, programma obrabotki otkazov obychno
priostanavlivaetsya, poskol'ku vydelyat' processam stranicy pamyati dal'she sta-
novitsya nevozmozhnym. "Sborshchik" stranic ne smozhet dostatochno bystro osvobo-
dit' mesto v pamyati, ibo vse stranicy prinadlezhat rabochemu mnozhestvu. Proiz-
voditel'nost' sistemy padaet, poskol'ku yadro tratit slishkom mnogo vremeni na
verhnem urovne, s bezumnoj skorost'yu perestraivaya pamyat'.
YAdro v versii V manipuliruet algoritmami podkachki processov i zameshcheniya
stranic tak, chto problemy sopernichestva perestayut byt' neizbezhnymi. Kogda
yadro ne mozhet vydelit' processu stranicy pamyati, ono vozobnovlyaet rabotu
processa podkachki i perevodit pol'zovatel'skij process v sostoyanie, ekviva-
lentnoe sostoyaniyu "gotovnosti k zapusku, buduchi zarezervirovannym". V etom
sostoyanii odnovremenno mogut nahodit'sya neskol'ko processov. Process podkach-
ki vygruzhaet odin za drugim celye processy, poka ob®em dostupnoj pamyati v
sisteme ne prevysit verhnyuyu otmetku. Na kazhdyj vygruzhennyj process prihodit-
sya odin process, zagruzhennyj v pamyat' iz sostoyaniya "gotovnosti k vypolneniyu,
buduchi zarezervirovannym". YAdro zagruzhaet eti processy ne s pomoshch'yu obychnogo
algoritma podkachki, a putem obrabotki otkazov pri obrashchenii k sootvetstvuyu-
shchim stranicam. Na posleduyushchih iteraciyah processa podkachki pri uslovii nali-
chiya v sisteme dostatochnogo ob®ema svobodnoj pamyati budut obrabotany otkazy,
poluchennye drugimi pol'zovatel'skimi processami. Primenenie takogo metoda
vedet k snizheniyu chastoty vozniknoveniya sistemnyh otkazov i ustraneniyu soper-
nichestva: po ideologii on blizok k metodam, ispol'zuemym v operacionnoj sis-
teme VAX/VMS ([Levy 82]).
286
Prochitannaya glava byla posvyashchena rassmotreniyu algoritmov podkachki pro-
cessov i zameshcheniya stranic, ispol'zuemyh v versii V sistemy UNIX. Algoritm
podkachki processov realizuet peremeshchenie processov celikom mezhdu osnovnoj
pamyat'yu i ustrojstvom vygruzki. YAdro vygruzhaet processy iz pamyati, esli ih
razmer pogloshchaet vsyu svobodnuyu pamyat' v sisteme (v rezul'tate vypolneniya
funkcij fork, exec i sbrk ili v rezul'tate estestvennogo uvelicheniya steka),
ili v tom sluchae, esli trebuetsya osvobodit' pamyat' dlya zagruzki processa.
Zagruzku processov vypolnyaet special'nyj process podkachki (process 0), koto-
ryj zapuskaetsya vsyakij raz, kak na ustrojstve vygruzki poyavlyayutsya processy,
gotovye k vypolneniyu. Process podkachki ne prekrashchaet svoej raboty do teh
por, poka na ustrojstve vygruzki ne ostanetsya ni odnogo takogo processa ili
poka v osnovnoj pamyati ne ostanetsya svobodnogo mesta. V poslednem sluchae
process podkachki pytaetsya vygruzit' chto-nibud' iz osnovnoj pamyati, no v ego
obyazannosti vhodit takzhe slezhenie za soblyudeniem trebovaniya minimal'noj pro-
dolzhitel'nosti prebyvaniya vygruzhaemyh processov v pamyati (v celyah predotvra-
shcheniya holostoj perekachki); po etoj prichine process podkachki ne vsegda dosti-
gaet uspeha v svoej rabote. Vozobnovlenie processa podkachki v sluchae voznik-
noveniya neobhodimosti v nem proizvodit s intervalom v odnu sekundu programma
obrabotki preryvanij po tajmeru.
V sisteme s zameshcheniem stranic po zaprosu processy mogut ispolnyat'sya,
dazhe esli ih virtual'noe adresnoe prostranstvo zagruzheno v pamyat' ne pol-
nost'yu; poetomu virtual'nyj razmer processa mozhet prevyshat' ob®em dostupnoj
fizicheskoj pamyati v sisteme. Kogda yadro ispytyvaet potrebnost' v svobodnyh
stranicah, "sborshchik" stranic prosmatrivaet vse aktivnye stranicy v kazhdoj
oblasti, pomechaya dlya vygruzki te iz nih, kotorye dostatochno "sozreli" dlya
etogo, i v konechnom itoge otkachivaet ih na ustrojstvo vygruzki. Kogda pro-
cess obrashchaetsya k virtual'noj stranice, kotoraya v nastoyashchij moment vygruzhena
iz pamyati, on poluchaet otkaz iz-za nedostupnosti dannyh. YAdro zapuskaet
programmu obrabotki otkaza, kotoraya naznachaet oblasti novuyu fizicheskuyu stra-
nicu pamyati i kopiruet v nee soderzhimoe virtual'noj stranicy.
Povysit' proizvoditel'nost' sistemy pri ispol'zovanii algoritma zameshche-
niya stranic po zaprosu mozhno neskol'kimi sposobami. Vo-pervyh, esli process
vyzyvaet funkciyu fork, yadro ispol'zuet bit kopirovaniya pri zapisi, tem samym
v bol'shinstve sluchaev snimaya neobhodimost' v fizicheskom kopirovanii stranic.
Vo-vtoryh, yadro mozhet zaprosit' soderzhimoe stranicy ispolnyaemogo fajla pryamo
iz fajlovoj sistemy, ustranyaya potrebnost' v vyzove funkcii exec dlya nezamed-
litel'nogo schityvaniya fajla v pamyat'. |to sposobstvuet povysheniyu proizvodi-
tel'nosti, poskol'ku ne isklyuchena vozmozhnost' togo, chto podobnye stranicy
tak nikogda i ne potrebuyutsya processu, i ustranyaet izlishnyuyu holostuyu pere-
kachku, imeyushchuyu mesto v tom sluchae, esli "sborshchik" stranic vygruzhaet eti
stranicy iz pamyati do togo, kak v nih voznikaet potrebnost'.
1. Nabrosajte shemu realizacii algoritma mfree, kotoryj osvobozhdaet prost-
ranstvo pamyati i vozvrashchaet ego tablice svobodnogo prostranstva.
2. V razdele 9.1.2 utverzhdaetsya, chto sistema blokiruet peremeshchaemyj pro-
cess, chtoby drugie processy ne mogli ego trogat' s mesta do momenta
okonchaniya operacii. CHto proizoshlo by, esli by sistema ne delala etogo ?
3. Predpolozhim, chto v adresnom prostranstve processa raspolagayutsya tablicy
ispol'zuemyh processom segmentov i stranic. Kakim obrazom yadro mozhet
vygruzit' eto prostranstvo iz pamyati?
4. Esli stek yadra nahoditsya vnutri adresnogo prostranstva processa, pochemu
process ne mozhet vygruzhat' sebya sam ? Kakoj na Vash vzglyad dolzhna byt'
sistemnaya programma vygruzki processov, kak ona dolzhna zapuskat'sya ?
*5. Predpolozhim, chto yadro pytaetsya vygruzit' process, chtoby osvobodit' mes-
287
to v pamyati dlya drugih processov, zagruzhaemyh s ustrojstva vygruzki.
Esli ni na odnom iz ustrojstv vygruzki dlya dannogo processa net mesta,
process podkachki priostanavlivaet svoyu rabotu do teh por, poka mesto ne
poyavitsya. Vozmozhna li situaciya, pri kotoroj vse processy, nahodyashchiesya v
pamyati, priostanovleny, a vse gotovye k vypolneniyu processy nahodyatsya
na ustrojstve vygruzki ? CHto nuzhno predprinyat' yadru dlya togo, chtoby is-
pravit' eto polozhenie ?
6. Rassmotrite eshche raz primer, privedennyj na Risunke 9.10, pri uslovii,
chto v pamyati est' mesto tol'ko dlya 1 processa.
7. Obratimsya k primeru, privedennomu na Risunke 9.11. Sostav'te podobnyj
primer, v kotorom processu postoyanno trebuetsya dlya raboty central'nyj
processor. Sushchestvuet li kakoj-nibud' sposob snyatiya podobnoj napryazhen-
nosti ?
+----------------------------------+
| main() |
| { |
| f(); |
| g(); |
| } |
| |
| f() |
| { |
| vfork(); |
| } |
| |
| g() |
| { |
| int blast[100],i; |
| for (i = 0; i < 100; i++) |
| blast[i] = i; |
| } |
+----------------------------------+
Risunok 9.29
8. CHto proizojdet v rezul'tate vypolneniya programmy, privedennoj na Risun-
ke 9.29, v sisteme BSD 4.2 ? Kakim budet stek processa-roditelya ?
9. Pochemu posle vypolneniya funkcii fork processa-potomka predpochtitel'nee
zapuskat' vperedi processa-roditelya, esli na razdelyaemyh stranicah bity
kopirovaniya pri zapisi ustanovleny ? Kakim obrazom yadro mozhet zastavit'
potomka zapustit'sya pervym ?
*10. Algoritm obrabotki otkaza iz-za nedostupnosti dannyh, izlozhennyj v tek-
ste, zagruzhaet stranicy poodinochke. Ego effektivnost' mozhno povysit',
esli podgotovit' k zagruzke pomimo stranicy, vyzvavshej otkaz, i vse so-
sednie s nej stranicy. Pererabotajte ishodnyj algoritm s uchetom ukazan-
noj operacii.
11. V algoritmah raboty "sborshchika" stranic i programmy obrabotki otkazov
iz-za nedostupnosti dannyh predpolagaetsya, chto razmer stranicy raven
razmeru diskovogo bloka. CHto nuzhno izmenit' v etih algoritmah dlya togo,
chtoby oni rabotali i v teh sluchayah, kogda ukazannoe ravenstvo ne soblyu-
daetsya ?
*12. Kogda process vyzyvaet funkciyu fork (vetvitsya), znachenie schetchika ssy-
lok na kazhduyu razdelyaemuyu stranicu (v tablice pfdata) uvelichivaetsya.
Predpolozhim, chto "sborshchik" stranic vygruzhaet razdelyaemuyu stranicu na
ustrojstvo vygruzki, i odin iz processov (skazhem, roditel') vposledst-
vii poluchaet otkaz pri obrashchenii k nej. Soderzhimoe virtual'noj stranicy
teper' raspolagaetsya na fizicheskoj stranice. Ob®yasnite, pochemu pro-
cess-potomok vsegda imeet vozmozhnost' poluchit' vernuyu kopiyu stranicy,
288
dazhe posle togo, kak process-roditel' chto-to zapishet na nee. Pochemu,
kogda process-roditel' vedet zapis' na stranicu, on dolzhen nemedlenno
porvat' svyaz' s ee diskovoj kopiej ?
13. CHto sleduet predprinyat' programme obrabotki otkazov v tom sluchae, esli
v sisteme ischerpany stranicy pamyati ?
*14. Sostav'te algoritm vygruzki redko ispol'zuemyh komponent yadra. Kakie iz
komponent nel'zya vygruzhat' i kak ih v takom sluchae sleduet oboznachit' ?
15. Pridumajte algoritm, otslezhivayushchij vydelenie prostranstva na ustrojstve
vygruzki, ispol'zuya vmesto kart pamyati, opisannyh v nastoyashchej glave,
bitovyj massiv. Sravnite effektivnost' oboih metodov.
16. Predpolozhim, chto v mashine net apparatno-ustanavlivaemogo bita dostup-
nosti, no est' kod zashchity, ustanavlivayushchij prava dostupa na chtenie, za-
pis' i "ispolnenie" soderzhimogo stranicy. Smodelirujte rabotu s pomoshch'yu
programmno-ustanavlivaemogo bita dostupnosti.
17. V mashine VAX-11 pered proverkoj nalichiya otkazov iz-za nedostupnosti
dannyh vypolnyaetsya apparatnaya proverka nalichiya otkazov sistemy zashchity.
Kak eto otrazhaetsya na algoritmah obrabotki otkazov ?
18. Sistemnaya funkciya plock daet superpol'zovatelyu vozmozhnost' ustanavli-
vat' i snimat' blokirovku (v pamyati) na oblastyah komand i dannyh vyzy-
vayushchego processa. Process podkachki i "sborshchik" stranic ne mogut vygru-
zhat' zablokirovannye stranicy iz pamyati. Processam, ispol'zuyushchim etu
sistemnuyu funkciyu, ne prihoditsya dozhidat'sya zagruzki stranic, poetomu
im garantirovan bolee bystryj otvet po sravneniyu s drugimi processami.
Sleduet li imet' takzhe vozmozhnost' blokirovki v pamyati i oblasti steka
? CHto proizojdet v tom sluchae, esli summarnyj ob®em zablokirovannyh ob-
lastej prevysit razmer dostupnoj pamyati v mashine ?
19. CHto delaet programma, privedennaya na Risunke 9.30 ? Podumajte nad al'-
ternativnoj strategiej zameshcheniya stranic, v sootvetstvii s kotoroj v
rabochee mnozhestvo kazhdogo processa vklyuchaetsya maksimal'no-vozmozhnoe
chislo stranic.
+------------------------------------------------------------+
| struct fourmeg |
| { |
| int page[512]; /* pust' int zanimaet 4 bajta */ |
| } fourmeg[2048]; |
| |
| main() |
| { for (;;) |
| { |
| switch(fork()) |
| { |
| case -1: /* process-roditel' ne mozhet vypolnit' |
| * fork --- slishkom mnogo potomkov */ |
| case 0: /* potomok */ |
| func(); |
| default: |
| continue; |
| } } } |
| |
| func() |
| { int i; |
| |
| for (;;) |
| { |
| printf("process %d povtoryaet cikl\n",getpid()); |
| for (i = 0; i < 2048; i++) |
| fourmeg[i]290ge[0] = i; |
| } } |
+------------------------------------------------------------+
289
Last-modified: Thu, 12 Feb 1998 07:20:20 GMT