Страница:
В системе разделения времени ядро предоставляет процессу ресурсы цент-
рального процессора (ЦП) на интервал времени, называемый квантом, по истече-
нии которого выгружает этот процесс и запускает другой, периодически переу-
порядочивая очередь процессов. Алгоритм планирования процессов в системе
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 раза больше по сравнению с каждым процессом из четвер-
той. В этом примере всем процессам в группе выделяется равное время, пос-
кольку продолжительность цикла, реализуемого каждым процессом, заранее не
установлена.
Реализация этой схемы довольно проста, что и делает ее привлекательной.
В формуле расчета приоритета процесса появляется еще один термин - "приори-
тет группы справедливого раздела". В пространстве процесса также появляется
новое поле, описывающее продолжительность ИЦП на основе справедливого разде-
ла, общую для всех процессов из группы. Программа обработки прерываний по
таймеру увеличивает значение этого поля для текущего процесса и ежесекундно
пересчитывает значения соответствующих полей для всех процессов в системе.
Новая компонента формулы вычисления приоритета процесса представляет собой
нормализованное значение ИЦП для каждой группы. Чем больше процессорного
рального процессора (ЦП) на интервал времени, называемый квантом, по истече-
нии которого выгружает этот процесс и запускает другой, периодически переу-
порядочивая очередь процессов. Алгоритм планирования процессов в системе
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 раза больше по сравнению с каждым процессом из четвер-
той. В этом примере всем процессам в группе выделяется равное время, пос-
кольку продолжительность цикла, реализуемого каждым процессом, заранее не
установлена.
Реализация этой схемы довольно проста, что и делает ее привлекательной.
В формуле расчета приоритета процесса появляется еще один термин - "приори-
тет группы справедливого раздела". В пространстве процесса также появляется
новое поле, описывающее продолжительность ИЦП на основе справедливого разде-
ла, общую для всех процессов из группы. Программа обработки прерываний по
таймеру увеличивает значение этого поля для текущего процесса и ежесекундно
пересчитывает значения соответствующих полей для всех процессов в системе.
Новая компонента формулы вычисления приоритета процесса представляет собой
нормализованное значение ИЦП для каждой группы. Чем больше процессорного