Design State Machine Engine for embedded system de

1 Introduction

This article discovers how to design a state machine engine for embedded system development.

2 Background

Embedded systems are some special purpose computers that are used inside of devices. Embedded systems generally use micro controllers that contain many functions of a computer on a single device.

Embedded systems have to tightly work together with special hardware. They have to respond to external interactions in a predetermined amount of time. Usually embedded systems are real time.

Many embedded system applications are natural candidates for being organized as a state machine. A program that must sequence a series of actions, or handle inputs differently depending on what state it's in, is often best implemented as a state machine.

In general, a state machine is any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change. In practice, however, state machines are used to develop and describe specific device or program interactions.

3 Address Embedded System Design Issues with State Machines

1) Real Time Response

Real time systems have to respond to external interactions in a predetermined amount of time. Successful completion of an operation depends upon the correct and timely operation of the system. Design the hardware and the software in the system to meet the real time requirements.

2) Communication

Components can use the following communication mechanism to exchange information:

(a) Synchronous communication / service calls. These synchronous service calls made by a customer, return immediately after the operation finishes. If caller and callee are executed in different task/thread, it will cause task/thread blocking.

(b) Asynchronous communication / service calls. These asynchronous service calls made by a customer, return before the operation completes. The service provider will respond with asynchronous events to the customer after finishing operation.

(c) Pro-active event indication. These events are posted from a service component to a customer component without any request.

Thus most embedded systems support state machine based design where multiple events can be received in a single state. The next state is determined by the contents of the received event. State machines provide a very flexible mechanism to handle asynchronous event interactions. The flexibility comes with its own complexities.

3) Working with Distributed Architecture

Most real time systems involve processing on several different nodes. The system itself distributes the processing load among several processors. Software in different components may run in some concurrent threads. Usually different components exchange information by asynchronous events.

4) Recovering from Failures

Real time systems must function reliably in event of failures

5) Race Conditions and Timing

A race condition occurs when the state of a resource depends on timing factors that are not predictable. Embedded system can use synchronization mechanism to ensure operation integrity.

State machine is a good approach to implementing embedded systems. Over the last years, people have used this approach to design dozens of systems, including a softkey-based user interface, several communications protocols, a silicon-wafer transport mechanism, an unmanned air vehicle's lost-uplink handler, and an orbital mechanics simulator.

4 Hierarchical State Machine Engine Implementation

In general, a state machine is any device that stores the status of something at a given time and can operate on input to change the status and/or cause an action or output to take place for any given change.

To summarize it, a state machine can be described as:

• A set of states
• An initial state or record of something stored someplace
• A set of input events
• A set of output events
• A set of actions or output events that maps states and input to output (which is called a state event handler)
• A set of actions or output events that states and inputs to states (which is called a state transition)

Usually, state machines allow users to model complex behavior via composite state with more than one hierarchy level. The state machine state hierarchy is based on a parent-child relationship.

• Similar sub-states are grouped into a composite state (nesting hierarchy is a tree);
• Composite states can have transitions, entry/exit actions, . . .(transitions can connect states from different nesting levels);
• Sub-states "inherit" from the composite state;
• Active state denotes a path from a top-level state to a leaf node in the state hierarchy;
• There must be an initial sub-state in every composite state. On entering a compose state or sub-state, both of them are activated. Order of the entry functions is from top to down.
• On exiting a composite state, exit active sub-state as well. Order of the exit functions is from down to top.

4.1 State Machine Data Construction

We could define a set of specific macros as state machine mapping data. These macros map to state enumerations, event handler function declarations, event handler table for a state, state tree definition and application variable definition.

4.1.1 State Enumeration

#define SME_BEGIN_STATE_DECLARE(_app) \
enum _app##_state_enum_t \
{
#define SME_STATE_DECLARE(_state) _state, 
#define SME_MAX_STATE(_app)
_app##_max_state	 
#define SME_END_STATE_DECLARE };

4.1.2 State Event Handler Table Definition

#define SME_ENTRY_FUNC_IDX	0
#define SME_EXIT_FUNC_IDX	1
#define SME_EVENT_HANDLER_FUNC_IDX	2
#define SME_BEGIN_STATE_DEF(_app,_state) \
static const SME_EVENT_TABLE_T _app##_state##_event_hdl_tbl[] \
={
#define SME_STATE_ENTRY_FUNC( _EntryFunc) \
{  SME_INVALID_EVENT_ID, _EntryFunc, 0},
#define SME_STATE_EXIT_FUNC( _ExitFunc) \
{  SME_INVALID_EVENT_ID, _ExitFunc, 0},
#define SME_ON_EVENT(_EventID, _Handler, _NewState) \
{  _EventID, _Handler, _NewState},
#define SME_END_STATE_DEF
{ SME_INVALID_EVENT_ID, 0, SME_INVALID_STATE}};

4.1.3 State Tree Definition

#define SME_BEGIN_STATE_TREE_DEF(_app) \
extern const SME_STATE_TREE_TABLE_T _app##_state_tree[] = \
{
#define SME_STATE
(_app,_state,_state_parent,_def_substate) \
{(SME_EVENT_TABLE_T *)
_app##_state##_event_hdl_tbl,
_state,_state_parent,_def_substate},
#define SME_END_STATE_TREE_DEF };
4.1.4	Application Definition
#define SME_APPLICATION_DEF(_app,_app_name) \
struct SME_APP_T _app##App = { \
_app_name, NULL, NULL, 0, NULL,	NULL, _app##_state_tree,
 SME_INVALID_STATE};
/* Get application variable name. */
#define SME_GET_APP_VAR(_app) _app##App
/* Declare application variable that has external linkage. */
#define SME_DEC_EXT_APP_VAR(_app)
 extern SME_APP_T _app##App;

4.2 State Machine Engine Type Definitions

/////////////////////////////////////////////////////////////
//  State Machine Engine Type Definitions
/////////////////////////////////////////////////////////////
//// State Definition
typedef short SME_STATE_T;
#define SME_APP_STATE		0
#define SME_INVALID_STATE	-1
//// Event Definition
// Positive 32-bit integer values are user-defined
// event identifiers.
// Negative 32-bit integer values are state machine
// engine defined event identifiers.
typedef long SME_EVENT_ID_T;
#define SME_INVALID_EVENT_ID	-1
#define SME_EVENT_KILL_FOCUS -2
#define SME_EVENT_SET_FOCUS  -3
typedef enum
{
SME_EVENT_CAT_UI=0,
SME_EVENT_CAT_OTHER,
};
typedef unsigned char SME_EVENT_CAT_T;
typedef enum
{
SME_EVENT_ORIGIN_INTERNAL=0,
SME_EVENT_ORIGIN_EXTERNAL,
};
typedef unsigned char SME_EVENT_ORIGIN_T;
typedef enum
{
SME_EVENT_DATA_FORMAT_INT=0,
SME_EVENT_DATA_FORMAT_PTR,
};
typedef unsigned char SME_EVENT_DATA_FORMAT_T;
typedef	struct SME_INT_DATA_T
{
unsigned long nParam1;
unsigned long nParam2;
} SME_INT_DATA_T;
typedef struct SME_PTR_DATA_T
{
void* pData;
unsigned long nSize;
} SME_PTR_DATA_T;
union SME_EVENT_DATA_T
{
SME_INT_DATA_T	Int;
SME_PTR_DATA_T  Ptr;
};
typedef struct SME_EVENT_T
{
SME_EVENT_ID_T nEventID;
unsigned long nSequenceNum;
struct SME_EVENT_T *pNext;
/* Provide 2 data formats: integer or pointer */
union SME_EVENT_DATA_T Data;
struct SME_APP_T *pDestApp; /* The destination application. */
unsigned long nOrigin :8; /* */
unsigned long nCategory :8; /* Category of this event. */
unsigned long nDataFormat :8; /* Flag for this event. */
unsigned long bIsConsumed :8; /* Is comsumed. */
}SME_EVENT_T;
typedef struct SME_APP_T
{
const char * sAppName;
struct SME_APP_T *pParent; /* Who starts me */
struct SME_APP_T *pNext; /* Applications are linked together. */
unsigned long nPortId;
void * pPortHandle;
void * pData;
const struct SME_STATE_TREE_TABLE_T *pStateTree;
SME_STATE_T nAppState;
}SME_APP_T;
#define SME_APP_DATA(app) (app.pData)
#define SME_IS_ACTIVATED(app) 
(app->nAppState != SME_INVALID_STATE)
typedef int (* SME_EVENT_HANDLER_T)
(SME_APP_T *, SME_EVENT_T *);
#define SME_INTERNAL_TRAN
SME_INVALID_STATE
typedef struct SME_EVENT_TABLE_T {
SME_EVENT_ID_T nEventID;
SME_EVENT_HANDLER_T pHandler;
SME_STATE_T nNewState;
}SME_EVENT_TABLE_T;
typedef struct SME_STATE_TREE_TABLE_T{
SME_EVENT_TABLE_T *pEventTable;
SME_STATE_T nState;
SME_STATE_T nParentState;
SME_STATE_T nDefSubState;
}SME_STATE_TREE_TABLE_T;

4.3 Event Dispatch Implementation

/**************************************************************/
* DESCRIPTION: Dispatch the incoming event to an application
* if it is specified, otherwise dispatch to all active 
* applications untile it is consumed.  
* INPUT:  
*  1) pEvent: Incoming event 
*  2) pApp: The destination application that event
*     will be dispatched.
*  OUTPUT: None.
*  NOTE: 
*	1) Call exit functions in old state   
*	2) Call event handler functions   
*	3) Call entry functions in new state  
*       4) Transit from one state region to another state region.
* All states exit functions that jump out 
* the old region will be called. And all states exit
* functions that jump in the new region will be called.
* 5) Although there is a property pEvent->pDestApp in
* SME_EVENT_T, this function will ignore this one,
* because if pEvent->pDestApp is NULL, this
* event have to dispatch to all active applications.
*****************************************************************/
BOOL SmeDispatchEvent(struct SME_EVENT_T *pEvent, struct SME_APP_T *pApp)
{
SME_STATE_T nOldState; /* Old state should be a leaf.*/
SME_STATE_T nState;
SME_STATE_T nNewState;
int i;
BOOL bFoundHandler=FALSE;
SME_EVENT_HANDLER_T pHandler = NULL;
SME_STATE_T OldStateStack[SME_MAX_STATE_TREE_DEPTH];
SME_STATE_T NewStateStack[SME_MAX_STATE_TREE_DEPTH];
SME_STATE_T nOldStateStackTop =0;
SME_STATE_T nNewStateStackTop =0;
/* Trace back from leaf to root, 
so as to retrieve all event handler tables.
 Find what nNewState is */
struct SME_EVENT_TABLE_T *pStateEventTable;
if (pEvent==NULL || pApp==NULL) 
return FALSE;
nOldState = pApp->nAppState; /* Old state should be a leaf. */
nState = nOldState;
pStateEventTable = pApp->pStateTree[nOldState].pEventTable;
/****************************************************************
 Check the state's event handler table from leaf to root.
 If find it, stop searching, no matter there
 is another handler in parent sate's event table.
*/
while (TRUE)
{
/* Check the current state's event handler table.*/
	
i=SME_EVENT_HANDLER_FUNC_IDX;
while (pStateEventTable[i].nEventID != SME_INVALID_EVENT_ID)
{
if (pStateEventTable[i].nEventID == pEvent->nEventID)
{nNewState=pStateEventTable[i].nNewState;
bFoundHandler = TRUE;
pHandler = pStateEventTable[i].pHandler;break;
} else
i++;
}
		
if (bFoundHandler || (nState == SME_APP_STATE))break;
/* Get the parent state's event handler table. */
nState = pApp->pStateTree[nState].nParentState; 
pStateEventTable = pApp->pStateTree[nState].pEventTable;
}
	
if (!bFoundHandler) 
return FALSE;
/***********************************************************/
if (nNewState != SME_INTERNAL_TRAN)
{
/* It is a state transition.
Push all old state's ancestors.
*/
nState = nOldState;
while (nState!=SME_APP_STATE)
{
OldStateStack[nOldStateStackTop++] = nState;
nState=pApp->pStateTree[nState].nParentState;
if (nOldStateStackTop >= SME_MAX_STATE_TREE_DEPTH)
return FALSE;
}
/* Push all new state's ancestors. */
nState = nNewState;
while (nState!=SME_APP_STATE)
{
NewStateStack[nNewStateStackTop++] = nState;
nState=pApp->pStateTree[nState].nParentState;
if (nNewStateStackTop >
= SME_MAX_STATE_TREE_DEPTH) return FALSE;
}
/* Pop all equal states except the last one.
Special case 1: self transition state1->state1,
leave one item in each stack.
Special case 2: parent state transits to child state,
leave one item in parent state stack.
*/
while ((nOldStateStackTop>1) && (nNewStateStackTop>1)
&& (OldStateStack[nOldStateStackTop-1] ==
 NewStateStack[nNewStateStackTop-1]))
{
nOldStateStackTop--;
nNewStateStackTop--;
}
/* Get the leaf of the old state.
Note: Old state should be a leaf state.
Call exit functions from leaf nState to old state stacks top.
 */
for (i=0; i{
nState = OldStateStack[i];
if(pApp->pStateTree[nState].pEventTable[SME_EXIT_FUNC_IDX].pHandler)
pApp->pStateTree[nState].
pEventTable[SME_EXIT_FUNC_IDX].pHandler(pApp,pEvent);
};
}; /* end of not internal transition.*/
/*********************************************************
 Call event handler function if given event handler
 is available and handler is not empty.
 Maybe their is a transition, however handler is empty.
*/
if (bFoundHandler && pHandler)
{
(*pHandler)(pApp,pEvent);
};
/*********************************************************
 Call entry functions from new state stack's top to leaf state. */
 if (nNewState != SME_INTERNAL_TRAN)
 {
/* It is a state transition.
Call entry functions from ancestor to new state.
*/
for (i=nNewStateStackTop-1; i>=0; i--)
{
nState = NewStateStack[i];
if(pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler)
pApp->pStateTree[nState].
pEventTable[SME_ENTRY_FUNC_IDX].pHandler(pApp,pEvent);
};
/* Call entry functions from new state's child to leaf. */
nState=nNewState;
while (pApp->pStateTree[nState].nDefSubState
!= SME_INVALID_STATE) /* It is not a leaf. */
		{
nState=pApp->pStateTree[nState].nDefSubState;
/* Call default sub-state's entry function.*/
if(pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler)
pApp->pStateTree[nState].
pEventTable[SME_ENTRY_FUNC_IDX].pHandler(pApp,pEvent);
}
pApp->nAppState = nState; 
/* New application state
 is the destination state's leaf. */
};
/************************************************************
Call event handle hook function
if given enent handler is available and no 
matter whether handler is empty or not
*/
if (bFoundHandler && g_fnOnEventHandleHook)
(*g_fnOnEventHandleHook)((SME_EVENT_ORIGIN_T)(pEvent->nOrigin), 
pEvent, 
pApp, 
pApp->nAppState);
#ifdef WIN32
#ifdef _DEBUG
if (bFoundHandler)
StateTrack(pEvent, pApp, pApp->nAppState);
#endif
#endif
return TRUE;
}

5 Application Manager

Programs on embedded system usually can be divided into a few applications. There are two kinds of mode for these applications: active or inactive. Active applications are exactly running on the state machine whereas inactive applications are not. In other words, only active applications can handle events. State machine engine is responsible for managing these applications and dispatching events to specific applications.

Embedded system program has to tightly co-work with lower layer (other modules) or hardware, which are called service providers. A service is formally specified by a set of primitives (operations) available to service users (applications). These primitives tell the service to perform some action or report on an action taken by a peer component/entity. The service primitives are classified to four categories: request, indication, response and confirm [Computer Networks, Andrew S.Tanenbaum]. The request and confirm primitives can be implemented in form of service calls. The indication and response primitives can be implemented in form of external event posting.

On simulation environment, developer can design some simulator using Windows program as service providers. These simulators have identical interface with target service providers' interface. On target environment, developer may take little effort to integrate state machine applications with these service providers to real environment. Active applications may make some service calls exported by service providers, meanwhile may receive some external events triggered by service providers through RTOS functions. There are many different RTOSs although they provide similar functions. RTOS Virtual Layer provides a set of platform independent functions so that it can be moved to other platforms without any state machine applications changes.

Communication between applications and service providers can be in asynchronous mode or synchronous mode. Applications are running on application thread. At same time, service providers are running on another service provider thread.

http://www.programmersheaven.com/articles/jerryding/design/image001.gif

Figure: Embedded System Block Diagram

6 UML State Machine Wizard

When UML was first being adopted, many embedded developers started by incorporating it through static CASE technology to allow them to capture their systems and software architecture visually. One of the most popular CASE technologies with the early adoption of UML has been Rational Rose. However as technology has evolved, CASE tools like Rose did not provide the step up in development necessary to keep pace with ongoing technology evolutions. Mode-Driven Development (MDD) environments which provide clear model to code synchronization as well as automated base simulation and validation, have proven to be the key process enabler to keep product development teams in step with emerging technologies.

Visual C++ is a powerful software developing tool. However it aims at developing Windows-specific applications. UML State Machine Wizard acts as a Visual C++ add-in, which provides a UML (Unified Modeling Language) state machine programming mechanism in portable standard C for embedded systems developing and simulating in Visual C++ developer studio. After simulating and debugging, developer can move the program to a destination working environment with little or no extra investment or effort.

The following picture shows the State Tree tab window in debugging mode. It tracks the application state transitions while program is running. The current active application set includes PowerUpDown only, and its active state is (PowerUp, Idle).

http://www.programmersheaven.com/articles/jerryding/design/image002.gif

Figure: State Tree in Debugging Mode

About the author

Jerome Ding has worked at some embedded system companies, launching products initiatives, such as developing framework, simulation environment, debugging and error prevention tools for embedded systems. He is the architect of the product of UML State Machine Wizard. He received his Master degree in Computer Science in 2000. He may be contacted at [e-mail].