     2     |     2     |     2     |     2
 2|   выгружен   | выгружен  | загружен  | загружен  |
  |       0      |     0     |     0     |     0     |
  |              |           |  запущен  |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      1      |     1     |     1     |     1     |     3
 3|              |           |           |  запущен  |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      2      |     2     |     2     |     2     |     4
 4|   загружен   |           | выгружен  | выгружен  | загружен
  |       0      |           |     0     |     0     |     0
  |              |           |           |           |  запущен
  |              |           |           |           |
  |              |           |           |           |
--+-      1      |     3     |     1     |     1     |     1
 5|    запущен   |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      2      |     4     |     2     |     2     |     2
 6|   выгружен   | загружен  | загружен  |           | выгружен
  |       0      |     0     |     0     |           |     0
  |              |  запущен  |           |           |
  |              |           |           |           |
  v


    ђисунок 9.10.    Џоследовательность   операций,   выполнЯемых
                     процессом подкачки


                                    264


‚ремЯ  Џроцесс A       B           C           D           E
--+--------------+-----------+-----------+-----------+-----------
 0|       0      |     0     | выгружен  |  nice 25  | выгружен
  |    запущен   |           |     0     | выгружен  |     0
  |              |           |           |     0     |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      1      |     1     |     1     |     1     |     1
 1|              |  запущен  |           |           |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      2      |     2     |     2     |     2     |     2
 2|   выгружен   | выгружен  | загружен  | загружен  |
  |       0      |     0     |     0     |     0     |
  |              |           |  запущен  |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      1      |     1     |     1     |     1     |     3
 3|              |           |           | выгружен  | загружен
  |              |           |           |     0     |     0
  |              |           |           |           |  запущен
  |              |           |           |           |
  |              |           |           |           |
--+-      2      |     2     |     2     |     1     |     1
 4|   загружен   |           | выгружен  |           |
  |       0      |           |     0     |           |
  |    запущен   |           |           |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      1      |     3     |     1     |     2     |     2
 5|              | загружен  |           |           | выгружен
  |              |     0     |           |           |     0
  |              |  запущен  |           |           |
  |              |           |           |           |
  |              |           |           |           |
--+-      2      |     1     |     2     |     3     |     1
 6|   выгружен   |           |           | загружен  |
  |       0      |           |           |     0     |
  |              |           |           |  запущен  |
  |              |           |           |           |
  v

    ђисунок 9.11.  ‡агрузка процессов в случае разбивки временных
                   интервалов на части


памЯти находЯтсЯ в состоЯнии приостанова, все готовые к выполнению  процессы
выгружены,  длЯ  новых  процессов  на устройстве выгрузки уже нет места, нет
свободного места и в основной памЯти. ќта ситуациЯ разбираетсЯ в  упражнении
9.5.  €нтерес к проблемам, свЯзанным с подкачкой процессов, в последние годы
спал в свЯзи с реализацией алгоритмов подкачки страниц памЯти.


                                    265

        9.2 ЏЋ„ЉЂ—ЉЂ ЏЋ ‡ЂЏђЋ‘“

    Ђлгоритм подкачки страниц памЯти поддерживаетсЯ на машинах со страничной
организацией памЯти и с –Џ, имеющим прерываемые команды (***). ‚ системах  с
подкачкой  страниц  отсутствуют  ограничениЯ на размер процесса, свЯзанные с
объемом доступной физической памЯти. Ќапример, в машинах с объемом  физичес-
кой  памЯти  1 и 2 Њбайта могут исполнЯтьсЯ процессы размером 4 или 5 Њбайт.
Ћграничение на виртуальный размер процесса, свЯзанное с  объемом  адресуемой
виртуальной  памЯти, остаетсЯ в силе и здесь. Џоскольку процесс может не по-
меститьсЯ в физической памЯти, Ядру приходитсЯ динамически загружать  в  па-
мЯть  отдельные  его  части и исполнЯть их, несмотрЯ на отсутствие остальных
частей. ‚ механизме подкачки страниц все открыто длЯ пользовательских  прог-
рамм, за исключением разрешенного процессу виртуального размера.
    Џроцессы стремЯтсЯ исполнЯть команды небольшими порциЯми, которые имену-
ютсЯ  программными  циклами  или  подпрограммами, используемые ими указатели
группируютсЯ в небольшие поднаборы, располагаемые в информационном простран-
стве процесса. ‚ этом состоит суть так называемого  принципа  "локальности".
„еннингом  [Denning  68] было сформулировано понЯтие рабочего множества про-
цесса как совокупности страниц, использованных процессом в последних n ссыл-
ках на адресное пространство памЯти; число n называетсЯ окном рабочего  мно-
жества.  Џоскольку  рабочее  множество процесса ЯвлЯетсЯ частью от целого, в
основной памЯти может поместитьсЯ больше процессов по сравнению с теми  сис-
темами,  где  управление памЯтью базируетсЯ на подкачке процессов, что в ко-
нечном итоге приводит к увеличению производительности системы. Љогда процесс
обращаетсЯ к странице, отсутствующей  в  его  рабочем  множестве,  возникает
ошибка,  при обработке которой Ядро корректирует рабочее множество процесса,
в случае необходимости подкачиваЯ страницы с внешнего устройства.
    Ќа ђисунке 9.12 приведена последовательность используемых процессом ука-
зателей страниц, описывающих рабочие множества с окнами  различных  размеров
при условии соблюдениЯ алгоритма замещениЯ "стариков" (замещениЯ страниц пу-
тем откачки тех, к которым наиболее долго не было обращений). Џо мере выпол-
нениЯ процесса его рабочее множество видоизменЯетсЯ в соответствии с исполь-
зуемыми процессом указателЯми страниц; увеличение размера окна влечет за со-
бой увеличение рабочего множества и, с другой стороны, сокращение числа оши-
бок  в  выполнении процесса. €спользование неизменного рабочего множества не
практикуетсЯ, поскольку запоминание очередности следованиЯ указателей  стра-
ниц потребовало бы слишком больших затрат. Џриблизительное соответствие меж-
ду  изменЯемым рабочим множеством и пространством процесса достигаетсЯ путем
установки бита упоминаниЯ (reference bit) при обращении к странице памЯти, а
также периодическим опросом указателей страниц. …сли на страницу была сдела-
на ссылка, эта страница включаетсЯ в рабочее множество; в  противном  случае
она "дозревает" в памЯти в ожидании своей очереди.
    ‚  случае возникновениЯ ошибки из-за обращениЯ к странице, отсутствующей
в рабочем множестве, Ядро приостанавливает выполнение процесса до  тех  пор,
пока страница не будет считана в памЯть и не станет доступной процессу. Љог-
да страница будет загружена, процесс перезапустит ту команду, на которой вы-
полнение  процесса  было  приостановлено из-за ошибки. ’аким образом, работа
подсистемы замещениЯ страниц распадаетсЯ на две части: откачка редко исполь-
зуемых страниц на устройство выгрузки и обработка  ошибок  из-за  отсутствиЯ
нужной страницы. ’акое общее толкование механизма замещениЯ страниц, конечно
же,  выходит  за пределы одной конкретной системы. ЋставшуюсЯ часть главы мы
посвЯтим более детальному рассмотрению особенностей реализации  этого  меха-
низма в версии V системы UNIX.

---------------------------------------
(***)  …сли при исполнении команды возникает ошибка, свЯзаннаЯ с отсутствием
      страницы, после обработки ошибки –Џ обЯзан перезапустить команду, пос-
      кольку промежуточные результаты, полученные  к  моменту  возникновениЯ
      ошибки, могут быть утрачены.

                                    266


        9.2.1 ‘труктуры данных, используемые подсистемой замещениЯ страниц

    „лЯ  поддержки  функций управлениЯ памЯтью на машинном (низком) уровне и
длЯ реализации механизма замещениЯ страниц Ядро использует 4 основные струк-
туры данных: записи таблицы страниц, дескрипторы  дисковых  блоков,  таблицу
содержимого страничных блоков (page frame data table - сокращенно: pfdata) и
таблицу  использованиЯ области подкачки. Њесто длЯ таблицы pfdata выделЯетсЯ
один раз на все времЯ жизни системы, длЯ других же структур страницы  памЯти
выделЯютсЯ динамически.
    €з главы 6 нам известно, что каждаЯ область располагает своими таблицами
страниц, с помощью которых осуществлЯетсЯ доступ к физической памЯти. ЉаждаЯ
запись  таблицы страниц (ђисунок 9.13) состоит из физического адреса страни-
цы, кода защиты, в разрЯдах которого описываютсЯ права  доступа  процесса  к
странице (на чтение, запись и исполнение), а также следующих двоичных полей,
используемых механизмом замещениЯ страниц:

Џоследователь-
ность указате-       ђабочие множества     ђазмеры окон
лей   страниц      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 |      -      |        -       |
+------------+ +-------+----------+-------------+----------------+

            ђисунок 9.12. ђабочее множество процесса


  * бит доступности
  * бит упоминаниЯ

                                    267

  * бит модификации
  * бит копированиЯ при записи
  * "возраст" страницы
    “становка  бита  доступности  свидетельствует о правильности содержимого
страницы памЯти, однако из того, что бит доступности выключен, не следует  с
необходимостью  то,  что  ссылка  на страницу недопустима, в чем мы убедимсЯ
позже. Ѓит упоминаниЯ устанавливаетсЯ в  том  случае,  если  процесс  делает
ссылку  на страницу, а бит модификации - в том случае, если процесс скоррек-
тировал содержимое страницы. “становка бита копированиЯ при записи, произво-
димаЯ во времЯ выполнениЯ системной функции fork, свидетельствует о том, что
Ядру в случае, когда процесс корректирует содержимое страницы, следует  соз-
давать  ее  новую копию. Ќаконец, "возраст" страницы говорит о продолжитель-
ности ее пребываниЯ в составе рабочего множества процесса. Ѓиты доступности,
копированиЯ при записи и "возраст" страницы устанавливаютсЯ Ядром, биты упо-
минаниЯ и модификации - аппаратным путем; в  разделе  9.2.4  рассматриваютсЯ
конфигурации, в которых эти возможности не поддерживаютсЯ аппаратурой.

+--------+ +->+----------------------+---------------------------+
|        | |  |                      |                           |
|        | |  +----------------------+---------------------------+
|        | |  |                      |                           |
|        | |  +----------------------+---------------------------+
| Ћбласть| |  |                      |                           |
|        | |  +----------------------+---------------------------+
|        | |  |‡аписи таблицы страниц|„ескрипторы дисковых блоков|
|    ----+-+  +----------------------+---------------------------+
|        |    |                      |                           |
|        |    +----------------------+---------------------------+
|        |    |                      |                           |
+--------+    +----------------------+---------------------------+
              |                      |                           |
              +----------------------+---------------------------+
              |                      |                           |
              +----------------------+---------------------------+
              |                      |                           |
              +----------------------+---------------------------+
              |                      |                           |
              +----------------------+---------------------------+

                     ‡апись таблицы страниц
+-----------------------------+-------+-----+-----+----+-----+---+
| Ђдрес страницы (физический) |‚озраст|Љопи-|Њоди-|“по-|„о-  |‡а-|
|                             |       |рова-|фика-|ми- |пус- |щи-|
|                             |       |ние  |циЯ  |на- |ти-  |та |
|                             |       |при  |     |ние |мость|   |
|                             |       |запи-|     |    |     |   |
|                             |       |си   |     |    |     |   |
+-----------------------------+-------+-----+-----+----+-----+---+

                   „ескриптор дискового блока
+-----------------------+---------------+------------------------+
|  “стройство выгрузки  |  Ќомер блока  | ’ип (находитсЯ на ус-  |
|                       |               | тройстве выгрузки, в   |
|                       |               | файле, при обращении   |
|                       |               | обнулЯетсЯ, заполнЯет- |
|                       |               | сЯ)                    |
+-----------------------+---------------+------------------------+

    ђисунок 9.13. ‡аписи таблицы страниц и дескрипторы дисковых блоков

                                    268

    ЉаждаЯ  запись  таблицы  страниц свЯзана с дескриптором дискового блока,
описывающим дисковую копию виртуальной страницы (ђисунок 9.13). Џоэтому про-
цессы, использующие разделЯемую область, обращаютсЯ к общим записЯм  таблицы
страниц  и  к одним и тем же дескрипторам дисковых блоков. ‘одержимое вирту-
альной страницы располагаетсЯ либо в отдельном блоке на устройстве выгрузки,
либо в исполнЯемом файле, либо вообще отсутствует  на  устройстве  выгрузки.
…сли страница находитсЯ на устройстве выгрузки, в дескрипторе дискового бло-
ка  содержитсЯ  логический  номер устройства и номер блока, по которым можно
отыскать содержимое страницы. …сли страница содержитсЯ в исполнЯемом  файле,
в  дескрипторе дискового блока располагаетсЯ номер логического блока в файле
с содержимым страницы; Ядро может быстро преобразовать этот номер в адрес на
диске. ‚ дескрипторе дискового блока также имеетсЯ информациЯ о  двух  уста-
навливаемых  функцией exec особых условиЯх: страница при обращении к ней за-
полнЯетсЯ ("demand fill") или обнулЯетсЯ  ("demand  zero").  ђазъЯснениЯ  по
этому поводу даютсЯ в разделе 9.2.1.2.
    ‚  таблице  pfdata описываетсЯ каждаЯ страница физической памЯти. ‡аписи
таблицы проиндексированы по номеру страницы и состоЯт из следующих полей:
  * ‘татус страницы, указывающий на то, что страница располагаетсЯ  на  уст-
    ройстве выгрузки или в исполнЯемом файле, что к странице произведено об-
    ращение  по прЯмому доступу в памЯть (путем считываниЯ информации с уст-
    ройства выгрузки), или на то, что страница может быть переназначена.
  * Љоличество процессов, ссылающихсЯ на  страницу.  ‘четчик  ссылок  хранит
    число записей в таблице страниц, имеющих ссылку на текущую страницу. ќто
    значение может отличатьсЯ от количества процессов, использующих разделЯ-
    емую область с данной страницей, в чем мы убедимсЯ чуть позже, когда бу-
    дем снова обращатьсЯ к алгоритму функции fork.
  * ‹огический номер устройства (устройства выгрузки или файловой системы) и
    номер блока, указывающие расположение содержимого страницы.
  * “казатели на другие записи таблицы pfdata в соответствии со списком сво-
    бодных страниц или с хеш-очередью страниц.
    Џо аналогии с буферным кешем Ядро свЯзывает записи таблицы pfdata в спи-
сок  свободных  страниц и хеш-очередь. ‘писок свободных страниц представлЯет
собой буфер, который содержит страницы, доступные длЯ переназначениЯ, однако
процесс, обратившийсЯ к этим страницам, может столкнутьсЯ с ошибкой  адреса-
ции,  так  и не получив соответствующую страницу из списка. ќтот список дает
Ядру возможность сократить число операций чтениЯ с устройства выгрузки. џдро
выделЯет страницы из этого списка по вышеназванному принципу замещениЯ "ста-
риков". џдро выстраивает записи таблицы в хеш-очередь в соответствии с номе-
ром устройства (выгрузки) и номером блока. €спользуЯ эти номера, Ядро  может
быстро  отыскать страницу, если она находитсЯ в памЯти. ЏередаваЯ физическую
страницу области, Ядро выбирает соответствующую запись из  списка  свободных
страниц,  исправлЯет указанные в ней номера устройства и блока и помещает ее
в соответствующее место хеш-очереди.
    ЉаждаЯ запись таблицы использованиЯ области подкачки соответствует стра-
нице, находЯщейсЯ на устройстве выгрузки. ‡апись  содержит  счетчик  ссылок,
показывающий количество записей таблицы страниц, в которых имеетсЯ ссылка на
текущую страницу.
    Ќа  ђисунке  9.14  показана  взаимосвЯзь между записЯми таблицы страниц,
дескрипторами дисковых блоков, записЯми таблицы pfdata и таблицы использова-
ниЯ области подкачки. ‚иртуальный адрес 1493Љ отображаетсЯ на запись таблицы
страниц, соответствующую странице с физическим номером 794; дескриптор  дис-
кового  блока, свЯзанный с этой записью, свидетельствует о том, что содержи-
мое страницы располагаетсЯ на устройстве выгрузки с  номером  1  в  дисковом
блоке  с  номером 2743. ‡апись таблицы pfdata, помимо того, что указывает на
те же номера устройства и блока, сообщает, что счетчик ссылок на  физическую
страницу  имеет значение, равное 1. Ћ том, почему номер дискового блока дуб-
лируетсЯ в записи таблицы pfdata, вы узнаете  из  раздела  9.2.4.1.  ‘четчик
ссылок  на виртуальную страницу (в записи таблицы использованиЯ области под-
качки) свидетельствует о том, что на копию страницы на  устройстве  выгрузки

                                    269

ссылаетсЯ только одна запись таблицы страниц.


        9.2.1.1 ”ункциЯ fork в системе с замещением страниц

    Љак  уже говорилось в разделе 7.1, во времЯ выполнениЯ функции fork Ядро
создает копию каждой области родительского процесса и присоединЯет ее к про-
цессу-потомку. ‚ системе с замещением стра-

             +-----------------------+--------------------------+
‚иртуальный  |‡апись таблицы  страниц|„ескриптор дискового блока|
   адрес     +-----------------------+--------------------------+
   1493Љ     |   Ќомер страницы 794  | “стройство 1   Ѓлок 2743 |
             +---+-+-----------------+--------------------+-----+
                 | |                                      |
                 | | ‡апись таблицы pfdata,               |
                 | | соответствующаЯ стра-   +------------+
    +------------+ v нице с номером 794      |
    | +------------+-----------------------+ |
    | |            | ‘четчик ссылок      1 | |  ‡апись таблицы
    | |            +-----------------------+ |  использованиЯ
    | |            | Ќомер устройства    1 | |  области подкачки
    | |            +-----------------------+ | +-----------------+
    | |            | Ќомер блока      2743 | | |‘четчик ссылок  1|
    | |            +-----------------+-----+ | +--------+--------+
    | |                              | +-----+          |
    | |                              | | +--------------+
    v v                              v v v
    +--------------------------+     +---------------------------+
    | ”изическаЯ страница  794 |     | Ќомер блока          2743 |
    +--------------------------+     +---------------------------+

    ђисунок 9.14. ‚заимосвЯзь между структурами данных, участвующими в  реа-
                  лизации механизма замещениЯ страниц по обращению

ниц Ядро по традиции создает физическую копию адресного пространства процес-
са-родителЯ,  что в общем случае ЯвлЯетсЯ довольно расточительной операцией,
поскольку процесс часто после выполнениЯ функции fork обращаетсЯ  к  функции
exec  и  незамедлительно  освобождает только что скопированное пространство.
…сли область разделЯемаЯ, в версии V вместо копированиЯ страницы Ядро просто
увеличивает значение счетчика ссылок на область (в таблице областей, в  таб-
лице  страниц и в таблице pfdata). ’ем не менее, длЯ частных областей, таких
как область данных и стека, Ядро отводит в таблице областей и таблице  стра-
ниц новую запись, после чего просматривает в таблице страниц все записи про-
цесса-родителЯ: если запись верна, Ядро увеличивает значение счетчика ссылок
в таблице pfdata, отражающее количество процессов, использующих страницу че-
рез  разные  области  (в отличие от тех процессов, которые используют данную
страницу через разделЯемую область). …сли страница располагаетсЯ на устройс-
тве выгрузки, Ядро увеличивает значение счетчика ссылок в таблице  использо-
ваниЯ области подкачки.
    ’еперь на страницу могут ссылатьсЯ обе области, использующие эту страни-
цу совместно, пока процесс не ведет на нее запись. Љак только страница пона-
добитсЯ  процессу  длЯ  записи, Ядро создаст ее копию, с тем, чтобы у каждой
области была своЯ личнаЯ версиЯ страницы. „лЯ этого при  выполнении  функции
fork в каждой записи таблицы страниц, соответствующей частным областЯм роди-
телЯ  и  потомка, Ядро устанавливает бит "копированиЯ при записи". …сли один
из процессов попытаетсЯ что-то записать на страницу, он получит отказ систе-
мы защиты, после чего длЯ него будет создана новаЯ копиЯ содержимого страни-
цы. ’аким образом, физическое копирование страницы откладываетсЯ до того мо-

                                    270

мента, когда в этом возникнет реальнаЯ потребность.
    ‚ качестве примера рассмотрим ђисунок 9.15. Џроцессы разделЯют доступ  к
таблице  страниц  совместно  используемой области команд T, поэтому значение
счетчика ссылок на область равно 2, а на страницы области единице (в таблице
pfdata). џдро назначает про-

           Џроцесс-родитель           Џроцесс-потомок

            —астнаЯ таблица            —астнаЯ таблица
           областей процесса          областей процесса
           +--------------+           +--------------+
           | -            |           | -            |
           +--------------+           +--------------+
           | -          - |           | -          - |
           +--------------+           +--------------+
             -   + ---------------------+          -
             -   -      -                          -
             v   v      v                          v
+-------------------+ +-------------------+ +-------------------+
|     Ћбласть T     | |     Ћбласть P1    | |     Ћбласть C1    |
| ‘четчик ссылок  2 | | ‘четчик ссылок  1 | | ‘четчик ссылок  1 |
|+-----------------+| |+-----------------+| |+-----------------+|
||  ‡аписи таблицы || ||  ‡аписи таблицы || ||  ‡аписи таблицы ||
||     страниц     || ||     страниц     || ||     страниц     ||
|+-----------------+| |+-----------------+| |+-----------------+|
||        -        || ||        -        || ||        -        ||
||        -        || ||        -        || ||        -        ||
|+-----------------+| ||        -        || ||        -        ||
||‚иртуаль-   ‘тра-|| ||        -        || ||        -        ||
||ный адрес   ница || ||        -        || ||        -        ||
||  24Љ        967 || ||        -        || ||        -        ||
|+-----------------+| |+-----------------+| |+-----------------+|
||        -     -  || ||‚иртуаль-   ‘тра-|| ||‚иртуаль-   ‘тра-||
||        -     -  || ||ный адрес   ница || ||ный адрес   ница ||
||        -     -  || ||  97Љ        613 || ||  97Љ        613 ||
||        -     -  || |+-----------------+| |+-----------------+|
||        -     -  || ||        -     -  || ||        -     -  ||
||        -     -  || ||        -     -  || ||        -     -  ||
|+-----------------+| |+-----------------+| |+-----------------+|
+-------------------+ +-------------------+ +-------------------+
                -                     -           -----------
                v                     v           v
+---------------------+         +---------------------+
| ‘траничный блок 967 |         | ‘траничный блок 613 |
| ‘четчик ссылок    1 |         | ‘четчик ссылок    2 |
+---------------------+         +---------------------+

    ђисунок 9.15.  ЂдресациЯ страниц,  участвующих в процессе вы-
                   полнениЯ функции fork


цессу-потомку новую область данных C1, ЯвлЯющуюсЯ копией области P1  процес-
са-родителЯ. Ћбе области используют одни и те же записи таблицы страниц, это
видно на примере страницы с виртуальным адресом 97Љ. ќтой странице в таблице
pfdata соответствует запись с номером 613, счетчик ссылок в которой равен 2,
ибо на страницу ссылаютсЯ две области.
    ‚  ходе выполнениЯ функции fork в системе BSD создаетсЯ физическаЯ копиЯ
страниц родительского процесса. Ћднако, учитываЯ наличие ситуаций, в которых
создание физической копии не ЯвлЯетсЯ обЯзательным, в системе BSD существует

                                    271

также функциЯ vfork, котораЯ используетсЯ в том случае, если  процесс  сразу
по  завершении функции fork собираетсЯ запустить функцию exec. ”ункциЯ vfork
не копирует таблицы страниц, поэтому она работает быстрее, чем функциЯ  fork
в  версии  V системы UNIX. Ћднако процесс-потомок при этом исполнЯетсЯ в тех
же самых физических адресах, что и его родитель, и  может  поэтому  затереть
данные  и  стек  родительского процесса. …сли программист использует функцию
vfork неверно, может возникнуть опаснаЯ ситуациЯ,  поэтому  всЯ  ответствен-
ность за ее использование возлагаетсЯ на программиста. ђазличие в подходах к
рассматриваемому  вопросу  в системах UNIX и BSD имеет философский характер,
они дают разный ответ на один и тот же вопрос: следует ли Ядру скрывать осо-
бенности реализации своих функций, превращаЯ их в тайну  длЯ  пользователей,
или  же  стоит дать опытным пользователЯм возможность повысить эффективность
выполнениЯ системных операций ?

    +------------------------------------------------------------+
    | int global;                                                |
    | main()                                                     |
    | {                                                          |
    |     int local;                                             |
    |                                                            |
    |     local = 1;                                             |
    |     if (vfork() == 0)                                      |
    |     {                                                      |
    |         /* потомок */                                      |
    |         global = 2;  /* запись в область данных родителЯ */|
    |         local = 3;   /* запись в стек родителЯ */          |
    |         _exit();                                           |
    |     }                                                      |
    |     printf("global %d local %d\n",global,local);           |
    | }                                                          |
    +------------------------------------------------------------+

     ђисунок 9.16. ”ункциЯ vfork и искажение информации процесса

    ‚ качестве примера рассмотрим программу, приведенную  на  ђисунке  9.16.
Џосле  выполнениЯ функции vfork процесс-потомок не запускает функцию exec, а
переустанавливает значениЯ переменных global и local и  завершаетсЯ  (****).
‘истема  гарантирует, что процесс-родитель приостанавливаетсЯ до того момен-
та, когда потомок исполнит функции exec или exit. ‚озобновив в конечном ито-
ге свое выполнение, процесс-родитель обнаружит, что значениЯ двух его  пере-
менных  не  совпадают  с  теми значениЯми, которые были у них до обращениЯ к
функции vfork ! …ще больший эффект может произвести возвращение процесса-по-
томка из функции, вызвавшей функцию vfork (см. упражнение 9.8).


        9.2.1.2 ”ункциЯ exec в системе с замещением страниц

    Љак уже говорилось в главе 7, когда процесс обращаетсЯ к системной функ-
ции exec, Ядро считывает из файловой системы в памЯть указанный  исполнЯемый
файл.  Ћднако  в  системе  с замещением страниц по запросу исполнЯемый файл,

---------------------------------------
(****) ”ункциЯ exit используетсЯ в варианте _exit, потому что она  "очищает"
       структуры данных, передаваемые через стандартный ввод-вывод (на поль-
       зовательском  уровне),  длЯ обоих процессов, так что оператор printf,
       используемый родителем, не даст правильный результат - еще один неже-
       лательный побочный эффект от применениЯ функции vfork.


                                    272

имеющий большой размер, может не уместитьсЯ в доступном пространстве  основ-
ной  памЯти. Џоэтому Ядро не назначает ему сразу все пространство, а отводит
место в памЯти по мере надобности.  ‘начала  Ядро  назначает  файлу  таблицы
страниц и дескрипторы дисковых блоков, помечаЯ страницы в записЯх таблиц как
"заполнЯемые  при  обращении"  (длЯ  всех данных, кроме имеющих тип bss) или
"обнулЯемые при обращении" (длЯ данных типа bss). ‘читываЯ в  памЯть  каждую
страницу  файла  по алгоритму read, процесс получает ошибку из-за отсутствиЯ
(недоступности) данных. Џодпрограмма обработки ошибок проверЯет, ЯвлЯетсЯ ли
страница "заполнЯемой при обращении" (тогда ее содержимое  будет  немедленно
затиратьсЯ  содержимым  исполнЯемого файла и поэтому ее не надо очищать) или
"обнулЯемой при обращении" (тогда ее следует очистить). ‚ разделе  9.2.3  мы
увидим,  как  это  происходит.  …сли  процесс не может поместитьсЯ в памЯти,
"сборщик" страниц освобождает длЯ него место, периодически откачиваЯ из  па-
мЯти неиспользуемые страницы.
    ‚  этой схеме видны Явные недостатки. ‚о-первых, при чтении каждой стра-
ницы исполнЯемого файла процесс сталкиваетсЯ с ошибкой из-за обращениЯ к от-
сутствующей странице, пусть даже процесс  никогда  и  не  обращалсЯ  к  ней.
‚о-вторых,  если  после того, как "сборщик" страниц откачал часть страниц из
памЯти, была запущена функциЯ exec, каждаЯ только что  выгруженнаЯ  и  вновь
понадобившаЯсЯ  страница  потребует  дополнительную операцию по ее загрузке.
—тобы повысить эффективность функции exec, Ядро может востребовать  страницу
непосредственно  из  исполнЯемого файла, если данные в файле соответствующим
образом настроены, что определЯетсЯ значением т.н. "магического числа".  Ћд-
нако,  использование стандартных алгоритмов доступа к файлу (например, bmap)
потребовало бы при обращении к странице, состоЯщей из блоков косвенной адре-
сации, больших затрат, свЯзанных с многократным использованием буферного ке-
ша длЯ чтениЯ каждого блока. Љроме того, функциЯ bmap не ЯвлЯетсЯ  реентера-
бельной,  отсюда  возникает опасность нарушениЯ целостности данных. ‚о времЯ
выполнениЯ системной функции read Ядро устанавливает в пространстве процесса
значениЯ различных параметров ввода-вывода.  …сли  при  попытке  скопировать
данные  в  пространство пользователЯ процесс столкнетсЯ с отсутствием нужной
страницы, он, считываЯ страницу из файловой системы, может затереть содержа-
щие эти параметры полЯ. Џоэтому Ядро  не  может  прибегать  к  использованию
обычных алгоритмов обработки ошибок данного рода. Љонечно же алгоритмы долж-
ны  быть  в  обычных  случаЯх реентерабельными, поскольку у каждого процесса
свое отдельное адресное пространство и процесс не может одновременно  испол-
нЯть несколько системных функций.
    „лЯ  того, чтобы считывать страницы непосредственно из исполнЯемого фай-
ла, Ядро во времЯ исполнениЯ функции exec составлЯет список номеров дисковых
блоков файла и присоединЯет этот список к индексу файла. ђаботаЯ с таблицами
страниц такого файла, Ядро находит дескриптор дискового  блока,  содержащего
страницу,  и запоминает номер блока внутри файла; этот номер позже использу-

                                               ‘писок блоков,
                  Ћбласть               +-> свЯзанный с индексом
    +---------------------------------+ |    +----------------+
    |                €ндекс-----------+-+  0 |                |
    |                                 |    - |                |
    |                                 |    - |                |
    |   „ескриптор дискового блока    |    - |                |
    |  +---------------------------+  |    - |                |
    |  | ‹огический блок        84 |  |    - +----------------+
    |  +---------------------------+  |   84 |       279      |
    |                                 |      +----------------+
    +---------------------------------+      |                |
                                             |                |
                                             +----------------+

            ђисунок 9.17. Ћтображение файла на область

                                    273

етсЯ при загрузке страницы из файла. Ќа ђисунке 9.17 показан пример, в кото-
ром страница имеет адрес расположениЯ в логическом блоке с номером 84 от на-
чала файла. ‚ области имеетсЯ указатель на индекс, в котором содержитсЯ  но-
мер соответствующего физического блока на диске (279).


        9.2.2 "‘борщик" страниц

    "‘борщик"  страниц (page stealer) ЯвлЯетсЯ процессом, принадлежащим Ядру
операционной системы и выполнЯющим выгрузку из памЯти тех  страниц,  которые
больше  не  входЯт  в  состав рабочего множества пользовательского процесса.
ќтот процесс создаетсЯ Ядром во времЯ инициализации системы и запускаетсЯ  в
любой  момент, когда в нем возникает необходимость. Ћн просматривает все ак-
тивные незаблокированные области и увеличивает  значение  "возраста"  каждой
принадлежащей им страницы (заблокированные области пропускаютсЯ, но впослед-
ствии, по снЯтии блокировки, тоже будут учтены). Љогда процесс при работе со
страницей,  принадлежащей  области, получает ошибку, Ядро блокирует область,
чтобы "сборщик" не смог выгрузить страницу до тех пор, пока ошибка не  будет
обработана.
    ‘траница  в памЯти может находитьсЯ в двух состоЯниЯх: либо "дозревать",
не будучи еще готовой к выгрузке, либо быть готовой к выгрузке  и  доступной
длЯ  привЯзки к другим виртуальным страницам. Џервое состоЯние означает, что
процесс обратилсЯ к странице и поэтому страница включена в его рабочее  мно-
жество.  Џри обращении к странице в некоторых машинах аппаратно устанавлива-
етсЯ бит упоминаниЯ, если же эта операциЯ не выполнЯетсЯ, соответственно,  и
программные  методы  скорее  всего  используютсЯ другие (раздел 9.2.4). …сли
страница находитсЯ в первом состоЯнии, "сборщик" сбрасывает бит упоминаниЯ в
ноль, но запоминает количество просмотров множества страниц,  выполненных  с
момента последнего обращениЯ к странице со стороны пользовательского процес-
са.  ’аким образом, первое состоЯние распадаетсЯ на несколько подсостоЯний в
соответствии с тем, сколько раз "сборщик" страниц обратилсЯ  к  странице  до
того,  как страница стала готовой длЯ выгрузки (см. ђисунок 9.18). Љогда это
число превышает некоторое пороговое значение,  Ядро  переводит  страницу  во
второе  состоЯние  - состоЯние готовности к выгрузке. ЊаксимальнаЯ продолжи-
тельность пребываниЯ страницы в первом состоЯнии зависит от условий конкрет-
ной реализации и ограничиваетсЯ числом отведенных длЯ этого полЯ разрЯдов  в
записи таблицы страниц.
    Ќа ђисунке 9.19 показано взаимодействие между процессами, работающими со
страницей,  и "сборщиком" страниц. –ифры обозначают номер обращениЯ "сборщи-

                        ‘сылка на страницу
    +------------+----------+----------+-----------------+
    |            ^          ^          ^                 |
    v            |          |          |                 | ѓотов-
+-------+        |          |          |                 | ность
| ‘тра- |      +-+-+      +-+-+      +-+-+             +-+-+ к
| ница в|----->| 1 +----->| 2 +----->| 3 +----­­­­---->| n | вы-
| памЯти|      +---+      +---+      +---+             +-+-+ груз-
+-------+      "„озревание" страницы --- отсутствие      |   ке
    ^                        ссылок                      |
    |                                                    |
    |                       +--------+                   |
    |                       | ‘трани-|                   |
‡а- +-----------------------| ца вы- |<------------------+ ‚ыгруз-
грузка                      | гружена|                     ка
                            +--------+

            ђисунок 9.18. „иаграмма состоЯний страницы

                                    274


ка" к странице с того момента, как страни-
ца была загружена в памЯть. Џроцесс, обратившийсЯ к странице  после  второго
просмотра страниц "сборщиком", сбросил ее "возраст" в 0. Џосле каждого прос-
мотра пользовательский процесс обращалсЯ к странице вновь, но в конце концов
"сборщик" страниц осуществил три просмотра страницы с момента последнего об-
ращениЯ к ней со стороны пользовательского процесса и выгрузил ее из памЯти.
    …сли  область используетсЯ совместно не менее, чем двумЯ процессами, все
они работают с битами упоминаниЯ в одном и том  же  наборе  записей  таблицы
страниц.  ’аким  образом, страницы могут включатьсЯ в рабочие множества нес-
кольких процессов, но длЯ "сборщика" страниц это не имеет никакого значениЯ.
…сли страница включена в рабочее множество хотЯ бы одного из процессов,  она
остаетсЯ  в памЯти; в противном случае она может быть выгружена. Ќичего, что
одна область, к примеру, имеет в памЯти страниц больше,  чем  имеют  другие:
"сборщик"  страниц  не  пытаетсЯ выгрузить равное количество страниц из всех
активных областей.
    џдро возобновлЯет работу "сборщика" страниц, когда доступнаЯ  в  системе
свободнаЯ памЯть имеет размер, не дотЯгивающий до нижней допустимой отметки,
и  тогда "сборщик" производит откачку страниц до тех пор, пока объем свобод-
ной памЯти не превысит верхнюю отметку. Џри использовании двух отметок коли-
чество производимых операций сокращаетсЯ, ибо если  Ядро  использует  только
одно  пороговое  значение, оно будет выгружать достаточное число страниц длЯ
освобождениЯ памЯти свыше порогового значениЯ, но в  результате  возвращениЯ
ошибочно  выгруженных страниц в памЯть размер свободного пространства вскоре
вновь опуститсЯ ниже этого порога. Ћбъем свободной памЯти при этом постоЯнно
бы поддерживалсЯ около пороговой отметки. ‚ыгрузка страниц  с  освобождением
памЯти в объеме, превышающем верхнюю отметку, откладывает момент, когда объ-
ем свободной памЯти в сист