Планировщик контролирует, какой поток будет выполняться и как долго он будет выполняться в Linux. Он должен решать 2 противоречащих друг другу требования: скорость реакции на ввод-вывод и пропускная способность вычислений.

Порядок выполнения основан на политике планирования и приоритете планирования, который имеет каждый поток. Политика планирования была введена в Linux в версии 2.2. Linux предоставляет 6 политик: SCHED_FIFO, SCHED_RR, SCHED_DEADLINE, SCHED_DEADLINE, SCHED_OTHER, SCHED_BATCH иSCHED_IDLE. Эти политики, за исключением SCHED_DEADLINE, разделены на 2 группы; SCHED_OTHER, SCHED_IDLE и SCHED_BATCH относятся к нормальной политике, а SCHED_FIFO, SCHED_RR относятся к политике реального времени. SCHED_DEADLINE threads - это особые потоки с наивысшим приоритетом.

Каждый поток имеет значение sched_priority, а потоки с более высокими значениями sched_priority имеют приоритет над другими. sched_priority иногда называют приоритетом реального времени, поскольку он в основном используется для определения порядка выполнения потоков с политикой реального времени. sched_priority значения потоков с обычными политиками равны 0, а значения потоков с политиками реального времени обычно принимают от 1 до 99. Хотя диапазон sched_priority зависит от системы, фактический диапазон можно проверить с помощью функций sched_get_priority_min и sched_get_priority_max в каждом POSIX система. Значение sched_priority вместе с политикой может быть установлено функцией sched_setscheduler и проверено функцией sched_getscheduler.

В то время как значение sched_priority предназначено для потоков реального времени, значение, определяющее, какой нормальный поток вытесняет другие нормальные потоки, называется хорошим значением. Диапазон значений nice: от -20 (высокий приоритет) до +19 (низкий приоритет). Значение nice может быть установлено функцией nice или функцией setpriority и проверено функцией getpriority.

Как Linux выполняет потоки в соответствии с этими значениями приоритета в реальном времени? Потоки реального времени не имеют ограничений по времени выполнения, и Linux в основном выполняет поток реального времени с наивысшим значением приоритета до тех пор, пока поток не завершит свое выполнение самостоятельно или поток с более высоким значением приоритета не вытеснит поток. Однако это часто вызывает проблемы, поскольку, если некоторые нежелательные потоки реального времени начинают работать и никогда не заканчиваются, единственный способ остановить это - запустить другие потоки с более высоким приоритетом. Итак, начиная с версии 2.6.25, есть другие функции для остановки этих нежелательных потоков реального времени, такие как предварительное ограничение времени выполнения с помощью RLMIT_RTTIME. Тем не менее, не рекомендуется использовать политику реального времени без внимательного рассмотрения, потому что в Linux есть интеллектуальная система планирования, называемая Completely Fair Scheduler (CFS) для обычных потоков, которая была представлена ​​в версии 2.6.23 ядра Linux. CFS решает, какой поток выполнять и как долго он может выполняться.

CFS использует красно-черную древовидную структуру данных, одно из двоичных деревьев, для реализации справедливого планирования. В CFS каждая задача имеет свое время выполнения, и CFS строит красно-черное дерево задач по времени выполнения. Для выполнения выбирается задача с наименьшим временем выполнения в дереве. После выполнения CFS добавляет время выполнения к задаче и снова помещает ее в красно-черное дерево в соответствии со временем выполнения. Это позволяет задачам, которые долго спят, выполняться, как только они должны быть выполнены, что звучит справедливо. Каждый раз, когда CFS завершает выполнение задачи, он должен вставить выполненную задачу обратно в дерево и искать следующую задачу с наименьшим временем выполнения. Это требует структуры данных, которая не займет много времени даже в худшем случае. Это одна из причин, по которой принято красно-черное дерево. В красно-черном дереве каждый узел красный или черный, а потомки красных узлов всегда черные. Наиболее важно то, что каждый путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов. Это приводит к критическому свойству красно-черного дерева, что путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа, это гарантирует наихудшее время для поиска, вставки , и удаление в O (журнал n), и это полезно для CFS, чтобы поддерживать свое расписание в актуальном состоянии.

Теперь мы знаем, как CFS определяет порядок выполнения, и перейдем к тому, как CFS определяет время каждого выполнения. Каждое время выполнения определяется в результате расчета баланса 4 факторов: целевая задержка, минимальная детализация, количество ожидающих задач, хорошие значения задач. Целевая задержка - это время, необходимое для выполнения каждой задачи хотя бы один раз. Минимальная степень детализации - это самое короткое время выполнения, время выполнения ниже которого приводит к высокой стоимости переключения контекста. По сути, целевая задержка делится на каждую задачу взвешенным образом в зависимости от значений nice, так что каждое время выполнения превышает минимальную степень детализации. Более высокая целевая задержка приводит к более длительному времени выполнения, особенно для задач с более высоким приоритетом, а более высокая минимальная степень детализации приводит к более равному времени выполнения независимо от значений nice.

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