ОПИСАНИЕ

Краткие сведения о программном интерфейсе

Программный интерфейс планирования в Linux:

sched_setscheduler(2)

Назначает алгоритм планирования и параметры заданной нити.

sched_getscheduler(2)

Возвращает алгоритм планирования и параметры заданной нити.

sched_setparam(2)

Назначает параметры планирования заданной нити.

sched_getparam(2)

Возвращает параметры планирования заданной нити.

sched_get_priority_max(2)

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

sched_get_priority_min(2)

Возвращает минимальный приоритет, доступный заданному алгоритму планирования.

sched_rr_get_interval(2)

Возвращает квант, используемый нитями, которые запланированы «циклическим» (round-robin) алгоритмом планирования.

sched_yield(2)

Заставляет вызывающего освободить ЦП для выполнения других нитей.

sched_setaffinity(2)

(только в Linux) Назначить увязываемый ЦП указанной нити.

sched_getaffinity(2)

(только в Linux) Возвращает увязываемый ЦП указанной нити.

sched_setattr(2)

Назначает алгоритм планирования и параметры заданной нити. Данный системный вызов (есть только в Linux) предоставляет охватывающий набор возможностей sched_setscheduler(2) и sched_setparam(2).

sched_getattr(2)

Возвращает алгоритм планирования и параметры заданной нити. Данный системный вызов (есть только в Linux) предоставляет охватывающий набор возможностей sched_setscheduler(2) и sched_setparam(2).

Алгоритмы планирования

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

Для нитей, которые планируются одним из обычных алгоритмом планирования (SCHED_OTHER, SCHED_IDLE, SCHED_BATCH), значение sched_priority при принятии решения не используется (должен быть указан 0).

Для процессов, которые планируются одним из алгоритмов реального времени (SCHED_FIFO, SCHED_RR), значение приоритета sched_priority лежит в диапазоне от 1 (низкий) до 99 (высокий) Как и числовые значения, нити реального времени всегда имеют более высокий приоритет чем обычные нити. Но заметим: согласно POSIX.1 от реализации для алгоритмов реального времени требуется поддержка только 32 различных уровней приоритета, и в некоторых системах обеспечивается только этот минимум. В переносимых программах нужно использовать вызовы sched_get_priority_min(2) и sched_get_priority_max(2) для для определения диапазона приоритетов, поддерживаемых определённым алгоритмом.

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

Алгоритм планирования определяет, в какое место списка будет добавлена нить с тем же статическим приоритетом и как она будет перемещаться внутри этого списка.

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

SCHED_FIFO: планировщик «первым вошёл — первым вышел»

Алгоритм SCHED_FIFO можно использовать только со значениями статического приоритета большими нуля. Это означает, что если нить с SCHED_FIFO готова к работе, то она сразу запустится, а все обычные нити с SCHED_OTHER, SCHED_BATCH или SCHED_IDLE будут приостановлены. SCHED_FIFO — это простой алгоритм планирования без квантования времени. Нити, работающие согласно алгоритму SCHED_FIFO, подчиняются следующим правилам:

*

Нить с алгоритмом SCHED_FIFO, приостановленная другой нитью с большим приоритетом, останется в начале списка нитей с равным приоритетом, и её исполнение будет продолжено сразу после того, как закончатся нити с большими приоритетами.

*

Когда нить с алгоритмом SCHED_FIFO готова к работе, она помещается в конец списка нитей с тем же приоритетом.

*

Вызов sched_setscheduler(2), sched_setparam(2) или sched_setattr(2) поместит нить с номером pid и алгоритмом SCHED_FIFO (или SCHED_RR) в начало списка нитей, если она запускаема. Как следствие, она может вытеснить выполняющуюся в данный момент нить, если она имеет такой же приоритет (в POSIX.1 указано, что нить должна перейти в конец списка).

*

Нить, вызывающая sched_yield(2), будет помещена в конец списка.

Других событий для перемещения нити с алгоритмом SCHED_FIFO в списке ожидания запускаемых нитей с одинаковым статическим приоритетом не существует.

Нить с алгоритмом SCHED_FIFO выполняется до тех пор, пока не будет заблокирована запросом ввода/вывода, вытеснена нитью с большим приоритетом или пока не вызовет sched_yield(2).

SCHED_RR: планирование выполнения по циклу

SCHED_RR — это просто улучшение SCHED_FIFO. Всё, относящееся к SCHED_FIFO, справедливо и для SCHED_RR за исключением того, что каждой нити разрешено работать непрерывно не дольше максимального кванта времени. Если нить с алгоритмом SCHED_RR работала столько же или дольше, чем квант, то она помещается в конец списка с тем же приоритетом. Нить с алгоритмом SCHED_RR, вытесненная нитью с большим приоритетом, возобновляя работу, использует остаток своего кванта из старого цикла. Длину этого кванта можно узнать, вызвав sched_rr_get_interval(2).

SCHED_DEADLINE: Модель планирования случайной задачи с предельным сроком

Начиная с версии 3.14, в Linux появился алгоритм планирования с предельным сроком (SCHED_DEADLINE). Сейчас этот алгоритм реализован с помощью GEDF (Global Earliest Deadline First) в совокупности с CBS (Constant Bandwidth Server). Для назначения и выборки данного алгоритма и его атрибутов, нужно использовать системные вызовы (есть только в Linux) sched_setattr(2) и sched_getattr(2).

Случайная задача — одна из последовательности заданий (jobs), где каждое задание активизируется не более чем один раз за промежуток времени. Также у каждого задания есть относительный крайний срок, до которого оно должно завершить выполнение и время вычисления — время ЦП, необходимое для выполнения задания. Момент, когда задача пробуждается из-за выполнения нового задания, называется временем принятия (arrival time) (его ещё называют временем запроса (request time) или временем выпуска (release time). Время начала — это время когда задача начинает выполнение. Абсолютный предельный срок получается сложением относительного предельного срока с временем принятия.

Эти определения показаны в следующей диаграмме:

принятие/пробуждение                    абсолютный предельный срок
     |    время начала                  |
     |        |                         |
     v        v                         v
-----x--------xooooooooooooooooo--------x--------x---
              |<- comp. time ->|
     |<------- относительный предельный срок ------>|
     |<-------------- промежуток времени ------------------->|

При назначении нити алгоритма SCHED_DEADLINE с помощью sched_setattr(2) можно указать три параметра: Runtime, Deadline и Period. Эти параметры не обязательно соответствуют вышеупомянутым терминам: на практике, Runtime задаётся чуть больше чем среднее время вычисления (или время вычисления в самом плохом варианте для задач жёсткого реального времени), Deadline равен относительному предельному сроку, а Period равен промежутку времени. Таким образом, при планировании SCHED_DEADLINE мы имеем:

принятие/пробуждение                    абсолютный предельный срок
     |    время начала                  |
     |        |                         |
     v        v                         v
-----x--------xooooooooooooooooo--------x--------x---
              |<-- Runtime ------->|
     |<----------- Deadline ----------->|
     |<-------------- Period ------------------->|

Три параметра алгоритма с крайним сроком соответствуют полям sched_runtime, sched_deadline и sched_period структуры sched_attr; смотрите sched_setattr(2). Значения этих полей задаются в наносекундах. Если sched_period равно 0, то его значение равно sched_deadline.

Для ядра требуется соблюдение условия:

    sched_runtime <= sched_deadline <= sched_period

Также, в текущей реализации, значения всех параметров должны быть не менее 1024 (т. е., чуть более одной микросекунды, ограничено в реализации) и меньше 2^63. При нарушении ограничений sched_setattr(2) завершается с ошибкой EINVAL.

CBS гарантирует отсутствие влияния задача друг на друга, регулируя (throttling) нити, которые пытаются превысить заданное им время выполнения (Runtime).

Чтобы гарантировать выполнение алгоритма планирования крайнего срока, ядро должно предотвращать ситуации, где установка SCHED_DEADLINE нитям не выполнима (не может быть запланирована) для указанных ограничений. Для этого ядро выполняет тест допустимости при назначении или изменении алгоритма SCHED_DEADLINE и атрибутов. В данном тесте вычисляется, выполнимы ли изменения; если нет, то sched_setattr(2) завершается с ошибкой EBUSY.

Например, для этого требуется (но не обязательно достаточно), чтобы общая загруженность была меньше или равной общему количеству доступных ЦП, так как каждая нить максимально может работать весь промежуток времени, то есть загруженность нити равна её Runtime, поделённый на Period.

Чтобы удовлетворить гарантиям, которые даны, когда нити назначен алгоритм SCHED_DEADLINE, нити с SCHED_DEADLINE имеют наивысший приоритет (управляется пользователем) по сравнению с другими нитями в системе; если нить с SCHED_DEADLINE запускается, то она вытеснит любую нить, запланированную любым другим алгоритмом.

Вызов fork(2) в нити, запланированной SCHED_DEADLINE завершится с ошибкой EAGAIN, если у нити не установлен флаг reset-on-fork (смотрите далее).

Нить с SCHED_DEADLINE, вызывающая sched_yield(2) приостановит текущее задание и будет ждать начала нового промежутка времени.

SCHED_OTHER: планирование с разделение времени (по умолчанию в Linux)

SCHED_OTHER можно использовать только с статическим приоритетом равным нулю. SCHED_OTHER — это стандартный планировщик Linux с разделением времени, предназначенный для всех нитей, не требующих специальных механизмов реального времени. Для выполнения выбирается нить из списка со статическим приоритетом 0 на основе динамического приоритета, существующего только внутри этого списка. Динамический приоритет основан на значении nice (установленном при помощи nice(2), setpriority(2) или sched_setattr(2)) и увеличивается с каждым квантом времени, при котором нить была готова к работе, но ей было отказано в этом планировщиком. Таким образом время равномерно распределяется между всеми нитями с алгоритмом SCHED_OTHER.

SCHED_BATCH: планирование для пакетных процессов

(начиная с Linux 2.6.16) SCHED_BATCH можно использовать только с статическим приоритетом равным нулю. Этот алгоритм похож на SCHED_OTHER в том, что он планирует выполнение нити на основе её динамического приоритета (на основе значения nice). Различие в том, что в этом алгоритме планировщик всегда предполагает, что нить, в основном, использует ЦП. Следовательно, планировщик немного понизит вероятность её следующего пробуждения для того, чтобы эта нить уступила другим при планировании.

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

SCHED_IDLE: планирование заданий с очень низким приоритетом

(начиная с Linux 2.6.23) SCHED_IDLE можно использовать только с статическим приоритетом равным нулю; значение nice не учитывает в этом алгоритме.

Данный алгоритм предназначен для выполнения заданий с чрезвычайно низким приоритетом (даже ниже чем значение nice +19 в алгоритме SCHED_OTHER или SCHED_BATCH).

Сброс алгоритма планирования у дочерних процессов

В каждой нити есть флаг планирования reset-on-fork. Когда этот флаг установлен, потомки, создаваемые fork(2), не наследуют привилегированные алгоритмы планирования. Флаг reset-on-fork может быть задан так:

*

Логическим сложением флага SCHED_RESET_ON_FORK с аргументом policy при вызове sched_setscheduler(2) (начиная с Linux 2.6.32); или

*

заданием флага SCHED_FLAG_RESET_ON_FORK в attr.sched_flags при вызове sched_setattr(2).

Заметим, что константы, используемые в этих двух вызовам имеют разные имена. Состояние флага reset-on-fork может быть получено аналогичным образом с помощью sched_getscheduler(2) и sched_getattr(2).

Возможность reset-on-fork предназначена для приложений, проигрывающих медиа-файлы, и может использоваться для обхождения ограничения ресурса RLIMIT_RTTIME (см. getrlimit(2)), посредством создания нескольких дочерних процессов.

Точнее говоря, если указан флаг reset-on-fork, то к новым потомкам применяются следующие правила:

*

Если вызывающая нить имеет алгоритм планирования SCHED_FIFO или SCHED_RR, то у потомков алгоритм сбрасывается в SCHED_OTHER.

*

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

После установки флага reset-on-fork его можно сбросить только, если нить имеет мандат CAP_SYS_NICE. Этот флаг выключается у потомков, созданных через fork(2).

Привилегии и ограничения по ресурсам

В ядрах Linux до версии 2.6.12, только привилегированные нити (CAP_SYS_NICE) могли устанавливать ненулевое значение статического приоритета (т.е. алгоритм планирования реального времени). Непривилегированные нити могли только установить алгоритм SCHED_OTHER, и это могло быть сделано только, если эффективный пользовательский идентификатор вызывающего совпадал с реальным или эффективным пользовательским идентификатором задаваемого нити (т.е., нити, указываемой в pid).

Для задания или изменения SCHED_DEADLINE нить должна быть привилегированной (CAP_SYS_NICE).

Начиная с Linux 2.6.12, ограничитель ресурса RLIMIT_RTPRIO определяет максимум статического приоритета непривилегированной нити для алгоритмов SCHED_RR и SCHED_FIFO. Правила для изменения алгоритма планирования и приоритета:

*

Если непривилегированная нить имеет ненулевое значение мягкого ограничения RLIMIT_RTPRIO, то она может изменять свой алгоритм планирования и приоритет, но при этом значение приоритета не может быть больше чем максимальное значение её текущего приоритета и его мягкого ограничения RLIMIT_RTPRIO.

*

Если мягкое ограничение RLIMIT_RTPRIO равно 0, то разрешается только снижать приоритет или переключиться на алгоритм выполнения не реального времени.

*

Согласно тем же самым правилам другая непривилегированная нить может также сделать эти изменения, пока эффективный идентификатор пользователя нити, производящей изменение, совпадает с реальным или эффективным идентификатором пользователя изменяемой нити.

*

Для политики SCHED_IDLE применяются специальные правила. В ядрах Linux до версии 2.6.39, сменить политику работы непривилегированной нити нельзя, независимо от значения её ограничителя ресурсов RLIMIT_RTPRIO. В ядрах Linux начиная с версии 2.6.39, непривилегированная нить может переключиться на политику SCHED_BATCH или SCHED_OTHER, если её значение уступчивости находится в диапазоне, разрешённом ей ограничителем ресурсов RLIMIT_NICE (см. getrlimit(2)).

Для привилегированных (CAP_SYS_NICE) нитей ограничение RLIMIT_RTPRIO игнорируется; как в старых ядрах, они могут произвольно менять алгоритм планирования и приоритет. Подробней смотрите в getrlimit(2) про RLIMIT_RTPRIO.

Ограничение использование ЦП процессами реального времени и процессами с крайним сроком

Неблокирующий бесконечный цикл в нити, запланированной алгоритмами SCHED_FIFO, SCHED_RR или SCHED_DEADLINE приведёт к вечному блокированию всех нитей с более низким приоритетом. До Linux 2.6.25 был только один способ предотвращения заморозки системы бесконтрольными процессами реального времени — запуск (с консоли) оболочки с наивысшим статическим приоритетом, большим чем тестируемое приложение. Это позволяло экстренно прибить тестируемое приложение реального времени, которое не блокируется или завершается как положено.

Начиная с Linux 2.6.25, есть другие способы работы с процессами реального времени и процессами с крайним сроком. Один из них — использовать ограничитель ресурса RLIMIT_RTTIME, задав потолок времени ЦП, которое процесс реального времени может задействовать. Подробней смотрите в getrlimit(2).

Начиная с версии 2.6.25, в Linux также предоставляется два файла в /proc, которые можно использовать для резервирования определённого количества времени ЦП, используемое процессами нереального времени. Резервирование некоторого количества ЦП подобным образом позволяет оставить время ЦП (скажем) оболочке root, через которую можно завершить неконтролируемый процесс. В этих файлах значение времени указывается в микросекундах:

/proc/sys/kernel/sched_rt_period_us

В данном файле задаётся планируемый промежуток времени, который равен 100% полосы ЦП. Значение в этом файле может лежать в диапазоне от 1 до INT_MAX, что даёт рабочий диапазон от 1 микросекунды до, приблизительно, 35 минут. Значение в файле по умолчанию равно 1000000 (1 секунда).

/proc/sys/kernel/sched_rt_runtime_us

Значением в этом файле определяется насколько большой промежуток времени может использоваться всеми процессами реального времени и процессами с крайним сроком в системе. Диапазон значений: от -1 до INT_MAX-1. Значение -1 означает, что время выполнения равно промежутку времени; то есть нет времени ЦП для приложений нереального времени (что соответствует поведению Linux до версии ядра 2.6.25). Значение по умолчанию равно 950000 (0.95 секунды), означающее, что 5% времени ЦП зарезервировано для процессов, планирование которых выполняется не по алгоритму реального времени или алгоритму с крайним сроком.

Время ответа

Блокированная нить с высоким приоритетом, ожидающая ввода/вывода, освобождает достаточно много процессорного времени до того, как снова начнёт работать. Авторы драйверов устройств могут более эффективно использовать это время, если воспользуются «медленным» обработчиком прерываний.

Разное

Дочерние процессы наследуют алгоритм планирования и его параметры после fork(2). Алгоритм планирования и параметры сохраняются при вызове execve(2).

Обычно, процессам реального времени необходимо блокировать память для того, чтобы избежать задержек при страничном обмене. Это можно сделать при помощи вызова mlock(2) или mlockall(2).

ЗАМЕЧАНИЯ

Изначально стандартный Linux представлял собой операционную систему общего назначения для выполнения как фоновых процессов, так и интерактивных приложений, а также нетребовательных приложений реального времени (приложений, которым желательно, чтобы задержки и интервалы времени выдерживались). Хотя ядро Linux 2.6 позволяет вытеснение и новый планировщик O(1) обеспечивает необходимое постоянство планирования и предсказуемое независимое количество активных задач, настоящая работа в реальном времени стала доступна начиная с версии ядра 2.6.17.

Возможности выполнения в реальном времени из оригинальной версии Linux

Начиная с версии 2.6.18, Linux постепенно обрастает возможностями выполнения в реальном времени, большая часть которых взята из ранних заплаток realtime-preempt, разработанных Ingo Molnar, Thomas Gleixner, Steven Rostedt и другими. Пока заплатки полностью не вошли в основное ядро, они должны быть установлены отдельно. Файлы заплаток называются

patch-версия_ядра-rtверсия_заплатки

и могут быть скачаны с

Без заплаток и до их полного включения в оригинальное ядро, через параметры ядра предлагается только три класса вытеснения: CONFIG_PREEMPT_NONE, CONFIG_PREEMPT_VOLUNTARY и CONFIG_PREEMPT_DESKTOP, которые, соответственно, не сокращают, частично сокращают и значительно сокращают задержку планирования при наихудшем случае.

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