Event Driven State Machines for AVR8

Вместо предисловия

Речь пойдёт о написании программ для микроконтроллеров. Всем нам порой приходится делать несколько дел "одновременно". Всяким там смартфонам, стиральным машинам и прочим планшетам - тоже. Для этого делали и делают операционные системы, в которых есть понятие процесс/нить/задача. Вот. Но мы тут о вычислительных системах с одним ядром в процессоре. Какая уж тут "одновременность". Задачи на таких системах исполняются поочередно, ни о какой паралеллельности речи быть не может. Зачем же тогда делать ОС для микроконтроллеров? А вот зачем - чтобы писать линейный код. Грубо говоря, программа исполняется в том порядке, как она написана в исходниках. Так типа понятнее. Других причин я не вижу. Для чисто вычислительных задач по-другому и не надо. Ввод-вывод - это другая история. Есть, однако, пара не очень приятных моментов в этом деле (я имею ввиду использование многозадачной ОС для разработки ПО для микроконтроллеров):

• каждой задаче нужен свой стек, чтобы контекст там хранить, а это место в ОЗУ
• переключение этих самых контекстов - весьма времяёмкая процедурка.

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

На тему "как лучше - с ОС или без ОС" есть всяких срачей полемик. Вот, например, глядите - protothreads-versus-state-machines

Я просто не могу не процитировать:

"Pure event-driven programming (without blocking) naturally partitions the code into small chunks that handle events. State machines partition the code even finer, because you have small chunks that are called only for a specific state-event combination. Such code naturally follows OCP, so you easily can add new functionality *without* changing the other already designed and *tested* code"

State machines partition the code even finer... золотые слова! Если вы попробуете, вы ощутите всю прелесть нового чая Лiптон. Если проектировать ПО, используя парадигму "конечных автоматов", то исходный текст программы САМ СОБОЙ структурируется. Just try it. К слову, структурирование важно не только само по себе - ещё так же важно, чтобы события обрабатывались быстро. Кстати, чо такое OCP?... Ух ты, вот оно что. Ну-ну.

Тема диспута, кстати, прикольная - ведь можно накрутить state machines поверх API любой ОС. Ну или хоть поверх Java-Script машины в интернет-браузере. Просто вся это конструкция с конечными автоматами будет работать в рамках одного процесса/нити/задачи ОС или в рамках одной нити интернет-браузера. Но тут мы не забываем, что cобираемся кодить вот таким образом.

Ну так и вот. Стало мне как-то в очередной раз печально и сподвигнулся я замутить нечто подобное этому, но поверх bare-metal в виде atmega328p, которая на борту у Arduino Nano. Вот зря я щас написал слово "arduino". Щас ведь некоторые подумают, что я тут собрался учить, как пользоваться средой разработки для платформы Arduino. Те, то так подумал, идите, блин, в python. Или ещё куда повыше. Всё, описанное далее, написано сугубо с использованием gcc-avr и avr-libc.

Сразу предупреждаю. Вместо "пары неприятных моментов", упомянутых чуть выше, можно поиметь другую, вполне аналогичную, пару неприятных моментов:

• описания автоматов надо где-то хранить, а это место в ОЗУ; впрочем, при особом желании их можно и во FLASH поместить
• помещение событий/сообщений в очередь оных и извлечение их оттедова суть процедурки, которые, в зависимости от реализации, могут потребовать значительного количества тактиков CPU.

Вобчем, хрен его знает, что "лучше", "многозадачность/threads" или "level 100 concurrency". Но мы попробуем. Итак...

Архитектура

Аппаратура является источником прерываний, обрабатываемых подпрограммами обработки прерываний (ISR); обработчики прерываний помещают сообщения, адресованные какому-либо из автоматов, в очередь mq0. Для "программных" событий/команд предусмотрена очередь mq1. Диспетчер событий просматривает обе очереди (mq0 является более приоритетной) и выполняет работу по доставке сообщений адресатам и по переводу автоматов из одного состояния в другое.

Основной цикл

 1 #include <avr/interrupt.h>
 2 #include <avr/sleep.h>
 3
 4 #include "message-queue.h"
 5 #include "edsm.h"
 6
 7 int main(void)
 8 {
 9	cli();
10	init_message_queue();
11	start_state_machines();
12	sei();
13
14	for (;;) {
15		process_messages();
16		sleep_mode();
17	}
18 }

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

Диспетчер сообщений

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

Собственно, сам диспетчер (если быть точным, то этот код есть нечто большее чем "диспетчер сообщений" - он ещё переводит автоматы из состояния в состояние, просто не придумалось другого названия):

 1 void process_messages(void)
 2 {
 3 	struct edsm *sm;
 4	struct state *state;
 5	struct reflex *r;
 6	    u8 msg;
 7
 8	for (;;) {
 9
10		msg = dequeue_message();
11		if (0xFF == msg)
12			/* message queue is empty */
13			 break;
14
15		/* dispatch the message */
16		sm = &state_machines[MSG_DEST_SM(msg)];
17		if (NULL == sm)
18			bug();
19
20		state = &sm->states[sm->state_number];
21		r = &state->reflexes[MSG_EV_CODE(msg)];
22		if (NULL == r)
23			bug();
24
25		if (r->action)
26			r->action(sm);
27
28		if (0xFF == r->next_state)
29			/* do not leave the state */
30			continue;
31
32		/* make a transition */
33		struct state *ns = &sm->states[r->next_state];
34		if (ns->enter)
35			ns->enter(sm);
36		sm->state_number = r->next_state;
37	}
38 }

Некоторые пояснения... В строчках 10-13 происходит извлечение сообщения из очереди; если при этом получаем 0xFF, то это значит, что очередь пуста и мы выходим из цикла. В строчке 16 определяем, какому автомату предназначено сообщение. Строчки 20 и 21 - определяем, в каком состоянии находится автомат-получатель и как он должен реагировать на сообщение. Если реакция подразумевает какое-то действие, оно исполняется (это строчки 25 и 26). Далее, если менять состояние не надо, то идём на начало цикла (строчки 28-30). Если же реакция подразумевает ещё и переход в другое состояние, то осуществляем его, попутно исполняя функцию входа в это состояние (это строчки 33-36). Собственно, всё, это весь, так сказать, "движок" всей нашей конструкции.

Описание автоматов

Для описания автоматов используются три сущности, собственно сам автомат, его состояние и реакция на событие:

struct edsm {	// конечный автомат
	char *name; // вдруг пригодится
	u8 state_number; // номер текущего состояния
	struct state *states; // массив состояний
	void *data;
};

struct state { // состояние автомата
	char *name; // вдруг пригодится
	action enter; // входная функция
	struct reflex *reflexes; // набор "рефлексов"
	u8 n_reflexes; // количество рефлексов
};

struct reflex { // реакция ("рефлекс")
	action action; // действие
	u8 next_state; // следующее состояние
};

"Действие" определено следующим образом:

typedef void (*action)(struct edsm *sm);

Примеры автоматов

В качестве примера спроектируем 2 взаимодействующих друг с другом автомата:

• автомат для работы с USART
• некий зачаток оболочки для взаимодействия с пользователем (shell)

Будем плясать от печки, то есть от обработчиков прерываний. Вот они:

#include <avr/io.h>
#include <avr/interrupt.h>

#include "message-queue.h"
#include "itypes.h"
#include "edsm.h"

ISR(USART_UDRE_vect)
{
	/* disable USART DRE interrupt */
	UCSR0B &= ~_BV(UDRIE0);
	enqueue_message_hw(M1_USART, R0_);
}

ISR(USART_RX_vect)
{
	/* disable USART RXC interrupt
	 * (for the sake of uniformity)
	 */
	UCSR0B &= ~_BV(RXCIE0);
	enqueue_message_hw(M1_USART, R0_);
}

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

Схема автомата для работы с USART:

Схема автомата SHELL:

Как видно из картинки, автомат для работы с USART может находиться в 3-х состояниях, "инициализация" (INIT), "приём" (RX) и "передача" (TX) (мы будем делать полудуплекс). На входе в состояние INIT произодится настройка приёмопередатчика и после этого автомат сам себя сразу переводит в состояние RX.

В состоянии RX по событию от ISR (которая USART_RX_vect) считывается принятый в приёмник байт; если команда ещё не пришла целиком, автомат разрешает прерывание "приём завершён" (которое было запрещено в соответствующей ISR); если приехал признак конца команды, то приём тут же выключается, а автомату shell посылается сообщение о том, что поступила команда. После этого автомат продолжает оставаться в состоянии RX до тех пор, пока не получит от автомата shell сообщение с кодом 1. По этому сообщению он перейдёт в состояние "передача" (данные для передачи готовит автомат shell).

На входе в это состояние включается передатчик и разрешается прерывание "data register empty". По событию от ISR (которая USART_UDRE_vect) производится запись очередного байта в в регистр данных USART. Пока не все байты отправлены, автомат разрешает прерывание, запрещенное в ISR. Как только передача всех байтов закончится, автомат посылает 2 сообщения - одно себе, по которому он перейдёт обратно в режим приёма, а другое - автомату shell, по которому тот перейдёт в состояние ожидания следующей команды.

Всё остальное см. в исходниках:

• для сравнения - некий вариант без автоматов
• r0
• r1 (когда-нибудь будет :) )

Дата последней модификации: 2018-02-14