Механизм планирования

Многоуровневая организация вычислений в ОС накладывает отпечаток на построение механизма планирования. Существование разных уровней вычислений позволяет обеспечить схему планирования, при которой на каждом уровне могут быть использованы процессы для выбора остальных процессов из своего или соседнего уровня. Планирующие процессы могут быть изменены или замещены, как и любые процессы в системе.

При разделении функций планирования глобальный алгоритм разбивается на ряд локальных функций, в результате выполнения которых происходит выбор наиболее приоритетного процесса для предоставления ему ЦП.

Общий вид дерева выбора процесса в уровневой ОС представлен на рис. 5.1. Дерево планирования рассматривается в виде цепочки планировщиков PP (L_i), где i =1,2,3. Локальный планировщик i -го уровня PP (L_i ) выбирает один из процессов своего уровня или активный процесс следующего уровня i +1. Запуск планировщика PP (L_i) происходит на уровне i –1. Планировщик PP (L_i) в зависимости от складывающейся ситуации может либо запустить процесс своего же уровня (или уровня i +1), либо передать управление процессу PP (L_{i –1} ).

Процессы внутри уровня, из которых выбираются активные процессы на представление им: П₁ (L_i), …П _k (L_i), выполняют системные функции в зависимости от функционального назначения уровня.

В общем случае в каждом планировщике производятся следующие действия: планировщик просматривает процессы, которым необходимо предоставить ЦП, и выставляет приоритет по определенному критерию. Затем в зависимости от приоритетов происходит переупорядочение очереди.

На каждом уровне вычисления используется свой критерий при назначении приоритетов активным процессам. Критерии независимы друг от друга и предназначены для учета статистических и динамических характеристик процессов. Процессы планирования используют алгоритмы, в которых учитываются различные факторы. При этом учитывается ступень иерархии, на которой находится планируемый процесс. Активным процессам, имеющим необходимые ресурсы и не находящимся в очереди ожиданий, назначается приоритет, и они становятся в очередь к ЦП.

Очередность работы планировщиков определяется в зависимости от ступени иерархии и системных приоритетов процессов, назначаемых изначально в зависимости от вида работ.

Распределение многоуровнего планирования имеет, как правило, три уровня: супервизора, ядра и мониторов. На каждом из уровней вычислений имеются очереди из активных процессов. Планировщик уровня выбирает процесс с наибольшим приоритетом и передает управление нижней сфере вычисления. Если там нет готовых процессов, то ЦП передается предварительно выбранному активному процессу нижнего уровня. На каждом из уровней планировщиками осуществляются следующие действия.

На уровне вычисления супервизора имеется ряд привилегированных процессов (процессы, осуществляющие связь с терминалами, процессы обработки аварийных сообщений и др.), которым присваивается абсолютный приоритет. Эти процессы ставятся первыми в очереди к ЦП. Остальные процессы ставятся в очередь согласно своим приоритетам, которые задаются априори либо назначаются на основании вычислений по выбранным критериям, проводимых на других уровнях. Выбор процессов из упорядоченной очереди происходит путем последовательного перебора элементов очереди. В общем случае очередь отражает динамические состояния процессов. Во время решения различные процессы могут быть приостановлены (ждут наступления события, ждут конца обмена и т.п.). Ожидающие процессы в этом случае блокируются. Планирующий процесс уровня супервизора PP (L ₁ ) выбирает из очереди первый ждущий процесс и предоставляет ему ЦП.

На уровне ядра планировщик PP (L ₂ ) проверяет процессы следующего внешнего уровня для предоставления им ЦП. Процессы от задач различных мониторов могут претендовать на решение. Активным процессам (имеющим ресурсы) назначается приоритет и они ставятся в очередь. В качестве основного критерия берется крайний срок решения задачи, т.е. момент времени, к которому задача должна быть решена в системе. Этот критерий учитывает ряд факторов, присущих задачам в системе: момент поступления задачи j в систему (t_nj), заказываемое (t_закj) и фактическое время решения (t_решj) задачи j в ЦП на момент перепланирования задач, время нахождения задачи j в системе (t_нj), заказываемое количество ресурсов R_i , статус задач, определяемый постоянной времени класса K_j. На основании этих факторов вычисляется крайний срок решения для задачи. Первыми ставятся в очередь задачи, имеющие наименьший крайний срок решения задачи.

На уровне мониторов планирующие процессы PP (L ₃ ) выбирают из подчиненных задач задачи на предоставление им ЦП. В каждом из мониторов свой планировщик, который планирует решение подчиненных ему задач. При назначении приоритетов планировщики учитывают статус монитора. Первыми в очереди оказываются задачи, которые раньше других поступили в систему. В мониторе коллективного пользования планирующий процесс вычисляет приоритет на основании критерия МИНРЕС (минимально заказываемое количество ресурсов системы). Учитывается количество заказываемых листов памяти (оперативной и внешней), возможное время решения задачи ЦП, предполагаемое количество листов выдачи на выводные устройства, возможность работы с файловой системой. Первыми в очереди оказываются задачи, которые меньше других заказывают ресурсов системы. На уровне вычисления прикладной задачи планирующего процесса нет. Требования процессов на предоставление им ЦП учитываются планировщиком, находящимся на уровне монитора.

Организация планирования в виде уровневой структуры имеет ряд преимуществ. Функции планировщиков упрощаются и локализуются по уровням вычислений. Критерии при назначении приоритетов процессам на каждом уровне вычислений разные и не зависят друг от друга. Алгоритмы на каждом уровне вычисления можно менять независимо от других алгоритмов. Общая схема планирования при этом не меняется, интерфейс между планировщиками разных уровней остается неизменным, меняется только алгоритм внутри планировщиков уровней. Это удобно на конечном этапе проектирования системы, когда приходится варьировать различные факторы планирования.

Механизм планирования ОС, построенный в виде иерархического дерева выбора процесса, позволяет разбить глобальные функции планировщика на ряд локальных алгоритмов, расположенных каждый на своем уровне иерархии. Многоуровневое планирование позволяет на каждом уровне иерархии применять свой алгоритм для выбора процесса на предоставление ему ресурса центральным процессором. Алгоритмы планирования на каждом из уровней возможно легко менять или модифицировать без изменения системы в целом, что особенно важно на конечном этапе реализации системы.

Дата добавления: 2014-12-29