Как реализовать конечный автомат для вашего встроенного проекта

Как реализовать конечный автомат для вашего встроенного проекта

Когда вы работаете со встроенным устройством, вы обычно начинаете с простого. Основной цикл, который что-то делает.
По мере того, как вы начинаете добавлять дополнительные функции, сложность кода растет. Вы добавляете больше if, больше циклов, больше условий и даже, не дай бог, переключаете операторы.
Это момент, когда вы должны сделать паузу и спросить себя: "Правильно ли я поступаю?"

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

Представляю вам: The State Machine

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

Что такое государственная машина?

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

Конкретный FSM определяется набором его состояний и переходов между ними.

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

Наивный подход

Определим интерфейс для состояния:

class IState 
{ 
  public:
    virtual IState* Run() = 0; 
}

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

class BootState :: IState 
{ 
  public: 
    IState* Run() 
    { 
      // Do something 
      return new StandByState(); 
    } 
}

Основной цикл должен выглядеть примерно так:

void main() 
{ 
  IState *currentState = new BootState();
  while(true)
  { 
    IState *nextState = currentState->Run();
    delete currentState;
    currentState = nextState; 
  } 
}

Просто, не так ли?

Это решение довольно простое, и вы можете найти множество его вариаций в нескольких открытых источниках, но эта простота скрывает несколько проблем.

Ремонтопригодность

Представьте себе систему с 10 состояниями, каждое из которых реализовано так, как я описал ранее. Теперь представьте, что вы пытаетесь объяснить кому-то, как выглядит график, не отслеживая/отлаживая код.

Кроме того, представьте, что каждое состояние может привести к нескольким состояниям…

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

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

OCPish

На первый взгляд кажется, что этот код соответствует принципу Open-Closed.
На самом деле это не так.

Что, если вы хотите добавить состояние в середину графика? Для этого вам придется изменить существующее состояние.

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

Это много существующего кода, который нужно изменить

объем памяти

Да, ты меня слышал. Во встроенной системе вам нужно позаботиться о памяти.

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

Итак, что мы узнали?

Мы хотим, чтобы наш мысленный граф конечного автомата был легким для понимания без трассировки/отладки.
Мы хотим, чтобы наш конечный автомат позволял нам очень легко добавлять состояния и переходы, при этом сами состояния соответствовали SOLID.
И мы хотим сделать это с правильным распределением памяти.

Давайте попробуем это снова

State Machine строится из состояний и переходов.
Итак, давайте добавим определение перехода:

class ITransition { }

Теперь давайте немного изменим IState:

class IState 
{ 
  public:
    virtual ITransition* Run() = 0; 
}

Теперь каждое состояние возвращает переход. Кто-то должен «знать», куда приведет этот переход.

Нам нужна карта, которая связывает каждый переход со следующим состоянием. Это идеальная работа для самой State Machine.

Итак, теперь давайте добавим класс для конечного автомата:

// StateMachine.h 
using <map> // map from STL 
class StateMachine 
{ 
  public: 
    StateMachine(std::map<ITransition*, IState*> *transitions, IState* initialState); 
    void Run(); 
  private: 
    std::map<ITransition*, IState*> *_transitions;
    IState* _currentState; 
}
// StateMachine.cpp 
using <StateMachine.h>
StateMachine::StateMachine(std::map<ITransition*, IState*> *transitions, IState* initialState) 
{ 
  _transitions = transitions;
  _currentState = initialState;
} 
void StateMachine::Run()
{ 
  ITransition *transition;
  
  while(true) 
  { 
    transition = _currentState->Run();
    _currentState = (*_transitions)[transition]; 
  } 
}

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

void main()
{ 
  BootState initialState;
  std::map<ITransition*, IState*> transitions; 
  /* BootState -> */ transitions[ConfiguredTransition::GetInstance(), new StandByState()]; 
  ... 
  StateMachine *stateMachine = new StateMachine(&transitions, &initialState);
  stateMachine->Run(); 
}

Это лучше?

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

Ментальная модель

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

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

Легко добавить

Принцип единой ответственности

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

Каждый компонент отвечает за свою работу.

Открытый закрытый принцип

Вот когда все усложняется... Добавление нового состояния требует создания нового класса. Включение нового состояния требует, чтобы вы добавили его на карту перехода. Это похоже на нарушение этого принципа. И это. Но единственное, что не может быть OCPied, — это заказ. В данном случае это так. Заказ сам по себе не может быть OCP — так как нужно «знать» другие компоненты в системе.

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

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

объем памяти

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

Поскольку все наши состояния известны (определение FSM), имеет смысл выделить их все и путешествовать по ним.

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

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

Проблема детализации

Все ли является государством? Нужно ли всем управлять в государственной машине?

Это интересные вопросы, которые начинают появляться по мере того, как ваша система продолжает расти.

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

Лучшим решением является сопоставление состояний высокого уровня. Основные столпы системы. Основные потоки.
Внутренне каждое из этих состояний может быть простым потоком (ifs и все) или небольшим конечным автоматом.

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

Что дальше?

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

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

Первоначально опубликовано на blog.house-of-code.com 30 января 2016 г.