Real-Time Scheduling -- планировщик для RTOS

Цель статьи - восполнить нехватку терминологии в области управления процессами в системе реального времени, ОСРВ (анг. Real-Time OS). Надо определить, где наша RTOS располагатся относительно мировых достижений. В данной статье рассматривается терминология и обсуждается применимость методов планирования.

Хороший планировщик заданий - не обязательно сложный и ресурсоемкий алгоритм. Когда мы создаем операционную систему для контроллера мы работаем с голым железом. Ничто нас не ограничивает, мы можем использовать предоставляемые возможности контроллера на свое усмотрение. Эффективное управление можно описать без использования операционной системы. Необходимостью является довольно существенный объем системного кода, который выполняет переключение задач - планировщик заданий (анг. Task Scheduler).

Наша RTOS как идея зарождалась, когда мы еще использовали 8-битные контроллеры 51-й серии. Тогда не было никакой необходимости в планировании времени, наша ОС состояла из двух основных частей: жеского реал-тайма, который запускался по таймеру, и некоторой системной части - модульного ядра, которая выполнялась последовательно без переключения между заданиями. Позже, с переходом на 32 битные контроллеры ARM7TDMI, мы внедрили динамическое распределение памяти, и с переходом на Cortex-M стали активно использовать многозадачность. В качестве основного интерфейса был выбран CMSIS-RTOS API, с поддержкой тредов и полного набора возможностей синхронизации. В таком виде концепция ОС для конотроллеров просуществовала на протяжении 10 лет. Сегодня мы поддерживаем три системных интерфейса: CMSIS-RTOS API, CMSIS-RTOS v2, C11 <threads.h>. В этом году мы начали работу по масштабной поддержке системных интерфейсов POSIX. Реализация POSIX позволяет обеспечить переносимость прикладного кода между системами. Мы хотим сохранить эффективность управления заданиями и возможность гибкой настройки процессов планирования и в тоже время добавить переносимость для прикладного кода. Мы придерживаемся требования на сохранение эффективности кода: внедрение поддержки POSIX не должно вызывать существенного увеличения объема прошивок и снижения эффективности.

Терминология

Real-Time System

-- ОС в которой для успешной работы требуется точное соблюдение временных параметров запуска и исполнения задач.

Soft real-time, Hard real-time

RTOS cистемы условно можно разделить на две категории: с мягкими и жесткими требованиями. Различие можно определить так: нарушение временных параметров запуска заданий ведет к фатальным последствиям (hard real-time) или к временным сбоям, с возможностью дальнейшей работы (soft real-time). Пример жесткого реал-тайма: управение двигателем, управление рановесием (балансом), упраление летательным аппаратом. Обычно жесткие требования возникают применительно к задачам с периодической активностью. Soft real-time применятеся к апериодичским процессам.

Task -- задача (τ_i), процесс или тред, объект, для которого выполняется планирование времени запуска.
Job -- задание (J_i,j), процесс (Task_i) складывается из заданий.
Arrival Time (a_i,j) -- абсолютное время, когда процесс (τ_i) готов к исполнению очередного задания (J_i,j).
Burst Time, Execution time (c_i,j) -- время исполнения, интервал времени, когда процесс исполняется на CPU (Job), занимает процессорное время.
Absolute deadline, d_i,j, -- время от момента постановки в очередь до завершения выполнения задания (J_i,j). Время ожидания (arrival) и время работы (Execution time) в сумме образуют deadline (готовность)
worst case execution time (WCET) -- максимальное время исполнения.
minimum inter-arrival time (MIT) -- минимальная измеренная разница между задержками (arrival) на исполнение двух последовательных заданий одного процесса.

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

Priority Scheduling (PS)
-- планирование на основе приоритетов. Процессы орагнизуются в несколько очередей, каждая со своим приоритетом: сначала исполняются процессы с большим приоритетом, затем - с меньшим. Термин PS может применяться в сочетании с другими принципами планирования. Система, в которой PS - единственный механизм планирования, не жизнеспособная и не применима к RTOS, поскольку не гарантирует своевременное исполнение заданий.

Cooperative vs. Preemptive -- кооперативная и вытесняющая многозадачность. Кооперативная получается, когда процесс может передать управление только добровольно, например при ожидании ввода-вывода. Вытесняющая, когда определены правила переключения задач по времени работы. Правила переключения задач могут включать требования на приоритеты задач. Самая простая модель -- переключение задач на основе приоритетов: сначала выполняются все задачи с большим приоритетом, затем с меньшим. Процессы с большим приоритетом могут прерывать работу процессов с меньшим приоритетом. Процессы могут быть организованы в кольцевой буфер без нарушения порядка следования, первым вошел первым вышел(FIFO). В случае PS на основе приоритетов говорят об использовании нескольких очередей, каждая со своим приоритетом.

Rate-monotonic scheduling

Это система планирования, при которой частота запуска задачи (период работы) определяется ее приоритетом. Период работы до переключения обрано пропорционален приоритету задачи (1/T_i). Отношение максимальной продолжительности исполнения задания C_i = max{c_i,j} к величине периода (T_i), дает оценку загруженности процессора. Система планирования дает хороший результат, если общая загруженность не превышает 69% (в литературе пишут). RMS планирование предоставляет каждой задаче время работы задания порядка C/T.

Deadline-monotonic scheduling
Период работы до переключения обрано пропорционален дедлайну задачи, оценке времени завершения.

Earliest Deadline First (EDF)
-- алгоритм планирования на основе оценки времени завершения задания. Задания в очереди готовых к исполнению заданий сортируются по времени завершения. Система планирования EDF дает хороший результат в высоко нагруженных системах, если общая загруженность достигает 100% (в литературе так пишут).

Атрибутами задачи является периодичность запуска, предоставляемый временной интервал для работы (initial_budget) и deadline - время завершения. В нашей терминологии, временной интервал в пределах периода - бюджет, который начисляется с периодом, а deadline - расчетная величина, используется для сортировки очереди заданий.

Mixed-Criticality real-time systems

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

Hierarchical Scheduling

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

Алгоритмы

FIFO - очередь процессов. Готовые к исполнению процессы перебираются по порядку из очереди, без нарушения порядка следования. Процесс может ожидать события или быть готовым к запуcку, так что представляем две очереди: процессы, которые ждут, и процессы готовые к исполнению. Процессы готовые к исполнению перебираются последовательно. В RTOS необходимо использовать вытесняющую многозадачность и обеспечить работу всех процессов. В сочетании с методом FIFO можно использовать кооперативную многозадачность. Расширением является планирование на основе приоритетов, нескольких очередей.

Round-Robin (RR) -- метод планирования с фиксированным интервалом переключения. На работу каждого процесса выделяется некоторое время, после чего происходит переключение на другой процесс. Метод позволяет избежать захвата процессора одной задачей. Совмещение метода RR с паланированием на основе приоритетов (PS) дает требование на динамическое или статическое изменение размера интервала в зависимости от приоритета задачи.

В POSIX используется похожая терминология для настройки политик планирования, режимов работы планировщика. Политика SCHED_FIFO - запрещает переключение задачи, SCHED_RR разрешает переключение задачи по времени, ограничивая интервал процессорного времени.

Можно получить хороший результат, если планирование выполняется методом RR. Когда я смотрю код контроллера - вижу, что метод RR - оптимальный выбор, сочетающий простоту и эффективность. Дело в том, что в RTOS не сильно загруженной, большая часть операций происходит асинхронно, каждая операция, которая требует отслеживания готовности или флага события не вызывает продолжительную загрузку CPU. Обработка событий выполняется в планировщике или по прерыванию, такми образом практически не реализуется необходимость принудительного переключения задач. Управление передается добровольно и возвращается по событию. Такое поведение характерно для систем с низкой нагруженностью. Однако можно представить некоторую ситуацию, когда отдельные процессы вызывают болшую загрузку CPU, например обработка графики или обработка сетевого трафика.

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

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

Например, мы упрвляем двигателем, задача управления запускается 40 тыс раз в секунду, и джиттер должен быть микросекунда. Вот такая задача запускается в режиме реалтайм, как таймерная задача, периодически. Представим, что двигателей (задач) штук пять и все они работают с такими требованиями. Наше решение - разнести по времени фазы запуска задач, и сохранить общий период, каждой задаче выделить свое временное окно и стараться минимизировать джиттер.

Параметры запуска будут включать приод, требование на джиттер, фазу и опцию фазовой подстройки частоты запуска задачи. При этом все эти задачи должны быть с высоким приоритетом, не прерываться, обладать свойством кооперативная многозадачность, добровольно передавать управление. Остальные задачи в системе должны выполняться в фоне, когда процессор не занят обработкой задач с требованием hard real-time.

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

Для RTOS НУЖЕН Планировщик, который обеспечивает такое планирование на периодических процессах. И в тоже время хорошо работает на не пероидических задачах.

Попробую описать модель. Определяем очередь событий таймера, в которую добавляются треды с задержкой запуска, указанной с точностью до микросекунды. Эта очередь анализируется периодически по таймеру. Сортировка в очереди соответсвует понятию EDF. По таймеру, при наступлении расчетного времени запуска задача ставится на исполнение и прерывает текущую задачу (preempt). Запишем так:

// тред прерывает работу исполнения треда
    // в зависимости от приоритета расчитывается прибавка к бюджету
    thread->budget += BUDGET(thread->priority)
    // бюджет не должен превышать установленный лимит
    if (thread->budget > thread->init_budget)
        thread->budget = thread->init_budget;
    // если процесс не активен, добавляем его в начало очереди
    thread->priority= thread->sched.priority;
    sched_head(thread, thread->priority);

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

if (running_thread->preempt) {
    running_thread->budget -= execution_time;
    sched_head(running_thread, running_thread->priority);
    __YIELD();
} else
if (running_thread->budget <= execution_time) {
  	running_thread->budget -= execution_time;
    running_thread->priority= running_thread->sched.low_priority;
  	running_thread->budget += BUDGET(running_thread->priority);
    sched_tail(running_thread, running_thread->priority);
    __YIELD();
}

В системе необходимо поддержать CPU_clock() - измерение штампа времени с точностью до такта процессора или такта системного таймера, из которого вычисляется execution_time до переключения.

Инициализация процесса происходит с атрибутами: sched_priority, sched_ss_low_priority, sched_ss_initial_budget. Можно немного доработать алгоритм и вычислять прибавку в бюджет BUDGET() на основе измеренного времени работы, thread->execution_time - время работы процесса до перехода в режим ожидания.

Aperiodic Task Scheduling

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

Апериодические сервисы называют Sporadic Server. Таким образом работу нашего планировщика можно описывать политикой SCHED_SPORADIC с набором атрибутов планирования. Такой сервис выполняется какое-то время (бюджетное, Q) с высоким приоритетом, затем приоритет занижается и разрешается прерывать задачу по времени, если она сама не отдала управление. Процесс ждет событие, затем выполняет некоторую работу в течение определенного времени (назовем бюджет) и уходит в ожидание. Если задача не ушла в ожидание, ей занижают приоритет. Измеренное время работы может использоваться для планирования и вычисления бюджета.

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

Background Service

Это механизм запука апериодических задач в фоновом режиме, в режиме FIFO. В одной системе мы можем использовать несколько планировщиков. Мы можем выделить некоторый квант времени на работу фоновых процессов, к которым не предъявляются особые требования и не применяется PS планирование на основе приоритетов. В нашей системе к таким сервисам отностится сбор мусора и терминал вывода отладочной информации.

Этим же термином мы можем определить две очереди в планировщике: background, foreground. Очередь background обрабатывается с низким приоритетом, в своем временном интервале и может прерываться процессами из очереди foreground. Если задача выполняется слишком долго, можно ее автоматически перекинуть в из очереди foreground в очередь background.

Polling Server (PS)

Апериодические процессы, к которым не предъявляются требования к синхронности обработки могут запускаться по опросу готовности. Мы поддерживаем некоторый механизм запуска задач (Сервисов) по событиям с периодическим опросом состояния. По сути у нас в системе есть еще один планировщик. Если бы нам удалось определить такие задачи через определение политики планировщика, их можно было бы запускать с использованием pthread или определить, как событие, как struct sigevent, подобно тому как запускаются таймерные задачи, но с запуском процесса по событию. PS работает в фоновом режиме. Теоретически реализация PS может быть представлена, как периодический запуск планировщика со своей очередью. Отличие сервиса от обычного треда: при выходе из функции подобно таймеру, сервис снова ставится в очередь ожидания обработки.

Deferrable Server (DS)

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

Sporadic Server (SS)

Политика SCHED_SPORADIC d POSIX.1-2017 задает набор параметров:
sched_priority -- начальный приоритет исполнения
sched_ss_max_repl -- ограничение на число операций начислений в бюджет
sched_ss_low_priority, -- низкий приоритет
sched_ss_repl_period, -- задержка перед активацией начисления
sched_ss_initial_budget -- максимальное время работы без переключения

Количество необработанных запросов (replenishment operation) на пополнение бюджета ограничено величиной sched_ss_max_repl. Превышение этого ограничения ведет к снижению приоритета. Если задача в данный момент не активна или сигнал не может быть доставлен, сигнал ставится в очередь с высоким приоритетом и параметром activation_time + sched_ss_repl_period, чтобы обработка произошла в течение заданного интервала времени, затем увеличиваем счетчик запросов thread->pending.

Величина прибавки в бюджет replenish_amount может вычисляться исходя из того сколько времени было потрачено на выполнение операции в прошлый раз и не может првышать изначальный бюджет sched_ss_initial_budget.

Политика SCHED_FIFO позволяет устанавливать приоритет в интервале pthread_setschedprio(). В определении политики SCHED_RR бюджет фиксирован и обозначается параметром Round-Robin Interval. Стандарт POSIX определяет политку SCHED_SPORADIC, которую мы используем под свои нужды, или определяем некотороую нестандартную политику SCHED_DEADLINE, обеспечивающую обработку событий в заданный интервал времени. Политика SCHED_OTHER ничего не определяет точно, под ней можно скрыть нормальный режим работы планировщика с любым количеством параметров. POSIX дает характеристики политикам планировщика [POSIX: 2.8.4 Process Scheduling]:

SCHED_FIFO

Threads scheduled under this policy are chosen from a thread list that is ordered by the time its threads have been on the list without being executed; generally, the head of the list is the thread that has been on the list the longest time, and the tail is the thread that has been on the list the shortest time

SCHED_RR

This policy shall be identical to the SCHED_FIFO policy with the additional condition that when the implementation detects that a running thread has been executing as a running thread for a time period of the length returned by the sched_rr_get_interval( ) function or longer, the thread shall become the tail of its thread list and the head of that thread list shall be removed and made a running thread.

SCHED_SPORADIC

The sporadic server policy is based primarily on two time parameters: the replenishment period and the available execution capacity. The replenishment period is given by the sched_ss_repl_period member of the sched_param structure. The available execution capacity is initialized to the value given by the sched_ss_init_budget member of the same parameter. The sporadic server policy is identical to the SCHED_FIFO policy with some additional conditions that cause the thread’s assigned priority to be switched between the values specified by the sched_priority and sched_ss_low_priority members of the sched_param structure.

POSIX Определяет группы опций и функций, из которых формируется понятие Real-Time. C этого ракурса Real-Time определяется возможностью настройки параметров планировщика из кода программы, возможностями диагностикии измерения временных параметров задач, наборами функций для синхронизации задач. За каждым термином кроется некоторый функционал ядра и режимы планирования.

Real-time

asynchronous, synchronized and prioritized I/O, shared memory objects, process and range based memory locking, semaphores, timers, real-time signals, message passing, process scheduling;

Advanced Real-time

clock selection, process CPU-time clocks, monotonic clock, timeouts, typed memory objects;

Real-time Threads

thread priority inheritance and protection, thread scheduling;

Advanced Real-time Threads

thread CPU-time clocks, thread sporadic server, spin locks and barriers.

Использованные здесь термины применяются в виде опеределений в заголовке <unistd.h>, который и определяет функционал ядра RTOS.

Я представляю себе меню выбора, конфигурацию ядра, мы могли бы определить ряд параметров конфигурации, которые влияют на поддержку опций и выбор способов планирования в ядре RTOS.

1. Mixed-Criticality/Иерархическое планирование - возможность разделения процессов на группы. Можно предложить выделить группы: hard real-time, soft real-time, background service.
2. RMS, EDF или RR -- методы планирования, методы выделения бюджета задаче. При этом в одном планировщике методы планирования могут сочетаться и применяться индивидуально к каждому процессу. RR рассматриваем, как частный случай при котором бюджет задания фиксирован.
3. Динамическое управление производительностью системы исходя из оценки загруженности системы.
4. Поддержка Deferable Server/Sporadic Server, сетевые интерфейсы (дарйверы) с ограниченной пропускной способностью. Предполагает поддержку очереди событий. О дин из видов события - начисление бюджета и повышение приоритета.
5. Поддержка Polling Server.

В настоящее время в нашей RTOS системе реализуется Mixed-Criticality с двумя группами на основе приоритета. hard real-time периодические процессы не могут прерываться по времени, по истечении бюджета задание переключается и переходит в группу с меньшим приоритетом, soft real-time -- использует RR - метод планирования с фиксированным интервалом переключения заданий. Экспериментально реализован метод планирования с выделением интервала переключения задач динамически на основе приоритета. Экспериментально поддержан механизм занижения приоритета по истечении бюджета. Поддержан механизм Deferred/Sporadic Service Экспериментально поддерживается EDF метод планирования. Политика EDF Реализуется с подменой FIFO очереди заданий на очередь с приоритетами. Задания могут исполняться в фоновом режиме background service (FIFO, Cooperative Miltitask), и в режиме опроса готовности (Polling services, FIFO, Cooperative), при этом весь поток background service участвует в процессе планирования, как единый процесс со своим приоритетом. Такое сочетание выведено опытным путем и применяется в условиях низкой загруженности системы. Динамическое управление производительностью выражено циклом WFE -- ожидание события в фоновом процессе. Поддержка сервисов в ядре задается через определения #define osFeature_* в конфигурационном файле системы <board.h>, <cmsis_os.h>(поддержка системных интерфейсов CMSIS RTOS) и набором опций _POSIX_* в файле <unistd.h>, который классифицирует поддержку системных интерфейсов POSIX.