來源：https://coolshell.cn/articles/12012.html
上回寫了篇《一個“蠅量級”C語言協程庫》，推薦了一下Protothreads，通過coroutine模擬了用戶級別的multi-threading模型，雖然本身足夠“輕”，杜絕了系統開銷，但這個庫本身應用場合主要是內存限制的嵌入式領域，提供原生態組件太少，使用限制太多，比如依賴其它調用產生阻塞等。
這回又替大家在開源界淘了個寶，推薦一個輕量級網絡應用框架State Threads（以下簡稱ST），總共也就3000行C代碼，跟Protothreads不同在於ST針對的就是高性能可擴展服務器領域（值得一提的是Protothreads官網參考鏈接上第一條就是ST的官網）。在其FAQ頁面上一句引用”Perfection is achieved not when there is nothing more to add, but rather when there is nothing more to take away.”可以視為開發人員對ST源碼質量的自信。
歷史淵源
首先介紹一下這個庫的歷史淵源，從代碼貢獻者來看，ST不是個人作品，而是有著雄厚的商業支持和應用背景，比如服務器領域，在這裡你可以看到ST曾作為Apache的多核應用模塊發佈。其誕生最初是由網景（Netscape）公司的MSPR（Netscape Portable Runtime library）項目中剝離出來，後由SGI（Silicon Graphic Inc）還有Yahoo!公司（前者是主力）開發維護的獨立線程庫。歷史版本方面，作為SourceForge上開源項目，由2001年發佈v1.0以來一直到2009年v1.9穩定版後未再變動。在平臺移植方面，從Makefile的配置選項中可知ST支持多種Unix-like平臺，還有專門針對Win32的源碼改寫。源碼例子中，提供了web server、proxy以及dns三種編程實例供參考。可以說代碼質量應該是相當的穩定和可靠的。
至於許可證方面，有必要略作說明。出於歷史原因，網景最初發布時選擇了MPL1.1許可證，而後SGI在維護中又混進了GPLv2許可證，照理說這兩種許可證是互不兼容的（MPL1.1後續版本是GPL兼容的），也就是說用雙許可證打包發佈理論上是非法無效的，見GNU官網上MPL兼容性一節。但這裡有值得商榷的地方，因為文中又提及，根據MPL1.1中某條款第13節，如果整段或部分代碼允許採用另一許可證作為備用（alternate）選擇，比如GPL及其兼容，那麼整個庫的許可證就可視為GPL兼容的。如此一來所謂GPL兼容性一般解釋為你不能在GPLv2的代碼中混入MPL1.1，而不是說你不能在MPL1.1代碼中混入GPLv2，也就是說GPLv2在MPL1.1之後是可以接受的，事實上SGI就採用了後面的做法，尚未引起版權上的糾紛。為此我還考證了一下FAQ上license一節的說法，說ST既可以在MPL和GPL之間選擇一種，也可以繼續用雙許可證，還補了一句在non-free項目使用上也沒有限制，但對ST源碼所做改動必須對用戶可見。在源碼文件中的SGI的附加聲明還解釋了將ST轉為GPL代碼的做法，就是可以刪除前面MPL的聲明，否則後續用戶仍可以在兩者之間二選一。個人覺得既然SGI都這樣發話了，那麼可解釋為反之刪除GPL的聲明繼續採用MPL也是可以接受的，如果你對雙許可證承諾仍不放心的話。
基於事件驅動狀態機（EDSM）
好了，下面該進入技術性話題了。前面說了ST的目標是高性能可擴展，其技術特徵一言以蔽之就是
“It combines the simplicity of the multi-threaded programming paradigm, in which one thread supports each simultaneous connection, with the performance and scalability of an event-driven state machine (EDSM) architecture.”我們先來縱向比較ST與傳統的EDSM區別，再來橫向比較與其它線程庫（比如Pthread）的區別（注：以下圖片全部來自State Threads Library FAQ）。
傳統EDSM最常見的方式就是I/O事件的異步回調。基本上都會有一個叫做dispatcher的單線程主循環（又叫event loop），用戶通過向dispatcher註冊回調函數（又叫event handler）來實現異步通知，從而不必在原地空耗資源乾等，在dispatcher主循環中通過select()/poll()系統調用來等待各種I/O事件的發生，當內核檢測到事件觸發並且數據可達或可用時，select()/poll()會返回從而使dispatcher調用相應的回調函數來對處理用戶的請求。所以異步回調與其說是通知，不如說用委託更恰當。
整個過程都是單線程的。這種處理本質上就是將一堆互不相交（disjoint）的回調實現同步控制，就像串聯在一個順序鏈表上。 見圖1，黑色的雙箭頭表示I/O事件複用，回調是個筐，裡面裝著對各種請求的處理（當然不是每個請求都有回調，一個請求也可以對應不同的回調），每個回調被串聯起來由dispatcher激活。這裡請求等價於thread的概念（不是操作系統的線程），只不過“上下文切換”（context switch）發生在每個回調結束之時（假設不同請求對應不同回調），註冊下一個回調以待事件觸發時恢復其它請求的處理。至於dispatcher的執行狀態（execute state）可作為回調函數的參數保存和傳遞。
異步回調的缺陷在於難以實現和擴展，雖然已經有libevent這樣的通用庫，以及其它actor/reacotor的設計模式及其框架，但正如Dean Gaudet（Apache開發者）所說：“其內在的複雜性——將線性思維分解成一堆回調的負擔（breaking up linear thought into a bucketload of callbacks）——仍然存在”。從上圖可見，回調之間請求例程不是連續的，比如回調之間的切換會打斷部分請求，又比如有新的請求需要重新註冊。
ST本質上仍然是基於EDSM模型，但旨在取代傳統的異步回調方式。ST將請求抽象為thread概念以更接近自然編程模式（所謂的linear thought吧，就像操作系統的線程之間切換那樣自然）。ST的調度器（scheduler）對於用戶來說是透明的，不像dispatcher那種將執行狀態（execute state）暴露給回調方式。每個thread的現場環境可以保存在棧上（一段連續的大小確定的內存空間），由C的運行環境管理。從圖2看到，ST的threads可以併發地線性地處理I/O事件，模型比異步回調簡單得多。
這裡稍微解釋一下ST調度工作原理，ST運行環境維護了四種隊列，分別是IOQ、RUNQ、SLEEPQ以及ZOMBIEQ，當每個thread處於不同隊列中對應不同的狀態（ST顧名思義所謂thread狀態機）。比如polling請求的時候，當前thread就加入IOQ表示等待事件（如果有timeout同時會被放到SLEEPQ中），當事件觸發時，thread就從IOQ（如果有timeout同時會從SLEEPQ）移除並轉移到RUNQ等待被調度，成為當前的running thread，相當於操作系統的就緒隊列，跟傳統EDSM對應起來就是註冊回調以及激活回調。再比如模擬同步控制wait/sleep/lock的時候，當前thread會被放入SLEEPQ，直到被喚醒或者超時再次進入RUNQ以待調度。
ST的調度具備性能與內存雙重優點：在性能上，ST實現自己的setjmp/longjmp來模擬調度，無任何系統開銷，並且context（就是jmp_buf）針對不同平臺和架構用底層語言實現的，可移植性媲美libc。下面放一段代碼解釋一下調度實現：
/*
* Switch away from the current thread context by saving its state
* and calling the thread scheduler
*/
#define _ST_SWITCH_CONTEXT(_thread) \
ST_BEGIN_MACRO \
if (!MD_SETJMP((_thread)->context)) { \
_st_vp_schedule(); \
} \
ST_END_MACRO
/*
* Restore a thread context that was saved by _ST_SWITCH_CONTEXT
* or initialized by _ST_INIT_CONTEXT
*/
#define _ST_RESTORE_CONTEXT(_thread) \
ST_BEGIN_MACRO \
_ST_SET_CURRENT_THREAD(_thread); \
MD_LONGJMP((_thread)->context, 1); \
ST_END_MACRO
void _st_vp_schedule(void)
{
_st_thread_t *thread;
if (_ST_RUNQ.next != &_ST_RUNQ) {
/* Pull thread off of the run queue */
thread = _ST_THREAD_PTR(_ST_RUNQ.next);
_ST_DEL_RUNQ(thread);
} else {
/* If there are no threads to run, switch to the idle thread */
thread = _st_this_vp.idle_thread;
}
ST_ASSERT(thread->state == _ST_ST_RUNNABLE);
/* Resume the thread */
thread->state = _ST_ST_RUNNING;
_ST_RESTORE_CONTEXT(thread);
}
如果你熟悉setjmp/longjmp的用法，你就知道當前thread在調用MD_SETJMP將現場上下文保存在jmp_buf中並返回返回0，然後自己調用_st_vp_schedule()將自己調度出去。調度器先從RUNQ上找，如果隊列為空就找idle thread，這是在整個ST初始化時創建的一個特殊thread，然後將當前線程設為自己，再調用MD_LONGJMP切換到其上次調用MD_SETJMP的地方，從thread->context恢復現場並返回1，該thread就接著往下執行了。
整個過程就同EDSM一樣發生在操作系統單線程下，所以沒有任何系統開銷與阻塞。其實真正的阻塞是發生在等待I/O事件複用上，也就是select()/poll()，這是整個ST唯一的系統調用。ST當前的狀態是，整個環境處於空閒狀態，所有threads的請求處理都已經完成，也就是RUNQ為空。這時在_st_idle_thread_start維護了一個主循環（類似於event loop），主要負責三種任務：1.對IOQ所有thread進行I/O複用檢測；2.對SLEEPQ進行超時檢查；3.將idle thread調度出去，代碼如下：
void *_st_idle_thread_start(void *arg)
{
_st_thread_t *me = _ST_CURRENT_THREAD();
while (_st_active_count > 0) {
/* Idle vp till I/O is ready or the smallest timeout expired */
_ST_VP_IDLE();
/* Check sleep queue for expired threads */
_st_vp_check_clock();
me->state = _ST_ST_RUNNABLE;
_ST_SWITCH_CONTEXT(me);
}
/* No more threads */
exit(0);
/* NOTREACHED */
return NULL;
}
這裡的me就是idle thread，因為_st_idle_thread_start就是創建idle thread的啟動點，每從上次_ST_SWITCH_CONTEXT()切換回來的時候，接著在_ST_VP_IDLE()裡輪詢I/O事件的發生，一旦檢測到發生了別的thread事件或者SLEEPQ裡面發生超時，再用_ST_SWITCH_CONTEXT()把自己切換出去，如果此時RUNQ中非空的話就切換到隊列第一個thread。這裡主循環是不會退出的。
在內存方面，ST的執行狀態作為局部變量保存在棧上，而不是像回調需要動態分配，用戶可能分別這樣使用thread模式和callback模式：
/* thread land */
int foo()
{
int local1;
int local2;
do_some_io();
}
/* callback land */
struct foo_data {
int local1;
int local2;
};
void foo_cb(void *arg)
{
struct foo_data *locals = arg;
...
}
void foo()
{
struct foo_data *locals = malloc(sizeof(struct foo_data));
register(foo_cb, locals);
}
基於Mult-Threading範式
同樣基於multi-threading編程範式，ST同其它線程庫又有和有點呢？比如Posix Thread（以下簡稱PThread）是個通用的線程庫，它是將用戶級線程（thread）同內核執行對象（kernel execution entity，有些書又叫lightweight processes）做了1:1或m:n映射，從而實現multi-threading模式。而ST是單線程（n:1映射），它的thread實際上就是協程（coroutine）。 通常的網絡應用上，多線程範式繞不開操作系統，但在某些特定的服務器領域，線程間的共享資源會帶來額外複雜度，鎖、競態、併發、文件句柄、全局變量、管道、信號等，面對這些Pthread的靈活性會大打折扣。而ST的調度是精確的，它只會在明確的I/O和同步函數調用點上發生上下文切換，這正是協程的特性，如此一來ST就不需要互斥保護了，進而也可以放心使用任何靜態變量和不可重入庫函數了（這在同樣作為協程的Protothreads裡是不允許的，因為那是stack-less的，無法保存上下文），極大的簡化了編程和調試同時增加了性能。
對於同樣用戶級線程如GNU Pth和MIT Phread比起來呢？有兩點，一是ST的thread是無優先級的非搶佔式調度，也就是說ST基於EDSM的，每個thread都是事件或數據驅動，遲早會把自己調度出去，而且調度點是明確的，並非按時間片來的，從而簡化了thread管理；二是ST會忽略所有信號處理，在_st_io_init中會把sigact.sa_handler設為SIG_IGN，這樣做是因為將thread資源最小化，避免了signal mask及其系統調用（在ucontext上是避免不了的）。但這並不意味著ST就不能處理信號，實際上ST建議將信號寫入pipe的方式轉化為普通I/O事件處理，示例詳見這裡。
這裡順便說一句，C語言實現的協程據我所知只有三種方式：Protothread為代表利用switch-case語義跳轉，以ST為代表不依賴libc的setjmp/longjmp上下文切換，以及依賴glibc的ucontext接口（雲風的coroutine）。第一種最輕，但受限最大，第三種耗資源性能慢（陳皓注：glibc的ucontext接口的實現中有一個和信號有關的系統調用，所以會慢，估計在一些情況下會比pthread還慢），目前看來ST是最好使的。
基於多核環境
下面來聊聊ST在多核環境下的應用。服務器領域多核的優勢在於實現了物理上真正的併發，所以如何充分利用系統優勢也是線程庫的一大難點。這對ST來說也許正是它的拿手好戲，前面提及ST曾作為Apache的多核引擎模塊發佈。這裡要補充一下前面漏掉的ST的一個重要概念——虛擬處理器（virtual processor，簡稱vp），見圖3，多個cpu通過內核的SMP模擬出多個“核”（core），一個core對應一個內核任務（kernel task），同時對應一個用戶進程（process），一個process對應ST的一個vp，每個vp下就是ST的thread（是協程不是線程），結合前面所述，vp初始化先創建idle thread，然後根據I/O事件驅動其它threads，這就是ST的多核架構。
這裡要指出的是，ST只負責自身thread調度，進程管理是應用程序的事情，也就是說由用戶來決定fork多少進程，每個進程分配多少資源，如何進行IPC等。這種架構的好處就是每個vp有自己獨立的空間，避免了資源同步競態（比如杜絕了多進程裡的多線程這樣混亂的模型）。我們知道這種基於進程的架構是非常健壯的，一個進程奔潰不會影響到其它進程，同時充分利用多核硬件的高併發。 同時對於具體邏輯業務使用vp裡的thread處理，這是基於EDSM的，如此一來做到了邏輯業務與內核執行對象之間的解耦，沒必要因為1K個連接去創建1K的進程。這就是ST的擴展性和靈活性。
使用限制
ST的主要限制在於，應用程序所有I/O操作必須使用ST提供的API，因為只有這樣thread才能被調度器管理，並且避免阻塞。
另一個限制在於thread調試，這本身不容易，好在v1.9的ST提供了DEBUG參數，使用TREADQ以及_st_iterate_threads接口檢測thread調度情況，用戶還可自定義_st_show_thread_stack接口dump每個thread的棧，在GDB使能_st_iterate_threads_flag變量，這些都在Readme中對調試方法有具體說明。按下不表。
總結
這篇文章寫得有點短了，主要是通過對比來介紹ST的，其實還有大段原理可以講，大段源碼以及實戰用例可以貼，但這一下子又寫不過來，ST還是有點技術含量的。說白了，ST的核心思想就是利用multi-threading的簡單優雅範式勝過傳統異步回調的複雜晦澀實現，又利用EDSM的性能和解耦架構避免了multi-threading在系統上的開銷和暗礁。 學習ST告訴我們一個道理：未來技術的趨勢永遠都是融合的。
參考
- 在SourceForge以及github上的源碼：前者有歷史版本及win32版本，後者只有v1.9。
- State Threads for Internet Applications：介紹原理的，值得一看，這裡有篇中文翻譯附加單元測試（在單CPU 512M內存上創建數萬個thread，CPU佔用率約5%，內存約4.3K/thread）。
- State Threads Library FAQ：本文基於此而寫。
- Complete reference：API完全手冊。
- Programing Notes：編程注意事項，包括信號處理，IPC，非網絡I/O事件等。
閱讀更多 cpp軟件架構獅 的文章
