большие и вложенные государственные машины

Question

У меня есть машина состояний в системе реального времени с очень небольшим (3) состоянием.

typedef enum {
    STATE1,
    STATE2,
    STATE3
} state_t;

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

typedef enum {
    STATE1,
    STATE1_PREPARE_TRANSITION_TO_STATE2,
    STATE1_DO_TRANSITION_TO_STATE2,
    STATE1_PREPARE_TRANSITION_TO_STATE3,
    STATE1_DO_TRANSITION_TO_STATE3,
    STATE2,
    ...
} state_t;

или я создаю вложенную машину состояний для соответствующих основных состояний:

typedef enum {
    STATE1_NOT_ACTIVE,
    STATE1_NORMAL,
    STATE1_PREPARE_TRANSITION_TO_STATE2,
    STATE1_DO_TRANSITION_TO_STATE2,
    STATE1_PREPARE_TRANSITION_TO_STATE3,
    STATE1_DO_TRANSITION_TO_STATE3
} sub_state1_t;
...

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

Я бы хотел избежать сложного кода, который должен обрабатывать несколько параллельных состояний, например:

if ((global_state == STATE1) &&
    (sub_state_1 == STATE1_DO_TRANSITION_TO_STATE2))
{
    ...
    if (transition_xy_done(...))
    {
        global_state = STATE2;
        sub_state_1 = STATE1_NOT_ACTIVE;
        sub_state_2 = STATE2_NORMAL;
    }
}

Каков общий наилучший подход к такой проблеме: много маленьких и вложенных машин состояний (со многими недопустимыми комбинациями), одна большая машина состояний или что-то еще?

Answer 1

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

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

Answer 2

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

Существует несколько платформ для C ++, которые моделируют иерархические конечные автоматы - HSM - (как звучит ваша идея вложенного конечного автомата), но единственная, о которой я знаю, которая поддерживает прямой C, - это Quantum Framework , и я думаю, что покупка в этом, вероятно, будет означать достойный уровень приверженности (то есть, вероятно, это не простое изменение). Однако, если вы хотите изучить эту возможность, Самек написал много статей ( и книгу ) о том, как поддерживать HSM в C.

Однако, если вам не нужны некоторые более сложные части моделей HSM (например, события, которые не обрабатываются «самым внутренним» состоянием), всплывают, чтобы, возможно, обрабатываться родительскими состояниями, полный ввод и выйдите из поддержки всей иерархии состояний), тогда довольно просто поддерживать вложенные конечные автоматы так же, как полностью независимые конечные автоматы, которые запускаются и останавливаются при входе / выходе из родительского состояния.

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

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

Answer 3

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

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

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

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

Чтобы привести упрощенный пример:

#define MyDataSIZE 10

void UpdateStateMachine(void)
{
    static enum {BeginSTATE, DoStuffSTATE, EndSTATE} State = BeginSTATE;
    static unsigned int Counter = 0;
    static unsigned int MyData[MyDataSIZE];

    switch(State)
    {
        default:
        case BeginSTATE:
            /* Some code */
            if(/* Some condition*/)
                {State = DoStuffSTATE;}
            break;
        case DoStuffSTATE:
            /* Some actions on MyData[Counter] */
            if(/* Some condition*/)
                {State = EndSTATE;}
            break;
        case EndSTATE:
            /* Some code */
            if(/* Some condition*/)
            {
                Counter++;
                if(Counter >= MyDataSIZE)
                    {Counter = 0;}
                State = BeginSTATE;
            } /* if */
            break;
    } /* switch */
} /* UpdateStateMachine() */

Answer 4

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

Еще один недостаток большого SM - большая таблица переходов, поэтому поиск занимает больше времени.

Answer 5

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

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

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

Также, как вы предложили, работа с несколькими конечными автоматами заставит вас отправлять больше параметров, выполняя более одного теста для каждого состояния и т. Д. '...

Что касается будущих ожиданий, я верю в ЯГНИ .

Answer 6

Почему бы вам не использовать шаблон состояния ?