[交流][微知识]一种简单易用的状态机
本帖最后由 Gorgon_Meducer 于 2018-11-29 00:39 编辑说在前面的话
我已经做好了准备,此帖一出,争议不休……我先表态,就是拿出来挨骂的,不求胜负对错。
此贴介绍的模板是基于函数指针的。如果你对基于switch的状态机模板感兴趣,推荐看另外一个帖子
[微知识]一种简单易用的状态机
状态机有很多写法,一些比较基础的写法在我的另外一个帖子里面已经有所介绍。是的,这些传统的状态机写法
及其简约、明了、常用,而且显然适应使用SI的场合。但这类状态机存在两个问题:
1、跳转关系是固定的。
1) 一个状态机的所有状态都是在同一个函数中以固定的格式出现的,比如if-else,比如switch case。这些固定的格式
通过编译器编译以后会生成固定形态(逻辑形态)的代码,虽然状态的切换是通过状态变量的修改实现的,似乎无
法通过普通的汇编跳转指令(jmp, rjmp, call, rcall)来直接还原出状态机逻辑,但固定形势的汇编代码(有一个英
文单词能准确地描述这种状况,pattern)对反汇编分析来说是非常有利的,这种固定形势会很快引起他们的注意以
及怀疑,对于自信有一定技能的破解者来说(有句俗话说得好,没有金刚钻不揽瓷器活),引起注意基本上就是破
解线索的开始——当然,状态机的优势已经得到了体现:就是前面说的,无法通过普通的汇编跳转指令来直接还原
出代码逻辑。
2)不幸得是,子状态机的调用在传统模式下会被直接编译成call和rcall,这无疑将整个调用关系暴露了出来。对于一些
专业的Opcode扫描工具来说——这类工具通常不会公开发售——jmp/rjmp/call/rcall会直接将整个代码的调用关系完
全暴露出来,原本完整的BIN文件会借由这些分析结果被自动拆分成有意义的小段落,不管这样的结构和脉络有多复
杂,从reset-vector和关键的中端vector开始的顺藤摸瓜从来都是中规中矩且有效的做法。
2、无法快速评估系统对栈的消耗
传统的状态机编写方式(这里的传统专指if-else和switch case)在自状态机调用上存在一个问题——当然,这个问题
也是普通代码存在的问题——即,随着子状态机调用的深入,栈的消耗会增加。简单说,当你获得了一个状态机库,
你在使用前如果不清楚该状态机或者代码对栈的消耗情况,你的系统在稳定性上就是无法评估的。——栈评估,以及
固件质量的评估和控制方法将在在书中详细介绍。
相对所谓的传统状态机编写方式来说,使用函数指针作为中间介质来进行间接调用的方式就是所谓的“指针法状态机”。
指针法状态机其本质与合作式调度器几乎就是同义词,或者说是调度器的一个“状态机”编程模式。指针法状态机的原理
其实很简单,通过函数指针调用的状态函数每次都会将下一个状态返回给这个指针用来指定后续——如果你返回同一个状态
函数的地址,就实现了状态的自反(Reflexive);如果你返回了后续状态函数的地址,就实现了状态的迁移(Transfer)
——很容易看出这几乎就是对合作式调度器(co-operation scheduler)的活用。
一个典型的指针法状态机如下:
typedef void *(fsm_state_t)(void *pArg);
//! \name FSM for led-flash
//! @{
static uint32_t s_wDelayCounter; //!< delay counter
static void *led_init(void *pArg); //!< state led init
static void *led_toggle(void *pArg); //!< state led toggle
static void *led_delay(void *pArg); //!< state led delay
//! @}
static void *led_init(void *pArg)
{
//! initialize gpios
led_initialization();
return (void *)&led_toggle;
}
static void *led_toggle(void *pArg)
{
toggle_led();
s_wDelayCounter = 10000;
return (void *)&led_delay; //!< tranfer to delay state
}
static void *led_delay(void *pArg)
{
if (s_wDelayCounter) {
s_wDelayCounter--;
} else {
return (void *)&led_toggle; //!< tranfer to led toggle state
}
return (void *)&led_delay; //!< reflexive
}
int main(void)
{
fsm_state_t* ptFlashLED = &led_init;
system_init();
while(1) {
ptFlashLED = (fsm_state_t *)ptFlashLED(NULL); //!< call state machine
}
}
通过例子代码,我们很容易看出指针法状态机的一些特点:
1、指针法依赖于一个统一的函数原形(Prototype),例如代码中所有的状态函数都拥有相同的原形typedef void *(fsm_state_t)(void *pArg);2、指针法的状态修改是通过返回目标函数的地址来实现的
3、指针法的状态机无论逻辑深度多大,实际在使用时只占用一级栈深度。
实际上,关于这一点可以有很多很深入地展开,比如,通过维护一个函数指针栈,我们可以加入
对子状态机调用的支持,这一支持仍然具有前面两条的特点。比如,将状态机所有要用到的局部
变量都通过一个结构体定义下来(你可以认为是一个类,参考帖子),然后通过堆分配(heap)
或者静态分配的方式获得一个结构体实体,通过pArg的方式传递给状态机——这就能使得这样的
状态机具有可充入性(当然,该技术对普通状态机表示方式同样适用)
指针法状态机的优点几乎是相对传统方式来说的:
1、由于函数指针的使用,编译器不会直接生成包含静态函数信息的call或者rcall。系统会使用根据
目标寄存器中数据来决定跳转地址的call指令,这种情况下,静态分析代码结构将变得异常困难。
同时,由于call指令是基于数据的,则这种方式存在进一步对数据进行加密的可能——这也是提
高系统安全性的方法之一——典型的做法之一是使用相对地址法(下一个状态函数的地址会根
据当前状态函数返回的数值进行计算后获得一个偏移量,该偏移量将于当前指针的值进行指定
的运算,从而获得目标状态的值。这种方式以额外操作的代价极大的增加了逆向工程的难度,
因为只要中间一个环节出现了计算错误,破解者就无法获得后续所有逻辑的正确地址)
2、栈深度永远是1。这意味着,栈的大小只要保证一个合理的最小值即可。状态机的可充入问题,
或者说状态机的资源消耗都是依靠程序员来指派的——要么通过堆,要么通过普通的静态分配,
无论是堆还是静态分派,其大小和位置都是编译时刻就可以确定的——而确定(determinacy)
几乎是和嵌入式软件的稳定性和质量划等号的。可以真正让程序员做到“了如指掌”,“捏在
手心里”。无论是评估还是优化都有确切的依据和方法。可观测,可控制,可量化。
指针法状态机如此简单,简单到简直就是一个简化到骨头的合作式调度器。无论是结构、效率还是
状态机的逻辑表现形式都简单到“一览无余”。在这种情况下,如果我们对上述的结构进行一些宏
封装,整个状态机也许可以看起来更像一个状态机——而不是C代码——当然,迈出这一步究竟是
天堂还是炼狱,这就仁者见仁,智者见智了。下面的代码就是一种可能的宏封装形式,该形式顺便
处理了状态机的可重入问题。对于子状态机调用功能的支持方式,请参考一个更为复杂的状态机系统。
#define DEF_TINY_FSM(__NAME)\
typedef struct tiny_fsm_##__NAME##_arg tiny_fsm_##__NAME##_arg_t;\
typedef void *(*tiny_fsm_##__NAME##_task)(tiny_fsm_##__NAME##_arg_t *pArg);\
struct tiny_fsm_##__NAME##_arg
#define DEF_PARAM {
#define END_DEF_PARAM };
#define END_DEF_TINY_FSM
#define NEW_TINY_FSM(__NAME, __VAR) \
tiny_fsm_##__NAME##_task s_TinyFSM##__VAR = NULL;
#define TINY_STATE(__NAME, __STATE_NAME) \
void *tiny_fsm_state_##__STATE_NAME(tiny_fsm_##__NAME##_arg_t *pArg)
#define BEGIN {
#define END }
#define PRIVATE static
#define PUBLIC
#define INTERNAL static
#define PARAM pArg
#define TINY_FSM_END return NULL;
#define TINY_FSM_TRANSFER_TO(__STATE_NAME) return (void *)&tiny_fsm_state_##__STATE_NAME;
#define IS_TINY_FSM_CPL(__VAR) (NULL == s_TinyFSM##__VAR)
#define CALL_TINY_FSM(__NAME,__VAR, __START_STATE) do {\
tiny_fsm_##__NAME##_task *s_ptTinyFSMTemp = &s_TinyFSM##__VAR;\
bool bReset = IS_TINY_FSM_CPL(__VAR);\
tiny_fsm_##__NAME##_task s_TinyFSMStart = &(tiny_fsm_state_##__START_STATE);\
static tiny_fsm_##__NAME##_arg_t tParam, tResetParam =
#define PARAM_INIT{
#define END_PARAM_INIT };\
if (bReset) {\
tParam = tResetParam;\
*s_ptTinyFSMTemp = s_TinyFSMStart;\
}
#define NO_PARAM_INIT {0};\
if (bReset) {\
tParam = tResetParam;\
*s_ptTinyFSMTemp = s_TinyFSMStart;\
}
#define SET_PARAM(__FIELD,__VALUE) do {tParam.__FIELD = (__VALUE);} while(false);
#define END_CALL_TINY_FSM(__NAME) \
*s_ptTinyFSMTemp = (tiny_fsm_##__NAME##_task)(*s_ptTinyFSMTemp)( &tParam );\
} while(false);
应用实例
/*! \brief function that output a char with none-block manner
*! \param chByte target char
*! \retval true the target char has been put into the output buffer
*! \retval false service is busy
*/
extern bool serial_out(uint8_t chByte);
extern void toggle_led_a(void);
extern void toggle_led_b(void);
#define SERIAL_OUT(__BYTE) serial_out(__BYTE)
DEF_TINY_FSM(Print_String)
DEF_PARAM
uint8_t *pchString;
END_DEF_PARAM
PRIVATE bool m_CriticalSection = false;
PRIVATE TINY_STATE(Print_String, Print_Init);
PRIVATE TINY_STATE(Print_String, Print_Output);
END_DEF_TINY_FSM
PRIVATE TINY_STATE(Print_String, Print_Init) BEGIN
if ((NULL == PARAM) || (NULL == PARAM->pchString)) {
TINY_FSM_END; //!< end fsm
} else if ('\0' == (*PARAM->pchString)) {
TINY_FSM_END; //!< end fsm
} else if (m_CriticalSection) {
TINY_FSM_TRANSFER_TO(Print_Init); //!< try to enter critical section
}
m_CriticalSection = true;
TINY_FSM_TRANSFER_TO(Print_Output)
END
PRIVATE TINY_STATE(Print_String, Print_Output) BEGIN
if (SERIAL_OUT(*(PARAM->pchString))) {
PARAM->pchString++;
if ('\0' == (*PARAM->pchString)) {
//! complete
m_CriticalSection = false; //!< leave critical section
TINY_FSM_END; //!< complete
}
}
TINY_FSM_TRANSFER_TO(Print_Output) //!< reflexive
END
int main(void)
{
NEW_TINY_FSM(Print_String, DemoStringA)
NEW_TINY_FSM(Print_String, DemoStringB)
static uint8_t chDemoA[] = "Hello world";
static uint8_t chDemoB[] = "Tiny FSM Demo";
...
while(true) {
//! call DemoStringA, the instance of the tiny FSM Print_String
CALL_TINY_FSM(Print_String, DemoStringA, Print_Init)
PARAM_INIT
.pchString = chDemoA //!< output string "Hello world"
END_PARAM_INIT
END_CALL_TINY_FSM(Print_String)
//! an example of checking whether a sepecified fsm is complete or not
if (IS_TINY_FSM_CPL(DemoStringA)) {
toggle_led_a(); //!< do something here. E.g. toggle a LED
}
//! call DemoStringB, the instance of the tiny FSM Print_String
CALL_TINY_FSM(Print_String, DemoStringB, Print_Init)
PARAM_INIT
.pchString = chDemoB //!< output string "Tiny FSM Demo"
END_PARAM_INIT
END_CALL_TINY_FSM(Print_String)
//! an example of checking whether a sepecified fsm is complete or not
if (IS_TINY_FSM_CPL(DemoStringB)) {
toggle_led_b(); //!< do something here. E.g. toggle a LED
}
}
return 0;
}
杀了个花。 板了个凳 本帖最后由 Gorgon_Meducer 于 2012-12-9 17:33 编辑
应用实例:在串口中断处理程序中做数据帧解析(前后台系统)
已知一个串口中断处理程序如下:
extern void usart_rxc_isr_handler(uint8_t chByte);
ISR(usart_rxc_vect)
{
uint8_t tData = UDR0; //!< get received byte
usart_rxc_isr_handler(tData); //!< call the real handler
}
显然,这个抽象了的usart_rxc_isr_handler就是一个与具体芯片无关的串口接收完成中断处理程序,这么
作的意图就是为了不给大家造成任何“硬件相关性”的误解。
目标,接收一个数据帧格式,格式如下
HEAD + LENGTH + DATA + XOR
byte byte byte * length byte
则很容易画出接收状态机如下:
有待补充图片
对应的状态机代码如下:
typedef void frame_parser(uint8_t *pchBuffer, uint8_t chLength);
DEF_TINY_FSM(Frame_Decoding)
DEF_PARAM
frame_parser *fnParser;
uint8_t chBuffer; //!< data buffer
uint8_t chByte;
uint8_t chXOR;
uint8_t chLength;
uint8_t chCounter;
END_DEF_PARAM
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Head);
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Length);
PRIVATE TINY_STATE(Frame_Decoding, FD_Receive_Data);
PRIVATE TINY_STATE(Frame_Decoding, FD_Check_XOR);
END_DEF_TINY_FSM
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Head) BEGIN
if (0xAA == PARAM->chByte) {
//! head received
PARAM->chXOR = 0xAA;
TINY_FSM_TRANSFER_TO(FD_Wait_Length);
}
TINY_FSM_TRANSFER_TO(FD_Wait_Head)
END
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Length) BEGIN
if (PARAM->chByte > 20 || PARAM->chByte < 1) {
//! illegal length
TINY_FSM_END; //!< reset fsm
}
PARAM->chLength = PARAM->chByte;
PARAM->chCounter = 0;
PARAM->chXOR ^= PARAM->chByte;
TINY_FSM_TRANSFER_TO(FD_Receive_Data);
END
PRIVATE TINY_STATE(Frame_Decoding, FD_Receive_Data) BEGIN
//! save byte to buffer
PARAM->chBuffer = PARAM->chByte;
//! calculate XOR check sum
PARAM->chXOR ^= PARAM->chByte;
if (PARAM->chCounter >= PARAM->chLength) {
//! all data received
TINY_FSM_TRANSFER_TO(FD_Check_XOR);
}
TINY_FSM_TRANSFER_TO( FD_Receive_Data );
END
PRIVATE TINY_STATE(Frame_Decoding, FD_Check_XOR) BEGIN
//! check XOR check SUM
if (PARAM->chXOR == PARAM->chByte) {
if (NULL != PARAM->fnParser) {
PARAM->fnParser(PARAM->chBuffer, PARAM->chLength); //!< call parser
}
}
TINY_FSM_END; //!< reset fsm
END
extern void add_frame_to_queue(uint8_t *, uint8_t);
void usart_rxc_isr_handler(uint8_t chByte)
{
PRIVTE NEW_TINY_FSM(Frame_Decoding, tFrameDeocoder)
CALL_TINY_FSM(Frame_Decoding, tFrameDeocoder, FD_Wait_Head)
PARAM_INIT
&add_frame_to_queue, //!< register frame parser handler
0
END_PARAM_INIT
SET_PARAM(chByte, chByte)
END_CALL_TINY_FSM(Frame_Decoding)
}
...
void add_frame_to_queue(uint8_t *pchData, uint8_t chLength)
{
//! add received data block to command chain list
...
}
void process_command_chain(void)
{
//! get command from chain list and try to parse it.
...
}
...
int main(void)
{
...
while(true) {
...
process_command_chain();
}
return 0;
}
目前对状态机没有什么概念{:dizzy:} 13、26、27、38行的末尾,应该不要分号——尤其是第38行,考虑它被放置在for循环语句的初始化部分时,用户可能会希望用逗号表达式完成复杂的初始化,这里如果有分号,结果会导致编译失败。 宏体的末尾不应该有预置的分号,这个分号应该留给用户来添加——他需要的可能不是分号而是逗号。 chengpiaopiao 发表于 2012-11-16 17:35 static/image/common/back.gif
板了个凳
禁止队形! Gorgon_Meducer 发表于 2012-11-16 17:35 static/image/common/back.gif
点评下?
自己:地了个板
评了,见LSS&LSSS。
PS禁止队形!你还是版主,竟然带头。 eduhf_123 发表于 2012-11-16 17:43 static/image/common/back.gif
宏体的末尾不应该有预置的分号,这个分号应该留给用户来添加——他需要的可能不是分号而是逗号。 ...
这个问题统一考虑过,原本的方案就是禁止分号,后来因为部分地方不能加分号,最后就统一决定都使用这种“使用的时候不加分号”的风格。
毕竟统一才是简单的。 我是做linux驱动开发的,个人感觉宏用的太复杂了,覆盖了很多东西,建议:
1. 可以考虑把状态机函数写成标准的API接口,按照一定的规范如posix(Portable Operating System Interface of Unix),方便扩展
2.最近看到一个嵌入式系统nuttx,想法挺好的,基本走的通用的一套,上手很容易,熟悉了这个也方便往linux这种系统转。 过份使用预处理的程序看不下去,MFC痕迹很重 eduhf_123 发表于 2012-11-16 17:41 static/image/common/back.gif
13、26、27、38行的末尾,应该不要分号——尤其是第38行,考虑它被放置在for循环语句的初始化部分时,用户 ...
尤其是你列举的这几行,都属于“定义性质的宏”而不是“函数性质的宏”,就是因为他们,所以才不能加分号。
这种“定义性质的宏”在MFC中也是常见的。 end2000 发表于 2012-11-16 17:48 static/image/common/back.gif
过份使用预处理的程序看不下去,MFC痕迹很重
恩,是的MFC毒害我很深——讽刺的是我最痛恨用MFC开发程序。 end2000 发表于 2012-11-16 17:48 static/image/common/back.gif
过份使用预处理的程序看不下去,MFC痕迹很重
有时候尝试换一换视角——比如抑制下自己想知道内部细节的欲望,直接从逻辑层面上看——看看逻辑层面是不是更清晰了。
当然,仁者见仁,智者见智。 huyugv_830913 发表于 2012-11-16 17:47 static/image/common/back.gif
我是做linux驱动开发的,个人感觉宏用的太复杂了,覆盖了很多东西,建议:
1. 可以考虑把状态机函数写成标 ...
推荐你也关注下RT-Thread,这个国人做的嵌入式操作系统就是严格按照你说的这个思路来的。
我比较固执,属于逻辑至上的,一直追求逻辑与代码分离的思想。 Gorgon_Meducer 发表于 2012-11-16 17:49 static/image/common/back.gif
尤其是你列举的这几行,都属于“定义性质的宏”而不是“函数性质的宏”,就是因为他们,所以才不能加分号。
这种“定义性质的宏”在MFC中也是常见的。
第38行应该属于“函数性质的宏”范畴吧。 Gorgon_Meducer 发表于 2012-11-16 17:47 static/image/common/back.gif
这个问题统一考虑过,原本的方案就是禁止分号,后来因为部分地方不能加分号,最后就统一决定都使用这种“使用的时候不加分号”的风格。
毕竟统一才是简单的。
也对,反正你这个东西本来就不是给“人”用的,而是给“程序”用的。 eduhf_123 发表于 2012-11-16 17:53 static/image/common/back.gif
第38行应该属于“函数性质的宏”范畴吧。
服从“统一原则” eduhf_123 发表于 2012-11-16 17:55 static/image/common/back.gif
也对,反正你这个东西本来就不是给“人”用的,而是给“程序”用的。
恩,被你看出来了……其实人也能用的嘛……
只不过现在是积极为未来的GUI工具做准备,这个tiny_fsm是为无调度器的系统准备的。
也就是说,用户通过GUI设计了一个逻辑上的状态机,代码也填写好了,但是最后生成
代码的阶段上,可以选择有调度器的状态(有一些高级特性);没有调度器的状态(比
较基础,比如不支持状态真阻塞);使用原始if-else结构或者switch case结构。 Gorgon_Meducer 发表于 2012-11-16 17:55 static/image/common/back.gif
服从“统一原则”
那也就是说,不能使用如下的代码组织形式了:for(SET_PARAM(__FIELD,__VALUE),i=0; i<LOOPCNT; ++i)
{
...
} 回头聊,帮朋友取个快递去。 eduhf_123 发表于 2012-11-16 17:59 static/image/common/back.gif
那也就是说,不能使用如下的代码组织形式了:
厄……不需要支持吧……写成两行会死么? eduhf_123 发表于 2012-11-16 17:59 static/image/common/back.gif
回头聊,帮朋友取个快递去。
被查水表了???! Gorgon_Meducer 发表于 2012-11-16 18:00 static/image/common/back.gif
被查水表了???!
卧槽!你太恶毒了!! end2000 发表于 2012-11-16 17:48 static/image/common/back.gif
过份使用预处理的程序看不下去,MFC痕迹很重
同感,我一般看到这么复杂的宏,直接就放弃了。 jameszxj 发表于 2012-11-16 18:27 static/image/common/back.gif
同感,我一般看到这么复杂的宏,直接就放弃了。
厄……看来我有点过分喜欢用宏了……为了帮助我克服这种心态,能否牺牲点时间
帮我看看哪些部分的宏是有益的,哪些部分是多余的,谢谢先。 我是来学习的 我是来自转的~~ Gorgon_Meducer 发表于 2012-11-16 18:34 static/image/common/back.gif
厄……看来我有点过分喜欢用宏了……为了帮助我克服这种心态,能否牺牲点时间
帮我看看哪些部分的宏是有 ...
写这种宏是需要一定功力才行的,我看不下去主要是水平不够。至于提意见更是谈不上了。{:sweat:} jameszxj 发表于 2012-11-16 18:46 static/image/common/back.gif
写这种宏是需要一定功力才行的,我看不下去主要是水平不够。至于提意见更是谈不上了。...
厄……我没有别的意思……你别误会,其实,随便什么想法都是有帮助的,比如看到什么最让你觉得不可接受。
之前有一个兄弟给我说SI没法在这类系统上用最烦…… 先收藏再看~~~ y574924080 发表于 2012-11-16 23:36 static/image/common/back.gif
先收藏再看~~~
怎么样,我至少在兑现承诺了吧 Gorgon_Meducer 发表于 2012-11-16 23:41 static/image/common/back.gif
怎么样,我至少在兑现承诺了吧
果然是好孩子
乖~~~
{:lol:} 好像没有QP里面的Statecharts 用的简洁一些。 看不懂啊 william_rain 发表于 2012-11-17 00:26 static/image/common/back.gif
看不懂啊
状态图看懂了么?下面的代码例子应该还是比较清晰的吧? Gorgon_Meducer 发表于 2012-11-17 00:35 static/image/common/back.gif
状态图看懂了么?下面的代码例子应该还是比较清晰的吧?
怎么两个条件都一样的 ? y574924080 发表于 2012-11-17 00:45 static/image/common/back.gif
怎么两个条件都一样的 ?
悲剧,写错了……下面那个应该是 遇到“\0” 目标明确,为了漂亮的程序外观,但是绝对不是做状态机的好东西,当然玩玩语法糖也可以,不过不实用。
傻孩子应该不是在大系统上应用gui,主要针对嵌入式类的低端处理器,所以不必要这么复杂。如果要搞大型系统,恐怕也不是这么个玩法。
这种玩法实际上是新创建一种语言和语法逻辑,并用宏来实现。且不说交互性差,代码维护时和提升性能极度困难。
混乱c语言代码大赛的很多代码可以用来学习,但极少用于工程,不符合28原则。
当然硬要这么玩,恐怕首先要解决的是数学证明该语法逻辑正确,此外对用户代码错误提示也最好用宏来处理,否则排错及其困难。 Gorgon_Meducer 发表于 2012-11-17 00:56 static/image/common/back.gif
悲剧,写错了……下面那个应该是 遇到“\0”
状态图是用什么软件画的?
有这方面好用易用的软件吗? STM32_Study 发表于 2012-11-17 14:28 static/image/common/back.gif
状态图是用什么软件画的?
有这方面好用易用的软件吗?
用word画的,不过据说viso不错 learner123 发表于 2012-11-17 12:51 static/image/common/back.gif
目标明确,为了漂亮的程序外观,但是绝对不是做状态机的好东西,当然玩玩语法糖也可以,不过不实用。
傻孩 ...
是的,你说的没错,设计初衷的确是为了做个C语法玩具。但后来也还是在效率上作了很多考量。
另外,易用性和维护上是一个仁者见仁智者见智的问题。这样的结构在我训练过的学生中一直应
用的很好,已经发展出对应的调试法则和开发手段。目前逻辑上的验证是通过有限状态机理论来
保证的。除掉宏,其本质就是普通的函数指针法状态机。以始终如一的栈深度为优势。 状态机的思路可能很清晰,能完成任务,但代码效率不是很好吧? 饭桶 发表于 2012-11-17 20:32 static/image/common/back.gif
状态机的思路可能很清晰,能完成任务,但代码效率不是很好吧?
关于这个问题,你需要考虑,这种方式和普通的基于函数指针的调度器有什么差别呢?
甚至没有差别,那么效率问题是从什么角度来评估的呢?不能凭感觉哦~ 本帖最后由 Gorgon_Meducer 于 2012-11-19 00:08 编辑
更新了指针法状态机的理论讲解,还希望大家重新审视这个问题。状态机作为计算机技术的基石,
与之相关的理论基本都是强调“确定论(Determinacy)”,对FSM来说,几乎没有什么理论和知识
是模棱两可的,都是可以仔细评估和考量的。我希望大家能一起研究这个问题,并逐渐体会这一点。
不客气地说,这个帖子前半部分的评论充斥着第一印象的批判而鲜有从“把问题弄清楚”的角度所作
的思考,这是我看了以后很难过的——事情还没有搞清楚就被下了结论,实在是作技术时候一个很
让人沮丧的事情——就好像不教而诛一样——是的,事实可能是我真的错了,也可能是我只有某一部分
是对的,但无论如何,没有经过充分讨论,真的就像你感兴趣的技术,被老板看都没看清楚,就骂成
“shit”一样的感觉。 图文并茂,支持楼主! netawater 发表于 2012-11-19 21:01 static/image/common/back.gif
图文并茂,支持楼主!
{:lol:} 只是不知道说清楚了没有。有没有什么疑问呢? 后排听课。上一次楼主的学生发了个串口打字母的游戏也是状态机还没看。顶一下 Gorgon_Meducer 发表于 2012-11-19 21:11 static/image/common/back.gif
只是不知道说清楚了没有。有没有什么疑问呢?
static void *led_init(void *pArg)
{
led_init();
return (void *)led_toggle;
}
>>>>自己调用自己么?
fsm_state_t* ptFlashLED = &led_init(0);
>>>>似乎不需要&运算符了。
m了个k netawater 发表于 2012-11-19 21:50 static/image/common/back.gif
static void *led_init(void *pArg)
{
led_init();
这里是笔误,应该是相关的led初始化代码。
另外&是必须的——从指针统一性角度来说的。 其实宏我感觉也挺好的,自己知道就可以了,最近在用VHDL,发现里面也是begin,end,如果这种方式可以简化程序的编写,我说的编写不是指打字,字多点少点没什么,编程序的时候可以复制的嘛,我觉得就挺好的,我上次编了个小程序,由于几个按键的功能互相牵扯,总是有点问题,后来用了状态机,很快就实现了,但是当时那个状态机也是我随心所欲而且有些简单,感觉少了一些统一的标准,楼主这样的方式我觉得不错 abcdzhy 发表于 2012-11-19 23:00 static/image/common/back.gif
其实宏我感觉也挺好的,自己知道就可以了,最近在用VHDL,发现里面也是begin,end,如果这种方式可以简化程 ...
是啊,这样写的好处就是关注应用逻辑本身,忽略状态机的具体实现细节。 老实说,看了修改之后的文章才看懂一点
关于函数指针和宏的使用我还是要去看C语言书复习复习~~ y574924080 发表于 2012-11-20 00:26 static/image/common/back.gif
老实说,看了修改之后的文章才看懂一点
关于函数指针和宏的使用我还是要去看C语言书复习复习~~ ...
看来必要的讲解和分析还是需要的。之前缺失了,不好意思。{:lol:} Gorgon_Meducer 发表于 2012-11-19 22:16 static/image/common/back.gif
这里是笔误,应该是相关的led初始化代码。
另外&是必须的——从指针统一性角度来说的。 ...
第一段代码,46行,末尾的一对括号应该不要。 Gorgon_Meducer 发表于 2012-11-20 00:31 static/image/common/back.gif
看来必要的讲解和分析还是需要的。之前缺失了,不好意思。
是我C语言没学好
明天补习去~~~
晚安~ eduhf_123 发表于 2012-11-20 00:47 static/image/common/back.gif
第一段代码,46行,末尾的一对括号应该不要。
谢谢。 同时在原先地板层增加了一个新的应用范例。 本帖最后由 yurinacn 于 2012-11-20 09:37 编辑
我比较赞同楼主说的逻辑至上的。
整个程序看起来就像任务清单,不光看起来舒服,而且编写时思路清晰,调试时也很方便,断到哪部分希望得到什么结果心里很有数。编写时的思路清晰很重要,写起来流畅顺手,既可节省时间,又可大大减少错误。
我现在甚至喜欢用良好的代码逻辑代替注释。
另:
软件都是层层包装的,到哪个层面只讨论那个层面的事,既不关心上层逻辑怎么用,同时假设下层接口是绝对可靠的。每个人只管好自己就可以了。 表示没看懂 好东西,正在研究中,收藏了。 yurinacn 发表于 2012-11-20 09:31 static/image/common/back.gif
我比较赞同楼主说的逻辑至上的。
整个程序看起来就像任务清单,不光看起来舒服,而且编写时思路清晰,调试 ...
看来兄台心中有个明确的层次数据流图啊 Gorgon_Meducer 发表于 2012-11-20 01:15 static/image/common/back.gif
谢谢。 同时在原先地板层增加了一个新的应用范例。
不客气哈,别嫌我老挑毛病就好,哈哈~!
{:lol:}
貌似看到了CLI Shell 的影子…… eduhf_123 发表于 2012-11-20 13:31 static/image/common/back.gif
不客气哈,别嫌我老挑毛病就好,哈哈~!
你无非看到了parser…… Gorgon_Meducer 发表于 2012-11-20 18:53 static/image/common/back.gif
你无非看到了parser……
被你发现了……
看到“parser”,就自然地联想到命令解析、联想到Command Line、进而联想到Shell了。 eduhf_123 发表于 2012-11-21 14:30 static/image/common/back.gif
被你发现了……
看到“parser”,就自然地联想到命令解析、联想到Command Line、进而联想到Shell了。 ...
这两天在研究PUBWEAK和__root配合。真心好东西啊~ Gorgon_Meducer 发表于 2012-11-21 16:48 static/image/common/back.gif
这两天在研究PUBWEAK和__root配合。真心好东西啊~
“PUBWEAK”知道是神马东东,不过面对这个“__root”,我就只有表示俺是屌丝了——虽不懂、但觉厉。 {:smile:}指针法状态思路很新颖的,赞!
这和电脑软件设计模式中其中的一种很类似(不好意思,具体名字我倒忘了),就是设计多个controller类,每个controller负责一部分事物,在不同的场合,控制权交给某个controller。当某个controller处理完毕,将控制权交由其他controller处理,多个controller之间相互合作来实现总体功能。多年前我编写一个短信收发软件,就是用的这种设计模式。
这种设计模式的优点是设计代码很清晰,而且功能扩展性也很好,比如增加一种新的功能,一般来说,就增加一个controller类就可以解决问题了,几乎不影响其他controller的代码。
我看了楼主的代码,感觉还是宏定义稍微多了一点,如果能精简一些,也许反而要好理解些。
另外一点,就是我也希望探讨下,就是设计controller的粒度问题。 也许楼主只是举例,用一个LED灯闪烁来举例而已。
但是如果真的一个LED的闪烁要多个函数来配合完成,我就觉得还是繁琐了点,而且代价是 CODE占用字节数会增大。
一般来说RAM和CODE的经济性是互斥的,节省了栈空间,但是带来的代价是代码空间的增大,在小资源单片机上(如只有几K Flash)上,也许这个问题会是个障碍。
另外,我觉得设计一个 controller (或者就是楼主说的状态函数), 其粒度是值得考虑的。 我觉得一个LED闪烁,应该就是一个状态函数解决问题,
从软件模式设计的角度来说,也是一个controller对应一件可以理解的动作过程。 而不是分解动作。
比如,我描述 打开一扇门, 那么打开一扇门可能就是一个动作过程, 适用于创建一个controller,
而如果 细分为 走到窗前,抬手,推门,返回, 是更细粒度的动作。
再细: 走到窗前= 抬左脚,落下,再抬右脚,再落下,。。。。。。。。, 那么这个就是更细的粒度了。
我的意思是,不可能把设计controller的粒度细化到抬脚这一步。那样反而程序就失去可读性了。
所以,我觉得,可能还是要把握一个度,指针式状态机是个很好的思路, 可以很好的控制栈深, 但是也许不能走向极端。
如果走到极端,追求完全只有一级栈深,那么很可能就是细化到抬脚这个粒度,其代价就是降低代码效率,以及降低程序的可理解性。
smset 发表于3 小时前 static/image/common/back.gif
所以,我觉得,可能还是要把握一个度,指针式状态机是个很好的思路, 可以很好的控制栈深, 但是也许不能走向极端。
如果走到极端,追求完全只有一级栈深,那么很可能就是细化到抬脚这个粒度,其代价就...
上面的例子只是一个演示,方便大家理解,实际开发一个状态函数就足够了。至于状态划分的粒度问题有专门的成熟理论,只是篇幅限制不便展开。 似乎,基于函数指针的有限状态机方法实质上和ProtoThread基于(GCC的)Labels as Values扩展(似乎有一些编译器支持)的实现实质上一样。
基于函数指针的方案,主要优点在于不依赖编译器扩展,是基于C标准的实现,可移植性强。但是,使用宏实现相关的各种定义和调用以及独立的状态描述,一方面是代码编写错误时,报错定位困难;另外是在没有状态转换图的情况下不利于源代码的维护,这个完全靠文档。
基于Labels as Values的实现,最大的问题是编译器依赖;好处是状态转换的主路径十分清晰,容易阅读理解,特别是状态转换主要是错误处理的情形;相对应用宏的约束也少很多。额外的一个好处,就是ProtoThread的实现可以引入Yield Point,使用更方便灵活。
个人不是太喜欢使用宏“扩展”语法的代码方式,没有良好的文档,很难弄明白是怎么回事儿;而且编码时可能隐藏有需要注意的约束。
供讨论。
dr2001 发表于 2012-11-24 20:33 static/image/common/back.gif
似乎,基于函数指针的有限状态机方法实质上和ProtoThread基于(GCC的)Labels as Values扩展(似乎有一些编 ...
你说到点子上了:关键就在于文档。大家还记得有一个被遗忘的要求了吧?开发代码先写文档还是先写代码?
如果这个问题很抽象,我说的具体一点,你先画流程图(状态图)还是先写代码?
这套系统的要求就是,必须先写文档(画流程图/状态图)再“翻译成代码”;修改和更新的时候,也是先更新
文档(流程图/状态图)再翻译成代码。这是一种强制要求。对于团队开发非常有意义的“强制要求”。
另外,这套系统的使用也是有文档的,只不过不方便直接以原始形态公开出来。
最后关于宏封装的问题,真正在应用领域使用的宏都是严格测试的,作为黑盒子,你必须信任他,所谓的调试
都是以绝对信任宏封装的内容为前提的。在另外一个我已经商用化几年的状态机系统中,关于状态机的系统级
支持都是只提供.a,并且通过严格测试的宏来封装的。实践证明,并不会妨害调试,第一次接触的开发人员的
确会有短暂的不适应,但在突破对系统的信任障碍以后,很快就适应了这种开发模式,开发效率和代码逻辑性、
可读性、可维护性大大提高。
目前这类系统最需要的就是一个进一步简化开发的GUI,而这个GUI目前已经经过了预研阶段,进入需求分析阶
段。一个可供参考的国外例子就是QL系统。(Quantum Leap) Gorgon_Meducer 发表于 2012-11-24 21:02 static/image/common/back.gif
你说到点子上了:关键就在于文档。大家还记得有一个被遗忘的要求了吧?开发代码先写文档还是先写代码?
...
找了半天还没有找到你的微博在哪里?
没有链接吗? y574924080 发表于 2012-11-24 21:13 static/image/common/back.gif
找了半天还没有找到你的微博在哪里?
没有链接吗?
新浪微博,搜人,然后搜索“傻孩子图书工作室”应该是能找到的。 Gorgon_Meducer 发表于 2012-11-24 21:15 static/image/common/back.gif
新浪微博,搜人,然后搜索“傻孩子图书工作室”应该是能找到的。
很少用微博,
之前我搜索的时候直接搜索了
没看到,汗~~ 没看懂的说
#define END_PARAM_INIT }; \
if (bReset) { \
tParam = tResetParam; \
s_TinyFSM##__VAR = s_TinyFSMStart; \
}
#define NO_PARAM_INIT {0}; \
if (bReset) { \
tParam = tResetParam; \
s_TinyFSM##__VAR = s_TinyFSMStart; \
}
在宏名称中并无参数“__VAR",但在宏定义中包含__VAR,编译时导致宏展开失败。 楼主还是发一个能编译的上来,让我等用编译器将宏展开后看看代码。 本帖最后由 ifree64 于 2012-12-9 16:04 编辑
在这几个宏上做了修改才能通过编译,请傻孩子看一下,是否修改正确
END_PARAM_INIT(__VAR)
NO_PARAM_INIT(__VAR)
END_CALL_TINY_FSM(__NAME)
PS:使用宏把C编程一种方言后,我的编辑器已经无法对源代码自动作出正确的缩进了,这恐怕可以作为另一个尽量少使用宏的理由。
typedef unsigned char uint8_t;
typedef unsigned char bool;
#define false 0
#define true (!false)
#define NULL 0
#define DEF_TINY_FSM(__NAME) \
typedef struct tiny_fsm_##__NAME##_arg tiny_fsm_##__NAME##_arg_t; \
typedef void *(*tiny_fsm_##__NAME##_task)(tiny_fsm_##__NAME##_arg_t *pArg); \
struct tiny_fsm_##__NAME##_arg
#define DEF_PARAM {
#define END_DEF_PARAM };
#define END_DEF_TINY_FSM
#define NEW_TINY_FSM(__NAME, __VAR) \
tiny_fsm_##__NAME##_task s_TinyFSM##__VAR = NULL;
#define TINY_STATE(__NAME, __STATE_NAME) \
void *tiny_fsm_state_##__STATE_NAME(tiny_fsm_##__NAME##_arg_t *pArg)
#define BEGIN {
#define END }
#define PRIVATE static
#define PUBLIC
#define INTERNAL static
#define PARAM pArg
#define TINY_FSM_END return NULL;
#define TINY_FSM_TRANSFER_TO(__STATE_NAME) return (void *)&tiny_fsm_state_##__STATE_NAME;
#define IS_TINY_FSM_CPL(__VAR) (NULL == s_TinyFSM##__VAR)
#define CALL_TINY_FSM(__NAME,__VAR, __START_STATE) do { \
tiny_fsm_##__NAME##_task *s_ptTinyFSM##__NAME##Temp = &s_TinyFSM##__VAR; \
bool bReset = IS_TINY_FSM_CPL(__VAR); \
tiny_fsm_##__NAME##_task s_TinyFSMStart = &(tiny_fsm_state_##__START_STATE); \
static tiny_fsm_##__NAME##_arg_t tParam, tResetParam =
#define PARAM_INIT{
#define END_PARAM_INIT(__VAR) }; \
if (bReset) { \
tParam = tResetParam; \
s_TinyFSM##__VAR = s_TinyFSMStart; \
}
#define NO_PARAM_INIT(__VAR) {0}; \
if (bReset) { \
tParam = tResetParam; \
s_TinyFSM##__VAR = s_TinyFSMStart; \
}
#define SET_PARAM(__FIELD,__VALUE) do {tParam.__FIELD = (__VALUE);} while(false);
#define END_CALL_TINY_FSM(__NAME) \
*s_ptTinyFSM##__NAME##Temp = (tiny_fsm_##__NAME##_task)(*s_ptTinyFSM##__NAME##Temp)( &tParam ); \
} while(false);
typedef void frame_parser(uint8_t *pchBuffer, uint8_t chLength);
DEF_TINY_FSM(Frame_Decoding)
DEF_PARAM
frame_parser *fnParser;
uint8_t chBuffer; //!< data buffer
uint8_t chByte;
uint8_t chXOR;
uint8_t chLength;
uint8_t chCounter;
END_DEF_PARAM
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Head);
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Length);
PRIVATE TINY_STATE(Frame_Decoding, FD_Receive_Data);
PRIVATE TINY_STATE(Frame_Decoding, FD_Check_XOR);
END_DEF_TINY_FSM
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Head) BEGIN
if (0xAA == PARAM->chByte) {
//! head received
PARAM->chXOR = 0xAA;
TINY_FSM_TRANSFER_TO(FD_Wait_Length);
}
TINY_FSM_TRANSFER_TO(FD_Wait_Head)
END
PRIVATE TINY_STATE(Frame_Decoding, FD_Wait_Length) BEGIN
if (PARAM->chByte > 20 || PARAM->chByte < 1) {
//! illegal length
TINY_FSM_END; //!< reset fsm
}
PARAM->chLength = PARAM->chByte;
PARAM->chCounter = 0;
PARAM->chXOR ^= PARAM->chByte;
TINY_FSM_TRANSFER_TO(FD_Receive_Data);
END
PRIVATE TINY_STATE(Frame_Decoding, FD_Receive_Data) BEGIN
//! save byte to buffer
PARAM->chBuffer = PARAM->chByte;
//! calculate XOR check sum
PARAM->chXOR ^= PARAM->chByte;
if (PARAM->chCounter >= PARAM->chLength) {
//! all data received
TINY_FSM_TRANSFER_TO(FD_Check_XOR);
}
TINY_FSM_TRANSFER_TO( FD_Receive_Data );
END
PRIVATE TINY_STATE(Frame_Decoding, FD_Check_XOR) BEGIN
//! check XOR check SUM
if (PARAM->chXOR == PARAM->chByte) {
if (NULL != PARAM->fnParser) {
PARAM->fnParser(PARAM->chBuffer, PARAM->chLength); //!< call parser
}
}
TINY_FSM_END; //!< reset fsm
END
extern void add_frame_to_queue(uint8_t *, uint8_t);
void usart_rxc_isr_handler(uint8_t chByte)
{
NEW_TINY_FSM(Frame_Decoding, tFrameDeocoder)
CALL_TINY_FSM(Frame_Decoding, tFrameDeocoder, FD_Wait_Head)
PARAM_INIT
&add_frame_to_queue, //!< register frame parser handler
0
END_PARAM_INIT(tFrameDeocoder)
SET_PARAM(chByte, chByte)
END_CALL_TINY_FSM(Frame_Decoding)
}
void add_frame_to_queue(uint8_t *pchData, uint8_t chLength)
{
//! add received data block to command chain list
// ...
}
void process_command_chain(void)
{
//! get command from chain list and try to parse it.
//...
}
int main(void)
{
//...
while(true) {
// ...
process_command_chain();
}
return 0;
}最后在调用状态机函数的部分
NEW_TINY_FSM(Frame_Decoding, tFrameDeocoder)
CALL_TINY_FSM(Frame_Decoding, tFrameDeocoder, FD_Wait_Head)
PARAM_INIT
&add_frame_to_queue, //!< register frame parser handler
0
END_PARAM_INIT(tFrameDeocoder) // 我对这个宏做了小小修改方能通过编译
SET_PARAM(chByte, chByte)
END_CALL_TINY_FSM(Frame_Decoding)
这段代码用NEW_TINY_FSM宏,定义了一个“状态机”,但从宏的实现上来看,并没有定义为static静态变量;
那么真正调用“状态机”的宏END_CALL_TINY_FSM,实际上不能“保存”状态,是不是应该在NEW_TINY_FSM宏
中加一个static呢?
ifree64 发表于 2012-12-9 15:22 static/image/common/back.gif
在这几个宏上做了修改才能通过编译,请傻孩子看一下,是否修改正确
END_PARAM_INIT(__VAR)
NO_PARAM_INIT( ...
太感谢了,后来更新了一些宏以后我也没来得及测试,不好意思,说句恶心的话,有人用才会发现哈,当然这么说自己都觉得该挨砖了,谢谢。
至于修改的方式,方案很好,不过我采取的是另外一个思路,已经更新到楼主位。
另外,的确要加static,但应该通过额外的PRIVTE修饰来实现,而不是整合到宏里。
最后,我一直不用自动缩进的,所以感觉不出来。
再次感谢 Gorgon_Meducer 发表于 2012-12-9 16:46 static/image/common/back.gif
太感谢了,后来更新了一些宏以后我也没来得及测试,不好意思,说句恶心的话,有人用才会发现哈,当然这么 ...
楼主位修改了END_CALL_TINY_FSM和PRIVATE两个地方,
END_PARAM_INIT
NO_PARAM_INIT
两个宏没有修改,这两个也应该需要修改吧。
当我试着从你的角度来理解宏的使用时,发现宏确实“自动化”了状态机的实现,如果宏测试工作良好应该可以起到提高效率的意义。不过
宏确实太难调试了。我把代码复制出来,用gcc一编译一堆堆的错误,基本不知道如何下手,换了一个编译器clang,利用她人性化的错误
提示才找到去哪里修改,遗憾的是clang现在的后端太少了,不如gcc那么丰富。 本帖最后由 Gorgon_Meducer 于 2012-12-9 17:07 编辑
ifree64 发表于 2012-12-9 16:58 static/image/common/back.gif
楼主位修改了END_CALL_TINY_FSM和PRIVATE两个地方,
END_PARAM_INIT
NO_PARAM_INIT
这两个地方也修改了,请仔细看。
其实宏的另外一个好处是固化逻辑,一劳永逸。初次调试的时候也许困难(也是有解决办法的),但一旦成功,就能保证以后一直高质量的获得正确固化的成果。高效复用代码逻辑不正是模块化的精神么?所以才有了宏为基础的代码模板。大家不要只看首次投入,要看以后的规模效应。 Gorgon_Meducer 发表于 2012-12-9 17:02 static/image/common/back.gif
这两个地方也修改了,请仔细看。
其实宏的另外一个好处是固化逻辑,一劳永逸。初次调试的时候也许困难( ...
从积极的意义上说,你的宏是代码模板,引入了一个书写状态机的基本套路,简化了每次写状态机都去搭这么一个框架的过程。
从弊端上讲,宏改善后的方言和C太不象了,有的时候用BEGIN END来包围代码快,有时候用() 来包围代码块;有的语句用“;"结尾
有的宏语句结尾又不能用“;",如果能改进宏的设计,使得所有的代码块用统一的方式,所有的语句用统一的符号结尾就好了。 ifree64 发表于 2012-12-9 18:29 static/image/common/back.gif
从积极的意义上说,你的宏是代码模板,引入了一个书写状态机的基本套路,简化了每次写状态机都去搭这么一 ...
统一性是我一直追求的,现在做的的确不好。这需要过程,慢慢会有结论的 看傻孩子写的指针法状态机思路很好,但也产生了好奇,到底指针法和switch大法相比较,资源占用如何呢?于是做了如下这样一个试验:
我使用的编译器:
$ avr-gcc -v
Using built-in specs.
COLLECT_GCC=avr-gcc
COLLECT_LTO_WRAPPER=/usr/local/Cellar/avr-gcc/4.7.2/libexec/gcc/avr/4.7.2/lto-wrapper
Target: avr
Configured with: ../configure --enable-languages=c,c++ --target=avr --disable-libssp --disable-nls --with-dwarf2 --prefix=/usr/local/Cellar/avr-gcc/4.7.2 --with-gmp=/usr/local/Cellar/gmp/5.0.5 --with-mpfr=/usr/local/Cellar/mpfr/3.1.1-p2 --with-mpc=/usr/local/Cellar/libmpc/1.0.1 --datarootdir=/usr/local/Cellar/avr-gcc/4.7.2/share --bindir=/usr/local/Cellar/avr-gcc/4.7.2/bin --with-as=/usr/local/bin/avr-as
Thread model: single
gcc version 4.7.2 (GCC)
代码1:
switch大法实现的数据帧解析状态机void parse_data(unsigned char *pdata, unsigned char size);
void receive_uart(unsigned char rbyte)
{
static unsigned char state = 0;
static unsigned char counter = 0;
static unsigned char buffer;
static unsigned char data_xor;
static unsigned char length = 0;
switch(state)
{
case 0:
if(rbyte == 0xAA)
data_xor = rbyte;
state = 1;
break;
case 1:
if(rbyte > 20 || rbyte < 1)
{
state = 0;
}else{
state = 2;
data_xor ^= rbyte;
length = rbyte;
}
break;
case 2:
buffer = rbyte;
data_xor ^= rbyte;
if(length == counter){
counter = 0;
state = 3;
}
break;
case 3:
if(data_xor == rbyte)
{
parse_data(buffer, length);
}
state = 0;
break;
default:
state = 0;
break;
}
}
代码2: 指针法实现的状态机,为了公平比较,写法两者尽量保持一致,为了在不同函数间通信,使用了全局变量
unsigned char buffer;
unsigned char length;
unsigned char data_xor;
typedef void *(*pf_state_action)(unsigned char c);
void parse_data(unsigned char *pdata, unsigned char size);
void *receive_wait_head(unsigned char c);
void *receive_wait_length(unsigned char c);
void *receive_msg_data(unsigned char c);
void *receive_check_xor(unsigned char c);
void *receive_wait_head(unsigned char c)
{
if(0xAA == c){
data_xor = 0xAA;
return receive_wait_length;
}
return receive_wait_head;
}
void *receive_wait_length(unsigned char c)
{
if(c > 20 || c < 1){
return receive_wait_head;
}
length = c;
data_xor ^= c;
return receive_msg_data;
}
void *receive_msg_data(unsigned char c)
{
static unsigned char counter = 0;
buffer = c;
if(length != counter){
return receive_msg_data;
}else{
counter = 0;
return receive_check_xor;
}
}
void *receive_check_xor(unsigned char c)
{
if(data_xor == c){
parse_data(buffer, length);
}
return receive_wait_head;
}
void receive_data(unsigned char rbyte)
{
static pf_state_action p_state = receive_wait_head;
p_state = p_state(rbyte);
}
代码3: 指针法状态机,但是用结构体和指针传递数据,看到宏就头痛的朋友可以看看我这个没有用宏写的代码,当然有一些细节上的不同。
typedef struct _fsm_frame_decoding_arg{
unsigned char rbyte;
unsigned char buffer;
unsigned char length;
unsigned char data_xor;
}fsm_frame_decoding_arg;
typedef void *(*pf_state_action)(fsm_frame_decoding_arg *parg);
void parse_data(unsigned char *pdata, unsigned char size);
void *receive_wait_head(fsm_frame_decoding_arg *parg);
void *receive_wait_length(fsm_frame_decoding_arg *parg);
void *receive_msg_data(fsm_frame_decoding_arg *parg);
void *receive_check_xor(fsm_frame_decoding_arg *parg);
void *receive_wait_head(fsm_frame_decoding_arg *parg)
{
if(0xAA == parg->rbyte){
parg->data_xor = 0xAA;
return receive_wait_length;
}
return receive_wait_head;
}
void *receive_wait_length(fsm_frame_decoding_arg *parg)
{
if(parg->rbyte > 20 || parg->rbyte < 1){
return receive_wait_head;
}
parg->length = parg->rbyte;
parg->data_xor ^= parg->rbyte;
return receive_msg_data;
}
void *receive_msg_data(fsm_frame_decoding_arg *parg)
{
static unsigned char counter = 0;
parg->buffer = parg->rbyte;
if(parg->length != counter){
return receive_msg_data;
}else{
counter = 0;
return receive_check_xor;
}
}
void *receive_check_xor(fsm_frame_decoding_arg *parg)
{
if(parg->data_xor == parg->rbyte){
parse_data(parg->buffer, parg->length);
}
return receive_wait_head;
}
void receive_data(unsigned char rbyte)
{
static pf_state_action p_state = receive_wait_head;
static fsm_frame_decoding_arg msg;
p_state = p_state(&msg);
}
代码4: 为了查看使用结构体指针是否带来了额外的开销,特对switch大法写的状态机数据也用结构体包装便于比较。
typedef struct _fsm_frame_decoding_arg{
unsigned char buffer;
unsigned char length;
unsigned char data_xor;
}fsm_frame_decoding_arg;
void parse_data(unsigned char *pdata, unsigned char size);
void receive_uart(unsigned char rbyte)
{
static unsigned char state = 0;
static unsigned char counter = 0;
static fsm_frame_decoding_arg msg;
switch(state)
{
case 0:
if(rbyte == 0xAA)
msg.data_xor = rbyte;
state = 1;
break;
case 1:
if(rbyte > 20 || rbyte < 1)
{
state = 0;
}else{
state = 2;
msg.data_xor ^= rbyte;
msg.length = rbyte;
}
break;
case 2:
msg.buffer = rbyte;
msg.data_xor ^= rbyte;
if(msg.length == counter){
counter = 0;
state = 3;
}
break;
case 3:
if(msg.data_xor == rbyte)
{
parse_data(msg.buffer, msg.length);
}
state = 0;
break;
default:
state = 0;
break;
}
}
ifree64tekiiMac:mcuprojects xlee$ avr-gcc -mmcu=atmega48 -Os -c receive*.c
ifree64tekiiMac:mcuprojects xlee$ avr-strip *.o
ifree64tekiiMac:mcuprojects xlee$ avr-size *.o
text data bss dec hex filename
138 0 24 162 a2 receive1.o
148 2 1 151 97 receive2.o
152 2 24 178 b2 receive3.o
138 0 24 162 a2 receive4.o
ifree64tekiiMac:mcuprojects xlee$ md5 *.o
MD5 (receive1.o) = 57a53b7b409084ea9243f1ba851e4c3f
MD5 (receive2.o) = 24a0abcf7bdfd472fd29d593842aca5a
MD5 (receive3.o) = 01477a74b6a92789e0d10344c7df33a0
MD5 (receive4.o) = 57a53b7b409084ea9243f1ba851e4c3f
代码1和代码4比较,发现对flash占用完全一样,md5的分析发现,编译器生成的代码居然一模一样,可见结构体按值语义访问是没有代价的。
代码2和代码3比较,对flash占用基本一样,所以,使用结构体的方式保存数据,并以指针访问,程序大小基本一样,性能上面也许有一点差别,但应该也是差不多的(没有对反汇编代码进行比较,只是从程序体积猜测的)
代码1(switch状态机)和代码3(结构体指针+指针状态机)比较,指针状态机对资源占用略大,在实践中如果更复杂的代码有多少差距希望有高手指点。 ifree64 发表于 2012-12-10 21:35 static/image/common/back.gif
看傻孩子写的指针法状态机思路很好,但也产生了好奇,到底指针法和switch大法相比较,资源占用如何呢?于是 ...
代码2和代码3,全局变量由于地址在链接时可以确认,实际上是用立即数地址直接抓数据;结构体传指针是函数调用的时候多一次参数赋值,抓数据用LDR Rdst, 这样的指令形式完成(如果有类似指令)。
如果结构体的规模不大,二者指令级的消耗是应该相仿的。和编译的结果基本能对上号。
代码1恰好隐性的用到了一个编译器优化:Switch的Jump Table优化。编译器在优化允许,并且开销许可的情况下,会用查表法查case的入口地址。你的case是从0开始的自然数序列,恰好最自然的符合这个需求。Jump Table的开销最差大约是每个case一个void *的大小,线性增长。
所以,我认为,
如果处理流程的主过程是线性的,跳转是错误处理/Reverse过程,那么使用switch的方法比较好。代码自明性强,与处理流程一致。其中,case的状态值最好单独用宏给出,最后统一编码为0开始的递增序列,以期望利用优化。
如果处理流程是复杂的状态转换图,那么基于状态机设计文档使用指针状态机的方法比较好。代码和状态转换图具有完全对应关系,而且和优化后的switch相比,调用开销不会有什么差异。
需要特别注意:指针的方法性能是可预估并且稳定的,这点通常很重要;switch的方法一旦没有Jump Table优化,性能下降很厉害(会出现序列比较),而这个优化是否实行是用户不可见的,除非反汇编。
重量级的评估啊……感动~
指针法另外一个不可忽略的优势是,你可以很方便的建立真正具有阻塞特性的critical section,semaphore, event, mailbox...
但是switch case法无法方便的产生这种具有真正任务阻塞性的结构,通常能做的只是查询。任务的阻塞性对低功耗来说相当关键,
因为假设当所有任务都阻塞的时候(等待某个基于中断的生产者产程资源或者set某些信号量),switch case法中所有的任务都会
处于对标志的查询状态,这也就是假阻塞,这种状况下,系统是无法执行所谓的idle任务的;对于指针法,我们有能力通过链表的
方式构建真阻塞的任务,同样是上面的情况,所有任务都阻塞后,系统处于idle状态,idle任务被执行,idle任务就有能力进入sleep
模式。这就是天壤之别…… 本帖最后由 dr2001 于 2012-12-11 11:07 编辑
两种方法使用的状态变量数量相同,可互相映射,有何种区别呢?典型如,指针NULL表示阻塞,那就switch的0表示阻塞好了,一样一样的东西。
更有甚者,状态机方法的函数放在一起,比如:
pFunc taskFunc1(Para_List)
{
Bla Bla Bla
return taskFunc2;
}
pFunc taskFunc2(Para_List)
{
Bla Bla Bla
return taskFunc1;
bla bla bla
returnNull;
}
函数的定义行用break; case 函数名进行替换,其它丢弃;函数中的return用__Next = 替换。假定状态0是"NULL";加上函数头尾,switch,状态宏定义,等等。
#define taskFunc11
#define taskFunc22
state_t Func(state_t curr, bla bla)
state_t __Next = 0;
switch(curr) {
case 0:
break; case taskFunc1:
{
Bla Bla Bla
__Next = taskFunc2;
}
break; case taskFunc2:
{
Bla Bla Bla
__Next = taskFunc1;
bla bla bla
__Next = Null;
}
}
return __Next;
}
有什么非常强力的反例么?这是一个函数指针法似乎无损转换到switch的方法。
本来每个状态函数的函数体就是封在{}中的完整代码,所以可以无损封装进来;状态函数自身的调用参数是固定的(函数指针依赖),因此原有参数可以移动到新函数的参数表中;标准case需要加上"NULL"状态的处理;然后加上状态定义的宏,甚至可以使用PreProcessor自动编码生成JumpList优化。 本帖最后由 Gorgon_Meducer 于 2012-12-11 11:13 编辑
dr2001 发表于 2012-12-11 10:56 static/image/common/back.gif
两种方法使用的状态变量数量相同,可互相映射,有何种区别呢?典型如,指针NULL表示阻塞,那就switch的0表 ...
我说的是真阻塞……所谓真阻塞,就是连标志都不会去查询了……你设置state为0,但是对应的函数仍然是要被执行的……
真阻阻塞是指,连任务函数都不会真的被执行了。
下面是一个真阻塞的例子:
/***************************************************************************
* Copyright(C)2009-2012 by Gorgon Meducer<Embedded_zhuoran@hotmail.com> *
* *
* This program is free software; you can redistribute it and/or modify*
* it under the terms of the GNU Lesser General Public License as *
* published by the Free Software Foundation; either version 2 of the *
* License, or (at your option) any later version. *
* *
* This program is distributed in the hope that it will be useful, *
* but WITHOUT ANY WARRANTY; without even the implied warranty of *
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.See the *
* GNU General Public License for more details. *
* *
* You should have received a copy of the GNU Lesser General Public *
* License along with this program; if not, write to the *
* Free Software Foundation, Inc., *
* 59 Temple Place - Suite 330, Boston, MA02111-1307, USA. *
***************************************************************************/
/*============================ INCLUDES ======================================*/
#include ".\app_cfg.h"
#if DEMO_USART_TERMINAL == ENABLED
/*============================ MACROS ========================================*/
/*============================ MACROFIED FUNCTIONS ===========================*/
#define SERIAL_OUT(__BYTE) \
(VSFERR_NONE == ESSF_USART_SEND_BYTE(TERM_PORT, (__BYTE)))
/*============================ TYPES =========================================*/
/*============================ GLOBAL VARIABLES ==============================*/
/*============================ LOCAL VARIABLES ===============================*/
/*============================ PROTOTYPES ====================================*/
STATIC_FSM(Output_Stream)
DEF_ARG
uint8_t *pchStream;
vsf_uint16_t hwSize;
END_DEF_ARG(stream_t)
PRIVATE critical_section_t m_Critical;
PRIVATE bool m_bInitialized = false;
PRIVATE STATE(Output_Init);
PRIVATE STATE(Output_Stream);
PRIVATE STATE(Output_Wait_Transfer_Complete);
END_FSM
/*============================ IMPLEMENTATION ================================*/
/*! \brief initliaze usart demo task
*! \param none
*! \return initliaze result
*/
bool usart_demo_init(void)
{
//! usart
do {
usart_cfg_t tOption = {
TERMINAL_BAUD,
USART_8_BIT_CHAR_LENGTH,
USART_NO_PARITY,
USART_1_STOPBIT
};
//!< tx / rx pin configuration
ESSF_GPIO_INIT(ESSF_PORTC);
ESSF_GPIO_ENABLE(ESSF_PORTC);
ESSF_PINMAP
{ESSF_PORTC, PIN(3), 3, PIN_DEFAULT},
{ESSF_PORTC, PIN(4), 3, PIN_DEFAULT}
ESSF_END_PINMAP
ESSF_USART_INIT(TERM_PORT); //!< usart initialize
ESSF_USART_CONFIG(TERM_PORT, &tOption); //!< usart configuration
//uart_init(UART1_BASE_PTR, core_clk_khz,&tOption);
} while (false);
return true;
}
/*! \brief initialize a output stream task
*! \param pArg stream_t structure
*! \param pTarget target stream
*! \param hwSize stream size
*! \return SAFE_TASK_FUNC PTR
*/
SAFE_TASK_FUNC *output_stream(stream_t *pArg, void *pTarget, vsf_uint16_t hwSize)
{
ARG(stream_t) *ptArg = (ARG(stream_t) *)pArg;
if ((NULL == pArg) || (NULL == pTarget)) {
return NULL;
} else if (0 == hwSize) {
return NULL;
}
SAFE_ATOM_CODE(
if (!m_bInitialized) {
m_bInitialized = true;
if (!CS_INIT_CRITICAL_SECTION(&m_Critical)) {
EXIT_SAFE_ATOM_CODE();
return NULL;
}
}
)
ptArg->pchStream = (uint8_t *)pTarget;
ptArg->hwSize = hwSize;
return REF_STATE(Output_Init);
}
/*----------------------------------------------------------------------------*
* State machine: Output Stream *
*----------------------------------------------------------------------------*/
PRIVATE STATE(Output_Init) CRITICAL_SECTION_BEGIN(&m_Critical)
ESSF_USART_ENABLE(TERM_PORT); //!< enable usart
TRANSFER_TO_STATE(Output_Stream);
REFLEXIVE_STATE;
END
PRIVATE STATE(Output_Stream) BEGIN
ARG(stream_t) *ptArg = &REF_ARG(stream_t);
uint8_t chByte = *(ptArg->pchStream);
if (SERIAL_OUT(chByte)) {
ptArg->pchStream++;
ptArg->hwSize--;
if (0 == ptArg->hwSize) {
TRANSFER_TO_STATE(Output_Wait_Transfer_Complete);
EXIT_STATE;
}
}
REFLEXIVE_STATE;
END
PRIVATE STATE(Output_Wait_Transfer_Complete) BEGIN
//! wait usart idle
if (ESSF_USART_IDLE(TERM_PORT)) {
//! disable usart for saving power
ESSF_USART_DISABLE(TERM_PORT);
//! leave critical section
CS_LEAVE_CRITICAL_SECTION(&m_Critical);
EXIT_STATE;
}
REFLEXIVE_STATE;
END
#endif
Gorgon_Meducer 发表于 2012-12-11 10:31 static/image/common/back.gif
重量级的评估啊……感动~
指针法另外一个不可忽略的优势是,你可以很方便的建立真正具有阻塞特性的critical ...
呃……上一个回复给出了一个函数指针方法转换到swtich的方案,以此证明其等价性。
有没有什么可以说明其不等价的方法呢?
供讨论,谢谢。 本帖最后由 Gorgon_Meducer 于 2012-12-11 11:17 编辑
dr2001 发表于 2012-12-11 11:10 static/image/common/back.gif
呃……上一个回复给出了一个函数指针方法转换到swtich的方案,以此证明其等价性。
有没有什么可以说明其 ...
注意上面的状态机部分,这个状态机就是支持真阻塞的,下面是背后的核心的代码:
//! \name task event
//! @{
/*! \brief state modifier which indicates a specified state to be a event
*! driven state.E.g.
*! STATE(DEMO_A) WAIT_EVENT_BEGIN(&g_tEvent)
*! ...
*! TRANSFER_TO_STATE(DEMO_B);
*! EXIT_STATE;
*! END
*/
# define WAIT_EVENT_BEGIN(__EVENT) { \
if (!wait_for_single_object((__EVENT), pTask)) { \
WAIT_FOR_OBJ; \
}
# define CS_WAIT_EVENT(__EVENT) wait_for_single_object((__EVENT), pTask)
//! \brief initialize a task event item
# define CS_INIT_EVENT(__EVENT,__MANUAL_RESET,__INITIAL_STATE) \
create_event((__EVENT),(__MANUAL_RESET), (__INITIAL_STATE))
//! \brief set task event to active state
# define CS_SET_EVENT(__EVENT) set_event((__EVENT))
//! \brief reset task event to inactive state
# define CS_RESET_EVENT(__EVENT) reset_event((__EVENT))
//! @}
# if SAFE_TASK_CRITICAL_SECTION == ENABLED
//! \name critical section
//! @{
//! \brief initialize a specified critical section
# define CS_INIT_CRITICAL_SECTION(__CRITICAL) \
create_event((event_t *)(__CRITICAL), false, true)
/*! \brief state modifier which inidicates a specified state to be critical
*! section. E.g.
*! STATE(DEMO_A) CRITICAL_SECTION_BEGIN(&g_tCritical)
*! ...
*! TRANSFER_TO_STATE(DEMO_B)
*! EXIT_STATE;
*! END
*/
# define CRITICAL_SECTION_BEGIN(__CRITICAL) { \
if (!wait_for_single_object((event_t *)(__CRITICAL), pTask)) {\
WAIT_FOR_OBJ; \
}
# define CS_ENTER_CRITICAL_SECTION(__CRITICAL) \
wait_for_single_object((event_t *)(__CRITICAL), pTask)
# define CS_LEAVE_CRITICAL_SECTION(__CRITICAL) \
leave_critical_section((__CRITICAL))
# define enter_critical_section(__CRITICAL, __TASK) \
wait_for_single_object((__CRITICAL),(__TASK))
# define create_critical_section(__CRITICAL) \
create_event((event_t *)(__CRITICAL), false, true))
//! @}
//! \name mutex
//! @{
# define CS_INIT_MUTEX(__MUTEX) \
INIT_CRITICAL_SECTION(__MUTEX)
# define CS_RELEASE_MUTEX(__MUTEX) \
LEAVE_CRITICAL_SECTION(__MUTEX)
# define CS_WAIT_MUTEX(__MUTEX) \
ENTER_CRITICAL_SECTION(__MUTEX)
# define release_mutex(__MUTEX) \
LEAVE_CRITICAL_SECTION(__MUTEX)
# define create_mutex(__MUTEX) \
INIT_CRITICAL_SECTION(__MUTEX)
//! @}
# endif
...
#if SAFE_TASK_THREAD_SYNC == ENABLED
//! \name task event item
//! @{
DEF_CLASS
bool bSignal; //!< signal
SAFE_TASK *ptHead; //!< task item
SAFE_TASK *ptTail;
bool bManualReset; //!< manual reset flag
locker_t tLocker; //!< thread locker
END_DEF_CLASS(fsm_flag_t)
//! @}
//! \name event
typedef fsm_flag_tevent_t;
# if SAFE_TASK_CRITICAL_SECTION == ENABLED
//! \name critical section
typedef event_t critical_section_t;
# endif
#endif
...
#if SAFE_TASK_THREAD_SYNC == ENABLED
/*! \brief initialize task event
*! \param ptEvent event object
*! \param bManualReset flag that indicates whether the event should reset to
*! inactived state automatically.
*! \param bInitialState event initial state, either set or not.
*! \return pointer for event object
*/
event_t *create_event(event_t *pEvent, bool bManualReset, bool bInitialState)
{
CLASS(fsm_flag_t) *ptEvent = (CLASS(fsm_flag_t) *)pEvent;
do {
if (NULL == ptEvent) {
break;
}
LOCK_INIT(ptEvent->tLocker); //!< initialize thread locker
ptEvent->bSignal = bInitialState; //!< set initial state
ptEvent->bManualReset = bManualReset; //!< manual reset flag
ptEvent->ptHead = NULL;
ptEvent->ptTail = NULL;
} while(0);
return (event_t *)ptEvent;
}
/*! \brief set task event
*! \param ptEvent pointer for task event
*! \return none
*/
void set_event(event_t *pEvent)
{
CLASS(fsm_flag_t) *ptEvent = (CLASS(fsm_flag_t) *)pEvent;
if (NULL == ptEvent) {
return ;
}
LOCK( ptEvent->tLocker,
//! wake up blocked tasks
SAFE_TASK *pTask = ptEvent->ptHead;
while(NULL != pTask) {
if (pTask->bThreadBlocked) {
pTask->bThreadBlocked = false;
while (!_register_task(pTask)); //!< register task
}
pTask->ptFlag = NULL;
pTask->bSignalRaised = true; //!< set task flag
pTask = pTask->pNext;
}
ptEvent->ptTail = NULL;
ptEvent->ptHead = NULL; //!< clear tasks
if (ptEvent->bManualReset) {
ptEvent->bSignal = true; //!< set flag
} else {
ptEvent->bSignal = false; //!< set flag
}
)
}
# if SAFE_TASK_CRITICAL_SECTION == ENABLED
/*! \brief try to enter critical section
*! \param critical section item
*! \return none
*/
void leave_critical_section(critical_section_t *ptCritical)
{
CLASS(fsm_flag_t) *ptEvent = (CLASS(fsm_flag_t) *)ptCritical;
if (NULL == ptEvent) {
return ;
}
LOCK( ptEvent->tLocker,
if (!ptEvent->bSignal) {
//! wake up blocked tasks
SAFE_TASK *ptTask = ptEvent->ptHead;
if (NULL == ptTask) {
ptEvent->bSignal = true;
} else {
ptEvent->bSignal = false; //!< set flag
//! remove task from queue list
ptEvent->ptHead = ptTask->pNext;
if (NULL == ptEvent->ptHead) {
ptEvent->ptTail = NULL;
}
ptTask->pNext = NULL;
//! release critical section for the target task
if (ptTask->bThreadBlocked) {
ptTask->bThreadBlocked = false;
while (!_register_task(ptTask)); //!< register task
}
ptTask->ptFlag = NULL;
ptTask->bSignalRaised = true; //!< set task flag
}
}
)
}
#endif
/*! \brief reset specified task event
*! \param ptEvent task event pointer
*! \return none
*/
void reset_event(event_t *pEvent)
{
CLASS(fsm_flag_t) *ptEvent = (CLASS(fsm_flag_t) *)pEvent;
if (NULL == ptEvent) {
return ;
}
LOCK(ptEvent->tLocker,
ptEvent->bSignal = false;
)
}
/*! \brief wait for a specified task event
*! \param ptEvent target event item
*! \param pTask parasitifer task
*! \retval true event raised
*! \retval false event haven't raised yet.
*/
bool wait_for_single_object(fsm_flag_t *ptFlag, void *ptTask)
{
bool bResult = true;
SAFE_TASK *pTask = (SAFE_TASK *)ptTask;
CLASS(fsm_flag_t) *ptEvent = (CLASS(fsm_flag_t) *)ptFlag;
if (NULL == ptEvent) {
return bResult; //!< wait nothing
}
LOCK(ptEvent->tLocker,
bResult = ptEvent->bSignal;
if (!ptEvent->bManualReset) {
ptEvent->bSignal = false;
}
if (NULL != pTask) {
if (bResult) {
pTask->bSignalRaised = false;
} else if (pTask->bSignalRaised) {
pTask->bSignalRaised = false;
bResult = true;
} else {
//! add task to the wait list
pTask->pNext = NULL;
if (NULL == ptEvent->ptTail) {
ptEvent->ptHead = pTask;
} else {
ptEvent->ptTail->pNext = pTask;
}
ptEvent->ptTail = pTask;
pTask->ptFlag = ptEvent;
pTask->bThreadBlocked = false;
bResult = false;
}
}
)
return bResult;
}
/*
event_t tEvent;
STATE(Demo) BEGIN
if (!wait_for_single_object(&tEvent, THIS_TASK)) {
WAIT_FOR_OBJ;
}
...
END
*/
#endif
Gorgon_Meducer 发表于 2012-12-11 11:09 static/image/common/back.gif
我说的是真阻塞……所谓真阻塞,就是连标志都不会去查询了……你设置state为0,但是对应的函数仍然是要被 ...
不Care怎么阻塞,只要给出状态机代码,就等效转换成以上的switch格式。只要调度器也做对应修改,完全等价,至少我没想到有什么不支持这种情况的反例。
函数指针的唯一特例就是返回NULL,表示不可继续调用,然后调度器移出。那显然,switch的调度器可以在返回0的情况下不调用对应函数,进而判断阻塞,或者,当所有任务次态都是0的时候判定系统阻塞。
唯一的不足就是switch的如果不统一接口,调度器不能动态增删任务,这是调度器动态管理的要求,没办法。
本帖最后由 Gorgon_Meducer 于 2012-12-11 11:34 编辑
dr2001 发表于 2012-12-11 11:16 static/image/common/back.gif
不Care怎么阻塞,只要给出状态机代码,就等效转换成以上的switch格式。只要调度器也做对应修改,完全等价 ...
你不care阻塞,我就没有什么好说的了,我一直没有对二者的等效性做出怀疑,但是我更关心阻塞性,
因为阻塞性是调度的关键,可以释放处理器资源,可以真正支持运行时刻的低功耗——可能是因为信
息不对称的缘故,我有一套SleepVote算法,可以实现整个系统的运行时功耗接近理论允许的最低,
为了适应这个算法,调度器或者操作系统必须有能力执行idle任务,并通过idle任务进入休眠模式。
以前面粘贴出来的例子,我解释一下真阻塞:
PRIVATE STATE(Output_Init) CRITICAL_SECTION_BEGIN(&m_Critical)
ESSF_USART_ENABLE(TERM_PORT); //!< enable usart
TRANSFER_TO_STATE(Output_Stream);
REFLEXIVE_STATE;
END
这是一个状态,虽然背后的宏比这个帖子给出的要复杂一些,但本质也是指针法。这个代码的关键在于
CRITICAL_SECTION_BEGIN(&m_Critical)
这句话表明这是一个临界状态,如果临界区这个时候是锁定的,则进入这个状态的时候,当前的任务控
制块会被从就绪队列里面移除,加入到m_Critical结构的链表中(一个FIFO链表),这就意味着只要临界
区没有被释放,m_Critical链表中所有的任务都是阻塞的,都是永远不会被执行的,系统任务队列里面就
失去了对他们的控制,当后面的状态
PRIVATE STATE(Output_Wait_Transfer_Complete) BEGIN
//! wait usart idle
if (ESSF_USART_IDLE(TERM_PORT)) {
//! disable usart for saving power
ESSF_USART_DISABLE(TERM_PORT);
//! leave critical section
CS_LEAVE_CRITICAL_SECTION(&m_Critical);
EXIT_STATE;
}
REFLEXIVE_STATE;
END
执行了至关重要的CS_LEAVE_CRITICAL_SECTION(&m_Critical),则一个保存在m_Critical的任务FIFO中的
任务会被重新注册到调度器中,从而完成了这个任务的激活。这就是一个真阻塞的例子。 一直为状态机的状态返回是否可以配置而伤神。也就是说一个状态到另外一个状态的切换是否可以用一个数组或者宏来配置,这样在后期维护中,如果需要更改状态机的跳转状态或者插入新的状态,就不要修改已经实现的函数的状态了。
但是一直没有找到很好的实现方式,不知道Gorgon_Meducer对此有什么好的提议不? john_8 发表于 2012-12-11 11:38 static/image/common/back.gif
一直为状态机的状态返回是否可以配置而伤神。也就是说一个状态到另外一个状态的切换是否可以用一个数组或者 ...
我觉得本贴楼主位的例子就能解决你的问题。修改状态的链接,并不会影响已经写好的代码。 Gorgon_Meducer 发表于 2012-12-11 11:20 static/image/common/back.gif
你不care阻塞,我就没有什么好说的了,我一直没有对二者的等效性做出怀疑,但是我更关心阻塞性,
因为阻 ...
我的问题在于,转换的等效性如何?
如果转换是等效的,没有不可转换或者转换后会发生歧义的反例,那么,就说明基于函数指针的状态机方案和基于switch的状态机方案是等效的。究竟执行效率谁高,代码密度谁高,是另外一个问题(尤其是带了真阻塞之后,乍看代码密度还可能下降了)。
具体阻塞是怎么实现的并不是这里的核心关切,除非阻塞的实现影响到了转换的等价性。
最后的真阻塞的例子,是调度器的特性,而不是基于函数指针/switch的状态机的实现的问题。一个是调度器;一个是被调度器调度的任务,这个任务的是一个状态机实现,这个实现是基于函数指针/switch的。
如果调度器都是基于函数指针的,那么没有区别。如果严格要求调度器在switch中也不能用函数指针,休眠的调度效率会从O(1)变成O(N),大致的估计。
至少,我不认为上面的例子说明了switch不能“真阻塞”。
似乎有点跑题了,呵呵。 本帖最后由 Gorgon_Meducer 于 2012-12-11 12:08 编辑
dr2001 发表于 2012-12-11 11:53 static/image/common/back.gif
我的问题在于,转换的等效性如何?
如果转换是等效的,没有不可转换或者转换后会发生歧义的反例,那么, ...
恩,同意你的分析。
我之前强调的是一种能力:用指针法有能力进一步实现真阻塞(代码密度降低的问题,我不明白你的意思),
而如果用switch 方法(显然这里假设不能用函数指针来辅助)是没有进一步的能力实现真阻塞的。我这里
强调的是能力,而不是立即就可以比较的“等效性”。等效性上二者毫无差别,你完全可以在函数指针的
状态机里面的某个状态里面插入一段switch的状态机,反之亦然。
我的结论是:
1、用函数指针法,有能力实现真阻塞
2、单纯使用switch法,而不借助函数指针,无法实现真阻塞。
3、在一些需要真阻塞的环境下,支持真阻塞的函数指针法状态机无法转换成纯用switch的状态机(并仍保持
真阻塞性) 现在在外面,晚上我将补充一个例子详细说明两种方法在我着重考虑的方向上的差异。 Gorgon_Meducer 发表于 2012-12-11 12:27 static/image/common/back.gif
现在在外面,晚上我将补充一个例子详细说明两种方法在我着重考虑的方向上的差异。 ...
哈哈,我真的是抛砖引玉了。
页:
[1]
2