Event Driven State Machines On Top Of UNIX/Linux API
(Конечные автоматы на основе Unix/Linux API, управляемые событиями)

Основные понятия

Канал (Channel)

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

В описываемом, не побоюсь этого слова, фреймворке... нет, скорее это всё-таки движок... имеется 3 типа каналов:

1. Таймер
2. Прерывание (сигнал)
3. Канал ввода-вывода (сокет, FIFO, /dev/ttyXXX etc)

Кроме того, имеется ещё 2 типа каналов для передачи "внутренних" событий (реализованы при помощи pipe).

1. Почтовый ящик
2. Расширенный почтовый ящик

Событие (Event)

Событие - изменение состояния канала, смысл события определяется типом канала.

Для каналов типа "таймер" возможно только одно событие, а именно, истёк указанный временной интервал, будет обозначаться вот так:

	T0 - сработал таймер номер 0
	T1 - сработал таймер номер 1

Для каналов типа "прерывание" также возможно одно событие - собственно, поступил сигнал, обозначается примерно так же:

	S0 - поступил сигнал номер 0
	S1 - поступил сигнал номер 1

По поводу нумерации сигналов смотри далее.

Для канала ввода-вывода определены 3 типа события:

	D0 - возможно чтение без блокировки (==POLLIN)
	D1 - возможна запись без блокировки (==POLLOUT)
	D2 - ошибка (==POLLERR/POLLHUP/POLLRDHUP)

Типы (номера) событий для канала типа "почтовый ящик" задаются программистом и обозначаются вот так:

	M0 - случилось нечто
	M1 - случилось нечто 2
	M2 - случилось нечто 3

Иногда под Mx вместо "случилось нечто" логически удобнее понимать команду, отправленную одним автоматом другому (или самому себе, для того чтобы "перекинуть себя" в следующее состояние).

Аналогично обстоит дело с каналом типа "расширенный почтовый ящик":

	B0 - случилось нечто
	B1 - случилось нечто 2
	B2 - случилось нечто 3

Event Capture Engine

Это программный код, который в цикле "отлавливает" события, пользуясь механизмами операционной системы. В описываемом движке используются системные вызовы poll() или epoll().

Event Dispatcher

Код, который направляет событие соответствующему конечному автомату.

State Machine

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

Moore Machine

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

Mealy Machine

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

И что с этим со всем делать? Далее на нескольких примерах показан процесс проектирования программного обеспечения для ОС типа Unix с использованием парадигмы "конечного автомата" и описанного движка.

Но сначала несколько замечаний.

• В программе может быть сколько угодно автоматов.
• У каждого канала есть автомат-владелец. Именно этому владельцу диспетчер направляет события, возникающие в данном канале.
• У каждого автомата может быть сколько угодно каналов-таймеров и каналов-прерываний, создаются они автоматически, по описанию автомата (см. далее).
• Каждый автомат может иметь только по одному каналу ввода-вывода, почтовому ящику и расширенному почтовому ящику. При этом обычный почтовый ящик создаётся автоматически (потому что почти всегда нужен), создание/удаление канала ввода-вывода и расширенного почтового ящика определяется программным кодом.

Hello, World!

Начнём с элементарного примерчика. Пусть нам нужно каждые 2 секунды выводить что-то на stdout и по SIGTERM/SIGINT завершаться. Итак, поехали:

Шаг 1. Рисуем диаграмму конечного автомата

Шаг 2. Описываем конечный автомат

 таймер на 2 секунды
T2000

 SIGTERM
S15
 SIGINT
S2

 State set
$idle
$done

@idle T0 do_hw
+idle S0 done
+idle S1 done

Данное описание нужно поместить в файл, пусть для определённости он будет называться 'hw.smd'. SMD - это аббревиатура от "State Machine Description", то есть "описание конечного автомата".

Пояснения к формату файлов SMD. Описание каждого автомата хранится в отдельном файле. Все строчки, которые не начинаются с символов из набора 'TS$@+' - комментарии. Таймеры описываются как 'Tчисло', где число - интервал в миллисекундах. Таймеры нумеруются в порядке перечисления, нумерация начинается, да, с нуля.

Сигналы задаются как 'Sномер', где номер - это номер сигнала (согласно выводу kill -l). "Внутри" автомата сигналы нумеруются с нуля в порядке перечисления в файле описания автомата.

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

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

Действие без перехода (автомат Мили) обозначается следующим образом:

@состояние событие действие

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

Переход в другое состояние обозначается вот так:

+состояние событие следующее_состояние

Это используется для реализации автоматов Мура: если что-то произошло, надо сменить состояние и что-то сделать. "Что-то сделать" оформляется в виде входной функции (см. чуть ниже). По поводу символа '+' - а этот символ несколько напоминает букву 'T', первую букву слова "transition"; стало быть, если плюсик, то после события надо писать название какого-то другого состояния.

Шаг 3. Пишем программу

Пояснения к программе. Помимо действий по типу машины Мили, есть два типа действий, которые не задаются в описании автомата - это входные и выходные функции. Имена их формируются из названия автомата (имя файла, для примера это hw.smd), названия состояния и суффиксов _enter/_leave. Входные функции являются обязательными, выходные - нет.

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

Hello-world (Moore only)

Рисуем диаграмму

Составляем по ней описание автомата

T2000

S15
S2

$idle
$print
$done

+idle T0 print
+idle S0 done
+idle S1 done

+print M0 idle
+print S0 done
+print S1 done

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

Обратите внимание на строчку, где edsm_put_event() - это как раз и есть "генерация" внутреннего события, по возникновении которого движок сменит состояние так, как это задано в описании автомата.

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

Hello-world (Mealy only)

Рисуем диаграмму

Составляем по ней описание автомата

T2000

S15
S2

$idle

@idle T0 do_hw
@idle S0 do_exit
@idle S1 do_exit

Пишем программу:

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

Эхо-сервер

Приступим теперь к проектированию более сложной программы, для которой описываемый подход действительно помогает, в отличие от вышеприведённых примеров hello-world. Эти примеры были приведены исключительно для демонстрации того, как обращаться с таймерами и сигналами. Теперь обратимся к вводу-выводу.

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

Итак, продумываем состояния и переходы между ними, рисуем картинки. Например, так:

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

Описание "главного" автомата (echo_accept.smd):

S15
S2

$idle

 B0 : EC_CLIENT_GONE

@idle D0 create_client
@idle B0 delete_client
@idle S0 bye
@idle S1 bye

Описание автомата ввода-вывода (echo_rxtx.smd):

 RX timeout timer
T5000

$init
$rx
$tx
$done

 M0: EC_INIT_DONE
 M1: EC_REQUEST_RECEIVED
 M2: EC_ERROR
 M3: EC_REPLY_SENT

+init M0 rx
+init M2 done

@rx D0 do_rx
@rx T0 on_timeout
+rx M1 tx
+rx D2 done
+rx M2 done

@tx D1 do_tx
+tx M3 rx
+tx D2 done
+tx M2 done

После этого прикидываем, что надо делать во входных функциях, нужны ли выходные и что в них делать, а также что делать в прочих функциях (тех, которые в строчках, начинающихся с '@').

Главный автомат. При входе в начальное (и единственное) состояние надо создать сокет, связанный с ним канал и расширенный почтовый ящик для приема сообщений от автоматов ввода-вывода. Также нужно разрешить события POLLIN для слушающего сокета. По событию D0 надо аккуратненько принять соединение и создать автомат ввода-вывода вкупе с контекстом для него. По событию B0 от какого-либо автомата ввода-вывода удаляем этот автомат и контекст для него. По событиям S0 и S1 завершаем цикл приёма событий.

Автомат ввода-вывода. При входе в состояние "init" нужно создать канал ввода-вывода. При входе в состояние "приём" нужно привести буфер данных в исходное состояние, разрешить приём данных и запустить таймер для отслеживания таймаута на поступление запроса. Для состояния "приём" пригодится выходная функция - там мы будем останавливать таймер. При входе в состояние "передача" нужно разрешить, собственно, получение событий POLLOUT. При входе в состояние "done" нужно удалить канал ввода-вывода и сообщить главному автомату, что мы типа закончили. В состоянии "приём" по событию D0 (есть данные) аккуратненько их читаем, при этом учитываем, что за раз могут придти не все данные. В состоянии "передача" по событию D1 (запись не заблокирует процесс) аккуратненько отправляем их клиенту, при этом учитываем, что за раз могут отправиться не все данные.

Ну, и теперь тупо пишем всё это на языке Си...

Исходные тексты вот.

Те, кто не поленился скачать-собрать-запустить и всё такое, обратите внимание на файл .config. Там два параметра, один включает некоторые сообщения - при отладке это очень полезно, будет видно, как автомат гуляет по состояниям; второй параметр - использовать не poll, а epoll. Но, поскольку в движке на epoll есть еще timerfd_create() и signalfd(), то это только для ядер версии>=2.6.25. После изменения файла .config программы надо, разумеется, пересобрать - make cleanall; make. Замечу между делом, что движок, основанный на poll, слегка простецкий в том смысле, что количество каналов, будучи заданным при инициализации, в процессе работы увеличить уже никак (epoll разруливает этот вопрос автоматически).

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

Литература:

1. Wagner F. и др.
Modeling Software with Finite State Machines: A Practical Approach

2. Поликарпова Н.И., Шалыто А.А.
Автоматное программирование

3. Сайт StateWorks (раздел Publications/TechNotes)

4. Программа, управляемая событиями

5. State Threads

6. Event-driven architecture, state machines et al.

7. State Machines for Event-Driven Systems

8. Reactor pattern

Замечание по поводу (цитата из документа по последней ссылке)

"Also, due to the synchronous calling of request handlers, the reactor pattern allows for simple coarse-grain concurrency while not adding the complexity of multiple threads to the system"

А вот использование конечных автоматов как раз и позволяет сделать "fine-grain concurrency", за счет большего количества внутренних сообщений и/или количества состояний. Рассмотрим вполне реальный пример. Нужно просканировать каталог, и для этого в каком-либо автомате есть предназначенное для этого состояние, назовём его SCAN. Можно сделать так: всё сделать на входе в это состояние, то есть использовать, к примеру, scandir() и для каждого файла сделать нужное действие. А можно сделать интереснее: на входе сделать opendir() и послать себе сообщение (M0); в обработчике этого сообщения сделать readdir(), если файлы кончились, то послать себе другое сообщение (M1), по которому далее произойдёт переход в другое состояние; если же readdir() вернула очередной файл, сделать обработку и опять послать себе сообщение M0 и выйти из обработчика; по выходу из состояния SCAN при необходимости сделать closedir(). Таким образом, после обработки каждого файла программа будет возвращаться в главный цикл и будет иметь возможность выполнить другую (не связанную со сканированием каталога) работу. Это и есть concurrency - программа делает кучу дел попеременно маленькими кусочками. Можно пойти ещё дальше и произвести декомпозицию состояния SCAN на несколько, например, PREPARE_TO_SCAN (там делаем opendir()), READ_DIR_ENTRY (там делаем readdir()) и PROCESS_FILE (там делаем какую-то обработку), тогда будет ещё более "fine-grain concurrency". Так-то!

Пару слов о тестировании

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

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

А вот как:

• отправляем процесс в анабиоз, посылая ему сигнал SIGSTOP
• выжидаем минут этак 5-10 (а не месяц!); за это время, во-первых, клиенты отвалятся-прицепятся (возможно, не по одному разу) и, во-вторых, у сервера истекут все сроки ожидания данных от них; вот вам и куча готовеньких событий, которые процесс будет быстро-быстро отрабатывать (когда мы вернём его к жизни, разумеется).
• выводим процесс из анабиоза, посылая ему SIGCONT и вуаля.

С помощью этого незатейливого приёмчика мне с первого (!) захода удалось определить, что за ералаш происходит в данном конкретном случае. Я наивно полагал, что клиент у меня отваливается ИЛИ по D2 (HUNGUP), ИЛИ по T0 (таймаут). Анализ логов, образовавшихся после вывода программы из комы, показал, что можно влёгкую словить оба события сразу - вот как раз в таких (в частности) случаях программа и начинала куролесить. Самой подлянкой оказалась последовательность событий D0 (== POLLIN) и D2 (==POLLERR), причем второе идёт сразу же вслед за первым; из-за особенностей логики программ первое событие отрабатывается "неатомарно" в том смысле, что прежде чем оно будет отработано полностью, программа не раз возвратится на epoll_wait() - где и словит D2... в конечном итоге это ломает логику работы автоматов и приводит к потрясающим спец-эффектам из разряда "больше всего работа программы удивляет её автора". Касабельно самой последовательности POLLIN/POLLERR, то есть "есть данные" и сразу "разрыв/ошибка" - она возникает оооочень редко и с чем она связана, мягко говоря, не понятно. То ли с работой сотовых сетей (все клиенты у меня выходили в инеты через GPRS), то ли с особенностями софта этих самых клиентов, зоопарк там ещё тот. В локальных проводных сетях с обычными программами, работающими под управлением распространённых ОС с надёжными стеками TCP/IP, как мне думается, такие ситуации ещё менее вероятны, если вообще возможны.

Через некоторое время обнаружилась ещё более зловредная (очень быстрая) последовательность, а именно D0,D2,D2. Она сломала автомат RX уже после внесения изменений, направленных на борьбу с этими делами. Сломала, к слову, спустя около месяца работы в режиме 24x7 и только у одной из десятка однотипных программ. ОС завалила программу-сервер сообщениями POLLHUP. С чего вдруг такая последовательность образовалась, есть только следующие соображения. Для начала напомню, что события POLLERR и POLLHUP движок транслирует в D2, то есть делает их неразличимыми. Скорей всего двойное D2 изначально было POLLERR, сопровождаемое POLLHUP. POLLERR возникает (вроде как) тогда, когда ПО на другой стороне соединения прислало TCP-пакетик с флажком RST. По всей видимости, чортова железяка прислала какие-то данные, при этом с флажком RST, а ядро ОС на этой стороне сгенерило одно за другим сразу 3 события - D0 ("есть данные"), D2 ("POLLERR") и снова D2 ("POLLHUP"). Такая вот загогулина.

Дата последней модификации: 2019-09-26