|
tutorials |
|
Next
State:UML Statecharts
Action:
prepare RTOS, fine-tune for acceptable real-time performance,
plan for difficult validation and verification, be prepared to
explain non-deterministic behavior and other anomalies, update
resume, check out Staccato™
- or
-
Next
State: Staccato™
Action:
be prepared for excellent real-time performance and
fully-deterministic behavior, welcome validation and
verification, add IEEE-CEUs to your resume, modestly accept your
bonus, raise and promotion.
Click here to get started...
|
|
|
Tutorial 5: 'Current
State' of Finite State Machines for Embedded Software Applications |
|
Previous State... |
|
Classical Mealy/Moore Finite State Machines have been used in the design
of embedded software applications likely since the 1970's, using
either assembly or the C-language. Using Finite State Machines in
embedded software has never achieved the status of a 'de-facto standard',
and to this day,
FSMs are likely used in only a small percentage of deployed embedded
systems. This may seem surprising, since 'embedded systems' implies
strong coupling between hardware and software, and the fact that Finite
State Machines have been the heart of digital sequential circuit design
(i.e. microprocessors, microcontrollers, communication controllers, etc)
even prior to that time. As hardware engineers originally took on the
task of writing software/firmware, it was soon recognized that software
development should be performed by more creative types, resulting in not
only a separation of activities, but also of mindsets and territorial
claims and responsibilities. Much 'finger-pointing' occurred between
hardware and software groups when things went wrong, which likely set
the foundation for software types to seek new solutions and methods
among their own, as computer scientists and engineers. This separation
of hardware and software was inevitable and necessary to the evolution
of the entire embedded industry, but unfortunately it seems, the
usefulness of Finite State Machine concepts in software got lost in the
rubble, save a few who, to this day, will attest to FSMs as being most beneficial even to software development.
Eventually, the C-language evolved into C++ to address more esoteric
challenges, and in the 1990's, embedded software engineers were found
scratching their heads trying to adopt the concepts of polymorphism,
abstraction and inheritance to make their products safer, more reliable
and less costly to develop. A decade later, the
Unified Modeling
Language (UML) was developed to provide more structure and modeling
capabilities to the realm of software development for enterprise/desktop
applications. To achieve broader acceptance among the embedded community
of developers, or possibly recognizing the usefulness of Finite State
Machine concepts, the UML 2.0 specification added Statecharts, based on
Harel[87]. Statecharts claims advancements over the classical
Mealy/Moore paradigm by adding two new concepts: hierarchical (nested)
state machines and orthogonality (independence and concurrency).
Even though the UML is a 'modeling language' and Statecharts a
'Visual Formalism for Complex Reactive Systems', many products based on
UML and Statecharts offer
visual FSM development tools and auto-code generation capabilities. The
execution framework for the resulting FSM code is usually a Real-Time
Operating System, or RTOS, which, for the most part, is a derivation of
enterprise/desktop computer operating systems, customized to meet the
real-time requirements of most embedded systems. These (real-time)
operating systems are complex and quite non-deterministic,
characteristics which must be addressed for any embedded system, using FSMs or not. |
|
The
Embedded Systems Design 2008 Market Study indicates that basically 1
project in 5 uses UML and 1 project in 5 either uses no commercial
Operating System/RTOS or uses one developed 'in-house'. The 2008
Survey does not include any data on the use of Finite State Machines or
Statecharts. |
|
Current State... |
|
So, on one hand, if an
embedded systems software developer decides to use Finite State Machine
concepts on a project, he/she will need to have a
comprehensive understanding of the Object-Oriented concepts of polymorphism,
inheritance and abstraction, the UML Statechart concepts of hierarchical
Finite State Machines and orthogonality, and real-time operating system
(RTOSes) kernals and schedulers, plus some basic Mealy and Moore
concepts. Now let's add up the cost of development tools, training and learning
curves, licenses, etc...
On the other hand, embedded software
developers can choose Staccato™ as an embedded system software
architecture using Finite State Machines. No RTOS is needed, as
Staccato™ FSMs are executed directly and continuously by an executive, providing
exceptional real-time performance. Statechart orthognonality (or
concurrency/AND states) is inherent in the Staccato™ method of
partitioning a system by resource, resulting in a 'system of Finite
State Machine-encoded tasks'. Staccato™ is based on classic Mealy and
Moore state machines without the need for, or perceived benefits of,
polymorphism, inheritance or abstraction as provided by the C++
programming language. The Staccato™ Crossroads SDK provides IEEE-CEU
Certified Training; all that is needed to implement Staccato™ in your
embedded system software is an ANSI-Compliant C Compiler as part of your
software development toolchain.
|
|
How Finite State Machines are
Implemented in Software... |
 |
Basic Method -
Using a Nested 'switch' Statement... |
|
The easiest way to
implement a Finite State Machine in software using the
C-Language is to use a 2-level
nested 'switch' statement, as shown in the C source code to the
left. The first level 'switches' on the current state of
the machine. Normally, states will be defined as constants such
as _INIT or _IDLE, etc, but here they are simply numbered. Next, within each
state defined in the outermost 'switch', a second level of
switching occurs for each defined event. Again, these events
should be defined as constants, but here they are numbered. Notice that a 'get_event()'
function is called with its return value assigned to the switch
variable 'event'. The outer 'switch' gets us to the current state,
and the inner 'switch' gets us to the event. The code to be
executed next will perform the necessary action and then specify
the next state. This example does
not specify how this FSM is executed, only the basic construct
of using a nested 'switch'. Notice that this construct becomes
inefficient as more states and more events are defined within
the machine. |
|
Using a State
Table |
|
A more
efficient method of implementing a Finite State Machine is to
use a State Table as shown in the diagram below. The number of
rows correspond to the number of states, and each row-state
contains the actions and next states for the defined events
along the columns. This could be implemented in C as a
2-dimensional array of a data structure (containing an action
code pointer and next state value). |
 |
|
|
Staccato™ uses a
simplified
state table concept to provide direct and continuous execution of FSM-encoded
tasks. These basic
concepts are discussed in much detail with many examples in the
Staccato™ Crossroads SDK,
taking the confusion and unnecessary complexity out of the process of
using Finite State Machines for your embedded system software
architecture.
For more information on
UML and Statechart-based products, check out these links:
|
|
|
|