Открытая коллекция знаний

OpenU.Ru

Справочник UML. Объектно-ориентированное проектирование.

state machine (конечный автомат)

Спецификация последовательности состояний, через которые проходит в течение своей жизни объект, или взаимодействие в ответ на происходящие события (а также ответные действия объекта на эти события). Конечный автомат прикреплен к исходному элементу (классу, кооперации или методу) и служит для определения поведения его экземпляров.
См. activity graph; composite state; event; pseudostate; state; transition.

Семантика

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

Семантика выполнения конечного автомата

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

Запуск перехода и действия

Считается, что конечный автомат обрабатывает по одному событию за один раз и перед обработкой следующего события завершает все, что касается предыдущего. Другими словами, при обработке событий они (события) не взаимодействуют друг с другом, в таких случаях обычно говорят как о "выполнении до завершения". Это не означает, что все вычисления производятся непрерывно. Обычное расширенное вычисление можно разложить на несколько атомарных шагов, после чего внешнее событие может прервать его между любыми двумя такими шагами. Эта ситуация очень напоминает компьютер, где прерывания могут осуществляться в дискретные моменты времени (хоть и маленьким шагом дискретизации).
Из всего вышесказанного следует вывод, что события асинхронны. Два события никогда не происходят в один и тот же момент. Впрочем, правильнее будет сказать, что если два события происходят одновременно, то это считается совпадением - они могут выполняться в любом порядке. Различный порядок выполнения может привести к различным результатам (состояние событий, вообще, является основным свойством параллельных систем), однако в распределенной системе на одновременность полагаться нельзя. Любое вычисление, в котором это правило не выполняется, обладает логическими и физическими дефектами. Параллельное выполнение в распределенной системе требует независимости.
Теоретически действия происходят мгновенно, а события никогда не бывают одновременными. В программной реализации выполнение действий занимает некоторый промежуток времени, однако нужно помнить, что действия (теоретически) атомарны и непрерывны. Если объект получает событие во время выполнения действия, то это событие помещается в очередь до rex пор, пока это выполнение не закончится. Событие обрабатывается только в том случае, если в это время не осуществляется выполнение каких-либо действий. Если действие посылает сигнал другому объекту, то получение этого сначала не будет синхронным - его будут обрабатывать так же, как и любое другое событие, то есть после завершения действия (и перехода, который является его частью). Вызов операции приостанавливает работу элемента, который осуществил этот вызов, до тех пор, пока операция не будет выполнена. В программном коде это может быть реализовано в виде метода или в виде события вызова, которое запускает конечный автомат элемента-получателя. Действия должны быть короткими, и противном случае система не сможет обрабатывать события в течение длительных промежутков времени. С помощью действия нельзя моделировать долгие непрерывные вычисления - их лучше проектировать в виде вложенных автоматов или вложенных состоянии деятельности. Это даст системе возможность обрабатывать события и прерывать вложенные вычисления. Если же включить в реальную систему слишком длинные действия, то обработка событий не сможет производиться своевременно. Это явный признак плохого моделирования. Чтобы такого не произошло действия должны быть непродолжительными по сравнению со временем, которое необходимо для отчета на возможные события.
Если объект не занят осуществлением какого-либо действия, он немедленно приступает к обработке полученного события. Теоретически все действия мгновенны, однако в реальной жизни их выполнение все же занимает некоторое время. Следовательно, вновь поступившие события должны образовывать очередь. Если в очереди нет никаких событий, то объект будет обрабатывать первое получение им событие. Таким образом, за один раз объект обрабатывает по одному событию (однако это не является ограничением, так как действия считаются атомарными и мгновенными). При фактической реализации в программном коде события могут помещаться в очередь в определенном порядке. Семантика языка UML не определяет не рядок обработки параллельных событий, более того, разработчика вообще не следует заниматься этим. Если события должны обрабатываться в некотором порядке, значит, этот порядок должен определиться конечным автоматом. В процессе программной реализации используется какое-либо простое правило очередности обработки событий.
Во время обработки события в конфигурации активных состоянии объекта может находиться одно или несколько параллельных ее состояний. Каждое из этих состояний получает свою копию события. действует независимо от всех других параллельных событий. Переходы в параллельных состояниях также запускаются, независим друг от друга. Подсостояние может измениться, не затрагивая при этом остальные (за исключением случаев комплексных переходов - развилки и слияния, - которые мы опишем ниже).
Исходящие переходы могут запускаться из любого активного состояния объекта. Переход будет запускаться в том случае, если обрабатываемое объектом событие будет того же типа, что и переключающее событие для этого перехода, или будет являться ею потомком. Запускаться событием-предком переход не может. Во время обработки события при запуске перехода происходит оценка сторожевого условия. Если оно истинно, то переход действительно запускается. Сторожевое условие может включать в себя аргументы переключающего события или атрибуты объекта. Следует отметить, что сторожевые условия не имеют побочных эффектов. Другими словами, они не могут изменять состояние объекта или остальной системы. Следовательно, порядок их вычисления не влияет на результат. Сторожевое условие вычисляется только во время обработки события. Если в этот момент сторожевое условие ложно, то оно не высчитывается повторно, даже если какая-либо переменная со временем сделает его истинным.
Для структуризации сложных условий переход можно моделировать из нескольких сегментов. У первого сегмента находится переключающее событие, за ним следует дерево из всех остальных сегментов, у которых есть сторожевые условия. Промежуточными узлами итого дерева являются псевдосостояния (фиктивные состояния, служащие для структурирования переходов, которые не могут остаться активными после окончания непрерывного шага). Каждый возможный маршрут по этому дереву рассматривается, как отдельный переход и может выполняться независимо от других. Отдельный сегмент запуститься не может. Для того чтобы переход запустился, необходимо, чтобы были истинными все сторожевые условия (на всех его сегментах), в противном случае переход не запустится. В действительности, сторожевые условия часто делят все возможные результаты в точке разветвления. Таким образом, многосегментный переход может быть реализован пошагово, хотя и не всегда.
Если не может запуститься ни один из переходов, то событие попросту игнорируется. Это не является ошибкой. Если возможен только один переход, то он и запускается. Если же из одного состояния может осуществиться сразу несколько переходов, то запускается только один из них. При отсутствии ограничений запустится любой из переходов - при этом невозможно определить, будет ли выбор перехода предсказуемым или случайным. В программной реализации могут быть свои правила для разрешения конфликтов, однако мы не рекомендуем на них полагаться - лучше моделировать выбор переходов явным образом. Событие обрабатывается независимо от того, запустило оно переход или нет.
Запускаться могут переходы, исходящие из активного состояния. Кроме них, могут запускаться переходы из любого композитного состояния, одно из вложенных состояний которого является активным. Можно считать, что переходы наследуются подсостояниями - точно так же, как операции наследуются подклассами. Переход во внешнем состоянии запускается только в том случае, если не запускается ни один их переходов во внутреннем состоянии. В противном случае его перекрывает внутренний переход.
При запуске перехода выполняется любое прикрепленное к нему действие. В выражении, описывающем действие, могут использоваться аргументы переключающего события, а также атрибуты объекта, которому принадлежит это событие, и доступные этому объекту значения. Действие атомарно, оно завершается до того, как начнут обрабатываться прочие события. Если у перехода есть несколько сегментов, то параметры переключающего события доступны действиям этих сегментов в качестве неявного текущего события.
Если объект имеет параллельные состояния, то они не могут взаимодействовать посредством общей памяти. Параллельные состояния независимы друг от друга и действуют на различных множествах значений. Любые взаимодействия должны моделироваться явно, в виде отправки сигналов. В случае если два параллельных состояния должны иметь доступ к одному общему ресурсу, они должны явно отправить атому ресурсу сигнал, после чего тот выступает арбитром. Такую коммуникацию можно включить в программную реализацию, однако, при этом нужно следить, чтобы и результате не возникла конфликтная ситуация. Если параллельные действия имеют доступ к общим значениям, то результат будет неопределенным.
Если переход пересекает границу композитного состояния, то выполняются действия при входе и выходе. Переход может пересекать границу в том случае, если его исходное и целевое состояния находятся в различных композитных состояниях. Кроме того, это может получиться в случае, если переход унаследован от внешнего композитного состояния, в связи, с чем объект вынужден совершить выход из одного или более внутренних состояний. Обратите внимание, что внутренний переход не приводит к смене состояния, а значит, не вызывает действий при входе и выходе.
Для того чтобы определить, какие действия при входе и выходе будут выполняйся во время перехода, необходимо найти текущее активное состояние объекта (оно может быть вложено, в то композитное состояние, которому принадлежит переход) и целевое состояние этого перехода. Затем найдите самое внутреннее композитное состояние, объемлющее как текущее состояние объекта, так и целевое состояние перехода. Назовем его общим предком. Итак, будут выполняться действия при выходе из текущего состояния и всех, объемлющих сто состояний, вплоть до (но не включительно) общего предка. Первым выполняется наиболее внутреннее действие. После этого выполняется действие перехода. Теперь будут выполняться действия при входе в целевое состояние и всеобъемлющие его состояния, вплоть до (по не включая) общего предка. Первым выполняется самое внутреннее действие. Другими слонами, осуществляется последовательный выход из всех состояний до тех пор, пока процесс не дойдет до общего предка. Затем выполняется действие, прикрепленное к переходу. После этого начинается вход в состояния - до тех пор, пока не будет достигнуто целевое состояние. Действия при входе и выходе, которые есть у общего предка, не выполняются, поскольку он остается неизменным. Такая процедура гарантирует строгую инкапсуляцию каждого состояния.
Действие, прикрепленное к переходу, выполняется сразу после действий при выходе из состояния и непосредственно до действий при входе.
Следует отметить, что запуск перехода в себя (из состояния в это же состояние) приводит к выходу из всех вложенных состояний, находящихся внутри начального состояния, которое может быть активно (переход мог быть унаследован от внешнего композитного состояния). Переход в себя приводит к выполнению действий при выходе из начального состояния, за которым следует выполнение действия при входе. Иначе говоря, сначала осуществляется выход из состояния, а потом вход в него же. Если это нежелательно, то следует моделировать ситуацию при помощи внутреннего перехода - это не приведет к изменению состояния, даже если активное состояние вложено в то состояние, которому принадлежит переход.
Во время выполнения непрерывного шага все действия имеют доступ к неявному текущему событию, которое представляет собой событие, запустившее первый переход в непрерывной последовательности. К выполнению действия может приводить несколько событий, поэтому для того, чтобы выполнять альтернативные ветви кода, действие может различать типы текущих событий (как, например, в языке Ada или у полиморфных операций).
После выполнения всех действий исходное текущее состояние становится неактивным (если только оно не является одновременно и целевым состоянием) - активизируется целевое состояние, после чего могут обрабатываться все последующие события.
Переход можно структурировать при помощи нескольких сегментов, узлы, пересечения которых представляют собой переходные состояния. Каждый сегмент может иметь свое собственное действие. Эти действия могут чередоваться с действиями при входе и выходе общего перехода. Что касается действий при входе и выходе, то каждое действие сегмента перехода выполняется таким обратом, будто сегмент является полным переходом (см. рис. 117).
Внутренние переходы
У внутреннего перехода есть исходное состояние, но нет целевого. Запуск такого перехода не приводит к изменению состояния даже в том случае, если переход наследуется от внешнего состояния. Следовательно, действия при входе и выходе не выполняются. Единственным следствием внутреннего перехода будет выполнение прикрепленного к нему действия. Условия запуска внутреннего перехода совпадают с условиями запуска внешнего.
Обратите внимание, что запуск внутреннего перехода может перекрыть внешний переход, который использует то же самое событие. Таким образом, внутренний переход без прикрепленного к нему действия тоже имеет смысл. (Как мы уже говорили, событие может запустить только один переход, а внутренний переход имеет приоритет над внешним.)
Внутренние переходы удобны для обработки событий без изменения состояния.
Исходное и конечное состояния
В целях инкапсуляции состояний нередко требуется отделить внутреннюю часть состояния от внешней. Кроме того, переходы удобно связывать с самим композитным состоянием, не учитывая его внутреннюю структуру. Для этого служат исходное и конечное состояния композитного состояния.
У композитного состояния могут быть исходное и конечное состояния. Исходное состояние представляет собой фиктивное состояние, обладающее связностью обычных состояний, в котором объект нe может оставаться. Объект может остаться в конечном состоянии, однако у конечного состояния нет никаких явно запускаемых переходов, так как его цель состоит в вызове перехода по завершении во внешнее состояние. У исходного состояния должен быть исходящий
переход по завершении. Если таких исходящих переходов несколько, то переключающих событий у них нет, а выбор соответствующего перехода осуществляется посредством сторожевого условия. Другими словами, при вызове исходного состояния запуститься может только один переход. При этом объект никогда не остается в исходном состоянии, а немедленно переходит в какое-либо обычное состояние.
Если у композитного состояния есть исходное состояние, то целью перехода может быть непосредственно композитное состояние. Любой переход в композитное состояние представляет собой неявный переход в его исходное состояние. Если исходного состояния нет, то целью перехода не может являться само композитное состояние - он должен вести прямо во вложенное состояние. У состояния, имеющего исходное состояние, могут быть как переходы, связанные непосредственно с внутренними состояниями, так и с композитным состоянием в целом.
Если у композитного состояния есть конечное состояние, то из него могут исходить один или несколько переходов по завершении, то есть, переходов, у которых нет явных переключающих событий. На самом деле, переход по завершении запускается сам по себе, при окончании всякой деятельности внутри данного состояния. Таким образом, переход в конечное состояние представляет собой утверждение завершения выполнения композитного состояния. Когда объект переходит в конечное состояние, запускаются переходы по завершении, которые выходят из внешнего композитного состояния этого объекта (разумеется, если удовлетворены сторожевые условия этих переходов).
У композитного состояния также могут быть помеченные исходящие переходы (то есть переходы, у которых есть явные переключающие события). Если происходит событие, которое приводит к запуску такого перехода, то заканчивается любая текущая деятельность в этом состоянии (на всех уровнях вложенности), выполняются действия при выходе из оконченных вложенных состояний и выполняется переход. При помощи таких переходов обычно моделируются исключения и сбойные ситуации.
Комплексные переходы
При переходе в параллельное композитное состояние происходит переход во все его параллельные подсостояння. Это может осуществляться двумя способами.
У перехода может быть несколько целевых состояний, по одному на каждое параллельное подсостояние. Обратите внимание, что у такого перехода-развилки есть только одно переключающее сооытие, сторожевое условие и действие. Это явный переход в композитное состояние, который непосредственно специфицирует каждое целевое состояние. Он представляет собой явную развилку управления на параллельные подпотоки.
Кроме того, переход может не укалывать явные цели в одном или нескольких параллельных подсостояниях или же его целью может являться непосредственно само композитное состояние. В этом случае у каждого пропущенного параллельного полсостояния должно быть исходное состояние, которое указывает на то состояние, которое по умолчанию считается стартовым. В противном случае конечный автомат считается плохо согласованным. При запуске комплексного перехода активизируются целевые параллельные подсостояния, а также исходные состояния других параллельных подсостояний. Короче говоря, любой переход в параллельное подсостояние подразумевает переход в исходные состояния всех прочих параллельных подсостояний, которые не были упомянуты явно. Переход в само композитное состояние подразумевает переход в исходные состояния каждой из его параллельной подобластей. Если параллельное композитное состояние активно, значит, активны нее его подобласти.
Точно так же переход из любого параллельного полсостояния означает переход из всех этих подсостояний. Если осуществление события вызывает запуск такого перехода, то деятельность в остальных подсостояниях заканчивается, выполняются их действия при выходе, затем выполняется действие самого перехода, после чего активизируется целевое состояние (уменьшая, таким образом, количество активных состояний).
Переход к конечному состоянию параллельного полсостояния не вызывает прекращения других параллельных подсостояний (поскольку это не является выходом из подсостояния). Когда все параллельные подсостояния достигнут своих конечных состояний, то считается, что внешнее композитное состояние закончило свою деятельность. После этого из этого состояния запускаются переходы по завершении.
У комплексного перехода может быть несколько исходных состояний и несколько целевых состояний, В таком случае его повеление будет представлять собой комбинацию развилки и слияния, которые
мы описали выше.
Историческое состояние
В композитном состоянии может находиться историческое состояние, которое также является псевдосостоянием. Если унаследованный переход приводит к автоматическому выходу из композитного состояния, то это псевдосостоянне "запоминает" то подсостояние. которое было активным непосредственно перед выходом. Переход в историческое псевдосостояние, находящееся внутри композитного состояния, приводит к восстановлению запомненного подсостояния. При явном переходе в какое-либо другое или в само внешнее состояние механизм исторических состояний не задействуется, в такой ситуации достаточно правил обычного перехода. Впрочем, исходное состояние композитного состояния может быть связано с историческим состоянием. В этом случае переход в композитное состояние косвенно задействует механизм исторических состояний. Историческое состояние может обладать одним исходящим переходом по завершении, у которого нет сторожевого условия. Целью такого перехода является историческое состояние по умолчанию. Если в определенную область некоего состояния вообще не было переходов или же если из нее был осуществлен обычный выход, то целью перехода в историческое состояние является состояние, на которое указывает переход из исторического состояния, то есть историческое состояние по умолчанию.
Существует два вида исторических состояний - кратковременное и долговременное. Кратковременное историческое состояние служит для восстановления тех состояний, которые содержатся в том же самом композитном состоянии, что и само историческое состояние. Долговременное историческое состояние восстанавливает то состояние или состояния, которые были активны до явного последнего перехода, вызвавшего выход из внешнего композитного состояния. Эти состояния могут находиться на любой глубине вложенности. У композитного состояния может быть не больше одного исторического состояния каждого вида, и у каждого из них может быть свое собственное историческое состояние по умолчанию.
Лучше всего, если ситуацию удается смоделировать без исторических состояний, поскольку они довольно сложны сами по себе и не всегда легко совместимы с механизмами реализации в программном коде. Особенно это относится к долговременному историческому состоянию, вместо которого вообще правильнее использовать другие, более явные механизмы, которые легко поддаются реализации.

Нотация

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

Эта нотация была создана Дэвидом Хзрелом (David Harel). В нее входят некоторые аспекты автоматов Мура (Моигс) (действия при входе), автоматов Мили (Mealy) (действия, прикрепленные к переходам), а также концепции, относящиеся к вложенным и параллельным состояниям.
Более подробную информацию смотрите в статьях state; composite state; submachine; pseudostate; entry action; exit action; transition и activity. Еще один вариант нотации, которую можно использовать для потока деятельности, вы найдете в статье activity graph.
См. также статью control icons энциклопедии, в которой делаются дополнительные символы, изначально предназначенные для диаграмм деятельности, которые, тем не менее можно использовать и в диаграммах состояний.

Обсуждение

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

Алфавитный указатель