狀態(tài)機設(shè)計原則：清晰！清晰！還是清晰！
來源：裸機思維
作者：GorgonMeducer 傻孩子
【說在前面的話】
我們常說：狀態(tài)機是一種思維方式、一種工具，同時它也是一種擁有極高自由度的語言，作為一種翻譯思維的語言工具，不同人在使用狀態(tài)機時也有類似的表達能力的問題。
【功能單一原則】
人類是視覺主導的“動物”，具體表現(xiàn)為：對于同樣的信息，一張優(yōu)秀的圖片往往能讓人秒懂，而對應(yīng)的優(yōu)秀文字描述哪怕寫的簡單易懂，人們通常也需要花費數(shù)倍的時間來閱讀。這里的原因其實很簡單——對于圖片，人類是并行處理的；而對于建立在閱讀之上才能理解的文字，人類采用的是一種“連蹦帶跳”的順序處理方式。并行和順序處理的在時間效率上的差異，可見一斑。
在普通的應(yīng)用邏輯中，使用狀態(tài)圖描述邏輯也具有這種“讓人一目了然”的潛力；理論上，通過讀圖理解設(shè)計者意圖的速度應(yīng)該遠高于直接閱讀翻譯后代碼的速度——遺憾的是，實踐中由于缺乏正確的設(shè)計原則指導，很多人繪制的狀態(tài)圖恐怕還不如代碼看起來好懂。空口白牙，抽象的很，我們不妨舉個例子：
一般來說，在全狀態(tài)機開發(fā)下，永遠都應(yīng)該“先畫圖”，覺得邏輯沒有問題的情況下，再“根據(jù)狀態(tài)圖來無腦的翻譯代碼”——這對一張白紙的初學者來說往往很容易做到；遺憾的是，對大部分已經(jīng)有幾年工作經(jīng)驗，習慣了線性邏輯開發(fā)的人來說就有點困難了。比如，當我們說要設(shè)計一個輸出字符串的狀態(tài)機，對很多人來說，首先出現(xiàn)在大腦中的不是一張狀態(tài)圖，而是類似如下函數(shù)的一個參考代碼：//! \brief 通過外設(shè)非阻塞的輸出一個字節(jié)
extern bool serial_out(uint8_t cbByte);
void print_str(const char *pchStr)
{
if (NULL == pchStr) {
return ;
}
//! C語言中，字符串一般以 '\0' 作為結(jié)尾
while (*pchStr != '\0') {
//! 由于外設(shè)比較慢，輸出不一定每次都成功
while(!serial_out(*pchStr));
pchStr++;
}
}
作為參考代碼，顯然，所有人都知道阻塞是大問題，只要把這個代碼改為非阻塞的就行了，于是基于上述代碼在腦海中先入為主的影響，很容易“逆向”出如下的狀態(tài)圖：
這個圖從嚴格的語法意義上來說完全合格，只不過閱讀起來有點痛苦——雖然只有一個狀態(tài)，但猛然讓一個第三人閱讀，估計要花費不少的時間，可能的原因如下：
這個狀態(tài)有三個躍遷
這個狀態(tài)實際上擁有兩個功能：
通過serial_out()函數(shù)輸出字符
判斷字符串的尾部
我們說這個圖雖然語法上正確，但是違反了一個很重要的狀態(tài)圖設(shè)計原則——功能單一原則。所謂功能單一原則是指：每個狀態(tài)的功能要盡可能單一，要避免將多個功能復(fù)合在同一個狀態(tài)上，從而產(chǎn)生所謂的“超級狀態(tài)”的情況。設(shè)計出超級狀態(tài)并不是什么值得驕傲的本事，它單純：
增加了旁人（以及幾個月后的自己）閱讀和理解狀態(tài)邏輯的難度
增加了修改和擴展狀態(tài)圖的難度
增加了白盒分析的難度
幾何狀的增加了單一一個狀態(tài)所擁有的躍遷的數(shù)量
回頭再看前面的例子，很容易發(fā)現(xiàn)，它違反了狀態(tài)功能單一原則：將字符輸出和判斷字符串尾部的功能集成進了同一個狀態(tài)，從而產(chǎn)生了一個擁有3條躍遷的超級狀態(tài)?；跔顟B(tài)功能單一原則，一個更好的設(shè)計如下：
在這個圖中，雖然狀態(tài)數(shù)量變成了兩個，但它們分工明確功能單一，閱讀起來較為簡單，也非常容易發(fā)現(xiàn)上一張圖中不太容易發(fā)現(xiàn)的邏輯問題——比如前一個狀態(tài)圖如果字符串是空串“”，就會產(chǎn)生內(nèi)存訪問越界的致命bug，而通過拆分成兩個狀態(tài)，很容易注意到“IS End Of String”狀態(tài)所處位置對空串的敏感度——這也是功能單一原則增強了白盒測試（肉眼看圖找bug）能力的一個強有力的證明。
有的小伙伴可能會說，前一個狀態(tài)圖其實也不是很復(fù)雜啦，我就能看懂。對此，我想說：前面的例子終究只是一個為了介紹問題而引入的例子，本身不會太復(fù)雜，講清楚問題就行了。而在實際應(yīng)用中，在缺乏“功能單一”原則的限制下，鬼知道設(shè)計師會復(fù)合出怎樣的“蜘蛛精”；
超級狀態(tài)的成因之一是一部分人受到先前習慣的影響，雖然是設(shè)計狀態(tài)機，但總是無法自控的“先有代碼在腦海里”然后“再逆向”繪制出對應(yīng)的狀態(tài)圖。這個習慣說實話很難克服，也非常容易理直氣壯的產(chǎn)生“自以為是在優(yōu)化代碼”的超級狀態(tài)。針對這種心理，我們不妨強調(diào)下狀態(tài)機設(shè)計的正確流程：
狀態(tài)機設(shè)計的第一步永遠都是邏輯設(shè)計，追求的是清晰，此時絕不需要考慮所謂的代碼翻譯時如何才能做到最優(yōu)；
狀態(tài)圖才是真正的源代碼，而翻譯后的C代碼則是“匯編”；
任何針對狀態(tài)機的修改都必須從狀態(tài)圖開始，完成邏輯修改后，無腦的翻譯成代碼來查看運行效果；
當且僅當狀態(tài)機的邏輯已經(jīng)經(jīng)過驗證，確認是正確無誤的情況下，如果確實有用戶需求或者系統(tǒng)性能沒有達到要求，此時才進入狀態(tài)圖優(yōu)化階段——這里遵守的原則是：先優(yōu)化狀態(tài)圖，最后萬不得已的情況下才去優(yōu)化翻譯后的代碼。
說了這么多，我們不妨再用一個例子實際操作一下：假設(shè)我們要設(shè)計一個狀態(tài)機，從用戶那里識別單詞"OK"——其中一種最無腦的設(shè)計思路如下：
從邏輯的角度來說，很容易想到，對每一個字符來說，我們都有兩個階段：讀取字符輸入
判斷字符是否是我們想要的目標字符
因此很容易無腦的畫出如下的狀態(tài)機：
眼尖的小伙伴可能已經(jīng)注意到，這個圖中引入了一個新的名為reset的小圓點，它的功能也很直接：當躍遷到reset小圓點時，狀態(tài)機復(fù)位，并返回on-going。一個系統(tǒng)中可以有多個reset小圓點。有的小伙伴可能要問，為啥不是“躍遷到狀態(tài)機的第一個狀態(tài)”而一定要使用reset小圓點呢？原因主要有二：
避免第一狀態(tài)扇入過多，導致狀態(tài)圖太丑；
如果使用躍遷到第一個狀態(tài)的方法，則每一個躍遷都可能要重復(fù)去做類似初始化的工作——每多一條躍遷就多了一個重復(fù)的內(nèi)容——這里如果不是簡單復(fù)制粘貼的話，可能還會出現(xiàn)在漫長的代碼維護過程中出現(xiàn)“某些躍遷的動作與其它不一致”從而給自己挖坑的情況；使用reset可以確保狀態(tài)機復(fù)位，從而安全的從唯一的start點進入，完成統(tǒng)一的初始化動作。
盡管有的小伙伴會說：“這個狀態(tài)機看起來好蠢啊”，“這個狀態(tài)機看起來一點通用性都沒有”，但我要說，領(lǐng)會下精神啦，這只是我用來介紹方法論的例子，實際應(yīng)用當然不會這么設(shè)計，但不管怎么說，這個狀態(tài)機很清晰有木有？就是非常簡單直接的“一二一二……”步驟的無腦疊加——而這種功能單一、邏輯清晰的無腦疊加正是狀態(tài)機設(shè)計思維的一種體現(xiàn)——先邏輯清晰，一切都對了再考慮要不要優(yōu)化。
然而，沒有對比就沒有傷害，我們再來看看一個反例——當我們先有代碼在腦海里“揮之不去”，再“逆向”出狀態(tài)圖時會發(fā)生什么。
一個很容易想到的“最優(yōu)”代碼如下：
fsm_rt_t check_ok(void)
{
uint8_t chByte;
...
switch (s_tState) {
...
case RCV_O:
if (!serial_in(&chByte)) {
break;
}
if (chByte != 'O') {
CHECK_OK_RESET_FSM();
break;
}
s_tState = RCV_K;
case RCV_K:
if (!serial_in(&chByte)) {
break;
}
if (chByte != 'K') {
CHECK_OK_RESET_FSM();
break;
}
CHECK_OK_RESET_FSM();
return fsm_rt_cpl;
}
return fsm_rt_on_going;
}
受其影響，“逆向”出的狀態(tài)圖如下：圖片
看到這個狀態(tài)圖，很多小伙伴估計要不淡定了？“傻孩子你是不是打自己臉了？”“這個圖看起來明明看起來更直接??？狀態(tài)更少，而且對應(yīng)的代碼明顯更優(yōu)化??！”
別急別急，好漢先看完下面的內(nèi)容再打不遲。
【如何在“結(jié)構(gòu)清晰”和“性能優(yōu)化”之間取得平衡】
在前面的討論中，我們遇到了狀態(tài)機設(shè)計的一個非常實際的問題：在追求邏輯清晰的時候，似乎由于狀態(tài)的增多，代碼執(zhí)行的性能受到了某種影響——它表現(xiàn)在當翻譯成switch狀態(tài)機時，增加了太多不必要的狀態(tài)切換，從而影響了當前狀態(tài)機的執(zhí)行效率。比如：
這里，每次成功閱讀到一個字符后，在翻譯成switch狀態(tài)機后，居然要到下一次才能對字符進行判斷，而判斷后居然又要退出狀態(tài)機，再下一次才能開始新的一輪字符讀取——這個狀態(tài)機也實在太“卑微”了?？紤]到《實時性迷思（2）——“時間片輪轉(zhuǎn)”的沙子》中推導出的結(jié)論：非必要的頻繁任務(wù)切換會浪費大量的處理器時間，從而影響系統(tǒng)的實時性，這里由狀態(tài)切換導致的頻繁CPU出讓（yield）實際上并非好事。
難道我們必須要在“邏輯清晰”和“性能優(yōu)化”中做出取舍么？
先別著急下結(jié)論，分析上面的原因容易發(fā)現(xiàn)：
遵循狀態(tài)功能單一原則會產(chǎn)生多個簡單狀態(tài)，邏輯清晰，閱讀簡單；
現(xiàn)有的狀態(tài)切換過程中根據(jù)翻譯方式的不同“有可能”出讓CPU時間給其它任務(wù)；
那么，如果有一種方法能在狀態(tài)切換的過程中明確“標注”不要出讓CPU控制權(quán)（避免yield）是否就能解決問題了呢？比如，我們把此類切換從實線箭頭修改為虛線箭頭——表示此類切換不“主動”出讓CPU控制權(quán)，則修改后的圖如下所示：
那么在switch狀態(tài)機中，這類“不讓出CPU”的切換，實際上就是“切換任務(wù)的同時確保不會退出狀態(tài)機函數(shù)”。要想做到這一點有兩種方式：
使用goto
使用switch的fall-through特性
如果你對switch的fall-through特性感到一頭霧水，可以去找一本經(jīng)典的C語言教程看一看，或者參考這里的博文（https://c-for-dummies.com/blog/?p=3607）
實際上，這里并不需要比較二者的優(yōu)劣。一般來說，fall-through具有瀑布一般一瀉千里不能回頭的特性；而goto則適用于那些需要“逆流而上”的場合。作為例子，我們不妨使用新的方法翻譯前面的狀態(tài)圖：
fsm_rt_t check_ok(void)
{
uint8_t chByte;
...
switch (s_tState) {
case START:
s_tState = READ_CHAR_0;
// break; //!< fall-through實現(xiàn)虛線切換
case READ_CHAR_0:
if (!serial_in(&chByte)) {
break;
}
s_tState = IS_O;
// break; //!< fall-through實現(xiàn)虛線切換
case IS_O:
if (chByte != 'O') {
CHECK_OK_RESET_FSM();
break;
}
s_tState = READ_CHAR_1:
// break; //!< fall-through實現(xiàn)虛線切換
case READ_CHAR_1:
if (!serial_in(&chByte)) {
break;
}
s_tState = IS_K;
// break; //!< fall-through實現(xiàn)虛線切換
case IS_K:
if (chByte != 'K') {
CHECK_OK_RESET_FSM();
break;
}
CHECK_OK_RESET_FSM();
return fsm_rt_cpl;
}
return fsm_rt_on_going;
}
通過觀察可以發(fā)現(xiàn)，上述代碼借助fall-through的特性取得了跟前一章節(jié)參考代碼幾乎無異的執(zhí)行性能——實際上，聰明的你已經(jīng)發(fā)現(xiàn)，在確有必要的情況下，可以在狀態(tài)機的優(yōu)化階段對上述代碼進行進一步的優(yōu)化，從而得到與此前參考代碼一模一樣的結(jié)果：
fsm_rt_t check_ok(void)
{
uint8_t chByte;
...
switch (s_tState) {
...
case RCV_O:
if (!serial_in(&chByte)) {
break;
}
if (chByte != 'O') {
CHECK_OK_RESET_FSM();
break;
}
s_tState = RCV_K;
case RCV_K:
if (!serial_in(&chByte)) {
break;
}
if (chByte != 'K') {
CHECK_OK_RESET_FSM();
break;
}
CHECK_OK_RESET_FSM();
return fsm_rt_cpl;
}
return fsm_rt_on_going;
}
至此，我們實際上明確了狀態(tài)機的日常設(shè)計步驟：
按照狀態(tài)功能單一原則，以邏輯清晰為基本目標，再完全不考慮優(yōu)化的情況下，完成狀態(tài)機的設(shè)計和調(diào)試；
在完成了狀態(tài)機邏輯正確性驗證的前提下，在必要的情況下，可以對狀態(tài)圖進行性能優(yōu)化；
如果經(jīng)過上述步驟，性能仍然達不到要求，可以對翻譯后的代碼進行進一步的等效優(yōu)化。
注意，以上過程是單向不可逆的。一般會把步驟1和步驟2視作“一次迭代”，敏捷開發(fā)中可能會允許用戶進行多次迭代。
【條件太多怎么辦】
很多時候，雖然借助“虛線切換”可以在性能和清晰度上獲得一定的平衡，但如果一個狀態(tài)機狀態(tài)數(shù)量太多，難免會讓人眼花繚亂。就前面的狀態(tài)圖check_ok來說，這只是識別兩個字符，如果字符一多，圖豈不是直接爆炸了？
也許不是一個很好的例子，但如果真的能省略掉圖中“IS_O”和“IS_K”兩個狀態(tài)，并且仍能保證清晰的邏輯，豈不美哉？為了應(yīng)對這種情況，我們引入了新的圖例：公共條件（common condition）和子條件（sub condition）。那么，如何理解這兩個新的概念呢？此前，我們的狀態(tài)模型上，每個躍遷都由兩部分組成：躍遷的條件（condition）和躍遷時執(zhí)行的一次性動作（action）：
這一模型可以應(yīng)對大部分較為簡單的情況，但實際應(yīng)用中，一個狀態(tài)的所涉及的具體行為可能會產(chǎn)生不止一個返回值，比如：
serial_in(&chByte);
就產(chǎn)生了兩個有效的返回值：
serial_in() 函數(shù)的 boolean值，表示讀取成功還是失敗；
當讀取成功時，保存在 chByte 中的字符也就成了一個我們要判斷的返回值；
對于這種源自同一個狀態(tài)的動作而產(chǎn)生的多個返回值，我們可以借助前面所說的“公共條件”和“子條件”的方式加以簡化：
根據(jù)這一方式，修改前面的狀態(tài)圖如下：
怎么樣，是不是又清晰又簡單呢？它的switch狀態(tài)機代碼如下：
fsm_rt_t check_ok(void)
{
uint8_t chByte;
...
switch (s_tState) {
case START:
s_tState = READ_CHAR_0;
// break; //!< fall-through實現(xiàn)虛線切換
case READ_CHAR_0:
if (!serial_in(&chByte)) {
break;
}
if (chByte != 'O') {
CHECK_OK_RESET_FSM();
break;
}
s_tState = READ_CHAR_1:
// break; //!< fall-through實現(xiàn)虛線切換
case READ_CHAR_1:
if (!serial_in(&chByte)) {
break;
}
if (chByte != 'K') {
CHECK_OK_RESET_FSM();
break;
}
CHECK_OK_RESET_FSM();
return fsm_rt_cpl;
}
return fsm_rt_on_going;
}
是不是似曾相識？這不就是之前的所謂最優(yōu)代碼么？
【八狀態(tài)準則】
借助前面介紹的方法，我們不僅能優(yōu)雅的設(shè)計出邏輯清晰的狀態(tài)圖、兼顧翻譯后代碼的性能，還能在不影響邏輯清晰度的情況下減少狀態(tài)的數(shù)量。至此這里“粗暴的”提出一個名為“八狀態(tài)”的經(jīng)驗準則，即：
一個優(yōu)秀的狀態(tài)機通常不應(yīng)該擁有超過八個以上的狀態(tài)；
如果你的狀態(tài)機超過了八個狀態(tài)，那么一定存在狀態(tài)圖層面的優(yōu)化可能；
除了前面介紹過的能夠減少狀態(tài)的方法以外，將一部分高度相關(guān)（可能也重復(fù)出現(xiàn)）的狀態(tài)提取成為子狀態(tài)機，往往也能有效的減少狀態(tài)的數(shù)量。
【后記】
使用狀態(tài)圖來設(shè)計狀態(tài)機，其本意就是利用人類的視覺優(yōu)于閱讀能力的特性來降低設(shè)計難度。為了確保這一初衷能夠貫徹始終，“邏輯清晰”就成為狀態(tài)圖設(shè)計的核心原則。
本著清晰第一的原則，首先要確保狀態(tài)機邏輯正確，也就是常說的：先讓功能跑起來沒有問題；然后再考慮所謂的優(yōu)化的問題。此外，對于有經(jīng)驗的老工程師來說，要嘗試克服設(shè)計狀態(tài)圖時滿腦子都是具體代碼實現(xiàn)的弊端——至于這樣，才能真正擁抱使用狀態(tài)機進行開發(fā)的思維方式。
嵌入式編程專輯 Linux 學習專輯 C/C++編程專輯 Qt進階學習專輯
關(guān)注我的微信公眾號，回復(fù)“加群”按規(guī)則加入技術(shù)交流群。