ГЛАВА 8. ДИСПЕТЧЕРИЗАЦИЯ ПРОЦЕССОВ И ЕЕ ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ
ГЛАВА 8. ДИСПЕТЧЕРИЗАЦИЯ ПРОЦЕССОВ И ЕЕ ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ
В системе разделения времени ядро предоставляет процессу ресурсы цент-
рального процессора (ЦП) на интервал времени, называемый квантом, по истече-
нии которого выгружает этот процесс и запускает другой, периодически переу-
порядочивая очередь процессов. Алгоритм планирования процессов в системе
UNIX использует время выполнения в качестве параметра. Каждый активный про-
цесс имеет приоритет планирования; ядро переключает контекст на процесс с
наивысшим приоритетом. При переходе выполняющегося процесса из режима ядра в
режим задачи ядро пересчитывает его приоритет, периодически и в режиме зада-
чи переустанавливая приоритет каждого процесса, готового к выполнению.
Информация о времени, связанном с выполнением, нужна также и некоторым
из пользовательских процессов: используемая ими, например, команда time поз-
воляет узнать, сколько времени занимает выполнение другой команды, команда
date выводит текущую дату и время суток. С помощью различных системных функ-
ций процессы могут устанавливать или получать временные характеристики вы-
полнения в режиме ядра, а также степень загруженности центрального процессо-
ра. Время в системе поддерживается с помощью аппаратных часов, которые посы-
лают ЦП прерывания с фиксированной, аппаратно-зависимой частотой, обычно
50-100 раз в секунду. Каждое поступление прерывания по таймеру (часам) име-
нуется таймерным тиком. В настоящей главе рассматриваются особенности реали-
зации процессов во времени, включая планирование процессов в системе UNIX,
описание связанных со временем системных функций, а также функций, выполняе-
мых программой обработки прерываний по таймеру.
8.1 ПЛАНИРОВАНИЕ ВЫПОЛНЕНИЯ ПРОЦЕССОВ
Планировщик процессов в системе UNIX принадлежит к общему классу плани-
ровщиков, работающих по принципу "карусели с многоуровневой обратной
связью". В соответствии с этим принципом ядро предоставляет процессу ресурсы
ЦП на квант времени, по истечении которого выгружает этот процесс и возвра-
щает его в одну из нескольких очередей, регулируемых приоритетами. Прежде
чем процесс завершится, ему может потребоваться множество раз пройти через
цикл с обратной связью. Когда ядро выполняет переключение контекста и восс-
танавливает контекст процесса, процесс возобновляет выполнение с точки при-
останова.
8.1.1 Алгоритм
Сразу после переключения контекста ядро запускает алгоритм планирования
выполнения процессов (Рисунок 8.1), выбирая на выполнение процесс с наивыс-
шим приоритетом среди процессов, находящихся в состояниях "резервирования" и
"готовности к выполнению, будучи загруженным в память". Рассматривать про-
цессы, не загруженные в память, не имеет смысла, поскольку не будучи загру-
жен, процесс не может выполняться. Если наивысший приоритет имеют сразу нес-
колько процессов, ядро, используя принцип кольцевого списка (карусели), вы-
бирает среди них тот процесс, который находится в состоянии "готовности к
выполнению" дольше остальных. Если ни один из процессов не может быть выбран
для выполнения, ЦП простаивает до момента получения следующего прерывания,
которое произойдет не позже чем через один таймерный тик; после обработки
этого прерывания ядро снова запустит алгоритм планирования.
232
+------------------------------------------------------------+
| алгоритм schedule_process |
| входная информация: отсутствует |
| выходная информация: отсутствует |
| { |
| выполнять пока (для запуска не будет выбран один из про-|
| цессов) |
| { |
| для (каждого процесса в очереди готовых к выполнению)|
| выбрать процесс с наивысшим приоритетом из загру-|
| женных в память; |
| если (ни один из процессов не может быть избран для |
| выполнения) |
| приостановить машину; |
| /* машина выходит из состояния простоя по преры- |
| /* ванию |
| */ |
| } |
| удалить выбранный процесс из очереди готовых к выполне- |
| нию; |
| переключиться на контекст выбранного процесса, возобно- |
| вить его выполнение; |
| } |
+------------------------------------------------------------+
Рисунок 8.1. Алгоритм планирования выполнения процессов
8.1.2 Параметры диспетчеризации
В каждой записи таблицы процессов есть поле приоритета, используемое
планировщиком процессов. Приоритет процесса в режиме задачи зависит от того,
как этот процесс перед этим использовал ресурсы ЦП. Можно выделить два клас-
са приоритетов процесса (Рисунок 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.1.3 Примеры диспетчеризации процессов
На Рисунке 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 уже говорилось о том, что ядро запускает процесс на вы-
полнение после переключения контекста: прежде чем перейти в состояние приос-
танова или завершить свое выполнение процесс должен переключить контекст,
кроме того он имеет возможность переключать контекст в момент перехода из
режима ядра в режим задачи. Ядро выгружает процесс, который собирается пе-
рейти в режим задачи, если имеется готовый к выполнению процесс с более вы-
соким приоритетом. Такая ситуация возникает, если ядро вывело из состояния
приостанова процесс с приоритетом, превышающим приоритет текущего процесса,
или если в результате обработки прерывания по таймеру изменились приоритеты
всех готовых к выполнению процессов. В первом случае текущий процесс не мо-
жет выполняться в режиме задачи, поскольку имеется процесс с более высоким
приоритетом выполнения в режиме ядра. Во втором случае программа обработки
прерываний по таймеру решает, что процесс использовал выделенный ему квант
времени, и поскольку множество процессов при этом меняют свои приоритеты,
ядро выполняет переключение контекста.
8.1.4 Управление приоритетами
Процессы могут управлять своими приоритетами с помощью системной функции
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) для
всех них сразу.
8.1.5 Планирование на основе справедливого раздела
Вышеописанный алгоритм планирования не видит никакой разницы между поль-
зователями различных классов (категорий). Другими словами, невозможно выде-
лить определенной совокупности процессов, например, половину сеанса работы с
ЦП. Тем не менее, такая возможность имеет важное значение для организации
работы в условиях вычислительного центра, где группа пользователей может по-
желать купить только половину машинного времени на гарантированной основе и
с гарантированным уровнем реакции. Здесь мы рассмотрим схему, именуемую
"Планированием на основе справедливого раздела" (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 и т.д.
8.1.6 Работа в режиме реального времени
Режим реального времени подразумевает возможность обеспечения достаточ-
ной скорости реакции на внешние прерывания и выполнения отдельных процессов
в темпе, соизмеримом с частотой возникновения вызывающих прерывания событий.
Примером системы, работающей в режиме реального времени, может служить сис-
тема управления жизнеобеспечением пациентов больниц, мгновенно реагирующая
на изменение состояния пациента. Процессы, подобные текстовым редакторам, не
считаются процессами реального времени: в них быстрая реакция на действия
пользователя является желательной, но не необходимой (ничего страшного не
произойдет, если пользователь, выполняющий редактирование текста, подождет
ответа несколько лишних секунд, хотя у пользователя на этот счет могут быть
и свои соображения). Вышеописанные алгоритмы планирования выполнения процес-
сов предназначены специально для использования в системах разделения времени
и не годятся для условий работы в режиме реального времени, поскольку не га-
рантируют запуск ядром каждого процесса в течение фиксированного интервала
времени, позволяющего говорить о взаимодействии вычислительной системы с
процессами в темпе, соизмеримом со скоростью протекания этих процессов. Дру-
гой помехой в поддержке работы в режиме реального времени является невыгру-
жаемость ядра; ядро не может планировать выполнение процесса реального вре-
мени в режиме задачи, если оно уже исполняет другой процесс в режиме ядра,
без внесения в работу существенных изменений. В настоящее время системным
программистам приходится переводить процессы реального времени в режим ядра,
чтобы обеспечить достаточную скорость реакции. Правильное решение этой проб-
лемы - дать таким процессам возможность динамического протекания (другими
словами, они не должны быть встроены в ядро) с предоставлением соответствую-
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 такая возможность отсутствует.
8.2 СИСТЕМНЫЕ ОПЕРАЦИИ, СВЯЗАННЫЕ СО ВРЕМЕНЕМ
Существует несколько системных функций, имеющих отношение к времени про-
текания процесса: 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