Статья
Версия для печати
Обсудить на форуме (3)
Многозадачность во встроенном приложении

© Dale, 26.11.2011 — 29.11.2011.

Часть 1

Оглавление


Введение

В статье «Hello World!» в embedded-исполнении мы познакомились с методикой создания надежных приложений для встроенных систем на основе микроконтроллеров. Впрочем, в качестве иллюстрации был взят примитивнейший пример, чтобы сложность решения задачи не отвлекала от освоения инструментов (как и положено программам уровня «Hello World!»). В результате спроектированная нами система выполняет простейшую задачу, которую мог бы решить даже посетитель школьного радиокружка при помощи обычного мультивибратора за несколько минут и при затратах на пару порядков меньше.
Дело тут даже не в том, что мы «выстрелили из пушки по воробьям». В конце концов, даже дорога в тысячу ли, как известно, начинается с одного шага. Самое плохое здесь — то, что все вычислительные ресурсы без остатка расходуются на одну-единственную задачу, как бы проста она ни была, и не позволяют делать что-либо еще. Даже если мы увеличим тактовую частоту нашего процессора в 10 или 100 раз, это ни на что не повлияет. Система получилась совершенно нерасширяемой: к ней невозможно добавить новые функции, поскольку ресурсов для их выполнения уже не остается.
Причина этой нерасширяемости лежит на поверхности: если мы посмотрим исходный код модуля Timer, который ответственен за формирования временных интервалов включения и выключения светодиодного индикатора, то увидим, что эти интервалы формируются процессором в пустом цикле. Зная тактовую частоту и время выполнения одного цикла, можно рассчитать, сколько таких циклов следует выполнить, чтобы обеспечить заданную задержку.
Напомню, что функция главного цикла приложения сейчас выглядит так:

Код: (C)
void Application_run(void)
{
    Led_on();
    Timer_wait(500);
    Led_off();
    Timer_wait(1500);
}

На что расходуются вычислительные ресурсы контроллера? Мы ранее уже выяснили, как выглядит машинный код функции Led_on():

Код:
0000009a <Led_on>:
  9a: a8 98       cbi 0x15, 0 ; 21
  9c: 08 95       ret

Инструкция cbi выполняется за 2 такта (это очевидно, т.к. требуется один такт, чтобы считать текущее состояние регистра на АЛУ, и еще один, чтобы записать результат с установленным битом обратно в регистр). Инструкция ret выполняется за 4 такта. Столько же тактов нужно, чтобы вызвать функцию. Итого выполнение Led_on() вместе с вызовом длится 10 тактов, что при тактовой частоте 16 МГц составляет 10/(16*106) = 0.625 мкс. Ровно столько же длится выполнение Led_off(), которая очень мало отличается от Led_on(). В сумме наш процессор за один цикл выполняет полезную работу в течение 1.25 мкс. Если учесть, что весь цикл длится 2 секунды, получаем КПД нашего устройства 0.0000625%. Прямо скажем, не очень высокий показатель.
Очевидно, что, чтобы иметь возможность заставить процессор выполнять больше полезной работы в течение цикла, следует разгрузить его от совершенно непродуктивного накручивания холостых циклов в качестве средства отмеривания временных интервалов. Для этой цели в состав микроконтроллеров разработчики включают таймеры, количество и функциональные возможности которых зависят от модели. В частности, в состав нашего прототипа входит микроконтроллер ATmega16, который оснащен одним 16-разрядным и двумя 8-разрядными программируемыми таймерами-счетчиками. Эти таймеры способны отмерять заданные интервалы параллельно с работой центрального процессора, давая ему возможность выполнять в это же время другую работу, и генерировать прерывания по истечении этого интервала, тем самым делая ненужным постоянный опрос текущего значения счетчика реального времени.
Использование таймера — лишь необходимое, но не достаточное условие распределения вычислительных ресурсов процессора между несколькими задачами. Нам потребуется также изменить саму концепцию работы приложения в многозадачном режиме. Те, кто использует настольные компьютеры, используют для этого многопоточность, когда внутри одного приложения создается несколько потоков выполнения для разбиения задачи на подзадачи; при корректном применении многопоточности создается иллюзия параллельного выполнения всех потоков одновременно, несмотря на наличие небольшого числа процессоров (иногда он даже один, хотя одноядерные процессоры на ПК уходят в историю). Создается эта иллюзия за счет того, что процессор достаточно часто переключается между потоками (говорят, что процессорное время разбивается на кванты), и хотя в каждый определенный момент каждый из процессоров способен выполнять лишь один поток, за определенный период каждый из потоков получит свою долю квантов (точнее, получит возможность мспользовать свою долю, что, строго говоря, не одно и то же).
Для микроконтроллеров тоже существуют операционные системы, причем их выбор не так уж мал (от самых простейших, с ядром в несколько килобайт и самыми скромными возможностями, до встраиваемых версий Linux). Впрочем, запросы даже самой скромной ОС реального времени могут оказаться не по зубам микроконтроллерам начального уровня. Но это не является непреодолимым препятствием для реализации многопоточности даже в этом случае. Существуют решения, способные работать в самых спартанских условиях. Именно их мы и рассмотрим в данной статье.
Поскольку самый лучший способ чему-то научиться — это решить какую-то практическую задачу, мы так и поступим. Сначала поставим задачу, которая не решается (или весьма неэффективно решается) теми средствами, которыми мы уже владеем, а затем попробуем ее решить, попутно осваивая новые средства.

Постановка задачи

Разработанные нами мигалки завоевали прекрасную репутацию на рынке мигалок благодаря качеству и стабильной работе, что вывело фирму General Blinkers на лидирующие позиции в этой отрасли. Недавно в коммерческую службу фирмы поступило заманчивое предложение от администрации одной из островных республик Тихоокеанского региона. Они выразили желание закупить партию сигнальных маячков на основе наших мигалок по заманчивым ценам. Однако для выполнения заказа конструкцию устройства придется переработать.
Заказчику необходимо, чтобы новое устройство генерировало не одну, а две независимые световые посылки:
  • прожектор, направленный на север, дает красные вспышки (0.5с длительность, 1.5с пауза;
  • прожектор, направленный на юг, дает зеленые вспышки (0.8с длительность, 1.3с пауза);
  • маячок включается с наступлением сумерек датчиком освещенности; включение в светлое время не допускается для экономии аккумуляторных батарей, заряжаемых днем солнечными панелями.
Менеджеры по сбыту, как обычно, уверили заказчика, что заказ будет выполнен в кратчайшие сроки, не удосужившись посоветоваться с разработчиками. На слабые протесты, что на нашей фирме пока еще нет опробованной в деле технологии разработки многопоточных предложения, они отвечают, что половина дела и так сделана (параметры северного прожектора случайно совпали с параметрами нашей серийной мигалки, и они, не вникая в детали, решили, что эту часть без доработок можно задействовать в новом проекте), и остается не так уж много. Тратить время на споры бесполезно, сроки и так поджимают.
Старший группы разработки принимает решение не ждать готовности прототипа, а начинать разработку на инструментальной системе немедленно, с последующим моделированием и переносом проекта на прототип по мере готовности последнего. В жестких временных рамках это единственная возможность не провалить проект.

Анализ задачи и вариантов решения

Для начала нарисуем эпюры выходных сигналов нашего устройства:

Рис. 1. Эпюры выходных сигналов.


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

Время
Интервал
Канал
Состояние
1
500
500
1
0
2
800
300
2
0
3
2000
1200
1
1
4
2100
100
2
1
5
2500
400
1
0
6
2900
400
2
0
7
4000
1100
1
1
8
4200
200
2
1

К сожалению, это совершенно нереализуемый вариант. Всего 4 с небольшим секунды работы устройства требуют таблицу длиной 8 строк, а наше устройство должно работать годы. Правда, через некоторое время таблица начнет повторяться (поскольку наименьшее общее кратное чисел 2000 и 2100 равно 42000), но на это все равно не стоит закладываться: во-первых, требования могут измениться, и период повторения таблицы может стать гораздо больше, а объем памяти микроконтроллера ATmega16 ограничен; во-вторых, может увеличиться число каналов устройства, либо разработчик вдруг вспомнит еще одну важную функцию, не включенную в первоначальную спецификацию, и таблица станет гораздо больше.
Можно, конечно, строить таблицу динамически: каждый раз, когда приходит срок очередного события, программа обработки прерывания спрашивает у обслуживаемого устройства, каким будет следующее событие и когда оно должно произойти. В этом случае достаточно будет таблицы с одной строчкой на каждый канал.
Работа программы в этом случае будет выглядеть примерно в таком духе:
  • Инициализация:
    • канал 1 переводится во включенное состояние;
    • канал 1 выставляет таймеру требование обслуживания через 500 мс с выключением;
    • канал 2 переводится во включенное состояние;
    • канал 2 выставляет таймеру требование обслуживания через 800 мс с выключением;
    • таймер выбирает требование обслуживания с минимальным интервалом (500 мс) и запускает отсчет этого интервала.
      № каналаИнтервалДействие
      1500Выкл
      2800Выкл
  • Через 500 мс происходит прерывание от таймера. Программа обработки прерывания:
    • уменьшает период всех требований на 500 мс:
      № каналаИнтервалДействие
      10Выкл
      2300Выкл
    • выполняет действие канала с истекшим (нулевым) периодом (в нашем случае — выключение канала 1);
    • процедура выключения канала 1:
      • переводит канал в выключенное состояние;
      • выставляет таймеру требование обслуживания через 1500 мс с включением:
        № каналаИнтервалДействие
        11500Вкл
        2300Выкл
    • таймер выбирает требование обслуживания с минимальным интервалом (300 мс) и запускает отсчет этого интервала.
  • Через 300 мс происходит прерывание от таймера. Программа обработки прерывания:
    • уменьшает период всех требований на 300 мс:
      № каналаИнтервалДействие
      11200Вкл
      20Выкл
    • выполняет действие канала с истекшим (нулевым) периодом (в этот раз — выключение канала 2);
    • процедура выключения канала 2:
      • переводит канал 2 в выключенное состояние;
      • выставляет таймеру требование обслуживания через 1300 мс с включением:
        № каналаИнтервалДействие
        11200Вкл
        21300Вкл
    • таймер выбирает требование обслуживания с минимальным интервалом (1200 мс) и запускает отсчет этого интервала.
  • И далее в том же духе.
Процедура получилась пусть и не слишком изящной, но, по крайней мере, ее поведение ничем не отличается от нашего табличного расписания; кроме того, размер таблицы событий ограничен количеством каналов одновременного отсчета времени. К тому же расширение процедуры на большее число каналов тривиально. Каждый раз при наступлении события оставшиеся интервалы во всех строках таблицы уменьшаются на истекший интервал, выполнятся требуемое действие, а затем выбирается минимальный интервал из оставшихся и используется для программирования таймера.
Впрочем, недостатки у такого подхода все же имеются. Первый из них не катастрофичен, но все же настораживает. Дело в том, что процедура обслуживания события явно устанавливает величину интервала ожидания следующего события по тому же каналу. Это значит, что мы не можем запустить отсчет следующего интервала до завершения текущей процедуры обслуживания события, поскольку еще не знаем, какой из интервалов минимален. Из этого следует, что очередной интервал удлиняется на время выполнения процедуры, а это снижает точность отсчета времени, особенно в случаях, когда обслуживание события длится долго.
Этот недостаток можно исправить, если не дожидаться завершения процедуры. В этом случае процедура в начале выполнения должна выставить новый запрос к таймеру и немедленно инициировать его обработку, а затем произвести остальные действия. Но тогда всплывает другая проблема: все процедуры обработки должны включать почти одинаковые фрагменты кода. Это не слишком сложно, но может вызвать проблемы при модификации кода, поскольку временные характеристики каждой подзадачи оказываются разбросанными по разным процедурам.
Второй недостаток гораздо существеннее. При таком подходе процедура обслуживания события выполняется в контексте обработчика прерывания, а это очень плохо. В некоторых случаях (вроде нашего примера) это может сойти с рук, поскольку процедура обслуживания события коротка и завершается быстро. Но в общем случае может возникнуть ситуация, когда до завершения обработки прерывания возникает еще одно прерывание, если оно не запрещено аппаратно. Поскольку у процедур обработки прерывания обычно проблемы с реентерабельностью, результат такой вложенности непредсказуем. Можно запретить повторные прерывания на время их обработки, но в этом случае есть риск их потерять, если они следуют достаточно часто. Оба варианта нежелательны.
В системах реального времени эту проблему обычно решают так: процедуру обработки прерывания делают максимально короткой; в ней выполняются лишь самые критические по времени действия, например, принимаются данные от быстрых устройств и заносятся в буфер, устанавливаются флаги наступления события и т.п. В дальнейшем эти данные, флаги и т.п. обрабатываются фоновыми потоками, которые делят оставшееся от оперативных потоков процессорное время.
Принимаем решение: на основе таймера реализуем часы реального времени, обновляемые по прерываниям; фоновые потоки, реализующие бизнес-логику приложения, самостоятельно отслеживают время и синхронизируют с ним свои действия. Такое решение представляется достаточно устойчивым и масштабируемым, но и у него есть свой недостаток: все это гораздо проще сказать, чем сделать. Нам нужен механизм параллельного выполнения фоновых потоков.

Способы распараллеливания вычислительных процессов

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

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

При вытесняющей многозадачности процессорное время делится на кванты, и эти кванты выделяются процессам. Каждый процесс вправе использовать свой квант, после чего планировщик прерывает его выполнение и предоставляет очередной квант следующему готовому к выполнению процессу, ожидающему своей очереди. Если процесс не может использовать свой квант полностью (например, процесс делает запрос ввода/вывода, который не может выполниться мгновенно), этот процесс тут же блокируется до завершения операции, а квант передается следующему в очереди процессу.
Главное достоинство вытесняющей многозадачности — гарантированное распределение процессорного времени. Даже если один из процессов зациклился и перестал реагировать на адресованные ему события, это не приведет к краху системы в целом: другие процессы по-прежнему будут получать и использовать собственные кванты процессорного времени.
Однако вытесняющая многозадачность — не панацея и имеет свои уязвимости. Прежде всего, зациклившийся процесс мог успеть захватить какой-либо ресурс общего доступа, и остальным придется ждать освобождения этого ресурса (вечно). Два по отдельности вполне корректных процесса могут угодить в так называемое «смертельное объятье», выйти из которого самостоятельно им вряд ли удастся. Квант времени может закончиться в любой момент, поэтому следует принимать особые предосторожности в части реализации «атомарных» операций, а также синхронизации взаимодействующих процессов.
Кроме того, сам механизм вытесняющей многозадачности достаточно сложен в реализации и ресурсоемок, и если ресурсы современных персональных компьютеров достаточны для его использования, то микроконтроллеры начального и даже среднего уровней обычно не могут позволить себе такую роскошь. Дело усугубляется еще и тем, что для каждого из параллельных процессов нужно сохранять контекст, который включает в себя мгновенный снимок состояния регистров процессора, а также отдельный для каждого процесса стек. Имея килобайт оперативной памяти, мы исчерпаем его целиком на контексты нескольких процессов и таблицы планировщика, и для работы уже ничего не останется. Переключение контекстов при смене процессов — также затратная процедура.
Приходим к выводу, что вытесняющая многозадачность — вещь в принципе хороша, но в данном конкретном случае она создаст больше проблем, чем решит.

Кооперативная многозадачность

Можно сказать, что кооперативная многозадачность строится на коммунистических идеалах и всеобщем альтруизме, воплощенных в машинном коде. Это проявляется в том, что каждый из процессов берет из «общего котла» процессорного времени ровно столько, сколько ему нужно (помните набивший оскомину древний лозунг «каждому по потребностям»?) и добровольно отказывается от излишков в пользу других процессов. Если операция длится долгое время, процесс разбивается на небольшие участки кода, и после выполнения такого участка процесс добровольно уступает очередь другим, а сам смиренно становится в конец очереди в надежде, что другие столь же альтруистично отнесутся к нему самому и передадут ему очередь при первой возможности.
Такая форма организации параллельности на практике оказываетсядовольно уязвимой, поскольку первый попавшийся «невоспитанный» процесс, нежелающий делиться с собратьями, способен полностью завесить всю систему в целом. Именно это происходило в 16-разрядных версиях ОС MS Windows 3.1 и 3.11 (for Workgroups), когда зависшее приложение зачастую можно было снять только нажатием на кнопку «Сброс». Поэтому использование кооперативной многозадачности требует жесткой дисциплины при проектировании каждого из параллельных процессов, в противном случае неприятности не заставят себя ждать. Впрочем, мы уже привыкли, что в мире программирования все имеет цену, поэтому искусство проектирования встроенных (и не только) систем определяется умением разработчика рассмотреть все альтернативы и выбрать правильный компромисс.
Плюсы кооперативной многозадачности: простота реализации, скромные требования к ресурсам (существуют реализации, требующие всего пару байт на процесс), сильное упрощение синхронизации взаимодействующих процессов.
О недостатках только что было сказано: один процесс способен полностью монополизировать процессор, нарушая работу всех остальных процессов.
В данном случае нам придется выбрать вариант кооперативной многозадачности, поскольку на вытесняющую у нас попросту не хватит ресурсов. Впрочем, слишком жестких требований к реальному времени в нашем проекте нет, а повышенные требования к качеству кода нас не испугают, поскольку мы вооружены методикой TDD.

Автоматная реализация устройства

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

Кратко о конечных автоматах
Конечный автомат можно представить как некую сущность, которая в каждый момент времени может пребывать в одном из состояний. Множество состояний задается при определении автомата, и оно является конечным (отсюда и название данного класса автоматов.
Находясь в некотором состоянии, автомат может реагировать на события (часто говорят, что он считывает символ из входного потока, что в принципе одно и то же). Под действием события (или прочитанного символа) автомат может перейти в другое состояние. Закон, по которому происходят эти переходы, называют функцией переходов данного автомата.
Для определенности принимают, что сначала автомат всегда находится в определенном состоянии — начальном, или стартовом.
Конечные автоматы часто применяются в качестве устройств распознавания формальных языков. В этом случае полезно оказывается задать множество заключительных состояний. Если, считав цепочку символов, автомат оказывается в одном из заключительных состояний, говорят, что данный автомат принимает данную цепочку (и, как следствие, цепочка принадлежит формальному языку, который распознает автомат). У нас несколько лругие цели, наши автоматы будут трудиться в бесконечномцикле, поэтому множество заключительных состояний в нашем случае пусто.
Подведем итог нашему блиц-обзору. Конечный автомат определяется набором следующих атрибутов:
  • множеством состояний (конечным);
  • начальным (стартовым) состоянием;
  • множеством заключительных состояний;
  • входным алфавитом (либо, если мы пользуемся понятием событий, то множеством событий);
  • функцией переходов.
Для наглядности конечные автоматы часто изображаются в виде характерных диаграмм, где состояния обозначаются кружками, а переходы — соединяющими их стрелками. Стрелки маркируют событиями, которые вызывают этот переход. Фактически такая диаграмма представляет собой ориентированный граф с выделенной начальной вершиной, перемещения по которому производятся в соответствии с последовательностью событий. Эта нотация настолько проста и выразительна, что «три товарища» включили ее в состав UML в слегка измененном виде.
Если переходов слишком много, диаграмма становится слишком перегруженной и запутанной и начинает напоминать воронье гнездо. В этом случае используют другую нотацию — таблицу переходов. Строки в этой таблице образуют состояния, а столбцы — события. В соответствующую ячейку вписывают новое состояние, в которое переходит автомат, находившийся в текущем состоянии при получении данного события.

Рис. 2. Диаграмма состояний красного канала.
Каждый из независимых каналов управления устройства может быть представлен своим конечным автоматом (который затем становится кандидатом на отдельный поток для выполнения на процессоре управляющего микроконтроллера). Выберем для начала «красный» канал и изобразим его диаграмму состояний на UML (рис. 2):
Автомат имеет три состояния:
  • INACTIVE (неактивное), в котором он пребывает в течение светового дня, когда подача световых сигналов запрещена;
  • LIGHT_OFF (пауза между вспышками);
  • LIGHT_ON (вспышка).
Закрашенный кружок обозначает начальное состояние, в котором автомат находится сразу после инициализации. Из него автомат переходит в состояние INACTIVE (верхний прямоугольник со скругленными углами) В нижней части прямоугольника обозначено действие, которое производится каждый раз при входе в это состояние, а именно выключение красного прожектора.
Автомат пребывает в состоянии INACTIVE в течение всего светового дня, пока не получит сигнал Night от датчика освещенности. Этот сигнал вызывает переход в новое состояние LIGHT_OFF. Переходы обозначены на диаграмме стрелками, соединяющими прежнее и новое состояния автомата, а надпись на стрелке указывает событие, которое инициировало этот переход.
При входе в состояние LIGHT_OFF гасится красный прожектор и запускается таймер на отсчет паузы между вспышками. Автомат остается в этом состоянии до тех пор, пока либо истечет период таймера (событие TimerElapsed), либо наступит день (событие Day).
При входе в состояние LIGHT_ON зажигается красный прожектор и запускается таймер на отсчет длительности вспышки. Автомат остается в этом состоянии до тех пор, пока либо истечет период таймера (событие TimerElapsed), либо наступит день (событие Day).
Попробуем реализовать этот автомат в коде.



Продолжение.
Версия для печати
Обсудить на форуме (3)