为嵌入式系统开发设计状态机引擎
本文介绍如何为嵌入式系统开发设计一个分层状态机引擎。
引言
嵌入式系统是一些用于设备内部的专用计算机。嵌入式系统通常使用微控制器，这些微控制器在一个设备上集成了计算机的许多功能。嵌入式系统必须与专用硬件紧密协作。它们必须在预定的时间内响应外部交互。通常，嵌入式系统是实时的。许多嵌入式系统应用自然适合组织成状态机。一个必须按顺序执行一系列操作，或者根据其所处状态以不同方式处理输入的程序，通常最好实现为状态机。
一般来说，状态机是任何在给定时间存储某事物状态的设备，并且可以根据输入来改变状态以及/或为任何给定变化触发动作或输出。
分层状态机
一般来说，状态机是任何在给定时间存储某事物状态的设备，并且可以根据输入来改变状态以及/或为任何给定变化触发动作或输出。
总而言之，状态机可以描述为：
- 一组状态。
- 一个初始状态或存储在某处的东西的记录。
- 一组输入事件。
- 一组输出事件。
- 一组将状态和输入映射到输出的动作或输出事件（称为状态事件处理器）。
- 一组将状态和输入映射到状态的动作或输出事件（称为状态转换）。
通常，状态机允许用户通过具有多个层级的复合状态来建模复杂行为。状态机的状态层级基于父子关系。
- 相似的子状态被分组到一个复合状态中（嵌套层级是一个树）；
- 复合状态可以具有转换、进入/退出动作等（转换可以连接不同嵌套级别的状态）；
- 子状态“继承”复合状态；
- 活动状态表示从顶层状态到状态层级中叶节点的路径；
- 每个复合状态都必须有一个初始子状态。进入复合状态或子状态时，两者都会被激活。进入函数的顺序是从上到下。
- 退出复合状态时，同时退出活动的子状态。退出函数的顺序是从下到上。
类型定义
//// 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;
状态机数据结构
我们可以定义一组特定的宏作为状态机映射数据。这些宏映射到状态枚举、事件处理器函数声明、状态的事件处理器表、状态树定义和应用程序变量定义。
- 状态枚举
#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 }; - 状态事件处理器表定义
#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} }; - 状态树定义
#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 }; - 应用程序定义
#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;
事件分发
/*********************************************************************
* 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<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);
};
}; /* end of not internal transition.*/
/**************************************************************************
Call event handler function if given enent
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;
/* It is not a leaf. */
while (pApp->pStateTree[nState].nDefSubState != SME_INVALID_STATE)
{
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);
return TRUE;
}
应用程序管理器
嵌入式系统上的程序通常可以分为几个应用程序。这些应用程序有两种模式：活动或非活动。活动应用程序正在状态机上运行，而非活动应用程序则没有。换句话说，只有活动应用程序才能处理事件。状态机引擎负责管理这些应用程序并将事件分发给特定的应用程序。
嵌入式系统程序必须与底层（其他模块）或硬件（称为服务提供者）紧密协作。服务由一系列可供服务用户（应用程序）使用的原语（操作）正式定义。这些原语告诉服务执行某些操作或报告对对等组件/实体所采取的操作。服务原语分为四类：请求、指示、响应和确认 [计算机网络，Andrew S.Tanenbaum]。请求和确认原语可以实现为服务调用。指示和响应原语可以实现为外部事件发布。
在模拟环境中，开发人员可以以Windows程序作为服务提供者来设计模拟器。这些模拟器的接口与目标服务提供者的接口相同。在目标环境中，开发人员可能只需付出少量努力即可将状态机应用程序与这些服务提供者集成到真实环境中。活动应用程序可能会调用服务提供者导出的某些服务，同时可能会通过RTOS函数接收服务提供者触发的某些外部事件。尽管RTOS提供的功能类似，但存在许多不同的RTOS。RTOS虚拟层提供了一组平台无关的函数，以便在不更改状态机应用程序的情况下将其移植到其他平台。
应用程序和服务提供者之间的通信可以是异步模式或同步模式。应用程序运行在应用程序线程上，同时，服务提供者运行在服务提供者线程上。
UML状态机向导
当UML首次被采用时，许多嵌入式开发人员通过静态CASE技术将其纳入，以便他们能够可视化地捕获系统和软件架构。在早期采用UML时，最流行的CASE技术之一是Rational Rose。然而，随着技术的发展，Rose等CASE工具无法提供跟上技术不断进步的必要发展。模型驱动开发（MDD）环境提供了清晰的模型与代码同步，以及自动化的基础模拟和验证，已被证明是使产品开发团队跟上新兴技术的关键流程推动者。
Visual C++是一个强大的软件开发工具。然而，它主要用于开发Windows特定的应用程序。UML状态机向导作为一个Visual C++插件，提供了一种UML（统一建模语言）状态机编程机制，采用可移植的标准C语言，用于在Visual C++开发者工作室中开发和模拟嵌入式系统。模拟和调试后，开发人员可以以极少的或无需额外投资或工作量即可将程序移植到目标工作环境。