Управление процессорами и заданиями в однопроцессорном вычислительном комплексе. Алгоритмы планирования процессов
Эти две подсистемы ОС выполняют сходные функции: планирование загрузки процессоров и планирование загрузки вычислительных комплексов, имеют сходные механизмы планирования, работающие на разных уровнях - процессов и заданий пользователя соответственно. В однопроцессорной ЭВМ подсистема управления процессорами выполняет единственную функцию: диспетчирования процессов, то есть планирует загрузку ЦП. Система управления заданиями управляет прохождением заданий в ВС и выполняет следующие функции: 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 различных уровня приоритета для класса.
Классы бывают: Критический или высокий - для программ управления процессом или связью с другими компьютерами; Обыкновенный - для большинства программ пользователя; Запасной или низкий - задачи и процессы из этого класса выполняются, если в очереди нет критических или обыкновенных задач.
