3.5.4 Расчет приоритета

Алгоритм планирования состоит из двух уровней.

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

2. Высокоуровневый алгоритм перемещает процессы из памяти на диск и обратно. (переключение контекста)

У каждой версии UNIX низкоуровневый алгоритм слегка различается, но все они имеют много общих черт.

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

Действия низкоуровневого планировщика

1. просматривает очереди, начиная с самого высокого приоритета, пока не находит очередь, в которой есть хотя бы один процесс,

2. в найденной очереди запускается первый процесс,

3. процессу разрешается работать в течении некоторого максимального кванта времени (обычно 100 мс) или пока он не заблокируется. Если процесс использует весь свой квант времени, он помещается обратно, в конец очереди, а алгоритм планирование запускается снова.

4. если процесс готов к запуску и имеет наивысший приоритет, планировщик приостановит выполнение текущего процесса (с более низким приоритетом), даже если последний не "выработал" свой временной квант.

Ядро UNIX является непрерываемым. Это означает, что процесс, находящийся в режиме ядра (в результате системного вызова или прерывания) и выполняющий системные инструкции, не может быть прерван системой, а вычислительные ресурсы переданы другому высокоприоритетному процессу. Система может прервать выполнение процесса только при переходе из режима ядра в пользовательский режим.

5. Раз в секунду приоритет каждого процесса пересчитывается по формуле:

Pri = CPU_usage + nice + base

CPU_usage – использование ЦП – среднее значение тиков (прерываний) таймера в секунду, которые процесс работал в течение последних нескольких секунд.

При каждом тика таймера счетчик использования ЦП в таблице процессов увеличивается на 1. Т.о., пока процесс выполняется в режиме задачи, его текущий приоритет линейно уменьшается.

Но для того, чтобы не снизить приоритет процесса окончательно, ядро последовательно уменьшает величину CPU_usage (в разных версиях для этого используются разные формулы, качество алгоритма планирования определяется как раз эффективностью вычисления CPU_usage, вследствие чего лучше учитываются интересы низкоприоритетных процессов).

Nice – поправка приоритета (допустимый диапазон от -20 до 20).

Base – предопределенные отрицательные значения приоритетов для следующих операций.

• ожидание дискового ввода-вывода

• ожидание дискового буфера

• ожидание терминального ввода

• ожидание выполнения дочернего процесса

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

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