Классификация потоков по распределению периодов ввода-вывода

o Процессы, ограниченные возможностями процессора (процессы, большую часть времени занятые вычислениями)

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

Планирование необходимо:

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

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

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

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

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

· По поведению в случае появления прерывания:

o Без переключений (процесс работает до завершения или блокировки)

o С переключениями (по таймеру)

· По обслуживаемым задачам:

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

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

o Системы реального времени (в системах с ограничениями реального времени приоритетность, как это ни стран­но, не всегда обязательна, поскольку процессы знают, что их время ограничено, и быстро выполняют работу, а затем блокируются. Отличие от интерактивных систем в том, что в системах реального времени работают только программы, предназна­ченные для содействия конкретным приложениям. Интерактивные системы явля­ются универсальными системами. В них могут работать произвольные программы, не сотрудничающие друг с другом и даже враждебные по отношению друг к другу. то есть подразумевается, что система реального времени ориентирована не на быстрый отклик на запрос пользователя, или какого либо произвольного приложения, а на получения вполне конкретных результатов к определённому моменту времени.)

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

- Все системы

Справедливость — предоставление каждому процессу справедливой доли процессорного времени

Принудительное применение политики — контроль за выполнением принятой политики

Баланс — поддержка занятости всех частей системы

- Системы пакетной обработки данных

Пропускная способность — максимальное количество задач в час

Оборотное время — минимизация времени, затрачиваемого на ожидание обслуживания и обработку задачи

Использование процессора — поддержка постоянной занятости процессора

- Интерактивные системы

Время отклика — быстрая реакция на запросы

Соразмерность — выполнение пожеланий пользователя

- Системы реального времени

Окончание работы к сроку — предотвращение потери данных

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

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

Первым пришел - первым обслужен (очередь) FIFO. Процессы следуют по мере поступления.

Кратчайшая задача первая. Первыми идут процессы, требующие меньшее время.

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

Трехуровневое планирова ние. По мере поступления в систему новые задачи сна­чала помещаются в очередь, хранящуюся на диске. Впускной планировщик доступа выбирает задание и передает его системе. Остальные задания остаются в очереди. Как только задание попало в систему, для него будет создан соответствующий процесс, и он может тут же вступить в борьбу за доступ к процессору. Второй уровень планирования определяет, какие процессы можно хранить в памяти, а какие — на диске. Этим занимается планировщик памяти. Третий уровень планирования отвечает за доступ процессов, находящихся в состоянии готовности, к процессору. Когда идет разговор о «планировщике», обычно имеется в виду именно планировщик процессора. Этим планировщиком используется любой подходящий к ситуации алгоритм, как с прерыванием, так и без

трехуровневое планирование

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

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

Приоритетное планирование. Каждому процессу присваивается статический или динамический приоритет. Обслуживаются процессы с более высокими приоритетами.

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

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

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

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

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

Планирование в системах реального времени – планировщик опирается на расписание.

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

Date: 2016-06-06; view: 596; Нарушение авторских прав