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容mom 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容mom 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容ktami 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容mom 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容ma 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. 9.1 SVOPING 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容mov 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容dinyaet 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容m 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. 9.1.2 Vygruzka processov 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容ma. 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容ma imeet, odnako, bolee ser'eznye iz座any. 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 |