求贤若渴礼贤下士 2014-05-08
============================================================================
原创作品,允许转载。转载时请务必以超链接形式标明原始出处、以及本声明。
============================================================================
软件设计中的状态机概念,一般是指有限状态机(英语:finite-state machine,缩写:FSM)又称有限状态自动机,简称状态机,是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。
FSM(有限状态机)可以使用UML中的状态机图来表示。也可以使用类似以下格式的状态转移表等等。下面展示最常见的表示:当前状态(B)和事件(Y)的组合指示出下一个状态(C)。
状态转移表 | |||
当前状态 → | 状态 A | 状态 B | 状态 C |
事件 X | … | … | … |
事件 Y | … | 状态 C | … |
事件 Z | … | … | … |
状态机有两个很重要的概念: 状态、事件。以下是一个CD机的简单例子:
CD机状态转移表 | |||
状态 → | 播放 | 暂停 | 停止 |
按播放键 | … | 播放 | 播放 |
按停止键 | 停止 | 停止 | … |
按暂停键 | 暂停 | … | … |
通过这个表,我们可以很直观的来理解状态机,如下:
1. 简单的CD机一般有三种状态: 播放、暂停、停止
2. 我们对CD机的操作,就是事件,简单来说有三种事件:按播放、停止、暂停按键。
3.在CD机不同的状态下,发生不同的事件(按不同的按钮),触发的事情以及CD机下一步的状态(即状态转移)是不一样的。
4. 按照以上表格,假如CD机当前状态是“播放”,这时候,我们按播放键,它会保持“播放”状态,不会发生状态转移,如果按暂停键,则会触发状态转移,CD机状态转移为“暂停”状态。同理,按停止键会转移为停止状态。
在软件的开发过程中,很多情况下,我们都会涉及到“状态”这个概念,比如监控服务器的软件,服务器会有:‘开机’,‘关机’,‘负载过高’等状态。
执行任务的软件,对于每个任务,会有“队列中”,“准备”,“运行”,“运行完毕”,“失败”等状态,任务在不同的状态下,发生不同的事件,状态迁移和对应的逻辑都是不一样的,比如在“队列中”状态,发生事件“取消任务”,这时候只需要把任务移出队列,并且状态变更为“失败”就行。同样,在“运行”状态时发生事件“取消任务”,则需要做很多工作,比如回收运行任务的资源等。
通常状况下,如果状态很少,可能不会涉及到状态机这个概念。但是如果状态、事件很多,如果设计不好状态机,软件开发到后期会非常吃力。对于后续的维护和升级也是问题。
状态机的实现主要有以下几种方式,这里我都以第一章中CD机的例子来做简单实现说明。
注:这里我主要以python或者C语言写的代码来说明,实际使用中,用任何语言都行,关键是逻辑思维。
1. if...else..... PS:最土最繁琐的方式(个人极不喜欢)
#!/usr/bin/python ##可以对应为C/C++/java中的enum类型,标示CD状态 class CDStatus: RUNNING = 0 STOP = 1 PAUSE = 2 ##同上,enum类型,标示CD的事件 class CDEvent: PRESS_RUNNING = 0 PRESS_STOP = 1 PRESS_PAUSE = 2 def do_change_stop(): #TODO someting and change CD status to STOP print "Chang CD to 'stop' status" def do_change_running(): #TODO someting and change CD status to RUNNING print "Chang CD to 'running' status" def do_change_pause(): #TODO someting and change CD status to PAUSE print "Chang CD to 'pause' status" ##对应CD机状态迁移图 def dispather(curr_status, event): if curr_status == CDStatus.RUNNING: if event == CDEvent.PRESS_STOP: do_change_stop() elif event == CDEvent.PRESS_PAUSE: do_change_pause() elif curr_status == CDStatus.STOP: if event == CDEvent.PRESS_RUNNING: do_change_running() elif event == CDEvent.PRESS_PAUSE: do_change_pause() elif curr_status == CDStatus.PAUSE: if event == CDEvent.PRESS_RUNNING: do_change_running() elif event == CDEvent.PRESS_STOP: do_change_stop() else: print "error!" def main(): current_status = CDStatus.STOP event = CDEvent.PRESS_RUNNING dispather(current_status, event) return if __name__ == "__main__": main()
可以看到,这个例子极为繁琐,if...else还需要嵌套2层,外层判断状态,里层判断事件,最终通过当前状态和发生的事件,对应“CD机状态迁移表”, 处理事件以及转移状态。
这种方式非常不灵活,因为每增加一个状态,都要加一堆if ..else的判定。
2. switch...case..... python中没有switch语法,可以用dict来代替,这里我用大体的C语言来描述。
下面的代码可以直接编译运行,在dispather中,嵌套了2层switch,类似上面if..else的结构,只不过换成了switch.
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef enum { STOP = 0, RUNNING, PAUSE, } CD_STATE; typedef enum { PRESS_RUNNING = '0', PRESS_PAUSE = '1', PRESS_STOP = '2', } CD_EVENT; char state_to_str[3][100] = {"STOP", "RUNNING", "PAUSE"}; //全局变量,用来存储CD当前状态 int current_state = STOP; void do_change_running() { printf("CD Status from %s to RUNING\n", state_to_str[current_state]); current_state = RUNNING; } void do_change_stop() { printf("CD Status from '%s' to STOP\n", state_to_str[current_state]); current_state = STOP; } void do_change_pause() { printf("CD Status from '%s' to pause\n", state_to_str[current_state]); current_state = PAUSE; } int dispather(current_state, event) { switch (current_state) { case STOP: switch(event) { case PRESS_RUNNING: do_change_running(); break; case PRESS_PAUSE: do_change_pause(); break; default: printf("CD's state not change\n"); break; } break; case PAUSE: switch(event) { case PRESS_RUNNING: do_change_running(); break; case PRESS_STOP: do_change_stop(); break; default: printf("CD's state not change\n"); break; } break; case RUNNING: switch(event) { case PRESS_PAUSE: do_change_pause(); break; case PRESS_STOP: do_change_stop(); break; default: printf("CD's state not change\n"); break; } break; default: printf("Error! no such status!\n"); break; } } int main () { char ch = '0'; printf ("请输入数字操作CD机(0:RUNNING, 1:PAUSE, 2:STOP):\n"); while (1) { ch = getchar(); if (ch == '\n') { } else if ((ch < '0') || (ch > '3')) { printf ("非法输入,请重新输入!\n"); continue; } else { char event = ch; dispather(current_state, event); printf ("请输入数字操作CD机(0:RUNNING, 1:PAUSE, 2:STOP):\n"); } } return 0; }
3. 函数指针法,这种方法是我最常用的,也是最喜欢的。所以这里我会分别贴出C和python的代码,详细讲解。
仔细观察第一章中的“CD机状态转换图”, 它其实就是一个二维矩阵结构,二维矩阵结构对应到数据结构中,无非就是二维数组。在状态转换时,都有对应的逻辑处理,所以,我们完全可以使用 “二维函数指针”来实现状态转换图。这里我没有使用二维数组,使用了结构体数组,这种实现更为直观。
如果有新的状态加入,只需要在state_mechine这个数组中加入新的状态,事件以及处理函数即可。
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef enum { STOP = 0, RUNNING, PAUSE, MAX_STATE, } CD_STATE; typedef enum { PRESS_RUNNING = 0, PRESS_PAUSE, PRESS_STOP, MAX_EVENT, } CD_EVENT; char state_to_str[3][100] = {"STOP", "RUNNING", "PAUSE"}; struct CD_STATE_MECHINE { int state; int event; void (*func)(unsigned char *); }; void do_change_running(unsigned char * user_data); void do_change_stop(unsigned char * user_data); void do_change_pause(unsigned char * user_data); struct CD_STATE_MECHINE state_mechine[] = { {RUNNING, PRESS_RUNNING, NULL}, {RUNNING, PRESS_STOP, do_change_stop}, {RUNNING, PRESS_PAUSE, do_change_pause}, {PAUSE, PRESS_RUNNING, do_change_running}, {PAUSE, PRESS_STOP, do_change_stop}, {PAUSE, PRESS_PAUSE, NULL}, {STOP, PRESS_RUNNING, do_change_running}, {STOP, PRESS_STOP, NULL}, {STOP, PRESS_PAUSE, do_change_pause}, {-1, -1, NULL}, }; //全局变量,用来存储CD当前状态 int current_state = STOP; void do_change_running(unsigned char * user_data) { printf("CD Status from %s to RUNING\n", state_to_str[current_state]); current_state = RUNNING; } void do_change_stop(unsigned char * user_data) { printf("CD Status from '%s' to STOP\n", state_to_str[current_state]); current_state = STOP; } void do_change_pause(unsigned char * user_data) { printf("CD Status from '%s' to pause\n", state_to_str[current_state]); current_state = PAUSE; } int dispather(current_state, event) { int i = 0; for(i = 0; state_mechine[i].state != -1; i++) { if (current_state == state_mechine[i].state && event == state_mechine[i].event) { void (*func)(unsigned char *); func = state_mechine[i].func; if (func != NULL) { func(NULL); } else { printf("state not change!\n"); } break; } } } int main () { char ch = '0'; printf ("请输入数字操作CD机(0:RUNNING, 1:PAUSE, 2:STOP):\n"); while (1) { ch = getchar(); if (ch == '\n') { } else if ((ch < '0') || (ch > '3')) { printf ("非法输入,请重新输入!\n"); continue; } else { int event = ch - '0'; dispather(current_state, event); printf ("请输入数字操作CD机(0:RUNNING, 1:PAUSE, 2:STOP):\n"); } } return 0; }
暂时写到这里,回头儿有空了,再不上python版本的状态机实现。
整体流程字符流 -> 状态机 -> 词token -> 栈 -> dom构建 DOM 的过程是:从父到子,从先到后,一个一个节点构造,并且挂载到DOM树上。<p class="a">text text