Технология разработки программного обеспечения Конечные автоматы

Введение В системах сильно зависимых от состояний машины конечных состояний (конечные автоматы) могут существенно помочь понять логику их работы. На языке UML диаграмма смены состояний называется диаграммой машины состояний. В UML диаграмма машины состояний (state machine diagram) основывается на конечных автоматах Харлея.

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

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

Типы диаграмм состояний Традиционная диаграмма смены состояний, которая не является иерархической, называется плоской диаграммой состояний (flat statechart). Термин иерархическая диаграмма состояний (hierarchical statechart) используется для обозначения понятия иерархической декомпозиции состояний.

События Событие (его также называют дискретным сигналом или стимулом) - это некоторое явление, происходящее в определенный момент времени. События являются атомарными (то есть не прерываемыми) и концептуально имеют нулевую продолжительность. – Примеры событий: «Карточка Вставлена в Банкомат», «Введен ПИН-код», «Нажат Тормоз», «Лифт Уехал».

События могут зависеть друг от друга. – Например, событие «Карточка Вставлена в Банкомат» всегда предшествует событию «Введен ПИН-код». С другой стороны, события бывают и совершенно независимыми. – Например, событие «Карточка Вставлена в Банкомат» в Москве не зависит от события «Карточка Вставлена в Банкомат» в Новосибирске.

Событие таймера Событие таймера - это особое событие, описываемое ключевым словом after, которое говорит, что событие происходит по истечении промежутка времени, заданного выражением в скобках. – Например: after (10с) или after (промежуток времени). На диаграмме состояний событие таймера вызывает выход из текущего состояния. Промежуток времени измеряется от момента входа в состояние до момента выхода из него, обусловленного событием таймера.

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

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

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

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

Примеры диаграмм состояний Использование плоских диаграмм состояний показано на трех примерах: 1. диаграммы состояний электрической лампочки; 2. диаграмма состояний счета; 3. диаграмма состояний банкомата ;

Пример 1: диаграммы состояний электрической лампочки

События обуславливают переходы состояний. Когда переключатель устанавливается в положение «On» (включен), лампочке посылается событие turnOn. – В диаграммах состояний события считаются мгновенными, т. е. от переключателя к лампочке событие доходит мгновенно. Лампочка получает событие turnOn и в ответ на него меняет свое состояние на On. В этом суть автоматов – объекты могут менять состояние при получении события. Лампочка переходит в состояние Off при получении события turnOff. В некоторый момент может произойти событие burnOut (лампочка перегорает). – Оно завершает конечный автомат.

Пример 2: диаграммы состояний счета В данном примере показана простая диаграмма из двух состояний: начального и конечного. Когда открывается счет с положительным балансом, событие «Счет Открыт» вызывает переход в начальное состояние «Счет Хороший». Последующие события «Вклад» и «Обычное Снятие Денег» не изменяют состояния при условии, что баланс счета остается положительным.

Диаграмма состояния счета

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

Пример 3: диаграмма состояний банкомата Начальное состояние данной диаграммы – «Простаивает». При получении события «Карточка Вставлена» банкомат переходит в состояние «Ожидание ПИН-кода», в котором ждет, пока клиент введет ПИН-код. При получении события «ПИН-код Введен» банкомат переходит в состояние «Проверка ПИН-кода», в котором выясняет, совпадает ли введенный клиентом ПИН-код с тем, что хранится в базе данных банковского сервера.

Из состояния «Проверка ПИН-кода» возможно четыре перехода. 1.Если ПИН-коды совпадают, осуществляется переход по ветке «Правильный ПИН-код» в состояние «Ожидание Выбора Клиента». 2.Если ПИН-коды не совпадают, то по ветке «Неправильный ПИН-код» осуществляется возврат в состояние «Ожидание ПИН-кода», и система предлагает клиенту повторить ввод. 3.Если и после третьей попытки клиент указывает неправильный код, то совершается переход «Три Неудачи» в состояние «Конфискация». 4.если карточка оказалась утерянной или украденной, то также совершается переход «Три Неудачи» в состояние «Конфискация». Кроме того, клиент может нажать клавишу отмены, после чего карточка будет возвращена, а транзакция прервана.

Диаграмма состояний банкомата

В состоянии «Ожидание Выбора Клиента» клиент может выбрать нужную операцию, например «Снятие Денег». Диаграмма состояний получает событие «Выбрано Снятие Денег» и переходит в состояние «Обработка Запроса на Снятие». Если снятие разрешено, то диаграмма оказывается в состоянии «Выдача Наличных».

После получения события «Наличные Выданы» банкомат переходит в состояние «Печать», в котором печатается чек, а затем в состояние «Возврат». После возврата карточки, о чем сигнализирует событие «Карточка Возвращена», мы попадаем в состояние «Завершение».

Из состояния «Завершение» производится переход в начальное состояние «Простаивает» после получения события таймера. Событие таймера обозначается After («Промежуток Времени»), – где «Промежуток Времени» - это продолжительность нахождения в состоянии «Завершение» (от момента входа в это состояние до момента выхода, вызванного событием таймера).

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

На диаграмме состояний действие изображается путем пометки перехода следующим образом: событие [условие] / действие. – Например, когда банкомат переходит из состояния «Ожидание ПИН-кода» в состояние «Проверка ПИН- кода» в результате события «ПИН-код Введен», выполняется действие «Проверить пин-код». Этот переход помечен так: ПИН-код введен / Проверить пин-код.

Пример действия Фрагмент диаграмма состояний банкомата с добавленными действиями.

Переход с несколькими действиями С переходом может быть связано несколько действий. Такие действия выполняются одновременно, и поэтому между ними не должно быть никаких зависимостей. – Например, неправильно включать два одновременных действия: «Рассчитать Изменение» и «Показать Изменение». В таком случае имеется подчиненность одного действия другому, поскольку нельзя показать изменение до того, как оно рассчитано. Для решения данной проблемы нужно ввести промежуточное состояние «Расчет Изменения». – действие «Рассчитать Изменение» выполняется при входе в это состояние, – действие «Показать Изменение» - при выходе из этого состояния.

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

Один из способов показать деятельность на диаграмме состояний – – пометить переход в состояние, где она протекает: событие / enable деятельность, – а также пометить переход из этого состояния: событие / disable деятельность.

Для сокращения записи, можно вместо слов enable и disable ассоциировать деятельность с самим состоянием. Для этого в прямоугольнике, представляющем состояние, записывают имя состояния и имя деятельности, разделяя их горизонтальной чертой. Деятельность изображают в виде do / деятельность (здесь do -- зарезервированное слово). Это означает, что деятельность начинается при входе в состояние и завершается при выходе из него.

Диаграмма состояний системы круиз- контроля с деятельностями

Действия при входе и выходе Некоторые действия можно записать более кратко, если связать их с самим состоянием, а не с переходами. Для это используются действия при входе и при выходе, для которых применяются ключевые слова: entry и exit. – мгновенное действие, выполняемое при входе в состояние, обозначается как entry / действие, – мгновенное действие, выполняемое при выходе из него, - как exit / /действие. Обычно действия при входе и выходе не используются, вместо этого помечаются переходы в данное состояние и из него.

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

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

Пример описания действия при входе На рис. действия изображены на переходах. – действие «Индицировать Останов Системы» связано со всеми тремя переходами в состояние Останов, – действие «Отобразить Приветствие» - с двумя переходами в состояние Простаивает.

Пример описания действия при входе (2) Другой способ к изображению действий : – при входе в состояние Останов выполняется мгновенное действие «Индицировать Останов Системы», – при входе в состояние «Простаивает» - мгновенное действие «Отобразить Приветствие«

Пример описания действия при выходе Рассмотрим действие «Установить Значение Требуемой Скорости», Оно выполняется после увеличения скорости в состоянии «Разгон» в ходе выполнения деятельности «Увеличить Скорость», поэтому изображено на обоих переходах из состояния Разгон.

Пример описания действия при выходе (2) Более краткая запись действия при выходе из состояния «Разгон»:

Пример описания действия при выходе (2) Деятельность «Увеличить Скорость» выполняется в течение всего времени пребывания в состоянии «Разгон». При выходе из этого состояния сначала прекращается деятельность в нем, а затем выполняется действие при выходе. Деятельность, выполняемая, пока автомат находится в данном состоянии, может сама возбуждать событие, вызывающее переход в новое состояние. – Например, деятельность «Возобновить Круиз-Контроль», которая осуществляется в состоянии «Возобновление», возбуждает событие «Выход на Крейсерский Режим», которое переводит диаграмму в состояние «Крейсерский Режим». Выход из состояния «Возобновление» может быть обусловлен и другим событием, в частности «Нажат Тормоз», полученным из внешней среды.

Синтаксис состояния

Событие keypress (нажатие клавиши) моделируется это как внутреннее событие, которое вызывает внутренний переход, инициирующий действие отобразить *. Два специальных действия – вход и выход – ассоциированы со специальными событиями entry и exit. – У этих двух событий особая семантика. Событие entry происходит мгновенно и автоматически при входе в состояние. – Это первое, что происходит, когда осуществляется вход в состояние. – Это событие обусловливает выполнение ассоциированного с ним действия на входе. Событие exit – самое последнее, что происходит мгновенно и автоматически при выходе из состояния. – Обусловливает выполнение ассоциированного действия на выходе.

Иерархические диаграммы состояний

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

Иерархическая декомпозиция состояний Иерархическая декомпозиция состояний: выделение «надсостояния», которое раскладывается на одно или несколько взаимосвязанных «подсостоянии». Такая операция также называется декомпозицией ИЛИ, так как пребывание в некотором надсостояний означает, что диаграмма находится в одном и только одном из его подсостоянии. Обозначения UML позволя.т показать надсостояние и подсостояния на одной или нескольких диаграммах в зависимости от уровня сложности.

Пример иерархической декомпозиции состояния В данном примере «надсостояние» «Обработка Ввода Клиента» состоит из подсостояний – «Ожидание ПИН-кода», – «Проверка ПИН-кода» и – «Ожидание Выбора Клиента».

Пример иерархической диаграммы состояния

Изображение иерархической декомпозиции состояния В иерархической диаграмме надсостояние изображается в виде внешнего прямоугольника с закругленными углами, в левом верхнем углу которого записывается имя надсостояния. Подсостояния изображаются внутренними прямоугольниками с закругленными углами.) Когда система оказывается в надсостояний обработка «Ввода Клиента», она находится в одном и только одном из подсостоянии – «Ожидание ПИН-кода», – «Проверка ПИН-кода» или – «Ожидание Выбора Клиента».

Отметим, что каждый переход в надсостояние «Обработка Ввода Клиента» - это переход в одно и только одно подсостояние диаграммы нижнего уровня. Любой выход из надсостояния это выход из какого-то его подсостояния. – Например, входное событие «Карточка Вставлена» вызывает переход в подсостояние «Ожидание пин-кода», внутреннего для надсостояния «Обработка Ввода Клиента».

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

Рекомендации по разработке диаграмм состояний (2) из каждого состояния должен быть выход. – Очень часто встречаются диаграммы, в которых нет конечного состояния; плоская диаграмма в любой момент времени находится только в одном состоянии. – Два состояния, например Лифт Движется и Лифт на Этаже, не могут быть активными одновременно. – Одно состояние должно следовать за другим;

для иерархических диаграмм применимы следующие правила: – если речь идет о последовательной иерархической диаграмме (декомпозиция ИЛИ), то пребывание в некотором надсостояний означает пребывание в одном и только одном из его подсостояний; – если используется параллельная иерархическая диаграмма (декомпозиция И), то пребывание в некотором надсостояний означает пребывание в одном из подсостояний каждой диаграммы нижнего уровня;

не следует путать события и действия. – Событие - это причина перехода состояний, а действие - его следствие; событие происходит в некоторый момент времени. – Имя события должно пояснять, что именно произошло, например: Вызов Вверх, Дверь Закрылась; действие - это команда, – например: Остановить, Закрыть Дверь, Поддерживать Скорость; действие выполняется мгновенно. деятельность продолжается все время, пока диаграмма находится в данном состоянии;

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

условие - это булевое значение. – Если переход помечен конструкцией событие [условие], то он происходит только тогда, когда в момент возникновения события условие истинно. – Условие остается истинным на протяжении конечного промежутка времени. – Переход «Разогнаться [Торможения Нет]» предназначен специально для того, чтобы предотвратить смену состояния в случае, если в момент возникновения события «Разогнаться» нажата педаль тормоза; действия, деятельности и условия необязательны. – Используйте их только при необходимости.