Introduction
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.
Hierarchical 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.
To summarize it, a state machine can be described as:
- A set of states.
- An initial state or record of something stored somewhere.
- A set of input events.
- A set of output events.
- A set of actions or output events that maps the states and input to output (which is called a state event handler).
- A set of actions or output events that maps the 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;
- The 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. The order of entry functions is from top to bottom.
- On exiting a composite state, exit the active sub-state as well. The order of exit functions is from bottom to top.
Type definitions
typedef short SME_STATE_T;
#define SME_APP_STATE 0
#define SME_INVALID_STATE -1
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;
union SME_EVENT_DATA_T Data;
struct SME_APP_T *pDestApp;
unsigned long nOrigin :8;
unsigned long nCategory :8;
unsigned long nDataFormat :8;
unsigned long bIsConsumed :8;
}SME_EVENT_T;
typedef struct SME_APP_T
{
const char * sAppName;
struct SME_APP_T *pParent;
struct SME_APP_T *pNext;
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;
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.
- 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 };
- 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}
};
- 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
};
- 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};
#define SME_GET_APP_VAR(_app) _app##App
#define SME_DEC_EXT_APP_VAR(_app) extern SME_APP_T _app##App;
Event dispatch
BOOL SmeDispatchEvent(struct SME_EVENT_T *pEvent, struct SME_APP_T *pApp)
{
SME_STATE_T nOldState;
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;
struct SME_EVENT_TABLE_T *pStateEventTable;
if (pEvent==NULL || pApp==NULL) return FALSE;
nOldState = pApp->nAppState;
nState = nOldState;
pStateEventTable = pApp->pStateTree[nOldState].pEventTable;
while (TRUE)
{
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;
nState = pApp->pStateTree[nState].nParentState;
pStateEventTable = pApp->pStateTree[nState].pEventTable;
}
if (!bFoundHandler) return FALSE;
if (nNewState != SME_INTERNAL_TRAN)
{
nState = nOldState;
while (nState!=SME_APP_STATE)
{
OldStateStack[nOldStateStackTop++] = nState;
nState=pApp->pStateTree[nState].nParentState;
if (nOldStateStackTop >= SME_MAX_STATE_TREE_DEPTH)
return FALSE;
}
nState = nNewState;
while (nState!=SME_APP_STATE)
{
NewStateStack[nNewStateStackTop++] = nState;
nState=pApp->pStateTree[nState].nParentState;
if (nNewStateStackTop >= SME_MAX_STATE_TREE_DEPTH)
return FALSE;
}
while ((nOldStateStackTop>1) && (nNewStateStackTop>1)
&& (OldStateStack[nOldStateStackTop-1] ==
NewStateStack[nNewStateStackTop-1]))
{
nOldStateStackTop--;
nNewStateStackTop--;
}
for (i=0; i<nOldStateStackTop; 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);
};
};
if (bFoundHandler && pHandler)
{
(*pHandler)(pApp,pEvent);
};
if (nNewState != SME_INTERNAL_TRAN)
{
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);
};
nState=nNewState;
while (pApp->pStateTree[nState].nDefSubState != SME_INVALID_STATE)
{
nState=pApp->pStateTree[nState].nDefSubState;
if(pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler)
pApp->pStateTree[nState].pEventTable[SME_ENTRY_FUNC_IDX].pHandler(
pApp,pEvent);
}
pApp->nAppState = nState;
};
if (bFoundHandler && g_fnOnEventHandleHook)
(*g_fnOnEventHandleHook)((SME_EVENT_ORIGIN_T)(pEvent->nOrigin),
pEvent, pApp, pApp->nAppState);
return TRUE;
}
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 the lower layer (other modules) or hardware, which are called service providers. A service is formally specified by a set of primitives (operations) available to the 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 the form of service calls. The indication and response primitives can be implemented in the form of external event posting.
In a simulation environment, a developer can design a simulator using a Windows program as service providers. The interfaces of these simulators are identical to the interface of target service providers. In a target environment, a developer may take a little effort to integrate the state machine applications with these service providers to real environment. Active applications may make some service calls exported by the service providers, and meanwhile may receive some external events triggered by the service providers through the 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 change in the state machine application.
The communication between the applications and the service providers can be either in asynchronous mode or in synchronous mode. The applications run on application thread, at same time, the service providers run on service provider thread.
UML state machine wizard
When UML was first adopted, many embedded developers incorporated it through the 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 was the Rational Rose. However as the technology evolved, CASE tools like Rose could not provide the step up in development necessary to keep pace with the ongoing technology evolutions. The Mode-Driven Development (MDD) environments which provide clear model for code synchronization as well as automated base simulation and validation, has proved to be the key process enabler to keep the product development teams in step with the 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 developing and simulating embedded systems in Visual C++ developer studio. After simulating and debugging, the developer can move the program to a destination working environment with little or no extra investment or effort.
