Как планировщик процесса Linux предотвращает голодание процесса

Question

Я читал, что ядро ​​linux содержит много классов расписания, каждый из которых имеет свой собственный приоритет. Чтобы выбрать новый процесс для запуска, планировщик процессов выполняет итерацию с класса с наивысшим приоритетом до класса с наименьшим приоритетом. Если в классе обнаружен runnable-процесс, то из этого класса выбирается процесс с наивысшим приоритетом.

Извлечение из разработки ядра Linux Роберт Love:

Основная точка входа в график процесса является функция график(), определенный в ядре/sched.c .Это функция, что остальная часть ядра использует для вызова планировщика процессов, решая , какой процесс запускается, а затем запускает его. schedule() является общим с уважением к классам планировщика. То есть он находит класс планировщика с наивысшим приоритетом с запущенным процессом и спрашивает, для чего он должен работать дальше. Учитывая это, неудивительно, что расписание() прост. только важная часть функции, которая иначе тоже , неинтересная для воспроизведения здесь, - это ее вызов pick_next_task() , также определенный в ядре/расписании .c. Функция pick_next_task() отправляется через каждый класс планировщика, начиная с наивысшего приоритета, а выбирает процесс с наивысшим приоритетом в классе с наивысшим приоритетом.

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

Answer 1

Было бы действительно голодать. Существует множество способов решения такого сценария.

1. Старение, чем дольше процесс в системе, тем выше приоритет.
2. Алгоритмы планирования, дающие каждому процессу квант времени для использования ЦП. Время-квант изменяется, как правило, интерактивным процессам дается более низкий квант времени, поскольку они тратят больше времени на ввод-вывод, в то время как трудоемкие/вычислительные процессы получают больший квант времени. После того, как процесс выполнит квант времени, он помещается в очередь с истекшим сроком, пока в системе не будет активных процессов. Затем истекшая очередь становится активной очередью и наоборот. Это 2 способа предотвращения голодания.

Answer 2

Ядро Linux реализует полностью справедливый алгоритм планирования, основанный на виртуальных часах.

Каждой диспетчеризация предприятие имеет sched_entity структуру, связанную с ним, чьим снимком выглядит как

struct sched_entity { 
    ... 
    u64 exec_start; 
    u64 sum_exec_runtime; 
    u64 vruntime; 
    u64 prev_sum_exec_runtime; 
    ... 
}

Вышеуказанные четыре атрибута используется для отслеживания времени выполнения процесса, и с помощью этих атрибутов наряду с некоторыми другими методами (update_curr() где они обновляются), виртуальные часы реализованы. Когда процесс присваивается процессору, exec_start обновляется до текущего времени, а потребляемое процессорное время записывается в sum_exec_runtime. Когда процесс снят с CPU sum_exec_runtime, значение сохраняется в prev_sum_exec_runtime. sum_exec_runtime рассчитывается кумулятивно. (Значение монотонно растет).

vruntime хранит время, прошедшее на виртуальных часах во время выполнения процесса.

Как рассчитывается vruntime?

Игнорируя все сложные расчеты, основное понятие, как она рассчитывается является: -

vruntime += delta_exec_weighted; 
delta_exec_weighted = delta_exec * (NICE_0_LOAD/load.weight); 

Здесь delta_exec разница во времени между процессом присвоенного CPU и вылетело из процессора, тогда как load.weight является вес процесса, который зависит от приоритета (Nice Value). Обычно увеличение хорошего значения 1 для процесса означает, что он получает на 10 процентов меньше процессорного времени, что приводит к меньшему весу. процесса с NICE значением 0, вес = 1024 Процесс повторной Niced со значением 1, вес = 1024/1,25 = 820 (приблизительно)

Очки, извлеченные из вышеуказанных

• So vruntime увеличивается, когда процесс получает CPU
• И vruntime медленно увеличивается для процессов с более высоким приоритетом по сравнению с процессами с более низким приоритетом.

runqueue поддерживается в красно-черном дереве, и каждый имеет runqueue min_vruntime переменный, связанные с ним, который содержит наименьшее среди всех vruntime процесса в runqueue. (min_vruntime может только увеличиваться, а не уменьшаться по мере планирования процессов).

Ключ для узла в красном черном дереве process->vruntime - min_vruntime

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

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

1. Когда процесс запущен, его vruntime будет неуклонно расти, поэтому он, наконец, движется вправо в красно-черном дереве. Поскольку vruntime увеличивается медленнее для более важных процессов, они также будут перемещаться вправо более медленно, поэтому их шанс быть запланированным больше для менее важного процесса - как и требовалось.
2. Если процесс засыпает, его vruntime останется без изменений. Так как количество очередей min_vruntime будет увеличиваться, процесс спящего будет больше расположен слева после пробуждения, потому что ключ (упомянутый выше) стал меньше.

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