Что-то тянет меня в последнее время на поднятие градуса гиковости (с) в бложике. Гражданские, простите, постараюсь иногда про вас вспоминать!
Конечные автоматы и т.н. автоматное программирование -- вещи, с которыми программисты часто сталкиваются при решение задач лексического и синтаксического разбора, при описании поведения объектов в играх, при реализации всевозможных протоколов связи.
По сути дела, Finite State Machine (FSM) это некий объект, у которого есть состояние, описываемое конечным множеством значений, плюс есть некое конечное множество событий, которые могут быть поданы на вход такому объекту. Самый простой пример FSM это, например, выключатель. Объект с двумя состояниями "вкл" и "выкл" и двумя событиями -- "включить" и "выключить".
Другой простой пример -- автоматическая дверь с датчиком контроля состояния
С точки зрения программы FSM описывается фактически как таблица, где по горизонтали идут события, а по вертикали идут состояния. Каждая ячейка этой таблицы, расположенная на пересечении конкретного события и конкретного состояния, есть указатель на некий код, который должен быть выполнен, когда на вход объекту, находящемуся в указанном состоянии, подается указанное событие.
struct FsmNode {
int state, event;
void (*routine) (struct FsmInst *, int, void *);
};
struct FsmNode L2FnList[] __initdata =
{
{ST_L2_1, EV_L2_DL_ESTABLISH_REQ, l2_mdl_assign},
{ST_L2_2, EV_L2_DL_ESTABLISH_REQ, l2_go_st3},
{ST_L2_4, EV_L2_DL_ESTABLISH_REQ, l2_establish},
{ST_L2_5, EV_L2_DL_ESTABLISH_REQ, l2_discard_i_setl3},
{ST_L2_7, EV_L2_DL_ESTABLISH_REQ, l2_l3_reestablish},
{ST_L2_8, EV_L2_DL_ESTABLISH_REQ, l2_l3_reestablish},
{ST_L2_4, EV_L2_DL_RELEASE_REQ, l2_release},
{ST_L2_5, EV_L2_DL_RELEASE_REQ, l2_pend_rel},
// ...
};
Обработчик сообщения в такой таблице это указатель на функцию, которая принимает на вход указатель на FSM машину (там есть пользовательский параметр void*, который можно использовать фактически как this), код события (int, но по факту используется enum) и его параметр в виде void*, который нужно трактовать (натягивать через типкаст) согласно типу события.
На этапе инициализации такое описание машины разворачивается в двумерный массив, и код события + состояние машины используются фактически как индексы для того, чтобы за O(1) находить нужный обработчик.
Решение, конечно, так себе, по причине злостных типкастов. С другой стороны, на си сильно лучше вряд ли придумаешь. Нечто подобное можно было бы сделать и на плюсах, введя усовершенствования, вроде событий, описанных через иерархию типов, унаследованных от какого-то базового типа. Тогда в обработчиках можно было бы отказаться от нетипизированного параметра события, а дополнительные параметры получать, к примеру, через безопасный dynamic_cast... Кстати, я считаю, что в си давно надо было бы ввести одну довольно нехитрую штуку -- наследование структур, которая бы очень серьезно облегчила жизнь программистам. Кстати, дедушка Вирт, в свое время придумывая свой минималистский язык Оберон, именно на такой схеме для ООП и остановился, посчитав ее вполне достаточной.
***
Однажды, копаясь в boost::mpl, я наткнулся на такой вот занятный код, описывающий таблицу переходов для FSM на этапе компиляции через (та-дам!) список типов в лучших традициях Александреску.
События в машину поступают типизированными, через шаблонный метод, и знание этого типа позволяет уже на этапе компиляции получить на руки таблицу с записями для обработки именно этого типа события, и уже по этим усеченным данным делать поиск для конкретного состояния уже во время выполнения.
Найденный код я несколько допилил и мы его стали использовать в своем проекте.
Таблицы для наших FSM выглядели так:
struct ExpireTimerNet : boost::mpl::vector5<
EvtRow<CallPresent_6, EvT303, &T::ExpireT303, _StateDynamic_>,
EvtRow<ReleaseReq_19, EvT308, &T::ExpireT308, _StateDynamic_>,
EvtRow<CallReceive_7, EvT301, &T::ExpireT301, CallReceive_7>,
EvtRow<OverlapReceiv_25, EvT304, &T::ExpireT304, OverlapReceiv_25>,
EvtRow<DiscIndication_12, EvT305, &T::ExpireT305, ReleaseReq_19>
> {};
Первые три колонки аналогичны подобным в сишном коде -- состояние, событие, обработчик. Четвертая, новая колонка это состояние, в которое машина должна перейти после вызова обработчика. Одна из моих доработок исходного варианта примера как раз и заключалась во введении специальных маркеров состояний. _AnyState_ -- используется в первой колонке и говорит о том, что следует использовать указанный обработчик для события вне зависимости от того, в каком состоянии находится машина (разумеется, уточняющие записи для конкретных состояний имеют более высокий приоритет). Два специальных маркера для последней колонки -- _SameState_ и _StateDynamic_. Первый означает, что состояния машины не меняется (особенно актуально в случае использования в связке с _AnyState_), второй -- что обработчику разрешается перевести машину в любое состояние.
Документ по машине можно почитать тут. Сырцы и тесты можно забрать отсюда. (Я знаю, что там идет использование кода, сырцы которого я не выкладываю, дык, на понимание сути оно никакого влияния не оказывает).
С типизацией, как вы понимаете, у такого решения проблем нет. Зато есть проблемы иного рода.
Во-первых, серьезные требования к качеству компилятора. К примеру, MSVS 2005 без сервис пака жрать все эти навороты упрямо не хотела (крашилась), а после сервиса пака тож находила поводы почудить (приколы с множественным и виртуальным наследованием, описанные в начале StateMachine.h).
Во-вторых, скорость компиляции всего этого добра сами, думаю, догадываетесь какая. Таблица переходов должна быть описана в определении класса, в .cpp ее не всегда спрячешь, поэтому иногда она попадает в заголовочный файл, и таким образом тормозит компиляцию сразу нескольких файлов. У нас был в проекте файл, в котором было с десяток таких таблиц где-то на сотню записей в сумме. Компилировался этот модуль секунд 20 на далеко не слабой машине.
В-третьих, были неудобства, связанный со списками типов. Нужно руками указывать их размерность, которая, к тому же, имеет конечный, относительно невысокий, порог.
И, в-четвертых, проблема полиморфизма. На вход автомата событие должно обязательно поступать в виде своего истинного типа, поэтому если нужен полиморфизм времени выполнения, то его нужно реализовывать через виртуальный метод базового типа сообщения (конкретный тип сообщения знает свой тип, поэтому может имплементировать в этом виртуальном методе свою типизированную передачу в FSM).
***
В конце-концов, в связи с проблемами компиляции всей этой кухни под MSVS 2010 (на которую мы засматриваемся в свете C++11) было решено всю эту историю основательно переделать. Основной посыл переделки -- перенос создания таблицы переходов из времени компиляции ко времени исполнения.
В итоге получилось вот такое вот решение.
Создание таблицы переходов теперь выглядит так:
void InitTable(Fsm &fsm)
{
UTILS_FSM_ADD_EXT( st1, Event1, ActNothing, (st2) );
UTILS_FSM_ADD_EXT( st2, Event1, SwitchToS3, (st1, st2, st3) );
UTILS_FSM_ADD_EXT( st3, Event1, SwitchToS4, (st1, st2, st3) );
}
Для добавления записей используется макрос. Изначально он появился для того, чтобы минимизировать работы по адаптации существующего кода, использующего старую версию FSM. В принципе, от него можно было бы отказаться, добившись относительно лаконичного добавления через объект, в который необходимо замкнуть this.
Появилась новая фича -- _StateDynamic_ я оставил для совместимости, в новых таблицах предполагается вместо него использовать массив возможных состояний, в которые может перевезти машину обработчик события.
Еще одна фича -- возможность делать записи с маркером "any event" (для этого в качестве типа события указывается базовый тип иерархии событий). Правда, после ее добавления я всерьез задумался о тех неоднозначностях, которые может привнести в таблицу его использование. В итоге, после бурного обсуждения этой проблемы с коллегами, было решено сделать два режима работы нового класса. Режим "классический", в котором "any event" записи запрещены, и режим "расширенный", в котором поиск в таблице идет до первой записи, которая в состоянии корректно обработать переданное событие для текущего состояния (т.е. порядок записей в таблице стал иметь значение).
Работает новый код через использование typeid на экземпляре события, которое передается в машину. Требование на "видимость" типа события ушло, новая машина вполне себе полиморфна.
От использования boost::bind (по факту, от использования boost вообще) вполне себе можно было бы отказаться, но мне лень было писать этот лишний код.
Скорость поиска я никаким макаром не оптимизировал, поэтому имеем O(n) в худшем случае, где n это количество записей в таблице. С учетом того, что даже в самых больших машинах записей несколько десятков, это не то место, которое сильно просится на оптимизацию.
Из-за того, что в старом варианте FSM были проблемы, связанные с ограниченной размерностью списка типов, в нее была добавлена возможность использовать множество таблиц для перехода в рамках одной машины. В новой машине таких ограничений нет, но множественность таблиц все-таки пришлось добавлять для переноса старого кода. Насчет переноса... Если написание новой версии машины у меня заняло буквально пару часов, то вот перенос отнял гораздо больше времени, в том числе, и из-за того, что класс использовали не должным образом -- не пользовались иерархией событий, перекрывали методы для этого изначально не предназначенные etc. И, тем не менее, старый код был успешно переделан под новую FSM и без вопрос прошел все тесты (кстати, про тесты... помните, это ваш ключ к смелому рефакторингу!).
Хэппи енд.
зы. В планах написание записи на тему C++11 (заготовил уже кучу материала). Эх, найти бы время...
No comments:
Post a Comment