golang的goroutine是如何實現的？

01-05

我知道同步並發的原理是利用進程或者線程，由操作系統調度；非同步並發的原理是DMA，即不經過CPU直接把IO的某一快copy到memory上或者反之，那麼，新學golang的我想知道，golang的所謂goroutine (協程)如何實現的？

The Go scheduler 純翻譯如下：

Go runtime的調度器：

在了解Go的運行時的scheduler之前，需要先了解為什麼需要它，因為我們可能會想，OS內核不是已經有一個線程scheduler了嘛？

熟悉POSIX API的人都知道，POSIX的方案在很大程度上是對Unix process進場模型的一個邏輯描述和擴展，兩者有很多相似的地方。 Thread有自己的信號掩碼，CPU affinity等。但是很多特徵對於Go程序來說都是累贅。尤其是context上下文切換的耗時。另一個原因是Go的垃圾回收需要所有的goroutine停止，使得內存在一個一致的狀態。垃圾回收的時間點是不確定的，如果依靠OS自身的scheduler來調度，那麼會有大量的線程需要停止工作。

單獨的開發一個GO得調度器，可以是其知道在什麼時候內存狀態是一致的，也就是說，當開始垃圾回收時，運行時只需要為當時正在CPU核上運行的那個線程等待即可，而不是等待所有的線程。

用戶空間線程和內核空間線程之間的映射關係有：N:1,1:1和M:N

N:1是說，多個（N）用戶線程始終在一個內核線程上跑，context上下文切換確實很快，但是無法真正的利用多核。

1：1是說，一個用戶線程就只在一個內核線程上跑，這時可以利用多核，但是上下文switch很慢。

M:N是說，多個goroutine在多個內核線程上跑，這個看似可以集齊上面兩者的優勢，但是無疑增加了調度的難度。

Go的調度器內部有三個重要的結構：M，P，S

M:代表真正的內核OS線程，和POSIX里的thread差不多，真正幹活的人

G:代表一個goroutine，它有自己的棧，instruction pointer和其他信息（正在等待的channel等等），用於調度。

P:代表調度的上下文，可以把它看做一個局部的調度器，使go代碼在一個線程上跑，它是實現從N:1到N:M映射的關鍵。

圖中看，有2個物理線程M，每一個M都擁有一個context（P），每一個也都有一個正在運行的goroutine。

P的數量可以通過GOMAXPROCS()來設置，它其實也就代表了真正的並發度，即有多少個goroutine可以同時運行。

圖中灰色的那些goroutine並沒有運行，而是出於ready的就緒態，正在等待被調度。P維護著這個隊列（稱之為runqueue），

Go語言里，啟動一個goroutine很容易：go function 就行，所以每有一個go語句被執行，runqueue隊列就在其末尾加入一個

goroutine，在下一個調度點，就從runqueue中取出（如何決定取哪個goroutine？）一個goroutine執行。

為何要維護多個上下文P？因為當一個OS線程被阻塞時，P可以轉而投奔另一個OS線程！

圖中看到，當一個OS線程M0陷入阻塞時，P轉而在OS線程M1上運行。調度器保證有足夠的線程來運行所以的context P。

圖中的M1可能是被創建，或者從線程緩存中取出。當MO返回時，它必須嘗試取得一個context P來運行goroutine，一般情況下，它會從其他的OS線程那裡steal偷一個context過來，

如果沒有偷到的話，它就把goroutine放在一個global runqueue里，然後自己就去睡大覺了（放入線程緩存里）。Contexts們也會周期性的檢查global runqueue，否則global runqueue上的goroutine永遠無法執行。

另一種情況是P所分配的任務G很快就執行完了（分配不均），這就導致了一個上下文P閑著沒事兒干而系統卻任然忙碌。但是如果global runqueue沒有任務G了，那麼P就不得不從其他的上下文P那裡拿一些G來執行。一般來說，如果上下文P從其他的上下文P那裡要偷一個任務的話，一般就『偷』run queue的一半，這就確保了每個OS線程都能充分的使用。

之前我也很關注這個問題，搜集到了一些資料，分享給你。

《go中的調度分析》

《goroutine背後的系統知識》

還有一個是Columbia University的三個傢伙發表的一篇paper,

《Analysis of the Go runtime scheduler》

最後還有Golang核心成員寫一個Goroutine Scheduler的設計。《 Scalable Go Scheduler Design Doc》以及對其詳細解釋的《The Go scheduler》

Goroutines are part of making concurrency easy to use. The idea, which has been around for a while, is to multiplex independently executing functions—coroutines—onto a set of threads. When a coroutine blocks, such as by calling a blocking system call, the run-time automatically moves other coroutines on the same operating system thread to a different, runnable thread so they won"t be blocked. The programmer sees none of this, which is the point. The result, which we call goroutines, can be very cheap: unless they spend a lot of time in long-running system calls, they cost little more than the memory for the stack, which is just a few kilobytes.

To make the stacks small, Go"s run-time uses segmented stacks. A newly minted goroutine is given a few kilobytes, which is almost always enough. When it isn"t, the run-time allocates (and frees) extension segments automatically. The overhead averages about three cheap instructions per function call. It is practical to create hundreds of thousands of goroutines in the same address space. If goroutines were just threads, system resources would run out at a much smaller number.

----------------- 我是分割線----------------------------------

我對goroutine的理解類似於C/C++下常用的線程池技術。但是goroutine要在這基礎上大大的前進了好多。首先,go關鍵字極大的簡化了C/C++下往線程池投遞任務的操作。雖然C++11引入了lambda，但是因為沒有GC的緣故用起來還是稍微蛋疼的。其次就是goroutine的調度器解決了一般線程池常見的問題，就是遇到阻塞或者同步動作時，怎麼讓線程池更容易擴展，不會因為其中一個任務的阻塞或者同步獨佔線程，甚至怎麼避免由此問題帶來的死鎖。而在C/C++語言里，想做到這點非常的困難，沒有類似Golang的runtime，做起來會非常痛苦。 Golang在這點上做的也是非常的漂亮。發起的同步或者channel動作，哪怕網路操作，都會把自身goroutine切換出去，讓下一個預備好的goroutine去運行。而且Golang其本身還在此基礎上很容易的做到對線程池的擴展，根據程序行為自動擴展或者收縮線程，儘可能的讓線程保持在一個合適的數目。

要理解這個事兒首先得了解操作系統是怎麼玩線程的。一個線程就是一個棧加一堆資源。操作系統一會讓cpu跑線程A，一會讓cpu跑線程B，靠A和B的棧來保存A和B的執行狀態。每個線程都有他自己的棧。

但是線程又老貴了，花不起那個錢，所以go發明了goroutine。大致就是說給每個goroutine弄一個分配在heap裡面的棧來模擬線程棧。比方說有3個goroutine，A,B,C，就在heap上弄三個棧出來。然後Go讓一個單線程的scheduler開始跑他們仨。相當於 { A(); B(); C() }，連續的，串列的跑。

和操作系統不太一樣的是，操作系統可以隨時隨地把你線程停掉，切換到另一個線程。這個單線程的scheduler沒那個能力啊，他就是user space的一段樸素的代碼，他跑著A的時候控制權是在A的代碼裡面的。A自己不退出誰也沒辦法。

所以A跑一小段後需要主動說，老大（scheduler），我不想跑了，幫我把我的所有的狀態保存在我自己的棧上面，讓我歇一會吧。這時候你可以看做A返回了。A返回了B就可以跑了，然後B跑一小段說，跑夠了，保存狀態，返回，然後C再跑。C跑一段也返回了。

這樣跑完{A(); B(); C()}之後，我們發現，好像他們都只跑了一小段啊。所以外面要包一個循環，大致是：

goroutine_list = [A, B, C] while(goroutine): for goroutine in goroutine_list: r = goroutine() if r.finished(): goroutine_list.remove(r)

比如跑完一圈A，B，C之後誰也沒執行完，那麼就在回到A執行一次。由於我們把A的棧保存在了HEAP里，這時候可以把A的棧複製粘貼會系統棧里（我很確定真實情況不是這麼玩的，會意就行），然後再調用A，這時候由於A是跑到一半自己說跳出來的，所以會從剛剛跳出來的地方繼續執行。比如A的內部大致上是這樣

def A: 上次跑到的地方 = 找到上次跑哪兒了讀取所有臨時變數 goto 上次跑到的地方 a = 1 print("do something") go.scheduler.保存程序指針 // 設置"這次跑哪兒了" go.scheduler.保存臨時變數們 go.scheduler.跑夠了_換人 //相當於return print("do something again") print(a)

第一次跑A，由於這是第一次，會列印do something，然後保存臨時變數a，並保存跑到的地方，然後返回。再跑一次A，他會找到上次返回的地方的下一句，然後恢復臨時變數a，然後接著跑，會列印「do something again"和1

所以你看出來了，這個關鍵就在於每個goroutine跑一跑就要讓一讓。一般支持這種玩意（叫做coroutine）的語言都是讓每個coroutine自己說，我跑夠了，換人。goroutine比較文藝的地方就在於，他可以來幫你判斷啥時候「跑夠了」。

其中有一大半就是靠的你說的「非同步並發」。go把每一個能非同步並發的操作，像你說的文件訪問啦，網路訪問啦之類的都包包好，包成一個看似樸素的而且是同步的「方法」，比如string readFile（我瞎舉得例子）。但是神奇的地方在於，這個方法里其實會調用「非同步並發」的操作，比如某操作系統提供的asyncReadFile。你也知道，這種非同步方法都是很快返回的。

所以你自己在某個goroutine里寫了

string s = go.file.readFile("/root")

其實go偷偷在裡面執行了某操作系統的API asyncReadFIle。跑起來之後呢，這個方法就會說，我當前所在的goroutine跑夠啦，把剛剛跑的那個非同步操作的結果保存下下，換人：

// 實際上 handler h = someOS.asyncReadFile("/root") //很快返回一個handler while (!h.finishedAsyncReadFile()): //很快返回Y/N go.scheduler.保存現狀() go.scheduler.跑夠了_換人() // 相當於return，不過下次會從這裡的下一句開始執行 string s = h.getResultFromAsyncRead()

然後scheduler就換下一個goroutine跑了。等下次再跑回剛才那個goroutine的時候，他就看看，說那個asyncReadFile到底執行完沒有啊，如果沒有，就再換個人吧。如果執行完了，那就把結果拿出來，該幹嘛幹嘛。所以你看似寫了個同步的操作，已經被go替換成非同步操作了。

還有另外一種情況是，某個goroutine執行了某個不能非同步調用的會blocking的系統調用，這個時候goroutine就沒法玩那種非同步調用的把戲了。他會把你挪到一個真正的線程里讓你在那個縣城裡等著，他接茬去跑別的goroutine。比如A這麼定義

def A: print("do something") go.os.InvokeSomeReallyHeavyAndBlockingSystemCall() print("do something 2")

go會幫你轉成

def 真實的A: print("do something") Thread t = new Thread( () =&> { SomeReallyHeavyAndBlockingSystemCall(); }) t.start() while !t.finished(): go.scheduler.保存現狀 go.scheduler.跑夠了_換人 print("finished")

所以真實的A還是不會blocking，還是可以跟別的小夥伴(goroutine)愉快地玩耍（輪流往複的被執行），但他其實已經佔了一個真是的系統線程了。

當然會有一種情況就是A完全沒有調用任何可能的「非同步並發」的操作，也沒有調用任何的同步的系統調用，而是一個勁的用CPU做運算（比如用個死循環調用a++）。在早期的go里，這個A就把整個程序block住了。後面新版本的go好像會有一些處理辦法，比如如果你A裡面call了任意一個別的函數的話，就有一定幾率被踢下去換人。好像也可以自己主動說我要換人的，可以去查查新的go的spec

另外，請不要在意語言細節，技術細節。會意即可

我覺得這篇文章講的最生動最容易理解

鏈接：http://studygolang.com/wr?u=http%3a%2f%2fskoo.me%2fgo%2f2013%2f11%2f29%2fgolang-schedule

我們都知道Go語言是原生支持語言級並發的，這個並發的最小邏輯單元就是goroutine。goroutine就是Go語言提供的一種用戶態線程，當然這種用戶態線程是跑在內核級線程之上的。當我們創建了很多的goroutine，並且它們都是跑在同一個內核線程之上的時候，就需要一個調度器來維護這些goroutine，確保所有的goroutine都使用cpu，並且是儘可能公平的使用cpu資源。

這個調度器的原理以及實現值得我們去深入研究一下。支撐整個調度器的主要有4個重要結構，分別是M、G、P、Sched，前三個定義在runtime.h中，Sched定義在proc.c中。

Sched結構就是調度器，它維護有存儲M和G的隊列以及調度器的一些狀態信息等。
M代表內核級線程，一個M就是一個線程，goroutine就是跑在M之上的；M是一個很大的結構，裡面維護小對象內存cache（mcache）、當前執行的goroutine、隨機數發生器等等非常多的信息。
P全稱是Processor，處理器，它的主要用途就是用來執行goroutine的，所以它也維護了一個goroutine隊列，裡面存儲了所有需要它來執行的goroutine，這個P的角色可能有一點讓人迷惑，一開始容易和M衝突，後面重點聊一下它們的關係。
G就是goroutine實現的核心結構了，G維護了goroutine需要的棧、程序計數器以及它所在的M等信息。

理解M、P、G三者的關係對理解整個調度器非常重要，我從網路上找了一個圖來說明其三者關係：

地鼠(gopher)用小車運著一堆待加工的磚。M就可以看作圖中的地鼠，P就是小車，G就是小車裡裝的磚。一圖勝千言啊，弄清楚了它們三者的關係，下面我們就開始重點聊地鼠是如何在搬運磚塊的。

啟動過程

在關心絕大多數程序的內部原理的時候，我們都試圖去弄明白其啟動初始化過程，弄明白這個過程對後續的深入分析至關重要。在asm_amd64.s文件中的彙編代碼_rt0_amd64就是整個啟動過程，核心過程如下：

CALL runtime·args(SB) CALL runtime·osinit(SB) CALL runtime·hashinit(SB) CALL runtime·schedinit(SB)


// create a new goroutine to start program

PUSHQ	$runtime·main·f(SB)		// entry

PUSHQ	$0			// arg size

CALL	runtime·newproc(SB)

POPQ	AX

POPQ	AX

// start this M CALL runtime·mstart(SB)

啟動過程做了調度器初始化runtime·schedinit後，調用runtime·newproc創建出第一個goroutine，這個goroutine將執行的函數是runtime·main，這第一個goroutine也就是所謂的主goroutine。我們寫的最簡單的Go程序」hello，world」就是完全跑在這個goroutine里，當然任何一個Go程序的入口都是從這個goroutine開始的。最後調用的runtime·mstart就是真正的執行上一步創建的主goroutine。

啟動過程中的調度器初始化runtime·schedinit函數主要根據用戶設置的GOMAXPROCS值來創建一批小車(P)，不管GOMAXPROCS設置為多大，最多也只能創建256個小車(P)。這些小車(p)初始創建好後都是閑置狀態，也就是還沒開始使用，所以它們都放置在調度器結構(Sched)的pidle欄位維護的鏈表中存儲起來了，以備後續之需。

查看runtime·main函數可以了解到主goroutine開始執行後，做的第一件事情是創建了一個新的內核線程(地鼠M)，不過這個線程是一個特殊線程，它在整個運行期專門負責做特定的事情——系統監控(sysmon)。接下來就是進入Go程序的main函數開始Go程序的執行。

至此，Go程序就被啟動起來開始運行了。一個真正幹活的Go程序，一定創建有不少的goroutine，所以在Go程序開始運行後，就會向調度器添加goroutine，調度器就要負責維護好這些goroutine的正常執行。

創建goroutine(G)

在Go程序中，時常會有類似代碼：

go do_something()

go關鍵字就是用來創建一個goroutine的，後面的函數就是這個goroutine需要執行的代碼邏輯。go關鍵字對應到調度器的介面就是runtime·newproc。runtime·newproc乾的事情很簡單，就負責製造一塊磚(G)，然後將這塊磚(G)放入當前這個地鼠(M)的小車(P)中。

每個新的goroutine都需要有一個自己的棧，G結構的sched欄位維護了棧地址以及程序計數器等信息，這是最基本的調度信息，也就是說這個goroutine放棄cpu的時候需要保存這些信息，待下次重新獲得cpu的時候，需要將這些信息裝載到對應的cpu寄存器中。

假設這個時候已經創建了大量的goroutne，就輪到調度器去維護這些goroutine了。

創建內核線程(M)

Go程序中沒有語言級的關鍵字讓你去創建一個內核線程，你只能創建goroutine，內核線程只能由runtime根據實際情況去創建。runtime什麼時候創建線程？以地鼠運磚圖來講，磚(G)太多了，地鼠(M)又太少了，實在忙不過來，剛好還有空閑的小車(P)沒有使用，那就從別處再借些地鼠(M)過來直到把小車(p)用完為止。這裡有一個地鼠(M)不夠用，從別處借地鼠(M)的過程，這個過程就是創建一個內核線程(M)。創建M的介面函數是:

void newm(void (*fn)(void), P *p)

newm函數的核心行為就是調用clone系統調用創建一個內核線程，每個內核線程的開始執行位置都是runtime·mstart函數。參數p就是一輛空閑的小車(p)。

每個創建好的內核線程都從runtime·mstart函數開始執行了，它們將用分配給自己小車去搬磚了。

###調度核心

newm介面只是給新創建的M分配了一個空閑的P，也就是相當於告訴借來的地鼠(M)——「接下來的日子，你將使用1號小車搬磚，記住是1號小車；待會自己到停車場拿車。」，地鼠(M)去拿小車(P)這個過程就是acquirep。runtime·mstart在進入schedule之前會給當前M裝配上P，runtime·mstart函數中的代碼：

} else if(m != runtime·m0) { acquirep(m-&>nextp); m-&>nextp = nil; } schedule();

if分支的內容就是為當前M裝配上P，nextp就是newm分配的空閑小車(P)，只是到這個時候才真正拿到手罷了。沒有P，M是無法執行goroutine的，就像地鼠沒有小車無法運磚一樣的道理。對應acquirep的動作是releasep，把M裝配的P給載掉；活幹完了，地鼠需要休息了，就把小車還到停車場，然後睡覺去。

地鼠(M)拿到屬於自己的小車(P)後，就進入工場開始幹活了，也就是上面的schedule調用。簡化schedule的代碼如下：

static void schedule(void) { G *gp;


	gp = runqget(m-&>p);

	if(gp == nil)

		gp = findrunnable();
	if (m-&>p-&>runqhead != m-&>p-&>runqtail

		runtime·atomicload(runtime·sched.nmspinning) == 0

		runtime·atomicload(runtime·sched.npidle) &> 0)  // TODO: fast atomic

		wakep();

execute(gp); }

schedule函數被我簡化了太多，主要是我不喜歡貼大段大段的代碼，因此只保留主幹代碼了。這裡涉及到4大步邏輯：

runqget, 地鼠(M)試圖從自己的小車(P)取出一塊磚(G)，當然結果可能失敗，也就是這個地鼠的小車已經空了，沒有磚了。
findrunnable, 如果地鼠自己的小車中沒有磚，那也不能閑著不幹活是吧，所以地鼠就會試圖跑去工場倉庫取一塊磚來處理；工場倉庫也可能沒磚啊，出現這種情況的時候，這個地鼠也沒有偷懶停下幹活，而是悄悄跑出去，隨機盯上一個小夥伴(地鼠)，然後從它的車裡試圖偷一半磚到自己車裡。如果多次嘗試偷磚都失敗了，那說明實在沒有磚可搬了，這個時候地鼠就會把小車還回停車場，然後睡覺休息了。如果地鼠睡覺了，下面的過程當然都停止了，地鼠睡覺也就是線程sleep了。
wakep, 到這個過程的時候，可憐的地鼠發現自己小車裡有好多磚啊，自己根本處理不過來；再回頭一看停車場居然有閑置的小車，立馬跑到宿舍一看，你妹，居然還有小夥伴在睡覺，直接給屁股一腳，「你妹，居然還在睡覺，老子都快累死了，趕緊起來幹活，分擔點工作。」，小夥伴醒了，拿上自己的小車，乖乖幹活去了。有時候，可憐的地鼠跑到宿舍卻發現沒有在睡覺的小夥伴，於是會很失望，最後只好向工場老闆說——」停車場還有閑置的車啊，我快乾不動了，趕緊從別的工場借個地鼠來幫忙吧。」，最後工場老闆就搞來一個新的地鼠幹活了。
execute，地鼠拿著磚放入火種歡快的燒練起來。

註：「地鼠偷磚」叫work stealing，一種調度演算法。

到這裡，貌似整個工場都正常的運轉起來了，無懈可擊的樣子。不對，還有一個疑點沒解決啊，假設地鼠的車裡有很多磚，它把一塊磚放入火爐中後，何時把它取出來，放入第二塊磚呢？難道要一直把第一塊磚燒練好，才取出來嗎？那估計後面的磚真的是等得花兒都要謝了。這裡就是要真正解決goroutine的調度，上下文切換問題。

#####調度點

當我們翻看channel的實現代碼可以發現，對channel讀寫操作的時候會觸發調用runtime·park函數。goroutine調用park後，這個goroutine就會被設置位waiting狀態，放棄cpu。被park的goroutine處於waiting狀態，並且這個goroutine不在小車(P)中，如果不對其調用runtime·ready，它是永遠不會再被執行的。除了channel操作外，定時器中，網路poll等都有可能park goroutine。

除了park可以放棄cpu外，調用runtime·gosched函數也可以讓當前goroutine放棄cpu，但和park完全不同；gosched是將goroutine設置為runnable狀態，然後放入到調度器全局等待隊列（也就是上面提到的工場倉庫，這下就明白為何工場倉庫會有磚塊(G)了吧）。

除此之外，就輪到系統調用了，有些系統調用也會觸發重新調度。Go語言完全是自己封裝的系統調用，所以在封裝系統調用的時候，可以做不少手腳，也就是進入系統調用的時候執行entersyscall，退出後又執行exitsyscall函數。也只有封裝了entersyscall的系統調用才有可能觸發重新調度，它將改變小車(P)的狀態為syscall。還記一開始提到的sysmon線程嗎？這個系統監控線程會掃描所有的小車(P)，發現一個小車(P)處於了syscall的狀態，就知道這個小車(P)遇到了goroutine在做系統調用，於是系統監控線程就會創建一個新的地鼠(M)去把這個處於syscall的小車給搶過來，開始幹活，這樣這個小車中的所有磚塊(G)就可以繞過之前系統調用的等待了。被搶走小車的地鼠等系統調用返回後，發現自己的車沒，不能繼續幹活了，於是只能把執行系統調用的goroutine放回到工場倉庫，自己睡覺去了。

從goroutine的調度點可以看出，調度器還是挺粗暴的，調度粒度有點過大，公平性也沒有想想的那麼好。總之，這個調度器還是比較簡單的。

#####現場處理

goroutine在cpu上換入換出，不斷上下文切換的時候，必須要保證的事情就是保存現場和恢復現場，保存現場就是在goroutine放棄cpu的時候，將相關寄存器的值給保存到內存中；恢復現場就是在goroutine重新獲得cpu的時候，需要從內存把之前的寄存器信息全部放回到相應寄存器中去。

goroutine在主動放棄cpu的時候(park/gosched)，都會涉及到調用runtime·mcall函數，此函數也是彙編實現，主要將goroutine的棧地址和程序計數器保存到G結構的sched欄位中，mcall就完成了現場保存。恢復現場的函數是runtime·gogocall，這個函數主要在execute中調用，就是在執行goroutine前，需要重新裝載相應的寄存器。

***

人也許總得有一點遺憾才完美

首先你的理解是錯的，不管用戶態的API(syscall)是否是同步還是非同步，在kernel層面都是非同步的。

其實實現原理很簡單，就是利用C(嵌入彙編)語言可以直接修改寄存器(setcontext/setjmp/longjmp均是類似原理，修改程序指針eip實現跳轉，棧指針實現上線文切換)來實現從func_a調進去，從func_b返回出來這種行為。對於golang來說，func_a/func_b屬於不同的goroutine，從而就實現了goroutine的調度切換。

另外對於所有可能阻塞的syscall，golang對其進行了封裝，底層實際是epoll方式做的，註冊回調後切換到另一個runnable的goroutine。

源代碼可參考libtask的實現，golang原理類似：

libtask/asm.S at master 路 llhe/libtask 路 GitHub

libtask/fd.c at master 路 llhe/libtask 路 GitHub

goroutine介於線程和協程之間。go的整個機制象線程池。

一、go 內部有三個對象： P對象(processor) 代表cpu，M(work thread)代表工作線程，G對象（goroutine）.

二、正常情況下一個cpu對象啟一個工作線程對象，線程去檢查並執行goroutine對象。碰到goroutine對象阻塞的時候，會啟動一個新的工作線程，以充分利用cpu資源。所有有時候線程對象會比處理器對象多很多。

三、go大部分棧信息存在goroutine中，線程之間切換速度很快，成本很低（介於線程和協程之間）。

文章首發於：Goroutine 淺析 - 技術分享 - 知乎專欄

並發還是並行

Concurrency is about dealing with lots of things at once. Parallelism is about doing lots of things at once.[1]

並發是在同一時間處理（dealing with）多件事情。
並行是在同一時間做（doing）多件事情。

並發的目的在於把當個 CPU 的利用率使用到最高。並行則需要多核 CPU 的支持。

CSP

Communicating Sequential Processes，譯為通信順序進程。是一種形式語言，用來描述並發系統間進行交互的模式。

例如：

COPY = *[c:character; west?c → east!c]
the process repeatedly receives a character from the process named west, and then sends that character to process named east. The parallel composition
[west::DISASSEMBLE || X::COPY || east::ASSEMBLE]
assigns the names west to the DISASSEMBLE process, X to the COPY process, and east to the ASSEMBLE process, and executes these three processes concurrently.[3]

CSP 通過把輸入和輸出作為編程的基本原語，把順序通信進程的並行組合作為基本方法。通過定義自己的原語，然後用定義好的語法去實現一些常見的問題，比如：協程，數論，經典的同步問題（生產者消費者，哲學家就餐）。

This paper suggests that input and output are basic primitives of programming and that parallel composition of communicating sequential processes is a fundamental program structuring method.[4]

通過 CSP 的定義，使並發編程能在更高的層次實現，編寫的程序不需要關心底層的資源共享、加鎖、調度切換等細節，使並發程序的編寫更簡單。[6]

Go 就是基於 CSP 的思想來實現的並發模型。

Go runtime scheduler

Why need Go scheduler?

主要有兩個原因：

線程較多時，開銷較大。
OS 的調度，程序不可控。而 Go GC 需要停止所有的線程，使內存達到一致狀態。[7]

Struct

M 代表系統線程，G 代表 goroutine，P 代表 context。

M:N

There are 3 usual models for threading. One is N:1 where several userspace threads are run on one OS thread. This has the advantage of being very quick to context switch but cannot take advantage of multi-core systems. Another is 1:1 where one thread of execution matches one OS thread. It takes advantage of all of the cores on the machine, but context switching is slow because it has to trap through the OS.[7]

M:N 則綜合兩種方式（N:1, 1:1）的優勢。多個 goroutines 可以在多個 OS threads 上處理。既能快速切換上下文，也能利用多核的優勢。

Context switch

在程序中任何對系統 API 的調用，都會被 runtime 層攔截來方便調度。

Goroutine 在 system call 和 channel call 時都可能發生阻塞[8]，但這兩種阻塞發生後，處理方式又不一樣的。

當程序發生 system call，M 會發生阻塞，同時喚起（或創建）一個新的 M 繼續執行其他的 G。

If the Go code requires the M to block, for instance by invoking a system call, then another M will be woken up from the global queue of idle M』s. This is done to ensure that goroutines, still capable of running, are not blocked from running by the lack of an available M.[11]

當程序發起一個 channel call，程序可能會阻塞，但不會阻塞 M，G 的狀態會設置為 waiting，M 繼續執行其他的 G。當 G 的調用完成，會有一個可用的 M 繼續執行它。

If a goroutine makes a channel call, it may need to block, but there is no reason that the M running that G should be forced to block as well. In a case such as this, the G』s status is set to waiting and the M that was previously running it continues running other G』s until the channel communication is complete. At that point the G』s status is set back to runnable and will be run as soon as there is an M capable of running it.[11]

P 的作用：

每個 P 都有一個隊列，用來存正在執行的 G。避免 Global Sched Lock。
每個 M 運行都需要一個 MCache 結構。M Pool 中通常有較多 M，但執行的只有幾個，為每個池子中的每個 M 分配一個 MCache 則會形成不必要的浪費，通過把 cache 從 M 移到 P，每個運行的 M 都有關聯的 P，這樣只有運行的 M 才有自己的 MCache。[11]

Goroutine vs OS thread

其實 goroutine 用到的就是線程池的技術，當 goroutine 需要執行時，會從 thread pool 中選出一個可用的 M 或者新建一個 M。而 thread pool 中如何選取線程，擴建線程，回收線程，Go Scheduler 進行了封裝，對程序透明，只管調用就行，從而簡化了 thread pool 的使用。[12]

Goroutine vs Python yield

創建成本：Go 原生支持協程，通過 go func() 就可以創建一個 goroutine。Python 可以通過 gevent.spawn 來新建一個 coroutine，需要第三方庫來支持。
Goroutine 之間的通信更簡單，通過 channel call 即可實現，上下文切換透明（只有少部分需要自己注意 Gosched）。Python 需要 yield 來傳遞數據和切換上下文（通過一些庫封裝後對調用者來說也是透明的，比如：gevent/tornado）。
Python coroutine 只會使用一個線程，所以只能利用單核。Goroutine 可以被多個線程調度，可以利用多核。

References:

[1]Concurrency is not parallelism
[2]並發編程框架背後的實現，goroutine 背後的系統知識
[3]CSP wikipedia
[4]Hoare 的 CSP 論文
[5]Go 對 Hoare CSP 論文中的實例的實現
[6]Why build concurrency on the ideas of CSP?
[7]The Go scheduler
[8]How goroutines work
[9]Goroutines vs OS threads
[10]Why goroutines instead of threads?
[11]Analysis of the Go runtime scheduler
[12]golang 的 goroutine 是如何實現的？ - 知乎

http://www.sizeofvoid.net/goroutine-under-the-hood/

skoo goroutine與調度器

最近在看goroutine方面的知識，說說自己的認識吧，不對請指正。

golang語言並發性極好，原因就是goroutine與channel的配合，能讓我們輕鬆實現高並發服務端程序。

協程可以說是用戶態線程。

要詳細了解協程的出現，應該要說說進程和線程。

簡單地說，進程就是「多任務」操作系統的一個程序，類似於打開一個記事本，本身就打開了一個進程。但是操作系統中執行的任務多於CPU個數，比如記事本寫了一點又想看視頻，看了一會兒視頻又想聽歌，在操作系統中就會進行任務切換，因為每個進程都有一個進程式控制制塊，切換的時候上下文都有保留，所以在哪停下重新執行有在哪開始。

那麼問題就來了，如果進程遇到IO阻塞或者時鐘阻塞，進程讓出CPU資源，頻繁地切換進程上下文，這樣操作系統大部分資源都被進程切換吃掉。這時候線程就出現了，比如：某個進程IO阻塞，我通過切換線程，可以在同一個地址空間做一些其他邏輯流的計算，這樣的切換比進程切換上下文開銷少。

但是，人們總是不滿足的。要是我能夠更細粒度地去控制線程就好了。要是能讓線程的資源分得更細粒度，我能在上面執行成千上萬個函數就好了。所以這時候協程就出現了。所以協程是語言級別實現的。

golang語言實現協程：只需要通過go關鍵字，執行某個函數就可以實現協程。當我們調用go function(x,y,z)運行某個函數並傳入x,y,z三個參數時，golang調度器創建一個協程，具體是調用runtime.newproc將參數大小，新的goroutine所運行的函數以及函數的n個參數傳入。這裡將需要運行函數為function且參數為x,y,z傳入，創建一個棧空間，將棧基址，棧可用空間下界等信息都保存在一個結構體G中，結構體G再關聯到一個隊列中。在Java虛擬機中，某個線程中運行函數也是有這樣的操作，創建一個新的棧空間，每個方法運行方式以棧幀的方式進行調用。

那麼goroutine是如何在語言級別實現的呢？

go語言中有一個負責goroutine運行的調度器。它主要是有結構體G、M、P組成，負責了goroutine的調度。

結構體G:

上面說調用go關鍵字後，將函數等信息保存的地方。

struct G {

uintptr stackguard; // 分段棧可用空間下界

uintptr stackbase; // 分段棧基址(這兩個參數是實現分段棧的關鍵)

Gobuf sched; // 進程切換時，利用sched域保存上下文

FunVal* fnstart; // goroutine運行的函數

void* param; // 函數中使用的參數

int16 status; // goroutine狀態(Gidle,Grunning,Gwaiting等)

int64 goid; // goroutine的id號

M* lockedm; // G被鎖定在這個M上運行

......

};

從源碼可以看到結構體G保存了go function執行的很多信息，那麼可以說執行go關鍵字後，執行的函數被包裝成這樣的結構體G，他的作用就類似與進程式控制制塊，它可以負責控制和管理goroutine的生老病死。

結構體M:

代表真正的OS線程，對機器的抽象，每個M都是對應到一條操作系統的物理線程。

strcut M {

G* g0; // 帶有調度棧的goroutine

G* gsignal; // signal-handling G 處理信號的goroutine

void (*mstartfn)(void);

G* curg; // M中當前運行的goroutine

P* p; // 關聯P以執行Go代碼 (如果沒有執行Go代碼則P為nil)

P* nextp;

int32 id;

int32 mallocing; //狀態

int32 helpgc; //不為0表示此m在做幫忙gc。helpgc等於n只是一個編號

M* alllink; // 這個域用於鏈接allm

M* schedlink;

MCache *mcache;

G* lockedg; // 某些情況下，G鎖定在這個M中運行而不會切換到其它M中去

M* nextwaitm; // next M waiting for lock

GCStats gcstats;

......

};

結構體M中包含了當前運行的G以及關聯的P，還有自己的內存緩存MCache

結構體P:

代表CPU處理器，保存調度上下文，它是實現work-stealing演算法的關鍵，通俗的說就是提高Go語言的並發度。通常P的數量等於CPU核數（GOMAXPROCS）

struct P{

Lock;

uint32 status; // P的狀態

M* m; // 鏈接到它關聯的M

G *gfree; // freelist, P當前運行的runqueue

G *ghead; // runnable, moved from sched

G *gtail;

MCache *mcache; // moved from M

FixAlloc *stackalloc; // moved from M

uint64 ncgocall;

GCStats gcstats;

......

};

那麼他是如何提高Go語言的並發度的呢？

貌似在go version1.1之前，Go語言調度器只存在了結構體G和結構體M，調度是由G與M完成。這樣的問題在於每當創建、終止Goroutine或者需要調度時，需要一個全局的鎖來保護調度的相關對象(sched)。全局鎖嚴重影響Goroutine的並發性能。

之後加入了結構體P，他們三者是如何合作運行的呢？

G需要綁定M才能運行
M需要綁定P才能運行
程序中的多個M並不會同時都處於執行狀態，最多只有GOMAXPROCS個M在執行。可以在程序開始設置。

也就是說 M:P:G = 1:1:N

上圖中的信息：

每一個P都維護了一個G的runqueue2，使用go關鍵字調用創建一個goroutine包裝為G就把他放入P的runqueue中。
當M線程沒有關聯P來運行G時，就需要將G放入全局列表。

work-stealing演算法：

當P中的runqueue裡面的G執行完了之後，他可以從全局列表中獲取，如果全局列表沒有G，那麼此時可以隨機向另一個P的runqueue中偷取一半的G執行，這樣提高了go語言的並發性，同時避免了goroutine調度時的全局鎖。

總結一下：

goroutine就像語言層面上實現的線程，用戶態的線程。

通過go關鍵字--&>調用runtime.newproc將信息傳入並創建新的棧空間--&>包裝為結構體G--&>放入P的runqueue等待執行。

高並發其實就是goroutine在等待執行過程中當前隊列若發生阻塞，可以隨時交由其他線程處理。

最近開始寫一些文章，歡迎關注討論。

go 1.2之前，goroutine只會在兩種情況下被調度:

顯式調用runtime.GoSched()
調用system call

協程一般都是這樣工作的，但是從1.2開始，為了避免餓死其它goroutine，就是在發生任意函數調用的時候，都有機會觸發scheduler。所以從1.2開始如果你的goroutine中是純計算，沒有任何系統調用，scheduler仍然有機會介入，不會永遠獨佔CPU。

前面的人已經說的非常好了，這裡再補充一下 goroutine 是如何切換的。

golang 裡面的 M struct ，也就是系統線程，裡面包含一個 g0，結構如下

type m struct { g0 *g }

也就是說當 goroutine 跑起來的時候除了 G 本身的 stack，M 裡面還有一個 g0 statck，那麼這個 g0 是用來幹嘛的呢？對，就是用來切換的時候保存上下文的。

當 goroutine 切換的時候，M 先將執行棧切換到 g0上，然後將 g 的 context 保存下來。

有圖有真相，看著很到位

在談goroutine之前，我們先談談並發和並行。

一般的程序，如果沒有特別的要求的話，是順序執行的，這樣的程序也容易編寫維護。但是隨著科技的發展、業務的演進，我們不得不變寫可以並行的程序，因為這樣有很多好處。

比如你在看文章的時候，還可以聽著音樂，這就是系統的並行，同時可以做多件事情，充分的利用計算機的多核，提升的軟體運行的性能。

在操作系統中，有兩個重要的概念：一個是進程、一個是線程。當我們運行一個程序的時候，比如你的IDE或者QQ等，操作系統會為這個程序創建一個進程，這個進程包含了運行這個程序所需的各種資源，可以說它是一個容器，是屬於這個程序的工作空間，比如它裡面有內存空間、文件句柄、設備和線程等等。

那麼線程是什麼呢？線程是一個執行的空間，比如要下載一個文件，訪問一次網路等等。線程會被操作系統調用，來在不同的處理器上運行編寫的代碼任務，這個處理器不一定是該程序進程所在的處理。操作系統過的調度是操作系統負責的，不同的操作系統可能會不一樣，但是對於我們程序編寫者來說，不用關心，因為對我們都是透明的。

一個進程在啟動的時候，會創建一個主線程，這個主線程結束的時候，程序進程也就終止了，所以一個進程至少有一個線程，這也是我們在main函數里，使用goroutine的時候，要讓主線程等待的原因，因為主線程結束了，程序就終止了，那麼就有可能會看不到goroutine的輸出。

go語言中並髮指的是讓某個函數獨立於其他函數運行的能力，一個goroutine就是一個獨立的工作單元，Go的runtime（運行時）會在邏輯處理器上調度這些goroutine來運行，一個邏輯處理器綁定一個操作系統線程，所以說goroutine不是線程，它是一個協程，也是這個原因，它是由Go語言運行時本身的演算法實現的。

文章內容比較多，詳細可以參考我寫的這篇文章 Go語言實戰筆記（十二）| Go goroutine

看了上面的回答我的理解就是在機器線程上再虛擬一層線程出來，主要目的還是隱藏底層機器線程的特性。用戶只要對go的線程了解就可以了額

看下libtask的實現，golang的一個合作者寫的！

racket 里有call/cc,

Delimited Continuations

如果了解Python的話，可以看看tornado的[文檔](Tornado Web Server)和[源碼](tornadoweb/tornado · GitHub)，還有就是Python 3.5中新添加的async package。還有就是一個關於用coroutine實現一個os的工程[curio](dabeaz/curio · GitHub)非常棒。

個人覺得，核心點可能類似於libevent或nginx等實現的事件復用機制，其實python也有協程實現。