User Tools

Site Tools


corehard-winter-2017:article-finite-state-machine

Диаграммы состояний и C++

К материалам конференции CoreHard Winter 2017

Предисловие

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

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

О чем поговорим?

  • Трудная задача (пример из жизни)
  • Машина состояний
  • Реализации на C++
  • Выводы и вопросы

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

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

Наглядный пример

  • Открыть ворота
  • Закрыть ворота
  • Запереть

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

Пример из жизни

void openTheDoor()
{
    if (startMotorForward())
        isOpening = true;
    else
        PrintError();
}

На слайде отображена функция обработки команды “открыть дверь”. Это типичный пример того, с чего обычно начинается разработка. При нажатии на кнопку пульта управления “открыть дверь” необходимо включить двигатель. Все просто и понятно. Но в реальных условиях приходится учитывать множество возможных факторов и условий. Например, нужно произвести дополнительные проверки, проверить текущее состояние дверей. Возможно дверь уже открыта или открывается или, возможно, в предыдущий момент произошла какая-либо ошибка.

Предусматривая различные ситуации наша реализация “обрастает” дополнительными условиями и проверками. В конце-концов, через некоторое время алгоритм становится сложным и непонятным.

Через XX-цать недель

void openTheDoor()
{
    while (!isOpened && !fail && !close) {
        if (isOpened || isOpening) {
           return;
        } else if ((closed && !locked && !isOpening) ||
                   (!closed && !opened && !isOpening)) {
            if (poweredOn && startMotorForward())
                isOpening = true;
        } else if (locked && closed) {
            displayLockedMessage(); return;
        }
        Sleep(100);
    }
    if (close)
       closeTheDoor();
}

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

А что если...

…нужно “чуть-чуть” изменить структуру алгоритма?

В реальной жизни заказчик может попросить внести какие-нибудь изменения (с его точки зрения незначительные, конечно) которые могут приводить к серьезным изменениям в программе и возникает вопрос “Как же ему объяснить, что такая возможность не была изначально предусмотрена и это изменение потребует серьезных усилий?” Ответ на этот вопрос простой - никак! Никак не объяснить, т. к. он не будет смотреть вашу программу и разбираться “от чего и почему”, а просто наймет другого программиста. Потом тот, другой программист, скажет, что изменить функциональность действительно сложно, но обвинит в этом вас! ;-)

Кроме этого есть еще один важный момент.

Будьте честными

  • Часто ли вы делаете блок схемы алгоритмов?
  • Можете ли вы легко объяснить как работает Ваша программа?

Допустим у вас в команде несколько человек. Вы часто обсуждаете с коллегами алгоритм решения поставленной задачи? Как в школе учили - сначала нарисовать блок схему, потом реализация… Например, я честно скажу, все мои попытки зарисовать алгоритм перед тем как начать кодировать заканчивались неудачей! Потытки когдато были, но в конце концов все они отправлялись в урну и я приступал непосредственно к кодированию. Второй момент - что если вы работаете в команде, вы чтото запрограммировали, можете ли вы объяснить коллегам по работе как работает ваш алгоритм? Более того, даже если вы работаете один, сможете ли вы вспомнить “а что вы имели ввиду” реализуя вон ту функцию?” Или, допустим, приходит в коллектив новый человек, вы можете ему объяснить как работает программа? (пауза) Я сменил несколько работ но только один раз мне хоть как-то на пальцах хоть что-то объяснили! Во всех остальных случаях в лучшем случае мне давали ссылку на вики или файлик с инструкциями как собрать проект и установить сторонние зависимости.

Я сменил несколько работ но только один раз мне хоть как-то на пальцах чтото объяснили! Во всех остальных случаях в лучшем случае мне давали ссылку на вики или файлик с инструкциями как собрать проект и установить сторонние зависимости.

А какая альтернатива?

StateClosed::react(const Event<Open>& event)
{
    if (startMotorForward())
        transit<StateOpening>();
    else
        transit<StateFail>(&Door::DisplayMotorError(), event);
}

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

Терминология

  • Машина состояний
  • Конечный автомат
  • Диаграмма состояний
  • Finite State Machine (FSM)
  • Statechart

Так что же такое Машина состояний? В научной литературе - “Конечный автомат”, но лично мне больше нравится термин “Машина состояний” или “Диаграмма состояний”. Это созвучно с английским термином State Machine и просто проще выговаривать. Итак, постараюсь определить своими словами.

Что такое Машина состояния?

Конечный автомат "Дверь"

  • Математическая модель, абстракция
  • Модель или подход к проектированию

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

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

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

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

Определив возможные состояния, внешние события и правила перехода между состояниями мы можем построить соответствующий алгоритм в рамках понятия машины состояний и реализовать алгоритм программно. А именно зарисовать его на бумаге или с использованием какого-нибудь редактора для создания диаграмм, обсудить его с кем-нибудь, если необходимо скорректировать и, в конечном итоге, реализовать программно. Для этого для C++ и других языков программирования существуют различные библиотеки, позволяющие упростить разработку, но он их мы поговорим позже.

Реализации для C++

  • Open source
  • Qt (Core / QML)
  • Boost
  • Custom

Машины состояния удобно использовать не только для проектирования, но и для разработки. Для этого существует некоторое количество библиотек на C++. В основном - это библиотеки с открытым исходным кодом. Реализация машин состояний представлена в такой широко известной библиотеке для C++ как Qt, есть две реализации в библиотеке Boost.

Свойства машин состояний

  • Автономность
  • Детерминированность состояний
  • Основана на событиях (во времени)
  • Конечность или цикличность

Чтобы понять, а где же можно использовать подход, основанный на машине состояний, предлагаю рассмотреть ее свойства. Одно из свойств характеризующих машину состояний - это автономность. Это означает, что алгоритм, реализованный на базе машин состояний является автономным, он не зависит от внешних факторов или функционирования других алгоритмов, существует как-бы “сам по себе”. Каждое возможное состояние строго определено, а изменять свое состояние система может только при возникновении определенных внешних событий или воздействий. Из свойств машины состояний, “автономности” и “строгой определенности” (или детерменированности) и конечности числа состояний, вытекает, что система циклична, т. е. может выполнять либо ограниченное число действий и завершить свою работу, либо бесконечно выполнять определенные повторяющиеся действия. На примере наших ворот - машина состояния для управления гаражной дверью может только открывать дверь, закрывать ее и замыкать и делать это бесконечное количество раз.

Примитивы

  • Состояния (States)
  • Переходы (Transitions)
  • События (Events)
  • Действия (Actions)

Для определения машины состояний как на диаграмме, так и в программе используются всего три базовых примитива - это состояния, переходы и события. Например, на практике определяется в каких состояниях вообще может находиться система. Как я уже говорил, для нашей двери это всего 5 состояний - открыто, закрыто, открывается, закрывается и замкнута. Переходы определяют из какого в какое состояния возможно перейти, а события определяют условия перехода. Например, для нашей двери из состояния “заперто” можно перейти только в состояние “закрыто”, при этом алгоритмом определено что перейти из состояния “заперто” в состояние “открыто” перейти невозможно. На практике наряду с событиями часто определяются еще воздействие или операции, которые машина состояния может производить при возникновении определенных событий. Например, срабатывание концевого выключателя генерирует событие о том “что дверь закрыта”, при этом нужно выключить привод двигателя.

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

Иерархии и ортогональные состояния

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

В более сложных реализациях машин состояний существует понятие ортогональных состояний. Ортогональность означает независимость и одновременное существование двух и более состояний в одном контексте. Например, если необходимо во время открытия и закрытия двери включать световую или звуковую сигнализацию, то получается, что наша машина состояния одновременно находится в двух состояниях - состояния открытия или закрытия и состояния сигнализации. Такие состояния, которые могут существовать одновременно называются ортогональными и отображаться как приведено на рисунке. Таким образом машины состояний реализуют многозадачность и при грамотном подходе нет необходимости создавать дополнительные потоки или создавать несколько машин состояний для выполнения параллельных задач.

Практическая польза

  • Проектирование и документирование
  • Помогает избежать сложного ветвления
  • Определенность последовательности событий
  • “Ограничение свободы”

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

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

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

“Ограничение свободы”. Если для реализации машины состояний используется какая-либо готовая библиотека, то ее использование накладывает ограничения на программирование. Программист вынужден следовать определенным правилам программирования, которые определены библиотекой реализующей машины состояний. С одной стороны это ограничение свободы выбора способа реализации, а с другой стороны все члены команды работают в единой всем понятной технологии. Если в команду приходит новый человек, то ему не нужно навязывать стиль программирования, он будет вынужден придерживаться правил, определенных реализацией машины состояний. Для того, чтобы понять как это работает, ему нужно просто обратиться к документации.

Примеры применения

  • Протоколы обмена
  • Системы самообслуживания
  • Системы автоматики, управления
  • Интерактивные игры

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

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

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

Перейдем к практике!

Реализации

cust. Qt2) MSM3) StCh 4) NSF5)
Static+-++-
Hierarchy-+-+-
Table-++--
History-+-++
Ortogonal-+-++
Serialize+++++

Cust. - реализация через оператор switch/case
StCh - Boost.Statechart
NSF - UML North State Framework

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

У различных реализаций существуют свои особенности. Например, существует возможность построения диаграммы машины состояния в памяти на этапе разработки программы (статические реализации) и во время исполнения программы (динамические реализации). Статические реализации обычно строятся с использованием шаблонов C++ и имеют жесткую структуру. Особенность статических реализаций состоит в том, что диаграмма машины состояний формируется и жестко прописывается в программе на этапе разработки и не может быть изменена в процессе исполнения программы. В динамических реализациях структура машины состояний формируется динамически, во время исполнения программы. У каждого из этих двух подходов существуют свои преимущества и недостатки. Также реализации могут отличаться возможностью построения иерархий состояний, что определяет сферу применения и сложность или тяжеловесность библиотеки. Связи между состояниями могут строится путем построения таблицы или внутри каждого из состояний может быть определено в какое состояние и при каких условиях можно перейти.

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

Различные реализации могут поддерживать или не поддерживать возможность распараллеливания задач, т. е. ортогональные состояния.

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

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

switch/case

static int currentState = CLOSED;
 
switch (currentState)
{
    case CLOSED:
        if (event == OPEN)
            currentState = OPENED;
        else if (event == LOCK)
            currentState = LOCKED;
        break;
    case OPENED:
        if (event == CLOSE)
            currentState = CLOSED;
        break;
    case LOCKED:
        ...
}

Qt State Machine Framework

QStateMachine Door;
 
QState *stateOpened = new QState();
QState *stateClosed = new QState();
QState *stateLocked = new QState();
 
stateOpened->addTransition(ctrl, SIGNAL(close()), stateClosed);
stateClosed->addTransition(ctrl, SIGNAL(open()), stateOpened);
stateLocked->addTransition(ctrl, SIGNAL(lockTrigger()), stateClosed);
stateClosed->addTransition(ctrl, SIGNAL(lockTrigger()), stateLocked);

Boost.Statechart

struct Open : sc::event<Open> {};
struct Close : sc::event<Close> {};
struct LockTrigger : sc::event<LockTrigger> {};
 
struct Opened : sc::simple_state<Opened, Door> {
    typedef sc::transition<Close, Closed> reactions;
};
 
struct Closed : sc::simple_state<Closed, Door> {
    typedef mpl::list<sc::transition<Open, Opened>
                      sc::transition<LockTrigger, Locked>
                     > reactions;
};
 
struct Locked : sc::simple_state<Locked, Door> {
    typedef sc::transition<LockTrigger, Closed> reactions;
};

Boost Meta State Machine

struct transition_table : mpl::vector<
//     Start     Event        Target      Action
//   +---------+------------+-----------+-------------------+ 
a_row< Closed  , open       ,  Opened   , &door_::motorFwd  >,
a_row< Closed  , lock       ,  Locked   , &door_::lock      >,
a_row< Locked  , lock       ,  Closed   , &door_::unlock    >,
a_row< Opened  , close      ,  Closed   , &door_::motorBack >,
//   +---------+------------+-----------+-------------------+
> {};

Бонусы от реализаций

  • Отсроченные события (deferred events)
  • История состояний (History)
  • Сериализация машин состояний
  • Контроль переходов состояний
  • Тестирование (Unit testing)

Отсроченные события

 Deferred events

История состояний

 История состояний

Сериализация

 Сериализация машин состояний

Контроль переходов

Заключение

  • Зачем? - Формализация процесса разработки, проектирование и документирование.
  • Для чего? - Алгоритмы основанные на событиях.
  • Почему FSM? - Если не знаете ничего лучше… :-)

Итак, подведем итог.

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

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

Вопросы?

Пишите на: vasviazhСОБАКАgmail.com

Тема: Диаграммы состояний и С++.

Докладчик: Василий Вяжевич

Компания: Klika Tech,
http://klika-tech.com/,
vviazhevich@klika-tech.com

1) Внимание! Все названия переменных и алгоритмы вымышленные, любые совпадения случайны!
corehard-winter-2017/article-finite-state-machine.txt · Last modified: 2017/02/20 12:40 by admin