Оцените этот текст





    В  системе  разделения времени ядро предоставляет процессу ресурсы цент-
рального процессора (ЦП) на интервал времени, называемый квантом, по истече-
нии которого выгружает этот процесс и запускает другой, периодически  переу-
порядочивая  очередь  процессов.  Алгоритм  планирования процессов в системе
UNIX использует время выполнения в качестве параметра. Каждый активный  про-
цесс  имеет  приоритет  планирования; ядро переключает контекст на процесс с
наивысшим приоритетом. При переходе выполняющегося процесса из режима ядра в
режим задачи ядро пересчитывает его приоритет, периодически и в режиме зада-
чи переустанавливая приоритет каждого процесса, готового к выполнению.
    Информация о времени, связанном с выполнением, нужна также  и  некоторым
из пользовательских процессов: используемая ими, например, команда time поз-
воляет  узнать,  сколько времени занимает выполнение другой команды, команда
date выводит текущую дату и время суток. С помощью различных системных функ-
ций процессы могут устанавливать или получать временные  характеристики  вы-
полнения в режиме ядра, а также степень загруженности центрального процессо-
ра. Время в системе поддерживается с помощью аппаратных часов, которые посы-
лают  ЦП  прерывания  с  фиксированной, аппаратно-зависимой частотой, обычно
50-100 раз в секунду. Каждое поступление прерывания по таймеру (часам)  име-
нуется таймерным тиком. В настоящей главе рассматриваются особенности реали-
зации  процессов  во времени, включая планирование процессов в системе UNIX,
описание связанных со временем системных функций, а также функций, выполняе-
мых программой обработки прерываний по таймеру.




    Планировщик процессов в системе UNIX принадлежит к общему классу  плани-
ровщиков,   работающих  по  принципу  "карусели  с  многоуровневой  обратной
связью". В соответствии с этим принципом ядро предоставляет процессу ресурсы
ЦП на квант времени, по истечении которого выгружает этот процесс и  возвра-
щает  его  в  одну из нескольких очередей, регулируемых приоритетами. Прежде
чем процесс завершится, ему может потребоваться множество раз  пройти  через
цикл  с обратной связью. Когда ядро выполняет переключение контекста и восс-
танавливает контекст процесса, процесс возобновляет выполнение с точки  при-
останова.



    Сразу  после переключения контекста ядро запускает алгоритм планирования
выполнения процессов (Рисунок 8.1), выбирая на выполнение процесс с  наивыс-
шим приоритетом среди процессов, находящихся в состояниях "резервирования" и
"готовности  к  выполнению, будучи загруженным в память". Рассматривать про-
цессы, не загруженные в память, не имеет смысла, поскольку не будучи  загру-
жен, процесс не может выполняться. Если наивысший приоритет имеют сразу нес-
колько  процессов, ядро, используя принцип кольцевого списка (карусели), вы-
бирает среди них тот процесс, который находится в  состоянии  "готовности  к
выполнению" дольше остальных. Если ни один из процессов не может быть выбран
для  выполнения,  ЦП простаивает до момента получения следующего прерывания,
которое произойдет не позже чем через один таймерный  тик;  после  обработки
этого прерывания ядро снова запустит алгоритм планирования.


                                    232

    +------------------------------------------------------------+
    | алгоритм schedule_process                                  |
    | входная информация:  отсутствует                           |
    | выходная информация: отсутствует                           |
    | {                                                          |
    |    выполнять пока (для запуска не будет выбран один из про-|
    |     цессов)                                                |
    |    {                                                       |
    |       для (каждого процесса в очереди готовых к выполнению)|
    |           выбрать процесс с наивысшим приоритетом из загру-|
    |            женных в память;                                |
    |       если (ни один из процессов не может быть избран для  |
    |        выполнения)                                         |
    |           приостановить машину;                            |
    |           /* машина выходит из состояния простоя по преры- |
    |           /* ванию                                         |
    |            */                                              |
    |    }                                                       |
    |    удалить выбранный процесс из очереди готовых к выполне- |
    |     нию;                                                   |
    |    переключиться на контекст выбранного процесса, возобно- |
    |     вить его выполнение;                                   |
    | }                                                          |
    +------------------------------------------------------------+

       Рисунок 8.1. Алгоритм планирования выполнения процессов






    В  каждой  записи  таблицы  процессов есть поле приоритета, используемое
планировщиком процессов. Приоритет процесса в режиме задачи зависит от того,
как этот процесс перед этим использовал ресурсы ЦП. Можно выделить два клас-
са приоритетов процесса (Рисунок 8.2): приоритеты выполнения в режиме ядра и
приоритеты выполнения в режиме задачи. Каждый класс включает в себя ряд зна-
чений, с каждым значением логически ассоциирована некоторая очередь  процес-
сов. Приоритеты выполнения в режиме задачи оцениваются для процессов, выгру-
женных по возвращении из режима ядра в режим задачи, приоритеты выполнения в
режиме  ядра  имеют смысл только в контексте алгоритма sleep. Приоритеты вы-
полнения в режиме задачи имеют верхнее пороговое значение, приоритеты выпол-
нения в режиме ядра имеют нижнее пороговое значение. Среди  приоритетов  вы-
полнения  в  режиме  ядра  далее можно выделить высокие и низкие приоритеты:
процессы с низким приоритетом возобновляются по получении сигнала, а процес-
сы с высоким приоритетом продолжают оставаться в состоянии приостанова  (см.
раздел 7.2.1).
    Пороговое значение между приоритетами выполнения в режимах ядра и задачи
на  Рисунке 8.2 отмечено двойной линией, проходящей между приоритетом ожида-
ния завершения потомка (в режиме ядра) и нулевым  приоритетом  выполнения  в
режиме  задачи. Приоритеты процесса подкачки, ожидания ввода-вывода, связан-
ного с диском, ожидания буфера и индекса являются высокими, не  допускающими
прерывания  системными  приоритетами, с каждым из которых связана очередь из
1, 3, 2 и 1 процесса, соответственно, в то  время  как  приоритеты  ожидания
ввода с терминала, вывода на терминал и завершения потомка являются низкими,
допускающими прерывания системными приоритетами, с каждым из которых связана
очередь из 4, 0 и 2 процессов, соответственно. На рисунке представлены также
уровни приоритетов выполнения в режиме задачи (*).
    Ядро вычисляет приоритет процесса в следующих случаях:

                                    233



(*) Наивысшим значением приоритета в системе является нулевое значение.  Та-
    ким образом, нулевой приоритет выполнения в режиме задачи выше приорите-
    та, имеющего значение, равное 1, и т.д.

  *  Непосредственно  перед  переходом процесса в состояние приостанова ядро
    назначает ему приоритет исходя из причины приостанова. Приоритет не  за-
    висит  от  динамических  характеристик  процесса (продолжительности вво-
    да-вывода или времени счета), напротив, это постоянная величина,  жестко
    устанавливаемая в момент приостанова и зависящая только от причины пере-
    хода процесса в данное состояние. Процессы, приостановленные алгоритмами
    низкого уровня, имеют тенденцию порождать тем больше узких мест в систе-
    ме,  чем  дольше  они находятся в этом состоянии; поэтому им назначается
    более высокий приоритет по сравнению с остальными процессами.  Например,
    процесс, приостановленный в ожидании завершения ввода-вывода, связанного
    с диском, имеет более высокий приоритет по сравнению с процессом, ожида-
    ющим освобождения буфера, по нескольким причинам. Прежде всего, у перво-
    го  процесса уже есть буфер, поэтому не исключена возможность, что когда
    он возобновится, он успеет освободить и буфер,  и  другие  ресурсы.  Чем
    больше  ресурсов  свободно, тем меньше шансов для возникновения взаимной
    блокировки процессов. Системе не придется часто переключать

Приоритеты выполнения     Уровни приоритетов     Процессы
    в режиме ядра
     |                 +----------------------+
     |                 |       Процесс        | +--+
     |                 |       подкачки       |-+  |
     | Не допускающие  +----------------------+ +--+
     |                 |Ожидание ввода-вывода,| +--+ +--+ +--+
     |   прерывания    | связанного с диском  |-+  +-+  +-+  |
     |                 +----------------------+ +--+ +--+ +--+
     |                 |       Ожидание       | +--+ +--+
     |                 |        буфера        |-+  +-+  |
     |                 +----------------------+ +--+ +--+
     |                 |       Ожидание       | +--+
     |                 |       индекса        |-+  |
     |                 +----------------------+ +--+
     |                 +----------------------+
     |                 | Ожидание ввода с тер-| +--+ +--+ +--+ +--+
     |                 |        минала        |-+  +-+  +-+  +-+  |
     |   Допускающие   +----------------------+ +--+ +--+ +--+ +--+
     |                 |  Ожидание вывода на  |
     |   прерывания    |       терминал       |
     |                 +----------------------+
     |                 | Ожидание завершения  | +--+ +--+
     |                 |        потомка       |-+  +-+  |
     v                 +----------------------+ +--+ +--+
Пороговый приоритет    +----------------------+
     ^                 |   Уровень задачи 0   |
     |                 +----------------------+ +--+ +--+ +--+ +--+
     |                 |   Уровень задачи 1   |-+  +-+  +-+  +-+  |
     |                 +----------------------+ +--+ +--+ +--+ +--+
     |                 |          -           |
     |                 |          -           |
     |                 +----------------------+ +--+
Приоритеты выполнения  |   Уровень задачи n   |-+  |
   в режиме задачи     +----------------------+ +--+

             Рисунок 8.2. Диапазон приоритетов процесса

                                    234


    контекст,  благодаря чему сократится время реакции процесса и увеличится
    производительность системы. Во-вторых, буфер, освобождения которого ожи-
    дает процесс, может быть занят процессом, ожидающим в свою  очередь  за-
    вершения ввода-вывода. По завершении ввода-вывода будут возобновлены оба
    процесса,  поскольку они были приостановлены по одному и тому же адресу.
    Если первым запустить на выполнение процесс, ожидающий освобождения  бу-
    фера,  он  в любом случае снова приостановится до тех пор, пока буфер не
    будет освобожден; следовательно, его приоритет должен быть ниже.
  * По возвращении процесса из режима ядра в режим задачи ядро вновь  вычис-
    ляет  приоритет  процесса.  Процесс  мог до этого находиться в состоянии
    приостанова, изменив свой приоритет на приоритет выполнения в режиме яд-
    ра, поэтому при переходе процесса из режима ядра в режим задачи ему дол-
    жен быть возвращен приоритет выполнения в режиме задачи. Кроме того, яд-
    ро "штрафует" выполняющийся процесс в пользу остальных процессов,  отби-
    рая используемые им ценные системные ресурсы.
  *  Приоритеты  всех  процессов в режиме задачи с интервалом в 1 секунду (в
    версии V) пересчитывает программа обработки прерываний по  таймеру,  по-
    буждая  тем  самым ядро выполнять алгоритм планирования, чтобы не допус-
    тить монопольного использования ресурсов ЦП одним процессом.

    В течение кванта времени таймер может послать процессу несколько  преры-
ваний;  при каждом прерывании программа обработки прерываний по таймеру уве-
личивает значение, хранящееся в поле таблицы  процессов,  которое  описывает
продолжительность  использования  ресурсов  центрального процессора (ИЦП). В
версии V каждую секунду  программа  обработки  прерываний  переустанавливает
значение этого поля, используя функцию полураспада (decay):

    decay(ИЦП) = ИЦП/2;

После этого программа пересчитывает приоритет каждого процесса, находящегося
в состоянии "зарезервирован, но готов к выполнению", по формуле

    приоритет = (ИЦП/2) + (базовый уровень приоритета задачи)

где  под  "базовым уровнем приоритета задачи" понимается пороговое значение,
расположенное между приоритетами выполнения в режимах ядра и задачи. Высоко-
му приоритету планирования соответствует количественно низкое значение. Ана-
лиз функций пересчета продолжительности использования ресурсов ЦП и  приори-
тета  процесса  показывает:  чем ниже скорость полураспада значения ИЦП, тем
медленнее приоритет процесса достигает  значение  базового  уровня;  поэтому
процессы  в  состоянии  "готовности  к  выполнению" имеют тенденцию занимать
большое число уровней приоритетов.
    Результатом ежесекундного  пересчета  приоритетов  является  перемещение
процессов, находящихся в режиме задачи, от одной очереди к другой, как пока-
зано  на  Рисунке  8.3.  По сравнению с Рисунком 8.2 один процесс перешел из
очереди, соответствующей уровню 1, в очередь, соответствующую нулевому уров-
ню. В реальной системе все процессы, имеющие приоритеты выполнения в  режиме
задачи, поменяли бы свое местоположение в очередях. При этом следует указать
на невозможность изменения приоритета процесса в режиме ядра, а также на не-
возможность  пересечения пороговой черты процессами, выполняющимися в режиме
задачи, до тех пор, пока они не обратятся к операционной системе и не перей-
дут в состояние приостанова.
    Ядро стремится производить пересчет приоритетов всех активных  процессов
ежесекундно, однако интервал между моментами пересчета может слегка варьиро-
ваться.  Если  прерывание  по  таймеру поступило тогда, когда ядро исполняло
критический отрезок программы (другими словами, в то время, когда  приоритет
работы  ЦП  был повышен, но, очевидно, не настолько, чтобы воспрепятствовать


                                    235

прерыванию данного типа), ядро не пересчитывает приоритеты, иначе ему  приш-
лось  бы надолго задержаться на критическом отрезке. Вместо этого ядро запо-
минает то, что ему следует произвести пересчет приоритетов, и делает это при
первом же прерывании по таймеру, поступающем после снижения приоритета рабо-
ты ЦП. Периодический пересчет приоритета  процессов  гарантирует  проведение
стратегии  планирования,  основанной на использовании кольцевого списка про-
цессов, выполняющихся в режиме задачи. При этом конечно же ядро  откликается
на  интерактивные  запросы таких программ, как текстовые редакторы или прог-
раммы форматного ввода: процессы, их реализующие, имеют высокий  коэффициент
простоя  (отношение  времени простоя к продолжительности использования ЦП) и
поэтому естественно было бы повышать их приоритет, когда они готовы для  вы-
полнения  (см.  [Thompson  78],  стр.1937). В других механизмах планирования
квант времени, выделяемый процессу на работу с ресурсами ЦП, динамически из-
меняется в интервале между 0 и 1 сек. в зависимости от степени загрузки сис-
темы. При этом время реакции на запросы процессов может

Приоритеты выполнения     Уровни приоритетов     Процессы
    в режиме ядра
     |                 +----------------------+
     |                 |       Процесс        | +--+
     |                 |       подкачки       |-+  |
     | Не допускающие  +----------------------+ +--+
     |                 |Ожидание ввода-вывода,| +--+ +--+ +--+
     |   прерывания    | связанного с диском  |-+  +-+  +-+  |
     |                 +----------------------+ +--+ +--+ +--+
     |                 |       Ожидание       | +--+ +--+
     |                 |        буфера        |-+  +-+  |
     |                 +----------------------+ +--+ +--+
     |                 |       Ожидание       | +--+
     |                 |       индекса        |-+  |
     |                 +----------------------+ +--+
     |                 +----------------------+
     |                 | Ожидание ввода с тер-| +--+ +--+ +--+ +--+
     |                 |        минала        |-+  +-+  +-+  +-+  |
     |   Допускающие   +----------------------+ +--+ +--+ +--+ +--+
     |                 |  Ожидание вывода на  |
     |   прерывания    |       терминал       |
     |                 +----------------------+
     |                 | Ожидание завершения  | +--+ +--+
     |                 |        потомка       |-+  +-+  |
     v                 +----------------------+ +--+ +--+
Пороговый приоритет    +----------------------+ +--+
     ^                 | Уровень задачи 0     |-+  |<- - - - - -+
     |                 +----------------------+ +--+            -
     |                 |                      | +--+ +--+ +--+ ++-+
     |                 |   Уровень задачи 1   |-+  +-+  +-+  + +  |
     |                 +----------------------+ +--+ +--+ +--+ +--+
     |                 |          -           |
     |                 |          -           |
     |                 +----------------------+ +--+
Приоритеты выполнения  |   Уровень задачи n   |-+  |
   в режиме задачи     +----------------------+ +--+

    Рисунок 8.2.  Переход процесса из одной очереди в другую


сократиться за счет того, что на ожидание момента запуска процессам  уже  не
нужно  отводить  по целой секунде; однако, с другой стороны, ядру приходится
чаще прибегать к переключению контекстов.

                                    236




    На Рисунке 8.4 показана динамика изменений приоритетов процессов A, B  и
C  в версии V при следующих допущениях: все эти процессы были созданы с пер-
воначальным приоритетом 60, который является наивысшим приоритетом  выполне-
ния  в режиме задачи, прерывания по таймеру поступают 60 раз в секунду, про-
цессы не используют вызов системных функций, в системе нет других процессов,
готовых к выполнению. Ядро вычисляет полураспад показателя ИЦП по формуле:


    Время     Процесс A         Процесс B         Процесс C
      |    Приоритет   ИЦП - Приоритет   ИЦП - Приоритет   ИЦП
  0 --+--                  -                 -
      |    60           0  - 60           0  - 60           0
      |                 1  -                 -
      |                 2  -                 -
      |                 ╜  -                 -
      |                 ╜  -                 -
  1 --+--               60 -                 -
      |    75           30 - 60           0  - 60           0
      |                    -              1  -
      |                    -              2  -
      |                    -              ╜  -
      |                    -              ╜  -
  2 --+--                  -              60 -
      |    67           15 - 75           30 - 60           0
      |                    -                 -              1
      |                    -                 -              2
      |                    -                 -              ╜
      |                    -                 -              ╜
  3 --+--                  -                 -              60
      |    63           7  - 67           15 - 75           30
      |                 8  -                 -
      |                 9  -                 -
      |                 ╜  -                 -
      |                 ╜  -                 -
  4 --+--               67 -                 -
      |    76           33 - 63           7  - 67           15
      |                    -              8  -
      |                    -              9  -
      |                    -              ╜  -
      |                    -              ╜  -
  5 --+--                  -              67 -
      |    68           16 - 76           33 - 63           7
      |                    -                 -
      |                    -                 -

           Рисунок 8.4. Пример диспетчеризации процессов


    ИЦП = decay(ИЦП) = ИЦП/2;
а приоритет процесса по формуле:
    приоритет = (ИЦП/2) + 60;

Если предположить, что первым запускается процесс A и ему  выделяется  квант
времени,  он  выполняется  в течение 1 секунды: за это время таймер посылает
системе 60 прерываний и столько же раз программа обработки прерываний увели-
чивает для процесса A значение поля, содержащего показатель ИЦП (с 0 до 60).

                                    237

По прошествии секунды ядро переключает контекст и, произведя пересчет  прио-
ритетов  для  всех  процессов,  выбирает для выполнения процесс B. В течение
следующей секунды программа обработки прерываний по таймеру 60 раз  повышает
значение  поля  ИЦП  для процесса B, после чего ядро пересчитывает параметры
диспетчеризации для всех процессов и вновь переключает  контекст.  Процедура
повторяется многократно, сопровождаясь поочередным запуском процессов на вы-
полнение.
    Теперь  рассмотрим процессы с приоритетами, приведенными на Рисунке 8.5,
и предположим, что в системе имеются и другие процессы. Ядро может выгрузить
процесс A, оставив его в состоянии "готовности к  выполнению",  после  того,
как он получит подряд несколько квантов времени для работы с ЦП и снизит та-
ким  образом свой приоритет выполнения в режиме задачи (Рисунок 8.5а). Через
некоторое время после запуска процесса A в состояние "готовности к  выполне-
нию"  может перейти процесс B, приоритет которого в тот момент окажется выше
приоритета процесса A (Рисунок 8.5б). Если ядро за это время не запланирова-
ло к выполнению любой другой процесс (из тех, что не показаны  на  рисунке),
оба  процесса (A и B) при известных обстоятельствах могут на некоторое время
оказаться на одном уровне приоритетности, хотя процесс  B  попадет  на  этот
уровень первым из-за того, что его первоначальный приоритет был ближе (Рису-
нок  8.5в и 8.5г). Тем не менее, ядро запустит процесс A впереди процесса B,
поскольку процесс A находился в состоянии "готовности  к  выполнению"  более
длительное  время (Рисунок 8.5д) - это решающее условие, если выбор произво-
дится из процессов с одинаковыми приоритетами.
    В разделе 6.4.3 уже говорилось о том, что ядро запускает процесс на  вы-
полнение после переключения контекста: прежде чем перейти в состояние приос-
танова  или  завершить  свое выполнение процесс должен переключить контекст,
кроме того он имеет возможность переключать контекст в  момент  перехода  из
режима  ядра  в режим задачи. Ядро выгружает процесс, который собирается пе-
рейти в режим задачи, если имеется готовый к выполнению процесс с более  вы-
соким  приоритетом.  Такая ситуация возникает, если ядро вывело из состояния
приостанова процесс с приоритетом, превышающим приоритет текущего  процесса,
или  если в результате обработки прерывания по таймеру изменились приоритеты
всех готовых к выполнению процессов. В первом случае текущий процесс не  мо-
жет  выполняться  в режиме задачи, поскольку имеется процесс с более высоким
приоритетом выполнения в режиме ядра. Во втором случае  программа  обработки
прерываний  по  таймеру решает, что процесс использовал выделенный ему квант
времени, и поскольку множество процессов при этом  меняют  свои  приоритеты,
ядро выполняет переключение контекста.




    Процессы могут управлять своими приоритетами с помощью системной функции
nice:

    nice(value);

где value - значение, в процессе пересчета прибавляемое к приори-
тету процесса:

    приоритет = (ИЦП/константа) + (базовый приоритет) + (значение nice)

Системная функция nice увеличивает или уменьшает значение поля nice в табли-
це процессов на величину параметра функции, при этом только суперпользовате-
лю дозволено указывать значения, увеличивающие приоритет процесса. Кроме то-
го,  только суперпользователь может указывать значения, лежащие ниже опреде-
ленного порога. Пользователи, вызывающие системную функцию  nice  для  того,
чтобы  понизить приоритет во время выполнения интенсивных вычислительных ра-
бот, "удобны, приятны" (nice) для остальных пользователей сис-

                                    238

          +---------+      +---------+      +---------+
     ^ 60 +---------+      +---------+      +----B----+
     |    +---------+      +---------+      +---------+
     |    +---------+      +----B----+      +----A----+
   Более  +---------+      +---------+      +---------+
  высокий +---------+      +----A----+      +---------+
  приори- +---------+      +---------+      +---------+
    тет   +----A----+      +---------+      +---------+
     |    +---------+      +---------+      +---------+
     |        (а)              (б)              (в)

          +----B----+      +-A-----B-+      +----B----+
       60 +----A----+      +---------+      +---------+(процесс
          +---------+      +---------+      +---------+
          +---------+      +---------+      +---------+
          +---------+      +---------+      +---------+
          +---------+      +---------+      +---------+
          +---------+      +---------+      +---------+
          +---------+      +---------+      +---------+
          +---------+      +---------+      +---------+
              (г)              (д)              (е)


    Рисунок 8.5. Планирование на основе кольцевого списка и прио-
                 ритеты процессов


темы, отсюда название функции. Процессы наследуют значение nice у своего ро-
дителя при выполнении системной функции fork. Функция nice действует  только
для  выполняющихся процессов; процесс не может сбросить значение nice у дру-
гого процесса. С практической точки зрения это означает, что если  админист-
ратору системы понадобилось понизить приоритеты различных процессов, требую-
щих  для  своего  выполнения  слишком много времени, у него не будет другого
способа сделать это быстро, кроме как вызвать функцию  удаления  (kill)  для
всех них сразу.




    Вышеописанный алгоритм планирования не видит никакой разницы между поль-
зователями  различных классов (категорий). Другими словами, невозможно выде-
лить определенной совокупности процессов, например, половину сеанса работы с
ЦП. Тем не менее, такая возможность имеет важное  значение  для  организации
работы в условиях вычислительного центра, где группа пользователей может по-
желать  купить только половину машинного времени на гарантированной основе и
с гарантированным уровнем реакции.  Здесь  мы  рассмотрим  схему,  именуемую
"Планированием на основе справедливого раздела" (Fair Share Scheduler) и ре-
ализованную   на   вычислительном   центре   Indian  Hill  фирмы  AT&T  Bell
Laboratories [Henry 84].
    Принцип "планирования на основе справедливого раздела" состоит в делении
совокупности пользователей на группы, являющиеся объектами ограничений, нак-
ладываемых обычным планировщиком на обработку процессов  из  каждой  группы.
При  этом система выделяет время ЦП пропорционально числу групп, вне зависи-
мости от того, сколько процессов выполняется в группе.  Пусть,  например,  в
системе имеются четыре планируемые группы, каждая из которых загружает ЦП на
25%  и  содержит,  соответственно, 1, 2, 3 и 4 процесса, реализующих счетные
задачи, которые никогда по своей воле не уступят ЦП. При условии, что в сис-
теме больше нет никаких других процессов, каждый процесс  при  использовании
традиционного  алгоритма  планирования  получил бы 10% времени ЦП (поскольку

                                    239

всего процессов 10 и между ними не делается никаких различий). При использо-
вании алгоритма планирования на основе справедливого раздела процесс из пер-
вой группы получит в два раза больше времени ЦП по сравнению с  каждым  про-
цессом  из второй группы, в 3 раза больше по сравнению с каждым процессом из
третьей группы и в 4 раза больше по сравнению с каждым процессом из  четвер-
той.  В  этом  примере всем процессам в группе выделяется равное время, пос-
кольку продолжительность цикла, реализуемого каждым  процессом,  заранее  не
установлена.
    Реализация  этой схемы довольно проста, что и делает ее привлекательной.
В формуле расчета приоритета процесса появляется еще один термин -  "приори-
тет  группы справедливого раздела". В пространстве процесса также появляется
новое поле, описывающее продолжительность ИЦП на основе справедливого разде-
ла, общую для всех процессов из группы. Программа  обработки  прерываний  по
таймеру  увеличивает значение этого поля для текущего процесса и ежесекундно
пересчитывает значения соответствующих полей для всех процессов  в  системе.
Новая  компонента  формулы вычисления приоритета процесса представляет собой
нормализованное значение ИЦП для каждой  группы.  Чем  больше  процессорного
времени  выделяется  процессам  группы, тем выше значение этого показателя и
ниже приоритет.
    В качестве примера рассмотрим две группы процессов (Рисунок 8.6), в  од-
ной  из  которых  один процесс (A), в другой - два (B и C). Предположим, что
ядро первым запустило на выполнение процесс A, в течение секунды  увеличивая
соответствующие  этому процессу значения полей, описывающих индивидуальное и
групповое ИЦП. В результате пересчета приоритетов по истечении секунды  про-
цессы B и C будут иметь наивысшие приоритеты. Допустим, что ядро выбирает на
выполнение процесс B. В течение следующей секунды значение поля ИЦП для про-
цесса B поднимается до 60, точно такое же значение принимает поле группового
ИЦП  для процессов B и C. Таким образом, по истечении второй секунды процесс
C получит приоритет, равный 75 (сравните с Рисунком 8.4), и ядро запустит на
выполнение процесс A с приоритетом 74. Дальнейшие действия можно  проследить
на рисунке: ядро по очереди запускает процессы A, B, A, C, A, B и т.д.



    Режим реального времени подразумевает возможность обеспечения  достаточ-
ной  скорости реакции на внешние прерывания и выполнения отдельных процессов
в темпе, соизмеримом с частотой возникновения вызывающих прерывания событий.
Примером системы, работающей в режиме реального времени, может служить  сис-
тема  управления  жизнеобеспечением пациентов больниц, мгновенно реагирующая
на изменение состояния пациента. Процессы, подобные текстовым редакторам, не
считаются процессами реального времени: в них быстрая  реакция  на  действия
пользователя  является  желательной,  но не необходимой (ничего страшного не
произойдет, если пользователь, выполняющий редактирование  текста,  подождет
ответа  несколько лишних секунд, хотя у пользователя на этот счет могут быть
и свои соображения). Вышеописанные алгоритмы планирования выполнения процес-
сов предназначены специально для использования в системах разделения времени
и не годятся для условий работы в режиме реального времени, поскольку не га-
рантируют запуск ядром каждого процесса в течение  фиксированного  интервала
времени,  позволяющего  говорить  о  взаимодействии вычислительной системы с
процессами в темпе, соизмеримом со скоростью протекания этих процессов. Дру-
гой помехой в поддержке работы в режиме реального времени является  невыгру-
жаемость  ядра; ядро не может планировать выполнение процесса реального вре-
мени в режиме задачи, если оно уже исполняет другой процесс в  режиме  ядра,
без  внесения  в  работу существенных изменений. В настоящее время системным
программистам приходится переводить процессы реального времени в режим ядра,
чтобы обеспечить достаточную скорость реакции. Правильное решение этой проб-
лемы - дать таким процессам возможность  динамического  протекания  (другими
словами, они не должны быть встроены в ядро) с предоставлением соответствую-


                                    240

    Время     Процесс A         Процесс B         Процесс C
      |    Прио- Ин-  Груп-- Прио- Ин-  Груп-- Прио- Ин-  Груп-
      |    ритет диви- по- - ритет диви- по- - ритет диви- по-
      |          дуал. вое -       дуал. вое -       дуал. вое
      |          ИЦП   ИЦП -       ИЦП   ИЦП -       ИЦП   ИЦП
  0 --+--                  -                 -
      |    60     0     0  - 60     0     0  - 60     0     0
      |           1     1  -                 -
      |           2     2  -                 -
      |           ╜     ╜  -                 -
      |           ╜     ╜  -                 -
  1 --+--         60    60 -                 -
      |    90     30    30 - 60     0     0  - 60     0     0
      |                    -        1     1  -              1
      |                    -        2     2  -              2
      |                    -        ╜     ╜  -              ╜
      |                    -        ╜     ╜  -              ╜
  2 --+--                  -        60    60 -              60
      |    74     15    15 - 90     30    30 - 75     0     30
      |           16    16 -                 -
      |           17    17 -                 -
      |           ╜     ╜  -                 -
      |           ╜     ╜  -                 -
  3 --+--         75    75 -                 -
      |    96     37    37 - 74     15    15 - 67     0     15
      |                    -              16 -        1     16
      |                    -              17 -        2     17
      |                    -              ╜  -        ╜     ╜
      |                    -              ╜  -        ╜     ╜
  4 --+--                  -              75 -        60    75
      |    78     18    18 - 81     7     37 - 93     30    37
      |           19    19 -                 -
      |           20    20 -                 -
      |           ╜     ╜  -                 -
      |           ╜     ╜  -                 -
  5 --+--         78    78 -                 -
      |    98     39    39 - 70     3     18 - 76     15    18
      |                    -                 -
      |                    -                 -

    Рисунок  8.6. Пример планирования на основе справедливого раздела, в ко-
                 тором используются две группы с тремя процессами



щего  механизма,  с помощью которого они могли бы сообщать ядру о своих нуж-
дах, вытекающих из особенностей работы в режиме реального времени. На сегод-
няшний день в стандартной системе UNIX такая возможность отсутствует.




    Существует несколько системных функций, имеющих отношение к времени про-
текания процесса: stime, time, times и alarm. Первые две имеют дело  с  гло-
бальным  системным временем, последние две - с временем выполнения отдельных
процессов.
    Функция stime дает суперпользователю возможность заносить  в  глобальную
ние глобальной переменной. Выбирается время из  этой  переменной  с  помощью
функции time:

                                    241

    time(tloc);

где  tloc - указатель на переменную, принадлежащую процессу, в которую зано-
сится возвращаемое функцией значение. Функция возвращает это значение  и  из
самой  себя, например, команде date, которая вызывает эту функцию, чтобы оп-
ределить текущее время.
    Функция times возвращает суммарное время выполнения процесса и всех  его
потомков, прекративших существование, в режимах ядра и задачи. Синтаксис вы-

    +------------------------------------------------------------+
    | #include                                      |
    | #include                                      |
    | extern long times();                                       |
    |                                                            |
    | main()                                                     |
    | {                                                          |
    |    int i;                                                  |
    |    /* tms - имя структуры данных, состоящей из 4 элемен-   |
    |       тов */                                               |
    |    struct tms pb1,pb2;                                     |
    |    long pt1,pt2;                                           |
    |                                                            |
    |    pt1 = times(&pb1);                                      |
    |    for (i = 0; i < 10; i++)                                |
    |         if (fork() == 0)                                   |
    |             child(i);                                      |
    |                                                            |
    |    for (i = 0; i < 10; i++)                                |
    |         wait((int*) 0);                                    |
    |    pt2 = times(&pb2);                                      |
    |    printf("процесс-родитель: реальное время %u             |
    |            в режиме задачи %u в режиме ядра %u             |
    |            потомки: в режиме задачи %u в режиме ядра %u\n",|
    |            pt2 - pt1,pb2.tms_utime - pb1.tms_utime,        |
    |            pb2.tms_stime - pb1.tms_stime,                  |
    |            pb2.tms_cutime - pb1.tms_cutime,                |
    |            pb2.tms_cstime - pb1.tms_cstime);               |
    | }                                                          |
    |                                                            |
    | child(n);                                                  |
    |    int n;                                                  |
    | {                                                          |
    |    int i;                                                  |
    |    struct tms cb1,cb2;                                     |
    |    long t1,t2;                                             |
    |                                                            |
    |    t1 = times(&cb1);                                       |
    |    for (i = 0; i < 10000; i++)                             |
    |         ;                                                  |
    |    t2 = times(&cb2);                                       |
    |    printf("потомок %d: реальное время %u в режиме задачи %u|
    |            в режиме ядра %u\n",n,t2 - t1,                  |
    |            cb2.tms_utime - cb1.tms_utime,                  |
    |            cb2.tms_stime - cb1.tms_stime);                 |
    |    exit();                                                 |
    | }                                                          |
    +------------------------------------------------------------+

      Рисунок 8.7. Пример программы, использующей функцию times

                                    242

зова функции:

    times(tbuffer)
    struct tms *tbuffer;
где  tms - имя структуры, в которую помещаются возвращаемые значения и кото-
рая описывается следующим образом:
    struct tms {
       /* time_t - имя структуры данных, в которой хранится время       */
       time_t tms_utime;  /* время выполнения процесса в режиме задачи  */
       time_t tms_stime;  /* время выполнения процесса в режиме ядра    */
       time_t tms_cutime;  /* время выполнения потомков в режиме задачи */
       time_t tms_cstime;  /* время выполнения потомков в режиме ядра   */
    };
Функция times возвращает время, прошедшее "с некоторого произвольного момен-
та в прошлом", как правило, с момента загрузки системы.
    На Рисунке 8.7 приведена программа, в которой  процесс-родитель  создает
10  потомков, каждый из которых 10000 раз выполняет пустой цикл. Процесс-ро-
дитель обращается к функции times перед созданием потомков и после их завер-
шения, в свою очередь потомки вызывают эту функцию  перед  началом  цикла  и
после его завершения. Кто-то по наивности может подумать, что время выполне-
ния  потомков  процесса  в режимах задачи и ядра равно сумме соответствующих
слагаемых каждого потомка, а реальное время процесса-родителя является  сум-
мой  реального  времени  его  потомков. Однако, время выполнения потомков не
включает в себя время, затраченное на исполнение системных  функций  fork  и
exit,  кроме того оно может быть искажено за счет обработки прерываний и пе-
реключений контекста.
    С помощью системной функции alarm пользовательские процессы могут иници-
ировать посылку сигналов тревоги  ("будильника")  через  кратные  промежутки
времени.  Например,  программа  на Рисунке 8.8 каждую минуту проверяет время
доступа к файлу и, если к файлу было произведено обращение, выводит соответ-
ствующее сообщение. Для этого в цикле, с помощью функции stat,  устанавлива-
ется  момент  последнего обращения к файлу и, если оно имело место в течение
последней минуты, выводится  сообщение.  Затем  процесс  с  помощью  функции
signal  делает  распоряжение  принимать  сигналы  тревоги, с помощью функции
alarm задает интервал между сигналами в 60 секунд и с помощью функции  pause
приостанавливает  свое выполнение до момента получения сигнала. Через 60 се-
кунд сигнал поступает, ядро подготавливает стек задачи к вызову функции  об-
работки сигнала wakeup, функция возвращает управление на оператор, следующий
за вызовом функции pause, и процесс исполняет цикл вновь.
    Все  перечисленные функции работы с временем протекания процесса объеди-
няет то, что они опираются на показания системных часов (таймера). Обрабаты-
вая прерывания по таймеру, ядро обращается к различным таймерным счетчикам и
инициирует соответствующее действие.



    8.3 ТАЙМЕР


    В функции программы обработки прерываний по таймеру входит:
  * перезапуск часов,
  * вызов на исполнение функций ядра, использующих встроенные часы,
  * поддержка возможности профилирования выполнения процессов в режимах ядра
    и задачи;
  * сбор статистики о системе и протекающих в ней процессах,
  * слежение за временем,
  * посылка процессам сигналов "будильника" по запросу,
  * периодическое возобновление процесса подкачки (см. следующую главу),
  * управление диспетчеризацией процессов.
    Некоторые из функций реализуются при каждом прерывании по таймеру,  дру-
гие - по прошествии нескольких таймерных тиков. Программа обработки прерыва-

                                    243


ний  по таймеру запускается с высоким приоритетом обращения к процессору, не
допуская во время работы возникновения других  внешних  событий  (таких  как
прерывания  от периферийных устройств). Поэтому программа обработки прерыва-
ний по таймеру работает очень быстро, за максимально-короткое время
пробегая свои критические отрезки, которые должны выполняться без прерываний
со стороны других процессов. Алгоритм обработки прерываний по таймеру приве-
ден на Рисунке 8.9.

    +------------------------------------------------------------+
    | #include                                      |
    | #include                                       |
    | #include                                     |
    |                                                            |
    | main(argc,argv)                                            |
    |     int argc;                                              |
    |     char *argv[];                                          |
    | {                                                          |
    |     extern unsigned alarm();                               |
    |     extern wakeup();                                       |
    |     struct stat statbuf;                                   |
    |     time_t axtime;                                         |
    |                                                            |
    |     if (argc != 2)                                         |
    |     {                                                      |
    |         printf("только 1 аргумент\n");                     |
    |         exit();                                            |
    |     }                                                      |
    |                                                            |
    |     axtime = (time_t) 0;                                   |
    |     for (;;)                                               |
    |     {                                                      |
    |         /* получение значения времени доступа к файлу */   |
    |         if (stat(argv[1],&statbuf) == -1)                  |
    |         {                                                  |
    |             printf("файла с именем %s нет\n",argv[1]);     |
    |             exit();                                        |
    |         }                                                  |
    |         if (axtime != statbuf.st_atime)                    |
    |         {                                                  |
    |             printf("к файлу %s было обращение\n",argv[1]); |
    |             axtime = statbuf.st_atime;                     |
    |         }                                                  |
    |         signal(SIGALRM,wakeup);   /* подготовка к приему   |
    |                                      сигнала */            |
    |         alarm(60);                                         |
    |         pause();      /* приостанов до получения сигнала */|
    |     }                                                      |
    | }                                                          |
    |                                                            |
    | wakeup()                                                   |
    | {                                                          |
    | }                                                          |
    +------------------------------------------------------------+

     Рисунок 8.8. Программа, использующая системную функцию alarm




                                    244
    +------------------------------------------------------------+
    | алгоритм clock                                             |
    | входная информация:  отсутствует                           |
    | выходная информация: отсутствует                           |
    | {                                                          |
    |     перезапустить часы;  /* чтобы они снова посылали преры-|
    |                             вания */                       |
    |     если (таблица ответных сигналов не пуста)              |
    |     {                                                      |
    |        установить время для ответных сигналов;             |
    |        запустить функцию callout, если время истекло;      |
    |     }                                                      |
    |     если (профилируется выполнение в режиме ядра)          |
    |        запомнить значение счетчика команд в момент прерыва-|
    |         ния;                                               |
    |     если (профилируется выполнение в режиме задачи)        |
    |        запомнить значение счетчика команд в момент прерыва-|
    |         ния;                                               |
    |     собрать статистику о самой системе;                    |
    |     собрать статистику о протекающих в системе процессах;  |
    |     выверить значение продолжительности ИЦП процессом;     |
    |     если (прошла 1 секунда или более и исполняется отрезок,|
    |      не являющийся критическим)                            |
    |     {                                                      |
    |        для (всех процессов в системе)                      |
    |        {                                                   |
    |            установить "будильник", если он активен;        |
    |            выверить значение продолжительности ИЦП;        |
    |            если (процесс будет исполняться в режиме задачи)|
    |                 выверить приоритет процесса;               |
    |        }                                                   |
    |        возобновить в случае необходимости выполнение про-  |
    |         цесса подкачки;                                    |
    |     }                                                      |
    | }                                                          |
    +------------------------------------------------------------+

        Рисунок 8.9. Алгоритм обработки прерываний по таймеру



    8.3.1 Перезапуск часов


    В большинстве машин после  получения  прерывания  по  таймеру  требуется
программными средствами произвести перезапуск часов, чтобы они по прошествии
интервала  времени  могли  вновь прерывать работу процессора. Такие средства
являются машинно-зависимыми и мы их рассматривать не будем.



    8.3.2 Внутренние системные тайм-ауты



    Некоторым из процедур ядра, в частности драйверам  устройств  и  сетевым
протоколам,  требуется вызов функций ядра в режиме реального времени. Напри-
мер, процесс может перевести терминал в режим ввода без обработки  символов,
при  котором ядро выполняет запросы пользователя на чтение с терминала через
фиксированные промежутки времени, не дожидаясь,  когда  пользователь  нажмет
клавишу  "возврата каретки" (см. раздел 10.3.3). Ядро хранит всю необходимую
информацию в таблице ответных сигналов (Рисунок 8.9), в том числе имя  функ-
ции, запускаемой по истечении интервала времени, параметр, передаваемый этой
функции,  а также продолжительность интервала (в таймерных тиках) до момента

                                    245

запуска функции.
    Пользователь не имеет возможности напрямую контролировать записи в  таб-
лице ответных сигналов; для работы с ними существуют различные системные ал-
горитмы. Ядро сортирует записи в этой таблице в соответствии с величиной ин-
тервала до момента запуска функций. В связи с этим для каждой записи таблицы
запоминается  не общая продолжительность интервала, а только промежуток вре-
мени между моментами запуска данной и предыдущей  функций.  Общая  продолжи-
тельность  интервала  до момента запуска функции складывается из промежутков
времени между моментами запуска всех функций, начиная с первой и  вплоть  до
текущей.

 Функция     Время до запуска        Функция     Время до запуска
+----------------------------+      +----------------------------+
|  a()                 -2    |      |  a()                 -2    |
+----------------------------+      +----------------------------+
|  b()                  3    |      |  b()                  3    |
+----------------------------+      +----------------------------+
|  c()                 10    |      |  f()                  2    |
+----------------------------+      +----------------------------+
                                    |  c()                  8    |
                                    +----------------------------+
            До                                   После

    Рисунок 8.10.  Включение новой записи в таблицу ответных сигналов

    На Рисунке 8.10 приведен пример добавления новой записи в таблицу ответ-
ных сигналов. (К отрицательному значению поля "время до запуска" для функции
a  мы вернемся несколько позже). Создавая новую запись, ядро отводит для нее
надлежащее место и соответствующим образом переустанавливает  значение  поля
"время до запуска" в записи, следующей за добавляемой. Судя по рисунку, ядро
собирается  запустить  функцию  f через 5 таймерных тиков: оно отводит место
для нее в таблице сразу после функции b и заносит в поле "время до  запуска"
значение, равное 2 (тогда сумма значений этих полей для функций b и f соста-
вит  5),  и меняет "время до запуска" функции c на 8 (при этом функция c все
равно запускается через 13 таймерных тиков). В одних версиях ядро пользуется
связным списком указателей на записи таблицы ответных сигналов, в  других  -
меняет положение записей при корректировке таблицы. Последний способ требует
значительно  меньших  издержек  при условии, что ядро не будет слишком часто
обращаться к таблице.

    При каждом поступлении прерывания по таймеру программа обработки  преры-
вания  проверяет  наличие  записей в таблице ответных сигналов и в случае их
обнаружения уменьшает значение поля "время до запуска" в первой записи. Спо-
соб хранения продолжительности интервалов до момента запуска каждой функции,
выбранный ядром, позволяет, уменьшив значение поля "время до запуска" в  од-
ной  только первой записи, соответственно уменьшить продолжительность интер-
вала до момента запуска функций, описанных во всех записях таблицы.  Если  в
указанном  поле  первой  записи хранится отрицательное или нулевое значение,
соответствующую функцию следует запустить. Программа обработки прерываний по
таймеру не запускает функцию немедленно, таким образом она не блокирует воз-
никновение последующих прерываний данного  типа.  Текущий  приоритет  работы
процессора  вроде бы не позволяет таким прерываниям вмешиваться в выполнение
процесса, однако ядро не имеет представления о том, сколько времени потребу-
ется на исполнение функции. Казалось бы, если функция выполняется дольше од-
ного таймерного тика, все последующие прерывания должны быть  заблокированы.
Вместо  этого,  программа обработки прерываний в типичной ситуации оформляет
вызов функции как "программное прерывание", порождаемое выполнением  отдель-
ной машинной команды. Поскольку среди всех прерываний программные прерывания
имеют  самый  низкий приоритет, они блокируются, пока ядро не закончит обра-

                                    246

ботку всех остальных прерываний. С момента завершения подготовки  к  запуску
функции и до момента возникновения вызываемого запуском функции программного
прерывания  может произойти множество прерываний, в том числе и программных,
в таком случае в поле "время до запуска", принадлежащее первой записи табли-
цы, будет занесено отрицательное значение. Когда же наконец программное пре-
рывание происходит, программа обработки прерываний убирает  из  таблицы  все
записи с истекшими значениями полей "время до запуска" и вызывает соответст-
вующую функцию.
    Поскольку  в  указанном поле в начальных записях таблицы может храниться
отрицательное или нулевое значение, программа  обработки  прерываний  должна
найти  в  таблице  первую  запись с положительным значением поля и уменьшить
его. Пусть, например, функции a соответствует "время до запуска", равное  -2
(Рисунок 8.10), то есть перед тем, как функция a была выбрана на выполнение,
система  получила 2 прерывания по таймеру. При условии, что функция b 2 тика
назад уже была в таблице, ядро пропускает запись, соответствующую функции a,
и уменьшает значение поля "время до запуска" для функции b.



    8.3.3 Построение профиля


    Построение профиля ядра включает в себя измерение продолжительности  вы-
полнения  системы  в режиме задачи против режима ядра, а также продолжитель-
ности выполнения отдельных процедур ядра. Драйвер параметров ядра следит  за
относительной  эффективностью  работы модулей ядра, замеряя параметры работы
системы в момент прерывания по таймеру. Драйвер параметров имеет список  ад-
ресов  ядра (главным образом, функций ядра); эти адреса ранее были загружены
процессом путем обращения к драйверу параметров. Если построение профиля яд-
ра возможно, программа обработки прерывания по таймеру запускает подпрограм-
му обработки прерываний, принадлежащую драйверу параметров, которая  опреде-
ляет, в каком из режимов - ядра или задачи - работал процессор в момент пре-
рывания.  Если процессор работал в режиме задачи, система построения профиля
увеличивает значение параметра, описывающего продолжительность выполнения  в
режиме  задачи, если же процессор работал в режиме ядра, система увеличивает
значение внутреннего счетчика, соответствующего счетчику  команд.  Пользова-
тельские  процессы  могут  обращаться  к драйверу параметров, чтобы получить
значения параметров ядра и различную статистическую информацию.

                +--------------------------------+
                | Алгоритм      Адрес    Счетчик |
                |                                |
                | bread          100         5   |
                | breada         150         0   |
                | bwrite         200         0   |
                | brelse         300         2   |
                | getblk         400         1   |
                | user            -          2   |
                +--------------------------------+

          Рисунок 8.11. Адреса некоторых алгоритмов ядра


    На Рисунке 8.11 приведены гипотетические адреса некоторых процедур ядра.
Пусть в результате 10 измерений, проведенных в моменты поступления  прерыва-
ний  по таймеру, были получены следующие значения счетчика команд: 110, 330,
145, адрес в пространстве задачи, 125, 440, 130, 320, адрес  в  пространстве
задачи и 104. Ядро сохранит при этом те значения, которые показаны на рисун-
ке.  Анализ этих значений показывает, что система провела 20% своего времени
в режиме задачи (user) и 50% времени потратила на выполнение алгоритма bread
в режиме ядра.

                                    247

    Если измерение параметров ядра выполняется в течение длительного периода
времени, результаты измерений приближаются к истинной картине  использования
системных  ресурсов.  Тем не менее, описываемый механизм не учитывает время,
потраченное на обработку прерываний по таймеру и выполнение процедур, блоки-
рующих поступление прерываний данного типа, поскольку таймер не может преры-
вать выполнение критических отрезков программ и, таким образом, не  может  в
это  время  обращаться к подпрограмме обработки прерываний драйвера парамет-
ров. В этом недостаток описываемого механизма, ибо критические отрезки прог-
рамм ядра чаще всего наиболее важны для измерений. Следовательно, результаты
измерения параметров ядра содержат определенную долю приблизительности. Уай-
нбергер [Weinberger 84] описал механизм включения счетчиков в главных блоках
программы, таких как "if-then" и "else", с целью повышения точности  измере-
ния  частоты  их выполнения. Однако, данный механизм увеличивает время счета
программ на 50-200%, поэтому его использование в качестве постоянного  меха-
низма измерения параметров ядра нельзя признать рациональным.
    На пользовательском уровне для измерения параметров выполнения процессов
можно использовать системную функцию profil:

    profil(buff,bufsize,offset,scale);

где  buff  -  адрес массива в пространстве задачи, bufsize - размер массива,
offset - виртуальный адрес подпрограммы пользователя (обычно, первой по сче-
ту), scale - способ отображения виртуальных адресов задачи на адрес массива.
Ядро трактует аргумент "scale" как двоичную  дробь  с  фиксированной  точкой
слева. Так, например, значение аргумента в шестнадцатиричной системе счисле-
ния,  равное  Oxffff, соответствует однозначному отображению счетчика команд
на адреса массива, значение, равное Ox7fff, соответствует размещению в одном
слове массива buff двух адресов программы, Ox3fff - четырех адресов програм-
мы и т.д. Ядро хранит параметры, передаваемые при вызове системной  функции,
в  пространстве  процесса.  Если таймер прерывает выполнение процесса тогда,
когда он находится в режиме задачи, программа обработки прерываний проверяет
значение счетчика команд в момент прерывания, сравнивает  его  со  значением
аргумента offset и увеличивает содержимое ячейки памяти, адрес которой явля-
ется функцией от bufsize и scale.
    Рассмотрим  в  качестве  примера программу, приведенную на Рисунке 8.12,
измеряющую продолжительность выполнения функций f и g. Сначала процесс,  ис-
пользуя  системную  функцию  signal, делает указание при получении сигнала о
прерывании вызывать функцию theend,  затем  он  вычисляет  диапазон  адресов
программы, в пределах которых будет производиться измерение продолжительнос-
ти (начиная с адреса функции main и кончая адресом функции theend), и, нако-
нец, запускает функцию profil, сообщая ядру о том, что он собира-
ется начать измерение. В результате выполнения программы в течение 10 секунд
на  несильно загруженной машине AT&T 3B20 были получены данные, представлен-
ные на Рисунке 8.13. Адрес функции f превышает адрес  начала  профилирования
на 204 байта; поскольку текст функции f имеет размер 12 байт, а размер цело-
го числа в машине AT&T 3B20 равен 4 байтам, адреса функции f отображаются на
элементы  массива  buf  с номерами 51, 52 и 53. По такому же принципу адреса
функции g отображаются на элементы buf c номерами 54, 55 и 56. Элементы  buf
с  номерами 46, 48 и 49 предназначены для адресов, принадлежащих циклу функ-
ции main. В обычном случае диапазон адресов, в пределах которого выполняется
измерение параметров, определяется в результате обращения к таблице  иденти-
фикаторов  для  данной программы, где указываются адреса программных секций.
Пользователи сторонятся функции profil из-за того, что она кажется им  слиш-
ком  сложной;  вместо нее они используют при компиляции программ на языке Си
параметр, сообщающий компилятору о необходимости сгенерировать код, следящий
за ходом выполнения процессов.




                                    248
    +------------------------------------------------------------+
    | #include                                         |
    | int buffer[4096];                                          |
    | main()                                                     |
    | {                                                          |
    |    int offset,endof,scale,eff,gee,text;                    |
    |    extern theend(),f(),g();                                |
    |    signal(SIGINT,theend);                                  |
    |    endof = (int) theend;                                   |
    |    offset = (int) main;                                    |
    |    /* вычисляется количество слов в тексте программы */    |
    |    text = (endof - offset + sizeof(int) - 1)/sizeof(int);  |
    |    scale = Oxffff;                                         |
    |    printf                                                  |
    |     ("смещение до начала %d до конца %d длина текста %d\n",|
    |      offset,endof,text);                                   |
    |    eff = (int) f;                                          |
    |    gee = (int) g;                                          |
    |    printf("f %d g %d fdiff %d gdiff %d\n",eff,gee,         |
    |            eff-offset,gee-offset);                         |
    |    profil(buffer,sizeof(int)*text,offset,scale);           |
    |    for (;;)                                                |
    |    {                                                       |
    |        f();                                                |
    |        g();                                                |
    |    }                                                       |
    | }                                                          |
    | f()                                                        |
    | {                                                          |
    | }                                                          |
    | g()                                                        |
    | {                                                          |
    | }                                                          |
    | theend()                                                   |
    | {                                                          |
    |    int i;                                                  |
    |    for (i = 0; i < 4096; i++)                              |
    |        if (buffer[i])                                      |
    |            printf("buf[%d] = %d\n",i,buffer[i]);           |
    |    exit();                                                 |
    | }                                                          |
    +------------------------------------------------------------+

    Рисунок 8.12. Программа, использующая системную функцию profil

     +------------------------------------------------------+
     | смещение до начала 212 до конца 440 длина текста 57  |
     | f 416 g 428 fdiff 204 gdiff 216                      |
     | buf[46] = 50                                         |
     | buf[48] = 8585216                                    |
     | buf[49] = 151                                        |
     | buf[51] = 12189799                                   |
     | buf[53] = 65                                         |
     | buf[54] = 10682455                                   |
     | buf[56] = 67                                         |
     +------------------------------------------------------+

    Рисунок 8.13.  Пример результатов выполнения программы, ис-
                   пользующей системную функцию profil


                                    249


    8.3.4 Учет и статистика


    В момент поступления прерывания по таймеру система может  выполняться  в
режиме  ядра  или  задачи, а также находиться в состоянии простоя (бездейст-
вия). Состояние простоя означает, что все процессы приостановлены в ожидании
наступления события. Для каждого состояния процессора ядро имеет  внутренние
счетчики,  устанавливаемые при каждом прерывании по таймеру. Позже пользова-
тельские процессы могут проанализировать  накопленную  ядром  статистическую
информацию.
    В  пространстве  каждого  процесса имеются два поля для записи продолжи-
тельности времени, проведенного процессом в режиме ядра и задачи. В ходе об-
работки прерываний по таймеру ядро корректирует значение поля, соответствую-
щего текущему режиму выполнения процесса. Процессы-родители собирают статис-
тику о своих потомках при выполнении функции wait, беря за  основу  информа-
цию, поступающую от завершающих свое выполнение потомков.
    В пространстве каждого процесса имеется также одно поле для ведения уче-
та  использования памяти. В ходе обработки прерывания по таймеру ядро вычис-
ляет общий объем памяти, занимаемый текущим  процессом,  исходя  из  размера
частных областей процесса и его долевого участия в использовании разделяемых
областей  памяти.  Если, например, процесс использует области данных и стека
размером 25 и 40 Кбайт, соответственно, и разделяет с четырьмя другими  про-
цессами  одну  область  команд размером 50 Кбайт, ядро назначает процессу 75
Кбайт памяти (50К/5 + 25К + 40К). В системе с замещением страниц ядро вычис-
ляет объем используемой памяти путем подсчета числа  используемых  в  каждой
области  страниц.  Таким образом, если прерываемый процесс имеет две частные
области и еще одну область разделяет с другим процессом, ядро назначает  ему
столько страниц памяти, сколько содержится в этих частных областях, плюс по-
ловину  страниц, принадлежащих разделяемой области. Вся указанная информация
отражается в учетной записи при завершении процесса и может быть использова-
на для расчетов с заказчиками машинного времени.


    8.3.5 Поддержание времени в системе


    Ядро увеличивает показание системных часов при каждом прерывании по тай-
меру, измеряя время в таймерных тиках от момента загрузки системы. Это  зна-
чение  возвращается процессу через системную функцию time и дает возможность
определять общее время выполнения процесса.  Время  первоначального  запуска
процесса  сохраняется  ядром в адресном пространстве процесса при исполнении
системной функции fork, в момент завершения процесса это значение вычитается
из текущего времени, результат вычитания и составляет реальное время  выпол-
нения  процесса. В другой переменной таймера, устанавливаемой с помощью сис-
темной функции stime и корректируемой раз в  секунду,  хранится  календарное
время.


    8.4 ВЫВОДЫ


    В настоящей главе был описан основной алгоритм диспетчеризации процессов
в  системе UNIX. С каждым процессом в системе связывается приоритет планиро-
вания, значение которого появляется в момент перехода процесса  в  состояние
приостанова и периодически корректируется программой обработки прерываний по
таймеру.  Приоритет,  присваиваемый  процессу  в момент перехода в состояние
приостанова, имеет значение, зависящее от того, какой из алгоритмов ядра ис-
полнялся процессом в этот момент. Значение приоритета, присваиваемое процес-
су во время выполнения программой обработки прерываний по таймеру (или в тот
момент, когда процесс возвращается из режима ядра в режим  задачи),  зависит
от того, сколько времени процесс занимал ЦП: процесс получает низкий приори-
тет, если он обращался к ЦП, и высокий - в противном случае. Системная функ-
ция nice дает процессу возможность влиять на собственный приоритет путем до-
бавления параметра, участвующего в пересчете приоритета.

                                    250

    В  главе  были также рассмотрены системные функции, связанные с временем
выполнения системы и протекающих в ней процессов: с установкой и  получением
системного  времени,  получением  времени  выполнения процессов и установкой
сигналов "будильника". Кроме того, описаны функции программы обработки  пре-
рываний по таймеру, которая следит за временем в системе, управляет таблицей
ответных сигналов, собирает статистику, а также подготавливает запуск плани-
ровщика  процессов,  программы подкачки и "сборщика" страниц. Программа под-
качки и "сборщик" страниц являются объектами рассмотрения в следующей главе.



    8.5 УПРАЖНЕНИЯ


  1. При переводе процессов в состояние приостанова ядро назначает процессу,
     ожидающему снятия блокировки с  индекса,  более  высокий  приоритет  по
     сравнению  с  процессом,  ожидающим  освобождения буфера. Точно так же,
     процессы, ожидающие ввода с терминала, получают более высокий приоритет
     по сравнению с процессами, ожидающими возможности производить вывод  на
     терминал. Объясните причины такого поведения ядра.
 *2. В алгоритме обработки прерываний по таймеру предусмотрен пересчет прио-
     ритетов  и перезапуск процессов на выполнение с интервалом в 1 секунду.
     Придумайте алгоритм, в котором интервал перезапуска динамически меняет-
     ся в зависимости от степени загрузки системы. Перевесит ли выигрыш уси-
     лия по усложнению алгоритма ?
  3. В шестой редакции системы UNIX для расчета продолжительности ИЦП  теку-
     щим процессом используется следующая формула:
     decay(ИЦП) = max (пороговый приоритет, ИЦП-10);
     а в седьмой редакции:
     decay(ИЦП) = .8 * ИЦП;
     Приоритет процесса в обеих редакциях вычисляется по формуле:
     приоритет = ИЦП/16 + (базовый уровень приоритета);
     Повторите пример на Рисунке 8.4, используя приведенные формулы.
  4.  Проделайте  еще  раз  пример  на Рисунке 8.4 с семью процессами вместо
     трех, а затем измените частоту прерываний по таймеру с 60 на 100 преры-
     ваний в секунду. Прокомментируйте результат.
  5. Разработайте схему, в которой система накладывает ограничение  на  про-
     должительность выполнения процесса, при превышении которого процесс за-
     вершается.  Каким образом пользователь должен отличать такой процесс от
     процессов, для которых не должны существовать  подобные  ограничения  ?
     Каким образом должна работать схема, если единственным условием являет-
     ся ее запуск из shell'а ?
  6.  Когда  процесс выполняет системную функцию wait и обнаруживает прекра-
     тившего существование потомка, ядро приплюсовывает к его  ИЦП  значение
     поля ИЦП потомка. Чем объясняется такое "наказание" процесса-родителя ?
  7.  Команда  nice  запускает последующую команду с передачей ей указанного
     значения, например:
     nice 6 nroff -mm big_memo > output
     Напишите на языке Си программу, реализующую команду nice.
  8. Проследите на примере Рисунка 8.4, каким образом  будет  осуществляться
     диспетчеризация  процессов  в  том  случае, если значение, передаваемое
     функцией nice для процесса A, равно 5 или -5.
  9. Проведите эксперимент с системной функцией renice x  y,  где  x  -  код
     идентификации  процесса (активного), а y - новое значение nice для ука-
     занного процесса.
 10. Вернемся к примеру, приведенному на Рисунке 8.6. Предположим, что груп-
     пе, в которую входит процесс A, выделяется 33% процессорного времени, а
     группе, в которую входит процесс B, - 66% процессорного времени. В  ка-
     кой  последовательности  будут исполняться процессы ? Обобщите алгоритм
     вычисления приоритетов таким образом, чтобы значение группового ИЦП ус-
     реднялось.

                                    251

 11. Выполните команду date. Команда без аргументов  выводит  текущую  дату:
     указав аргумент, например:
     date mmddhhmmyy
     (супер)пользователь может установить текущую дату  в системе
     (соответственно, месяц, число, часы, минуты и год). Так,
     date 0911205084
     устанавливает  в  качестве  текущего времени 11 сентября 1984 года 8:50
     пополудни.
 12. В программах можно  использовать  функцию  пользовательского
     уровня sleep:
     sleep(seconds);
     с помощью которой выполнение программы приостанавливается на  указанное
     число секунд. Разработайте ее алгоритм, в котором используйте системные
     функции  alarm  и  pause.  Что произойдет, если процесс вызовет функцию
     alarm раньше функции sleep ? Рассмотрите две возможности:  1)  действие
     ранее  вызванной функции alarm истекает в то время, когда процесс нахо-
     дится в состоянии приостанова,  2)  действие  ранее  вызванной  функции
     alarm истекает после завершения функции sleep.
*13. Обратимся еще раз к последней проблеме. Ядро может выполнить переключе-
     ние  контекста во время исполнения функции sleep между вызовами alarm и
     pause. Тогда есть опасность, что процесс получит сигнал alarm до  того,
     как  вызовет  функцию pause. Что произойдет в этом случае ? Как вовремя
     распознать эту ситуацию ?





































                                    252

Last-modified: Thu, 12 Feb 1998 07:20:11 GMT

Оцените этот текст

List100_Counter