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

Грамотная архитектура играет ключевую роль при разработке любого программного продукта. Корни большинства распространенных проблем с производительностью, расширяемостью или понятностью кода растут именно из ее отсутствия. Отсутствие строго определенной структуры проекта лишает разработчиков возможности мыслить абстракциями, понимать написанный коллегой код с первого взгляда и предугадывать место возникновения ошибки. А в некоторых случаях человек может запутаться даже в своем собственном коде, перенасыщенном сущностями и компонентами. Но практически каждый программист рано или поздно, сам ли или с помощью умной книжки, знакомится с решениями, которые хороши вне зависимости от контекста. Они настолько эффективны и универсальны, что находят место в решении множества задач, и... Да, знаю, можно не продолжать, все уже и так поняли, что я о шаблонах проектирования. Одни на них молятся, другие находили среди них свои велосипеды. Некоторые утверждают на собеседовании, что изучили их вдоль и поперек и уличили в полной бесполезности. Но все, так или иначе, слышали о них. Сегодня речь пойдет об одном из паттернов - "Состояние". А точнее, о конечных автоматах. Даже если вы относитесь к последней из перечисленных выше групп, вы наверняка сталкивались со следующим инструментом:

Аниматоры в Unity построены как раз на конечных автоматах. Каждая анимация группы объектов представлена в виде состояния. Условия и порядок переходов между ними определяется в аниматоре, который является конечным автоматом. Также, неоднократно поднималась тема использования конечных автоматов для описания логики работы объектов со сложным поведением. AI ботов, управление главным героем, вот это все.

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

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

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

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

• Многие баги становятся просто невозможны, потому что мы строго определяем условия переходов. Мы точно не попадем в состояние Play, пока состояние WaitMatch не получит сигнал "match_ready", а если мы захотим вернуться в лобби, мы сначала отправим серверу команду об этом, и только после сигнала "room_left" выполним переход.

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

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

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

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

Итак, мы имеем 2 сущности:

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

 public class FSM {   private AState currentState;   public FSM(AState initState) => ChangeState(initState);      private void ChangeState(AState newState)   {     if (newState == null) return;     currentState?.Exit();     currentState = newState;     currentState.Enter();   }   public void Signal(string name, object arg = null)   {     var result = currentState.Signal(name, arg);     ChangeState(result);   } }

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

public class AState{  public virtual void Enter() => null;  public virtual void Exit() => null;  public virtual AState Signal(string name, object arg) => null;}

А в самих состояниях мы просто описываем логику

public class SLoad : AState{    public override void Enter()    {        Game.Data.Set("loader_visible",true);        var load = SceneManager.LoadSceneAsync("SceneGameplay");        load.completed+=a=>Game.Fsm.Signal("scene_loaded");    }    public override void Exit()    {        Game.Data.Set("loader_visible",false);    }        public override AState Signal(string name, object arg)    {        if (name == "scene_loaded")            return new SLobby();        return null;    }    }

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

public class SMessage : AState{    private string msgText;    private AState next;    public SMessage(string messageText, AState nextState)    {        msgText = messageText;        btnText = buttonText;        next = nextState;    }        public override void Enter()    {        Game.Data.Set("message_text", msgText);        Game.Data.Set("window_message_visible",true);    }    public override void Exit()    {        Game.Data.Set("window_message_visible",false);    }        public override AState Signal(string name, object arg)    {        if (name == "message_btn_ok")             return next;        return null;    }}

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

...case "iap_ok":return new SMessage("Item purchased! Going back to store.", new SStore());...

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

public class ButtonFSM : MonoBehaviour, IPointerClickHandler{    public string key;        public override void OnPointerClick(PointerEventData eventData)    {        Game.Fsm.Signal(key);    }}

Иными словами, мы при клике по кнопке(на самом деле, любому CanvasRenderer) передаем соответствующий сигнал в автомат. При переходе между состояниями мы можем любым удобным нам способом включать и выключать разные Canvas, менять маски, используемые в Physics.Raycast и даже иногда менять Time.timeScale! Как бы ужасно и бескультурно это ни казалось на первый взгляд, пока сделанное в Enter отменяется в Exit, оно гарантированно не может доставить каких-либо неудобств, так что вперед! Главное - не переусердствуйте.

Здравствуйте! Меня зовут Александр, я работаю инженером-программистом микроконтроллеров.

Пишу на С/С++, причем предпочитаю плюсы, ибо верую в их эволюционную неизбежность в embedded.

Мир встроенного ПО, язык С++ динамично развиваются, поэтому разработчикам важно не отставать и поддерживать свои скиллы и наработки актуальными моменту.

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

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

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

// Transition table definitionusing transitions =  transition_table<  /*  State       Event       Next       */  tr< initial,    start,      running    >,  tr< running,    stop,       terminated >>;};// State machine objectusing minimal = state_machine<transitions>;minimal fsm;//...and then callfsm.process_event(start{});fsm.process_event(stop{});

А если добавить к этому перенос части функциональности кода в компайл тайм, заявленную автором потокобезопасность, улучшенные по сравнению с Boost::MSM выразительность, читаемость кода и скорость сборки, header only модель библиотеки, то - надо брать, решил я.

Вот только попытка собрать и запустить даже простейший пример на STM-ке закончилась матерком компилятора: "cannot use 'typeid' with "-fno-rtti" и "exception handling disabled".

Да, все так. Более того, помимо отключенной поддержки RTTI и исключений, у меня также выставлены флаги -fno-cxa-atexit, -fno-threadsafe-static. А еще в линкере применены настройки --specs=nano.specs (используем урезанную версию стандартной библиотеки с++ newlib-nano), --specs=nosys.specs (применяем легковесные заглушки для системных вызовов).

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

Делать нечего, поступимся принципами, включим поддержку RTTI, а вместо throw в исходниках автора проставим заглушки.

На этот раз все собралось. Вот только при использовании тулчейна gcc-arm-none-eabi-9-2020-q2-update и уровне оптимизации -O3, размер исполняемого файла превысил 200Кб.

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

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

Итак, с наскоку взять высоту не удалось, и я на некоторое время переключился на другие задачи. Но красота идеи меня не отпускала, и на днях я все-таки решился "достучаться до небес" - написать extra light embedded версию FSM из упомянутого доклада самостоятельно.

Уточню свои хотелки:

• Оперировать состояниями, эвентами и действиями как пользовательскими типами.

• Таблицу переходов реализовать в виде шаблонного параметра

• Перетащить что возможно в компайл тайм

• Асинхронно и атомарно постить эвенты

• Переключать состояния за константное время

• Выйти в итоге на приемлемый по меркам встроенного ПО размер кода

• Повторить header only модель библиотеки

Забегая вперед, скажу, что в итоге что-то получилось и даже взлетело.

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

Первым делом опишем базовые сущности:

struct StateBase{};template <base_t N, typename Action = void>struct State : StateBase{  static constexpr base_t idx = N;  using action_t = Action;  };

Здесь и далее base_t - платформозависимый тип, машинное слово. В моем случае это unsigned int.

Состояния пусть будут двух типов - пассивное, в котором никаких действий не происходит, и активное - при нахождении в котором будет выполнятся переданный шаблонным параметром функтор, action_t.

Цель статического члена idx уточню далее по тексту.

struct EventBase{};template <base_t N>struct Event : EventBase{  static constexpr base_t idx = N;};

Элементарная структура, все ясно.

Действие при наступлении события и смене состояний:

struct action{  void operator()(void){    // do something};

Безусловно, сигнатура operator() может и должна варьироваться от задач приложения, пока же для упрощения остановимся на самом легковесном варианте.

Сторож состояния:

enum class Guard : base_t{  OFF,  CONDITION_1,  CONDITION_2,  //etc.};

Идея сторожа - допустить переход в новое состояние, только если в данный момент выполнения программы текущее значение сторожа соответствует заданному пользователем значению в типе перехода/transition-a. Если такого соответствия нет, то переход в новое состояние не происходит. Но тут возможны варианты. Например, все же переходить, но не выполнять действие, переданное в состояние. Up to you.

Итак, пока все тривиально. Идем дальше.

Переход:

struct TrBase{};template <typename Source,          typename Event,          typename Target,          typename Action,          Guard G,          class =          std::enable_if_t<std::is_base_of_v<StateBase, Source>&&          std::is_base_of_v<EventBase, Event> &&          std::is_base_of_v<StateBase, Target>>          >  struct Tr : TrBase{  using source_t = Source;  using event_t  = Event;  using target_t = Target;  using action_t = Action;    static constexpr Guard guard = G;};

Структура Tr тоже элементарна. Она параметризуется типом исходного состояния - Source, типом события Event, по наступлению которого произойдет переход в целевое состояние Target, и типом Guard.

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

Таблица переходов:

struct TransitionTableBase{};template<typename... T>struct TransitionTable : TransitionTableBase{    using test_t = typename NoDuplicates<Collection<T...>>::Result;    static_assert(std::is_same_v<test_t, Collection<T...>>,                "Repeated transitions");    using transition_p = type_pack<T...>;    using state_collection = typename NoDuplicates   <Collection<typename T::source_t... ,typename T::target_t...>   >::Result;    using event_collection = typename NoDuplicates  <Collection<typename T::event_t...>    >::Result;    using state_v = decltype(get_var(state_collection{}));  using event_v = decltype(get_var(event_collection{}));  using transition_v = std::variant<T...>;};

Нуу, тут я набросил на вентилятор, конечно. Хотя все не настолько пугающе, как выглядит.

Структура TransitionTable параметризуется списком переходов/transition-ов, которые собственно и описывают всю логику конечного автомата.

Первым делом нам необходимо подстраховать себя от копипаста и просигналить при компиляции, что у нас повторы в списке. Исполняем это с помощью алгоритма NoDuplicates из всем известной библиотеки Loki. Результирующий тип под псевдонимом test_t сравниваем в static_assert-e с исходным списком переходов.

Далее, допуская что static_assert пройден, параметризуем некую структуру type_pack списком переходов и выведенному типу назначаем псевдоним transition_p. Структура type_pack, а также современные алгоритмы и методы по работе со списками типов собраны в файле typelist.h. Данный хедер написан под чутким руководством этого продвинутого парня.

Тип transition_p понадобится нам далее в конструкторе класса StateMachine.

Следом проходим по списку переходов, вытаскиваем, очищаем от повторов и сохраняем в отдельные коллекции состояния и эвенты. Эти коллекции alias-им как state_collection и event_collection соответственно.

К чему эта эквилибристика?

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

Удобным вариантом для этой цели является std::variant (тафтология умышленна).

Последовательно параметризуем std::variant списком переходов (выведенному типу назначим псевдоним transition_v); списком состояний и списком эвентов и назначаем для удобства псевдонимы state_v и event_v соответственно.

Тут нюанс. Чтобы вывести transition_v нам достаточно пробросить в шаблонный параметр std::variant variadic pack (T...) из шаблонного параметра класса TransitionTable.

А вот чтобы вывести state_v и event_v мы используем

template<typename... Types>constexpr auto get_var (th::Collection<Types...>){return std::variant<Types...>{};}

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

Оставшихся к этому моменту читателей я не обрадую - начинается основной замес.

Целиком приводить класс StateMachine не буду, он громоздок, прокомментирую его для удобства восприятия по частям.

template<typename Table>class StateMachine{//other stuffprivate:using map_type =std::unordered_map < Key, transition_v, KeyHash, KeyEqual>;Key key;map_type transitions;};

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

Объект типа Key хранит у себя значения индексов состояния и эвента:

struct Key{  base_t state_idx = 0;  base_t event_idx = 0;};

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

template<typename Table>class StateMachine{//other stuffprivate:using queue_type =  RingBufferPO2 <EVENT_STACK_SIZE, event_v, Atomic>;    queue_type events;};

events - очередь, в которую будут прилетать эвенты. Так как это чисто рантаймовая история, необходимо избежать динамических аллокаций. Поэтому реализуем ее на базе статического кольцевого буффера RingBufferPO2, который я позаимствовал здесь (отличная для своего времени работа!).

Помимо указанных контейнеров, в объекте типа StateMachine мы будем хранить текущее состояние/state и значение сторожа/guard:

template<typename Table>class StateMachine{//other stuffprivate:state_v current_state;Guard guard = Guard::OFF;};

Саспенс уже не за горами.

template<typename Table>class StateMachine{public:using transition_pack = typename Table::transition_p;StateMachine(){  set(transition_pack{});} // other stuff};

В конструкторе метод set принимает аргументом объект с информацией о списке переходов, пробегается по нему, достает инфо о каждом состоянии и эвенте, заполняет контейнер transitions, а также запоминает начальные состояние и значение сторожа:

template <class... Ts>void set (type_pack<Ts...>){(set_impl(just_type<Ts>{}), ...);};template <typename T>void set_impl (just_type<T> t){using transition = typename decltype(t)::type;using state_t = typename transition::source_t;using event_t = typename transition::event_t;Guard g = transition::guard;Key k;k.state_idx = state_t::idx;k.event_idx = event_t::idx;transitions.insert( {k, transition{}} );if (0 == key.state_idx) {key.state_idx = k.state_idx;guard = g;current_state = state_t{};}}

Итак, объект StateMachine сконструирован, пора его как-то шевелить.

Но перед этим забудем как страшный сон суммируем что уже рассмотрели к этому моменту:

• Определили типы компонентов конечного автомата: состояние/state, событие/event, действие/action, сторож/guard

• Определили тип переход/transition, который должен параметризоваться типами source state, event, target state, guard.

• Определили тип таблицы переходов. В качестве шаблонных параметров ему передается список переходов/transition-ов, который и определяет алгоритмы работы автомата.

• При компиляции в классе TransitionTable, на основе std::variant выводятся типы-коллекции переходов, состояний и эвентов, которые впоследствии при конструировании объекта StateMachine инстанцируются и сохраняются в контейнеры, с которыми уже можно работать в рантайме.

Стержневая идея моей имплементации автомата такова (вдохнули): при наступлении события, мы достаем из его типа индекс (idx), объединяем его с индексом текущего состояния в объекте Key, по которому в контейнере transitions находим нужный нам переход, где получаем знания о целевом состоянии, стороже и действии, которое требуется выполнить в этом переходе, а также сверяем значения сторожа с текущим, для подтверждения или отмены перехода/действия(выдохнули).

Теперь рассмотрим методы API нашего автомата, реализующие эту логику.

Переключать состояния мы можем двумя способами: вызывать немедленный переход методом fsm.on_event(event{}) (шаблонная версиия fsm.on_event<Event>() если тип события известен на этапе проектирования), или можем складывать события в очередь методом fsm.push_event(event{}), чтобы потом, например в основном цикле, разобрать ее методом fsm.process(). Также, если в состояние передано какое-то действие, то мы можем вызывать его методом fsm.state_action().

Рассмотрим их детальнее, начиная с последнего

template <typename... Args>void state_action (const Args&... args){state_v temp_v{current_state};    auto l = [&](const auto& arg){      using state_t =  std::decay_t<decltype(arg)>;    using functor_t = typename state_t::action_t;        if constexpr (!std::is_same_v<functor_t, void>){    functor_t{}(args...);      }  };    std::visit(l, temp_v);}  

В методе мы создаем локальную переменную типа std::variant<State...> temp_v и инициализируем ее текущим состоянием. Далее определяем лямбду, которая послужит аргументом в методе std::visit.

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

Знаю, что иногда лямбда может юзать кучу, но похоже, это не мой случай. Поправьте меня, пожалуйста, если я заблуждаюсь. В этом случае не сложно будет заменить лямбду на callable object.

template <typename Event,class = std::enable_if_t<std::is_base_of_v<EventBase, Event>>>void on_event(const Event& e){Key k;  k.event_idx = e.idx;  k.state_idx = key.state_idx;  on_event_impl(k);}void on_event_impl (Key& k){transition_v tr_var = transitions[k];    Key &ref_k = key;  Guard &ref_g = guard;  state_v &ref_state = current_state;    auto l = [&](const auto& arg){    using tr_t =  std::decay_t<decltype(arg)>;    using functor_t = typename tr_t::action_t;        if ( GuardEqual{}(ref_g, tr_t::guard) ){          using target_t = typename tr_t::target_t;            ref_k.state_idx = target_t::idx;      ref_state = target_t{};            functor_t{}();      }   };      std::visit(l, tr_var);}

Здесь, как я уже описывал, мы достаем индекс из эвента, объединяем его в Key с индексом текущего состояния, и в качестве ключа передаем в приватный метод on_event_impl(Key& k).

Там мы по принятому ключу достаем из контенера transitions объект типа std::variant<Tr...> и инициализируем им локальную переменную tr_var. Ну а далее - логика, схожая с предыдущим примером. Вызываем std::visit c tr_var и лямдой l, в которой из типа Tr получаем сведения о состоянии, в которое нужно перейти (target_t), стороже (tr_t::guard)и типе действия (functor_t) к исполнению.

Сверив значение сторожа перехода с текущим сторожем, мы или оcуществляем переход, инстанцируя и вызывая functor_t, и сохраняя target_t в переменную с текущим состоянием(current_state), или возвращаемся в исходное состояние. Где ждем смены значения сторожа и нового события.

template <unsigned int N>void push_event (const Event<N>& e){  events.push_back(e);}

Тут все просто.

void set_guard (const Guard& g){  guard = g;}

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

void process (void){    state_action();    auto it = transitions.begin();    Key k;  k.state_idx = key.state_idx;    for (uint32_t i = 0; i != events.size(); ++i){        auto v = events.front();     auto l = [&](const auto& arg){      using event_t =  std::decay_t<decltype(arg)>;      k.event_idx = event_t::idx;      it = transitions.find(k);    }        std::visit(l, v);        if ( it != transitions.end() ){            events.pop_front();      on_event_impl(k);      return;        } else {      events.push_back(v);      events.pop_front();    }  }}

При вызове метода мы первым делом выполняем некое полезное действие (если не void), переданное в состояние, state_action().

Ну а далее пробегаемся по очереди эвентов и просто воспроизводим логику, уже описанную для метода fsm.on_event(event{}).

Разумеется, работу с событиями можно значительно ускорить, при этом расширив функционал автомата. Тип Event модернизируем

template <base_t N, base_t Priority>struct Event : EventBase{  static constexpr base_t idx = N;  static constexpr base_t pri = Priority;};

Теперь мы можем не пушить все события в одну очередь, а завести, скажем, std::array<queue_t, PRIRITY_NUM>, где индексом ячейки будет служить приоритет события. Тогда у нас получится приняв эвент, вытащить его приоритет, по нему, как по индексу за константное время попасть в нужную очередь событий, которая будет гораздо меньше, чем общая и быстрее в обработке.

И, что не менее важно, так мы сможем прыгать между состояниями не по очередности принятых эвентов, но по их приоритету.

На самом деле в следующей версии своего FSM у меня так и реализовано, но здесь я привожу упрощенный вариант.

Хорошо, каков же будет практический результат этой разнузданной шаблонной вакханалии?

struct green_a {/*toogle green led every 50ms*/}struct yellow_a {/*toogle yellow led every 50ms*/}struct red_a {/*toogle red led every 50ms*/}struct green_f {/*toogle green led every 150ms*/}struct yellow_f {/*toogle yellow led every 150ms*/}struct red_f {/*toogle red led every 150ms*/}using STATE_A(green_s, green_f);using STATE_A(yellow_s, yellow_f);using STATE_A(red_s, red_f);using EVENT(green_e);using EVENT(yellow_e);using EVENT(red_e);using fsm_table = TransitionTable    <    Tr<green_s, yellow_e, yellow_s, yellow_a, Guard::NO_GUARD>,    Tr<yellow_s, red_e, red_s, red_a, Guard::NO_GUARD>,    Tr<red_s, green_e, green_s, green_a, Guard::NO_GUARD>    >;int main(void){  //some other stuff  StateMachine<fsm_table> fsm;  fsm.push_event(red_e{});  fsm.push_event(yellow_e{});  fsm.push_event(green_e{});  while (1){    fsm.process();  }}

В этом примере структуры типа color_a(ction) - это действия при переходе; color_f(unctor) - функторы, которые будут выполняться каждый раз при заходе в стейт, ну и далее понятно.

Объявляем стейты, эвенты, переходы, таблицу переходов. Конструируем из класса StateMachine<fsm_table> наш конечный автомат fsm. Пушим события, заходим в while и наблюдаем аквасветодискотеку на нашей отладке.

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

using even_t = Event<1, 15>;

using state_t = State<1, state_functor>;

Очевидно, почему это плохо. Ручная индексация - практически неизбежные ошибки и очепятки.

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

#define STATE_A(str, act) str = State<name(#str), act>#define EVENT(str) str = Event<name(#str)>constexpr base_t name (const char* n){    base_t  res = 0;    for (base_t i = 0; n[i] != '\0'; i++){        char data = n[i];        for (base_t j = sizeof (char) * 8; j > 0; j--){            res = ((res ^ data) & 1) ? (res >> 1) ^ 0x8C : (res >> 1);      data >>= 1;    }  }  return res;};

После крайнего проекта на работе у меня на руках осталась отладка NUCLEO-H743ZI2, на ней я и запилил тестовый вариант (забирайте здесь).

С оптимизацией -O3 реализация приведенного примера (только сам FSM) заняла 6,8Кб, с HAL-ом и моргалками - 14,4Кб.

Конечно же, пока это не более чем эксперимент, проверка концепции. Но агрегат завелся, черт его дери.

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

Спасибо за внимание!

Сегодня я расскажу вам про довольно простую, но интересную реализацию многопоточности в HTTP-сервере без создания потока для каждого клиента. На мое удивление информацию про такую реализацию я нашёл с трудом, поэтому решил поделиться с вами. Начнем с описание проблемы.

Проблемы решения "один поток = один клиент"

Проблемы, которые описаны ниже, справедливы как для потоков, так и для процессов, поэтому "один поток = один клиент" также можно расценивать как и "один процесс - один клиент" в данном контексте.

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

Проблема вторая - один поток занят только одним клиентом. В связи с этим мы получаем неэффективное использование ресурсов. (поток может простаивать, пока ждёт события от клиента)

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

Решение, которое я приведу ниже, закрывает эти проблемы.

Решение есть

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

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

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

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

На каждое состояние у нас есть свой хэндлер. Рассмотрим пример. У клиента четыре состояния: readRequest, generateResponse, sendResponse и closeConnection (чтение запроса, создание ответа, отправка ответа и закрытие соединения, соответственно). На каждое состояние мы имеем хэндлер. readRequest читает и парсит запрос и, в зависимости от успеха чтения и парсинга (например, в зависимости от того, что вернула функция чтения запроса), переключает состояние либо на generateResponse, либо на closeConnection. generateResponse отвечает за генерацию ответа и переключает состояние клиента на sendResponse. sendResponse отправляет ответ клиенту и либо возвращет клиента на состояние readRequest, либо переключает на closeConnection. closeConnection, в свою очередь, просто отключает клиента и удаляет его.

Этот примитивный пример показывает суть принципа. Мы можем добавлять новые состояния клиентов (причем в коде делается это довольно просто: мы просто реализуем новый метод) и переключать их как угодно в зависимости от условий. Вы можете с легкостью разбивать состояние на два отдельных, если чувствуете в этом необходимость. В нашем примере парсинг запроса включен в состояние readRequest и его можно вынести в отдельное состояние - parsingRequest, например.

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

Довольно неплохая лекция на тему конечных автоматов. Также информации об этом методе в интернете полно, поэтому заострять внимание на деталях мы не будем.

ThreadPool (или пул потоков)

Пул потоков как таковым пулом потоков не является. Скорее он представляет собой пул (в виде очереди, например) задач для этих потоков.

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

Если наш клиент отправил нам только часть запроса, поток в сервере формата "один клиент=один поток" будет ожидать оставшуюся часть запроса. (то есть простаивать) В нашем же случае поток обработает часть запроса и пойдет обрабатывать следующих клиентов, если такие есть (простаивания потока не происходит).

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

Заключение

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

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

На этом все. Делитесь своими вариантами, предложениями, дополнениями и критикой в комментариях! Благодарю за прочтение:)

Несколько полезных ссылок:

http://personeltest.ru/aways/habr.com/ru/post/260065/

http://personeltest.ru/aways/habr.com/ru/company/latera/blog/273283/

http://www.aosabook.org/en/nginx.html

Введение

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

Термин <<автомат>> в основном используется в двух аспектах:

• техническом;

• математическом.

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

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

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

В данной работе рассматриваются цифровые сигналы и двоичная логика на базе логических элементов.

Применение

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

Другое важнейшее применение теории автоматов математически строгое нахождение разрешимости и сложности задач.

Автоматы Мура и Мили широко применяются при проектировании цифровых устройств на основе программируемых логических интегральных схем (ПЛИС). Наличие минимальной выходной задержки, связанной с переключением выходного регистра, отсутствие нестабильности переходного процесса на выходе автомата, отсутствие сквозного распространения сигнала через комбинационную схему от входа до выхода автомата, простота описания на языках описания аппаратуры делает автомат Мура практически незаменимым. Также автоматы Мура и взаимодействующие автоматы Мили используются в генетическом программировании.

Описание проблемы

Построение цифрового автомата -- довольно трудоёмкий процесс. Можно выделить следующие этапы разработки ЦА:

1) Очень часто разработка ЦА начинается с реализации графа, который отражает закладываемую логику в простом и понятном для человека виде.

2) Оптимизация графа -- с этой задачей человек может справиться довольно быстро.

3) Определение разрядности памяти. Минимальное число триггеров можно вычислить по формуле:

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

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

5) Составление таблицы состояний-переходов.

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

7) Преобразование уравнений для согласования с элементной базой.

8) Разработка электрической схемы.

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

Решение

Была разработана программа для построения цифровых автоматов. На вход программа принимает граф. В программе граф представляется в наборе вершин и рёбер(вершина, входной сигнал, вершина для перехода). Итерируясь по рёбрам составляются таблицы истинности для каждого разряда в СКНФ и СДНФ. Методом Куайна-Мак-Класки минимизируются обе формы уравнений. Для каждого разряда выбирается выражение с минимальным количеством логических операций <<И>>, <<ИЛИ>>. Общее количество этих операций является критерием качества данной кодировки.

Количество возможных вариантов задания состояний можно рассчитать зная разрядность памяти(M) и количество состояний(S).

Количество кодов:

Количество вариантов выборки(V) нужного количества состояний(S) из всего количества кодов(C), формула из комбинаторики:

Количество возможных вариантов задания состояний(A) равно:

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

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

Результаты

Для исследования был спроектирован автомат с числом возможных вариантов задания состояний равным 6720. Для каждого варианта было рассчитано количество необходимых элементов для реализации.

Данный ЦА описывает поведение пчелы (для простоты восприятия), входной сигнал представляет 0(всё спокойно) или 1(пчела видит шершня).

Описание ЦА:

• Количество состояний: 5

• Разрядность памяти: ceil(log2(5)) = 3

• Разрядность входного сигнала: 1

Пример расчёта числа всех возможных вариантов построения автомата:

Для любой выборки(V) нашлось не менее X(X<S!) перестановок с наилучшим исходом. Наилучший исход -- исход с минимальным числом элементов необходимых для реализации данного автомата. Для поиска способа кодирования c наилучшим исходом достаточно перебрать S! вариантов.

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

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