State Machines Lectures 13 & 14 PDF

Lectures 13 and 14 State machines Course 2024/2025 Software Engineering 2024/2025 Why do computer scientists never tell lies? Software Engineering 2024/2025 UML - State Machine Diagrams Software Engineering 2024/2025 3 Or...

Lectures 13 and 14 State machines Course 2024/2025 Software Engineering 2024/2025 Why do computer scientists never tell lies? Software Engineering 2024/2025 UML - State Machine Diagrams Software Engineering 2024/2025 3 Originally State charts David Harel Based on Finite state machines to describe large, complex, reactive systems behaviour, bring: Broadcast (communication) Orthogonality (concurrency) Depth (abstraction, nesting of statecharts) Memory (History mechanism) Software Engineering 2024/2025 4 State Charts and their role in OO design Software Engineering 2024/2025 Guido Zockoll, Axel Scheithauer & Marcel Douwe Dekker, “History of Object-Oriented Modeling Languages”, 2009 5  State machines are defined during design State machines are usually defined during the design workflow Create a state machine to understand a complex life cycle or behaviour ○ If it is too simple, it may not pay off to do so Particularly useful in real-time, embedded systems, where objects may have complex behavior and life cycles Software Engineering 2024/2025 6  A state diagram models the dynamic behaviour of a reactive object Goal: to model behaviour (dynamic) Use for modelling objects (or systems) with complex behaviour (that would otherwise be hard to understand) Use when the control is deeply influenced by external events Don’t use when several objects are involved ○ Interaction diagrams are more adequate, in that scenario Software Engineering 2024/2025 7  Key elements in state machine diagrams State ○ A condition or situation during the life cycle of an object during which it satisfies some condition, performs some activity, or waits for some event Event ○ The specification of a noteworthy occurrence that has location in time and space Transition ○ The movement from a state to another in response to an event Software Engineering 2024/2025 8 A reactive object provides context for a state machine Responds to external events May generate and respond to internal events Has a life cycle modelled as a progression of states, transitions, and events May have current behaviour that depends on past behaviour Software Engineering 2024/2025 9  State machines model the behaviour of classifiers, such as Classes Use cases Subsystems Entire systems Software Engineering 2024/2025 10  Behavioural vs protocol state machines Behavioural state machines Protocol state machines Specify the implementation of a Do not specify the implementation of behaviour this behaviour, only use order and results of operations calls Can be used to specify the behaviour of classifiers with implementation Can be used to specify the protocol for all classifier, including those States can specify one or more without implementation actions that execute when the state is entered States can’t specify actions Denoted by the keyword {protocol} after the state machine name Software Engineering 2024/2025 11 State machine diagrams Software Engineering 2024/2025 12  Example of correspondence to Java code Fragment (incomplete) of a State Machine of a Lecture Hall: More detailed version for implementation: class LectureHall { private boolean free; occupy() public void occupy() { free = false; free = free = } true false public void free() { release() free = true; } } Software Engineering 2024/2025 13  State is a semantically significant condition of an object A condition or situation during the life cycle of an object during which: ○ It satisfies some condition ○ Performs some activity ○ or waits for some event The state consists of: ○ Name ○ Actions, or activities ○ Internal transitions ○ Sub-states ○ Deferred events (to delay the answer to certain events) Software Engineering 2024/2025 14  Actions are instantaneous and uninterruptible Each action in a state is associated with an internal transition triggered by an event ○ In this example, two special actions, entry and exit are modelled The entry event occurs immediately after entering a state and causes the event action to execute The exit event is the last thing that happens on exiting the state and causes the associated event action action syntax: eventName/ someAction to execute activity syntax: do/ someActivity Software Engineering 2024/2025 15  Internal transitions capture that some transition within the same state has happened Each internal transition captures an event which is noteworthy but does not cause a state transition ○ In this example, it is relevant to know that a key was pressed, or that help is being internal displayed, but none of those cause leaving the transitions state EnteringPassword Software Engineering 2024/2025 16  Actions are instantaneous and uninterruptible Each action in a state is associated with an internal transition triggered by an event entry and exit actions are associated with two special events (entry and exit) The entry event occurs when the state is entered The exit event is the last thing to occur when the state is exited action syntax: eventName/ someAction activity syntax: do/ someActivity Software Engineering 2024/2025 17  Activities take finite time to execute and are interruptible Each activity takes a finite time to execute and is interruptible by an event The keyword do indicates an activity Unlike actions, activities can be interrupted before they finish processing action syntax: eventName/ someAction activity syntax: do/ someActivity Software Engineering 2024/2025 18  Types of States Real States ○ The ones described before Pseudostates ○ Those are transient. The system cannot remain in a pseudostate. They are not states in the actual sense but rather control structures that enable more complex states and state transitions. Initial state and Terminate node Decision node Junction Parallelization and synchronization nodes History Entry and exit points Software Engineering 2024/2025 19  Initial state Has no incoming edges and usually one outgoing edge which leads to the first “real” state. If multiple outgoing edges are used, their guard conditions must be mutually exclusive and cover all possible cases to ensure that exactly one target state is reached. As soon as the system is in the initial state, it immediately — that is, without consuming any time—switches to the next state. Software Engineering 2024/2025 20  Terminate and Final state nodes If a terminate node is reached in a flow, the state machine terminates and the modeled object ceases to exist Final state is not pseudostate and has at least one incoming edge and no outgoing edges. It marks the end of the sequence of states. The object can remain in a final state permanently. Software Engineering 2024/2025 21  Transitions show movement between states Relationship between two states, indicating that an object in the source state will execute certain actions and transition to a target state, when a given set of events occur and certain conditions are met Example: On (event1 or event2), if (guardCondition) then perform anAction and enter state B. Software Engineering 2024/2025 22  A transition occurs when 1. An object is in its source state 2. An event occurs 3. If a guard condition is true a. An action is executed b. The object changes to the target state Software Engineering 2024/2025 23  Transitions have three optional elements Zero or more events ○ These specify external or internal occurrences that can trigger the transition Zero or one guard condition ○ This is a boolean expression that must evaluate to true before the transition can occur Zero or more actions ○ This is a piece of work associated with the transition and occurs when the transition fires Software Engineering 2024/2025 24  Transitions in state protocols have a slightly different syntax There is no action, as we are specifying a protocol rather than an implementation The guard condition is replaced by pre and post conditions ○ Notice how the precondition is placed before the slash while the postcondition is placed after the slash Software Engineering 2024/2025 25  What if the transition has no event? If a transition has no event it is an automatic transition Automatic transitions ○ do not wait for an event ○ fire when their guard conditions or preconditions are true Software Engineering 2024/2025 26 Junction pseudo-states join or branch transitions Junction pseudo-states represent points where transitions merge or branch They may have one or more input transitions and one or more output transitions Software Engineering 2024/2025 27  Protect junction pseudo-states with mutually exclusive guard conditions Note how the junction pseudo-state has two inputs and two mutually exclusive guards, [extend] and [!extend] Note also the junction pseudo-state before the OnLoan state Software Engineering 2024/2025 28 The choice pseudo-state directs the flow through the state machine according to guard conditions Software Engineering 2024/2025 29 Upon receiving the acceptPayment event, the BankLoan object transitions to one of three states Software Engineering 2024/2025 30 The choice pseudo-state guard conditions are mutually exclusive, so that only one transition is fired Software Engineering 2024/2025 31  Attention In (c) the first transition increments b an only then the guards are evaluated while in (d) the guards are evaluated first and then b is incremented Software Engineering 2024/2025 32 Junction points can also help tidying up your diagram, to increase its understandability Without the junction With the junction Software Engineering 2024/2025 33 Events trigger transitions event Software Engineering 2024/2025 34 The same event (e.g. checkmate), when on different states, may lead to different outcomes Software Engineering 2024/2025 35  There are four kinds of events Call events Signal events Change events Time events Software Engineering 2024/2025 36 A call event is a request for a specific operation to be invoked on an instance of the context class Software Engineering 2024/2025 37  Call events A call event should have the same signature as an operation of the context class of the state machine ○ This applies to internal and external call operations Receiving a call operation triggers the operation to execute You can specify a sequence of actions, separated by “;”, for a call event ○ these specify the semantics of the operation and can use attributes and operations of the context class and may have a return type - the call event has a value of the same return type Software Engineering 2024/2025 38  A signal event is a one-way asynchronous communication between objects A signal event is a package of information sent asynchronously between objects ○ It usually does not have operations, as its purpose is to carry information Software Engineering 2024/2025 39 SimpleBankAccount sends a signal when withdrawal is rejected Software Engineering 2024/2025 40 A signal receipt accepts the signal as a parameter and leads to a new state Software Engineering 2024/2025 41  Change events occur when a Boolean expression changes value from false to true A change event implies continuously testing the Boolean condition while in state. Change events are positive-edge triggered - they are triggered whenever the condition changes from false to true. Software Engineering 2024/2025 42  Time events occur in response to time Time events are usually indicated with the keywords when, or after: when specifies a particular time in which the event is triggered. [e.g. when (date = 2018/12/07)] after specifies a threshold time after which the event is triggered. [e.g. after (3 months)] Software Engineering 2024/2025 43 Composite states Dealing with model complexity Software Engineering 2024/2025 44  Initial and process are substates of On Initial and Process “inherit” the switchOff If a composite state is active, only one of its substates is active at any point in time. Software Engineering 2024/2025 45  Orthogonal states - Composite states that contain one or more nested submachines To achieve concurrent states, a composite state can be divided into two or more regions, whereby one state of each region is always active at any point in time Each submachine exists in its own region within the composite state Software Engineering 2024/2025 46  Regions are independent, concurrent parts of a composite state - they are activated synchronously Each region can also have a final state. In this case, the completion event of the higher level state is not created until the final state is reached in all regions. Software Engineering 2024/2025 47  Entering and exiting composite states A transition to the boundary of the orthogonal state activates the initial states of all regions To enter in a composed state, you need to This is an equivalent alternative to have an initial substate in each region representing this model, using pseudo-states “fork” and “join”. Software Engineering 2024/2025 48  Nested substates inherit all of the transitions of their containing superstates If the composite state has a transition, each of its nested states also has this transition Software Engineering 2024/2025 49  The final pseudo-state of a submachine only applies within that region If the second submachine reaches its final state first, that region will terminate, but the first region will continue to execute In contrast, when the terminate pseudo-state of the first region is reached, the whole composite state stops Software Engineering 2024/2025 50  Nested states can also be composite states This mechanism should be used with parsimony ○ When possible keep nesting to two or three levels Beyond that, the state machine tends to become hard to read and understand To keep the state machine simple, you may hide the details of a composite state ○ Use the composition icon to denote that a given state is a composite state Software Engineering 2024/2025 51  Entry and Exit points: type of encapsulation mechanism If an external transition leads to this entry point, the execution can be started with the desired state without the external transition having to know the structure of the composite state. If the composite state is not to be ended as usual when the final state is reached but instead through the ending of another state, you can model exit points in the same way. Software Engineering 2024/2025 52  Simple vs orthogonal composite spaces Simple composite state ○ One region only Orthogonal composite state ○ Two or more regions Software Engineering 2024/2025 53 Simple composite states contain a single nested state machine Software Engineering 2024/2025 54 Orthogonal composite states contain two or more nested state machines that execute concurrently When you enter an orthogonal composite state, all its submachines start at once (this is an implicit fork) You can exit an orthogonal composite state ○ When all its submachines finish (this is an implicit join) ○ When one of its submachines transitions to a state outside the supermachine, usually via an exit pseudo-state This does not cause a join - no synchronization among submachines The remaining submachines simply abort Software Engineering 2024/2025 55  example Software Engineering 2024/2025 56  Initializing composite state: synchronization between submachines The initialization only finishes after both InitializingFireSensors and InitializingSecuritySensors finish. Software Engineering 2024/2025 57  Monitoring composite state: no synchronization between the two submachines If a fire is detected, we exit the monitoring state. Similarly, if an intruder is detected, we also exit the monitoring state. Software Engineering 2024/2025 58  A submachine state references another state machine (recorded in a separate diagram) Semantically equivalent to a composite state Submachine states are used to simplify complex state machines Submachine states provide a reuse mechanism Syntax: state name: name of referenced state machine diagram Software Engineering 2024/2025 59 Consider this machine state Software Engineering 2024/2025 60 Now, we can reuse the VerifyingUser submachine state Software Engineering 2024/2025 61 It is as if the contents of the submachine state are replaced by VerifyingUser Software Engineering 2024/2025 62 You can use attribute values to communicate asynchronously between concurrent submachines When we set paidFor in the top submachine, this enables the transition in the bottom one! Software Engineering 2024/2025 63 You can also use Synch state synchronization points to synchronize different regions (in combination with fork and join) We can only start the project after Lab1 is done. Software Engineering 2024/2025 64 Memory in State Machines Software Engineering 2024/2025 65 Shallow history remembers the last substate you were in at the same level as the shallow history pseudo-state Software Engineering 2024/2025 66 Shallow history remembers the last substate you were in at the same level as the shallow history pseudo-state Software Engineering 2024/2025 67 Deep history remembers the last substate you were in at the same level, or lower, than the deep history pseudo-state Software Engineering 2024/2025 68 Examples Software Engineering 2024/2025 69 Examples with memory (history state) Software Engineering 2024/2025 70 What happens with H ? It remembers and restores the previously active state at the same nesting depth Assume that E is active and event e1 occurs. G becomes active. When G is active and event e5 occurs, the next state might be B, C, or F (depending on which was active before - in our example, it would be C) The next state is not E, even if it was previously active, because H does not remember it. Software Engineering 2024/2025 71  What happens with H*? H* remembers and restores the previously active state at any depth Assuming that E is active and event e1 occurs, G is the next active state If now e3 occurs, C and more concretely E becomes the next active state Software Engineering 2024/2025 72 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 73 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 74 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 75 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 76 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 77 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 78 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 79 SEQUENCE OF EVENTS: e4 -> e5-> e1 http://elearning.uml.ac.at/submitQuiz Software Engineering 2024/2025 80 Did you really understand State Machines? Test yourself at: http://elearning.uml.ac.at/ Software Engineering 2024/2025 81  References Jim Arlow and Ila Neustadt, “UML 2 and the Unified Process”, Second Edition, Addison-Wesley 2006 Software Engineering 2024/2025 82  Why do computer scientists never tell lies? Because they can't stand unhandled exceptions. Software Engineering 2024/2025