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 9.2 PODKACHKA PO ZAPROSU 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 sist