Файл: А. В. Гордеев А. Ю. Молчанов системное программное обеспечение электронный вариант книги издательства Питер СанктПетербург Челябинск юургу каф. Автоматика и управление 2002 2 Предисловие Настоящий учебник.pdf

65
полнены, несмотря на то, что прошло несколько лет (!) с момента их планирования.
Поэтому вопрос гарантии обслуживания является очень актуальным.
Более жестким требованием к системе, чем просто гарантированное заверше- ние процесса, является его гарантированное завершение к указанному моменту времени или за указанный интервал времени. Существуют различные дисциплины диспетчеризации, учитывающие жесткие временные ограничения, но не сущест- вует дисциплин, которые могли бы предоставить больше процессорного времени,
чем может быть в принципе выделено.
Планирование с учётом жестких временных ограничений легко реализовать,
организуя очередь готовых к выполнению процессов в порядке возрастания их вре- менных ограничений. Основным недостатком такого простого упорядочения яв- ляется то, что процесс (за счёт других процессов) может быть обслужен быстрее,
чем это ему реально необходимо. Для того чтобы избежать этого, проще всего процессорное время выделять все-таки квантами. Гарантировать обслуживание можно следующими тремя способами:
♦ выделять минимальную долю процессорного времени некоторому классу процессов, если по крайней мере один из них готов к исполнению. Например,
можно отводить 20 % от каждых 10 мс процессам реального времени, 40 % от каж- дых 2 с – интерактивным процессам и 10 % от каждых 5 мин – пакетным (фоно- вым) процессам;
♦ выделять минимальную долю процессорного времени некоторому конкрет- ному процессу, если он готов к выполнению;
♦ выделять столько процессорного времени некоторому процессу, чтобы он мог выполнить свои вычисления к сроку.
Для сравнения алгоритмов диспетчеризации обычно используются следующие критерии:
♦ Использование (загрузка) центрального процессора (CPU utilization). В
большинстве персональных систем средняя загрузка процессора не превышает 2-
3%, доходя в моменты выполнения сложных вычислений и до 100 %. В реальных системах, где компьютеры выполняют очень много работы, например, в серверах,

66
загрузка процессора колеблется в пределах 15-40% для легко загруженного про- цессора и до 90-100 % – для сильно загруженного процессора.
♦ Пропускная способность (CPU throughput). Пропускная способность процес- сора может измеряться количеством процессов, которые выполняются в единицу времени.
♦ Время оборота (turnaround time). Для некоторых процессов важным крите- рием является полное время выполнения, то есть интервал от момента появления процесса во входной очерёди до момента его завершения. Это время названо вре- менем оборота и включает время ожидания во входной очерёди, время ожидания в очерёди готовых процессов, время ожидания в очерёдях к оборудованию, время выполнения в процессоре и время ввода/вывода.
♦ Время ожидания (waiting time). Под временем ожидания понимается сум- марное время нахождения процесса в очерёди готовых процессов.
♦ Время отклика (response time). Для интерактивных программ важным пока- зателем является время отклика или время, прошедшее от момента попадания про- цесса во входную очередь до момента первого обращения к терминалу. Очевидно,
что простейшая стратегия краткосрочного планировщика должна быть направлена на максимизацию средних значений загруженности и пропускной способности,
времени ожидания и времени отклика.
Правильное планирование процессов сильно влияет на производительность всей системы. Можно выделить следующие главные причины, приводящие к уменьшению производительности системы:
♦ Накладные расходы на переключение процессора. Они определяются не только переключениями контекстов задач, но и (при переключении на процессы другого приложения) перемещениями страниц виртуальной памяти, а также необ- ходимостью обновления данных в кэше (коды и данные одной задачи, находящие- ся в кэше, не нужны другой задаче и будут заменены, что приводит к дополнитель- ным задержкам).
♦ Переключение на другой процесс в тот момент, когда текущий процесс вы- полняет критическую секцию, а другие процессы активно ожидают входа в свою

67
критическую секцию (см. главу 6). В этом случае потери будут особо велики (хотя вероятность прерывания выполнения коротких критических секций мала). В случае использования мультипроцессорных систем применяются следующие методы по- вышения производительности системы:
♦ совместное планирование, при котором все потоки одного приложения (не- блокированные) одновременно выбираются для выполнения процессорами и одно- временно снимаются с них (для сокращения переключений контекста);
♦ планирование, при котором находящиеся в критической секции задачи не прерываются, а активно ожидающие входа в критическую секцию задачи не выби- раются до тех пор, пока вход в секцию не освободится;
♦ планирование с учётом так называемых «советов» программы (во время её
выполнения). Например, в известной своими новациями ОС Mach имелись два класса таких советов (hints) – указания (разной степени категоричности) о снятии текущего процесса с процессора, а также указания о том процессе, который должен быть выбран взамен текущего.
Диспетчеризация задач с использованием динамических приоритетов
При выполнении программ, реализующих какие-либо задачи контроля и управления (что характерно, прежде всего, для систем реального времени), может случиться такая ситуация, когда одна или несколько задач не могут быть реали- зованы (решены) в течение длительного промежутка времени из-за возросшей на- грузки в вычислительной системе. Потери, связанные с невыполнением таких за- дач, могут оказаться больше, чем потери от невыполнения программ с более высо- ким приоритетом. При этом оказывается целесообразным временно изменить при- оритет «аварийных» задач (для которых истекает отпущенное для них время обра- ботки). После выполнения этих задач их приоритет восстанавливается. Поэтому почти в любой ОС реального времени имеются средства для изменения приоритета программ
1
. Есть такие средства и во многих ОС, которые не относятся к классу
ОСРВ. Введение механизмов динамического изменения приоритетов позволяет
1
Dynamic priority variation.

68
реализовать более быструю реакцию системы на короткие запросы пользователей,
что очень важно при интерактивной работе, но при этом гарантировать выполне- ние любых запросов.
Рассмотрим, например, как реализован механизм динамических приоритетов в
ОС UNIX, которая, как известно, не относится к ОСРВ. Приоритет процесса вы- числяется следующим образом [70]. Во-первых, в вычислении участвуют значения двух полей дескриптора процесса – p_nice и р_cpu. Первое из них назначается пользователем явно или формируется по умолчанию с помощью системы програм- мирования. Второе поле формируется диспетчером задач (планировщиком разде- ления времени) и называется системной составляющей или текущим приоритетом.
Другими словами, каждый процесс имеет два атрибута приоритета, с учётом кото- рого и распределяется между исполняющимися задачами процессорное время: те-
кущий приоритет, на основании которого происходит планирование, и заказанный
относительный приоритет, называемый nice number (или просто nice).
Схема нумерации (числовых значений) текущих приоритетов различна для различных версий UNIX. Например, более высокому значению текущего приорите- та может соответствовать более низкий фактический приоритет планирования.
Разделение между приоритетами режима ядра и задачи также зависит от версии.
Рассмотрим частный случай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий приоритет) до 127. (наивысший приоритет). Процессы, вы- полняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра.
Для режима задачи приоритет меняется в диапазоне 0-65, для режима ядра – 66-95
(системный диапазон). Процессы, приоритеты которых лежат в диапазоне 96-127,
являются процессами с фиксированным приоритетом, не изменяемым операцион- ной системой, и предназначены для поддержки приложений реального времени.
Процессу, ожидающему недоступного в данный момент ресурса, система оп- ределяет значение приоритета сна, выбираемое ядром из диапазона системных приоритетов и связанное с событием, вызвавшее это состояние. Когда процесс про- буждается, ядро устанавливает значение текущего приоритета процесса равным приоритету сна. Поскольку приоритет такого процесса находится в системном

69
диапазоне и выше, чем приоритет режима задачи, вероятность предоставления процессу вычислительных ресурсов весьма велика. Такой подход позволяет, в ча- стности, быстро завершить системный вызов, выполнение которого, в свою оче- редь, может блокировать некоторые системные ресурсы.
После завершения системного вызова перед возвращением в режим задачи яд- ро восстанавливает приоритет режима задачи, сохраненный перед выполнением системного вызова. Это может привести к понижению приоритета, что, в свою очередь, вызовет переключение контекста.
Текущий приоритет процесса в режиме задачи p_priuser, как мы только что отметили, зависит от значения nice number и степени использования вычислитель- ных ресурсов р_cpu:
p_priuser - a*p_nice - b*р_cpu
Задача планировщика разделения времени – справедливо распределить вычис- лительный ресурс между конкурирующими процессами. Для принятия решения о выборе следующего запускаемого процесса планировщику необходима инфор- мация об использовании процессора. Эта составляющая приоритета уменьшается обработчиком прерываний таймера по каждому «тику» таймера. Таким образом,
пока процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается.
Каждую секунду ядро пересчитывает текущие приоритеты процессов, готовых к запуску (приоритеты которых меньше некоторого порогового значения, в нашем примере эта величина равна 65), последовательно увеличивая их. Это осуществ- ляется за счёт того, что ядро последовательно уменьшает отрицательную компо- ненту времени использования процессора. Как результат, эти действия приводят к перемещению процессов в более приоритетные очерёди и повышают вероятность их последующего запуска.
Возможно использование следующей формулы:
р_cpu = р__cpu/2
Это правило проявляет недостаток нивелирования приоритетов при повыше- нии загрузки системы. Происходит это потому, что в таком случае каждый процесс

70
получает незначительный объём вычислительных ресурсов и, следовательно, имеет малую составляющую р_cpu, которая ещё более уменьшается благодаря формуле пересчета величины р_сpu. В результате степень использования процессора пере- стает оказывать заметное влияние на приоритет, и низкоприоритетные процессы
(то есть процессы с высоким значением nice number) практически «отлучаются» от вычислительных ресурсов системы.
В некоторых версиях ОС UNIX для пересчета значения р_cpu используется другая формула:
p_cpu = p_cpu*(2*load)/(2*load+1)
Здесь параметр load равен среднему числу процессов, находившихся в очерё- ди на выполнение за последнюю секунду, и характеризует среднюю загрузку сис- темы за этот период времени. Такой алгоритм позволяет частично избавиться от недостатка планирования по формуле p_cpu = р_сpu/2, поскольку при значитель- ной загрузке системы уменьшение р_срu при пересчете будет происходить мед- леннее.
Описанные алгоритмы планирования позволяют учесть интересы низкопри- оритетных процессов, так как в результате длительного ожидания очерёди на за- пуск приоритет таких процессов увеличивается, соответственно увеличивается и вероятность запуска. Эти алгоритмы также обеспечивают более вероятный выбор планировщиком интерактивных процессов по отношению к вычислительным (фо- новым). Такие задачи, как командный интерпретатор или редактор, большую часть времени проводят в ожидании ввода, имея, таким образом, высокий приоритет
(приоритет сна). При наступлении ожидаемого события (например, пользователь осуществил ввод данных) им сразу же предоставляются вычислительные ресурсы.
Фоновые процессы, потребляющие значительные ресурсы процессора, имеют вы- сокую составляющую р_срu и, как следствие, менее высокий приоритет.
Аналогичные механизмы имеют место и в таких ОС, как OS/2 или Windows
NT. Правда, алгоритмы изменения приоритета задач в этих системах иные. Напри- мер, в Windows NT каждый поток (тред) имеет базовый уровень приоритета, ко- торый лежит в диапазоне от двух уровней ниже базового приоритета процесса, его

71
породившего, до двух уровней выше этого приоритета, как показано на рис. 2.4.
Базовый приоритет процесса определяет, сколь сильно могут различаться при- оритеты потоков процесса и как они соотносятся с приоритетами потоков других процессов. Поток наследует этот базовый приоритет и может изменять его так,
чтобы он стал немного больше или немного меньше. В результате получается при- оритет планирования, с которым поток и начинает исполняться. В процессе испол- нения потока его приоритет может отклоняться от базового.
На рис. 2.4 показан динамический приоритет потока, нижней границей кото- рого является базовый приоритет потока, а верхняя – зависит от вида работ, испол- няемых потоком. Например, если поток обрабатывает пользовательский ввод, то диспетчер задач Windows NT поднимает его динамический приоритет; если же он выполняет вычисления, то диспетчер постепенно снижает его приоритет до базово- го. Снижая приоритет одного процесса и поднимая приоритет другого, подсистемы могут управлять относительной приоритетностью потоков внутри процесса.

72
токов с низкими приоритетами. Система прекращает исполнение или вытесняет
(preempts) текущий поток, если становится готовой к выполнению другая задача
(поток) с более высоким приоритетом.
Существует группа очерёдей – по одной для каждого приоритета. Windows NT
поддерживает 32 уровня приоритетов; потоки делятся на два класса: реального времени и переменного приоритета. Потоки реального времени, имеющие при- оритеты от 16 до 31 – это высокоприоритетные потоки, используемые про- граммами с критическим временем выполнения, то есть требующие немедленного внимания системы (по терминологии Microsoft).
Диспетчер задач просматривает очерёди, начиная с самой приоритетной. При этом если очередь пустая, то есть нет готовых к выполнению задач с таким при- оритетом, осуществляется переход к следующей очерёди. Следовательно, если есть задачи, требующие процессор немедленно, они будут обслужены в первую оче- редь. Для собственно системных модулей, функционирующих в статусе задач, за- резервирована очередь с номером 0.
Большинство потоков в системе относятся к классу переменного приоритета с уровнями приоритета (номером очерёди) от 1 до 15. Эти очерёди используются по- токами с переменным приоритетом (variable priority), так как диспетчер задач кор- ректирует их приоритеты по мере выполнения задач для оптимизации отклика сис- темы. Диспетчер приостанавливает исполнение текущего потока после того, как тот израсходует свой квант времени. При этом если прерванный тред – это поток переменного приоритета, то диспетчер задач понижает его приоритет на единицу и перемещает в другую очередь. Таким образом, приоритет потока, выполняющего много вычислений, постепенно понижается (до значения его базового приоритета).
С другой стороны, диспетчер повышает приоритет потока после освобождения за- дачи (потока) из состояния ожидания. Обычно добавка к приоритету потока опре- деляется кодом исполнительной системы, находящимся вне ядра ОС, однако вели- чина этой добавки зависит от типа события, которого ожидал заблокированный тред. Так, например, поток, ожидавший ввода очерёдного байта с клавиатуры, по- лучает большую добавку к значению своего приоритета, чем процесс вво-