      `Elementy arhitektury sistemy virtual'noj pamyati vo FreeBSD

  Matthew Dillon

       <dillon@apollo.backplane.com>
     

   $FreeBSD:
   release/8.4.0/ru_RU.KOI8-R/articles/vm-design/article.xml 39632
   2012-10-01 11:56:00Z gabor $

   $FreeBSD:
   release/8.4.0/ru_RU.KOI8-R/articles/vm-design/article.xml 39632
   2012-10-01 11:56:00Z gabor $

   FreeBSD `eto zaregistrirovannaya torgovaya marka FreeBSD
   Foundation.

   Linux `eto zaregistrirovannaya torgovaya marka Linus Torvalds.

   Microsoft, FrontPage, IntelliMouse, MS-DOS, Outlook, Windows,
   Windows Media i Windows NT `eto ili zaregistrirovannye torgovye
   marki ili torgovye marki Microsoft Corporation v Soedinennyh
   SHtatah i/ili drugih stranah.

   Motif, OSF/1 i UNIX `eto zaregistrirovannye torgovye marki, a IT
   DialTone i The Open Group `eto torgovye marki Open Group v
   Soedinennyh SHtatah i drugih stranah.

   Mnogie iz oboznachenij, ispol'zuemye proizvoditelyami i prodavcami
   dlya oboznacheniya svoih produktov, zayavlyayutsya v kachestve
   torgovyh marok. Kogda takie oboznacheniya poyavlyayutsya v `etom
   dokumente, i Proektu FreeBSD izvestno o torgovoj marke, k
   oboznacheniyu dobavlyaetsya znak ''(TM)'' ili ''(R)''.

   Pervonachal'no `eta stat'ya byla opublikovana v nomere DaemonNews
   za yanvar' 2000 goda. `Eta versiya stat'i mozhet vklyuchat'
   dobavleniya, kasayuschiesya izmenenij v realizacii VM vo FreeBSD
   ot M`etta i drugih avtorov.

   Nazvanie stat'i govorit lish' o tom, chto ya popytayus' opisat' v
   celom VM-sistemu ponyatnym yazykom. Poslednij god ya sosredotochil
   usiliya v rabote nad neskol'kimi osnovnymi podsistemami yadra
   FreeBSD, sredi kotoryh podsistemy VM i podkachki byli samymi
   interesnymi, a NFS okazalas' ''neobhodimoj rutinoj''. YA perepisal
   lish' maluyu chast' koda. CHto kasaetsya VM, to ya edinstvennym
   bol'shim obnovleniem, kotoroe ya sdelal, yavlyaetsya peredelka
   podsistemy podkachki. Osnovnaya chast' moej raboty zaklyuchalas' v
   zachistke i podderzhke koda, s edinstvennoj zametnoj peredelkoj
   koda i bez znachitel'noj peredelki algoritmov v VM-podsisteme. V
   osnovnom teoreticheskaya baza raboty VM-podsistemy ostalas'
   neizmennoj, a bol'shinstvo blagodarnostej za sovremennyh
   novovvedeniya za poslednie neskol'ko let prinadlezhat John Dyson i
   David Greenman. Ne yavlyayas' istorikom, kak Kerk, ya ne budu
   pytat'sya svyazat' razlichnye vozmozhnosti sistemy s imenami,
   potomu chto obyazatel'no oshibus'.

     --------------------------------------------------------------

1. Vvedenie

   Pered tem, kak perejti neposredstvenno k suschestvuyuschej
   arhitekture, potratim nemnogo vremeni na rassmotrenie voprosa o
   neobhodimosti podderzhki i modernizacii lyubogo dlitel'no
   zhivuschego koda. V mire programmirovaniya algoritmy stanovyatsya
   bolee vazhnymi, chem kod, i imenno iz-za akademicheskih kornej BSD
   iznachal'no bol'shoe vnimanie udelyalos' prorabotke algoritmov.
   Vnimanie, udelennoe arhitekture, v obschem otrazhaetsya na
   yasnosti i gibkosti koda, kotoryj mozhet byt' dostatochno legko
   izmenen, rasshiren ili s techeniem vremeni zamenen. Hotya
   nekotorye schitayut BSD ''staroj'' operacionnoj sistemoj, te ih
   nas, kto rabotaet nad nej, vidyat ee skoree sistemoj so ''zrelym''
   kodom s razlichnymi komponentami, kotorye byli zameneny,
   rasshireny ili izmeneny sovremennym kodom. On razvivaetsya, i
   FreeBSD ostaetsya peredovoj sistemoj, vne zavisimosti ot togo,
   naskol'ko staroj mozhet byt' chast' koda. `Eto vazhnoe otlichie,
   kotoroe, k sozhaleniyu, ne vsemi ponimaetsya. Samoj bol'shoj
   oshibkoj, kotoruyu mozhet dopustit' programmist, yavlyaetsya
   ignorirovanie istorii, i `eto imenno ta oshibka, kotoruyu sdelali
   mnogie drugie sovremennye operacionnye sistemy. Samym yarki
   primerom zdes' yavlyaetsya Windows NT(R), i posledstviya uzhasny.
   Linux takzhe v nekotoroj stepeni sovershil `etu
   oshibku-dostatochno, chtoby my, lyudi BSD, po krajnej mere po razu
   otpustili po `etomu povodu shutku. Problema Linux zaklyuchaetsya
   prosto v otsutstvii opyta i istorii dlya sravneniya idej,
   problema, kotoraya legko i bystro reshaetsya soobschestvom Linux
   tochno tak zhe, kak ona reshaetsya v soobschestve BSD-postoyannoj
   rabotoj nad kodom. Razrabotchiki Windows NT, s drugoj storony,
   postoyanno sovershayut te zhe samye oshibki, chto byli resheny v
   UNIX(R) desyatki let nazad, a zatem tratyat gody na ih ustranenie.
   Snova i snova. Est' neskol'ko sluchaev ''prorabotka arhitektury
   otsutstvuet'' i ''my vsegda pravy, potomu chto tak govorit nash
   otdel prodazh''. YA ploho perenoshu teh, kogo ne uchit istoriya.

   Bol'shinstvo ochevidnoj slozhnosti arhitektury FreeBSD, osobenno v
   podsisteme VM/Swap, yavlyaetsya pryamym sledstviem togo, chto ona
   reshaet ser'eznye problemy s proizvoditel'nost'yu, kotorye
   proyavlyayutsya pri razlichnyh usloviyah. `Eti problemy vyzvany ne
   plohoj prorabotkoj algoritmov, a voznikayut iz okruzhayuschih
   faktorov. V lyubom pryamom sravnenii mezhdu platformami `eti
   problemy proyavlyayutsya, kogda sistemnye resursy nachinayut
   istoschat'sya. Tak kak ya opisyvayu podsistemu VM/Swap vo FreeBSD,
   to chitatel' dolzhen vsegda imet' v vidu dva obstoyatel'stva:

    1. Samym vazhnym aspektom pri proektirovanii proizvoditel'nosti
       yavlyaetsya to, chto nazyvaetsya "optimizaciej kriticheskogo
       marshruta". CHasto sluchaetsya, chto optimizaciya
       proizvoditel'nosti daet prirost ob"ema koda radi togo, chtoby
       kriticheskij marshrut rabotal bystree.

    2. CHetkost' obschej arhitektury okazyvaetsya luchshe sil'no
       optimizirovannoj arhitektury s techeniem vremeni. Kogda kak
       obobschennaya arhitektura mozhet byt' medlennee, chem
       optimizirovannaya arhitektura, pri pervoj realizacii, pri
       obobschennoj arhitekture legche podstraivat'sya pod
       izmenyayuschiesya usloviya i chrezmerno optimizirovannaya
       arhitektura okazyvaetsya neprigodnoj.

   Lyuboj kod, kotoryj dolzhen vyzhit' i poddavat'sya podderzhke
   gody, dolzhen po`etomu byt' tschatel'no produman s samogo nachala,
   dazhe esli `eto stoit poteri proizvoditel'nosti. Dvadcat' let
   nazad byli te, kto otstaival preimuschestvo programmirovaniya na
   yazyke assemblera pered programmirovaniem na yazyke vysokogo
   urovnya, potomu chto pervyj generiroval v desyat' raz bolee
   bystryj kod. V nashi dni oshibochnost' `etogo argumenta
   ochevidna - mozhno provesti paralleli s postroeniem algoritmov i
   obobscheniem koda.

     --------------------------------------------------------------

2. Ob"ekty VM

   Luchshe vsego nachat' opisanie VM-sistemy FreeBSD s popytki
   vzglyanut' na nee s tochki zreniya pol'zovatel'skogo processa.
   Kazhdyj pol'zovatel'skij process imeet edinoe, prinadlezhaschee
   tol'ko emu i nerazryvnoe adresnoe prostranstvo VM, soderzhaschee
   neskol'ko tipov ob"ektov pamyati. `Eti ob"ekty imeyut razlichnye
   harakteristiki. Kod programmy i ee dannye yavlyayutsya edinym
   fajlom, otobrazhaemym v pamyat' (`eto vypolnyayuschijsya dvoichnyj
   fajl), odnako kod programmy dostupen tol'ko dlya chteniya, kogda
   kak dannye programmy razmeschayutsya v rezhime
   kopirovaniya-pri-zapisi. BSS programmy predstavlyaet soboj vsego
   lish' vydelennuyu oblast' pamyati, zapolnennuyu, esli `eto
   trebovalos', nulyami, chto nazyvaetsya obnuleniem stranic pamyati
   po trebovaniyu. Otdel'nye fajly mogut takzhe otobrazhat'sya v
   adresnoe prostranstvo, imenno tak rabotayut dinamicheskie
   biblioteki. Takie otobrazheniya trebuyut izmenenij, chtoby
   ostavat'sya prinadlezhaschimi processu, kotoryj ih vypolnil.
   Sistemnyj vyzov fork dobavlyaet perevodit problemu upravleniya VM
   polnost'yu v novuyu ploskost', vdobavok k uzhe imeyuschimsya
   slozhnostyam.

   Illyustriruet slozhnost' stranica dannyh dvoichnoj programmy
   (kotoraya yavlyaetsya stranicej kopiruemoj-pri-zapisi). Dvoichnaya
   programma soderzhit sekciyu predvaritel'no inicializirovannyh
   dannyh, kotoraya pervonachal'no otobrazhaetsya neposredstvenno iz
   fajla programmy. Kogda programma zagruzhaetsya v Vm-prostranstvo
   processa, `eta oblast' snachala otobrazhaetsya v pamyat' i
   podderzhivaetsya binarnym fajlom programmy, pozvolyaya VM-sisteme
   osvobozhdat'/povtorno ispol'zovat' stranicu, a potom zagruzhat' ee
   snova iz binarnogo fajla. Odnako v moment, kogda process izmenyaet
   `eti dannye, VM-sistema dolzhna sdelat' kopiyu stranicy,
   prinadlezhaschuyu tol'ko `etomu processu. Tak kak `eta kopiya byla
   izmenena, to VM-sistema ne mozhet bol'she osvobozhdat' `etu
   stranicu, tak kak vposledstvii ee nevozmozhno budet vosstanovit'.

   Vy tut zhe zametite, chto to, chto snachala bylo prostym
   otobrazheniem fajla v pamyat', stanovitsya gorazdo bolee slozhnym
   predmetom. Dannye mogut modificirovat'sya postranichno, kogda kak
   otobrazhenie fajla vypolnyaetsya dlya mnogih stranic za raz.
   Slozhnost' esche bolee uvelichivaetsya, kogda process vypolnyaet
   vyzov fork. Pri `etom porozhdayutsya dva processa-kazhdyj so s
   sobstvennym adresnym prostranstvom, vklyuchayuschim vse
   izmeneniya, vypolnennye ishodnym processom do vyzova funkcii
   fork(). Bylo by glupo dlya VM-sistemy delat' polnuyu kopiyu dannyh
   vo vremya vyzova fork(), tak kak ves'ma veroyatno, chto odin iz
   dvuh processov budet nuzhen tol'ko dlya chteniya iz toj stranicy,
   chto pozvolyaet ispol'zovanie ishodnoj stranicy. To, chto bylo
   stranicej, prinadlezhaschej tol'ko processu, sdelaetsya snova
   stranicej, kopiruemoj pri zapisi, tak kak kazhdyj iz processov (i
   roditel', i potomok) polagayut, chto ih sobstvennye izmeneniya
   posle razvetvleniya budut prinadlezhat' tol'ko im, i ne zatronut
   rodstvennyj process.

   FreeBSD upravlyaet vsem `etim pri pomoschi mnogourovnevoj modeli
   VM-ob"ektov. Ishodnyj fajl s dvoichnoj programmoj perenositsya na
   samyj nizhnij uroven' ob"ektov VM. Uroven' stranic, kopiruemyh pri
   zapisi, nahoditsya vyshe nego, i hranit te stranicy, kotorye byli
   skopirovany iz ishodnogo fajla. Esli programma modificiruet
   stranicy dannyh, otnosyaschiesya k ishodnomu fajlu, to sistema VM
   obnaruzhivaet `eto i perenosit kopiyu `etoj stranicy na bolee
   vysokij uroven'. Kogda process razvetvlyaetsya, dobavlyayutsya
   novye urovni VM-ob"ektov. `Eto mozhno pokazat' na prostom primere.
   Funkciya fork() yavlyaetsya obschej operaciej dlya vseh sistem
   *BSD, tak chto v `etom primere budet rassmatrivat'sya programma,
   kotoraya zapuskaetsya, a zatem razvetvlyaetsya. Kogda process
   zapuskaetsya, VM-sistema sozdaet nekotoryj uroven' ob"ektov,
   oboznachim ego A:

 +---------------+
 |       A       |
 +---------------+

   A sootvetstvuet fajlu-po neobhodimosti stranicy pamyati mogut
   vysvobozhdat'sya i podgruzhat'sya s nositelya fajla. Podgruzka s
   diska mozhet potrebovat'sya programme, odnako na samom dele my ne
   hotim, chtoby ona zapisyvalas' obratno v fajl. Po`etomu VM-sistema
   sozdaet vtoroj uroven', B, kotoryj fizicheski podderzhivaetsya
   diskovym prostranstvom podkachki:

 +---------------+
 |       B       |
 +---------------+
 |       A       |
 +---------------+

   Pri pervoj zapisi v stranicu posle vypolneniya `etoj operacii, v B
   sozdaetsya novaya stranica, soderzhimoe kotoroj beretsya iz A. Vse
   stranicy v B mogut sbrasyvat'sya i schityvat'sya iz ustrojstva
   podkachki. Kogda programma vetvitsya, VM-sistema sozdaet dva novyh
   urovnya ob"ektov-C1 dlya porozhdayuschego processa i C2 dlya
   porozhdennogo-oni raspolagayutsya poverh B:

 +-------+-------+
 |   C1  |   C2  |
 +-------+-------+
 |       B       |
 +---------------+
 |       A       |
 +---------------+

   V `etom sluchae, dopustim, chto stranica v B byla izmenena
   nachal'nym roditel'skim processom. V processe vozniknet situaciya
   kopirovaniya pri zapisi i stranica skopiruetsya v C1, pri `etom
   ishodnaya stranica ostanetsya v B netronutoj. Teper' dopustim,
   chto ta zhe samaya stranica v B izmenyaetsya porozhdennym
   processom. V processe vozniknet situaciya kopirovaniya pri zapisi
   i stranica skopiruetsya v C2. Ishodnaya stranica v B teper'
   polnost'yu skryta, tak kak i C1, i C2 imeyut kopii, a B
   teoreticheski mozhet byt' unichtozhena, esli ona ne predstavlyaet
   soboj ''real'nogo'' fajla). Odnako takuyu optimizaciyu ne tak uzh
   prosto osuschestvit', potomu chto ona delaetsya na urovne melkih
   edinic. Vo FreeBSD takaya optimizaciya ne vypolnyaetsya. Teper'
   polozhim (a `eto chasto sluchaetsya), chto porozhdennyj process
   vypolnyaet vyzov exec(). Ego tekuschee adresnoe prostranstvo
   obychno zamenyaetsya novym adresnym prostranstvom,
   predstavlyayuschim novyj fajl. V `etom sluchae uroven' C2
   unichtozhaetsya:

 +-------+
 |   C1  |
 +-------+-------+
 |       B       |
 +---------------+
 |       A       |
 +---------------+

   V `etom sluchae kolichestvo potomkov B stanovitsya ravnym odnomu i
   vse obrascheniya k B teper' vypolnyayutsya cherez C1. `Eto
   oznachaet, chto B i C1 mogut byt' ob"edineny. Vse stranicy v B,
   kotorye takzhe suschestvuyut i v C1, vo vremya ob"edineniya iz B
   udalyayutsya. Takim obrazom, hotya optimizaciya na predyduschem
   shage mozhet ne delat'sya, my mozhem vosstanovit' mertvye stranicy
   pri okonchanii raboty processov ili pri vyzove exec().

   Takaya model' sozdaet nekotoroe kolichestvo potencial'nyh problem.
   Pervaya, s kotoroj vy mozhete stolknut'sya, zaklyuchaetsya v
   sravnitel'no bol'shoj posledovatel'nosti urovnej ob"ektov VM, na
   skanirovanie kotoryh tratitsya vremya i pamyat'. Bol'shoe
   kolichestvo urovnej mozhet vozniknut', kogda processy
   razvetvlyayutsya, a zatem razvetvlyayutsya esche raz (kak
   porozhdennye, tak i porozhdayuschie). Vtoraya problema
   zaklyuchaetsya v tom, chto vy mozhete stolknut'sya s mertvymi,
   nedostupnymi stranicami gluboko v ierarhii ob"ektov VM. V nashem
   poslednem primere esli kak roditel', tak i potomok izmenyayut odnu
   i tu zhe stranicu, oni oba poluchayut sobstvennye kopii stranicy,
   a ishodnaya stranica v B stanovitsya nikomu ne dostupnoj. takaya
   stranica v B mozhet byt' vysvobozhdena.

   FreeBSD reshaet problemu s glubinoj vlozhennosti s pomosch'yu
   priema optimizacii, kotoryj nazyvaetsya "All Shadowed Case". `Etot
   sluchaj voznikaet, esli v C1 libo C2 voznikaet stol'ko sluchaev
   kopirovaniya stranic pri zapisi, chto oni polnost'yu zakryvayut
   vse stranicy v B. Dopustim, chto takoe proizoshlo v C1. C1 mozhet
   teper' polnost'yu zamenit' B, tak chto vmesto cepochek C1->B->A i
   C2->B->A my teper' imeem cepochki C1->A i C2->B->A. No posmotrite,
   chto poluchaetsya-teper' B imeet tol'ko odnu ssylku (C2), tak chto
   my mozhem ob"edinit' B i C2. V konechnom itoge B budet polnost'yu
   udalen i my imeem cepochki C1->A i C2->A. CHasto B budet
   soderzhat' bol'shoe kolichestvo stranic, i ni C1, ni C2 ne smogut
   polnost'yu ih zamenit'. Esli my snova porodim process i sozdadim
   nabor urovnej D, pri `etom, odnako, bolee veroyatno, chto odin iz
   urovnej D postepenno smozhet polnost'yu zamestit' gorazdo men'shij
   nabor dannyh, predstavlennyj C1 i C2. Ta zhe samaya optimizaciya
   budet rabotat' v lyuboj tochke grafa i glavnym rezul'tatom `etogo
   yavlyaetsya to, chto dazhe na sil'no zagruzhennoj mashine s
   mnozhestvom porozhdaemyh processov steki ob"ektov VM ne chasto
   byvayut glubzhe chetyreh urovnej. `Eto tak kak dlya
   porozhdayuschego, tak i dlya porozhdennogo processov, i ostaetsya
   v sile kak v sluchae, kogda vetvlenie delaet roditel', tak i v
   sluchae, kogda vetvlenie vypolnyaet potomok.

   Problema s mertvoj stranicej vse esche imeet mesto, kogda C1 ili
   C2 ne polnost'yu perekryvayut B. Iz-za drugih primenyaemyh nami
   metodov optimizacii `etot sluchaj ne predstavlyaet bol'shoj
   problemy i my prosto pozvolyaem takim stranicam suschestvovat'.
   Esli sistema ispytyvaet nehvatku operativnoj pamyati, ona
   vypolnyaet ih vygruzku v oblast' podkachki, chto zanimaet
   nekotoroe prostranstvo v oblasti podkachki, no `eto vse.

   Preimuschestvo modeli VM-ob"ektov zaklyuchaetsya v ochen' bystrom
   vypolnenii funkcii fork(), tak kak pri `etom ne vypolnyaetsya
   real'nogo kopirovaniya dannyh. Minusom `etogo podhoda yavlyaetsya
   to, chto vy mozhete postroit' sravnitel'no slozhnuyu ierarhiyu
   ob"ektov VM, kotoraya neskol'ko zamedlyaet obrabotku situacij
   otsutstviya stranic pamyati, i k tomu zhe tratitsya pamyat' na
   upravlenie strukturami ob"ektov VM. Priemy optimizacii,
   primenyaemye vo FreeBSD, pozvolyayut snizit' znachimost' `etih
   problem do stepeni, kogda ih mozhno bez osobyh poter'
   ignorirovat'.

     --------------------------------------------------------------

3. Urovni oblasti podkachki

   Stranicy s sobstvennymi dannymi pervonachal'no yavlyayutsya
   stranicami, kopiruemymi pri zapisi ili zapolnyaemymi nulyami.
   Kogda vypolnyaetsya izmenenie, i, sootvetstvenno, kopirovanie,
   nachal'noe hranilische ob"ekta (obychno fajl) ne mozhet bol'she
   ispol'zovat'sya dlya hraneniya kopii stranicy, kogda VM-sisteme
   nuzhno ispol'zovat' ee povtorno dlya drugih celej. V `etot moment
   na pomosch' prihodit oblast' podkachki. Oblast' podkachki
   vydelyaetsya dlya organizacii hranilischa pamyati, kotoraya inache
   ne mozhet byt' dostupna. FreeBSD sozdaet strukturu upravleniya
   podkachkoj dlya ob"ekta VM, tol'ko kogda `eto dejstvitel'no
   nuzhno. Odnako struktura upravleniya podkachkoj istoricheski imela
   nekotorye problemy:

     * Vo FreeBSD 3.X v strukture upravleniya oblast'yu podkachki
       predvaritel'no vydelyaetsya massiv, kotoryj predstavlyaet
       celyj ob"ekt, trebuyuschij hraneniya v oblasti podkachki-dazhe
       esli tol'ko neskol'ko stranic `etogo ob"ekta hranyatsya v
       oblasti podkachki. `Eto sozdaet problemu fragmentacii pamyati
       yadra v sluchae, kogda v pamyat' otobrazhayutsya bol'shie
       ob"ekty ili kogda vetvyatsya processy, zanimayuschie bol'shoj
       ob"em pamyati pri rabote (RSS).

     * Takzhe dlya otslezhivaniya pamyati podkachki v pamyati yadra
       podderzhivaetsya ''spisok dyr'', i on takzhe neskol'ko
       fragmentirovan. Tak kak ''spisok dyr'' yavlyaetsya
       posledovatel'nym spiskom, to proizvoditel'nost' pri
       raspredelenii i vysvobozhdenii pamyati v oblasti podkachki
       neoptimal'no i ee slozhnost' zavisit ot kolichestva stranic
       kak O(n).

     * Takzhe v processe vysvobozhdeniya pamyati v oblasti podkachki
       trebuetsya vydelenie pamyati v yadre, i `eto privodit k
       problemam blokirovki pri nedostatke pamyati.

     * Problema esche bolee obostryaetsya iz-za dyr, sozdavaemyh po
       chereduyuschemusya algoritmu.

     * Krome togo, spisok raspredeleniya blokov v oblasti podkachki
       legko okazyvaetsya fragmentirovannym, chto privodit k
       raspredeleniyu neposledovatel'nyh oblastej.

     * Pamyat' yadra takzhe dolzhna raspredelyat'sya po hodu raboty
       dlya dopolnitel'nyh struktur po upravleniyu oblast'yu
       podkachki pri vygruzke stranic pamyati v `etu oblast'.

   Ochevidno, chto mest dlya usovershenstvovanij predostatochno. Vo
   FreeBSD 4.X podsistema upravleniya oblast'yu podkachki byla
   polnost'yu perepisana mnoyu:

     * Struktury upravleniya oblast'yu podkachki raspredelyayutsya
       pri pomoschi h`esh-tablicy, a ne cherez linejnyj massiv, chto
       daet im fiksirovannyj razmer pri raspredelenii i rabotu s
       gorazdo men'shimi strukturami.

     * Vmesto togo, chtoby ispol'zovat' odnonapravlennyj svyaznyj
       spisok dlya otslezhivaniya vydeleniya prostranstva v oblasti
       podkachki, teper' ispol'zuetsya pobitovaya karta blokov
       oblasti podkachki, vypolnennaya v osnovnom v vide drevovidnoj
       struktury s informaciej o svobodnom prostranstve,
       nahodyaschejsya v uzlah struktur. `Eto privodit k tomu, chto
       vydelenie i vysvobozhdenie pamyati v oblasti podkachki
       stanovitsya operaciej slozhnosti O(1).

     * Vse derevo takzhe raspredelyaetsya zaranee dlya togo, chtoby
       izbezhat' raspredeleniya pamyati yadra vo vremya operacij s
       oblast'yu podkachki pri kriticheski malom ob"eme svobodnoj
       pamyati. V konce koncov, sistema obraschaetsya k oblasti
       podkachki pri nehvatke pamyati, tak chto my dolzhny izbezhat'
       raspredeleniya pamyati yadra v takie momenty dlya izbezhaniya
       potencial'nyh blokirovok.

     * Dlya umen'sheniya fragmentacii derevo mozhet raspredelyat'
       bol'shoj posledovatel'nyj kusok za raz, propuskaya men'shie
       fragmentirovannye oblasti.

   YA ne sdelal poslednij shag k zavedeniyu ''ukazatelya na
   raspredelenie'', kotoryj budet peredvigat'sya po uchastku oblasti
   podkachki pri vydelenii pamyati dlya obespecheniya v buduschem
   raspredeleniya posledovatel'nyh uchastkov, ili po krajnej mere
   mestopolozheniya ssylki, no ya ubezhden, chto `eto mozhet byt'
   sdelano.

     --------------------------------------------------------------

4. Kogda osvobozhdat' stranicu

   Tak kak sistema VM ispol'zuet vsyu dostupnuyu pamyat' dlya
   k`eshirovaniya diska, to obychno dejstvitel'no nezanyatyh stranic
   ochen' malo. Sistema VM zavisit ot togo, kak ona tochno vybiraet
   nezanyatye stranicy dlya povtornogo ispol'zovaniya dlya novyh
   raspredelenij. Optimal'nyj vybor stranic dlya vysvobozhdeniya,
   vozmozhno, yavlyaetsya samoj vazhnoj funkciej lyuboj VM-sistemy,
   iz teh, chto ona mozhet vypolnyat', potomu chto pri nepravil'nom
   vybore sistema VM vynuzhdena budet zaprashivat' stranicy s diska,
   znachitel'no snizhaya proizvoditel'nost' vsej sistemy.

   Kakuyu dopolnitel'nuyu nagruzku my mozhet vydelit' v kriticheskom
   puti dlya izbezhaniya vysvobozhdeniya ne toj stranicy? Kazhdyj
   nepravil'nyj vybor budet stoit' nam sotni tysyach taktov raboty
   central'nogo processora i zametnoe zamedlenie raboty zatronutyh
   processov, tak chto my dolzhny smirit'sya so znachitel'nymi
   izderzhkami dlya togo, chtoby byla zavedomo vybrana pravil'naya
   stranica. Vot pochemu FreeBSD prevoshodit drugie sistemy v
   proizvoditel'nosti pri nehvatke resursov pamyati.

   Algoritm opredeleniya svobodnoj stranicy napisan na osnove istorii
   ispol'zovaniya stranic pamyati. Dlya polucheniya `etoj istorii
   sistema ispol'zuet vozmozhnosti bita ispol'zovaniya pamyati,
   kotorye imeyutsya v bol'shinstve apparatnyh tablicah stranic
   pamyati.

   V lyubom sluchae, bit ispol'zovaniya stranicy ochischaetsya, i v
   nekotoryj bolee pozdnij moment VM-sistema obraschaetsya k stranice
   snova i obnaruzhivaet, chto `etot bit ustanovlen. `Eto ukazyvaet
   na to, chto stranica aktivno ispol'zuetsya. Periodicheski
   proveryaya `etot bit, nakaplivaetsya istoriya ispol'zovaniya (v
   vide schetchika) fizicheskoj stranicy. Kogda pozzhe VM-sisteme
   trebuetsya vysvobodit' nekotorye stranicy, proverka istorii
   vystupaet ukazatelem pri opredelenii naibolee veroyatnoj
   kandidatury dlya povtornogo ispol'zovaniya.

   +----------------------------------------------------------------+
   | CHto, esli apparatura ne imeet bita ispol'zovaniya stranicy?   |
   |                                                                |
   | Dlya teh platform, chto ne imeyut `etoj vozmozhnosti, sistema  |
   | `emuliruet `etot bit. Ona snimaet otobrazhenie ili             |
   | zaschischaet stranicu, chto privodit k oshibke dostupa k       |
   | stranice, esli k stranice vypolnyaetsya povtornoe obraschenie. |
   | Pri vozniknovenii `etoj oshibki sistema prosto pomechaet       |
   | stranicu kak ispol'zuemuyu i snimaet zaschitu so stranicy, tak |
   | chto ona mozhet ispol'zovat'sya. Hotya ispol'zovanie takogo    |
   | priema tol'ko dlya opredeleniya ispol'zovaniya stranicy ves'ma |
   | nakladno, `eto vygodnee, chem povtorno ispol'zovat' stranicu   |
   | dlya drugih celej i obnaruzhit', chto ona snova nuzhna         |
   | processu i podgruzhat' ee s diska.                             |
   +----------------------------------------------------------------+

   FreeBSD ispol'zuet neskol'ko ocheredej stranic dlya obnovleniya
   vybora stranic dlya povtornogo ispol'zovaniya, a takzhe dlya
   opredeleniya togo, kogda zhe gryaznye stranicy dolzhny byt'
   sbrosheny v hranilische. Tak kak tablicy stranic vo FreeBSD
   yavlyayutsya dinamicheskimi ob"ektami, prakticheski nichego ne
   stoit vyrezat' stranicu iz adresnogo prostranstva lyubogo
   ispol'zuyuschego ee processa. Posle togo, kak podhodyaschaya
   stranica, na osnove schetchika ispol'zovaniya, vybrana, imenno
   `eto i vypolnyaetsya. Sistema dolzhna otlichat' mezhdu chistymi
   stranicami, kotorye teoreticheski mogut byt' vysvobozhdeny v
   lyuboe vremya, i gryaznymi stranicami, kotorye snachala dolzhny
   byt' perepisany v hranilische pered tem, kak ih mozhno budet
   ispol'zovat' povtorno. Posle nahozhdeniya podhodyaschej stranicy
   ona peremeschaetsya v neaktivnuyu ochered', esli ona yavlyaetsya
   gryaznoj, ili v ochered' k`esha, esli ona chistaya. Otdel'nyj
   algoritm, osnovyvayuschijsya na otnoshenii kolichestva gryaznyh
   stranic k chistym, opredelyaet, kogda gryaznye stranicy v
   neaktivnoj ocheredi dolzhny byt' sbrosheny na disk. Kogda `eto
   vypolnitsya, sbroshennye stranicy peremeschayutsya iz neaktivnoj
   ocheredi v ochered' k`esha. V `etot moment stranicy v ocheredi
   k`esha mogut byt' povtorno aktivizirovany VM so sravnitel'no
   malymi nakladnymi rashodami. Odnako stranicy v ocheredi k`esha
   predpolagaetsya ''vysvobozhdat' nemedlenno'' i povtorno
   ispol'zovat' v LRU-poryadke (men'she vsego ispol'zuemyj), kogda
   sisteme potrebuetsya vydelenie dopolnitel'noj pamyati.

   Stoit otmetit', chto vo FreeBSD VM-sistema pytaetsya razdelit'
   chistye i gryaznye stranicy vo izbezhanie srochnoj neobhodimosti v
   nenuzhnyh sbrosah gryaznyh stranic (chto otrazhaetsya na
   propusknoj sposobnosti vvoda/vyvoda) i ne peremeschaet
   besprichinno stranicy mezhdu raznymi ocheredyami, kogda podsistema
   upravleniya pamyat'yu ne ispytyvaet nehvatku resursov. Vot pochemu
   vy mozhete videt', chto pri vypolnenii komandy systat -vm v
   nekotoryh sistemah znachenie schetchika ocheredi k`esha malo, a
   schetchik aktivnoj ocheredi bol'shoj. Pri povyshenii nagruzki na
   VM-sistemu ona prilagaet bol'shie usiliya na podderzhku razlichnyh
   ocheredej stranic v sootnosheniyah, kotorye yavlyayutsya naibolee
   `effektivnymi.

   Godami hodili sovremennye legendy, chto Linux vypolnyaet rabotu po
   predotvrascheniyu vygruzki na disk luchshe, chem FreeBSD, no `eto
   ne tak. Na samom dele FreeBSD staraetsya sbrosit' na disk
   neispol'zuemye stranicy dlya osvobozhdeniya mesta pod diskovyj
   k`esh, kogda kak Linux hranit neispol'zuemye stranicy v pamyati i
   ostavlyaet pod k`esh i stranicy processov men'she pamyati. YA ne
   znayu, ostaetsya li `eto pravdoj na segodnyashnij den'.

     --------------------------------------------------------------

5. Optimizaciya oshibok dostupa k stranicam i ih obnuleniya

   Polagaya, chto oshibka dostupa k stranice pamyati v VM ne
   yavlyaetsya operaciej s bol'shimi nakladnymi rashodami, esli
   stranica uzhe nahoditsya v osnovnoj pamyati i mozhet byt' prosto
   otobrazhena v adresnoe prostranstvo processa, mozhet okazat'sya,
   chto `eto stanet ves'ma nakladno, esli ih budet okazyvat'sya
   regulyarno mnogo. Horoshim primerom `etoj situacii yavlyaetsya
   zapusk takih programm, kak ls(1) ili ps(1), snova i snova. Esli
   binarnyj fajl programmy otobrazhen v pamyat', no ne otobrazhen v
   tablicu stranic, to vse stranicy, k kotorym obraschalas'
   programma, okazhutsya nedostupnymi pri kazhdom zapuske programmy.
   `Eto ne tak uzh neobhodimo, esli `eti stranicy uzhe prisutstvuyut
   v k`eshe VM, tak chto FreeBSD budet pytat'sya vosstanavlivat'
   tablicy stranic processa iz teh stranic, chto uzhe raspolagayutsya
   v VM-k`eshe. Odnako vo FreeBSD poka ne vypolnyaetsya
   predvaritel'noe kopirovanie pri zapisi opredelennyh stranic pri
   vypolnenii vyzova exec. Naprimer, esli vy zapuskaete programmu
   ls(1) odnovremenno s rabotayuschej vmstat 1, to zametite, chto ona
   vsegda vydaet nekotoroe kolichestvo oshibok dostupa k stranicam,
   dazhe kogda vy zapuskaete ee snova i snova. `Eto oshibki
   zapolneniya nulyami, a ne oshibki koda programmy (kotorye uzhe
   byli obrabotany). Predvaritel'noe kopirovanie stranic pri
   vypolnenii vyzovov exec ili fork nahodyatsya v oblasti,
   trebuyuschej bolee tschatel'nogo izucheniya.

   Bol'shoj procent oshibok dostupa k stranicam, otnositsya k
   oshibkam pri zapolnenii nulyami. Vy mozhete obychno videt' `eto,
   prosmatrivaya vyvod komandy vmstat -s. `Eto proishodit, kogda
   process obraschaetsya k stranicam v svoej oblasti BSS. Oblast' BSS
   predpolagaetsya iznachal'no zapolnennoj nulyami, no VM-sistema ne
   zabotitsya o vydelenii pamyati do teh por, poka process real'no k
   nej ne obratitsya. Pri vozniknovenii oshibki VM-sistema dolzhna ne
   tol'ko vydelit' novuyu stranicu, no i zapolnit' ee nulyami. Dlya
   optimizacii operacii po zapolneniyu nulyami v sisteme VM imeetsya
   vozmozhnost' predvaritel'no obnulyat' stranicy i pomechat' ih, i
   zaprashivat' uzhe obnulennye stranicy pri vozniknovenii oshibok
   zapolneniya nulyami. Predvaritel'noe zapolnenie nulyami
   proishodit, kogda CPU prostaivaet, odnako kolichestvo stranic,
   kotorye sistema zaranee zapolnyaet nulyami, ogranicheno, dlya
   togo, chtoby ne perepolnit' k`eshi pamyati. `Eto prekrasnyj primer
   dobavleniya slozhnosti v VM-sistemu radi optimizacii kriticheskogo
   puti.

     --------------------------------------------------------------

6. Optimizaciya tablicy stranic

   Optimizaciya tablicy stranic sostavlyaet samuyu soderzhatel'nuyu
   chast' arhitektury VM vo FreeBSD i ona proyavlyaetsya pri
   poyavlenii nagruzki pri znachitel'nom ispol'zovanii mmap(). YA
   dumayu, chto `eto na samom dele osobennost' raboty bol'shinstva
   BSD-sistem, hotya ya ne uveren, kogda `eto proyavilos' vpervye.
   Est' dva osnovnyh podhoda k optimizacii. Pervyj zaklyuchaetsya v
   tom, chto apparatnye tablicy stranic ne soderzhat postoyannogo
   sostoyaniya, a vmesto `etogo mogut byt' sbrosheny v lyuboj moment
   s malymi nakladnymi rashodami. Vtoroj podhod sostoit v tom, chto
   kazhdaya aktivnaya tablica stranic v sisteme imeet
   upravlyayuschuyu strukturu pv_entry, kotoraya svyazana v strukturu
   vm_page. FreeBSD mozhet prosto prosmatrivat' `eti otobrazheniya,
   kotorye suschestvuyut, kogda kak v Linux dolzhny proveryat'sya vse
   tablicy stranic, kotorye mogut soderzhat' nuzhnoe otobrazhenie,
   chto v nekotoryh situaciya daet uvelichenie slozhnosti O(n^2).
   Iz-za togo, chto FreeBSD stremitsya vybrat' naibolee
   podhodyaschuyu k povtornomu ispol'zovaniyu ili sbrosu v oblast'
   podkachki stranicu, kogda oschuschaetsya nehvatka pamyati, sistema
   daet luchshuyu proizvoditel'nost' pri nagruzke. Odnako vo FreeBSD
   trebuetsya tonkaya nastrojka yadra dlya sootvetstviya situaciyam s
   bol'shim sovmestno ispol'zuemym adresnym prostranstvom, kotorye
   mogut sluchit'sya v sisteme, obsluzhivayuschej server
   telekonferencij, potomu chto struktury pv_entry mogut okazat'sya
   ischerpannymi.

   I v Linux, i vo FreeBSD trebuyutsya dorabotki v `etoj oblasti.
   FreeBSD pytaetsya maksimizirovat' preimuschestva ot potencial'no
   redko primenyaemoj modeli aktivnogo otobrazheniya (k primeru, ne
   vsem processam nuzhno otobrazhat' vse stranicy dinamicheskoj
   biblioteki), kogda kak Linux pytaetsya uprostit' svoi algoritmy.
   FreeBSD imeet zdes' obschee preimuschestvo v proizvoditel'nosti za
   schet ispol'zovaniya dopolnitel'noj pamyati, no FreeBSD vyglyadit
   huzhe v sluchae, kogda bol'shoj fajl sovmestno ispol'zuetsya
   sotnyami processov. Linux, s drugoj storony, vyglyadit huzhe v
   sluchae, kogda mnogo processov chastichno ispol'zuyut odnu i tu
   zhe dinamicheskuyu biblioteku, a takzhe rabotaet neoptimal'no pri
   popytke opredelit', mozhet li stranica povtorno ispol'zovat'sya,
   ili net.

     --------------------------------------------------------------

7. Podgonka stranic

   My zakonchim rassmotreniem metoda optimizacii podgonkoj stranic.
   Podgonka yavlyaetsya metodom optimizacii, razrabotannym dlya togo,
   chtoby dostup v posledovatel'nye stranicy virtual'noj pamyati
   maksimal'no ispol'zoval k`esh processora. V dalekom proshlom (to
   est' bol'she 10 let nazad) processornye k`eshi predpochitali
   otobrazhat' virtual'nuyu pamyat', a ne fizicheskuyu. `Eto
   privodilo k ogromnomu kolichestvu problem, vklyuchaya
   neobhodimost' ochistki k`esha v nekotoryh sluchayah pri kazhdom
   pereklyuchenii konteksta i problemy s zamescheniem dannyh v
   k`eshe. V sovremennyh processorah k`eshi otobrazhayut fizicheskuyu
   pamyat' imenno dlya resheniya `etih problem. `Eto oznachaet, chto
   dve sosednie stranicy v adresnom prostranstve processov mogut ne
   sootvetstvovat' dvuh sosednim stranicam v k`eshe. Fakticheski,
   esli vy ob `etom ne pozabotilis', to sosednie stranicy v
   virtual'noj pamyati mogut ispol'zovat' tu zhe samuyu stranicu v
   k`eshe processora-`eto privodit k sbrosu k`eshiruemyh dannyh i
   snizheniyu proizvoditel'nosti CPU. `Eto tak dazhe s
   mnozhestvennymi associativnymi k`eshami (hotya zdes' `effekt
   neskol'ko sglazhen).

   Kod vydeleniya pamyati vo FreeBSD vypolnyaet optimizaciyu s
   primeneniem podgonki stranic, oznachayuschuyu to, chto kod
   vydeleniya pamyati budet pytat'sya najti svobodnye stranicy,
   kotorye yavlyayutsya posledovatel'nymi s tochki zreniya k`esha.
   Naprimer, esli stranica 16 fizicheskoj pamyati naznachaetsya
   stranice 0 virtual'noj pamyati processa, a v k`esh pomeschaetsya 4
   stranicy, to kod podgonki stranic ne budet naznachat' stranicu 20
   fizicheskoj pamyati stranice 1 virtual'noj pamyati processa.
   Vmesto `etogo budet naznachena stranica 21 fizicheskoj pamyati.
   Kod podgonki stranic popytaetsya izbezhat' naznachenie stranicy
   20, potomu chto takoe otobrazhenie perekryvaetsya v toj zhe samoj
   pamyati k`esha kak stranica 16, i privedet k neoptimal'nomu
   k`eshirovaniyu. Kak vy mozhete predpolozhit', takoj kod
   znachitel'no dobavlyaet slozhnosti v podsistemu vydeleniya pamyati
   VM, no rezul'tat stoit togo. Podgonka stranic delaet pamyat' VM
   predskazuemoj, kak i obychnaya fizicheskaya pamyat', otnositel'no
   proizvoditel'nosti k`esha.

     --------------------------------------------------------------

8. Zaklyuchenie

   Virtual'naya pamyat' v sovremennyh operacionnyh sistemah dolzhna
   reshat' neskol'ko razlichnyh zadach `effektivno i pri raznyh
   usloviyah. Modul'nyj i algoritmicheskij podhod, kotoromu
   istoricheski sleduet BSD, pozvolyaet nam izuchit' i ponyat'
   suschestvuyuschuyu realizaciyu, a takzhe sravnitel'no legko
   izmenit' bol'shie bloki koda. Za neskol'ko poslednih let v
   VM-sisteme FreeBSD bylo sdelano nekotoroe kolichestvo
   usovershenstvovanij, i rabota nad nimi prodolzhaetsya.

     --------------------------------------------------------------

9. Dopolnitel'nyj seans voprosov i otvetov ot Allena Briggsa (Allen
Briggs) <briggs@ninthwonder.com>

   9.1. CHto `eto za "algoritm cheredovaniya", kotoryj vy upominali v
   spiske nedostatkov podsistemy upravleniya razdelom podkachki vo
   FreeBSD 3.X?

   9.2. Kak razdelenie chistyh i gryaznyh (neaktivnyh) stranic
   svyazano s situaciej, kogda vy vidite malen'kij schetchik ocheredi
   k`esha i bol'shoj schetchik aktivnoj ocheredi v vydache komandy
   systat -vm? Razve sistemnaya statistika ne schitaet aktivnye i
   gryaznye stranicy vmeste za schetchik aktivnoj ocheredi?

   9.3. V primere s ls(1) / vmstat 1 mogut li nekotorye oshibki
   dostupa k stranice byt' oshibkami stranic dannyh (COW iz
   vypolnimogo fajla v privatnye stranicy)? To est' ya polagayu, chto
   oshibki dostupa k stranicam yavlyayutsya chastichno oshibkami pri
   zapolnenii nulyami, a chastichno dannyh programmy. Ili vy
   garantiruete, chto FreeBSD vypolnyaet predvaritel'no COW dlya
   dannyh programmy?

   9.4. V vashem razdele ob optimizacii tablicy stranic, ne mogli by
   vy bolee podrobno rasskazat' o pv_entry i vm_page (ili vm_page
   dolzhna byt' vm_pmap-kak v 4.4, cf. pp. 180-181 of McKusick,
   Bostic, Karel, Quarterman)? A imenno kakoe dejstvie/reakciyu
   dolzhno potrebovat'sya dlya skanirovaniya otobrazhenij?

   9.5. Nakonec, v razdele o podgonke stranic horosho by bylo imet'
   kratkoe opisanie togo, chto `eto znachit. YA ne sovsem `eto
   ponyal.

   9.1. CHto `eto za "algoritm cheredovaniya", kotoryj vy upominali v
   spiske nedostatkov podsistemy upravleniya razdelom podkachki vo
   FreeBSD 3.X?

   FreeBSD ispol'zuet v oblasti podkachki mehanizm cheredovaniya, s
   indeksom po umolchaniyu, ravnym chetyrem. `Eto oznachaet, chto
   FreeBSD rezerviruet prostranstvo dlya chetyreh oblastej podkachki,
   dazhe esli u vas imeetsya vsego lish' odna, dve ili tri oblasti.
   Tak kak v oblasti podkachki imeetsya cheredovanie, to linejnoe
   adresnoe prostranstvo, predstavlyayuschee ''chetyre oblasti
   podkachki'', budet fragmentirovat'sya, esli u vas net na samom
   dele chetyreh oblastej podkachki. Naprimer, esli u vas dve oblasti
   A i B, to predstavlenie adresnogo prostranstva dlya `etoj oblasti
   podkachki vo FreeBSD budet organizovano s cheredovaniem blokov iz
   16 stranic:

   A B C D A B C D A B C D A B C D

   FreeBSD 3.X ispol'zuet ''posledovatel'nyj spisok svobodnyh
   oblastej'' dlya upravleniya svobodnymi oblastyami v razdele
   podkachki. Ideya sostoit v tom, chto bol'shie posledovatel'nye
   bloki svobodnogo prostranstva mogut byt' predstavleny pri pomoschi
   uzla odnosvyaznogo spiska (kern/subr_rlist.c). No iz-za
   fragmentacii posledovatel'nyj spisok sam stanovitsya
   fragmentirovannym. V primere vyshe polnost'yu neispol'zuemoe
   prostranstvo v A i B budet pokazano kak ''svobodnoe'', a C i D kak
   ''polnost'yu zanyatoe''. Kazhdoj posledovatel'nosti A-B trebuetsya
   dlya ucheta uzel spiska, potomu chto C i D yavlyayutsya dyrami,
   tak chto uzel spiska ne mozhet byt' svyazan so sleduyuschej
   posledovatel'nost'yu A-B.

   Pochemu my organizuem cheredovanie v oblasti podkachki vmesto
   togo, chtoby prosto ob"edinit' oblasti podkachki v odno celoe i
   pridumat' chto-to bolee umnoe? Potomu chto gorazdo legche
   vydelyat' posledovatel'nye polosy adresnogo prostranstva i
   poluchat' v rezul'tate avtomaticheskoe cheredovanie mezhdu
   neskol'kimi diskami, chem pytat'sya vydumyvat' slozhnosti v drugom
   meste.

   Fragmentaciya vyzyvaet drugie problemy. YAvlyayas'
   posledovatel'nym spiskom v 3.X i imeya takoe ogromnuyu
   fragmentaciyu, vydelenie i osvobozhdenie v oblasti podkachki
   stanovitsya algoritmom slozhnosti O(N), a ne O(1). Vmeste s
   drugimi faktorami (chastoe obraschenie k oblasti podkachki) vy
   poluchaete slozhnost' urovnej O(N^2) i O(N^3), chto ploho. V
   sisteme 3.X takzhe mozhet potrebovat'sya vydelenie KVM vo vremya
   raboty s oblast'yu podkachki dlya sozdaniya novogo uzla spiska,
   chto v uslovii nehvatki pamyati mozhet privesti k blokirovke, esli
   sistema popytaetsya sbrosit' stranicy v oblast' podkachki.

   V 4.X my ne ispol'zuem posledovatel'nyj spisok. Vmesto `etogo my
   ispol'zuem bazisnoe derevo i bitovye karty blokov oblasti
   podkachki, a ne ogranichennyj spisok uzlov. My prinimaem
   predvaritel'noe vydelenie vseh bitovyh kart, trebuemyh dlya vsej
   oblasti podkachki, no pri `etom tratitsya men'she pamyati, potomu
   chto my ispol'zuem bitovye karty (odin bit na blok), a ne
   svyazannyj spisok uzlov. Ispol'zovanie bazisnogo dereva vmesto
   posledovatel'nogo spiska daet nam proizvoditel'nost' O(1) vne
   zavisimosti ot fragmentacii dereva.

   9.2. Kak razdelenie chistyh i gryaznyh (neaktivnyh) stranic
   svyazano s situaciej, kogda vy vidite malen'kij schetchik ocheredi
   k`esha i bol'shoj schetchik aktivnoj ocheredi v vydache komandy
   systat -vm? Razve sistemnaya statistika ne schitaet aktivnye i
   gryaznye stranicy vmeste za schetchik aktivnoj ocheredi?

   YA ne ponyal sleduyuschee:

     Stoit otmetit', chto vo FreeBSD VM-sistema pytaetsya razdelit'
     chistye i gryaznye stranicy vo izbezhanie srochnoj neobhodimosti
     v nenuzhnyh sbrosah gryaznyh stranic (chto otrazhaetsya na
     propusknoj sposobnosti vvoda/vyvoda) i ne peremeschaet
     besprichinno stranicy mezhdu raznymi ocheredyami, kogda
     podsistema upravleniya pamyat'yu ne ispytyvaet nehvatku
     resursov. Vot pochemu vy mozhete videt', chto pri vypolnenii
     komandy systat -vm v nekotoryh sistemah znachenie schetchika
     ocheredi k`esha malo, a schetchik aktivnoj ocheredi bol'shoj.

   Da, `eto zaputyvaet. Svyaz' zaklyuchaetsya v "zhelaemom" i
   "dejstvitel'nom". My zhelaem razdelit' stranicy, no real'nost'
   takova, chto poka u nas net problem s pamyat'yu, nam `eto na samom
   dele ne nuzhno.

   `Eto oznachaet, chto FreeBSD ne budet ochen' sil'no starat'sya nad
   otdeleniem gryaznyh stranic (neaktivnaya ochered') ot chistyh
   stranic (ochered' k`esha), kogda sistema ne nahoditsya pod
   nagruzkoj, i ne budet deaktivirovat' stranicy (aktivnaya ochered'
   -> neaktivnaya ochered'), kogda sistema ne nagruzhena, dazhe esli
   oni ne ispol'zuyutsya.

   9.3. V primere s ls(1) / vmstat 1 mogut li nekotorye oshibki
   dostupa k stranice byt' oshibkami stranic dannyh (COW iz
   vypolnimogo fajla v privatnye stranicy)? To est' ya polagayu, chto
   oshibki dostupa k stranicam yavlyayutsya chastichno oshibkami pri
   zapolnenii nulyami, a chastichno dannyh programmy. Ili vy
   garantiruete, chto FreeBSD vypolnyaet predvaritel'no COW dlya
   dannyh programmy?

   Oshibka COW mozhet byt' oshibkoj pri zapolnenii nulyami ili dannyh
   programmy. Mehanizm v lyubom sluchae odin i tot zhe, potomu chto
   hranilische dannyh programmy uzhe v k`eshe. YA na samom dele ne
   rad ni tomu, ni drugomu. FreeBSD ne vypolnyaet predvaritel'noe COW
   dannyh programmy i zapolnenie nulyami, no ona vypolnyaet
   predvaritel'no otobrazhenie stranic, kotorye imeyutsya v ee
   k`eshe.

   9.4. V vashem razdele ob optimizacii tablicy stranic, ne mogli by
   vy bolee podrobno rasskazat' o pv_entry i vm_page (ili vm_page
   dolzhna byt' vm_pmap-kak v 4.4, cf. pp. 180-181 of McKusick,
   Bostic, Karel, Quarterman)? A imenno kakoe dejstvie/reakciyu
   dolzhno potrebovat'sya dlya skanirovaniya otobrazhenij?

   CHto delaet Linux v teh sluchayah, kogda FreeBSD rabotaet ploho
   (sovmestnoe ispol'zovanie otobrazheniya fajla mezhdu mnogimi
   processami)?

   vm_page predstavlyaet soboj paru (object,index#). pv_entry
   yavlyaetsya zapis'yu iz apparatnoj tablicy stranic (pte). Esli u
   vas imeetsya pyat' processov, sovmestno ispol'zuyuschih odnu i tu
   zhe fizicheskuyu stranicu, i v treh tablicah stranic `etih
   processov na samom dele otobrazhaetsya stranica, to stranica budet
   predstavlyat'sya odnoj strukturoj vm_page i tremya strukturami
   pv_entry.

   Struktury pv_entry predstavlyayut stranicy, otobrazhaemye MMU
   (odna struktura pv_entry sootvetstvuet odnoj pte). `Eto oznachaet,
   chto, kogda nam nuzhno ubrat' vse apparatnye ssylki na vm_page
   (dlya togo, chtoby povtorno ispol'zovat' stranicu dlya chego-to
   esche, vygruzit' ee, ochistit', pometit' kak gryaznuyu i tak
   dalee), my mozhem prosto prosmotret' svyaznyj spisok struktur
   pv_entry, svyazannyh s `etoj vm_page, dlya togo, chtoby udalit'
   ili izmenit' pte iz ih tablic stranic.

   V Linux net takogo svyaznogo spiska. Dlya togo, chtoby udalit' vse
   otobrazheniya apparatnoj tablicy stranic dlya vm_page, linux
   dolzhen projti po indeksu kazhdogo ob"ekta VM, kotoryj mozhet
   otobrazhat' stranicu. K primeru, esli u vas imeetsya 50 processov,
   kotorye vse otobrazhayut tu zhe samuyu dinamicheskuyu biblioteku i
   hotite izbavit'sya ot stranicy X v `etoj biblioteke, to vam nuzhno
   projtis' po indeksu vsej tablicy stranic dlya kazhdogo iz `etih 50
   processov, dazhe esli tol'ko 10 iz nih na samom dele otobrazhayut
   stranicu. Tak chto Linux ispol'zuet prostotu podhoda za schet
   proizvoditel'nosti. Mnogie algoritmy VM, kotorye imeyut slozhnost'
   O(1) ili (N maloe) vo FreeBSD, v Linux priobretayut slozhnost'
   O(N), O(N^2) ili huzhe. Tak kak pte, predstavlyayuschij
   konkretnuyu stranicu v ob"ekte, skoree vsego, budet s tem zhe
   smescheniem vo vseh tablicah stranic, v kotoryh oni
   otobrazhayutsya, to umen'shenie kolichestva obraschenij v tablicy
   stranic po tomu zhe samomu smescheniyu chasto pozvolyaet izbezhat'
   razrastaniya k`esha L1 dlya `etogo smescheniya, chto privodit k
   uluchsheniyu proizvoditel'nosti.

   Vo FreeBSD vvedeny dopolnitel'nye slozhnosti (shema s pv_entry)
   dlya uvelicheniya proizvoditel'nosti (umen'shaya kolichestvo
   obraschenij tol'ko k tem pte, kotorye nuzhno modificirovat').

   No vo FreeBSD imeetsya problema masshtabirovaniya, kotoroj net v
   Linux, potomu chto imeetsya ogranichennoe chislo struktur
   pv_entry, i `eto privodit k vozniknoveniyu problem pri bol'shom
   ob"eme sovmestno ispol'zuemyh dannyh. V `etom sluchae u vas mozhet
   vozniknut' nehvatka struktur pv_entry, dazhe esli svobodnoj
   pamyati hvataet. `Eto mozhet byt' dostatochno legko ispravleno
   uvelicheniem kolichestva struktur pv_entry pri nastrojke, no na
   samom dele nam nuzhno najti luchshij sposob delat' `eto.

   CHto kasaetsya ispol'zovaniya pamyati pod tablicu stranic protiv
   shemy s pv_entry: Linux ispol'zuet ''postoyannye'' tablicy
   stranic, kotorye ne sbrasyvayutsya, no emu ne nuzhny pv_entry dlya
   kazhdogo potencial'no otobrazhaemogo pte. FreeBSD ispol'zuet
   ''sbrasyvaemye'' tablicy stranic, no dlya kazhdogo real'no
   otobrazhaemogo pte dobavlyaetsya struktura pv_entry. YA dumayu,
   chto ispol'zovanie pamyati budet primerno odinakova, tem bolee
   chto u FreeBSD est' algoritmicheskoe preimuschestvo,
   zaklyuchayuscheesya v sposobnosti sbrasyvat' tablicy stranic s
   ochen' malymi nakladnymi rashodami.

   9.5. Nakonec, v razdele o podgonke stranic horosho by bylo imet'
   kratkoe opisanie togo, chto `eto znachit. YA ne sovsem `eto
   ponyal.

   Znaete li vy, kak rabotaet apparatnyj k`esh pamyati L1?
   Ob"yasnyayu: Predstav'te mashinu s 16MB osnovnoj pamyati i tol'ko
   so 128K pamyati k`esha L1. V obschem, `etot k`esh rabotaet tak,
   chto kazhdyj blok po 128K osnovnoj pamyati ispol'zuet te zhe samye
   128K k`esha. Esli vy obraschaetes' k osnovnoj pamyati po
   smescheniyu 0, a zatem k osnovnoj pamyati po smescheniyu 128K, vy
   perezapisyvaete dannye k`esha, prochtennye po smescheniyu 0!

   YA ochen' sil'no vse uproschayu. To, chto ya tol'ko chto opisal,
   nazyvaetsya ''napryamuyu otobrazhaemym'' apparatnym k`eshem
   pamyati. Bol'shinstvo sovremennyh k`eshej yavlyayutsya tak
   nazyvaemymi 2-storonnimi mnozhestvennymi associativnymi ili
   4-storonnimi mnozhestvennymi associativnymi k`eshami.
   Mnozhestvennaya associativnost' pozvolyaet vam obraschat'sya k
   vplot' do N razlichnym oblastyam pamyati, kotorye ispol'zuyut odnu
   i tu zhe pamyat' k`esha bez unichtozheniya ranee pomeschennyh v
   k`esh dannyh. No tol'ko N.

   Tak chto esli u menya imeetsya 4-storonnij associativnyj k`esh, ya
   mogu obratit'sya k pamyati po smescheniyu 0, smescheniyu 128K,
   256K i smescheniyu 384K, zatem snova obratit'sya k pamyati po
   smescheniyu 0 i poluchu ee iz k`esha L1. Odnako, esli posle `etogo
   ya obraschus' k pamyati po smescheniyu 512K, odin iz ranee
   pomeschennyh v k`esh ob"ektov dannyh budet iz k`esha udalen.

   `Eto chrezvychajno vazhno... dlya bol'shinstva obraschenij k
   pamyati processora chrezvychajno vazhno, chtoby dannye nahodilis'
   v k`eshe L1, tak kak k`esh L1 rabotaet na taktovoj chastote raboty
   processora. V sluchae, esli dannyh v k`eshe L1 ne
   obnaruzhivaetsya, i oni ischutsya v k`eshe L2 ili v osnovnoj
   pamyati, processor budet prostaivat', ili, skoree, sidet', slozhiv
   ruchki, v ozhidanii okonchaniya chteniya iz osnovnoj pamyati,
   hotya za `eto vremya mozhno bylo vypolnit' sotni operacij.
   Osnovnaya pamyat' (dinamicheskoe OZU, kotoroe ustanovleno v
   komp'yutere) rabotaet po sravneniyu so skorost'yu raboty yadra
   sovremennyh processorov medlenno.

   Horosho, a teper' rassmotrim podgonku stranic: Vse sovremennye
   k`eshi pamyati yavlyayutsya tak nazyvaemymi fizicheskimi k`eshami.
   Oni k`eshiruyut adresa fizicheskoj pamyati, a ne virtual'noj. `Eto
   pozvolyaet k`eshu ne prinimat' vo vnimanie pereklyuchenie
   kontekstov processov, chto ochen' vazhno.

   No v mire UNIX vy rabotaete s virtual'nymi adresnymi
   prostranstvami, a ne s fizicheskimi. Lyubaya programma, vami
   napisannaya, imeet delo s virtual'nym adresnym prostranstvom, ej
   predostavlennym. Real'nye fizicheskie stranicy, sootvetstvuyuschie
   virtual'nomu adresnomu prostranstvu, ne obyazatel'no raspolozheny
   fizicheski posledovatel'no! Na samom dele u vas mogut okazat'sya
   dve stranicy, kotorye v adresnom prostranstve processov
   yavlyayutsya granichaschimi, no raspolagayuschimisya po
   smescheniyu 0 i po smescheniyu 128K v fizicheskoj pamyati.

   Obychno programma polagaet, chto dve granichaschie stranicy budut
   k`eshirovat'sya optimal'no. To est' vy mozhete obraschat'sya k
   ob"ektam dannyh v obeih stranicah bez zameschenij v k`eshe dannyh
   drug druga. No `eto imeet mesto, esli tol'ko fizicheskie stranicy,
   sootvetstvuyuschie virtual'nomu adresnomu prostranstvu,
   raspolagayutsya ryadom (v takoj mere, chto popadayut v k`esh).

   `Eto imenno to, chto vypolnyaet podgonka. Vmesto togo, chtoby
   naznachat' sluchajnye fizicheskie stranicy virtual'nym adresam,
   chto mozhet privesti k neoptimal'noj rabote k`esha, pri podgonke
   stranic virtual'nym adresam naznachayutsya primerno podhodyaschie
   po poryadku fizicheskie stranicy. Takim obrazom, programmy mogut
   pisat'sya v predpolozhenii, chto harakteristiki nizlezhaschego
   apparatnogo k`esha dlya virtual'nogo adresnogo prostranstva budut
   takimi zhe, kak esli by programma rabotala neposredstvenno v
   fizicheskom adresnom prostranstve.

   Zamet'te, chto ya skazal ''primerno'' podhodyaschie, a ne prosto
   ''posledovatel'nye''. S tochki zreniya napryamuyu otobrazhaemogo
   k`esha v 128K, fizicheskij adres 0 odinakov s fizicheskim adresom
   128K. Tak chto dve granichaschie stranicy v vashem virtual'nom
   adresnom prostranstve mogut raspolagat'sya po smescheniyu 128K i
   132K fizicheskoj pamyati, no mogut legko nahodit'sya po
   smescheniyu 128K i po smescheniyu 4K fizicheskoj pamyati, i imet'
   te zhe samye harakteristiki raboty k`esha. Tak chto pri podgonke
   ne nuzhno naznachat' v dejstvitel'nosti posledovatel'nye stranicy
   fizicheskoj pamyati posledovatel'nym stranicam virtual'noj
   pamyati, dostatochno prosto dobit'sya raspolozheniya stranic po
   sosedstvu drug s drugom s tochki zreniya raboty k`esha.

     --------------------------------------------------------------

            `Etot, i drugie dokumenty, mogut byt' skachany s
                ftp://ftp.FreeBSD.org/pub/FreeBSD/doc/.

  Po voprosam, svyazannym s FreeBSD, prochitajte dokumentaciyu prezhde
                 chem pisat' v <questions@FreeBSD.org>.
         Po voprosam, svyazannym s `etoj dokumentaciej, pishite
                           <doc@FreeBSD.org>.
  Po voprosam, svyazannym s russkim perevodom dokumentacii, pishite v
                    rassylku <frdp@FreeBSD.org.ua>.
  Informaciya po podpiske na `etu rassylku nahoditsya na sajte proekta
                               perevoda.
