Unix overview CHAP08
ГЛАВА 8
В системе разделения времени ядро предоставляет процессу ресурсы цент-
рального процессора (ЦП) на интервал времени, называемый квантом, по истече-
нии которого выгружает этот процесс и запускает другой, периодически переу-
порядочивая очередь процессов. Алгоритм планирования процессов в системе
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, и процесс исполняет цикл вновь.
Все перечисленные функции работы с временем протекания процесса объеди-
няет то, что они опираются на показания системных часов (таймера). Обрабаты-
вая прерывания по таймеру, ядро обращается к различным таймерным счетчикам и
инициирует соответствующее действие.
В функции программы обработки прерываний по таймеру входит:
* перезапуск часов,
* вызов на исполнение функций ядра, использующих встроенные часы,
* поддержка возможности профилирования выполнения процессов в режимах ядра
и задачи;
* сбор статистики о системе и протекающих в ней процессах,
* слежение за временем,
* посылка процессам сигналов "будильника" по запросу,
* периодическое возобновление процесса подкачки (см. следующую главу),
* управление диспетчеризацией процессов.
Некоторые из функций реализуются при каждом прерывании по таймеру, дру-
гие - по прошествии нескольких таймерных тиков. Программа обработки прерыва-
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. Алгоритм обработки прерываний по таймеру
В большинстве машин после получения прерывания по таймеру требуется
программными средствами произвести перезапуск часов, чтобы они по прошествии
интервала времени могли вновь прерывать работу процессора. Такие средства
являются машинно-зависимыми и мы их рассматривать не будем.
Некоторым из процедур ядра, в частности драйверам устройств и сетевым
протоколам, требуется вызов функций ядра в режиме реального времени. Напри-
мер, процесс может перевести терминал в режим ввода без обработки символов,
при котором ядро выполняет запросы пользователя на чтение с терминала через
фиксированные промежутки времени, не дожидаясь, когда пользователь нажмет
клавишу "возврата каретки" (см. раздел 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.
Построение профиля ядра включает в себя измерение продолжительности вы-
полнения системы в режиме задачи против режима ядра, а также продолжитель-
ности выполнения отдельных процедур ядра. Драйвер параметров ядра следит за
относительной эффективностью работы модулей ядра, замеряя параметры работы
системы в момент прерывания по таймеру. Драйвер параметров имеет список ад-
ресов ядра (главным образом, функций ядра); эти адреса ранее были загружены
процессом путем обращения к драйверу параметров. Если построение профиля яд-
ра возможно, программа обработки прерывания по таймеру запускает подпрограм-
му обработки прерываний, принадлежащую драйверу параметров, которая опреде-
ляет, в каком из режимов - ядра или задачи - работал процессор в момент пре-
рывания. Если процессор работал в режиме задачи, система построения профиля
увеличивает значение параметра, описывающего продолжительность выполнения в
режиме задачи, если же процессор работал в режиме ядра, система увеличивает
значение внутреннего счетчика, соответствующего счетчику команд. Пользова-
тельские процессы могут обращаться к драйверу параметров, чтобы получить
значения параметров ядра и различную статистическую информацию.
+--------------------------------+
| Алгоритм Адрес Счетчик |
| |
| 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
В момент поступления прерывания по таймеру система может выполняться в
режиме ядра или задачи, а также находиться в состоянии простоя (бездейст-
вия). Состояние простоя означает, что все процессы приостановлены в ожидании
наступления события. Для каждого состояния процессора ядро имеет внутренние
счетчики, устанавливаемые при каждом прерывании по таймеру. Позже пользова-
тельские процессы могут проанализировать накопленную ядром статистическую
информацию.
В пространстве каждого процесса имеются два поля для записи продолжи-
тельности времени, проведенного процессом в режиме ядра и задачи. В ходе об-
работки прерываний по таймеру ядро корректирует значение поля, соответствую-
щего текущему режиму выполнения процесса. Процессы-родители собирают статис-
тику о своих потомках при выполнении функции wait, беря за основу информа-
цию, поступающую от завершающих свое выполнение потомков.
В пространстве каждого процесса имеется также одно поле для ведения уче-
та использования памяти. В ходе обработки прерывания по таймеру ядро вычис-
ляет общий объем памяти, занимаемый текущим процессом, исходя из размера
частных областей процесса и его долевого участия в использовании разделяемых
областей памяти. Если, например, процесс использует области данных и стека
размером 25 и 40 Кбайт, соответственно, и разделяет с четырьмя другими про-
цессами одну область команд размером 50 Кбайт, ядро назначает процессу 75
Кбайт памяти (50К/5 + 25К + 40К). В системе с замещением страниц ядро вычис-
ляет объем используемой памяти путем подсчета числа используемых в каждой
области страниц. Таким образом, если прерываемый процесс имеет две частные
области и еще одну область разделяет с другим процессом, ядро назначает ему
столько страниц памяти, сколько содержится в этих частных областях, плюс по-
ловину страниц, принадлежащих разделяемой области. Вся указанная информация
отражается в учетной записи при завершении процесса и может быть использова-
на для расчетов с заказчиками машинного времени.
Ядро увеличивает показание системных часов при каждом прерывании по тай-
меру, измеряя время в таймерных тиках от момента загрузки системы. Это зна-
чение возвращается процессу через системную функцию time и дает возможность
определять общее время выполнения процесса. Время первоначального запуска
процесса сохраняется ядром в адресном пространстве процесса при исполнении
системной функции fork, в момент завершения процесса это значение вычитается
из текущего времени, результат вычитания и составляет реальное время выпол-
нения процесса. В другой переменной таймера, устанавливаемой с помощью сис-
темной функции stime и корректируемой раз в секунду, хранится календарное
время.
В настоящей главе был описан основной алгоритм диспетчеризации процессов
в системе UNIX. С каждым процессом в системе связывается приоритет планиро-
вания, значение которого появляется в момент перехода процесса в состояние
приостанова и периодически корректируется программой обработки прерываний по
таймеру. Приоритет, присваиваемый процессу в момент перехода в состояние
приостанова, имеет значение, зависящее от того, какой из алгоритмов ядра ис-
полнялся процессом в этот момент. Значение приоритета, присваиваемое процес-
су во время выполнения программой обработки прерываний по таймеру (или в тот
момент, когда процесс возвращается из режима ядра в режим задачи), зависит
от того, сколько времени процесс занимал ЦП: процесс получает низкий приори-
тет, если он обращался к ЦП, и высокий - в противном случае. Системная функ-
ция nice дает процессу возможность влиять на собственный приоритет путем до-
бавления параметра, участвующего в пересчете приоритета.
250
В главе были также рассмотрены системные функции, связанные с временем
выполнения системы и протекающих в ней процессов: с установкой и получением
системного времени, получением времени выполнения процессов и установкой
сигналов "будильника". Кроме того, описаны функции программы обработки пре-
рываний по таймеру, которая следит за временем в системе, управляет таблицей
ответных сигналов, собирает статистику, а также подготавливает запуск плани-
ровщика процессов, программы подкачки и "сборщика" страниц. Программа под-
качки и "сборщик" страниц являются объектами рассмотрения в следующей главе.
1. При переводе процессов в состояние приостанова ядро назначает процессу,
ожидающему снятия блокировки с индекса, более высокий приоритет по
сравнению с процессом, ожидающим освобождения буфера. Точно так же,
процессы, ожидающие ввода с терминала, получают более высокий приоритет
по сравнению с процессами, ожидающими возможности производить вывод на
терминал. Объясните причины такого поведения ядра.
*2. В алгоритме обработки прерываний по таймеру предусмотрен пересчет прио-
ритетов и перезапуск процессов на выполнение с интервалом в 1 секунду.
Придумайте алгоритм, в котором интервал перезапуска динамически меняет-
ся в зависимости от степени загрузки системы. Перевесит ли выигрыш уси-
лия по усложнению алгоритма ?
3. В шестой редакции системы UNIX для расчета продолжительности ИЦП теку-
щим процессом используется следующая формула:
decay(ИЦП) = max (пороговый приоритет, ИЦП-10);
а в седьмой редакции:
decay(ИЦП) = .8 * ИЦП;
Приоритет процесса в обеих редакциях вычисляется по формуле:
приоритет = ИЦП/16 + (базовый уровень приоритета);
Повторите пример на Рисунке 8.4, используя приведенные формулы.
4. Проделайте еще раз пример на Рисунке 8.4 с семью процессами вместо
трех, а затем измените частоту прерываний по таймеру с 60 на 100 преры-
ваний в секунду. Прокомментируйте результат.
5. Разработайте схему, в которой система накладывает ограничение на про-
должительность выполнения процесса, при превышении которого процесс за-
вершается. Каким образом пользователь должен отличать такой процесс от
процессов, для которых не должны существовать подобные ограничения ?
Каким образом должна работать схема, если единственным условием являет-
ся ее запуск из shell'а ?
6. Когда процесс выполняет системную функцию wait и обнаруживает прекра-
тившего существование потомка, ядро приплюсовывает к его ИЦП значение
поля ИЦП потомка. Чем объясняется такое "наказание" процесса-родителя ?
7. Команда nice запускает последующую команду с передачей ей указанного
значения, например:
nice 6 nroff -mm big_memo > output
Напишите на языке Си программу, реализующую команду nice.
8. Проследите на примере Рисунка 8.4, каким образом будет осуществляться
диспетчеризация процессов в том случае, если значение, передаваемое
функцией nice для процесса A, равно 5 или -5.
9. Проведите эксперимент с системной функцией renice x y, где x - код
идентификации процесса (активного), а y - новое значение nice для ука-
занного процесса.
10. Вернемся к примеру, приведенному на Рисунке 8.6. Предположим, что груп-
пе, в которую входит процесс A, выделяется 33% процессорного времени, а
группе, в которую входит процесс B, - 66% процессорного времени. В ка-
кой последовательности будут исполняться процессы ? Обобщите алгоритм
вычисления приоритетов таким образом, чтобы значение группового ИЦП ус-
реднялось.
251
11. Выполните команду date. Команда без аргументов выводит текущую дату:
указав аргумент, например:
date mmddhhmmyy
(супер)пользователь может установить текущую дату в системе
(соответственно, месяц, число, часы, минуты и год). Так,
date 0911205084
устанавливает в качестве текущего времени 11 сентября 1984 года 8:50
пополудни.
12. В программах можно использовать функцию пользовательского
уровня sleep:
sleep(seconds);
с помощью которой выполнение программы приостанавливается на указанное
число секунд. Разработайте ее алгоритм, в котором используйте системные
функции alarm и pause. Что произойдет, если процесс вызовет функцию
alarm раньше функции sleep ? Рассмотрите две возможности: 1) действие
ранее вызванной функции alarm истекает в то время, когда процесс нахо-
дится в состоянии приостанова, 2) действие ранее вызванной функции
alarm истекает после завершения функции sleep.
*13. Обратимся еще раз к последней проблеме. Ядро может выполнить переключе-
ние контекста во время исполнения функции sleep между вызовами alarm и
pause. Тогда есть опасность, что процесс получит сигнал alarm до того,
как вызовет функцию pause. Что произойдет в этом случае ? Как вовремя
распознать эту ситуацию ?
252
Last-modified: Fri, 2-Jun-95 11:25:03 GMT