В  системе  разделения времени ядро предоставляет процессу ресурсы цент-
рального процессора (ЦП) на интервал времени, называемый квантом, по истече-
нии которого выгружает этот процесс и запускает другой, периодически  переу-
порядочивая  очередь  процессов.  Алгоритм  планирования процессов в системе
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

Популярность: 18, Last-modified: Thu, 12 Feb 1998 07:19:50 GMT