goroutine調度源碼閱讀筆記
以下為本人閱讀goroutine調度源碼隨手記的筆記，現在還是一個個知識點的形式，暫時還沒整理，先發到這裡，一點點更新：
1). runq [256]guintptr P 的runable隊列最大只能保存256個G
2). 全局的可執行隊列由schedt持有，runq gQueue
3). goroutine 狀態從_Grunning轉為_Grunnable後，解除g與m的關聯，將g放入全局的任務隊列，然後再找到一個新的_Grunable狀態的G來執行
1 func goschedImpl(gp *g) { 2 status := readgstatus(gp) 3 if status&^_Gscan != _Grunning { 4 dumpgstatus(gp) 5 throw("bad g status") 6 } 7 casgstatus(gp, _Grunning, _Grunnable) 8 dropg() 9 lock(&sched.lock) 10 globrunqput(gp) 11 unlock(&sched.lock) 12 13 schedule() 14 }
4). 尋找下一個g來執行的函數 findrunnable 在proc.go:2178
大致分為三大步驟，一是嘗試從本地隊列獲取一個，二是嘗試從全局隊列獲取n個，三是嘗試竊取。這裡要說一下的是：從本地隊列獲取時和從全局隊列獲取時關於並發訪問的控制是不一樣的，從本地隊列獲取的時候，都是通過原子操作來和自旋鎖來實現的，而從全局隊列獲取時，則是通過獲取sched.lock鎖控制的，這是一個全局的排他鎖。
首先嘗試從本地隊列獲取(本地隊列先看runnext是否不為0，如果是，先返回runnext指向的g，否則從隊首彈一個g出來)，如果本地隊列沒有則從全局隊列獲取，如果全局隊列也沒有，就嘗試從其他P的隊列中竊取，但是竊取之前會先做如下幾個判斷：
1. sched.npidle == gomaxprocs – 1 也就是看其他的P是不是都空閑着，如果是的話，就沒必要去竊取了。
2. 2*sched.nmspinning >= gomaxprocs – npidle 當前處於spinning狀態的M的兩倍 大於等於非空閑的P的數量. 翻譯過來就是在正在竊取G的M的數量應該不超過非空閑狀態的P的一半
3. 是否準備執行GC，如果是，就先不竊取了
5).從全局隊列取一部分g到本地隊列的操作。
源碼位置: proc.go:4665 globrunqget (go1.12)
關於取多少個的問題。假設全局隊列一共有t個G，一共有n個P，則，取的數量不超過t / n，並且不超過本隊隊列總長度的一半，目前1.14版本中，本地隊列總長度為256，也就是每次從全局隊列取的G的數量不超過128個.
6).關於選取哪個P進行竊取以及竊取多少個的問題：
源碼位置：proc.go:2238 findrunnable(go1.12)
1. 選取竊取的P
首先一共進行4輪嘗試，每輪都會遍歷所有的P。
另外這裡的遍歷P的過程值得說一下，並不是從下標0位置一個個往後遍歷的，而且跳躍式的遍歷，而且跳躍的步長是隨機出來的。關於步長的選取，算法是這樣的：
首先定義了一個randomOrder結構如下：
type randomOrder struct {
count uint32 // P的數量
coprimes []uint32 // 小於等於count,且與count互質的數(從小到大排列)
}
首先會生成一個與P的數量互質的數的列表，然後隨機出一個數i，遍歷P列表的步長= i % len(coprimes)。開始遍歷的位置=i % nprocs (nproc即P的數量，源碼中是用i對count取模，而count的值是通過randomOrder.reset操作把nprocs賦值給count的).
有意思的是，當第一輪遍歷完了之後，發現一個g都沒拿到，這個時候就會把stealRunNextG的值置為true，這個值表示是否從別的P的runnext竊取，第一輪竊取的時候這個值都為false。（也就是飢不擇食了）
7). 竊取數量
源碼位置: runqgrab proc.go:4858
假設現在P1從P2竊取一部分G。關於竊取多少個G是怎麼定的呢？有以下幾點原則，第一，假設P2的可執行隊列中G的數量為x個，竊取個數n = x – x / 2；第二不得超過P1的可執行隊列(環形buffer)容量的一半,當前最新版本(go1.14)中P的可執行隊列最大容量為256，因此，竊取G的個數不超過128個。
8). 最終沒有找到可執行的G之後發生了什麼
1. 斷開m和p之間的聯繫
2. 把P放進sched.pidle(空閑P的鏈表)
3. 把M的spinning(是否正在獲取可用G)狀態改為false
4. 再次確認一遍所有的P的runq都是空的
5. 嘗試輪訓阻塞事件列表，看看是否有一些G已經轉變為runable狀態.此處獲取到的gList將嘗試空閑的P列表中取一個P出來，然後把gList放進P的runq。而如果沒有空閑的P，那麼將把gList放進全局的runq。
6. 若步驟5仍然沒能獲取到可執行的G，或者步驟5獲取到了G，但是沒有空閑的P，那麼將這部分G放到全局隊列後，M將停止運行，將當前M加入到空閑M列表，然後開始睡眠，直到下一次被喚醒。
9).全局隊列的來源有以下幾種：
1. 輪詢等待隊列，解除等待之後將放入全局隊列
2. 在M上正常執行的g，被切換之後被放入全局隊列
3. 插入新的goroutine時，如果本地隊列已滿，則會將本地隊列的一半取出來，再加上新加入的g，一起放入全局隊列，放入全局隊列前，會將取出來的這個列表隨機打亂順序再放入proc.go:4803(go1.12)
10).一個go程序在64位機上，最小的棧空間大小是2048個位元組，最大的棧空間大小是1G，在32位機上是250M，不過這裡要注意，這裡的1GB並不等於1024M，而是10的9次方位元組，proc.go中有這樣一句話：Using decimal instead of binary GB and MB because they look nicer in the stack overflow failure message.因為看起來更好看。
11).go關鍵字新建一個協程時，傳的參數大小是有限制的，最大是2048個位元組，實際上比這個還要小一點(經測試，參數最大為2000是沒問題的，2001個位元組的時候，會拋出這個錯誤：newproc: function arguments too large for new goroutine.
12).新建G時，不會總是重新分配，而是先嘗試從本地空閑的G 列表裏面取一個，如果本地空閑G列表沒有，則從全局空閑G列表中取，如果都沒取到，就重新分配一個。
13).關於新創建的G會放到哪個P的隊列的問題
以下是runqput函數的注釋，在創建新的G之後，傳入的next始終是true的，所以，新創建的G會放到runnext，因此，新創建的G會在當前的G被換出後，立即執行，不用排隊。
// runqput tries to put g on the local runnable queue.
// If next is false, runqput adds g to the tail of the runnable queue.
// If next is true, runqput puts g in the _p_.runnext slot.
// If the run queue is full, runnext puts g on the global queue.
14). sudog用來保存g的等待隊列，例如channel的發送或接收等待隊列
type sudog struct {
g *g
isSelect bool
next *sudog
prev *sudog
elem unsafe.Pointer // data element (may point to stack)
acquiretime int64
releasetime int64
ticket uint32
parent *sudog // semaRoot binary tree
waitlink *sudog // g.waiting list or semaRoot
waittail *sudog // semaRoot
c *hchan // channel
}
