Протокол как конечный автомат

Обновлено: 28.05.2024

Спецификация последовательности состояний, через которые проходит в течение своей жизни объект, или взаимодействие в ответ на происходящие события (а также ответные действия объекта на эти события). Конечный автомат прикреплен к исходному элементу (классу, кооперации или методу) и служит для определения поведения его экземпляров.
См. activity graph; composite state; event; pseudostate; state; transition.

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

Семантика выполнения конечного автомата

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

Запуск перехода и действия

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

Эта нотация была создана Дэвидом Хзрелом (David Harel). В нее входят некоторые аспекты автоматов Мура (Моигс) (действия при входе), автоматов Мили (Mealy) (действия, прикрепленные к переходам), а также концепции, относящиеся к вложенным и параллельным состояниям.
Более подробную информацию смотрите в статьях state; composite state; submachine; pseudostate; entry action; exit action; transition и activity. Еще один вариант нотации, которую можно использовать для потока деятельности, вы найдете в статье activity graph.
См. также статью control icons энциклопедии, в которой делаются дополнительные символы, изначально предназначенные для диаграмм деятельности, которые, тем не менее можно использовать и в диаграммах состояний.

Существует два вида использования конечных автоматов. Следовательно, их содержание тоже можно понимать двояко. В одном случае конечный автомат служит для спецификации поведения того элемента, которому он принадлежит, - как правило, класса. Это означает, что конечный автомат описывает реакцию этого элемента на получение событий извне. Такая реакция описывается в виде переходов, каждый из которых указывает на то, что происходит после того, как элемент. находясь в определенном состоянии, получил какое-либо событие. Она может выражаться в виде действия и изменения состояния, К действиям относится и отправка другим объектам сигналов, которые запускают их конечные автоматы. Конечные автоматы служат для упрощенной спецификации поведения системы.
Другой способ использования конечных автоматов - спецификация протокола, в соответствии, с которым определяется порядок вызова операций для класса или интерфейса. В таком конечном автомате переходы запускаются при помощи событий вызова, а их действия вызывают требуемые операции. Это означает, что объект имеет право вызвать операцию в данной точке. В конечном автомате протокола нет действии, которые определяют поведение самой операции. Он просто указывает, в каком порядке должны вызываться операции, то есть определяет разрешенные Последовательности операций. Иными словами, конечный автомат в данном случае используется как генератор последовательности на определенном языке программирования. Такой конечный автомат выполняет роль ограничения в общем, проектировании системы. Он не предназначен для непосредственного выполнения и не указывает, что случится, если последовательность операций будет нарушена (этого не должно происходить - ответственность за правильный порядок выполнения операции лежит на разработчике системы).
Второй способ использования конечных автоматов более абстрактный, чем первый, который описывает в выполнимой форме, что происходит во всех случаях. Тем не менее, второй способ тоже удобен, особенно на ранних стадиях проектирования и при кодировании процедур.

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

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

Вызывая эту функцию подряд мы заставим диодик менять свое состояние при каждом вызове.

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

Приведу другой, более сложный пример. Генерацию сигнала сложной формы.

Пусть у нас есть сигнал:

Цифрами указана задержка, в каких нибудь величинах. Это не суть важно.

Обычно народ не парится и лепит его по быдлокодерски, через delay:

Set_Pin(); // Вывод в 1 Delay(10); // Задержка 10 Clr_Pin(); // Вывод в 0 Delay(100); // Задержка в 100 Set_Pin(); Delay(1); Clr_Pin(); Delay(5); Set_Pin(); Delay(2); Clr_Pin(); Delay(3); Set_Pin; Delay(4); Clr_Pin();

Это дает минимальный код, но затыкает работу контроллера на весь период посылки. А если слать надо постоянно? Да еще дофига всего попутно делать? Экран обновлять, данные обрабатывать, в память писать…
В таком случае у нас рулит RTOS, где на Delay происходит передача управления диспетчеру. Но если ОС нету? Вот тут то и идет в ход конечный автомат.

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

А запускается эта байда простым пинком:

Set_Pin(); TCNT=255-10; // Грузим таймер на выдержку 10 тиков TMR_State = 0; // Устанавливаем начальное положение Timer_ON(); // Поехали! . // После чего можно заниматься чем угодно.

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

Конечный автомат можно зациклить — скажем на стадии 6 сделать перенаправление на стадию 0, то получим генератор сигнала сложной формы. Причем он будет занимать минимум процессорного времени.

Если мы, например, захотим сделать десяток ШИМ сигналов? То что нам мешает повесить их на ОДИН таймер, главное отсортировать все скважности по возростанию, причем сортировать их вместе с ногами которыми нужно дрыгать. А потом прогнать по прерыванию таймера конечный автомат, да так чтобы он по стадиям передергивал ножки. Правда при изменении скважности любого из этих софтверных ШИМ каналов придется делать повторную сортировку всего массива. Разумеется больших скоростей мы на этом не получим. Таймер не может щелкать так быстро, да и математики там хватит. Но для многих задач, например, одновременное управление десятком сервомашинок этого более чем достаточно.

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

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

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

Особенно автоматный метод доставляет тем, что готовые автоматы вписываются как родные в ЛЮБУЮ почти архитектуру. У меня они и во флаговых автоматах работают на ура, и из диспетчера RTOS я их гоняю как родные. Красота!

Спасибо. Вы потрясающие! Всего за месяц мы собрали нужную сумму в 500000 на хоккейную коробку для детского дома Аистенок. Из которых 125000+ было от вас, читателей EasyElectronics. Были даже переводы на 25000+ и просто поток платежей на 251 рубль. Это невероятно круто. Сейчас идет заключение договора и подготовка к строительству!

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

70 thoughts on “AVR. Учебный курс. Конечный автомат”

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

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

Так если б программистов нормально учили, а то ведь та же фигня, КА нам прочли только на третьем курсе. Чего теперь стоит отучиваться писать говнокод…

Чего-чего? А, гугль подсказывает, есть такие кафедры…
Не. Кафедра ЭВС (ранее — КЭВА), МарГТУ (ранее — МарПИ).

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

Меня во время учёбы очень зацепили микропрограммные автоматы — простая ПЗУ плюс регистр-защелка плюс тактовый сигнал — и можно наворотить нечто, что казалось бы, требует целого процессора. Хотя процессор так и устроен, ага — только добавляются АЛУ, РОН и прочие блоки.

Я с ПЗУ делал лет 10 назад много чего интересного :) Управление ксетником, робота маленького…. Даже делал 4ьитный калькулятор..

А как АЛУ реализовывалось? Таблично?

Да :) было использовано на всё это 6 штук РЕ5

Замечу: вместо номеров состояний лучше использовать осмысленные идентификаторы, объявив их перечислением. Легче будет писать и изменять программу, меньше вероятность перепутать.
Конечно, если состояния меняются строго по порядку — то и с номерами никаких проблем, но часто граф переходов бывает весьма хитрым.

И у нас был курс по этим автоматам! Я его прошел и забыл, но суть уяснил. Успешно использую это знание в своих работах =)

Эт не моя тема, не думаю что я там дам толковый совет.

Значит будем ждать новые статьи по Вашей теме, спасибо.

А что конкретно вас интересует в расчете? Использование Матлаба или другой способ подгонки коэффициентов? Или что то другое?

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

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

Чем плох такой подход?

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

Прямую передачу можно присобачить, тем более, что пример есть в статье :)
Кстати, а зачем временная задержка нужна?

Какая временная задержка?

case 0:
Clr_Pin(); // Вывод в 0
TCNT = 255-100; // Задержка в 100 (до переполнения)
TMR_State = 1; // Следующая стадия 1
Break; // Выход
>

Вот эта -> // Задержка в 100 (до переполнения)

Ну так это — параметры генерируемого сигнала посмотри. =)

Точно, протирание глаз иногда помогает :) Т.е. основная цель — это генерация такого сигнала. А так по сути, если такие интервалы не критичны, то задержка нафиг не нужна.

imho, переменную состояния лучше запихнуть внутрь функции и объявить как статическую, ибо чем меньше область видимости, тем меньше потом придется разбираться с непонятными зависимостями и побочными эффектами:

А если захочется изменить ее извне? В более сложных премерах это сплошь и рядом.

ИМХО, когда захочется её изменять из вне, тогда и надо её выносить в глобальную область видимости, а пока такой необходимости нет, то лучше пусть она будет локальной.

Присоединяюсь. Инкапсуляцию не зря придумали.

Вот как понадобится — так и вытаскивать.
Чем меньше в системе связей, тем проще ее развивать или чинить-диагностировать.

Кстати, по поводу стилей оформления исходников.
Я предпочитаю так:
фигурные скобки всегда с новой строки.
Весь блок внутри скобок сдвинут вправо относительно скобок на два пробела.
Не помню, откуда этот стандарт, но так реально удобнее читать, особенно если вложенность хотя бы пять-шесть.

Ага, всё это вполе субъективно-религиозно, а не Великая Истина.

Круто! Не догадался бы. Возьму на вооружение.

Мне тоже понравилось :-) Мерси, nicka

маньяки, блин! больше кнопок нажмете, больше калорий потратите ))
чем ваc if(var) или if(!var) не устраивает?
давайте тогда уж x=x+1 писать ))

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

Ну, например, так:

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

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

А так забыл поставить break в каком-то развесистом case — и вылезет это боком через год на реальном оборудовании.

По-моему получилось не менее былокодерски. Не лучше ли сделать массив с длительностью задержек и при каждом прерывании простым кодом брать из него значение? По идее такой способ и места в прошивке будет меньше занимать. А при генерации сигналов длиной 30 и более шагов разница будет очень очевидна :)

А кто тебе сказал что это конечное решение? И суть тут не в массиве, а в подходе.

Коллега!
Мигалка на псевдокоде мигать не будет! Будет всегда выключена, потому что второй иф выполнится сразу же за первым

Внимательнее смотри код, там return.

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

Статья как нельзя кстати. На дня нашел вот такое вот чудо:

C/C++ Open Source State machine framework. Может интегрироваться в некоторые, популярные RTOS. Поддержка AVR (под WinAVR / IAR).

Очень хотелось бы заюзать, да только для начала неплохо бы вникнуть в саму суть конечных автоматов.

Таймер может сделать только ОДНУ какую либо выдержку. Как сделать так, чтобы ОДИН таймер поочередно реализовал массу выдержек, причем сделал это сам, без вмешательства фоновой программы? С помощью конечного автомата.

Полезная штука. А как такое на асме реализовать? Каким способом?

Вариантов масса. Начиная с бального комплекта
LDS R16,Avtom_state
CPI R16,value
BREQ nnn
CPI R16,value
BREQ mmm
CPI Rn,value
BREQ kkk

До создания таблицы переходов, где Avtom_state будет создавать смещение в таблице, где лежит адрес перехода.

О, большое спасибо. Но если у меня около 30 операций в автомате, разница-то во времени выбора каждого действия будет разная. Правильно я понимаю?

Если на CPI банде то да. Чем глубже тем дольше. А если на таблицах перехода то нет. Каждый кейс будет обрабатываться за одинаковое количество тактов.

error: Relative branch out of reach

Не подскажете, что это за ошибка? Точнее из-за чего она? У меня сразу в обработчике стоят сравнения.

CPI R19,1
JMP stolb_1

CPI R19,2
BREQ stolb_2

CPI R19,3
BREQ stolb_3

Бранч который в BREQ не умеет прыгать дальше чем 127 (или даже 64) команды вверх или вниз. У тебя просто он не достает до метки.

Обычно в таких случаях делается островок вида:
RJMP Obhod
m: RJMP M
m2: RJMP M2
Obhod:
…..

Примеры сделаны на пинбоорде v1.1, для тех кто не сильно понимает язык С++ (хотя я осознаю что рано или поздно надо будет и им овладеть, но пока мне и asm хватает, аппетит приходит как говориться во время еды _)
Конечный автомат (state machine, машина состояний) представляет собой устройство, имеющее внутреннюю память (переменные состояния), а также набор входов и выходов.
Работа автомата состоит в том, что он анализирует состояния своих входов, и, в зависимости от значений входов и своего внутреннего состояния, изменяет значения выходов и внутреннее состояние. Правила, в соответствии с которыми происходит изменение:
1. диаграммой переходов или
2. описываются таблицей.
Диаграммы как я понял по ходу дела составляются из блок схем, нарисовать не могу, т.к. не знаю как вставит в коменты (отзывы) картинку, но код мне кажется должен выглядеть вот так:

iini: cbi ddrD,6; инициализация, настройка кнопки на подтяжку sbi portD,6; PullUP knopka: sbic pinD,6; тест кнопки на rjmp knopka; 0 – GND ;------------------------------------------ ;Задержка опроса кнопки тупым циклом т.к. таймерами я еще не овладел, в процессе еще … извините. LDI R26,255;LowByte; LDI R27,255;MidleByte; LDI R28,4;HighByte; loop1: SUBI R26,1; SBCI R27,0; SBCI R28,0; BRCC Loop1; ;-------------------------------------------- status: sbrc r16,0; Пропустить если бит в регистре очшищен rjmp led_on; перескок к метке led_on rjmp led_of; перескок к метке led_of led_on: sbi ddrD,7; на выход нога sbi portD,7; поднять ногу ldi r16,0b00000000; сохранить состояние автомата в регистр rjmp knopka; переход на ожидание нажатия кнопки led_of: cbi ddrD,7; нога на вход cbi portD,7; вырубить ногу ldi r16,0b00000001; сохранить состояние автомата rjmp knopka; переход на ожидание нажатия кнопки

В качестве ячейки сохранения состояния автомата в данном случае был использован регистр r16, (что бы таким как я было понятнее суть) и в нем (r16) можно было бы сохранить 256 различных состояний автомата, НО как я понял можно использовать вместо одного регистра любую ячейку не только РОН, но и RAM, ROM, EEROM и т.д. (включая внешние накопители), где можно было бы сохранить и считать биты статуса. (вопрос лишь в скорости и целесообразности ясный пень что РОН и RAM самый быстрые ячейки).
2. описываются таблицей.

;Резервирование ячейки в ОЗУ: .DSEG ; сегмент RAM (ОЗУ) для Мега16 начинается с $0060, (см. *.inc на тип контроллера) status: .BYTE 1; зарезервировали 1 байт в ОЗУ .CSEG ; кодовый сегмент ; Настройка кнопки D6 и очистка ячейка status в ОЗУ. ini: cbi ddrD,6; надо обнулить направление, sbi portD,6; поднять PullUP clr r16; очистка регистра sts status,r16; для того что бы обнулить ячейку в ОЗУ ; Проверка на нажатие кнопки с помошью флага Т knopkaa: in r17,pinD; чтение из порта save в регистр ;------------------------------------------ ;Задержка опроса кнопки тупым циклом т.к. таймерами я еще не овладел, в процессе еще … извините. LDI R26,255;LowByte; LDI R27,255;MidleByte; LDI R28,4;HighByte; loop1: SUBI R26,1; SBCI R27,0; SBCI R28,0; BRCC Loop1; ;-------------------------------------------- bst r17,6; сохранить в 6 бит регистра в sreg T brts knopkaa; есть/нет sreg T, кнопка нажата или нет ldi r20,0b00000001; загрузить число 1, lds r18,status; сохранить из ячейки ОЗУ в регистр sub r20,r18; вычесть 1 – status. ; Косвенный переход (ijmp) по адресу в таблице (tablica1), бессовестно скопипастена у Di Halt’a, но пока еще до конца не осмыслена (в процессе т.с. близко к финишу). lsl r20; сдвиг влево (в данном случае получается значение 2 или 4) ldi zl,low (tablica1*2); умножаем адрес таблицы на 2, младший байт ldi zh,high (tablica1*2); умножаем адрес таблицы на 2 старший байт add zl,r20; сложить младший байт (r30) с ячейкой в таблице clr r21; обнулить регистр, хотя end FLASH = 0x1FFF, а не 0x00FF adc zh,r21; вносим в r31 значение 0, хотя если табл. в конце флеша будет то видимо надо будет переписать по другому lpm r20,z+; загрузка в r20 значения адреса с пост-инкрементом lpm r21,z; загрузка в r21 значения адреса movw zh:zl,r21:r20; копировать регистровые пары ijmp; переход по адресу указанному в ячейках r31:r30 Вот пошла таблица с ячейками ссылок на метки: rjmp mimo; перескок через таблицу на всякий случай tablica1: .dw led_on_D7, led_of_D7; отсчет ячеек идет само собой с нуля, через запятые. mimo: nop; led_on_D7: sbi ddrD,7; на выход sbi portD,7; поднять ногу зажечь диод ldi r16,0b00000000; 0 значение в регистр sts status,r16; save значение в ОЗУ в ячейку status rjmp knopkaa; led_of_D7: cbi ddrD,7; на вход cbi portD,7; нога вниз ldi r16,0b00000001; 1 значение в регистр sts status,r16; save значение в ОЗУ в ячейку status rjmp knopkaa;

Мне так кажется что табличный вариант лучше, удобнее (читабелнее и в отладке в самый раз), выглядит стройнее, не говоря о комбинации с косвенным переходом, (без перебора значений), не говоря о практически безграничной (размер таблицы переменных значений состояний автомата в ОЗУ, уже в голове созрел коварный план заныкать таблицу в ОЗУ в конце, а SP поднять выше таблицы.)
p/s: примеры у меня работают не забывайте выставить конец стека и во втором примере зарезервировать байт в ОЗУ.

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

Несмотря на свою древность, RS232 и его вариации до сих пор широко используются в различных системах автоматизации и в бытовых приборах. И это все потому, что COM-порт очень прост в освоении. И еще существует большое количество переходников USB-UART, которые позволяют добавить интерфейс USB в свой девайс без мучительного изучения стандарта USB и покупки VID. Однако, встает вопрос о том, каким образом передавать байты информации по последовательному порту. В этой статье мы рассмотрим мое решение данного вопроса, которое называется BinExchange protocol.

Обзор протокола Modbus

Для начала давайте рассмотрим одно из существующих решений, которое является промышленным стандартном, а именно протокол Modbus.

Modbus является пакетным протоколом обмена данными с архитектурой ведущий-ведомый. Modbus в основном используется для создания сетей поверх RS485. Существует 3 варианта Modbus:

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

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

Свой вариант протокола

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

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

где AABBCCDD — полезные данные, в данном случае 4 байта, EEFF — контрольная сумма, 2 байта.

В принципе удобно и наглядно. При большом желании, пакеты можно генерить в уме и отправлять вручную прямо из консоли, если научитесь устному счету CRC16))) Служебной информации в таком пакете 2*n + 6, n-количество передаваемых байт, но если скорость передачи не очень важна, то такой вариант является приемлемым. Такая реализация себя неплохо зарекомендовала в нескольких моих проектах.

Однако, хочется все же уменьшить количество служебной информации в пакете для увеличения пропускной способности протокола при той же скорости работы UART. Можно в качестве системы кодирования пакета использовать не HEX, а что-то типа Base64, Base128, и т.д. Но давайте все же обратимся к бинарной реализации протокола. Возникает вопрос, а как нам тогда отделять один пакет от другого? Очень просто: зарезервируем один специальный байт, с которого будет начинаться каждый новый пакет. Но как быть, если этот байт будет встречаться в самих передаваемых данных? Ответ очень простой — будем использовать экранирование: если он будет попадаться в передаваемых данных, то мы просто отправим его 2 раза подряд.

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

S 0 L0 L1 D0 D1 D2 D3 … Dn C0 C1

  • S — спец. байт начала пакета
  • L0, L1 — длина полезных данных пакета
  • D — полезные данные
  • C0, C1 — контрольная сумма CRC16

Если в передаваемых данных будет встречаться наш спец. симпол, то пакет будет выглядеть так:

S 0 L0 L1 D0 D1 S S D3 … Dn C0 C1

S 0 L0 L1 D0 D1 D2 D3 … Dn S S C1

S 0 L0 S S D0 D1 D2 D3 … Dn C0 C1

Думаю, с этим все понятно.

Реализация

Реализацию протокола BinExchange приведу для микроконтроллера STM32F030, однако, его можно с легкостью перенести на любой другой МК, нужно только переписать драйвер UART. Модуль BinExchange реализован в виде конечного автомата, что позволяет работать протоколу параллельно с другими задачами.

Рассмотрим функции протокола:

BinEx_Init() — инициализация протокола

BinEx_Process() — процесс конечного автомата протокола, вызывается в бесконечном цикле в main()

Функции передатчика:

BinEx_TxStatus() — статус передатчика, возвращает следующие значения:

  • BINEX_READY — готов к следующей передаче;
  • BINEX_RUN — в данный момент ведется передача.
  • BINEX_OK — передача успешно запущена;
  • BINEX_BUSY — в данный момент еще не закончена предыдущая передача данных.

BinEx_TxGetBuffPntr() — если в данный момент передатчик находится в состоянии BINEX_READY, то возвращает указатель на буфер передатчика uint8_t *, если передатчик в состоянии BINEX_RUN, то возвращает ноль.

Функции приемника:

BinEx_RxStatus() — Получить статус приемника. Возвращает следующие значения:

  • BINEX_READY — приемник находится в режиме ожидания и не обрабатывает входной поток данных;
  • BINEX_RUN — приемник находится в режиме приема данных и ждет получения пакета. После получения пакета перейдет в состояние BINEX_READY, либо в BINEX_ERROR, если возникла какая-либо ошибка;
  • BINEX_ERROR — произошла ошибка приема пакета, для получения более подробной информации необходимо воспользоваться функцией BinEx_RxExtendedStatus().

BinEx_RxExtendedStatus() — подробная информация о статусе приемника. Возвращает следующие значения:

  • RXPACK_OK — пакет принят успешно;
  • RXPACK_CRCERR — ошибка контрольной суммы пакета;
  • RXPACK_TOO_LONG — длина пакета, указанного в заголовке, больше максимальной длины пакета BINEX_BUFFLEN.

BinEx_RxBegin() — начать прием пакета, приемник переходит в режим обработки потока входных данных. Возвращаемые значения:

BinEx_RxDataLen() — получить длину принятого пакета. Возвращает актуальные данные после перехода приемника из состояния BINEX_RUN в состояние BINEX_READY.

BinEx_RxGetBuffPntr() — если приемник находится в состоянии BINEX_READY, то возвращает указатель на буфер приемника, иначе ноль.

Практика

Перейдем теперь к практике работы с протоколом BinExchange. Приведу код, который принимает пакет данных и отправляет его обратно без изменений. Что-то типа ping-а))) Код IAR для stm32f030:

Рассмотрим наш тестовый конечный автомат TxTestProc(). В исходном состоянии мы разрешаем прием пакета данных и переходим в состояние 1. В состоянии 1 мы дожидаемся окончания процесса, и в случае его успеха переходим в состояние 2, а если возникли ошибки, то в состояние 3.

Рассмотрим состояние 2. Первым делом мы убеждаемся в том, что передатчик в данный момент ни чем не занят. Далее, получаем указатели на буферы приемника и передатчика, получаем количество принятых байт, и копируем буфер приемника в буфер передатчика. Затем запускаем процесс передачи и переходим в исходное состояние.

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

Мы генерируем массив случайных байт с помощью rnd.NextBytes(tx) и отправляем его в микроконтроллер. Затем, читаем то, что нам вернул МК и выводим в консоль. Так же возможна работа в асинхронном режиме. В этом случае, при получении очередного пакета данных, возникает событие Bin_DataReceived(), в котором мы читаем полученный пакет:

На этом вроде как все! Статья получилась довольно объемной, надеюсь, она будет кому-нибудь полезна. Спасибо за внимание, всем пока 🙂


Конечный автомат с счастливым и грустным Васькой

Конечные автоматы

Для начала дадим определение: конечный автомат (finite-state machine, FSM) — это математическая абстракция, модель, которая может находиться только в одном из конечного числа состояний в каждый конкретный момент времени. Автомат умеет переходить из одного состояния в другое в ответ на данные, которые подаются на вход; изменение состояния называется переходом. FSM определяется списком его состояний, начальным состоянием и инпутами, запускающими переходы.

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

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

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

Примеры использования

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

  1. Логика искусственного интеллекта для игр. Вот статья, раскрывающая эту идею.
  2. Синтаксический и лексический анализ. Подробнее о таком применении можно прочитать здесь. В том числе сюда относится проверка языка — мы собираемся реализовать её в части статьи, посвящённой проверке бинарного кода.
  3. Сложные компоненты. О них есть хорошая статья, однако мы тоже попробуем разобрать эту тему.

Проверка бинарного кода

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

  • Алфавит. Набор символов, которые должно содержать проверяемое значение (и ни одного символа вне алфавита).
  • Конечные состояния. Подмножество существующих состояний — возможно, пустое. Когда FSM завершает свою работу, он принимает проверяемое значение, если это подмножество включает текущее состояние, и отклоняет в противном случае.
  • Нам нужно создать автомат для проверки случайных значений, который будет отвечать, является ли значение бинарным кодом.
  • Мы принимаем непустые строки с символами 0 и 1 и отклоняем всё остальное.

Вот наш автомат, детерминированный акцептор с конечным состоянием:


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

Схема акцептора бинарного кода

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

  • Если текущее состояние — q0, а текущий символ — 0 или 1, выполнить переход в состояние q1.
  • Если текущее состояние — q1, а текущий символ — 0 или 1, выполнить переход в то же состояние.
  • Если текущий символ не равен 0 или 1, отклонить проверяемое значение независимо от текущего состояния.

Использование и тестирование

Получилось! Обратите внимание: нам не нужно указывать все возможные символы для каждого состояния — когда автомат встречает не прописанный в алфавите символ, он заканчивает работу.

Сложная форма

Пример с проверкой бинарного кода — довольно тривиальный. Вряд ли вам часто придётся решать такие задачи, если придётся вообще. Давайте рассмотрим ещё один пример — создадим форму с несколькими состояниями в UI-ориентированном FSM. Код автомата доступен на CodeSandbox, вы можете перейти к нему или попробовать написать его самостоятельно.

Для начала создайте новый проект в React:


Структура проекта должна выглядеть так:


App.js и index.js не требуют изменений. FSM.js будет содержать новую реализацию FSM, напишем её:


Обратите внимание, что мы удалили алфавит и состояния. Теперь у нас есть только два параметра, которые нужно определить:

  • Начальное состояние. Работа FSM должна где-то начинаться.
  • Переходы. Объединяем их с состояниями — так мы создаём более ёмкий экземпляр, при этом обеспечивая ту же функциональность.

Наша реализация обязывает использовать метод send для изменения состояния. Мы также добавили метод subscribe . Это очень полезно, если мы хотим, чтобы автомат реагировал на изменение состояния.

Давайте протестируем код на нашем примере с Васькой. Создайте файл test.js :


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

happy
sad
happy

Автомат определённо работает! Наконец, давайте отреагируем на изменение настроения Васьки:


Запустите автомат снова.

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

Небольшая диаграмма, чтобы стало понятнее:



Автомат, определяющий нашу анкету

Когда стало ясно, какие состояния у нас есть и как они соотносятся друг с другом, мы можем приступить к работе над проектом. Первое: нужно установить дополнительные зависимости:


После завершения установки добавляем директорию /components с компонентами внутри. Также мы создаём файл questionnaireMachine.js в директории /src . Теперь структура проекта выглядит так:


Файл questionnaireMachine.js создаёт и экспортирует экземпляр Questionnaire FSM:

Questionnaire FSM

Следующим шагом будет создание презентационного слоя проекта — самой анкеты. Мы разделим его на три отдельных компонента:

  • Анкета. Основной компонент, определяющий последовательность вопросов.
  • Карточка. Многоразовый компонент для отображения части анкеты.
  • Прелоадер. Простая анимированная точка.

Первое: нам нужно подписаться на изменения состояния конечного автомата. Каждый раз, когда состояние меняется, мы обновляем uiState . Это нужно для вычисления свойства active компонента карточки — именно оно позволяет экземпляру компонента карточки решать, показывать себя или нет.

Теперь займёмся компонентом карточки:

Кнопки в нижней части компонента используют указанные действия как listener для события клика. Вот почему мы здесь передаём функции, изменяющие состояние FSM: так компонент анкеты сможет обновить uiState и отобразить нужную карточку.

Последняя мелочь — компонент прелоадера. Здесь нет ничего интересного, просто анимированная точка:

Наконец, добавляем анкету в компонент приложения. Корневой компонент со стилями:

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

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

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

Заключение


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

Читайте также: