Выбор алгоритма планирования в Rtos: балансирование теории с применением

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

Понимание операционных систем в реальном времени и основы планирования

Операционные системы реального времени являются событийно-управляемыми и превентивными, то есть ОС может контролировать соответствующий приоритет конкурирующих задач и вносить изменения в приоритет задачи. Ключевой характеристикой RTOS является уровень его согласованности относительно количества времени, необходимого для принятия и выполнения задачи приложения; изменчивость «дрожит». Эта согласованность отличает RTOS от операционных систем общего назначения, которые отдают приоритет пропускной способности над гарантиями времени.

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

Жесткие системы реального времени против мягких систем реального времени

RTOS, которая обычно или обычно может соответствовать сроку, является мягкой ОС в реальном времени, но если она может соответствовать сроку детерминировано, это жесткая ОС в реальном времени. Это различие фундаментально влияет на выбор алгоритма планирования. Hard RTOS используются в чувствительных ко времени приложениях, таких как управление движением, антиблокировочное торможение или датчики самолета, выполнение задач в запланированные сроки. Несоблюдение определенных ограничений приводит к сбою системы, а иногда и катастрофическим последствиям.

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

Классификация алгоритмов планирования

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

Превентивный против непревентивного планирования

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

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

Статический vs. динамический приоритет

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

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

Монотонное планирование (RMS): Статический стандарт приоритета

Rate-monotonic scheduling (RMS) — алгоритм приоритетного назначения, используемый в операционных системах реального времени (RTOS) с классом статично-приоритетного планирования, где статичные приоритеты назначаются в соответствии с продолжительностью цикла работы, поэтому более короткая продолжительность цикла приводит к более высокому приоритету работы. RMS стал одним из наиболее широко изученных и реализованных алгоритмов планирования для периодических задач в реальном времени.

Основные принципы RMS

Алгоритм планирования Rate Monotonic — это простое правило, которое присваивает приоритеты различным задачам в соответствии с их периодом времени, при этом задача с наименьшим периодом времени имеет наивысший приоритет, а задача с самым длинным периодом времени имеет наименьший приоритет для выполнения.Поскольку период времени задачи не изменяется, его приоритет не меняется с течением времени, что делает Rate Monotonic фиксированным алгоритмом приоритета.

Алгоритм монотонного планирования с высокой скоростью работает по принципу превенции, где превенция происходит на заданном процессоре, когда более высокая приоритетная задача блокирует более низкую приоритетную задачу от выполнения. Если запущен процесс с более низкой приоритетностью и становится доступным для запуска процесс с более высокой приоритетностью, он будет превентивным процессом с более низкой приоритетностью. Это гарантирует, что задачи, требующие более частого выполнения, получают процессорное время, когда это необходимо.

Анализ графиков и границы использования

Liu & Layland (1973) доказал, что для набора n периодических задач с уникальными периодами существует осуществимый график, который всегда будет соответствовать срокам, если использование процессора ниже определенной границы (в зависимости от количества задач). Набор n независимых периодических задач, запланированных RMS, всегда будет соответствовать своим срокам для всех этапов задач, если общая загрузка меньше, чем граница (n(2^{1/n} - 1)).

В особом случае, когда все периоды выполнения задач гармоничны, граница использования равна 1,0, что позволяет 100% пропускную способность процессора при соблюдении всех сроков, хотя эта граница является приближением к худшему случаю; для случайно выбранных наборов задач вероятная верхняя граница составляет около 88%. Эта теоретическая основа предоставляет инженерам математические инструменты для проверки планируемости перед развертыванием.

Оптимальные и практические соображения

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

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

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

Ограничения тарифного монотонного планирования

Наиболее ранний срок (EDF): динамическое планирование приоритетов

Наиболее важным (и проанализированным) алгоритмом динамического приоритета является Earliest Deadline First (EDF). Приоритет работы (инстанции) обратно пропорционален ее абсолютному сроку, то есть наиболее приоритетной работой является та, которая имеет самый ранний срок. В отличие от RMS, EDF динамически корректирует приоритеты задач на основе их текущих сроков, а не фиксированных периодов.

Как работает EDF

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

RMS (и планирование с фиксированным приоритетом в целом) не является оптимальным по сравнению с алгоритмами с динамическим приоритетом, такими как самый ранний крайний срок (EDF), который может достичь до 100% использования процессора при гарантировании сроков, в то время как методы с фиксированным приоритетом по своей сути ограничены.

Преимущества EDF

Недостатки EDF

Сравнение RMS и EDF

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

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

Другие алгоритмы общего планирования в RTOS

В настоящее время наиболее используемыми алгоритмами в практическом РОС являются неупреждающее планирование, круглое планирование и упреждающее планирование приоритетов. Помимо RMS и EDF, несколько других подходов к планированию служат конкретным случаям использования и системным требованиям.

Первый первый подан (FCFS)

FCFS - это неупреждающий алгоритм планирования, который не имеет уровней приоритета, назначенных задачам, где задача, которая сначала попадает в очередь планирования (т.е. входит в готовое состояние), сначала вводится в запущенное состояние и начинает использовать процессор. FIFO - самый простой планировщик, поскольку все, что ему требуется, - это очень простой алгоритм очереди, не требующий ввода от пользователя (например, назначение приоритетов, оценка времени выполнения или периода задач), поскольку все обрабатывается RTOS.

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

Круглый Робин Спланирование

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

Round Robin имеет преимущество простоты понимания и почти такой же простоты реализации, с преимуществом «справедливости», поскольку все задачи получат равную долю процессора, и ни одна задача не может зацепить процессор. Эта справедливость чрезвычайно полезна для типичной многопользовательской системы (например, сервера Linux), но гораздо менее актуальна для ОС реального времени. Round robin не имеет предельной осведомленности, необходимой для жестких систем реального времени, но может быть полезна для мягких приложений реального времени, требующих справедливости.

Приоритетное превентивное планирование

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

Расписание временных игровых автоматов (ARINC 653)

Расписание временных слотов аналогично ARINC 653, где настроено несколько временных слотов и каждая задача назначается временному слоту в концентрической петле. Задачи должны выполняться в пределах назначенных им временных слотов или ждать следующего слота, который назначен для этой задачи. Такой подход обеспечивает сильную временную изоляцию между задачами, что делает его популярным в критически важных для безопасности аэрокосмических и автомобильных приложениях.

Least Laxity First (Меньшая слабость)

Least Slack Time (LST) — это динамический алгоритм планирования, основанный на приоритете, используемый в системах реального времени, где всем задачам в системе присваивается некоторый приоритет в соответствии с их временем слакса, причем задача, которая имеет наименьшее время слакса, имеет самый высокий приоритет и наоборот. Лаксити (или время слакса) представляет, сколько времени остается до крайнего срока после учета оставшегося времени выполнения. Этот алгоритм может обеспечить оптимальное планирование, но требует частого перерасчета приоритета.

Критические факторы, влияющие на выбор алгоритма планирования

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

Характеристики задач и временные ограничения

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

Система управления в реальном времени состоит из множества одновременных периодических задач, имеющих индивидуальные временные ограничения, включая время выпуска (ri), время исполнения (Ci), период (ti) и крайний срок (Di) для каждой отдельной задачи (Ti).

Системная предсказуемость и детерминизм

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

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

Требования к использованию процессора

Коэффициент использования процессора говорит о нагрузке процессора на один процессор, где U=1 означает 100% использование процессора. Для набора задач n периодического использования процессора больше, чем один, тогда этот набор задач не будет планироваться никаким алгоритмом. Системы, работающие вблизи максимального использования, могут потребовать EDF или другие динамические алгоритмы, в то время как системы с умеренным использованием могут извлечь выгоду из простоты RMS.

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

Сложность реализации и накладные расходы

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

Большинство высокопроизводительных встроенных систем не нуждаются в дорогостоящей и полнофункциональной операционной системе реального времени (RTOS), поскольку выделенный планировщик, такой как те, которые используются в арбитражных процессах и управлении трафиком, является достаточным, чрезвычайно эффективным и имеет низкий объем памяти, особенно предпочтительно, когда размер памяти ограничен и сроки должны строго соблюдаться.

Обмен ресурсами и синхронизация

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

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

Инверсия приоритета: критический вызов

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

Понимание приоритетной инверсии

Интервалы неупреждаемости и прерываний являются источниками инверсии приоритета, и когда более приоритетная задача не позволяет упреждать более низкую приоритетную задачу, выполнение более приоритетной задачи задерживается из-за выполнения более низкой приоритетной задачи.Это явление может привести к тому, что приоритетные задачи пропустят сроки, даже когда система, по-видимому, обладает достаточной емкостью.

Классический пример инверсии приоритета произошёл в миссии Mars Pathfinder, где низкоприоритетная метеорологическая задача, держащая общий ресурс, блокировала высокоприоритетную коммуникационную задачу, вызывая сброс системы.Пример использования базового приоритетного наследования связан с «жуком сброса Марс-Патфайндера», который был зафиксирован на Марсе путём изменения флагов создания семафора, чтобы включить приоритетное наследование.

Протокол о приоритетном наследовании

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

Для смягчения инверсии приоритетов в RTOS обычно реализуются протоколы приоритетного наследования или протоколы потолочного приоритета. Многие коммерческие RTOS, такие как VxWorks, VRTX и DSP RTOS, такие как DSP/BIOS, реализуют RMS с протоколами приоритетного наследования или потолочного приоритета для ограничения блокировки ресурсов и инверсии приоритета. Эти протоколы обеспечивают ограниченное время блокировки, что позволяет более точно анализировать планирование.

Протокол приоритетного потолка

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

Практические соображения по осуществлению

Как правильно выбрать планировщик в начале проекта, когда программное обеспечение не готово и у нас есть только спецификация руководства аппаратного обеспечения? Существует множество подходов, таких как анализ скорости монотонного (RMA), анализ времени выполнения в худшем случае и анализ моделирования производительности на системном уровне. Для преодоления разрыва между теорией и практикой требуются систематические подходы к выбору и валидации алгоритма.

Аппаратные платформы ограничения

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

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

Прерывное управление и интеграция ISR

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

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

Контекстный переключатель Overhead

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

Частые коммутаторы контекста могут значительно снизить эффективное использование процессора. Алгоритмы динамического приоритета, такие как EDF, могут запускать больше коммутаторов контекста, чем статические подходы, такие как RMS. Фактические накладные расходы зависят от архитектуры процессора, реализации RTOS и характеристик задачи. Измерение и учет времени коммутатора контекста имеет важное значение для точного анализа планирования.

Тестирование и валидация на предмет соответствия графику

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

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

Моделирование системы и моделирование

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

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

Соображения по составлению расписания с учетом конкретных условий применения

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

Автомобильные системы

Разделенная RMS особенно подходит для встраиваемых систем с ограниченными ресурсами, таких как автомобильные электронные блоки управления (ECU), где предсказуемость и минимальные накладные расходы имеют решающее значение для сертифицированных по безопасности приложений, таких как управление двигателем и передовые системы помощи водителю. Автомобильные системы обычно имеют многочисленные ECU, обменивающиеся данными по сетям, таким как CAN или FlexRay, с задачами, начиная от управления двигателем (жесткий в режиме реального времени) до информационно-развлекательных (мягкий в режиме реального времени).

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

Аэрокосмическая и авионика

Аэрокосмические приложения требуют высочайшего уровня надежности и сертификации. Стандартный монотонный подход обеспечивает теоретическую основу при разработке поддержки планирования в режиме реального времени для IEEE Futurebus +, которая широко одобрена промышленностью, включая сообщества VME и MultiBUS, а также является стандартом, принятым ВМС США, причем стандартный монотонный подход является рекомендуемым подходом в руководстве по конфигурации системы Futurebus + (IEEE 896.3).

ARINC 653 определяет разделение графиков для интегрированной модульной авионики, обеспечивая пространственную и временную изоляцию между приложениями. Этот подход позволяет нескольким приложениям с различными уровнями критичности сосуществовать на совместно используемом оборудовании при сохранении сертификации безопасности. Разделение времени и пространства предотвращает неисправности в одном разделе от воздействия на другие, что необходимо для критически важной для безопасности авионики.

Промышленный контроль и автоматизация

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

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

Медицинские приборы

В таких секторах, как аэронавтика или медицинские устройства, где точность и скорость необходимы, жесткая RTOS обеспечивает быструю обработку данных и обработку. Медицинские устройства варьируются от имплантируемых кардиостимуляторов с экстремальными требованиями к надежности до диагностического оборудования со сложными потребностями обработки сигналов. Нормативные требования от агентств, таких как FDA, требуют строгой проверки и проверки поведения в режиме реального времени.

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

Потребительская электроника и IoT

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

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

Расширенные темы планирования

Многопроцессорное и многоядерное планирование

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

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

Обработка апериодических и спорадических задач

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

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

Смешанные системы критики

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

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

Энерго-ориентированное планирование

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

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

Выбор правильного RTOS и Scheduler

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

Коммерческий vs. Open Source RTOS

Коммерческие предложения RTOS обычно обеспечивают профессиональную поддержку, обширную документацию и артефакты сертификации для критически важных приложений. Такие продукты, как VxWorks, QNX и ThreadX, имеют проверенные послужной список в требовательных приложениях. ThreadX предоставляет расширенные функции, такие как превентивное планирование порога, цепочка событий и анализ исполнения, а также архитектуру пико-ядра и всеобъемлющие показатели производительности, что делает его небольшим, быстрым и эффективным RTOS, который обеспечивает надежную и предсказуемую среду для запуска приложений в режиме реального времени, что делает его надежным выбором в таких отраслях, как автомобильная, аэрокосмическая и потребительская электроника.

Альтернативы с открытым исходным кодом, такие как FreeRTOS, Zephyr и RTEMS, предлагают гибкость и преимущества по стоимости. RTEMS - это операционная система с открытым исходным кодом в реальном времени, содержащая рабочий модуль с высокой ставкой. RTOS с открытым исходным кодом может быть настроена для конкретных потребностей и выгод от вклада сообщества, хотя профессиональная поддержка может потребовать коммерческих договоренностей.

Оценка особенностей планирования

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

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

Насколько настраиваемым является планировщик? Понимание этих возможностей помогает сопоставить функции RTOS с требованиями приложений.

Инструмент поддержки и развития окружающей среды

Эффективная разработка RTOS требует надежных инструментов для отладки, профилирования и анализа. Отладчики с ядром обеспечивают видимость состояний задач, приоритетов и использования ресурсов. Инструменты отслеживания выполнения фиксируют поведение времени для анализа и оптимизации. Инструменты анализа предсказуемости автоматизируют проверку требований времени.

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

Лучшие практики для реализации алгоритмов планирования

Фазовые соображения проектирования

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

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

Руководящие принципы осуществления

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

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

Тестирование и валидация

Комплексное тестирование должно проверять как функциональную корректность, так и временнóе поведение. Единичное тестирование проверяет индивидуальную логику задач, а интеграционное тестирование проверяет взаимодействие задач и совместное использование ресурсов. Стресс-тестирование с максимальными условиями нагрузки выявляет маржу и выявляет потенциальные нарушения сроков.

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

Мониторинг и техническое обслуживание

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

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

Обычные подводные камни и как их избежать

Недооценка времени казни

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

Игнорирование приоритетной инверсии

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

Неадекватное тестирование

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

Пренебрежение эффектом прерывания

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

Чрезмерная инженерия

Выбор чрезмерно сложных алгоритмов планирования увеличивает время разработки и затраты на техническое обслуживание без соразмерных преимуществ. Выберите самый простой алгоритм, отвечающий требованиям. Эффективность RTOS во многом зависит от его алгоритма планирования, что делает его важным аспектом проектирования системы. Зарезервируйте сложные подходы для систем, действительно требующих своих возможностей.

Будущие тенденции в графике РТОС

Машинное обучение и интеграция ИИ

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

Неоднородные вычислительные платформы

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

Сетевые системы с чувствительностью ко времени

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

Адаптивные и самооптимизирующиеся системы

Будущее РТС может включать адаптивное планирование, которое адаптируется к изменяющимся условиям и рабочим нагрузкам. Машинное обучение может оптимизировать параметры планирования на основе наблюдаемого поведения. Системы самоконтроля могут обнаруживать аномалии времени и автоматически корректировать приоритеты или распределение ресурсов. Однако поддержание детерминизма и сертификации в адаптивных системах представляет значительные проблемы.

Вывод: достижение правильного баланса

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

Rate Monotonic Scheduling обеспечивает отличную основу для систем с периодическими задачами и умеренными требованиями к использованию, предлагая простоту, предсказуемость и проверенный промышленный послужной список. Earliest Deadline First обеспечивает более высокое использование для систем, выдвигающих ограничения по мощности, хотя и при повышенной сложности реализации. Другие алгоритмы служат специализированным потребностям, включая справедливость, разделение времени и поддержку смешанной критики.

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

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

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

Ключевые выводы для практикующих

Для дальнейшего изучения концепций планирования в реальном времени сообщество встроенных систем предоставляет обширные ресурсы и тематические исследования.Институт разработки программного обеспечения Университета Карнеги-Меллона предлагает комплексные исследования по монотонному анализу скорости.Документация FreeRTOS предоставляет практические рекомендации по внедрению, в то время какGeeksforGeeks предлагает доступные учебные пособия по алгоритмам планирования.Статья Википедии об операционных системах реального времени служит отличной отправной точкой для понимания фундаментальных концепций.