嵌入式软件中状态机的抽象与实现
收稿日期 :2003 - 04 - 15 ;修订日期 :2003 - 07 - 08
作者简介 :熊振云(1979 - ) ,男 ,云南大理人 ,硕士研究生 ,主要研究方向 :实时嵌入式系统 ; 阮俊波(1974 - ) ,男 ,湖北人 ,博士研究生 ,主要
研究方向 :实时嵌入式系统 ; 金惠华(1938 - ) ,男 ,博士生导师 ,主要研究方向 :实时嵌入式系统、容错技术.
文章编号 :1001 - 9081(2003) 10 - 0084 - 03
嵌入式软件中状态机的抽象与实现
熊振云 ,阮俊波 ,金惠华
(北京航空航天大学 计算机学院 ,北京 100083)
摘 要 :文中提出了在嵌入式软件中把状态机作为一个独立模块从控制模块中抽象出来的思想 ,
描述了抽象出来的状态机模块。并介绍了如何将这种状态机抽象模块应用到实际项目中。
关键词 :嵌入式软件 ;状态机 ;模块化
中图分类号 : TP311 文献标识码 :A
Abstract State Machine in Embed Software
XIONG Zhen2yun ,RUAN Jun2bo ,J IN Hui2hua
(Computer Science and Engineering School ,Beihang University ,Beijing 100083 ,China)
Abstract : This article brings forward an idea that abstracting state machine from control module in embed software and describes
the abstract state machine module. It also talks about how to use this kind of abstract state machine in a project.
Key words : embed software ;state machine ;modularization
1 引言
从传统的工业控制到人们日常生活中的电视、手机 ,到处
都可以见到实时嵌入式系统的应用。实时嵌入式系统与普通
计算机系统的差别首先是资源较少 ,其次是系统不仅要保证
计算产生正确结果 ,而且还要保证在规定时间内产生结果。
在开发嵌入式实时系统的软件时 ,经常需要用多个状态
来描述系统的行为。这些状态的状态变化和转移形成了状态
机。如果能抽象出一种通用的状态机模型 ,则可减轻嵌入式
软件开发人员的工作负担 ,同时提高软件的可读性 ,增强软件
的可维护性和可扩充性。
2 抽象状态机的意义
在实时程序中 ,执行速度和各事件之间的配合是非常重
要的 ,但软件中的结构化设计和数据隐藏等方法也同样十分
重要。如果在处理速度、硬件资源和开发工具允许的范围内
充分将软件划分为各个独立的模块 ,将可以提高程序的可维
护性 ,并为软件升级奠定良好的基础。
虽然在嵌入式实时软件中常用的开发语言 ———C 语言不
直接支持模块 ,但可以把一个文件当作一个模块来处理。在
C 语言中 ,被说明为是静态函数和静态变量的内容 ,可以被同
一文件内的其它例程调用 ,而不能由文件外的程序调用[1] 。
在不支持静态声明的应用中 ,也可以人为的规定不作外部引
用 (或除少数特殊应用外不作外部引用) 。待组织成不同的模
块文件后 ,可用头文件的形式说明函数和变量类型 ,以便模块
间相互调用。用这种方式构造的典型的模块文件的组织形式
如下[1] :包含头文件说明函数和变量 ;说明全局变量 ;说明模
块内的函数原型和变量 ;接口或输入函数的源代码 ;初始化函
数的源代码。
在实际的工程应用中 ,比较容易就可以将诸如主程序模
块、控制程序模块之类的功能抽象出来 ,却往往习惯将状态机
的处理混入控制程序模块中。如果这么做 ,将会在控制程序
模块中引入大量的变量赋值和条件判断 ,增大软件开发的难
度并给系统带来安全隐患 ,因为开发人员可能会弄不清楚变
量的意义而不得不反复查阅设计文档 ,或者因混淆众多变量
而错误的对某些变量进行赋值。这种情况在系统开发后期尤
为明显。
在工程实践中发现 :可以将状态机作为一个单独的模块
抽象出来。这样做的好处是进一步增强了软件的可读性 ,而
且状态机模块作为一个独立模块 ,可以在其它工程项目中实
现代码级的软件重用 ,甚至可以影响到设计级的重用。
3 抽象状态机介绍
3. 1 设计思路
图 1
不同项目中的状态机可谓是千变万化 ,我们总结发现 :一
般情况下 ,状态机如图 1 所示 (Mealy 机模型[2] ) ,表现为由现
态在条件触发下进行事务处理 ,然后进入次态 ,等待下一个
(次) 触发条件。为了
方便的把状态机映射
到一个数据结构上 ,可
以将各个状态抽象为
状态表示和状态对触
发条件的反应 ,将这二
者的组合称为状态节
点。这样 ,程序中的状态机就可以用一个状态节点的集合和
现态加转移触发表示。因为任何 Moore 机模型都可以转换为
Mealy 机模型 ,所以这种抽象是具有通用性的。
在状态机的抽取中 ,使用了 C 语言加以实现并遵循上面
第 23 卷第 10 期
2003 年 10 月 计算机应用
Computer Applications Vol. 23 ,No. 10
Oct. ,2003
提到的模块化文件的典型组织形式。
3. 2 数据结构定义
依照在设计思路里提到的表示方法 ,用下面的数据结构
定义表示状态节点 :
typedef struct
{ uchar uState ;
void( 3 lfInit) (void) ;
void( 3 lfMain) (void) ; / / 状态的处理函数
}STM-STATE , 3 PSTM-STATE;
其中 ,uState 是状态表示 ,它与真实状态间是一一对应的 ;
lfInit 是状态的初始化函数 ,它可为状态中用到的静态变量赋
初值 ,并为应用扩展留下了空间 ;lfMain 是状态的处理函数 ,
它完成状态的职能 ,并实现状态的转移 (完成现态的改变) 。
lfInit ,lfMain 两个函数是与具体应用相关的 ,所以它们的实现
在调用状态机模块的控制程序模块中完成。
为描述一个状态机 ,还需要定义一个含有所有状态节点
信息和状态机现态信息的数据结构 ———状态机描述 ,其定义
如下 :
typedef struct
{ uchar nOldState ; / / 上一个状态
uchar nCurState ; / / 当前状态
uchar nIndex ; / / 现态索引 ,状态在状态节点向量表中的位置
PSTM-STATE pStates ;
}STM-MAIN , 3 PSTM-MAIN ;
其中 ,nCurState 是状态机的当前状态 ;pStates 是指向状态
节点向量表 (状态节点数组) 的指针 ,该表包含了所有该状态
机的状态节点。
图 2
3. 3 接口函数说明
模块是一个具有固定接口的黑盒子[1] 。抽象出的这个状
态机模块也有其固定的接口 :
首先是整个状态机的初始化函数 STM- Init ,它主要完成状
态机描述对象中属性的初始化及它和状态节点向量表的关
联。
其次是状态机的派发函数 STM-Dispatch ,它在触使状态机
发生转移的事件到来时被调用 (通常是在中断处理函数或在
消息循环中) 。该函数先对现态及现态处理函数的合法性进
行检查 ,然后调用现态处理函数。
最后是状态转移函数 STM- To ,它完成状态描述对象中上
一个状态、现态、现态索引的更新 ;同时 ,它检测是否进入一个
新状态 ,如果是则调用该状态的初始化函数。该函数仅在各
个状态的处理函数中及设置状态机初始状态时被调用。
3. 4 抽象状态机使用模型
开发者在使用抽象状态机时 ,遵循
如图 2 所示的使用模型。其中 ,初始化
和状态派发处于开发程序的内核部分 ,
用户只要在适当时候调用即可 ;状态转
移加事务处理部分处于用户程序部分 ,
需要用户自己实现。
4 应用举例
在某公司的一套嵌入式实时软件中 ,上述的状态机模块
得到了运用及证明。下面通过该实例讨论抽象状态机在具体
项目中的应用。
4. 1 工程中的状态机描述
如表 1 所示 ,工程中的状态机有八个状态 ,七个触发条
件 ,表格中的数字表示状态在特定触发条件下转向的状态 ,空
缺表示状态在该触发条件下不发生转移 ;状态机的初始状态
为状态 0。
表 1
状态 触发条件
条件 1 条件 2 条件 3 条件 4 条件 5 条件 6 条件 7
0 1
1 1 2 3 5
2 1 4
3 1
4 2 3 4 10
5 3 5 10
10 10 11
11 2 3 5 11
4. 2 工程中的状态机实现
在设计中提到 ,抽象状态机的使用者需要将各个状态的
职能写成函数 ,然后将这些函数的信息填到状态节点向量表
里 ,最后 ,调用状态机初始化函数 STM- Init ,将状态节点向量表
与状态机关联起来。
程序实现中 ,在控制模块里声明并实现了以下函数 :
void TEXT-State0Init (void) ;
void TEXT-State0Do (void) ;
void TEXT-State1Init (void) ;
void TEXT-State1Do (void) ;
* *
void TEXT-State11Init (void) ;
void TEXT-State11Do (void) ;
void TEXT-Reserve(void) ;
其中 ,TEXT-Reserve 函数为空函数 ,作为保留扩展用。
同样的 ,在控制模块中 ,还给出了状态节点向量表 :
STM-STATE code StmStates[ ] =
{
{0 ,TEXT-Reserve ,TEXT-State0Do} ,
{1 ,TEXT-State1Init ,TEXT-State1Do} ,
* *
{11 ,TEXT-State11Init ,TEXT-State11Do} ,
{0xff ,TEXT-Reserve ,TEXT-Reserve}
} ;
其中 ,最后一个数组变量是为了标识数组结束而设置的
空状态。
在控制模块的初始化函数中 ,先后调用了状态机模块提
供的状态机初始化函数 STM- Init ( &StmStateCtl ,StmStates) 和状
态转移函数 STM- To( &StmStateCtl ,0) :
初始化函数中的 StmStateCtl 是状态机描述类型 STM-
MAIN 的变量 ,相当于面向对象思想中类的对象实例 ;StmStates
就是前面描述的状态节点向量表。转移函数的作用是设置初
始状态为状态 0。
在控制模块的消息循环中 ,调用了状态机模块的消息派
发函数 :
STM-Dispatch( &StmStateCtl) ;
这保证了每一个触发条件都能得到正确、及时的响应。
4. 3 性能比较
该工程的程序规模为 5000 行左右的 C 语言源代码 ,其中
58第 10 期 熊振云等 :嵌入式软件中状态机的抽象与实现
涉及到状态机的部分约为 1000 行 ;程序最终运行在 PHILIPS
的 89C58 单片机上 ,时钟频率为 24MHz。在这种情况下 ,对将
状态机的实现并入控制模块的方法 (方法 1) 和使用状态机抽
象模块的方法 (方法 2) 进行了比较 ,结果如表 2 所示。
表 2
比较科目 方法 1 方法 2
源代码行数(状态机实现部分) 约 1000 行 约 1100 行
占用 ROM 空间 4427 字节 4537 字节
占用 RAM 空间 76 字节 84 字节
状态 0 处理时间 约 7μs 约 77μs
状态 1 处理时间 约 166μs 约 237μs
状态 2 处理时间 约 145μs 约 216μs
模块化程度 较差 较高
可读性 较差 较高
可维护性 较差 较高
实践证明 ,使用状态机抽象模块这种方法实现的系统是
可以正确运行的。而且 ,从表中可以看出 ,在满足响应时间的
前提下 (状态转移多花费 70μs) ,只用了很少的代价就提高了
程序的可读性 ,可维护性及可扩展性。
由此得出结论 :在时间要求不是特别苛刻的项目中 ,都可
以使用该状态机抽象模块。
5 应用展望
状态机的抽象软件模块可直接作为程序包应用到其它的
项目开发中 ;在设计阶段 ,开发人员可以利用这种简明的状态
机模型来描述复杂的系统 ,这有助于从全局上把握工程。其
次 ,在对现有系统的改造中 ,也可以方便地将状态机剥离出
来 ,以便于维护和扩展。
参考文献
[1] 张云生. 实时控制系统软件设计原理及应用[M]. 北京 :国防工
业出版社 ,1998.
[2] 尹宝林 ,何自强 ,等. 离散数学 [M]. 北京 : 高等教育出版社 ,
1998.
(上接第 83 页)
3. 4. 2 代码实现
整个网站是 Visual Studio. Net 集成环境中 Visual C # 项目
的 ASP. NET Web 应用程序。为了实现目录服务相关操作 ,添
加了业务逻辑模块 :Visual C # 项目 CL-DirectoryServices 类库 ,
它包含下列类 :
CLDAPEntry类 , 对 应 于 目 录 服 务 中 自 定 义 的 对 象 类
myuser ,用于存储页面数据 ;
CLDAPConnection类 ,用于业务逻辑接口的实现 ,如目录
服务器的连接 ,用户身份认证 ,用户信息的添加、修改和删除
功能的实现。
下面以用户信息的添加的程序片断为例 ,简单说明 ADSI
函数调用。
/ / 在 m-objEntry 条目下 ,添加一个新条目(用户)
public string Add(CLDAPEntry entryUser)
{
try
{
DirectoryEntries users = m-objEntry. Children ;
DirectoryEntry user = users. Add ( " uid = " + entryUser. uid ,"
myuser") ;
/ / 添加所属的对象类属性
user. Properties["objectClass" ]. Add("top") ;
user. Properties["objectClass" ]. Add("person") ;
user. Properties["objectClass" ]. Add("organizationalPerson") ;
user. Properties["objectClass" ]. Add("inetOrgPerson") ;
user. Properties["objectClass" ]. Add("myuser") ;
/ / 添加必需和允许的属性
user. Properties["uid" ]. Add(entryUser. uid) ;
*
/ / 刷新高速缓冲存储器 ,提交已改变的数据到目录服务
器
user. CommitChanges() ;
}
catch(Exception error)
{ return entryUser. uid + error. Message ; }
return null ;
}
调用方法示例如下 :
/ / 添加用户信息到目录服务系统
CLDAPConnection ld = new CLDAPConnection() ;
/ / 建立到目录服务器指定条目下的连接
ld. Connect ("forest. buaa. edu. cn/ o = buaa. edu. cn") ;
/ / 验证绑定到目录服务器的用户名和密码 ,该用户必需有操作条
目的权限
ld . Authenticate ( " uid = admin , ou = Administrators , ou =
TopologyManagement ,o = NetscapeRoot" ,"energumen") ;
/ / 网页输入的用户信息存储到目录服务系统
CLDAPEntry user = new CLDAPEntry() ;
user. uid = strUsername ;
*
/ / 添加用户信息条目
ld. Add(user) ;
4 结语
文中所描述的目录服务相关业务逻辑模块 ,采用 ADSI 技
术访问目录服务 ,实现了目录服务系统中的条目操作和基于
用户 ID 和密码的简单认证 ,但远远不够。而目录服务系统本
身提供了丰富的安全访问控制 ,如基于证书的认证和安全套
接字层 SSL 上的数据传输等 ,因此该模块可以进一步地扩充 ,
以达到更好的安全要求。
参考文献
[1] Lightweight Directory Access Protocol (v3) . RFC2251[S]. 1997.
[2] Netscape Communications Corporation. The Netscape Directory SDK4. 0
for Java Programmerps Guide[ Z]. 1999.
[3] 王燕 ,谢金宝. Linux 下基于 Web 的目录服务系统的设计与实现
[J ]. 计算机工程 ,2000 ,26(12) .
[4] Robinson S ,Cornes O , et al. C # 高级编程[M]. 康博 ,译. 北京 :清
华大学出版社 ,2002.
[5] Kirkpatrick G. 活动目录编程指南[M]. 谭郁松 ,张明杰 ,张志伟 ,
译. 北京 :清华大学出版社 ,2001.
68 计算机应用 2003 年
嵌入式软件中状态机的抽象与实现.pdf
