翻譯至：[Scalable Go Scheduler Design Doc]--DmitryVyukov (https://docs.google.com/document/d/1TTj4T2JO42uD5ID9e89oa0sLKhJYD0Y_kqxDv3I3XMw/edit#heading=h.mmq8lm48qfcw)
當(dāng)前調(diào)度器的問(wèn)題
??當(dāng)前的goroutine調(diào)度器限制了用go編寫(xiě)編發(fā)程序的可伸縮性,特別是高吞吐量服務(wù)和并行計(jì)算程序。Vtocc (https://github.com/vitessio/vitess]服務(wù)在8核機(jī)子上的最大CPU消耗為70%,profile顯示在runtime.futex()函數(shù)花費(fèi)了14%虑凛。通常翎碑，調(diào)度器會(huì)禁止用戶使用慣用的細(xì)顆粒度的并發(fā)裆甩，這對(duì)性能至關(guān)重要。
目前的實(shí)現(xiàn)存在以下問(wèn)題:
1.單個(gè)全局互斥鎖(
Schd.Lock)和集中的狀態(tài)潘悼。此鎖保護(hù)所有與goroutine有關(guān)的操作(創(chuàng)建律秃，完成，重新調(diào)度等)2.
Goroutine(G)間的交替 (G.nextg)治唤。工作線程(M)頻繁地切換可運(yùn)行的goroutine,這可能導(dǎo)致延遲增加和額外的開(kāi)銷棒动。每個(gè)M必須能夠執(zhí)行任務(wù)可運(yùn)行的G,特別是剛剛創(chuàng)建G的M。- Per-M 內(nèi)存緩存(
M.mcache)宾添。內(nèi)存緩存與其他緩存(堆棧分配)都與所有M相關(guān)聯(lián),而其實(shí)它們只需要與運(yùn)行Go代碼的M相關(guān)聯(lián)(在syscall內(nèi)部阻塞的M其實(shí)并不需要mcache)船惨。 運(yùn)行Go代碼的M與所有M的比率高達(dá)1:100。這導(dǎo)致過(guò)多的資源消耗(每個(gè)MCache最多可以到2M)和槽糕的數(shù)據(jù)局部性辞槐。
- Per-M 內(nèi)存緩存(
- 過(guò)于積極的線程阻塞/解除阻塞掷漱。在系統(tǒng)調(diào)度時(shí),工作線程經(jīng)常被阻塞和解除阻塞。這增加了很多開(kāi)銷榄檬。
設(shè)計(jì)
Processors
??普遍的想法是將P(Processors處理器)的概念引入運(yùn)行時(shí)卜范，并在處理器智之上實(shí)現(xiàn)work-stealing scheduler(工作竊取調(diào)度)http://supertech.csail.mit.edu/papers/steal.pdf程序
??M表示OS線程鹿榜。P表示執(zhí)行Go代碼所需的資源海雪。當(dāng)M執(zhí)行Go代碼時(shí),它有一個(gè)關(guān)聯(lián)的P。
當(dāng)M空閑或在系統(tǒng)調(diào)用時(shí)舱殿，它需要獲取P奥裸。
??我們擁有與GOMAXPROCS 相同數(shù)量的P。所有的P都被組織成一個(gè)數(shù)組沪袭，這是為了實(shí)現(xiàn)work-stealing工作竊取的要求湾宙。GOMAXPROCS 更改設(shè)計(jì) stop/start the world 來(lái)重新調(diào)整P的數(shù)組。來(lái)自sched的一些變量被分散并移動(dòng)到P，來(lái)自M的一些變量也被移動(dòng)到P（與Go代碼的主動(dòng)執(zhí)行相關(guān)的變量）
struct P
{
Lock;
G *gfree; // freelist, moved from sched
G *ghead; // runnable, moved from sched
G *gtail;
MCache *mcache; // moved from M
FixAlloc *stackalloc; // moved from M
uint64 ncgocall;
GCStats gcstats;
// etc
...
};
P *allp; // [GOMAXPROCS]
還有一個(gè)無(wú)鎖的空閑P列表：
P *idlep; // lock-free list
??當(dāng)M開(kāi)始執(zhí)行Go代碼時(shí),必須先從列表中彈出P侠鳄。當(dāng)M結(jié)結(jié)束執(zhí)行Go代碼時(shí)埠啃，它將P塞回列表中。因此伟恶，當(dāng)M執(zhí)行Go代碼時(shí),它必須具有關(guān)聯(lián)的P碴开。這種機(jī)制渠道了sched.atomic(mcpu/mcpumax)
調(diào)度
??當(dāng)創(chuàng)建新的G或G變?yōu)榭蛇\(yùn)行時(shí)，它被塞到當(dāng)前P的可運(yùn)行goroutine列表博秫。當(dāng)P完成執(zhí)行G時(shí)潦牛，它首先嘗試從自己的可運(yùn)行goroutine列表中彈出G;如果列表為空，則P選擇一個(gè)隨機(jī)受害者(另一個(gè)P)并試圖從中竊取一半可運(yùn)行的goroutine挡育。
Syscalls/M 停止和非停止
??當(dāng)M創(chuàng)建一個(gè)新的G時(shí),它必須確保有另一個(gè)M來(lái)執(zhí)行G(如果不是所有的M都處于忙碌)巴碗。類似的，當(dāng)M進(jìn)入系統(tǒng)調(diào)用時(shí)静盅，它必須確保有另一個(gè)M來(lái)執(zhí)行Go代碼良价。
??有兩個(gè)選項(xiàng),我們可以迅速阻止和解鎖M,或采用一些旋轉(zhuǎn)。這是性能跟CPU不必要消耗之間的固有沖突蒿叠。我們的想法是使用旋轉(zhuǎn)并消耗CPU循環(huán)周期明垢。但是，它不應(yīng)該影響使用GOMAXPROCS = 1運(yùn)行的程序（命令行實(shí)用程序市咽，appengine等）痊银。
??旋轉(zhuǎn)分兩個(gè)級(jí)別:(1)一個(gè)關(guān)聯(lián)P的空閑M一直旋轉(zhuǎn)尋找新的G; (2)一個(gè)關(guān)聯(lián)P的w/o M旋轉(zhuǎn)等待可用的P;最多有GOMAXPROCS數(shù)量的旋轉(zhuǎn)M（包括（1）和（2））。當(dāng)存在類型（2）的空閑M時(shí)施绎，類型（1）的空閑M不會(huì)阻塞溯革。
??當(dāng)產(chǎn)生新的G，或者M(jìn)進(jìn)入系統(tǒng)調(diào)用谷醉，或者M(jìn)從空閑轉(zhuǎn)為忙時(shí)致稀，它確保至少有1個(gè)旋轉(zhuǎn)M（或者所有P都忙）。這確保了沒(méi)有可以運(yùn)行的可運(yùn)行的G;并避免同時(shí)過(guò)多的M阻塞/解除阻塞俱尼。
??旋轉(zhuǎn)主要是被動(dòng)的（屈服于OS抖单，sched_yield（）），但可能包括一點(diǎn)點(diǎn)主旋（循環(huán)切換CPU）（需要調(diào)查和調(diào)整）遇八。
終止/死鎖檢測(cè)
??終止/死鎖檢測(cè)在分布式系統(tǒng)中更存在問(wèn)題矛绘。一般的想法是僅在所有P都空閑時(shí)才進(jìn)行檢查（空閑P的全局的原子計(jì)數(shù)器）,這允做一些更昂貴代價(jià)的檢查比如涉及 prep狀態(tài)聚合的檢查。
系統(tǒng)線程鎖
??此功能不是性能關(guān)鍵刃永。
- 鎖定G變?yōu)椴豢蛇\(yùn)行（Gwaiting）货矮。 M立即將P返回到空閑列表，喚醒另一個(gè)M并阻塞斯够。
- 鎖定G變?yōu)榭蛇\(yùn)行（并到達(dá)runq的頭部）囚玫。 當(dāng)前M移出自己的P并將G鎖定到與鎖定的G相關(guān)聯(lián)的M喧锦，并解鎖它。 當(dāng)前的M變得空閑劫灶。
實(shí)施
目標(biāo)是將整個(gè)事物分成可以獨(dú)立審查和提交的最小部分裸违。
- 1.介紹P結(jié)構(gòu); 實(shí)現(xiàn)allp / idlep容器（idlep為啟動(dòng)器提供互斥保護(hù)）; 將P與M運(yùn)行Go代碼相關(guān)聯(lián)。 全局互斥和原子狀態(tài)仍然存在本昏。
- 2.將G freelist移動(dòng)到P.
- 3.將mcache移動(dòng)到P.
- 4.將stackalloc移動(dòng)到P.
- 5.將ncgocall / gcstats移動(dòng)到P.
- 6.分散運(yùn)行隊(duì)列，實(shí)現(xiàn)工作竊取枪汪。 消除G的不可接觸涌穆。 這部分操作仍在全局互斥下。
- 7.刪除全局互斥鎖雀久，實(shí)現(xiàn)分布式終止檢測(cè)宿稀，LockOSThread。
- 8.實(shí)現(xiàn)旋轉(zhuǎn)而不是提示阻止/解除阻塞赖捌。
該計(jì)劃可能會(huì)失效祝沸，有很多未探索的細(xì)節(jié)。
潛在的進(jìn)一步改進(jìn)
- 1.嘗試LIFO調(diào)度越庇，局部上有所提升罩锐。 但是，它仍然必須提供一定程度的公平性卤唉，并優(yōu)雅地處理屈服的goroutines涩惑。
- 2.在goroutine首次運(yùn)行之前，不要分配G和堆棧桑驱。 對(duì)于新創(chuàng)建的goroutine竭恬，我們只需要callerpc，fn熬的，narg痊硕，nret和args，即大約6個(gè)單詞押框。 這將允許創(chuàng)建大量運(yùn)行到完成的goroutine岔绸，顯著降低內(nèi)存開(kāi)銷。
- 4.更好的G-to-P局部性强戴。 嘗試將未阻塞的G排入上一次運(yùn)行的P亭螟。
- P-to-M的更好的局部性。 嘗試在上次運(yùn)行的同一個(gè)M上執(zhí)行P.
- 6.限制M創(chuàng)建骑歹。 調(diào)度程序可以很容易地強(qiáng)制每秒創(chuàng)建數(shù)千M预烙，直到OS拒絕創(chuàng)建更多線程。 必須立即創(chuàng)建M道媚，直到k * GOMAXPROCS扁掸，之后可以通過(guò)計(jì)時(shí)器添加新的M.
其他
- 由于這項(xiàng)工作翘县，GOMAXPROCS不會(huì)消失。
