Abstract
A report highlighting the deficiencies inherent in conventional state machine modelling, and the features of Statechart modelling that facilitate the design of a solution by overcoming these deficiencies. The report also compares Statechart modelling with CSP and draws attention to their differences and similarities.
Introduction
The modelling facilities provided by the conventional state machine modelling technique are used frequently to model real time systems. Real time systems are based upon events happening to which the system responds, and then transitions to another state. This directly maps onto the state machine model for simpler systems.
This report examines the paucity of support for concurrent systems, which have an increasing role in real time systems, and how these deficiencies are recognised and overcome in the Statechart modelling paradigm.
The report will then compare and contrast the roles Statecharts modelling and CSP have when developing more complex systems.
Conventional State Machine Modelling
Explanation
State Machine Modelling is concerned with modelling the system which it describes as a collection of discrete sates. State machines model these states in a language independent manner. The state model of a system is always in one of its set of possible states, the model transitions from one state to another system state when stimuli are received.
Limitations
There are limitations to the use of conventional state machine modelling.
One of the limitations inherent in conventional state machine modelling techniques is the complexity of the state diagram increases dramatically as the number of possible states increases. The state machine model then becomes unwieldy to use, this detracts from the intended purposes of state machine models, to allow the system to be modelled in a more comprehensible manner.
Another of the limitations of modelling a computer system as a conventional state machine is the lack of support for concurrent constructs. Traditional state machine modelling is based on sequential transitions from one state to the next. Concurrent systems cannot be modelled in this manner as various aspects of the system may be in different states.
It is seen that the limitations inherent in state machine models include the inherent complexity which occurs as the number of states increases, and also the modelling of concurrent systems.
Statechart Modelling
Explanation
State machine modelling is the basis for various real-time methods such as that proposed by Ward and Mellor (1985) and Harel (1987). This section details how Harel’s method, Statechart modelling, overcomes the limitations of conventional modelling.
These limitations which have been shown to be present in state machine models are, the complexity of the model and the inability to model of concurrent systems.
Benefits of Statecharts with respect to Limitations of State Machines.
Statecharts overcome the limitations of state machines by providing a construct known as the and-state. In the Mealy-Moore state machine model, states were an or-state; they were either in one state or another, never in two states concurrently.
The and-state overcomes this limitation of or-states by allowing the state chart to have substates of a higher level state active at the same time. The state machine model could be decomposed into lower states, however these lower states were still sequential not contemporaneous, in the state chart modelling system proposed by Hare (1987) these substates may be concurrent. Each of these substates model an aspect of the object of which they are a part.
These substates are also allowed to communicate with each other in well-defined manners. These communication and synchronisation methods have been enumerated by Douglass (1999)
- All orthogonal regions of the chart accept events sent to the object
- One region may create an event as a result of a transition that is consumed by another orthogonal region.
- A guard may be used to test if another region is in a certain state before allowing a transition to occur to the guarded state.
The third enumerated point introduces the concept of a guard. This is a construct introduced to Statecharts which adds additional features not available in a state machine model, conditional event responses.
To overcome the second limitation of conventional state machine modelling, that of a quickly escalating level of complexity as the number of states increased, orthogonal regions are all used.
These regions allow the modeller to detail highly complex specification logic in a condensed manner. Harel (1997) stated “Modellers can use orthogonal states to decompose large state spaces naturally into independent (or almost independent) parts.” This flexibility enable statecharts to be far less complex as the number of states increases the modeller can use some of the more powerful facilities provided by statecharts, such as orthogonal regions and guards, to succinctly specify the required logic in a more comprehensible manner.
Comparison (of Statecharts) with CSP
Similarities
A brief overview of statecharts has now been provided, showing how the statechart method of system modelling overcomes the difficulties that may be experienced when attempting to model real-time systems using state machines.
CSP is another commonly used method of specifying the behaviour of modelled systems. It is also used to model the flow of control from one “state” to another, and also supports concurrency.
A fundamental aspect of CSP as defined by Hoare (1985) involves the synchronisation of concurrent processes on their inputs and outputs. The synchronisation only occurs when two processes wishing to synchronise to send a message, are both in a sending and receiving state respectively.
Statecharts also make provision for the synchronisation of states or processes with the functionality provided by guards. These guards are placed at the transition from one state to another. The transition may only occur when the transition event occurs and the condition on the guard is met, a conditional event response. This condition may be that another orthogonal region needs to be in a particular state. Thus these two separate states may be synchronised.
Both techniques are based upon mathematical foundations. This enables a degree of formalism to be inherent in designs produced according to these two methods, formal reasoning is therefore possible with both of these practices.
Contrasts
CSP and statecharts do provide similar functionality in many areas; this is to be expected due to their predominant use in developing real time systems. There are some differences within each of their respective paradigms.
Contrasting CSP and statecharts on a paradigmatic approach statecharts are concerned primarily with clearly and succinctly express complex logic relationships between states. Hilderink (2000) showed that CSP is primarily concerned with the specification of communicating concurrent processes, and describing complex communication patterns. CSP is not suitable for describing the internals behaviour of processes, whereas statecharts can address this.
The method by which CSP and statecharts describe the specification is also different. Statecharts provide a graphical representation of the system. CSP provides a character based representation. These two representations each have different advantages and disadvantages, a statechart may be more comprehensible to many people, a CSP description may be easier to include as a comment in source code thereby enabling the programmer easy access to the specification to which he is writing in an easy and unambiguous manner.
Statecharts are also unaware of the concept of time in the same respect as timed CSP. Although statecharts may recognise that transitions take some time (unlike state machines), they do not include the notion of states taking a measured amount of time in the same respect as timed CSP does. When developing real time systems timed CSP provides a better set of tools for dealing with “real time” than statecharts do.
Conclusions
Statecharts were introduced as a development over modelling techniques such as traditional state machine modelling. The weaknesses inherent in state machine modelling such as overly complex diagrams for larger systems, and the lack of concurrent support were addressed by the statechart method.
Statecharts overcame these weaknesses by introducing concepts such as orthogonal regions, and-states and also guards. These concepts allow for the specification of far more complex real time systems than traditional state machine modelling.
Other techniques for developing complex real time systems include CSP. These techniques provide slightly different aspects than statecharts at which systems can be specified. The basis of all these techniques in formal mathematics enables them to be used to comprehensibly specify the system in a provably correct manner. As well as this benefit, work is currently ongoing (Harel, 1997) into developing tools by which automatic synthesis of efficient code can be achieved from a suitably rigorous statechart specification. Hoare (1994) also describes the relationships which can exist between formal models such as programming languages and specification languages.
Statecharts are a methodology by which complex real time systems can be specified in an intuitive graphical manner. They enable complex relationships between concurrent states to be formed, through synchronisation techniques and decomposition of states.
References
D. Harel, “Statecharts: A visual Formalism for complex systems”, The Science of Computer Programming, 1987, 8, pp.231-274.
D. Harel, “Executable Object Modeling with Statecharts”, 1997, IEEE COMPUTER, Vol. 30, issue 7, JULY, pp.31-42
Also online at http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/OOStatecharts.pdf
P. Ward and S. Mellor, “Structured Development for Real-time Systems”, 1985, Prentice Hall pp.86 & 302.
B.P. Douglass, “UML Statecharts”, 1999, http://www.embedded.com/1999/9901/9901feat1.htm
C.A.R. Hoare, “Communicating Sequential Processes”, 1985, Prentice Hall International Series in Computer Science.
C.A.R. Hoare, “Mathematical Models for Computer Science”,1994,ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Tony.Hoare/mathmodl.ps.z
G. Hilderink, A. Bakkers, J. Broenink, “A Distributed Real-Time Java System Based on CSP”, 2000, The Third IEEE International Symposium on Object-Oriented Real-Time Distributed Computing ISORC 2000, California, March 15-17, pp. 400-407.
Also online at http://www.rt.el.utwente.nl/javapp/information/CTJ/DRTJSBCSP.pdf