31 марта 2012 в 18:05

Асинхронный конечный автомат: идеология и технология из песочницы

Вступление


Хорошо, когда твои подчиненные никогда не болеют, не умирают, всегда присутствуют на работе и выполняют твои распоряжения без предварительных приготовлений: «Вызвали — встань». Таковы, например, веб-сервисы, соблюдающие модель REST (которая, если отбросить специальную HTTP-терминологию, сводится к тому, что интерфейс сервиса фактически является интерфейсом контейнера данных).

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

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

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

Анатомия (объектная декомпозиция)


Модель конечного автомата включает следующие базовые сущности:
  1. Состояние — это режим функционирования управляемой системы, отличный от других по предоставляемым возможностям. Таким образом, снапшоты кешей и буферов, варианты циклов «от забора и до обеда» и другие акциденции управляемой системы в понятие «состояния» не входят. В норме состояний должны быть считанные единицы; если счет пошел на второй десяток — скорее всего, управляемую систему следует раздробить или иерархизировать.
  2. Условие — это логическое значение (true или false) на одном из «входов» системы. Суперпозиция состояний всех входов автомата однозначно определяет целевое состояние автомата. Таким образом, любой входной сигнал, значимый для состояния автомата, в конечном счете сводится к установке значения одного или нескольких условий.
  3. Реакция — это отклик автомата на отличие текущего состояния от целевого. Принципиально различных видов реакции мы насчитали два с половиной: прямой переход между состояниями, маршрут и стоп-маршрут («кирпич»). Прямой переход может быть и пустой операцией (NOP) — например, в случае, если изменение входов вызвано уведомлением о завершении асинхронной операции.


Еще раз: состояние определяется набором условий, реакция определяется парой состояний. Любому набору входов можно поставить в соответствие какое-нибудь состояние — то есть ни при каком наборе входов желательное состояние системы не должно быть неопределенным.

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

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

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

Если вы пишете на Java, задайте наборы условий и состояний как enum, а в абстрактной реализации автомата используйте параметризацию, EnumSet для «слова состояния» и EnumMap для таблиц маршрутов и переходов. Это не догма. Наверное, можно как-нибудь по-другому. Но, как говорит армянское радио, жалко.

Физиология (threading и сигнализация)


Асинхронный конечный автомат удобно строить над очередью сообщений. На Android (пакет android.os) есть инфраструктура MessageQueue + Looper + Handler, идеально отвечающая нашим требованиям; во «взрослой» Java можно использовать ThreadPoolExecutor из одного потока или просто цикл, разбирающий LinkedBlockingQueue. Если у вас нет блокадных ресурсных ограничений, не жалейте заварки и выделите каждой управляемой системе по потоку.

Ответные сообщения клиентскому коду (по умолчанию это ID состояний, в которые переходит управляемая система, но могут быть и какие-то полезные результаты — молоко, телята...) рассылаются через thread-safe список подписчиков. (На C# подписка делегатов на события реализована «из коробки».) В методе отправки сообщения удобно возвращать булевский флаг «мне достаточно». Простейшее, что можно сделать с таким флагом — это реализовать одноразовую «защелку» (latch), на которой клиент сможет дожидаться нужного ему состояния; но можно написать и довольно-таки комплексный сценарий («после А сделай это, после Б сделай то и отцепись»).

Сообщения о перемене входного состояния просто учитываются установкой или сбросом соответствующего флага. Никаких других действий по этим сигналам не происходит. Реальный переход между состояниями отрабатывается, когда в очереди нет (или «предположительно нет» — здесь не требуется thread-safe гарантий, поскольку мы не предотвращаем race condition, а только сокращаем телодвижения) других сообщений, то есть когда «входящая почта» полностью разобрана.

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

Педагогика (runlevels и паника)


Удобная для понимания таблица состояний делается на основе последовательно применяемых containsAll() — то есть система считается находящейся в состоянии A(n), если в «слове состояния» входов присутствуют все необходимые условия этого состояния, и при этом то же самое неверно для всех A(m|m<n). В большинстве практических случаях состояния можно строго ранжировать по накоплению возможностей (от «выключено и не используется» до «включено и готово на все») и достижений (от «готовности ехать» к «едем» и «доехали»). В этом случае каждое последующее состояние отличается от предыдущего строгим ослаблением набора необходимых условий.

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

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

Экономика (ресурсы)


Ресурсы, которые вы получаете сами, специального обхождения не требуют. В частности, их можно хранить в обыкновенных non-final non-volatile private-полях. Информация о том, если ли у вас этот ресурс, целиком вытекает из вашего текущего состояния.

Ресурс, требующий специального обхождения — это dependency: то, чем управляемая система пользуется, сама не производя. Ресурсы берутся извне. Dependency injection в state-машину реализуется отдельным паттерном, который мне нравится называть «equipment» («оборудование»).

У каждого «слота» оборудования есть один постоянный атрибут: условие, сигнализирующее доступность этого вида оборудования — и два значения: suggested и effective. Suggested — это то, что предложено клиентом. Effective — это то, что фактически используется. Состояние оборудование проверяется в начале обработчика исчерпания очереди, а также после каждого перехода между состояниями.

Проверка состояния оборудования выполняется следующим образом (разбираем наиболее сложный случай, когда не-null effective заменяется на не-null suggested — остальные получаются изъятием нерелевантных «если-то»):
  • Если suggested != effective, и effective != null, то флаг «оборудование доступно» сбрасывается.
  • Если в текущем состоянии оборудование «требуется» (т.е. условие, которое мы только что сбросили, является необходимым для нахождения в текущем состоянии — однозначности здесь очень помогает runlevel-правило) то на этом мы и останавливаемся — ожидаем перехода управляемой системы в состояние, где старое оборудование не нужно.
  • Если в текущем состоянии старое (suggested != effective) оборудование не требуется, мы сбрасываем его в null.
  • Если в текущем состоянии suggested != null && effective == null, то присваиваем effective = suggested и устанавливаем флаг доступности оборудования.


Метод get() объекта — держателя оборудования пакетно-приватен и возвращает effective.

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

Этика и психология семейной жизни (интеграция)


Строго разделяйте входные сигналы по их происхождению:
  • распоряжения клиентского кода («поехали!»);
  • callbacks от управляемой системы («стучит левый двигатель»);
  • состояние ресурсов («в замке присутствует ключ зажигания»).


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

Гигиена (best practices)


Принципиально важно, что все манипуляции с подсистемой выполняются в порядке перехода между состояниями. Строго все. Настолько строго, что, в идеале, в классе конкретной реализации автомата не должно быть никаких отдельных private-методов — только делегаты (в С#-смысле; в Java — псевдо-делегаты, такие, как Callable или Runnable) в таблице переходов. В каком-то объеме ради этого можно даже потерпеть дублирование кода — так как стандартные способы его устранения не устраняют выдаваемой им избыточности семантики. (Групповое заполнение одним делегатом нескольких клеток таблицы переходов не ведет к размыванию семантики и в целом кошерно; в нашей скелетной реализации есть такие facility-методы.)

«Хуков» по образцу onStateEnter() или onStateExit(), соответственно, также не должно быть. Им придется либо знать, в каком «направлении» подсистема проходит соответствующее им состояние, либо игнорировать его.

Убедитесь, что управляемая система («физика», оставшаяся за фасадом вашего конечного автомата) не проявляет дурацкой инициативы — то есть не следит за своим состоянием сама (кроме диагностики ошибок) и ничего не делает «заодно» или «на всякий случай». Сюда относятся и «ленивая инициализация», и попытки предугадать и упредить поведение клиента. Все это является источником ошибок.

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

При автоматическом тестировании автомата (пардон за нехулигантный самоповтор) «грузите» его сообщениями с меняющимся в ходе теста порядком частоты: очень быстро (заметно быстрее, чем они обрабатывались бы поодиночке — чтобы убедиться, что наполнение очереди ничему не угрожает per se), просто быстро (с частотой, сопоставимой с частотой реакций — чтобы проверить на race conditions), медленнее частоты реакций (чтобы наблюдать самостоятельный «рост» runlevel по мере отработки «физикой» асинхронных заданий и принятия автоматом самостоятельных решений о последующих действиях).

P.S. Перед тем, как подписать клиента на изменения параметра А, синхронно передавайте ему текущее значение А. («Be racially correct — prevent race conditions».)

Заключение


Тривию какую-то написал, но судя по коду, который регулярно приходится читать — тривия, наверное, получилась полезная.
Алексей Романовский @LXE
карма
8,0
рейтинг 0,0
Самое читаемое Разработка

Комментарии (2)

  • +1
    О FSM можно рассказывать очень много. Поставил плюс в надежде на продолжение и формализацию подхода. Было бы интересно узнать о методиках, не привязанных к конкретному языку. И побольше поясняющих картинок.
  • +1
    Вот как раз, наверное, стоит рассказать об автоматическом рисовании поясняющих картинок.
    Что до привязки к языку — по-моему, очереди сообщений есть во всех языках общего назначения.

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

Интересные публикации