FSM

21 февраль, 2005 - 00:00Андрей Зубинский Не будем делать длительных отступлений и сразу устраним первое вероятное заблуждение – аббревиатура FSM никакого отношения к садомазохизму не имеет. FSM – это Finite State Machines, автоматы с конечным числом состояний. Умное название, как это часто бывает, ничего страшного под собой не таит. Впрочем, мы не будем забегать вперед и сразу попробуем ответить на совершенно законные вопросы: "А кому это нужно и нужно ли кому-то вообще?"

Одно время изучение теории FSM было исключительно уделом ученых-теоретиков (которые, очевидно, не подходят для аудитории еженедельного компьютерного журнала). Полученными научными результатами впоследствии воспользовались специалисты по моделированию систем, затем – конструкторы радиоэлектронной аппаратуры (в первую очередь – цифровых устройств). В общем, после специалистов всех-всех-всех профессий к FSM наконец проявили интерес и самые косные ортодоксы – естественно, программисты. Возможно, это и не произошло бы так скоро, но... как спросил бы Исаак Бабель – "Об чем думает такой программист?" И как он сам бы ответил – "Он думает об выпить хорошую бутылку пива, об дать кому-нибудь по морде в Quake 3, об своих любимых сайтах – и ничего больше". Короче говоря, лень-матушка заставила-таки программистов обратить внимание на "конечные автоматы" (это еще один синоним FSM), потому что в некоторых специфических (и не очень) областях применения они дают возможность хоть частично реализовать мечты одновременно двух антагонистических классов. Классу программистов FSM позволяют "программировать, не программируя". К слову, автор надеется, что стиль статьи удержит читателя от приступа наивности, при котором можно легко поверить в невероятное – в программирование вообще без программирования. И даже если недавние инвестиции DARPA в вечнозеленую (во всех смыслах, в том числе и в денежном) тему "искусственного интеллекта" приведут к созданию "искусственного программиста", у естественных программистов забот не убавится. Как только искусственный брат по разуму минует этап первой влюбленности в свое первое детище (это когда начинающий программист готов часами рассказывать о созданной им программе в стиле: "А здесь у нее так..."), он начнет повышать свой профессиональный уровень, а о результате этого процесса мы уже сказали немного искалеченными словами Бабеля. Соответственно в этом случае на плечи естественного коллеги ляжет забота и об ограничении доступа к "не тем сайтам", и о непонятно откуда возникающих гигабайтовых коллекциях искусственно-интеллектуального взрослого аниме (рисованные материнские платы со слегка приподнятыми из слотов -подчеркнуто большими процессорами и т. п.). В общем, естественный программист будет озабочен тем, чем сегодня озабочен его антагонист – руководитель проекта. И в первую очередь – надежностью и качеством созданной программы. Так вот, FSM, по идее, именно это и позволяет: разработанные на основе FSM-технологии программы могут быть очень качественными и надежными. А могут и не быть таковыми – все, в конце концов, зависит только от ленивых программистов и ретивых менеджеров проектов.

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

Быстро о реактивном

Главной областью применения конечных автоматов является моделирование так называемых реактивных систем. Термин этот настолько важен (и очень отдален от принципов работы авиа- и ракетных двигателей), что мы сразу его поясним. Реактивной системой принято называть нечто трансформирующее потоки "событий" в потоки "реакций на события". Например, встроенный микрокомпьютер мобильного телефона отлично подходит под это описание: он трансформирует потоки событий – нажатий на кнопки, сигналов от радиоприемной части – в потоки видимых пользователю или скрытых от него реакций. Заметьте, что о временных характеристиках этих потоков ничего не сказано, точнее, не сказано ни о каких временных ограничениях на них. А то, что не запрещено, разрешено, соответственно события могут случаться одновременно. И реактивная система должна на них правильно реагировать. О таком свойстве, как "одновременность", мы не так давно уже говорили, поэтому подробно на нем останавливаться не будем. Традиционный подход для реализации реактивных программных систем заключается в использовании операционной системы реального времени и создании многопоточной управляющей программы. Это требует решения массы весьма щекотливых вопросов, связанных с синхронизацией, блокировками разделяемых ресурсов и т. д. В общем, непростое это дело. Высший пилотаж профессионального программирования. И, естественно, очень высокий риск: в силу своей специфики реактивные системы используются именно там, где цена ошибки может быть астрономически большой. А вот теперь пора прояснить одну важную (если не главную) деталь FSM-технологии: потенциальная ее пригодность к решению одновременно двух задач (уменьшение количества написанного вручную кода и повышение надежности) объясняется тем, что эта технология позволяет создавать реактивные системы, не применяя ни ОС реального времени, ни сложное потоковое программирование. Но даже после столь многообещающего утверждения не только говорить, что "вот если бы программу X (подставьте любое известное вам название) так написали, она была бы несоизмеримо лучше", но даже и думать о FSM-технологии как о панацее непозволительно. Чтобы исключить подобные заблуждения, давайте дополним признак "реактивности" одной косвенной характеристикой – доминированием в реактивных системах задач управления. То есть основным источником, "генератором" потоков событий, является окружающая (по отношению к вычислителю, исполняющему программу реактивной системы) среда. Соответственно и возможных событий может быть очень много, и, что главное, еще большим будет количество возможных одновременных их комбинаций. Это существенно отличает реактивные системы от обычных приложений, обрабатывающих большие объемы информации от незначительного числа источников (чаще всего – вообще от одного источника, например входного файла, содержащего текст статьи, изображение или компрессированный звук). Если не учитывать этого важного нюанса, можно легко стать экстремистом, берущимся утверждать, что "серебряная пуля" все-таки существует. В качестве примера такого экстремального отношения к конечным автоматам можно привести фразу известного разработчика ядра ОС Linux Алана Кокса: "Компьютер – это машина состояний. Потоковое программирование нужно тем, кто не умеет использовать конечные автоматы". (A computer is a state machine. Threads are for people who can't program state machines.)

Состояния, переходы, инструменты

Традиционно, как только изложение доходит до описания двух важнейших абстракций, лежащих в основе любого конечного автомата, принято прибегать к испытанному приему. А именно – приводить страшно обнаученные определения "из учебника" (непременно с использованием теоретико-множественных конструкций) и перекладывать все остальное на плечи читателя. К сожалению автора, этот прием нам не подходит – технология FSM-программирования настолько далека от чистых теоретических построений, что как раз с последними читатель сам сможет ознакомиться на досуге. Да и излишнее теоретизирование обозревателю не к лицу – дело обозревателя забраться куда повыше, всматриваться в даль и, увидев что-нибудь интересное, громкими криками призывать отвлечься на пару минут прочих граждан, увлеченных своими делами.

Одна из самых мощных сред разработки машин состояний – транслятор графической модели в код, который можно транслировать для разных целевых платформ, – IAR visualSTATE. Среда позволяет не только разрабатывать реактивные системы, но и моделировать и верифицировать их поведение

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

Машина состояний (помните, как назвал компьютер Алан Кокс), описывающая реактивную систему, – это нечто, характеризующееся конечным множеством состояний и перечнем переходов (из состояния в состояние, как бы ни хотелось избежать тавтологии). В свою очередь состояние – абстракция, описывающая некоторый этап, или даже, точнее, момент вычислительного процесса. Переходы отображают "путь" этого процесса – благодаря им формируются аналоги ветвлений и циклов в традиционном, императивном программировании. Состояния могут быть двух фундаментальных типов – наблюдаемые и скрытые. Наблюдаемые, или видимые, состояния реактивной системы определяются состояниями окружающей среды или объекта управления, т. е. такими, которые могут наблюдаться пользователем. Скрытые же, напротив, спрятаны в кодах программы, реализующей реактивную систему. Разницу между ними можно объяснить на простом примере – скажем, на примере микроволновой печи. У нее могут быть два явно наблюдаемых состояния – "дверца открыта", "дверца закрыта", одно особое наблюдаемое состояние – "питание включено" (особое потому, что пользователь может наблюдать только косвенное подтверждение включения питания по индикатору), а также ряд скрытых состояний. К последним, например, относится "печка ожидает команды пользователя" (такой энергосберегающий режим ожидания во многих устройствах называется standby), "опрос датчика напряжения питания", "опрос датчика закрытия двери", "опрос кнопок выбора режима" и т. д. И наконец, еще одна важная деталь: некоторое состояние объявляется "начальным", с него любая реактивная система начинает свое функционирование (в случае с микроволновой печью таким состоянием будет standby – именно в нем "оказывается" впервые включенное устройство). Переходы – это, по сути, правила, описываемые следующим типовым шаблоном на естественном языке: "Если реактивная система находится в состоянии Si и случается нечто, то она изменяет свое состояние на Sj".

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

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

Вот, собственно, и весь минимально необходимый для начала освоения FSM-программирования базис. Разве что стоит добавить, что в развитых системах конечно-автоматного проектирования используются дополнительные (но необязательные) абстракции. К таким абстракциям, достойным рассмотрения в этой статье, стоит отнести понятие "надсостояния". Благодаря ему появляется возможность не только преодолеть главный недостаток графического описания машины состояний (потеря наглядности при увеличении сложности модели), но и повысить надежность кода, реализующего реактивную систему. "Надсостояние" – это, если так можно выразиться, отдельный "режим" работы системы, в который она может быть введена строго определенными событиями и который объединяет некоторую группу логически связанных состояний. Возвращаясь к примеру с микроволновой печью, следует выделить два ее фундаментальных "надсостояния": нахождение в режиме "standby" (мало ли чем будет в это время заниматься управляющий микрокомпьютер печки) и в режиме "работа". Соответственно в каждом из этих -"надсостояний" можно отыскать еще много режимов.

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

switch( текущее_состояние) case Si : выполнение_операций_в_текущем_состоянии() ; if ( событие_01 ) текущее_состояние = Sj ; break ; if ( событие_02 ) текущее_состояние = Sk ; break ; ... case Sj : выполнение_операций_в_текущем_состоянии() ; if ( событие_01 ) текущее_состояние = Sz ; break ; ...

и т. д.

Действительно, так делать тоже можно. И многие именно так и делают (больше того, некоторые средства FSM-генерации кода создают именно такие программы). Но по мере роста количества событий и состояний проектируемой системы императивная программная реализация становится все сложнее и сложнее. В большинстве трансляторов FSM-описаний в код, напротив, используются единая программная среда времени исполнения (маленькая, буквально в сотню строк, программка) и сгенерированная таблица. Этот нюанс будет очень важен при создании программ для микровычислителей с крайне ограниченными ресурсами оперативной памяти – ведь единожды спроектированная таблица переходов не изменяется, и ее можно "зашить" в дешевую постоянную память.

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

Инструментальных средств, поддерживающих разработку машин состояний и много и мало. Высококлассных – мало, всяких разных – много. К наиболее профессиональным и охватывающим весь производственный цикл (от формирования требований и прототипирования до генерации кода, отладки во взаимодействии с кросс-средствами, в том числе и с аппаратными) следует отнести коммерческие системы visualSTATE (компания IAR SYSTEMS, www.iar.com/Products/VS/) и EventStudio (компания EventHelix, eventhelix.com). Несмотря на сравнительно большую цену, продукты такого класса действительно необходимы (и даже безальтернативны) тем коллективам разработчиков, которые заняты созданием критичных к надежности реактивных программных систем. Но и для начинающих будет небесполезно "вытянуть" доступные для временного использования ограниченные версии этих программ – не только для того, чтобы почувствовать "вкус" продуктов такого класса, но и для получения -доступа к отличной сопровождающей документации. К слову, компания EventHelix известна и хорошей программой, и великолепной онлайн-книгой "Мантра реального времени" (eventhelix.com/RealtimeMantra/), изучение которой можно порекомендовать всем профессиональным программистам, желающим повысить свой уровень.

Из легально инструментальных средств наиболее привлекательным является языковый транслятор Libero (компания iMatix, www.imatix.com/html/libero/index.htm). Эта небольшая утилита принимает в качестве входа описания машины состояний на собственном несложном языке, а выдает код, реализующий эту машину состояний. Libero сопровождается исчерпывающей документацией (правда, немного трудной в освоении из-за использованного стиля и изобилия слишком хорошего нетехнического английского языка), поставляется в исходных текстах и не раз уже доказала свою пригодность к практическому применению (в том числе и при разработке известного Web-сервера Xitami). Программа кросс-платформенна и великолепно адаптируется к нуждам разработчика – ее можно настраивать на генерацию кода на различных языках и создавать свои собственные кодогенераторы.