Архитектура операционной системы UNIX (ЛП) - Бах Морис Дж.
Шрифт:
Интервал:
Закладка:
43. Формат записей в файле "/etc/inittab" допускает задание действия, связанного с каждым порождаемым процессом. Например, с getty-процессом связано действие "respawn" (возрождение), означающее, что процесс init должен возрождать getty-процесс, если последний прекращает существование. На практике, когда пользователь выходит из системы процесс init порождает новый getty-процесс, чтобы другой пользователь мог получить доступ к временно бездействующей терминальной линии. Каким образом это делает процесс init?
44. Некоторые из алгоритмов ядра прибегают к просмотру таблицы процессов. Время поиска данных можно сократить, если использовать указатели на: родителя процесса, любого из потомков, другой процесс, имеющий того же родителя. Процесс обнаруживает всех своих потомков, следуя сначала за указателем на любого из потомков, а затем используя указатели на другие процессы, имеющие того же родителя (циклы недопустимы). Какие из алгоритмов выиграют от этого? Какие из алгоритмов нужно оставить без изменений?
ГЛАВА 8. ДИСПЕТЧЕРИЗАЦИЯ ПРОЦЕССОВ И ЕЕ ВРЕМЕННЫЕ ХАРАКТЕРИСТИКИ
В системе разделения времени ядро предоставляет процессу ресурсы центрального процессора (ЦП) на интервал времени, называемый квантом, по истечении которого выгружает этот процесс и запускает другой, периодически переупорядочивая очередь процессов. Алгоритм планирования процессов в системе UNIX использует время выполнения в качестве параметра. Каждый активный процесс имеет приоритет планирования; ядро переключает контекст на процесс с наивысшим приоритетом. При переходе выполняющегося процесса из режима ядра в режим задачи ядро пересчитывает его приоритет, периодически и в режиме задачи переустанавливая приоритет каждого процесса, готового к выполнению.
Информация о времени, связанном с выполнением, нужна также и некоторым из пользовательских процессов: используемая ими, например, команда time позволяет узнать, сколько времени занимает выполнение другой команды, команда date выводит текущую дату и время суток. С помощью различных системных функций процессы могут устанавливать или получать временные характеристики выполнения в режиме ядра, а также степень загруженности центрального процессора. Время в системе поддерживается с помощью аппаратных часов, которые посылают ЦП прерывания с фиксированной, аппаратно-зависимой частотой, обычно 50-100 раз в секунду. Каждое поступление прерывания по таймеру (часам) именуется таймерным тиком. В настоящей главе рассматриваются особенности реализации процессов во времени, включая планирование процессов в системе UNIX, описание связанных со временем системных функций, а также функций, выполняемых программой обработки прерываний по таймеру.
8.1 ПЛАНИРОВАНИЕ ВЫПОЛНЕНИЯ ПРОЦЕССОВ
Планировщик процессов в системе UNIX принадлежит к общему классу планировщиков, работающих по принципу "карусели с многоуровневой обратной связью". В соответствии с этим принципом ядро предоставляет процессу ресурсы ЦП на квант времени, по истечении которого выгружает этот процесс и возвращает его в одну из нескольких очередей, регулируемых приоритетами. Прежде чем процесс завершится, ему может потребоваться множество раз пройти через цикл с обратной связью. Когда ядро выполняет переключение контекста и восстанавливает контекст процесса, процесс возобновляет выполнение с точки приостанова.
8.1.1 Алгоритм
Сразу после переключения контекста ядро запускает алгоритм планирования выполнения процессов (Рисунок 8.1), выбирая на выполнение процесс с наивысшим приоритетом среди процессов, находящихся в состояниях "резервирования" и "готовности к выполнению, будучи загруженным в память". Рассматривать процессы, не загруженные в память, не имеет смысла, поскольку не будучи загружен, процесс не может выполняться. Если наивысший приоритет имеют сразу несколько процессов, ядро, используя принцип кольцевого списка (карусели), выбирает среди них тот процесс, который находится в состоянии "готовности к выполнению" дольше остальных. Если ни один из процессов не может быть выбран для выполнения, ЦП простаивает до момента получения следующего прерывания, которое произойдет не позже чем через один таймерный тик; после обработки этого прерывания ядро снова запустит алгоритм планирования.
алгоритм schedule_process
входная информация: отсутствует
выходная информация: отсутствует
{
выполнять пока (для запуска не будет выбран один из процессов) {
for (каждого процесса в очереди готовых к выполнению)
выбрать процесс с наивысшим приоритетом из загруженных в память;
if (ни один из процессов не может быть избран для выполнения)
приостановить машину;
/* машина выходит из состояния простоя по прерыванию */
}
удалить выбранный процесс из очереди готовых к выполнению;
переключиться на контекст выбранного процесса, возобновить его выполнение;
}
Рисунок 8.1. Алгоритм планирования выполнения процессов
8.1.2 Параметры диспетчеризации
В каждой записи таблицы процессов есть поле приоритета, используемое планировщиком процессов. Приоритет процесса в режиме задачи зависит от того, как этот процесс перед этим использовал ресурсы ЦП. Можно выделить два класса приоритетов процесса (Рисунок 8.2): приоритеты выполнения в режиме ядра и приоритеты выполнения в режиме задачи. Каждый класс включает в себя ряд значений, с каждым значением логически ассоциирована некоторая очередь процессов. Приоритеты выполнения в режиме задачи оцениваются для процессов, выгруженных по возвращении из режима ядра в режим задачи, приоритеты выполнения в режиме ядра имеют смысл только в контексте алгоритма sleep. Приоритеты выполнения в режиме задачи имеют верхнее пороговое значение, приоритеты выполнения в режиме ядра имеют нижнее пороговое значение. Среди приоритетов выполнения в режиме ядра далее можно выделить высокие и низкие приоритеты: процессы с низким приоритетом возобновляются по получении сигнала, а процессы с высоким приоритетом продолжают оставаться в состоянии приостанова (см. раздел 7.2.1).
Пороговое значение между приоритетами выполнения в режимах ядра и задачи на Рисунке 8.2 отмечено двойной линией, проходящей между приоритетом ожидания завершения потомка (в режиме ядра) и нулевым приоритетом выполнения в режиме задачи. Приоритеты процесса подкачки, ожидания ввода-вывода, связанного с диском, ожидания буфера и индекса являются высокими, не допускающими прерывания системными приоритетами, с каждым из которых связана очередь из 1, 3, 2 и 1 процесса, соответственно, в то время как приоритеты ожидания ввода с терминала, вывода на терминал и завершения потомка являются низкими, допускающими прерывания системными приоритетами, с каждым из которых связана очередь из 4, 0 и 2 процессов, соответственно. На рисунке представлены также уровни приоритетов выполнения в режиме задачи[24].
Ядро вычисляет приоритет процесса в следующих случаях:
• Непосредственно перед переходом процесса в состояние приостанова ядро назначает ему приоритет исходя из причины приостанова. Приоритет не зависит от динамических характеристик процесса (продолжительности ввода-вывода или времени счета), напротив, это постоянная величина, жестко устанавливаемая в момент приостанова и зависящая только от причины перехода процесса в данное состояние. Процессы, приостановленные алгоритмами низкого уровня, имеют тенденцию порождать тем больше узких мест в системе, чем дольше они находятся в этом состоянии; поэтому им назначается более высокий приоритет по сравнению с остальными процессами. Например, процесс, приостановленный в ожидании завершения ввода-вывода, связанного с диском, имеет более высокий приоритет по сравнению с процессом, ожидающим освобождения буфера, по нескольким причинам. Прежде всего, у первого процесса уже есть буфер, поэтому не исключена возможность, что когда он возобновится, он успеет освободить и буфер, и другие ресурсы. Чем больше ресурсов свободно, тем меньше шансов для возникновения взаимной блокировки процессов. Системе не придется часто переключать контекст, благодаря чему сократится время реакции процесса и увеличится производительность системы. Во-вторых, буфер, освобождения которого ожидает процесс, может быть занят процессом, ожидающим в свою очередь завершения ввода-вывода. По завершении ввода-вывода будут возобновлены оба процесса, поскольку они были приостановлены по одному и тому же адресу. Если первым запустить на выполнение процесс, ожидающий освобождения буфера, он в любом случае снова приостановится до тех пор, пока буфер не будет освобожден; следовательно, его приоритет должен быть ниже.
