Планирование и диспетчеризация. Алгоритмы планирования

Планирование и диспетчеризация. Общие положения.

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

- переключение в режим ядра;

- сохранение контекста;

- сохранение карты памяти;

- запуск блока управления памятью с картой памяти нового процесса;

- восстановление контекста нового процесса из таблицы процессов;

- запуск нового процесса и переключение в режим пользователя.

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

- процессы, ограниченные возможностями процессора. Характеризуются длинными периодами использования процессора и редким ожиданием ввода/вывода;

- процессы, ограниченные возможностями устройств ввода/вывода. Короткие периоды вычислений и частое ожидание устройств ввода/вывода.

Ключевым вопросом планирования является выбор момента для принятия решений. Самые распространенные ситуации:

- создание нового процесса - планировщику необходимо выбрать: запустить дочерний процесс либо продолжить выполнять родительский;

- когда процесс завершает работу, планировщик должен выбрать один процесс из списка готовых;

- процесс блокируется на операции ввода/вывода либо семафоре;

- при возникновении прерывания от устройства ввода/вывода планировщик может восстановить прерванный процесс либо запустить процесс, ожидаюий это прерывание, либо какой-то другой процесс;

- при каждом k-ом прерывании по таймеру алгоритмы планирования можно разделить на 2 больших типа:

‡ без переключений - выбранный процесс может работать до завершения блокировки либо пока сам не отдаст процессор;

‡ с переключениями (приоритетное плаинрование) - выбранному процессу позволяют работать некоторое максимально возможное фиксированное время. Если к концу этого времени процесс не заблокируется или не завершится, управление передается другому процессу. Такие алгоритмы требуют прерывание по таймеру.

Задачи алгоритмов планирования:

- справедливость - каждому процессу предоставляется справедливая доля процессорного времени. Сопоставимые процессы получают сопоставимое обслуживание;

- принудительное применение политики планирования;

- контроль занятости всех частей системы - при постоянной работе всех компонентов эффективность системы будет выше, чем, если отдельные компоненты будут работать попеременно.

Для систем пакетной обработки данных:

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

- оборотное время - статистически усредненное время от момента получения задачи до ее выполнения.

Стоит заметить, что алгоритм, увеличивающий пропускную способность, необязательно минимизирует оборотное время.

Для интерактивных систем:

- задача минимизации времени отклика - время между получением команды и получением результата;

- достижение соразмерности - задачи должны исполняться такое время, какое от них ожидает пользователь.

Для систем реального времени (мультимедийные системы):

- жесткие сроки выполнения некоторых операций с целью предотвращения потери данных;

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

Алгоритмы планирования.

Для систем пакетной обработки данных:

- FIFO (First In First Out) - задачи поступают на выполнение по мере поступления в систему. Алгоритм легок для понимания и программирования. Не выполняется задача баланса использования системы;

- «кратчайшая задача – первая» - если в очереди одновременно есть несколько задач, на исполнение выбирается самая короткая. Такой алгоритм минимизирует оборотное время. Версией этого алгоритма с переключением является алгоритм "наименьшее оставшееся время выполнения".

Для интерактивных систем:

- циклическое планирование - каждому процессу предоставляется квант процессорного времени. Если по его истечении процесс продолжает работать, то управление передается другому процессу, а сам процесс помещается в конец очереди. Интересным моментом данного алгоритма является выбор кванта времени, поскольку переключение между процессами так же занимает определенное время. Значение кванта времени нужно устанавливать чуть выше, чем средний интервал работы процессора без переключения. В этом случае переключение процессов будет происходить редко. Большинство процессов будет выполнять блокировку до истечения кванта времени, что улучшит производительность системы за счет устранения принудительных переключений.

Приоритетное планирование

В циклическом алгоритме планирования есть важное допущение о том, что все процессы равнозначны. Принимая во внимание все факторы, появляется необходимость приоритетного планирования. Каждому процессу присваивается определенный приоритет, и к выполнению принимается процесс с наивысшим приоритетом. Чтобы предотвратить бесконечную работу высокоприоритетных процессов, блокировщик может, например, с каждым тактом часов уменьшать приоритет текущего процесса, пока не произойдет переключение. Приоритеты могут присваиваться статически и динамически. Аналогом статического выделения приоритета могут служить воинские звания. В некоторых ОС существует специальная команда nice, которая позволяет программисту добровольно понизит приоритет процесса. ОС может динамически назначать приоритеты для достижения своих целей. Например, разумно давать высокий приоритет процессам, ограниченным возможностями устройств ввода/вывода. Поскольку большинство времени такие процессы ожидают прерывания, логично предоставить им процессор как только он потребуется, чтобы инициировать новую операцию ввода/вывода и заблокировать данный процесс. Простейшие алгоритмы обслуживания таких процессов состоит в установке приоритета = 1/f, где f - часть использованного в последний раз кванта времени.

Часто бывает удобно сгруппировать процессы в классы по приоритетам и использовать приоритетное планирование среди классов и циклическое планирование внутри класса. Процесс из нижнего класса получит управление только тогда, когда очередь верхнего класса пуста. Поскольку каждое переключение между процессами занимает значительную часть времени, логично выделять процессам, ограниченным возможностями процессора, больший квант времени, что может привести к ухудшению времени отклика. Чтобы исправить этот недостаток, процессам из разных классов выдавались разные кванты времени. Например, процессам первого класса выдвался 1 квант, второго - 2 и т.д. Если процесс использовал все отведенное ему время, на следующий раз ему уменьшали приоритет и увеличивали время работы. Если процесс одно время работает как вычислительный, то есть использует все отведенное ему время, а в другие моменты становится интерактивным, то, для увеличения его приоритета, отслеживается приход специального сигнала.

Лотерейное планирование

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

22. Управление памятью. Однозадачные системы. Многозадачность с фиксированными разделами.

Часть ОС, которая занимается управлением, распределением, очисткой памяти называется менеджером памяти. Менеджеры памяти делятся на 2 типа:

- не перемещают процессы между оперативной памятью и диском;

- перемещают процессы между оперативной памятью и диском:

‡ перемещают процессы целиком (swapping);

‡ перемещают процессы постранично (paging).

Однозадачные системы без подкачки на диск

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

- первая схема использовалась в ранний компьютерах фоннеймоновской архитектуры;

- вторая схема используется до сих пор в простейших контроллерах;

- треться схема использовалась в ранних компьютерах на основе ОС DOS. Используется до сих пор в сложных контроллерах.

Многозадачность с фиксированными разделами

Большинство современныз систем поддерживают псевдопараллельную работу нескольких процессов. Самый легкий способ достижения многозадачности - это разделение памяти на N возможно неравных частей. Когда задание поступает в память, его располагают во входной очереди к наименьшему разделу, способному вместить его. Поскольку размер разделов фиксирован, все пространство раздела, не используемое процессом, пропадает.

Недостаток такой схемы проявляется, когда к большому разделу нет очереди, в то время как к маленькому разделу выстроилась большая очередь задач. Небольшие задания (чаще всего интерактивные и высокоприоритетные) вынуждены ждать в то время как основная часть памяти пустует.