9 An introduction to state machines
9.1 What is a state machine?
An event is an occurrence of a phenomenon at a certain moment in time. The occurrence of the event itself is assumed to have no duration. Typically, when an event occurs, it affects the state of an object. A state machine is a model of the behaviour of a single object over time and helps you to understand how that object's state affects its reactions to events.
Figure 18 shows a state machine diagram (known as a statechart diagram in the UML) relating to the occupancy of a room in a hotel. In this problem a room has two states: unoccupied and occupied. An unoccupied room becomes occupied when a guest checks into the hotel, and reverts to being unoccupied when the guest checks out.
The states are represented by rectangles with rounded corners containing their names. Transitions from one state to another are represented by arrows identified by the events that give rise to them. The solid black circle shows the initial state and indicates the starting state – that is, it says that a newly created room starts in the unoccupied state.
The events that fire the transitions have been given simple names: guest checks in and guest checks out. However, we can do better than this by specifying the event and the subsequent action. For example, one kind of event is the receipt of a message by an object which may cause the object to respond by sending a message to another object. Such a response is known as an action. Thus, if the event ‘guest checks out’ is initiated by a message being sent to the room object saying ‘vacate room’ and the room's response is to remove its association with a particular guest by sending itself the message ‘removeOccupant’ we could write:
vacateRoom / removeOccupant
Figure 19 shows a revised version of Figure 18 in which event / actions have been used.
In general, there can be several actions that result from a single event.
Sometimes an event might take place, but you only want a transition to fire under certain conditions. In the UML, conditions are modelled by guards. A guard is evaluated when an event occurs and a transition will only take place if the guard evaluates to ‘true’. For example, suppose that guests are only allowed to check into a room if they already have a reservation. We can indicate this on the state machine of Figure 19 by writing:
accept(aGuest) [reservation exists] / setOccupant(aGuest)
where, as usual, the guard is placed inside square brackets. This expression means ‘when the message (event) accept(aGuest) is received by the room object, the transition from the unoccupied state to the occupied state will only occur if the guest (denoted by aGuest) already has a reservation’.
Sometimes the same event can give rise to different transitions and actions depending on the prevailing conditions. To illustrate this, consider what happens when a hotel becomes full. If we identify two simple states ‘full’ and ‘not full’ for a hotel object, what happens as guests check in and check out? At some point the hotel will be unable to accept any more guests. This situation is shown in Figure 20.
The hotel is not full provided that there is at least one room that is unoccupied. Checking out is not a problem in this example. Both instances of the event checkOut(aGuest) lead to the not full state. However, an occurrence of the event checkln(aGuest) can lead to either the ‘not full’ state or the ‘full’ state depending on whether or not the hotel has at least one room unoccupied. Hence, the guard conditions are mutually exclusive, [last room] and [not last room].
Figure 20 contains two instances of a special kind of transition, known as a self-transition, that originates in one state and returns to the same state.
From the perspective of checking in and checking out, the state machine in Figure 20 is incomplete because it does not deal with the empty state. If every guest in the hotel checks out, the hotel is empty. Figure 21 illustrates one way of following the checking in and out of guests into a hotel that might be full, empty or somewhere in between. The maximum number of rooms in the hotel is denoted by hotelLimit and a simple counter, called availableRooms, keeps track of the number of unoccupied rooms in the hotel.
If the same event is used on more than one transition, you must make sure that no more than one guard can evaluate to true. At most, you want just one transition to fire in such situations. For example, which transition will fire if the hotelLimit is 100 and the value of availableRooms is two when the event checkln(aGuest) occurs and the Hotel object is in the ‘not full’ state? First of all, we do not need to worry about the hotelLimit under these conditions. There are two possibilities, the Hotel object either moves to the full state or remains in the not full state. Since the value of availableRooms is greater than one, it is the self-transition that is triggered.
It is recommended that you provide a guard on each event as illustrated in Figure 21. Doing so enables you to check that when the same event occurs more than once, for example, checkOut(aGuest) occurs three times in Figure 21, the associated guards are mutually exclusive (only one can be true at any one time).
You can view the diagram in Figure 21 as showing the normal processing, omitting exceptional cases such as what happens when the event checkln(aGuest) occurs and the hotel object is in the full state, or the event checkout(aGuest) occurs and the hotel object is in the empty state. It would be reasonable to view these cases as errors. You could represent such cases on the state machine by introducing an Error state and adding appropriate transitions. However, doing so makes the state machine more complex and hence more difficult to read and understand. There is always a trade-off between completeness and complexity and you may be better off by dealing with exceptional cases separately from the state machine.
In the UML, there is a simple device for reducing the complexity of some state machines by using two special events associated with each state:
an entry event that occurs every time an object enters a state, and
an exit event that occurs every time an object leaves a state.
Instead of writing the same action on two or more transitions leading to or from the same state, that action can be associated with the state's entry or exit event. For example, Figure 19 can be redrawn by adding an action to both an entry and an exit event, as shown in Figure 22.
Whenever you are tempted to use an entry event, you must remember that all transitions into the state will cause the entry event to occur. This means that the entry event must be appropriate for all incoming transitions. Similarly, an exit event must be appropriate for all outgoing transitions. In the case of a self-transition, both the entry and the exit events will occur, so you must take care to ensure that they are consistent with each other. A restriction on entry and exit events is that they may not have guards (simply because these events must occur, unconditionally).
We have shown that a state machine starts with a single initial state, denoted by a solid black circle. But what do we use to show that processing has completed or an object's life history has ended? The UML uses a final state, signified by a black circle surrounding a solid black circle to show that processing has terminated. An initial state has only one outgoing transition whereas a final state can have many incoming transitions but no outgoing transitions.
On a state machine there can be only one initial state but there can be more than one final state. For example, Figure 23 shows the life history of books in a lending library in which newly purchased copies of a book are put on the shelf for lending to the library's members. Damaged copies are removed from stock. At certain times of the year, the library is allowed to select copies of unwanted books to go on sale to the public.
As with any other kind of model, you should try to keep each state machine as simple as possible. The more often an attribute of an object changes, the more likely you are to want to model the object's behaviour in a state machine.