關于Golang和JVM中并發模型實現的探討

引子

話說最近終于決定把之前收藏了很久的 mit-6.824 課程的lab拿出來做一下，這門課最有價值的地方就在于它設計了一些列的lab，讓你能夠在一定程度可控的工作量的coding之后比較深入地體會到眾多分布式程序中所面臨的一些列公共的問題以及如何去解決它們。例如，分布式容錯、并發、網絡底層實現等等。這門課的targeted language是golang。原因自然不說，因為golang的簡潔所以非常適合用來替代C++等語言來作為lab的實現語言。

在實現的過程當中，我遇到的一個最主要的問題就是，如何在CPU密集型任務、I/O密集型任務以及充分利用多核CPU提升程序性能上找到一個平衡點。當然，這之中最容易想到的解決方案就是 多線程 。但是由于分布式程序的特殊性，它可能擁有大量的網絡I/O或者計算任務。這就不可避免需要將使用同步的方式來抒寫異步的情懷，解決方案就是將這些計算或者IO放到新的線程中去做，具體的線程調度交給操作系統來完成（雖然我們可以使用異步IO，但是異步IO由于存在大量的callback，不便于程序邏輯組織，所以這里不考慮直接使用異步IO）。這樣有一個問題就在于，這之中會有大量的線程在context中，所以線程的上下文切換的開銷不可忽視。如果我們在jvm中實現的話，大量的thread可能會很快耗盡jvm堆的內存，不僅會造成堆溢出，而且增大GC時間和不穩定性。因此，最近我就考察了幾種常見的并發編程模型以及其對應常見的實現方式。

常見并發編程模型分類

并發編程模型，顧名思義就是為了解決高并發充分利用多核特性減少CPU等待提高吞吐量而提出的相關的編程范式。目前為止，我覺得比較常見的并發編程模型大致可以分為兩類：

• 基于消息（事件）的活動對象

• 基于 CSP 模型的協程的實現

其中基于消息（事件）的活動對象的并發模型，最典型的代表就是Akka的actor。actor的并發模型是把一個個計算序列按抽象為一個一個Actor對象，每一個Actor之間通過異步的消息傳遞機制來進行通訊。這樣一來，本來順序阻塞的計算序列，就被分散到了一個一個Actor中。我們在Actor中的操作應該盡量保證非阻塞性。當然，在akka中actor是根據具體的Dispatcher來決定如何處理某一個actor的消息，默認的dispatcher是ForkJoinExecutor，只適合用來處理非阻塞非CPU密集型的消息；akka中還有另外一些Dispatcher可以用于處理阻塞或者CPU密集型的消息，具體的底層實現用到CachedThreadPool。這兩種Dispatcher結合起來，我們便能在jvm上建立完整的并發模型。

基于協程的實現，這里主要的代表就是goroutine。Golang的runtime實現了goroutine和OS thread的M:N模型，因此實際的goroutine是基于線程的更加輕量級的實現，我們便可以在Golang中大量創建goroutine而不用擔心昂貴的context swtich所帶來的開銷。goroutine之間，我們可以通過channel來進行交互。由于go已將將所有system call都wrap到了標準庫中，在針對這些systemcall進行調用時會主動標記goroutine為阻塞狀態并保存現場，交由scheduler執行。所以在golang中，在大部分情況下我們可以非常安心地在goroutine中使用阻塞操作而不用擔心并發性受到影響。

goroutine的這種并發模型有一個非常明顯的優勢，我們可以簡單地使用人見人愛的阻塞編程方式來抒發異步的情懷，只要能合理運用 go 關鍵字。相比較于akka的actor而言，goroutine的程序可讀性更強且更好定位錯誤。

Java能否做到goroutine這樣？

既然goroutine這么好用，那么我們能否基于jdk來實現一套類似goroutine的并發模型庫？很遺憾，如果基于JDK的話，是無法實現的。下面我們來分析一下這個問題的本質。

下面我將goroutine的并發模型定義為以下幾個要點：

• 基于Thread的輕量級協程

• 通過channel來進行協程間的消息傳遞

• 只暴露協程，屏蔽線程操作的接口

首先，我們假設能夠在JDK中建立起一套基于已有Thread模型的coroutine機制，并且可以通過調用某些方法來創建coroutine對象，分配coroutine任務并執行。但是JDK中存在許多已有的阻塞操作，而這些阻塞操作的調用會直接讓線程被阻塞，這樣一來依托于線程的coroutine就會失去重新調度的能力。也許你有很多其他的方法進行設計，但是這里本質問題是 不管你怎么進行設計，你都始終無法擺脫JDK中協程狀態和線程狀態不統一的情況 。除非做到像Go中一樣，所有的阻塞操作均被wrap到協程的層次來進行操作。所以，一旦我們用到JDK中和線程綁定的阻塞API時，那么這種并發模型就基本歇菜了。

那么下面我們來分析一下goroutine的實現原理從而解釋為什么Java無法做到goroutine那樣的協程。

Goroutine原理

在操作系統的OS Thread和編程語言的User Thread之間，實際上存在3中線程對應模型，也就是：1:1，1:N，M:N。

JVM specification中規定JVM線程和操作系統線程為1:1的關系，也就是說Java中的Thread和OS Thread為1:1的關系。也有把線程模型實現為1:N的模式，不過這樣做其實不夠靈活。goroutine google runtime默認的實現為M:N的模型，于是這樣可以根據具體的操作類型（操作系統阻塞或非阻塞操作）調整goroutine和OS Thread的映射情況，顯得更加的靈活。

在goroutine實現中，有三個最重要的數據結構，分別為G M P：

• G：代表一個goroutine

• M：代表 一個OS Thread

• P：一個P和一個M進行綁定，代表在這個OS Thread上的調度器

如上圖所示，我們可以看到圖中有兩個M，即兩個OS Thread線程，分別對應一個P，每一個P有負責調度多個G。如此一來，就組成的goroutine運行時的基本結構。

下面我們對G M P的具體代碼進行分析

structG
{
 uintptr stackguard0;// 用于棧保護，但可以設置為StackPreempt，用于實現搶占式調度
 uintptr stackbase; // 棧頂
 Gobuf sched; // 執行上下文，G的暫停執行和恢復執行，都依靠它
 uintptr stackguard; // 跟stackguard0一樣，但它不會被設置為StackPreempt
 uintptr stack0; // 棧底
 uintptr stacksize; // 棧的大小
 int16 status; // G的六個狀態
 int64 goid; // G的標識id
 int8 waitreason; // 當status==Gwaiting有用，等待的原因，可能是調用time.Sleep之類
 G schedlink; // 指向鏈表的下一個G
 uintptr gopc; // 創建此goroutine的Go語句的程序計數器PC，通過PC可以獲得具體的函數和代碼行數
};

structP
{
 Lock; // plan9 C的擴展語法，相當于Lock lock;
int32 id; // P的標識id
 uint32 status; // P的四個狀態
 P link; // 指向鏈表的下一個P
 M m; // 它當前綁定的M，Pidle狀態下，該值為nil
 MCache* mcache; // 內存池
// Grunnable狀態的G隊列
 uint32 runqhead;
 uint32 runqtail;
 G* runq[256];
// Gdead狀態的G鏈表（通過G的schedlink）
// gfreecnt是鏈表上節點的個數
 G* gfree;
 int32 gfreecnt;
};
structM
{
 G g0; // M默認執行G
void(mstartfn)(void);// OS線程執行的函數指針
 G curg; // 當前運行的G
 P p; // 當前關聯的P，要是當前不執行G，可以為nil
 P nextp; // 即將要關聯的P
 int32 id; // M的標識id
 M alllink; // 加到allm，使其不被垃圾回收(GC)
 M schedlink; // 指向鏈表的下一個M
};
</code></pre> 
  
這里，G最重要的三個狀態為Grunnable Grunning Gwaiting。具體的狀態遷移為Grunnable -> Grunning -> Gwaiting -> Grunnable。goroutine在狀態發生轉變時，會對棧的上下文進行保存和恢復。下面讓我們來開一下G中的Gobuf的定義
 
  
structGobuf
{
 uintptr sp; // 棧指針
 uintptr pc; // 程序計數器PC
 G g; // 關聯的G
};
</code></pre> 
  
當具體要保存棧上下文時，最重要的就是保存這個Gobuf結構中的內容。goroutine具體是通過 void gosave(Gobuf*) 以及 void gogo(Gobuf*) 這兩個函數來實現棧上下文的保存和恢復的，具體的底層實現為匯編代碼，因此goroutine的context swtich會非常快。
 
  
接下來，我們來具體看一下goroutine scheduler在幾個主要場景下的調度策略。
 
  
goroutine將scheduler的執行交給具體的M，即OS Thread。每一個M就執行一個函數，即 void schedule(void) 。這個函數具體做得事情就是從各個運行隊列中選擇合適的goroutine然后執行goroutine中對應的 func 。
 
  
具體的schedule函數如下：
 
  
// 調度的一個回合：找到可以運行的G，執行
// 從不返回
staticvoidschedule(void)
{
 G *gp;
 uint32 tick;

top:
 gp = nil;
// 時不時檢查全局的可運行隊列，確保公平性
// 否則兩個goroutine不斷地互相重生，完全占用本地的可運行隊列
 tick = m->p->schedtick;
// 優化技巧，其實就是tick%61 == 0
if(tick - (((uint64)tick0x4325c53fu)>>36)61==0&& runtime·sched.runqsize >0) {
 runtime·lock(&runtime·sched);
 gp = globrunqget(m->p, 1);// 從全局可運行隊列獲得可用的G
 runtime·unlock(&runtime·sched);
if(gp)
 resetspinning();
 }
if(gp == nil) {
 gp = runqget(m->p); // 如果全局隊列里沒找到，就在P的本地可運行隊列里找
if(gp && m->spinning)
 runtime·throw("schedule: spinning with local work");
 }
if(gp == nil) {
 gp = findrunnable(); // 阻塞住，直到找到可用的G
 resetspinning();
 }
// 是否啟用指定某M來執行該G
if(gp->lockedm) {
// 把P給指定的m，然后阻塞等新的P
 startlockedm(gp); 
gototop;
 }
execute(gp); // 執行G
}
</code></pre> 
  
于是這里拋出幾個問題：
 
  
 
   
當M發現分配給自己的goroutine鏈表已經執行完畢時怎么辦？
 
   
當goroutine陷入系統調用阻塞后，M是否也一起阻塞？
 
   
當某個gorouine長時間占用CPU怎么辦？
 
  
 
  
首先第一個問題，當M發現在P中的gorouine鏈表已經全部執行完畢時，將會從其他的P中偷取goroutine然后執行，其策略就是一個工作密取的機制。當其他的P也沒有可執行的goroutine時，就會從全局等待隊列中尋找runnable的goroutine進行執行，如果還找不到，則M讓出CPU調度。
 
  
第二個問題，例如阻塞IO讀取本地文件，此時調用會systemcall會陷入內核，不可避免地會使得調用線程阻塞，因此這里goroutine的做法是將所有可能阻塞的系統調用均封裝為gorouine友好的接口。具體做法為，在每次進行系統調用之前，從一個線程池從獲取一個OS Thread并執行該系統調用，而本來運行的gorouine則將自己的狀態改為Gwaiting，并將控制權交給scheduler繼續調度，系統調用的返回通過channel進行同步即可。因此，這里其實goroutine也沒有辦法做到完全的協程化，因為系統調用總會阻塞線程。 具體可以參考stackoverflow上的討論 ： 鏈接
 
  
第三個問題，go支持簡單的搶占式調度，在goruntime中有一個sysmon線程，負責檢測goruntime的各種狀態。sysmon其中一項職責就是檢測是否有長時間占用CPU的goroutine，如果發現了就將其搶占過來。
 
  
JDK上無法實現goroutine的原因
 
  
到這里，我們已經大致了解了goroutine的原理，可見goroutine中最重要的一個設計就在于它將所有的語言層次上的api都限制在了goroutine這一層，進而屏蔽了執行代碼與具體線程交互的機會。所以在goroutine中，我們實際上就可以忽略線程的存在，把goroutine當成是一個非常廉價能夠大量創建的Thread。
 
  
然而在Java中或者說打算和JDK交互的JVM系語言（如scala，clojure），本質上都無法完全實現goroutine（clojure雖然有async，但是依然無法和JDK中的阻塞api結合良好）。假設，我們在Java中基于Thread之上實現一個scheduler，一個輕量級的協程以及協程相關的原語（如resume, pause等），我們也只能基于我們自己封裝的api來協助協程調度。如果在創建的協程中直接使用Java阻塞api，結果就是使得用來調度協程的OS Thread陷入阻塞，無法繼續運行scheduler進行調度。
 
  
綜上所述，如果在不更改JDK Native實現的前提下，我們是無法徹底實現類似goroutine的協程的。
 
  
TODO
 
  
于是乎，要使得JDK支持coroutine，那么我們就只能改JDK了，是的我就是這么執著！。
 
  
 
 
  
來自：http://www.nyankosama.com/2015/04/03/java-goroutine/