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

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

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

8

A B C D

B C D A

4 4 4 4 4 4 8

Рис. 2.21. Пример алгоритма планирования «Кратчайшая задача — первая»: запуск четырех задач в исходном порядке (а); запуск в соответствии с алгоритмом (б)

Запустим задачи в соответствии с алгоритмом, как показано на рис. 2.21, б. Теперь значения оборотного времени составляют 4,8,12 и 20 мин соответственно, а среднее время равно 11 мин. Алгоритм оптимизирует задачу. Рассмотрим четы­ре процесса со временем выполнения а, Ь, с и d. Первая задача выполняется за время а, вторая — за время а + Ъ и т. д. Среднее оборотное время будет равно (4а + ЪЬ + 2с + d)/A. Очевидно, что вклад времени а в среднее больше, чем всех остальных интервалов времени, поэтому первой должна выполняться самая корот­кая задача, а последней — самая длинная, вносящая вклад, равный собственному оборотному времени. Точно так же рассматривается система из любого количества задач.

Следует отметить, что эта схема работает лишь в случае одновременного нали­чия задач. В качестве контрпримера можно рассмотреть пять задач, А, В, С, D и Е, причем первые две доступны стразу же, а три оставшиеся — еще через три минуты. Время выполнения этих задач составляет 2, 4,1,1 и 1 мин соответственно. Вначале можно выбрать только А или В, поскольку остальные недоступны. Если руковод­ствоваться алгоритмом «Кратчайшая задача — первая», задачи будут запущены в следующем порядке: А, В, С, D, Е, и среднее оборотное время составит 4,6 мин. Если же запустить их в порядке В, С, D, Е, А, то среднее оборотное время составит 4,4 мин.

Наименьшее оставшееся время выполнения

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

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

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

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

С одной стороны, распределение процессов необходимо часто пересматривать, чтобы у процессов, хранящихся на диске, тоже был шанс получить доступ к про­цессору. С другой стороны, перемещение процесса с диска в память требует за­трат, поэтому к диску следует обращаться не чаще, чем раз в секунду, а может быть и реже. Если содержимое оперативной памяти будет слишком часто меняться, про­пускная способность диска будет расходоваться впустую, что замедлит файловый ввод-вывод. Для оптимизации эффективности системы планировщик памяти должен ре­шить, сколько и каких процессов может одновременно находиться в памяти. Ко­личество процессов, одновременно находящихся в памяти, называется степенью многозадачности. Если планировщик памяти обладает информацией о том, какие процессы ограничены возможностями процессора, а какие — возможностями устройств ввода-вывода, он может пытаться поддерживать смесь этих процессов в памяти. Можно грубо оценить, что если некая разновидность процессов будет за­нимать примерно 20 % времени процессора, то пяти процессов будет достаточно для поддержания постоянной занятости процессора. Более совершенная модель многозадачности будет рассмотрена в главе 4.

Процессор О

Планировщик процесса

Н

О О О О

Оперативная

память

овая задача

Очередь

О О О О О

Планировщик Планировщик

Доступа памяти

Рис. 2.22. Трехуровневое планирование

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

1. Сколько времени прошло с тех пор, как процесс был выгружен на диск или
   загружен с диска?

2. Сколько времени процесс уже использовал процессор?

3. Каков размер процесса (маленькие процессы не мешают)?

4. Какова важность процесса?

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

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

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

Циклическое планирование

В этом подразделе мы обратимся к некоторым характерным алгоритмам планиро­вания. Одним из наиболее старых, простых, справедливых и часто используемых является алгоритм циклического планирования. Каждому процессу предоставля­ется некоторый интервал времени процессора, так называемый квант времени. Если к концу кванта времени процесс все еще работает, он прерывается, а управ­ление передается другому процессу. Разумеется, если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент. Реа­лизация циклического планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности согласно рисунку 2.23, а. Когда процесс исчерпал свой лимит времени, он отправляется в конец списка (рис. 2.23, б).

Текущий Следующий Текущий

п роцесс процесс процесс

B

F

D

G

A

F

D

G

A

B

а б

Рис. 2.23. Циклическое планирование: список процессов в состоянии готовности (а); список процессов в состоянии готовности после того, как процесс 8 исчерпал свой квант времени (б)

Единственным интересным моментом этого алгоритма является длина кванта. Переключение с одного процесса на другой занимает некоторое время — необхо­димо сохранить и загрузить регистры и карты памяти, обновить таблицы и спис­ки, сохранить и перезагрузить кэш памяти и т. п. Представим, что переключение процессов или переключение контекста, как его иногда называют, занимает 1 мс, включая переключение карт памяти, перезагрузку кэша и т. п. Пусть размер кван­та установлен в 4 мс. В таком случае 20 % процессорного времени уйдет на адми­нистрирование — это слишком много.

Для увеличения эффективности назначим размер кванта, скажем, 100 мс. Теперь пропадает только 1 % времени. Но представьте, что будет в системе с разделением времени, если 10 пользователей одновременно нажмут клавишу возврата каретки. В список будет занесено 10 процессов. Если процессор был свободен, первый про­цесс будет запущен немедленно, второму придется ждать 100 мс и т. д. Последне­му процессу, возможно, придется ждать целую секунду, если все остальные не бло­кируются за время кванта. Большинству пользователей секундная задержка вряд ли понравится.

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

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

Приоритетное планирование

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

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

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

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

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