Specification of Software: UML State Machines

UML state machine, also known as UML statechart, is an extension of the mathematical concept of a finite automaton in computer science applications as expressed in the Unified Modeling Language (UML) notation.

The concepts behind it are about organizing the way a device, computer program, or other (often technical) process works such that an entity or each of its sub-entities is always in exactly one of a number of possible states and where there are well-defined conditional transitions between these states.

UML state machine is an object-based variant of Harel statechart, adapted and extended by UML. The goal of UML state machines is to overcome the main limitations of traditional finite-state machines while retaining their main benefits. UML statecharts introduce the new concepts of hierarchically nested states and orthogonal regions, while extending the notion of actions. UML state machines have the characteristics of both Mealy machines and Moore machines. They support actions that depend on both the state of the system and the triggering event, as in Mealy machines, as well as entry and exit actions, which are associated with states rather than transitions, as in Moore machines.

The term “UML state machine” can refer to two kinds of state machines: behavioral state machines and protocol state machines. Behavioral state machines can be used to model the behavior of individual entities (e.g., class instances), a subsystem, a package, or even an entire system. Protocol state machines are used to express usage protocols and can be used to specify the legal usage scenarios of classifiers, interfaces, and ports.

Basic state machine concepts

Many software systems are event-driven, which means that they continuously wait for the occurrence of some external or internal event such as a mouse click, a button press, a time tick, or an arrival of a data packet. After recognizing the event, such systems react by performing the appropriate computation that may include manipulating the hardware or generating “soft” events that trigger other internal software components. (That’s why event-driven systems are alternatively called reactive systems.) Once the event handling is complete, the system goes back to waiting for the next event.

The response to an event generally depends on both the type of the event and on the internal state of the system and can include a change of state leading to a state transition. The pattern of events, states, and state transitions among those states can be abstracted and represented as a finite-state machine (FSM).

The concept of a FSM is important in event-driven programming because it makes the event handling explicitly dependent on both the event-type and on the state of the system. When used correctly, a state machine can drastically cut down the number of execution paths through the code, simplify the conditions tested at each branching point, and simplify the switching between different modes of execution. Conversely, using event-driven programming without an underlying FSM model can lead programmers to produce error prone, difficult to extend and excessively complex application code.

Basic UML state diagrams

UML preserves the general form of the traditional state diagrams. The UML state diagrams are directed graphs in which nodes denote states and connectors denote state transitions. For example, Figure 1 shows a UML state diagram corresponding to the computer keyboard state machine. In UML, states are represented as rounded rectangles labeled with state names. The transitions, represented as arrows, are labeled with the triggering events followed optionally by the list of executed actions. The initial transition originates from the solid circle and specifies the default state when the system first begins. Every state diagram should have such a transition, which should not be labeled, since it is not triggered by an event. The initial transition can have associated actions.

Events

An event is something that happens that affects the system. Strictly speaking, in the UML specification, the term event refers to the type of occurrence rather than to any concrete instance of that occurrence. For example, Keystroke is an event for the keyboard, but each press of a key is not an event but a concrete instance of the Keystroke event. Another event of interest for the keyboard might be Power-on, but turning the power on tomorrow at 10:05:36 will be just an instance of the Power-on event.

An event can have associated parameters, allowing the event instance to convey not only the occurrence of some interesting incident but also quantitative information regarding that occurrence. For example, the Keystroke event generated by pressing a key on a computer keyboard has associated parameters that convey the character scan code as well as the status of the Shift, Ctrl, and Alt keys.

An event instance outlives the instantaneous occurrence that generated it and might convey this occurrence to one or more state machines. Once generated, the event instance goes through a processing life cycle that can consist of up to three stages. First, the event instance is received when it is accepted and waiting for processing (e.g., it is placed on the event queue). Later, the event instance is dispatched to the state machine, at which point it becomes the current event. Finally, it is consumed when the state machine finishes processing the event instance. A consumed event instance is no longer available for processing.

States

Each state machine has a state, which governs reaction of the state machine to events. For example, when you strike a key on a keyboard, the character code generated will be either an uppercase or a lowercase character, depending on whether the Caps Lock is active. Therefore, the keyboard’s behavior can be divided into two states: the “default” state and the “caps_locked” state. (Most keyboards include an LED that indicates that the keyboard is in the “caps_locked” state.) The behavior of a keyboard depends only on certain aspects of its history, namely whether the Caps Lock key has been pressed, but not, for example, on how many and exactly which other keys have been pressed previously. A state can abstract away all possible (but irrelevant) event sequences and capture only the relevant ones.

In the context of software state machines (and especially classical FSMs), the term state is often understood as a single state variable that can assume only a limited number of a priori determined values (e.g., two values in case of the keyboard, or more generally – some kind of variable with an enum type in many programming languages). The idea of state variable (and classical FSM model) is that the value of the state variable fully defines the current state of the system at any given time. The concept of the state reduces the problem of identifying the execution context in the code to testing just the state variable instead of many variables, thus eliminating a lot of conditional logic.

Extended states

In practice, however, interpreting the whole state of the state machine as a single state variable quickly becomes impractical for all state machines beyond very simple ones. Indeed, even if we have a single 32-bit integer in our machine state, it could contribute to over 4 billion different states – and will lead to a premature state explosion. This interpretation is not practical, so in UML state machines the whole state of the state machine is commonly split into (a) enumeratable state variable and (b) all the other variables which are named extended state. Another way to see it is to interpret enumeratable state variable as a qualitative aspect and extended state as quantitative aspects of the whole state. In this interpretation, a change of variable does not always imply a change of the qualitative aspects of the system behavior and therefore does not lead to a change of state.^[7]

State machines supplemented with extended state variables are called extended state machines and UML state machines belong to this category. Extended state machines can apply the underlying formalism to much more complex problems than is practical without including extended state variables. For example, if we have to implement some kind of limit in our FSM (say, limiting number of keystrokes on keyboard to 1000), without extended state we’d need to create and process 1000 states – which is not practical; however, with an extended state machine we can introduce a key_count variable, which is initialized to 1000 and decremented by every keystroke without changing state variable.