Эти
две подсистемы ОС выполняют сходные функции: планирование загрузки процессоров
и планирование загрузки вычислительных комплексов, имеют сходные механизмы
планирования, работающие на разных уровнях - процессов и заданий пользователя
соответственно.
В
однопроцессорной ЭВМ подсистема управления процессорами выполняет единственную
функцию: диспетчирования процессов, то есть планирует загрузку ЦП.
Система
управления заданиями управляет прохождением заданий в ВС и выполняет следующие
функции:
1.Предоставление языковых средств управления работами в
вычислительной системе (Job Control Language (JCL) в ОС ЕС ЭВМ , Shell
в UNIX).
2.Ввод и интерпретация заданий/команд.
3.Выделение и освобождение необходимых ресурсов.
4.Планирование заданий на выполнение.
5.Сбор и предоставление информации о состоянии заданий.
В однопроцессорном
вычислительном комплексе существует три основных уровня планирования:
1.Планирование
на верхнем уровне или планирование заданий.
На
этом уровне осуществляется выбор заданий пользователем для выполнения и их
запуск. Выбранные задания становятся готовыми процессами. Эту работу выполняет
системный компонент - планировщик заданий.
2.Планирование
на нижнем уровне или диспетчирование процессов.
Здесь
осуществляется выбор готового процесса для выполнения, то есть предоставления
ему ЦП. Выбранный процесс становится активным. Эту работу выполняет системный
компонент - диспетчер.
3.Планирование
на промежуточном уровне.
На
данном уровне определяется, каким процессам будет разрешено состязаться за
захват ЦП, то есть быть готовыми, и какие процессы будут кратковременно
приостановлены (задержаны) для оптимизации загрузки системы. Промежуточное
планирование управляет текущей производительностью вычислительной системы.
В
соответствии с тремя уровнями планирования, из которых два обязательны,
существует двух и трехуровневые системы планирования.
Типичная
двухуровневая система планирования имеет следующий вид:
Двухуровневая
процедура вводится в системах с ограниченным мультипрограммированием, что
определяется ограниченными ресурсами и производительностью вычислительной
системы. Это основная схема для ВС с реальной ОП без поддержки систем реального
времени (СРВ).
В
вычислительных системах с ВП, допускающих неограниченный уровень
мультипрограммирования и СРВ, требующих высокую реактивность системы,
используется трехуровневая система планирования, представленная на рисунке 2.
Эффективное
планирование заданий и процессов является сложной проблемой, поскольку должно
учитываться много противоречивых требований, таких как:
·
cправедливость;
·
максимальная пропускная способность;
·
приемлемое время ответа для максимального числа
интерактивных пользователей;
·
предсказуемость (задание должно выполняться
примерно за одно время независимо от загрузки вычислительной системы);
·
минимум накладных расходов на выполнение
планирования;
·
сбалансированность использования ресурсов;
·
исключение бесконечного откладывания;
·
учет приоритетов;
·
отдавать предпочтение процессам, занимающие
ключевые ресурсы;
·
плавно деградировать при увеличении нагрузок.
Для
того чтобы реализовать перечисленные требования, механизм планирования должен
знать и учитывать следующие факторы:
·
является ли процесс обменным (активно использующим
операции ввода/вывода) или вычислительным (активно использующим процессор);
·
является ли процесс пакетным или диалоговым;
·
уровень реактивности интерактивного процесса;
·
приоритетность процесса;
·
частота прерываний по отсутствию нужной
страницы;
·
частота прерывания с низкого приоритета на
высокий;
·
длительность периода ожиданий ЦП процесса;
·
суммарное использование времени ЦП и оценочное
время, необходимое для завершения.
Существует
множество различных алгоритмов планирования процессов, преследующих различные
цели и обеспечивающих различное качество мультипрограммирования. Среди этого
множества алгоритмов рассмотрим подробнее две группы наиболее часто
встречающихся алгоритмов: алгоритмы, основанные на приоритетах, и
алгоритмы, основанные на квантовании.
В
соответствии с алгоритмами, основанными на квантовании, смена активного
процесса происходит, если:
1. процесс
завершился и покинул систему,
2. произошла
ошибка,
3. процесс
перешел в состояние ОЖИДАНИЕ,
4. исчерпан
квант процессорного времени, отведенный данному процессу.
Процесс,
который исчерпал свой квант, переводится в состояние ГОТОВНОСТЬ и ожидает, когда
ему будет предоставлен новый квант процессорного времени, а на выполнение в
соответствии с определенным правилом выбирается новый процесс из очереди готовых.
Таким образом, ни один процесс не занимает процессор надолго, поэтому
квантование широко используется в системах разделения времени.
Кванты,
выделяемые процессам, могут быть одинаковыми для всех процессов или различными.
Кванты, выделяемые одному процессу, могут быть фиксированной величины или
изменяться в разные периоды жизни процесса. Процессы, которые не полностью
использовали выделенный им квант (например, из-за ухода на выполнение операций
ввода-вывода), могут получить или не получить компенсацию в виде привилегий при
последующем обслуживании. По разному может быть организована очередь готовых
процессов: циклически, по правилу "первый пришел - первый обслужился"
(FIFO) или по правилу "последний пришел - первый обслужился" (LIFO).
Многие
современные системы планирования основывается на системе приоритетов, которая воплощается
в соответствующих дисциплинах планирования. Приоритет - это число,
характеризующее степень привилегированности процесса при использовании ресурсов
вычислительной машины, в частности, процессорного времени: чем выше приоритет,
тем выше привилегии.
Приоритеты
подразделяются на статические, назначаемые извне системы администрацией ВЦ, и
динамические, присваиваемые системой автоматически в соответствии с поведением,
потребностями в ресурсах и прочими характеристиками процессов.
Начальные
значения динамических приоритетов обычно устанавливаются на основе статического,
но действуют в течение короткого времени. Существует две разновидности
приоритетных алгоритмов: алгоритмы, использующие относительные приоритеты, и
алгоритмы, использующие абсолютные приоритеты.
В
обоих случаях выбор процесса на выполнение из очереди готовых осуществляется
одинаково: выбирается процесс, имеющий наивысший приоритет. По-разному решается
проблема определения момента смены активного процесса. В системах с
относительными приоритетами активный процесс выполняется до тех пор, пока он
сам не покинет процессор, перейдя в состояние ОЖИДАНИЕ (или же произойдет
ошибка, или процесс завершится). В системах с абсолютными приоритетами выполнение
активного процесса прерывается еще при одном условии: если в очереди готовых
процессов появился процесс, приоритет которого выше приоритета активного
процесса. В этом случае прерванный процесс переходит в состояние готовности.
Во
многих операционных системах алгоритмы планирования построены с использованием
как квантования, так и приоритетов. Например, в основе планирования лежит
квантование, но величина кванта и/или порядок выбора процесса из очереди
готовых определяется приоритетами процессов.
Для
установления значений приоритетов заданий и процессов используются следующие
дисциплины планирования и их различные комбинации.
1. Планирование
по сроку завершения, гарантирующее выполнение задания в назначенное время. Это
сложная проблема в мультипрограммных системах, поскольку пользователь должен
точно указать все требуемые ресурсы. Необходимо активное управление ресурсами,
что связано с высокими накладными расходами. Недостаток: несправедливо к другим
пользователям (протекционизм).
2. Планирование
по принципу FIFO, где ЦП предоставляется процессам в порядке готовности,
и они выполняются до завершения или блокировки. Это самая простая дисциплина
планирования фактически без переключения ЦП. Формально - справедливый принцип,
но фактически не справедлив, так как длинные задания заставляют ждать короткие.
Менее важные - заставляют ждать более важные. Характеризуется небольшим
колебанием времени выполнения и большей предсказуемостью, нежели другие дисциплины.
Используется только в пакетных системах, не гарантирует реактивности системы и
обычно в комбинации с другими дисциплинами.
3. Циклическое
или круговое планирование, где каждому готовому процессу в цикле представляется
квант времени. По истечении кванта времени процесс переходит в конец очереди
готовых процессов. При блокировке квант теряется. Эффективно для СРВ, так как
гарантирует приемлемое время ответа для всех интерактивных пользователей.
Основная проблема выбора - оптимальный размер кванта. Стараются выбрать такой
размер, чтобы большинство рядовых запросов обслуживались за один квант.
4. Планирование
по принципу - "кратчайшее задание - первым" или "по
наименьшему оставшемуся времени выполнения". Максимальный приоритет
назначается процессу, либо заданию с минимальным оценочным временем до завершения.
Недостаток: время ожидания на большие задания растет; большие издержки на
регистрацию истекшего времени обслуживания. Достоинство: сокращение очередей
заданий и ожидающих процессов; стремится к минимальному времени ожиданий для
заданий.
5. Планирование
по времени нахождения в системе, в которой приоритет есть функция времени
обслуживания и времени ожидания.
Приоритет
=
Приоритет
отдает меньшее предпочтение коротким заданиям и без предубеждения относится к
длинным. Чем реже процесс получает ЦП, тем выше его приоритет. Задания с
вводом/выводом повышают приоритет.
Сеть
многоуровневых очередей с обратными связями (рисунок 3), которая имеет
следующие достоинства:
·
определяет характер процессов и разделяет на
соответствующие категории;
·
отдает предпочтение коротким процессам;
·
отдает предпочтение обменным процессам с хорошим
коэффициентом использования устройств ввода/вывода. Это наиболее совершенный и
сложный механизм планирования.
Сеть
представляет собой упорядоченную структуру очередей готовых процессов,
работающих с различными дисциплинами обслуживания. Каждый процесс входит в сеть
очередей с конца верхней очереди и перемещается по FIFO пока не получит ЦП.
Процесс выполняется. Если в течение кванта процесс запросил выполнение операции
ввода/вывода, то он после завершения операции будет установлен в очередь
готовых процессов текущего уровня. Если в течение выделенного кванта времени
процесс не завершился, то он устанавливется в очередь готовых процессов
следующего уровня, у которого понижен приоритет и увеличен квант времени. Таким
образом, чем больше время работы процесса, тем больший квант времени
выделяется, но меньше приоритет, что приводит к получению ЦП реже, но на более
длительный период.
Таким
образом, сеть многоуровневых очередей - это адаптивный механизм планирования,
который реагирует на изменение поведения системы.
В
ОС OS/2, UNIX приоритеты устанавливаются с помощью класса приоритета и уровня
приоритета в классе. Есть три класса приоритета и 32 различных уровня
приоритета для класса.
Классы
бывают:
Критический или высокий - для программ управления
процессом или связью с другими компьютерами;
Обыкновенный - для большинства программ
пользователя;
Запасной или низкий - задачи и процессы из этого
класса выполняются, если в очереди нет критических или обыкновенных задач.
|