 |
Планирование заданий. Критерии планирования и требования к алгоритмам. . Планирование в системах пакетной обработки
|
|
|
|
ПЛАНИРОВАНИЕ ЗАДАНИЙ
Планирование – обеспечение поочередного доступа процессов к одному процессору. Планировщик – отвечающая за это часть операционной системы. Алгоритм планирования – используемый алгоритм для планирования.
Ситуации, когда необходимо планирование:
1) когда создается процесс;
2) когда процесс завершает работу;
3) когда процесс блокируется на операции ввода-вывода, семафоре, и т. д.;
4) при прерывании ввода-вывода.
Критерии планирования и требования к алгоритмам.
Для каждого уровня планирования процессов можно предложить много различных алгоритмов. Выбор конкретного алгоритма определяется классом задач, решаемых вычислительной системой, и целями, которых нужно достичь, используя планирование.
К числу таких целей можно отнести следующие:
- справедливость: гарантировать каждому заданию или процессу определенную часть времени использования процессора в компьютерной системе, стараясь не допустить возникновения ситуации, когда процесс одного пользователя постоянно занимает процессор, в то время как процесс другого пользователя фактически не начинал выполняться;
- эффективность: постараться занять процессор на все 100% рабочего времени, не позволяя ему простаивать в ожидании процессов, готовых к исполнению. В реальных вычислительных системах загрузка процессора колеблется от 40 до 90%;
- сокращение полного времени выполнения: обеспечить минимальное время между стартом процесса или постановкой задания в очередь для загрузки и его завершением;
- сокращение времени ожидания: сократить время, которое проводят процессы в состоянии готовность и задания в очереди для загрузки;
|
|
|
- сокращение времени отклика: минимизировать время, которое требуется процессу в интерактивных системах для ответа на запрос пользователя.
Независимо от поставленных целей планирования желательно также, чтобы алгоритмы обладали следующими свойствами:
- были предсказуемыми. Одно и то же задание должно выполняться приблизительно за одно и то же время. Применение алгоритма планирования не должно приводить, к примеру, к извлечению квадратного корня из 4 за сотые доли секунды при одном запуске и за несколько суток – при втором запуске;
- были связаны с минимальными накладными расходами. Если на каждые 100 миллисекунд, выделенные процессу для использования процессора, будет приходиться 200 миллисекунд на определение того, какой именно процесс получит процессор в свое распоряжение, и на переключение контекста, то такой алгоритм, очевидно, применять не стоит;
- равномерно загружали ресурсы вычислительной системы, отдавая предпочтение тем процессам, которые будут занимать малоиспользуемые ресурсы;
- обладали масштабируемостью, т. е. не сразу теряли работоспособность при увеличении нагрузки. Например, рост количества процессов в системе в два раза не должен приводить к увеличению полного времени выполнения процессов на порядок.
Существует два основных вида алгоритмов планирования:
1) Алгоритм планирования без переключений (неприоритетный) – не требует прерывание по аппаратному таймеру, процесс останавливается только когда блокируется или завершает работу;
2) Алгоритм планирования с переключениями (приоритетный) – требует прерывание по аппаратному таймеру, процесс работает только отведенный период времени, после этого он приостанавливается по таймеру, чтобы передать управление планировщику.
Вид алгоритма планирования зависит от задач, для которых будет использоваться операционная система.
|
|
|
Существуют три основные системы:
1) Системы пакетной обработки – могут использовать неприоритетный и приоритетный алгоритм (например, для расчетных программ);
2) Интерактивные системы – могут использовать только приоритетный алгоритм, нельзя допустить, чтобы один процесс занял надолго процессор (например, сервер общего доступа или персональный компьютер);
3) Системы реального времени – могут использовать неприоритетный и приоритетный алгоритм (например, система управления автомобилем).
Планирование в системах пакетной обработки
1. «Первый пришел - первым обслужен» (FIFO – First In Fist Out)
Процессы ставятся в очередь по мере поступления.
Преимущества:
- простота;
- справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди).
Недостаток: процесс, ограниченный возможностями процессора может затормозить более быстрые процессы, ограниченные устройствами ввода-вывода.
2. «Кратчайшая задача – первая».
Преимущества:
- уменьшение оборотного времени;
- справедливость (как в очереди покупателей, кто без сдачи проходит вперед).
Недостаток: длинный процесс, занявший процессор, не пустит более новые краткие процессы, которые пришли позже.
3. Наименьшее оставшееся время выполнение.
Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.
|
|
|
