50. Планирование

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

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

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

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

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

большую часть времени работает один процесс.

время процессора не представляет собой дефицитный ресурс.

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

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

С увеличением скорости процессоров про­цессы все больше зависят от устройств ввода-вывода. Поэтому пла­нирование процессов с ограниченными возможностями ввода-вывода имеет большее значение.

Самым важным в планировании является выбор момента при­нятия решений. Существует ряд ситуаций, в которых необходимо пла­нирование:

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

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

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

— при прерывании ввода-вывода.

Если аппаратный таймер выполняет периодические прерыва­ния, то решения планировщика могут приниматься при каждом пре­рывании.

Существует два вида алгоритмов планирования:

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

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

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

В зависимости от операционной системы можно выделить раз­личные алгоритмы планирования. Можно выделить три вида среды:

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

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

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

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

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

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

Можно выделить ряд задач, возникающих при планировании в различных средах:

1. Характерные для всех систем:

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

Задача контроля за выполнением принятой политики.

Задача поддержания загруженности всех частей системы.

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

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

Задача минимизации времени, затрачиваемого на ожидание обслу­живания и обработку задания (оборотного времени).

Задача поддержания загруженности процессора.

3. Характерные для интерактивных систем:

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

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

4. Характерные для систем реального времени:

Задача окончания работы к сроку, т.е. предотвращение потери данных.

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

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

Алгоритмы, используемые в системах пакетной обработки:1) «первым пришел — первым обслужен»Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. Чаще всего формируется единая очередь ждущих процессов. Как только появляется первая задача, она немедленно запускается и работает столько, сколько необходимо. Остальные задачи ставятся в конец очереди. Когда текущий процесс блокируется, запускается следующий в очереди, а когда блокировка снимается, процесс попадает в конец очереди. В этом алгоритме все процессы в состоянии готовности контролируются одним связным списком. Чтобы выбрать процесс для запуска, нужно всего лишь взять первый элемент списка и удалить его. Появление нового процесса приводит к помещению его в конец списка.2) «Кратчайшая задача — первая» алгоритм предполагающий, что временные отрезки работы известны заранее. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу. 3)Наименьшее оставшееся время выполнения. Планировщик каждый раз выбирает процесс с наименьшим оставшимся временем выполнения. В этом случае также необходимо заранее знать время выполнения задач. Когда поступает новая задача, ее полное время выполнения сравнивается с оставшимся временем выполнения текущей задачи. Если время выполнения новой задачи меньше, текущий процесс приостанавливается и управление передается новой задаче. Эта схема позволяет быстро обслуживать короткие запросы.4) Трехуровневое планирование. По мере поступления в систему новые задачи сначала помещаются в очередь, хранящуюся на диске. Впускной планировщик выбирает задание и передает его системе. Остальные задания остаются в очереди. Как только задание попало в систему, для него будет создан соответствующий процесс, и он может тут же вступить в борьбу за доступ к процессору. Возможна ситуация, когда процессов слишком много и они все в памяти не помещаются, тогда некоторые из них будут выгружены на диск. Второй уровень планирования определяет, какие процессы можно хранить в памяти, а какие на диске. Этим занимается планировщик памяти. Для оптимизации эффективности системы планировщик памяти должен решить, сколько и каких процессов может одновременно находиться в памяти. Количество процессов, одновременно находящихся в памяти, называется степенью многозадачности. Третий уровень планирования отвечает за доступ процессов, находящихся в состоянии готовности, к процессору.