Миро Самек, Роберт Вард

Построение наипростейшего диспетчера задач (перевод)

7/12/2006 11:26 AM EDT

Перевод teap0t<caxapa.ru> v1.000 17-Jul-2013
 

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

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

В данной статье будет показано как скрестить эпизодический характер работы типичной встраиваемой системы с ядром или диспетчером, функционирующим в режиме "выполнение-до-завершения" (run-to-com-pletion - RTC). Такая конструкция получается простой, компактной и быстрой. На самом деле здесь будет показано как создать ядро операционной системы реального времени с вытесняющей многозадачностью, приоритизацией и предсказуемым поведением, используя всего несколько десятков строк на языке Си. Авторское название - наипростейший диспетчер задач (Super Simple Tasker - SST) [2].

Подобный тип ядра не нов - он широко используется в промышленности, а вот в печати освещается редко. Авторы надеются, что для всех интересующихся вопросом данная статья послужит удобным источником сведений об устройстве простейших диспетчеров задач. Что ещё важнее, эта публикация разъяснит почему простые операционные системы, работающие в режиме "выполнение-до-завершения", очень хорошо подходят для создания сред исполнения, которые строятся на идеях машин состояния и схемах переходов UML-подобных языков. Именно идеология "выполнение -до-завершения", лежащая в основе конечных автоматов, делает естественным использование для их реализации ядра, которое предполагает использование именно такой модели работы.

Описание начнётся с пояснения особенностей работы наипростейшего диспетчера задач (SST) и ответа на вопрос, почему ему нужен только один стек для всех задач и прерываний. Затем будут рассмотрены отличия от обычных ядер операционных систем реального времени, которые позволят ещё раз обсудить основные принципы построения таких систем. Далее описывается минимальная реализация SST с использованием ANSI C и её воплощение в исполняемом примере, который можно запустить на любой x86-совместимой машине. Завершится дискуссия рассмотрением комбинации из одностекового ядра и средств работы с конечными автоматами. Обе составные части имеют открытые исходные тексты и вместе образуют среду исполнения с предсказуемыми характеристиками для машин состояний, создаваемых на языке UML. Предполагается, что читатель знаком с базовыми принципами пострения систем реального времени: обработкой прерываний, переключением контекста, взаимными исключениями и блокировкой, очередями событий и конечными автоматами.

Вытесняющая многозадачность с единым стеком

Общеупотребительные операционные системы реального времени создают достаточно сложную рабочую среду (включающую раздельные области стеков) для каждого запущенного процесса и объясняются в отличной книге Jean Labrosse "MicroC/OS-II: The Real-Time Kernel" [3]. Сохранение всех деталей такого контекста и процедура его переключения требует множества служебных операций. Описываемое в этой статье ядро устроено чрезвычайно просто, так как ему не нужно работать со множеством стеков и выполнять связанные с ними манипуляции.

Выставив требование по работе всех задач в режиме "выполнение-до- -завершения" и диспетчеризацией с фиксированными приоритетами можно добиться того, чтобы обрабатывать всю контекстную информацию, используя только стандартные средства работы со стеком. Каждый раз, когда задача с более высоким приоритетом перехватывает прерывание, диспетчер SST использует обычную Си-функцию для построения рабочего окружения задачи в стеке поверх контекста процесса, отдающего управление. Каждый раз, когда управление перехватывает прерывание, диспетчер SST вновь использует обычную Си-функцию для того, чтобы построить рабочую область поверх уже существующего кадра [* он создан аппаратно в качестве первой реакции на прерывание]. Столь незамысловатый метод управления контекстом задач вполне соответствует поставленным целям, так как нам известно, что любой процесс, как и любое прерывание, выполняется до завершения, то есть контекст процесса более низкого приоритета не потребуется до тех пор, пока перехватившая управление задача (и, возможно, код ещё более высокого приоритета) не завершит свою работу. В этот момент контекст передавшей управление задачи естественным образом оказывается на вершине стека готовый к продолжению работы.

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

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

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

Приоритизация задач и прерываний в SST

Интересно отметить, что большинство приоритетных контроллеров прерываний (например, 8259A, входящий в состав x86-совместимых компьютеров, AIC ARM-процессорах фирмы Atmel, VIC в LPC2xxx от Philips, контроллер прерываний в M16C от Renesas и многие другие) аппаратно реализует точно такую же, как описанная выше, схему асинхронной диспетчеризации прерываний. А именно: любой приоритетный контроллер допускает перехват управления у активного в данный момент прерывания только для события более высокого приоритета. Все прерывания отрабатывают до завершения и все используют один стек.

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

Рисунок 1. Схема приоритизации в SST