Глава_1 (1085730), страница 11

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

Текст из файла (страница 11)

Если аппаратный таймер выполняет периодические прерывания с частотой 50 Гц, 60 Гц или с любой другой частотой, решения планирования могут прини­маться при каждом прерывании по таймеру или при каждом k-м прерывании. Ал­горитмы планирования можно разделить на две категории согласно их поведению после прерываний. Алгоритмы планирования без переключений, иногда называ­емого также неприоритетным планированием, выбирают процесс и позволяют ему работать вплоть до блокировки (в ожидании ввода-вывода или другого процесса), либо вплоть до того момента, когда процесс сам не отдаст процессор. Процесс не будет прерван, даже если он работает часами. Соответственно, решения планиро­вания не принимаются по прерываниям от таймера. После обработки прерывания таймера управление всегда возвращается приостановленному процессу.

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

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

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

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

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

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

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

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

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

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

Чтобы разработать алгоритм планирования, необходимо иметь представление о том, что должен делать хороший алгоритм. Некоторые задачи зависят от среды (системы пакетной обработки, интерактивные или реального времени), но есть задачи, одина­ковые во всех системах. Список задач представлен в табл. 2.5. Мы рассмотрим их ниже.

Таблица 2.5. Некоторые задачи алгоритмов планирования

Все системы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Руководители крупных компьютерных центров, в которых обрабатываются большие пакетные задания, обычно контролируют три показателя, позволяющие оценить эффективность системы: пропускную способность, оборотное время и ис­пользование процессора. Пропускной способностью называется число выполнен­ных системой задач в час. В любом случае 50 задач в час лучше, чем 40 задач в час. Оборотное время — статистически усредненное время от момента получения за­дачи до ее выполнения. Оно характеризует время, которое среднестатистический пользователь должен ждать получения выходных данных. Основным правилом является «чем меньше, тем лучше».

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

Учет такой характеристики, как использование процессора, связан с тем, что процессор все еще является самой дорогой частью мэйнфреймов, на которых ис­пользуются системы пакетной обработки. Руководители таких центров чувству­ют себя неловко, если процессор не занят все время. Хотя на самом деле этот пока­затель не так уж и важен. Гораздо важнее пропускная способность и оборотное время. Рассматривать коэффициент использования процессора в качестве показателя эффективности примерно так же разумно, как рассматривать рейтинг ма­шин, основанный на количестве оборотов двигателя в минуту.

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

Еще одной задачей является достижение соразмерности. У пользователя все­гда есть собственное (зачастую неправильное) представление о том, сколько време­ни должна занимать та или иная операция. Если запрос, оцениваемый пользовате­лем как сложный, занимает много времени, пользователь готов с этим согласиться, но если запрос оценивался как простой, пользователь сердится. Так, если после щелчка на значке соединения с Интернет-провайдером, у которого аналоговый модем, до момента выхода в Интернет проходит 45 с, пользователь воспринимает это как должное. Но если 45 с будет занимать отключение от сети, пользователь через 30 с начнет безостановочно ругаться, а к 45-й секунде у него пойдет пена изо рта. Такое поведение пользователя основано на его представлении о том, что зво­нок по телефону и установление соединения должно занимать существенно боль­ше времени, чем разрыв соединения. В некоторых случаях (и в этом тоже) плани­ровщик не может ничего сделать, но может улучшить ситуацию во многих других, особенно если задержка вызвана неправильным порядком процессов.

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

В некоторых системах реального времени, особенно связанных с мультимедиа, важна предсказуемость. Небольшая временная задержка не является катастрофич­ной, но неравномерность аудиопроцесса тут же скажется на ухудшении качества звука. Это касается и изображения, но слух более чувствителен к вибрации, чем зрение. Чтобы исключить эту проблему, планирование процессов необходимо сде­лать предсказуемым и регулярным. Мы рассмотрим в этой главе алгоритмы пла­нирования для систем пакетной обработки и интерактивных систем, но рассмот­рение планирования в системах реального времени отложим до главы 7, в которой изучим мультимедийные операционные системы.

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

Перейдем от общих проблем планирования к конкретным алгоритмам. В этом па­раграфе мы рассмотрим алгоритмы, используемые в системах пакетной обработ­ки, а в дальнейших параграфах обратимся к алгоритмам интерактивных систем

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

«Первым пришел — первым обслужен»

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

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

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

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

«Кратчайшая задача — первая»

Рассмотрим еще один алгоритм без переключений для систем пакетной обработ­ки, предполагающий, что временные отрезки работы известны заранее. Например, работники страховой компании могут довольно точно предсказать, сколько вре­мени займет обработка пакета из 1000 исков, поскольку они делают это каждый день. Если в очереди есть несколько одинаково важных задач, планировщик выби-

рает первой самую короткую задачу. Посмотрите на рис. 2.21. У нас есть четыре задачи: А, В, Си D, со временем выполнения 8, 4, 4 и 4мин соответственно. Если мы запустим их в данном порядке, оборотное время задачи А будет 8 мин, В — 12 мин, С — 16 мин и D — 20 мин, и среднее время будет равно 14 мин.

Характеристики

Список файлов книги