State machine, Приведите примеры реализации Опции

[sat]

Где можно почитать по теме/посмотреть примеры на С, асме

[Владимир_2010]

Diz спасибо за ссылку на книги. В сети также есть «Samek Miro, Practical UML Statecharts in C/C++. 2008».
Diz писал:

Другое дело – визуализация уже написанного на низком уровне конечного автомата

Нельзя ли в этом месте поподробней?! Задачи по дискретным системам автоматики я решал в основном по методе/идее изложено в книге «Юдицкий С.А. Проектирование дискретных систем автоматики. 1980». На русском искал, но больше ничего не встречал по этой теме. Встречались книги просто про конечные автоматы, без приложений к автоматике. Но там одна математика.
Вот как я решал задачки по автоматике: по методе вначале рисовал конечный автомат (графы с переходами) в пакете Stateflow от Matlab, затем проверял логику работы автомата моделируя различные состояния, далее записывал граф в виде уравнений/формул (вручную на бумажке), оптимизировал (вручную на бумажке) если требовалось конечный автомат с применением методов дискретной математики. Потом формулы рисовал в виде релейно-контакторной схемы (или функционально-логической схемы – триггеры, или, и, не), писал программу на Step7 (софт для программирования логических контроллеров Siemens) или на CX-Programmer (софт плк Omron) и прогонял логику работы с использованием симулятора для этих контроллеров.
Применяя эту методу к нескольким различным задачам, убедил себя (возможно зря) что самое главное для любой задачи по автоматике на плк это нарисовать правильно конечный автомат (графы с переходами) и проверить его работу средствами моделирования – все остальное дело техники, рутинный труд, все можно делать по одному шаблону/правилам, выключив мозг, нужно только время. Хотел даже весь этот процесс автоматизировать и написать автоматический генератор из графов всех этих формул и схем. Но потом подумал, что не надо горячиться: наверняка все это давным-давно уже сделано кем-то. Теперь вот вижу что на языке Си IAR реализует этот подход в VisualState, Telelogiс, великий ученый Шалыто А. А. и его друзья.
Вопросы:
1) Какие инструменты для моделирования/визуализации абстрактного конечного автомата есть кроме VisualState, Stateflow? Кто чем пользуется, опишите пожалуйста и поделитесь впечатлениями.
2) Какие инструменты для визуализация/моделирования/отладки уже написанного на языке С алгоритма есть?! Если применительно к мк AVR: в Proteus если загнать hex файл – не видно кода на Си и видны только входы/выходы с мк, при отладке в AVRStudio – код на Си виден, но не наглядно – нет временных диаграмм. И еще: может есть другие инструменты, без приложениям к мк?!
3) Есть ли что-нибудь из книг наподобие Miro Samek на русском для Cи?!

TMX писал

Про реализацию напишу позже

Ждем, интересны детали – уверен, что каждый по-разному генерирует код из графов.

Diz писал

Если интересно, могу рассказать и про вариант с иерархией

Интересно все и с иерархией и без. Если это возможно – то с простыми примерами, постановка задачи, с графом на 3-4 состояния, с кодом и с комментариями, желательно на Си для микроконтроллеров. Все в форум не войдет – может быть в rar(е) куда-нибудь выложите.
Спасибо.

Сообщение отредактировал Владимир_2010 - Mar 5 2009, 07:17

[TMX]

Интересно все и с иерархией и без. Если это возможно – то с простыми примерами, постановка задачи, с графом на 3-4 состояния, с кодом и с комментариями, желательно на Си для микроконтроллеров. Все в форум не войдет – может быть в rar(е) куда-нибудь выложите.
Спасибо.

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

К сожалению, на русском языке можно почитать Шалыто и Парондажанова. На английском есть пяток книг, но там самые азы - только Самек предлагает интересную реализацию.

Если нужно протокол сваять, то можно взять реализацию COCO/R для С и написать в L1 грамматике правила обработки, там генерится автомат, работает очень быстро. Правила обработки распознанных пакетов тоже удобно описывать автоматом, но на другом уровне.

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

Код

enum (RED, GREEN, YELLOW);

static char automaton_state = RED;

void super_auto(void)
{
  switch (automaton_state)
  {
    case RED:
      if (timer_flag)
      {
        output_control(RED_LAMP, OFF);
        output_control(GREEN_LAMP, ON);
        start_timer (GREEN_DELAY);
        automaton_state = GREEN;
      }
      break;
    case YELLOW:
...
...
  }
}

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

есть несколько модернизированных реализаций такого типа.

[_Pasha]

недостатки: если состояний много, то они могут перебираться долго. На самом деле здесь помог бы переход по изменяемой метке, типа GOTO STATE, но в С такого нет.
есть несколько модернизированных реализаций такого типа.

Позволю себе немного поправить Вас:

С недавних пор реализация оператора switch() отдана на откуп оптимизатору, т.е если структура приводится к таблице переходов - никакого перебора не будет. За таким подходом - будущее. В принципе, компиляторы смогут даже патчить входные значения, например

Код

switch(state)

{

case 1:

case 2:

case 14:

case 15:

}

Что мешает  в "рваных" вариантах и вычислять адрес в таблице перехода по какому-нибудь вспомогательному алгоритму?


По поводу вычисляемого goto - в гнусях такая фича ведь есть и давно. Если она войдет в "скрижали"...

[TMX]

Позволю себе немного поправить Вас:

С недавних пор реализация оператора switch() отдана на откуп оптимизатору, т.е если структура приводится к таблице переходов - никакого перебора не будет. За таким подходом - будущее. В принципе, компиляторы смогут даже патчить входные значения, например

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

Чтобы не полагаться на компилятор используются модернизированные методы:

выше упоминалась ссылка http://www.embedded.com/2000/0012/0012feat1.htm
там Martin Gomez вручную забивает таблицу переходов: http://i.cmpnet.com/embedded/gifs/2000/001...t1_listing1.gif
Недостатки: во-первых, надо записывать в трех местах и легко ошибиться.
Во-вторых, вообще не понятно, зачем такая громоздкая реализация: состояние храниться в виде номера, функции и указателя на функцию. по номеру выбирается ссылка на функцию состояний и вызывается сама функция. Реализация требует и память и стек.
Гораздо проще хранить состояние в виде ссылки на функцию. Память не используется, стек используется. Ошибиться при переходе сложнее.

Что касается визуализации, то я имел в виду следующее. Автомат описывается на С.
Перед компляцией запускается утилита, которая парсит C-файл, находит все, относящееся к автомату - состояния, события, переходы, иерархию - после чего рисует красивый statechart. Который можно окинуть взглядом и убедиться, что все в порядке.
Вот, для примера Pelican (светофор) от Самека:
[attachment=30421:pelican.pdf]

не слышал о таком, есть программа, которая flowchart генерирует.
Писать программу без картинки - если получается, тогда зачем картинка?

[_Pasha]

там Martin Gomez вручную забивает таблицу переходов

no comment

 в виде номера, функции и указателя на функцию. по номеру выбирается ссылка на функцию состояний и вызывается сама функция. Реализация требует и память и стек.


Писать программу без картинки - если получается, тогда зачем картинка?

1. А что? Дорого? Зато может способствовать уменьшению количества функций

2.Например, для повышения уровня языка реализации до проблемно-ориентированного  http://www.citforum.ru/internet/xml/graphml/

[TMX]

no comment

Возможно, я не совсем понятно выразился - Gomez забивает не всю таблицу переходов автомата, а только одномерный массив jump table, указателей на функции состояний. Там в самом начале листинга можно ее увидеть.
В любом случае это не дает преимуществ по сравнению с прямым присвоением:

Код

void(*state_pointer)(void) = RED_state;
void main (void)
{
  while(1)
  {
    state_pointer();
  }
}

void RED_state (void)
{
      if (timer_flag)
      {
        output_control(RED_LAMP, OFF);
        output_control(GREEN_LAMP, ON);
        start_timer (GREEN_DELAY);
        state_pointer = GREEN_state;
        return;
      }
              if (button_flag)
......................
}

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

По поводу объема: в 8-битных процессорах если указатель занимает 2 байта, то каждое присвоение требует 2 команды ассемблера. Соответственно для автомата на 50 состояний и 150 переходов потребуется 300 команд в ПЗУ (600Б для AVR), для switch с переменной состояния типа char потребуется 300Б ПЗУ на переходы, для Gomez-технологии потребуется 300Б на переходы и 100Б на jump_table, итого 400Б. Для 16-ти и 32-х битных объем switch и присвоения указателей практически одинаков, а для Gomeza все равно дополнительно требуется место для jump table.

1. А что? Дорого? Зато может способствовать уменьшению количества функций
2.Например, для повышения уровня языка реализации до проблемно-ориентированного http://www.citforum.ru/internet/xml/graphml/

1. За счет чего? C использованием switch вообще одна функция.
2.Обычно проблему снаала описывают, а потом реализуют.

если еще есть интерес, могу продолжить про реализации...

[TMX]

Недостатки прямого присваивания значения переменной состояния, типа

Код

state = NEW_state

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

Код

void main (void)
{
static char state = STATE_X;
  while(1)
  {
    state = state_function(state);
  }
}

char state_function (char state)
{
  switch(state)
  {
      case STATE_X:
        if (event)
        {
          return STATE_Y;
        }
        else
          return STATE_X;
      case STATE_Y:
        ...
      case STATE_Z:
        ...
  }
}

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