GB2377285A

GB2377285A - State machine

Info

Publication number: GB2377285A
Application number: GB0116191A
Authority: GB
Inventors: Joby Allen; Raj Gawera
Original assignee: Ubinetics Ltd
Current assignee: Aeroflex Cambridge Ltd
Priority date: 2001-07-02
Filing date: 2001-07-02
Publication date: 2003-01-08
Also published as: GB0116191D0; WO2003005137A1

Abstract

A state machine hierarchy 10, 12 wherein certain states S<SB>m</SB>, S<SB>r</SB> contain exit transitions 14, 16 leading to other state machines. When a state machine is left in favour of another, its exit state is saved onto the C-stack. Events arising which are not applicable to the currently active state machine are saved on the C-stack.

Description

DATA PROCESSING The invention relates to data processing and event handling. In particular, the invention relates to state machines.

According to one aspect, the invention provides a data processing system comprising a parent state machine and a child state machine each comprising a group of states interlinked by transitions, wherein the parent state machine comprises a parent exit state in which an appropriate event causes the execution of a parent exit transition to a state in the child state machine.

The invention thus provides that a state machine can be decomposed into a hierarchy of interacting state machines. For example, a complex system can be represented as a hierarchy of simpler state machines which facilitates efficient definition of the overall system.

The data processing system according to the invention may also be arranged such that the parent exit transition is accompanied by deactivation of the parent state machine in favour of the child state machine. This means that the data processing system's resources need only be sufficient to run either the child or the parent state machine.

In one embodiment, the data processing system is arranged such that the parent exit transition is accompanied by storing of parameters defining the parent exit state used to depart the parent state machine into memory, e. g. a memory stack of the system. Where the data processing system is being implemented using a C-language type system, the parameters can be stored on the C-stack.

The child state machine may comprise a child exit state in which an appropriate event causes the execution of a child exit transition to a state in the parent state machine. Thus, the data processing system can be adapted to provide a return path to the parent state machine. Preferably, the child exit transition is accompanied by the deactivation of the child state machine in favour of the parent state machine, which means that the system

resources need only be sufficient to run either the child or parent state machine at any one time. Advantageously, the child exit transition is accompanied by the retrieval from a memory e. g. a memory stack, of parameters defining the parent state machine state to which the child exit transition leads.

In one embodiment, the data processing system is arranged such that details of an event are saved into storage, e. g. a memory stack, if the event is not applicable to the state machine which is currently active. The data processing system may also be arranged such that details of an event saved in storage may be retrieved when a state machine to which the event applies becomes active in order to allow the event to be processed. For example, if, during operation of the child state machine, an event occurs which is applicable to the parent state machine, then the details of the event can be stored until such time as the parent state machine again becomes active, at which point the details of the event can be retrieved to allow the event to be processed by the parent state machine.

It is possible that the data processing system according to the invention may contain a hierarchy of more than two levels, i. e. more than just the"parent"and"child"levels discussed above. For example, the child state machine may itself have a child state machine, and so on. The state machines in the hierarchy can be interlinked using exit transitions as discussed above.

By way of example only, the invention will now be described with reference to the accompanying figures, in which: Figure 1 illustrates a state machine; and Figures 2 and 3 each illustrate a state machine implemented as a state-event matrix; and Figures 4 and 5 each illustrate state machines linked so as to call one another.

The state machine of Figure 1 illustrates the simple case of an electric light operated by a push button switch. The system has two states A and B, in which the light is on and off

respectively. When the button is pressed, the system toggles to the other one of its states.

In other words, when the event of pressing the switch occurs, then, regardless of the current state, the"press"event triggers a transition to the other state. These transitions are indicated by the arrows in Figure 1.

Figure 2 illustrates how the state machine of Figure 1 can be rendered as a state-event matrix. The state-event matrix of Figure 2 contains a column for each state and a row for each event. Hence, the state-event matrix comprises a single row for the"press"event and two columns, one each for the A and B states. The entries in the state-event matrix are populated with the necessary actions. If the current state is A, and the event is"press", then the action is"go to state B". If the current state is B, and the event is"press", then the action is"go to state A".

Figure 3 shows how the state-event matrix can be extended to arbitrary size, using the example of n columns for n states and m rows for m events.

Figure 3 illustrates a state machine hierarchy according to an embodiment of the invention.

The state machine hierarchy is implemented using a C-type programming language and comprises a parent state machine implemented as a parent state-event matrix 12 and a child state machine implemented as a child state-event matrix 10. When the parent state machine is in a particular state, for example Sm, and a particular event, for example en, occurs then a sequence of actions are performed to call the child state machine. The parameter values defining state Sm are saved onto the C-stack of the system, the parent state machine is closed, the child state machine is opened and a state of the child state machine, for example Sp, is nominated as the active state. Subsequently, the active state moves around the child state event matrix 10 in accordance with whichever events occur. When the child state machine is in a particular state, for example Sr, and a particular event, for example, eq, occurs, then the active state is transferred back to the parent state machine. To achieve this transfer, the child state machine is closed, the parameter values for the parent state machine are retrieved from the C-stack and the active state is assigned as the state in the parent state machine which is specified by the retrieved parameter values. Thus, either the parent state machine or the child state machine is active at any given time. If an event

occurs which cannot be processed by the state machine which is currently active, then it is saved onto the C-stack pending the activation of a state machine to which the event applies.

The transitions between the state machines are shown by arrows 14 and 16.

Figure 5 illustrates a state machine hierarchy according to an embodiment of the invention being used to implement a controller for configuring telecommunications transceiver equipment, such as a mobile telephone. The state machine hierarchy is being used to configure a controller which works with a layered communications protocol, where inter-layer communication is achieved via signalling. Consider the case where layer N of a protocol is a controller layer which is responsible for configuring layers N-1 and N-2 in response to external signals. The parent state machine, designated as an external signal handler in Figure 5, responds to the external signals by calling the layer N-1 or N-2 state machine to configure the N-1 and N-2 layers respectively. The child state machines each only contain state-event actions to handle responses from their respective layers, and do not respond to external signals. Any external signals received during the execution of a child state machine are saved for processing when the child state machine exits. This ensures that the state machine implementations are"clean", i. e. they only contain transitions relevant to their purpose.

Claims

CLAIMS 1. A data processing system comprising a parent state machine and a child state machine each comprising a group of states interlinked by transitions, wherein the parent state machine comprises a parent exit state in which an appropriate event causes the execution of a parent exit transition to a state in the child state machine.
2. A data processing system according to claim 1, wherein said appropriate event in said parent exit state causes the parent state machine to be deactivated.
3. A data processing system according to claim 1 or 2, wherein said appropriate event in said parent exit state causes parameters defining the parent exit state to be stored on a memory stack of the system.
4. A data processing system according to claim 1, 2 or 3, wherein the child state machine comprises a child exit state in which an appropriate event causes the execution of a child exit transition to a state in the parent state machine.
5. A data processing system according to claim 4, wherein said appropriate event in said child exit state causes the child state machine to be deactivated.
6. A data processing system according to claim 4 or 5, wherein said appropriate event in said child exit state causes the retrieval from a memory stack of the system of parameters defining the parent state machine state to which said child exit transition leads.
7. A data processing system according to any one of claims 1 to 6, wherein an event is saved to a memory stack of the system if it is not applicable to the state machine which is currently active.
8. A data processing system according to claim 7, wherein an event stored on the memory stack is retrieved when a state machine to which it applies becomes active to allow the event to be processed by the state machine.

<Desc/Clms Page number 6>
9. A data processing system comprising state machines substantially as hereinbefore described with reference to Figure 4 or 5.