Geum.ru

The design of the unix operating system by Maurice J

Вид материалаРеферат
8.1 Планирование выполнения процессов
Подобный материал:
1   ...   28   29   30   31   32   33   34   35   ...   55

мер, команда time позволяет узнать, сколько времени занимает вы-

полнение другой команды, команда date выводит текущую дату и вре-

мя суток. С помощью различных системных функций процессы могут

устанавливать или получать временные характеристики выполнения в

режиме ядра, а также степень загруженности центрального процессо-

ра. Время в системе поддерживается с помощью аппаратных часов,

которые посылают ЦП прерывания с фиксированной, аппаратно-зависи-

мой частотой, обычно 50-100 раз в секунду. Каждое поступление

прерывания по таймеру (часам) именуется таймерным тиком. В насто-

ящей главе рассматриваются особенности реализации процессов во

времени, включая планирование процессов в системе UNIX, описание

связанных со временем системных функций, а также функций, выпол-

няемых программой обработки прерываний по таймеру.


8.1 ПЛАНИРОВАНИЕ ВЫПОЛНЕНИЯ ПРОЦЕССОВ


Планировщик процессов в системе UNIX принадлежит к общему

классу планировщиков, работающих по принципу "карусели с многоу-

ровневой обратной связью". В соответствии с этим принципом ядро

предоставляет процессу ресурсы ЦП на квант времени, по истечении

которого выгружает этот процесс и возвращает его в одну из нес-

кольких очередей, регулируемых приоритетами. Прежде чем процесс

завершится, ему может потребоваться множество раз пройти через

цикл с обратной связью. Когда ядро выполняет переключение кон-

текста и восстанавливает контекст процесса, процесс возобновляет

выполнение с точки приостанова.


-------------------------------------------------------------┐

│ алгоритм schedule_process │

│ входная информация: отсутствует │

│ выходная информация: отсутствует │

│ { │

│ выполнять пока (для запуска не будет выбран один из про-│

│ цессов) │

│ { │

│ для (каждого процесса в очереди готовых к выполнению)│

│ выбрать процесс с наивысшим приоритетом из загру-│

│ женных в память; │

│ если (ни один из процессов не может быть избран для │

│ выполнения) │

│ приостановить машину; │

│ /* машина выходит из состояния простоя по преры- │

│ /* ванию │

│ */ │

│ } │

│ удалить выбранный процесс из очереди готовых к выполне- │

│ нию; │

│ переключиться на контекст выбранного процесса, возобно- │

│ вить его выполнение; │

│ } │

L-------------------------------------------------------------


Рисунок 8.1. Алгоритм планирования выполнения процессов


8.1.1 Алгоритм


Сразу после переключения контекста ядро запускает алгоритм

планирования выполнения процессов (Рисунок 8.1), выбирая на вы-

полнение процесс с наивысшим приоритетом среди процессов, находя-

щихся в состояниях "резервирования" и "готовности к выполнению,

будучи загруженным в память". Рассматривать процессы, не загру-

женные в память, не имеет смысла, поскольку не будучи загружен,

процесс не может выполняться. Если наивысший приоритет имеют сра-

зу несколько процессов, ядро, используя принцип кольцевого списка

(карусели), выбирает среди них тот процесс, который находится в

состоянии "готовности к выполнению" дольше остальных. Если ни

один из процессов не может быть выбран для выполнения, ЦП проста-

ивает до момента получения следующего прерывания, которое прои-

зойдет не позже чем через один таймерный тик; после обработки

этого прерывания ядро снова запустит алгоритм планирования.


8.1.2 Параметры диспетчеризации


В каждой записи таблицы процессов есть поле приоритета, ис-

пользуемое планировщиком процессов. Приоритет процесса в режиме

задачи зависит от того, как этот процесс перед этим использовал

ресурсы ЦП. Можно выделить два класса приоритетов процесса (Рису-

нок 8.2): приоритеты выполнения в режиме ядра и приоритеты выпол-

нения в режиме задачи. Каждый класс включает в себя ряд значений,

с каждым значением логически ассоциирована некоторая очередь про-

цессов. Приоритеты выполнения в режиме задачи оцениваются для

процессов, выгруженных по возвращении из режима ядра в режим за-

дачи, приоритеты выполнения в режиме ядра имеют смысл только в

контексте алгоритма sleep. Приоритеты выполнения в режиме задачи

имеют верхнее пороговое значение, приоритеты выполнения в режиме

ядра имеют нижнее пороговое значение. Среди приоритетов выполне-

ния в режиме ядра далее можно выделить высокие и низкие приорите-

ты: процессы с низким приоритетом возобновляются по получении

сигнала, а процессы с высоким приоритетом продолжают оставаться в

состоянии приостанова (см. раздел 7.2.1).

Пороговое значение между приоритетами выполнения в режимах

ядра и задачи на Рисунке 8.2 отмечено двойной линией, проходящей

между приоритетом ожидания завершения потомка (в режиме ядра) и

нулевым приоритетом выполнения в режиме задачи. Приоритеты про-

цесса подкачки, ожидания ввода-вывода, связанного с диском, ожи-

дания буфера и индекса являются высокими, не допускающими преры-

вания системными приоритетами, с каждым из которых связана

очередь из 1, 3, 2 и 1 процесса, соответственно, в то время как

приоритеты ожидания ввода с терминала, вывода на терминал и за-

вершения потомка являются низкими, допускающими прерывания сис-

темными приоритетами, с каждым из которых связана очередь из 4, 0

и 2 процессов, соответственно. На рисунке представлены также

уровни приоритетов выполнения в режиме задачи (*).

Ядро вычисляет приоритет процесса в следующих случаях:

* Непосредственно перед переходом процесса в состояние приоста-

нова ядро назначает ему приоритет исходя из причины приоста-

нова. Приоритет не зависит от динамических характеристик про-

цесса (продолжительности ввода-вывода или времени счета),

напротив, это постоянная величина, жестко устанавливаемая в

момент приостанова и зависящая только от причины перехода

процесса в данное состояние. Процессы, приостановленные алго-

ритмами низкого уровня, имеют тенденцию порождать тем больше

узких мест в системе, чем дольше они находятся в этом состоя-

нии; поэтому им назначается более высокий приоритет по срав-

нению с остальными процессами. Например, процесс,

приостановленный в ожидании завершения ввода-вывода, связан-

ного с диском, имеет более высокий приоритет по сравнению с

процессом, ожидающим освобождения буфера, по нескольким при-

чинам. Прежде всего, у первого процесса уже есть буфер, поэ-

тому не исключена возможность, что когда он возобновится, он

успеет освободить и буфер, и другие ресурсы. Чем больше ре-

сурсов свободно, тем меньше шансов для возникновения взаимной

блокировки процессов. Системе не придется часто переключать


---------------------------------------

(*) Наивысшим значением приоритета в системе является нулевое

значение. Таким образом, нулевой приоритет выполнения в режи-

ме задачи выше приоритета, имеющего значение, равное 1, и

т.д.


Приоритеты выполнения Уровни приоритетов Процессы

в режиме ядра

│ -----------------------┐

│ │ Процесс │ ---┐

│ │ подкачки │-+ │

│ Не допускающие +----------------------+ L---

│ │Ожидание ввода-вывода,│ ---┐ ---┐ ---┐

│ прерывания │ связанного с диском │-+ +-+ +-+ │

│ +----------------------+ L--- L--- L---

│ │ Ожидание │ ---┐ ---┐

│ │ буфера │-+ +-+ │

│ +----------------------+ L--- L---

│ │ Ожидание │ ---┐

│ │ индекса │-+ │

│ +----------------------+ L---

│ +----------------------+

│ │ Ожидание ввода с тер-│ ---┐ ---┐ ---┐ ---┐

│ │ минала │-+ +-+ +-+ +-+ │

│ Допускающие +----------------------+ L--- L--- L--- L---

│ │ Ожидание вывода на │

│ прерывания │ терминал │

│ +----------------------+

│ │ Ожидание завершения │ ---┐ ---┐

│ │ потомка │-+ +-+ │

v +----------------------+ L--- L---

Пороговый приоритет +----------------------+

│ Уровень задачи 0 │

│ +----------------------+ ---┐ ---┐ ---┐ ---┐

│ │ Уровень задачи 1 │-+ +-+ +-+ +-+ │

│ +----------------------+ L--- L--- L--- L---

│ │ │

│ │ │

│ │ │

│ +----------------------+ ---┐

Приоритеты выполнения │ Уровень задачи n │-+ │

в режиме задачи L----------------------- L---


Рисунок 8.2. Диапазон приоритетов процесса


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

увеличится производительность системы. Во-вторых, буфер, ос-

вобождения которого ожидает процесс, может быть занят процес-

сом, ожидающим в свою очередь завершения ввода-вывода. По за-

вершении ввода-вывода будут возобновлены оба процесса, пос-

кольку они были приостановлены по одному и тому же

адресу. Если первым запустить на выполнение процесс, ожидаю-

щий освобождения буфера, он в любом случае снова приостано-

вится до тех пор, пока буфер не будет освобожден; следова-

тельно, его приоритет должен быть ниже.

* По возвращении процесса из режима ядра в режим задачи ядро

вновь вычисляет приоритет процесса. Процесс мог до этого на-

ходиться в состоянии приостанова, изменив свой приоритет на

приоритет выполнения в режиме ядра, поэтому при переходе про-

цесса из режима ядра в режим задачи ему должен быть возвращен

приоритет выполнения в режиме задачи. Кроме того, ядро "штра-

фует" выполняющийся процесс в пользу остальных процессов, от-

бирая используемые им ценные системные ресурсы.

* Приоритеты всех процессов в режиме задачи с интервалом в 1

секунду (в версии V) пересчитывает программа обработки преры-

ваний по таймеру, побуждая тем самым ядро выполнять алгоритм

планирования, чтобы не допустить монопольного использования

ресурсов ЦП одним процессом.

В течение кванта времени таймер может послать процессу нес-

колько прерываний; при каждом прерывании программа обработки пре-

рываний по таймеру увеличивает значение, хранящееся в поле табли-

цы процессов, которое описывает продолжительность использования

ресурсов центрального процессора (ИЦП). В версии V каждую секунду

программа обработки прерываний переустанавливает значение этого

поля, используя функцию полураспада (decay):

decay(ИЦП) = ИЦП/2;

После этого программа пересчитывает приоритет каждого процесса,

находящегося в состоянии "зарезервирован, но готов к выполнению",

по формуле

приоритет = (ИЦП/2) + (базовый уровень приоритета задачи)

где под "базовым уровнем приоритета задачи" понимается пороговое

значение, расположенное между приоритетами выполнения в режимах

ядра и задачи. Высокому приоритету планирования соответствует ко-

личественно низкое значение. Анализ функций пересчета продолжи-

тельности использования ресурсов ЦП и приоритета процесса показы-

вает: чем ниже скорость полураспада значения ИЦП, тем медленнее

приоритет процесса достигает значение базового уровня; поэтому

процессы в состоянии "готовности к выполнению" имеют тенденцию

занимать большое число уровней приоритетов.

Результатом ежесекундного пересчета приоритетов является пе-

ремещение процессов, находящихся в режиме задачи, от одной

очереди к другой, как показано на Рисунке 8.3. По сравнению с Ри-

сунком 8.2 один процесс перешел из очереди, соответствующей уров-

ню 1, в очередь, соответствующую нулевому уровню. В реальной сис-

теме все процессы, имеющие приоритеты выполнения в режиме задачи,

поменяли бы свое местоположение в очередях. При этом следует ука-

зать на невозможность изменения приоритета процесса в режиме яд-

ра, а также на невозможность пересечения пороговой черты процес-

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

обратятся к операционной системе и не перейдут в состояние приос-

танова.

Ядро стремится производить пересчет приоритетов всех активных

процессов ежесекундно, однако интервал между моментами пересчета

может слегка варьироваться. Если прерывание по таймеру поступило

тогда, когда ядро исполняло критический отрезок программы (други-

ми словами, в то время, когда приоритет работы ЦП был повышен,

но, очевидно, не настолько, чтобы воспрепятствовать прерыванию

данного типа), ядро не пересчитывает приоритеты, иначе ему приш-

лось бы надолго задержаться на критическом отрезке. Вместо этого

ядро запоминает то, что ему следует произвести пересчет приорите-

тов, и делает это при первом же прерывании по таймеру, поступаю-

щем после снижения приоритета работы ЦП. Периодический пересчет

приоритета процессов гарантирует проведение стратегии планирова-

ния, основанной на использовании кольцевого списка процессов, вы-

полняющихся в режиме задачи. При этом конечно же ядро откликается

на интерактивные запросы таких программ, как текстовые редакторы

или программы форматного ввода: процессы, их реализующие, имеют

высокий коэффициент простоя (отношение времени простоя к продол-

жительности использования ЦП) и поэтому естественно было бы повы-

шать их приоритет, когда они готовы для выполнения (см. [Thompson

78], стр.1937). В других механизмах планирования квант времени,

выделяемый процессу на работу с ресурсами ЦП, динамически изменя-

ется в интервале между 0 и 1 сек. в зависимости от степени заг-

рузки системы. При этом время реакции на запросы процессов может


Приоритеты выполнения Уровни приоритетов Процессы

в режиме ядра

│ -----------------------┐

│ │ Процесс │ ---┐

│ │ подкачки │-+ │

│ Не допускающие +----------------------+ L---

│ │Ожидание ввода-вывода,│ ---┐ ---┐ ---┐

│ прерывания │ связанного с диском │-+ +-+ +-+ │

│ +----------------------+ L--- L--- L---

│ │ Ожидание │ ---┐ ---┐

│ │ буфера │-+ +-+ │

│ +----------------------+ L--- L---

│ │ Ожидание │ ---┐

│ │ индекса │-+ │

│ +----------------------+ L---

│ +----------------------+

│ │ Ожидание ввода с тер-│ ---┐ ---┐ ---┐ ---┐

│ │ минала │-+ +-+ +-+ +-+ │

│ Допускающие +----------------------+ L--- L--- L--- L---

│ │ Ожидание вывода на │

│ прерывания │ терминал │

│ +----------------------+

│ │ Ожидание завершения │ ---┐ ---┐

│ │ потомка │-+ +-+ │

v +----------------------+ L--- L---

Пороговый приоритет +----------------------+ ---┐

│ Уровень задачи 0 │-+ │<- - - - - -┐

│ +----------------------+ L---

│ │ │ ---┐ ---┐ ---┐ -+-┐

│ │ Уровень задачи 1 │-+ +-+ +-+ + + │

│ +----------------------+ L--- L--- L--- L---

│ │ │

│ │ │

│ │ │

│ +----------------------+ ---┐

Приоритеты выполнения │ Уровень задачи n │-+ │

в режиме задачи L----------------------- L---


Рисунок 8.2. Переход процесса из одной очереди в другую


сократиться за счет того, что на ожидание момента запуска процес-

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

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


8.1.3 Примеры диспетчеризации процессов


На Рисунке 8.4 показана динамика изменений приоритетов про-

цессов A, B и C в версии V при следующих допущениях: все эти про-

цессы были созданы с первоначальным приоритетом 60, который явля-

ется наивысшим приоритетом выполнения в режиме задачи, прерывания

по таймеру поступают 60 раз в секунду, процессы не используют вы-

зов системных функций, в системе нет других процессов, готовых к

выполнению. Ядро вычисляет полураспад показателя ИЦП по формуле:


Время Процесс A Процесс B Процесс C

│ Приоритет ИЦП Приоритет ИЦП Приоритет ИЦП

0 --+--

│ 60 0 60 0 60 0

│ 1

│ 2

│ ·

│ ·

│ ·

1 --+-- 60

│ 75 30 60 0 60 0

│ 1

│ 2

│ ·

│ ·

│ ·

2 --+-- 60

│ 67 15 75 30 60 0

│ 1

│ 2

│ ·

│ ·

│ ·

3 --+-- 60

│ 63 7 67 15 75 30

│ 8

│ 9

│ ·

│ ·

│ ·

4 --+-- 67

│ 76 33 63 7 67 15

│ 8

│ 9

│ ·

│ ·

│ ·

5 --+-- 67

│ 68 16 76 33 63 7

│

│

│


Рисунок 8.4. Пример диспетчеризации процессов


ИЦП = decay(ИЦП) = ИЦП/2;

а приоритет процесса по формуле:

приоритет = (ИЦП/2) + 60;

Если предположить, что первым запускается процесс A и ему выделя-

ется квант времени, он выполняется в течение 1 секунды: за это

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

программа обработки прерываний увеличивает для процесса A значе-

ние поля, содержащего показатель ИЦП (с 0 до 60). По прошествии

секунды ядро переключает контекст и, произведя пересчет приорите-

тов для всех процессов, выбирает для выполнения процесс B. В те-

чение следующей секунды программа обработки прерываний по таймеру

60 раз повышает значение поля ИЦП для процесса B, после чего ядро

пересчитывает параметры диспетчеризации для всех процессов и

вновь переключает контекст. Процедура повторяется многократно,

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

Теперь рассмотрим процессы с приоритетами, приведенными на

Рисунке 8.5, и предположим, что в системе имеются и другие про-

цессы. Ядро может выгрузить процесс A, оставив его в состоянии

"готовности к выполнению", после того, как он получит подряд нес-

колько квантов времени для работы с ЦП и снизит таким образом

свой приоритет выполнения в режиме задачи (Рисунок 8.5а). Через

некоторое время после запуска процесса A в состояние "готовности

к выполнению" может перейти процесс B, приоритет которого в тот

момент окажется выше приоритета процесса A (Рисунок 8.5б). Если

ядро за это время не запланировало к выполнению любой другой про-

цесс (из тех, что не показаны на рисунке), оба процесса (A и B)

при известных обстоятельствах могут на некоторое время оказаться

на одном уровне приоритетности, хотя процесс B попадет на этот

уровень первым из-за того, что его первоначальный приоритет был

ближе (Рисунок 8.5в и 8.5г). Тем не менее, ядро запустит процесс

A впереди процесса B, поскольку процесс A находился в состоянии

"готовности к выполнению" более длительное время (Рисунок 8.5д) -

это решающее условие, если выбор производится из процессов с оди-

наковыми приоритетами.

В разделе 6.4.3 уже говорилось о том, что ядро запускает про-

цесс на выполнение после переключения контекста: прежде чем пе-

рейти в состояние приостанова или завершить свое выполнение про-

цесс должен переключить контекст, кроме того он имеет возможность

переключать контекст в момент перехода из режима ядра в режим за-

дачи. Ядро выгружает процесс, который собирается перейти в режим

задачи, если имеется готовый к выполнению процесс с более высоким

приоритетом. Такая ситуация возникает, если ядро вывело из состо-

яния приостанова процесс с приоритетом, превышающим приоритет те-

кущего процесса, или если в результате обработки прерывания по

таймеру изменились приоритеты всех готовых к выполнению процес-

сов. В первом случае текущий процесс не может выполняться в режи-

ме задачи, поскольку имеется процесс с более высоким приоритетом

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