Система пакетной обработки
Планирование процессов для персональных компьютеров.
Во-первых, большую часть времени активен только один процесс. Пользователь, работающий с документом в текстовом редакторе, вряд ли будет одновременно считать что-либо в фоновом режиме. Когда пользователь дает команду текстовому процессору, планировщику не приходится долго выбирать, какой процесс запустить, поскольку других кандидатов нет.
Во-вторых, компьютеры стали настолько быстрее, что время процессора практически перестало быть дефицитным ресурсом. Большинство программ для персонального компьютера ограничены скоростью, с которой пользователь вводит входные данные (с клавиатуры или с помощью мыши), а не скоростью процессора. Даже процедуры компиляции, основные потребители процессорного времени прошлого, теперь занимают всего несколько секунд. Если одновременно запущены две программы, например текстовый редактор и электронная таблица, и то вряд ли имеет значение, которая из них была первой, поскольку пользователь, вероятно, ждет окончания работы обеих.
Таким образом, на простых персональных компьютерах планирование не играет существенной роли.
Планирование процессов для серверов и мощных сетевых рабочих станций.
Здесь несколько процессов пытаются получить доступ к процессору. Например, когда процессору нужно выбрать между процессом, перерисовывающим экран после того, как пользователь закрыл окно приложения, и процессом, отсылающим почту, впечатление пользователя о реакции компьютера будет существенно зависеть от этого выбора. Ведь если перерисовка экрана во время отправки почты займет 2с, пользователь решит, что система очень медленная, тогда как двухсекундная отсылка почты даже не будет замечена. В этом случае планирование процессов очень важно.
Помимо правильного выбора следующего процесса, планировщик также должен заботиться об эффективном использовании процессора, поскольку переключение между процессами требует затрат.
Во-первых, необходимо переключиться из режима пользователя в режим ядра.
Во-вторых, следует сохранить состояние текущего процесса, включая сохранение регистров в таблице процессов, чтобы их можно было загрузить заново позже. В большинстве систем также необходимо сохранить карту памяти (то есть биты-признаки обращения к страницам памяти).
В-третьих, нужно выбрать следующий процесс, запустив алгоритм планирования.
В-четвертых, необходимо перезапустить блок управления памятью с картой памяти нового процесса.
В-пятых, нужно запустить новый процесс.
Поведение процесса
Практически все процессы чередуют периоды вычислений с операциями (дисковыми) ввода-вывода. Обычно процессор некоторое время работает без остановки, затем происходит системный вызов на чтение из файла или запись в файл. После выполнения системного вызова процессор опять считает, пока ему не понадобятся новые данные или не потребуется записать полученные данные.
Некоторые процессы (рис. 2.20а) большую часть времени заняты вычислениями – такие процессы называются ограниченными возможностями процессора. Процессы, ограниченные возможностями процессора, обычно характеризуются длительными периодами использования процессора и нечастыми ожиданиями ввода-вывода.
Другие (рис. 2.20б) большую часть времени ожидают ввода-вывода – такие процессы называются ограниченными возможностями устройств ввода-вывода. Процессы, ограниченные возможностями устройств ввода-вывода, характеризуются короткими периодами использования процессора и частыми ожиданиями ввода-вывода.
Ситуации, в которых необходимо планирование.
Во-первых, когда создается новый процесс, необходимо решить, какой процесс запустить: родительский или дочерний. Поскольку оба процесса находятся в состоянии готовности, эта ситуация не выходит за рамки обычного и планировщик может запустить любой из двух процессов.
Во-вторых, планирование необходимо, когда процесс завершает работу. Этот процесс уже не существует, следовательно, необходимо из набора готовых процессов выбрать и запустить следующий. Если процессов, находящихся в состоянии готовности, нет, обычно запускается холостой процесс, поставляемый системой.
В-третьих, когда процесс блокируется на операции ввода-вывода, семафоре, или по какой-либо другой причине, необходимо выбрать и запустить другой процесс. Иногда причина блокировки может повлиять на выбор. Например, если А — важный процесс и он ожидает выхода процесса В из критической области, можно запустить следующим процесс В, чтобы он вышел из критической области и позволил процессу А продолжать работу. Сложность, однако, в том, что планировщик обычно не обладает информацией, необходимой для принятия правильного решения.
В-четвертых, необходимость планирования может возникнуть при появлении прерывания ввода-вывода. Если прерывание пришло от устройства ввода-вывода, закончившего работу, можно запустить процесс, который был блокирован в ожидании этого события. Планировщик должен выбрать, какой процесс запустить: новый, тот, который был остановлен прерыванием, или какой-то другой.
Вопрос №2. «Категории алгоритмов планирования. Задачи алгоритмов планирования».
Алгоритмы планирования можно разделить на две категории согласно их поведению после прерываний.
Алгоритмы планирования без переключений, иногда называемого также неприоритетным планированием, выбирают процесс и позволяют ему работать вплоть до блокировки (в ожидании ввода-вывода или другого процесса), либо вплоть до того момента, когда процесс сам не отдаст процессор. Процесс не будет прерван, даже если он работает часами. Соответственно, решения планирования не принимаются по прерываниям от таймера. После обработки прерывания таймера управление всегда возвращается приостановленному процессу.
Алгоритмы планирования с переключениями, называемого также приоритетным планированием, выбирают процесс и позволяют ему работать некоторое максимально возможное фиксированное время. Если к концу заданного интервала времени процесс все еще работает, он приостанавливается и управление переходит к другому процессу (если в очереди есть процесс). Приоритетное планирование требует прерываний по таймеру, происходящих в конце отведенного периода времени, чтобы передать управление планировщику.
Категории алгоритмов планирования
В различных средах требуются различные алгоритмы планирования. Это связано с тем, что различные операционные системы и различные приложения ориентированы на разные задачи. Другими словами, то, для чего следует оптимизировать планировщик, различно в разных системах.
Можно выделить три среды:
1. Системы пакетной обработки данных.
2. Интерактивные системы.
3. Системы реального времени.
В системах пакетной обработки нет пользователей, сидящих за терминалами и ожидающих ответа. В таких системах приемлемы алгоритмы без переключений или с переключениями, но с большим временем, отводимым каждому процессу. Такой метод уменьшает количество переключений между процессами и улучшает эффективность.
В интерактивных системах необходимы алгоритмы планирования с переключениями, чтобы предотвратить захват процессора одним процессом. Даже если ни один процесс не захватывает процессор на неопределенно долгий срок намеренно, из-за ошибки в программе один процесс может заблокировать остальные. Для исключения подобных ситуаций используется планирование с переключениями.
В системах с ограничениями реального времени приоритетность, как это ни странно, не всегда обязательна, поскольку процессы знают, что их время ограничено, и быстро выполняют работу, а затем блокируются. Отличие от интерактивных систем в том, что в системах реального времени работают только программы, предназначенные для содействия конкретным приложениям. Интерактивные системы являются универсальными системами. В них могут работать произвольные программы, не сотрудничающие друг с другом и даже враждебные по отношению друг к другу.
Задачи алгоритмов планирования.
Чтобы разработать алгоритм планирования, необходимо иметь представление о том, что должен делать хороший алгоритм.
Некоторые задачи зависят от среды (системы пакетной обработки, интерактивные или реального времени), но есть задачи, одинаковые во всех системах.
| Все системы | Справедливость — предоставление каждому процессу справедливой доли процессорного времени |
| Принудительное применение политики — контроль за выполнением принятой политики | |
| Баланс — поддержка занятости всех частей системы | |
| Системы пакетной обработки данных | Пропускная способность — максимальное количество задач в час |
| Оборотное время — минимизация времени, затрачиваемого на ожидание обслуживания и обработку задачи | |
| Использование процессора — поддержка постоянной занятости процессора | |
| Интерактивные системы | Время отклика — быстрая реакция на запросы |
| Соразмерность — выполнение пожеланий пользователя | |
| Системы реального времени | Окончание работы к сроку — предотвращение потери данных |
| Предсказуемость — предотвращение деградации качества в мультимедийных системах |
Задачи для всех систем.
Справедливость. При всех обстоятельствах необходимо справедливое распределение процессорного времени. Сопоставимые процессы должны получать сопоставимое обслуживание. Выделить одному процессу намного больше времени процессора, чем другому, эквивалентному, несправедливо. Разумеется, с различными категориями процессов можно обращаться весьма по-разному. Возьмите, например, задачи обеспечения безопасности и начисления заработной платы в компьютерном центре атомной электростанции.
Принудительное применение политики. С принципом справедливости в какой-то мере связано принудительное применение системной политики. Если локальная политика заключается в предоставлении процессора процессам контроля безопасности по первому требованию, планировщик должен удостовериться в принудительном применении этой политики, даже когда это приводит к начислению заработной платы на 30с позже.
Баланс. Еще одной глобальной задачей является контроль занятости всех частей системы. Если устройства ввода-вывода и процессор все время работают, в единицу времени окажется выполнено гораздо больше полезной деятельности, чем если отдельные компоненты будут простаивать. Например, в системах пакетной обработки планировщик выбирает, какие задачи загрузить в память для работы. Гораздо лучше иметь в памяти одновременно несколько процессов, ограниченных возможностями процессора, и несколько процессов, ограниченных возможностями устройств ввода-вывода, чем сначала загрузить и запустить несколько процессов, ограниченных возможностями процессора, и только потом несколько процессов, ограниченных возможностями устройств ввода-вывода. В последнем случае во время работы процессов, ограниченных возможностями процессора, будет простаивать диск, а во время работы процессов, ограниченных возможностями устройств ввода-вывода, будет простаивать процессор. Правильнее будет заставить работать всю систему, аккуратно перемешав процессы.
Система пакетной обработки.
Руководители крупных компьютерных центров, в которых обрабатываются большие пакетные задания, обычно контролируют три показателя, позволяющие оценить эффективность системы:
· пропускную способность,
· оборотное время
· использование процессора.
Пропускной способностью называется число выполненных системой задач в час. В любом случае 50 задач в час лучше, чем 40 задач в час.
Оборотное время — статистически усредненное время от момента получения задачи до ее выполнения. Оно характеризует время, которое среднестатистический пользователь должен ждать получения выходных данных. Основным правилом является «чем меньше, тем лучше».
Алгоритм планирования, максимизирующий пропускную способность, не обязательно минимизирует оборотное время.
При наличии смеси из длинных и коротких задач алгоритм, запускающий только короткие задачи, может добиться высокой пропускной способности (много коротких задач в час), но за счет ужасного оборотного времени для длинных задач. Если короткие задачи поступают с постоянной скоростью, до длинных задач дело может не дойти никогда, в результате чего оборотное время будет бесконечным при высокой пропускной способности.
Учет такой характеристики, как использование процессора, связан с тем, что процессор все еще является самой дорогой частью мэйнфреймов, на которых используются системы пакетной обработки. Руководители таких центров чувствуют себя неловко, если процессор не занят все время. Хотя на самом деле этот показатель не так уж и важен. Гораздо важнее пропускная способность и оборотное время. Рассматривать коэффициент использования процессора в качестве показателя эффективности примерно так же разумно, как рассматривать рейтинг машин, основанный на количестве оборотов двигателя в минуту.
Интерактивные системы.
Для интерактивных систем, особенно систем и серверов, работающих в режиме разделения времени, важны другие задачи.
Самой важной является минимизация времени отклика, то есть времени между введением команды и получением результата. На персональном компьютере с фоновым процессом (например, отправкой и получением почты) запрос пользователя на запуск программы или открытие файла должен иметь приоритет перед фоновым процессом. Первоочередная обработка всех интерактивных запросов рассматривается как хорошее обслуживание.
Еще одной задачей является достижение соразмерности. У пользователя всегда есть собственное (зачастую неправильное) представление о том, сколько времени должна занимать та или иная операция. Если запрос, оцениваемый пользователем как сложный, занимает много времени, пользователь готов с этим согласиться, но если запрос оценивался как простой, пользователь сердится. Так, если после щелчка на значке соединения с Интернет-провайдером, у которого аналоговый модем, до момента выхода в Интернет проходит 45с, пользователь воспринимает это как должное. Но если 45с будет занимать отключение от сети, пользователь через 30с начнет безостановочно ругаться, а к 45-й секунде у него пойдет пена изо рта. Такое поведение пользователя основано на его представлении о том, что звонок по телефону и установление соединения должно занимать существенно больше времени, чем разрыв соединения. В некоторых случаях (и в этом тоже) планировщик не может ничего сделать, но может улучшить ситуацию во многих других, особенно если задержка вызвана неправильным порядком процессов.