18.Планирование в системах пакетной обработки данных. Планирование в интерактивных системах. Планирование в системах реального времени.

1. Введение в планирование.

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

• создание процесса;

• завершение процесса;

• блокировка процесса на различных операциях;

• прерывание ввода/вывода.

2. Категории алгоритмов планирования.

Всё многообразие алгоритмов планирования может быть разделено на невытесняющие (назовем их неприоритетными) и вытесняющие (назовем их приоритетными).

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

Использование того или иного алгоритма планирования зависят от типа решаемых ОС задач. В этом смысле ОС можно разделить на:

• системы пакетной обработки;

• интерактивные системы;

• системы реального времени.

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

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

Системы реального времени могут использовать как неприоритетный, так и приоритетный алгоритмы.

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

К задачам алгоритмов планирования относятся:

• для всех систем

• справедливость (каждому процессу справедливую долю процессорного времени);

• контроль за выполнением принятой политики;

• баланс (поддержка занятости всех частей системы так, чтобы, например, были заняты процессор и устройства ввода/вывода);

• для систем пакетной обработки

• пропускная способность (количество задач в час);

• оборотное время (минимизация времени на ожидание обслуживания и обработку задач);

• использование процессора (процессор должен быть всегда занят);

• для интерактивных систем

• время отклика (быстрая реакция на запросы);

• соразмерность (выполнение ожиданий пользователя);

• для систем реального времени

• окончание работы к сроку (предотвращение потери данных);

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

3. Планирование в системах пакетной обработки данных

Планирование в системах пакетной обработки данных может происходить по следующим алгоритмам:

1. «Первый пришел – первым обслужен»

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

2. «Кратчайшая задача – первая» (рис. 3.9)

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

Рис. 3.9. Выполнение алгоритма «Кратчайшая задача – первая»

3. Наименьшее оставшееся время выполнения

Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса

4. Трехуровневое планирование (рис. 3.10)

Рис. 3.10. Трехуровневое планирование

Планировщик доступа выбирает задачи оптимальным образом (например: процессы, ограниченные процессором и вводом/выводом).

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

4. Планирование в интерактивных системах

Планирование в интерактивных системах может происходить по следующим алгоритмам:

1) Циклическое планирование

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

Рис. 3.11. Пример циклического планирования

Преимущества: простота, справедливость. Недостатки: при частых переключениях уменьшается производительность; при редких переключениях увеличивается время ответа на запрос.

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

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом.

5. Планирование в системах реального времени

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

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

Для планирования системы реального времени необходимо выполнение следующего условия:

где m – число периодических событий; T_i – время, которое уходит на обработку события; P_i – период поступления события.

Таким образом, перегруженная система реального времени является не планируемой.