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

• Приоритеты всех процессов в режиме задачи с интервалом в 1 секунду (в версии V) пересчитывает программа обработки прерываний по таймеру, побуждая тем самым ядро выполнять алгоритм планирования, чтобы не допустить монопольного использования ресурсов ЦП одним процессом.

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

В течение кванта времени таймер может послать процессу несколько прерываний; при каждом прерывании программа обработки прерываний по таймеру увеличивает значение, хранящееся в поле таблицы процессов, которое описывает продолжительность использования ресурсов центрального процессора (ИЦП). В версии V каждую секунду программа обработки прерываний переустанавливает значение этого поля, используя функцию полураспада (decay):

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

После этого программа пересчитывает приоритет каждого процесса, находящегося в состоянии "зарезервирован, но готов к выполнению", по формуле

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

где под "базовым уровнем приоритета задачи" понимается пороговое значение, расположенное между приоритетами выполнения в режимах ядра и задачи. Высокому приоритету планирования соответствует количественно низкое значение. Анализ функций пересчета продолжительности использования ресурсов ЦП и приоритета процесса показывает: чем ниже скорость полураспада значения ИЦП, тем медленнее приоритет процесса достигает значение базового уровня; поэтому процессы в состоянии "готовности к выполнению" имеют тенденцию занимать большое число уровней приоритетов.

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

Ядро стремится производить пересчет приоритетов всех активных процессов ежесекундно, однако интервал между моментами пересчета может слегка варьироваться. Если прерывание по таймеру поступило тогда, когда ядро исполняло критический отрезок программы (другими словами, в то время, когда приоритет работы ЦП был повышен, но, очевидно, не настолько, чтобы воспрепятствовать прерыванию данного типа), ядро не пересчитывает приоритеты, иначе ему пришлось бы надолго задержаться на критическом отрезке. Вместо этого ядро запоминает то, что ему следует произвести пересчет приоритетов, и делает это при первом же прерывании по таймеру, поступающем после снижения приоритета работы ЦП. Периодический пересчет приоритета процессов гарантирует проведение стратегии планирования, основанной на использовании кольцевого списка процессов, выполняющихся в режиме задачи. При этом конечно же ядро откликается на интерактивные запросы таких программ, как текстовые редакторы или программы форматного ввода: процессы, их реализующие, имеют высокий коэффициент простоя (отношение времени простоя к продолжительности использования ЦП) и поэтому естественно было бы повышать их приоритет, когда они готовы для выполнения (см. [Thompson 78], стр.1937). В других механизмах планирования квант времени, выделяемый процессу на работу с ресурсами ЦП, динамически изменяется в интервале между 0 и 1 сек. в зависимости от степени загрузки системы. При этом время реакции на запросы процессов может сократиться за счет того, что на ожидание момента запуска процессам уже не нужно отводить по целой секунде; однако, с другой стороны, ядру приходится чаще прибегать к переключению контекстов.

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

На Рисунке 8.4 показана динамика изменений приоритетов процессов A, B и C в версии V при следующих допущениях: все эти процессы были созданы с первоначальным приоритетом 60, который является наивысшим приоритетом выполнения в режиме задачи, прерывания по таймеру поступают 60 раз в секунду, процессы не используют вызов системных функций, в системе нет других процессов, готовых к выполнению. Ядро вычисляет полураспад показателя ИЦП по формуле:

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

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

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

Если предположить, что первым запускается процесс A и ему выделяется квант времени, он выполняется в течение 1 секунды: за это время таймер посылает системе 60 прерываний и столько же раз программа обработки прерываний увеличивает для процесса A значение поля, содержащего показатель ИЦП (с 0 до 60). По прошествии секунды ядро переключает контекст и, произведя пересчет приоритетов для всех процессов, выбирает для выполнения процесс B. В течение следующей секунды программа обработки прерываний по таймеру 60 раз повышает значение поля ИЦП для процесса B, после чего ядро пересчитывает параметры диспетчеризации для всех процессов и вновь переключает контекст. Процедура повторяется многократно, сопровождаясь поочередным запуском процессов на выполнение.

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

Теперь рассмотрим процессы с приоритетами, приведенными на Рисунке 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 уже говорилось о том, что ядро запускает процесс на выполнение после переключения контекста: прежде чем перейти в состояние приостанова или завершить свое выполнение процесс должен переключить контекст, кроме того он имеет возможность переключать контекст в момент перехода из режима ядра в режим задачи. Ядро выгружает процесс, который собирается перейти в режим задачи, если имеется готовый к выполнению процесс с более высоким приоритетом. Такая ситуация возникает, если ядро вывело из состояния приостанова процесс с приоритетом, превышающим приоритет текущего процесса, или если в результате обработки прерывания по таймеру изменились приоритеты всех готовых к выполнению процессов. В первом случае текущий процесс не может выполняться в режиме задачи, поскольку имеется процесс с более высоким приоритетом выполнения в режиме ядра. Во втором случае программа обработки прерываний по таймеру решает, что процесс использовал выделенный ему квант времени, и поскольку множество процессов при этом меняют свои приоритеты, ядро выполняет переключение контекста.