Real-Time Systems Development

104 Real-time systems development

it will need to be cancelled manually. The radio will need to be timed out

after 30 mins. At some time in the future, an Internet connection may also

be demanded.

5.10 Hierarchical state charts

Criticism of FSM as a design tool is often focused on its lack of expressive

power when dealing with complex problems. It provides no immediate facil-

ities to handle large systems which would generally be viewed hierarchically,

to assist with their progressive decomposition into parts. This enables peo-

ple to cope with all the low-level details separately. With the introduction

of statecharts, David Harel (1987) introduced the concept of nested FSMs,

where every state is capable of sequestering another ‘internal’ FSM.

Washing

Pause1

motor off

Set timer

TumbleCCW

motor on CCW

Set timer

Pause2

motor off

Set timer

TumbleCW

motor on CW

Set timer

Filling

Open valve

Heating

Heater on

Draining

Pump on

Cancel pressed

Washing machine as a hierarchical FSD

Now, following the above figure, if the client wants a manual override

button to drain the water immediately, whichever of the four washing sub-

states it is in, all that is needed is a single transition arrow coming from the

washing superstate. This is then interpreted as originating from all the con-

tained substates, which saves confusing the diagram with repetitive, extra

transitions. In the case of a transition onto a superstate, one component

substate may be designated as the default start or entry state. In such a sit-

uation, where a sub-FSM is hidden inside a superstate, all inward transitions

are routed on to the ‘initial’ substate, and it is not necessary to save the

substate index number when leaving the superstate. However, there is also

Finite state machines – design tool 105

the option of directing incoming transitions back to the same substate from

which a superstate exit was last achieved. This is referred to as ‘entry with

history’, and requires the superstate to store its own state index number.

Another example of the application of statecharts is presented below. This

involves the sequence of button presses used to set up a digital watch. The

NEXT button selects the time or date display, and also moves through the

digits when initializing time or alarm values. So a button pressing sequence

of NEXT, SET, NEXT, INCR, END would set the display to time, enter

NEXT

INCR

SET

END

Digital watch buttons

Display

h

min

hour

day

month

year

Clock

min

hour

day

month

year

Alarm

Setting

TOD

Alarm

Cleared Set

Alarm

next

next

set

set

set

next

next

next

next

next

next

next

incr

incr

incr

incr

incr

alarm set

Hierarchical statechart for the digital watch