Дисциплины диспетчеризации

Стратегия планирования

Планирование и диспетчеризация процессов и задач

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

Диспетчеризация связана с понятием задачи (потока). Если ОС не поддерживает механизма потоков, то понятие задачи можно заменить на понятие процесса.
Известно большое количество правил, в соответствии с которыми формируется очередь (список) готовых к выполнению задач.
Имеются два больших класса дисциплин обслуживания:
- бесприоритетные:
- приоритетные.
При бесприоритетном обслуживании выбор задачи производится в некотором порядке без учета их важности и времени обслуживания.
При реализации приоритетных дисциплин обслуживания отдельным задачам предоставляется преимущественное право на исполнение.
Бесприоритетные дисциплины обслуживания делятся на следующие:
- линейные:
o в порядке очереди;
o случайный выбор процесса;
- циклический:
o циклический алгоритм;
o многоприоритетный циклический алгоритм.
Приоритетные дисциплины обслуживания делятся на следующие:
- с фиксированным приоритетом:
o с относительным приоритетом;
o с абсолютным приоритетом;
o адаптивное обслуживание;
o приоритет зависит от времени ожидания;
- с динамическим приоритетом:
o приоритет зависит от времени ожидания;
o приоритет зависит от времени обслуживания.
Свойства приоритетов:
- приоритет, присвоенный задаче, может являться величиной постоянной;
- приоритет задачи может изменяться в процессе ее решения.
Диспетчеризация с динамическими приоритетами требует дополнительных расходов на вычисление значений приоритетов, поэтому многие ОС реального времени используют методы диспетчеризации на основе статических (постоянных) приоритетов.
Самой простой в реализации является дисциплина FCFS (first come – first served), задачи обслуживаются в порядке очереди, т.е. в порядке их появления. Задачи, приостановленные для ожидания какого-либо ресурса, после перехода в состояние готовности становятся в эту очередь перед задачами, которые еще не выполнялись.
Образуются две очереди:
- новые задачи;
- ранее выполнявшиеся, но попавшие в состояние ожидания.
Дисциплина FCFS реализует стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина не требует внешнего вмешательства в ход вычислений и перераспределения процессорного времени. По классу диспетчеризации (вытесняющие и не вытесняющие) дисциплина FCFS относится к не вытесняющим.

Достоинства дисциплины FCFS:
- простота реализации;
- малые расходы системных ресурсов на формирование очереди задач.
Основной недостаток – при увеличении загрузки вычислительной системы растет среднее время ожидания обслуживания, короткие задачи ожидают столько же времени, как и трудоемкие.
Дисциплина обслуживания SJN (shortest job next) требует, чтобы для каждого задания была известна оценка в потребностях процессорного времени. Пользователи должны были указывать предположительное время выполнения. Диспетчер задач сравнивал указанное время с реальным временем выполнения и, если время выполнения превышало указанное, то помещал это задание в конец очереди.
Дисциплина обслуживания SJN предполагает, что имеется только одна очередь заданий, готовых к выполнению. Если задание было временно заблокировано из-за занятости какого-либо ресурса, то оно помещается в конец очереди готовых к выполнению заданий наравне с вновь поступившими. Задания, которым требуется совсем немного времени для завершения, попадают в конец очереди.
Для устранения этого недостатка была предложена дисциплина SRT (shortest remaining time, следующее задание требует меньше всего времени для своего завершения).
Перечисленные три дисциплины обслуживания могут использоваться для пакетных режимов работы, когда не важно время отклика.
Для интерактивной работы надо обеспечить приемлемое время реакции системы и равенство в обслуживании, если система мультитерминальная. Интерактивные задания должны иметь преимущество перед фоновыми. Эти условия решены в дисциплине RR (round robin – круговая, карусельная).
Дисциплина обслуживания RR предполагает, что каждая задача получает процессорное время порциями (квантами). После окончания выделенного кванта времени задача снимается с исполнения и на выполнение выбирается следующая задача. Снятая задача помещается в конец очереди готовых к выполнению задач.
Величина кванта времени выбирается как компромисс между приемлемым временем реакции системы на запросы пользователей и накладными расходами на частоту смены контекста задач.