Миро Самек, Роберт Вард "Построение наипростейшего диспетчера задач" (перевод)


Запуск многозадачности и цикл ожидания (idle)

В листинге 7 приведён исходный текст функции "SST_run()", вызываемой из "main()", когда приложение передаёт управление ядру для запуска многозадачности.

Листинг 7. Запуск многозадачности в SST

    void SST_run(void) {
(1)     SST_start();                  /* start ISRs  */

(2)     SST_INT_LOCK();
(3)     SST_currPrio_ = (uint8_t)0;   /* set the priority for the SST idle loop */
(4)     SST_schedule_();              /* process all events produced so far */
(5)     SST_INT_UNLOCK();

(6)     for (;;) {                    /* the SST idle loop */
(7)         SST_onIdle();             /* invoke the on-idle callback */
        }
    }

				

"SST_run()" обращается к функции обратного вызова "SST_start()" (1), в которой инициализируются прерывания (см. "examples\bsp.c"). После запрещения прерываний (2) текущее значение приоритета через переменную "SST_currPrio_" снижается до уровня "0" (3), соответствующего приоритету цикла ожидания (начальный приоритет SST равен "0xFF"). После снижения приоритета вызывается диспетчер (4), чтобы обслужить события, могущие возникнуть на этапе инициализации системы. Наконец, разрешаются прерывания (5) и функция "SST_run()" переходит в цикл ожидания (6), который выполняется всё время, пока процессор не занят выполнением какой-либо задачи или обработчика прерывания. В цикле ожидания происходит вызов функции обратного вызова "SST_onIdle()" (7), которая может использоваться для перевода процессора в режим сохранения энергии.

Куда двигаться дальше

Минимальная конфигурация SST, представленная в статье, вполне работоспособна, несмотря на скромный размер в 421 байт кода, 256 байт таблиц поиска, нескольких байт оперативной памяти на каждую задачу (TCB и очередь событий) плюс память для стека. Возможно, это всё, что будет нужно в маленьких разработках, но при работе над большими системами проект неизбежно столкнётся с ограничениями. Опыт авторов говорит, что ограничения касаются в первую очередь не модели многозадачности, а окружения ядра: скромный размер параметров событий, примитивный механизм их передачи и отсутствие обработки ошибочных ситуаций.

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

И, наконец, наиважнейшее отличие SST. Принцип выполнения-до-завершения (run-to-completion - RTC), на основе которого создано столь простое ядро, отлично ложится на семантику исполнения, подразумеваемую формальным определением конечных автоматов и диаграмм состояний UML. SST и машины состояний созданы друг для друга. Пожалуй, можно утверждать даже, что если условия для работы нескольких работающих одновременно конечных автоматов создаются с помощью какой-либо операционной системы реального времени, то, возможно, это делается за счёт неоправданного перерасхода программной и оперативной памяти и чрезмерной нагрузки на процессор.

Модификация SST до состояния универсальной платформы для запуска программных проектов на основе конечных автоматов выходит за рамки данной публикации, но протестировать такую платформу с открытыми исходными текстами, созданную одним из авторов, читатель может самостоятельно. Все исходные тексты программ и примеров, а также документацию, можно найти по адресу www.state-machine.com.

Миро Самек - учредитель и руководитель Quantum Leaps, LLC, продвигающий свой набор программных средств для создания программного обеспечения для встраиваемых систем. Автор книги "Practical Statecharts in C/C++"(CMP Books, 2002) и множества журнальных публикаций, постоянный участник "the Embedded Systems Conference". Он будет рад пообщаться с вами [* по-английски] через почтовый ящик miro@quantum-leaps.com.

Роберт Вард в прошлом основатель "The C Users Journal". В данный момент главный проектировщик программного обеспечения фирмы Netopia, Inc, где он разрабатывает на основе языка Java серверы для командной сетевой работы. Доступен по адресу rward@codecraftsman.com.

Ссылки

0. Оригинальная публикация и страничка переводчика.

1. Selic, Bran. "The Challenges of Real-Time Software Design," /Embedded Systems Programming/, October 1996.

2. Ward, Robert. "Practical Real-Time Techniques" Proceedings of the Embedded Systems Conference, San Francisco, 2003.

3. Labrosse, Jean J. MicroC/OS-II: The Real Time Kernel. 2nd Edition CMP Books 2002.

4. Borland Developer Network, Antique Software: Turbo C++ version 1.01

5. Kalinsky, David. "Mutexes Prevent Priority Inversions," /Embedded Systems Programming/, August 1998.

"Избранные места из переписки с читателями"

------------------------------------------------------------------------

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

Может быть вы вкладываете в указанные термины какое-либо иное значение ?

- Mike O'Dell President Compass Rose Labs LLC Oakton, VA

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

------------------------------------------------------------------------

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

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

- Phil Ouellette Senior Engineer Mettler-Toledo, Inc. Worthington, OH

Роберт Вард: Именно поэтому мы предпочитаем совмещать SST с приложениями, создаваемыми в виде диаграммы состояний. Диаграмма состояний - способ выражения предыстории взаимоотношений между приложением и его окружением. SST - это всё, что нужно для работы с такими диаграммами. Диаграммы состояний - форма представления алгоритмов, отличающаяся от общепринятой, но более естественная (сходная по форме - изоморфная) для задач вида "воздействие / реакция". При каком из подходов получается "более простой" код, на мой взгляд, сильно зависит от вкусовых пристарастий.

------------------------------------------------------------------------

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

- Leon van Snippenberg Software Architect TA (Technical Automation) Atos Origin TA - IPS Den Bosch, The Netherlands

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

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

------------------------------------------------------------------------

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

- Douglas Schmidt Sr. Development Engineer Thermo Electron Inc. Minneapolis, MN

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

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

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

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

ПредпросмотрAttachmentSize
super_simple_tasker.zip293.38 КБ
sst_code.zip43.69 КБ