Go語(yǔ)言——goroutine并發(fā)模型

參考：

創(chuàng)新互聯(lián)公司是一家集網(wǎng)站建設(shè),姚安企業(yè)網(wǎng)站建設(shè),姚安品牌網(wǎng)站建設(shè),網(wǎng)站定制,姚安網(wǎng)站建設(shè)報(bào)價(jià),網(wǎng)絡(luò)營(yíng)銷,網(wǎng)絡(luò)優(yōu)化,姚安網(wǎng)站推廣為一體的創(chuàng)新建站企業(yè)，幫助傳統(tǒng)企業(yè)提升企業(yè)形象加強(qiáng)企業(yè)競(jìng)爭(zhēng)力。可充分滿足這一群體相比中小企業(yè)更為豐富、高端、多元的互聯(lián)網(wǎng)需求。同時(shí)我們時(shí)刻保持專業(yè)、時(shí)尚、前沿，時(shí)刻以成就客戶成長(zhǎng)自我，堅(jiān)持不斷學(xué)習(xí)、思考、沉淀、凈化自己，讓我們?yōu)楦嗟钠髽I(yè)打造出實(shí)用型網(wǎng)站。

Goroutine并發(fā)調(diào)度模型深度解析手?jǐn)]一個(gè)協(xié)程池

Golang 的 goroutine 是如何實(shí)現(xiàn)的？

Golang - 調(diào)度剖析【第二部分】

OS線程初始棧為2MB。Go語(yǔ)言中，每個(gè)goroutine采用動(dòng)態(tài)擴(kuò)容方式，初始2KB，按需增長(zhǎng)，最大1G。此外GC會(huì)收縮?？臻g。

BTW，增長(zhǎng)擴(kuò)容都是有代價(jià)的，需要copy數(shù)據(jù)到新的stack，所以初始2KB可能有些性能問(wèn)題。

更多關(guān)于stack的內(nèi)容，可以參見(jiàn)大佬的文章。 聊一聊goroutine stack

用戶線程的調(diào)度以及生命周期管理都是用戶層面，Go語(yǔ)言自己實(shí)現(xiàn)的，不借助OS系統(tǒng)調(diào)用，減少系統(tǒng)資源消耗。

Go語(yǔ)言采用兩級(jí)線程模型，即用戶線程與內(nèi)核線程KSE（kernel scheduling entity）是M:N的。最終goroutine還是會(huì)交給OS線程執(zhí)行，但是需要一個(gè)中介，提供上下文。這就是G-M-P模型

Go調(diào)度器有兩個(gè)不同的運(yùn)行隊(duì)列：

go1.10\src\runtime\runtime2.go

Go調(diào)度器根據(jù)事件進(jìn)行上下文切換。

調(diào)度的目的就是防止M堵塞，空閑，系統(tǒng)進(jìn)程切換。

詳見(jiàn) Golang - 調(diào)度剖析【第二部分】

Linux可以通過(guò)epoll實(shí)現(xiàn)網(wǎng)絡(luò)調(diào)用，統(tǒng)稱網(wǎng)絡(luò)輪詢器N（Net Poller）。

文件IO操作

上面都是防止M堵塞，任務(wù)竊取是防止M空閑

每個(gè)M都有一個(gè)特殊的G，g0。用于執(zhí)行調(diào)度，gc，棧管理等任務(wù)，所以g0的棧稱為調(diào)度棧。g0的棧不會(huì)自動(dòng)增長(zhǎng)，不會(huì)被gc，來(lái)自os線程的棧。

go1.10\src\runtime\proc.go

G沒(méi)辦法自己運(yùn)行，必須通過(guò)M運(yùn)行

M通過(guò)通過(guò)調(diào)度，執(zhí)行G

從M掛載P的runq中找到G，執(zhí)行G

golang map源碼淺析

golang 中 map的實(shí)現(xiàn)結(jié)構(gòu)為： 哈希表 + 鏈表。 其中鏈表，作用是當(dāng)發(fā)生hash沖突時(shí)，拉鏈法生成的結(jié)點(diǎn)。

可以看到， []bmap 是一個(gè)hash table， 每一個(gè) bmap是我們常說(shuō)的“桶”。 經(jīng)過(guò)hash 函數(shù)計(jì)算出來(lái)相同的hash值， 放到相同的桶中。 一個(gè) bmap中可以存放 8個(gè) 元素， 如果多出8個(gè)，則生成新的結(jié)點(diǎn)，尾接到隊(duì)尾。

以上是只是靜態(tài)文件 src/runtime/map.go 中的定義。 實(shí)際上編譯期間會(huì)給它加料 ，動(dòng)態(tài)地創(chuàng)建一個(gè)新的結(jié)構(gòu)：

上圖就是 bmap的內(nèi)存模型， HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 這樣的形式。源碼里說(shuō)明這樣的好處是在某些情況下可以省略掉 padding 字段，節(jié)省內(nèi)存空間。

每個(gè) bmap設(shè)計(jì)成 最多只能放 8 個(gè) key-value 對(duì) ，如果有第 9 個(gè) key-value 落入當(dāng)前的 bmap，那就需要再構(gòu)建一個(gè) bmap，通過(guò) overflow 指針連接起來(lái)。

map創(chuàng)建方法:

我們實(shí)際上是通過(guò)調(diào)用的 makemap ，來(lái)創(chuàng)建map的。實(shí)際工作只是初始化了hmap中的各種字段，如：設(shè)置B的大小， 設(shè)置hash 種子 hash 0.

注意 :

makemap 返回是*hmap 指針， 即 map 是引用對(duì)象， 對(duì)map的操作會(huì)影響到結(jié)構(gòu)體內(nèi)部 。

使用方式

對(duì)應(yīng)的是下面兩種方法

map的key的類型，實(shí)現(xiàn)了自己的hash 方式。每種類型實(shí)現(xiàn)hash函數(shù)方式不一樣。

key 經(jīng)過(guò)哈希計(jì)算后得到hash值，共 64 個(gè) bit 位。 其中后B 個(gè)bit位置， 用來(lái)定位當(dāng)前元素落在哪一個(gè)桶里， 高8個(gè)bit 為當(dāng)前 hash 值的top hash。 實(shí)際上定位key的過(guò)程是一個(gè)雙重循環(huán)的過(guò)程， 外層循環(huán)遍歷 所有的overflow， 內(nèi)層循環(huán)遍歷 當(dāng)前bmap 中的 8個(gè)元素 。

舉例說(shuō)明： 如果當(dāng)前 B 的值為 5， 那么buckets 的長(zhǎng)度 為 2^5 = 32。假設(shè)有個(gè)key 經(jīng)過(guò)hash函數(shù)計(jì)算后，得到的hash結(jié)果為：

外層遍歷bucket 中的鏈表

內(nèi)層循環(huán)遍歷 bmap中的8個(gè) cell

建議先不看此部分內(nèi)容，看完后續(xù) 修改 map中元素 - 擴(kuò)容 操作后 再回頭看此部分內(nèi)容。

擴(kuò)容前的數(shù)據(jù)：

等量擴(kuò)容后的數(shù)據(jù)：

等量擴(kuò)容后，查找方式和原本相同， 不多做贅述。

兩倍擴(kuò)容后的數(shù)據(jù)

兩倍擴(kuò)容后，oldbuckets 的元素，可能被分配成了兩部分。查找順序如下：

此處只分析 mapaccess1 ,。 mapaccess2 相比 mapaccess1 多添加了是否找到的bool值， 有興趣可自行看一下。

使用方式：

步驟如下：

擴(kuò)容條件 ：

擴(kuò)容的標(biāo)識(shí) ： h.oldbuckets ！= nil

假設(shè)當(dāng)前定位到了新的buckets的3號(hào)桶中，首先會(huì)判斷oldbuckets中的對(duì)應(yīng)的桶有沒(méi)有被搬遷過(guò)。 如果搬遷過(guò)了，不需要看原來(lái)的桶了，直接遍歷新的buckets的3號(hào)桶。

擴(kuò)容前：

等量擴(kuò)容結(jié)果

雙倍擴(kuò)容會(huì)將old buckets上的元素分配到x， y兩個(gè)部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y(tǒng)部分

注意： 當(dāng)前只對(duì)雙倍擴(kuò)容描述， 等量擴(kuò)容只是重新填充了一下元素， 相對(duì)位置沒(méi)有改變。

假設(shè)當(dāng)前map 的B == 5，原本元素經(jīng)過(guò)hash函數(shù)計(jì)算的 hash 值為：

因?yàn)殡p倍擴(kuò)容之后 B = B + 1，此時(shí)B == 6。key 1 B == 1, 即 當(dāng)前元素rehash到高位，新buckets中 y 部分. 否則 key 1 B == 0 則rehash到低位，即x 部分。

使用方式：

可以看到，每一遍歷生成迭代器的時(shí)候，會(huì)隨機(jī)選取一個(gè)bucket 以及 一個(gè)cell開(kāi)始。 從前往后遍歷，再次遍歷到起始位置時(shí)，遍歷完成。

GoLang中的切片擴(kuò)容機(jī)制

[5]int 是數(shù)組，而 []int 是切片。二者看起來(lái)相似，實(shí)則是根本上不同的數(shù)據(jù)結(jié)構(gòu)。

切片的數(shù)據(jù)結(jié)構(gòu)中，包含一個(gè)指向數(shù)組的指針 array ，當(dāng)前長(zhǎng)度 len ，以及最大容量 cap 。在使用 make([]int, len) 創(chuàng)建切片時(shí)，實(shí)際上還有第三個(gè)可選參數(shù) cap ，也即 make([]int, len, cap) 。在不聲明 cap 的情況下，默認(rèn) cap=len 。當(dāng)切片長(zhǎng)度沒(méi)有超過(guò)容量時(shí)，對(duì)切片新增數(shù)據(jù)，不會(huì)改變 array 指針的值。

當(dāng)對(duì)切片進(jìn)行 append 操作，導(dǎo)致長(zhǎng)度超出容量時(shí)，就會(huì)創(chuàng)建新的數(shù)組，這會(huì)導(dǎo)致和原有切片的分離。在下例中

由于 a 的長(zhǎng)度超出了容量，所以切片 a 指向了一個(gè)增長(zhǎng)后的新數(shù)組，而 b 仍然指向原來(lái)的老數(shù)組。所以之后對(duì) a 進(jìn)行的操作，對(duì) b 不會(huì)產(chǎn)生影響。

試比較

本例中， a 的容量為6，因此在 append 后并未超出容量，所以 array 指針沒(méi)有改變。因此，對(duì) a 進(jìn)行的操作，對(duì) b 同樣產(chǎn)生了影響。

下面看看用 a := []int{} 這種方式來(lái)創(chuàng)建切片會(huì)是什么情況。

可以看到，空切片的容量為0，但后面向切片中添加元素時(shí)，并不是每次切片的容量都發(fā)生了變化。這是因?yàn)?，如果增大容量，也即需要?jiǎng)?chuàng)建新數(shù)組，這時(shí)還需要將原數(shù)組中的所有元素復(fù)制到新數(shù)組中，開(kāi)銷很大，所以GoLang設(shè)計(jì)了一套擴(kuò)容機(jī)制，以減少需要?jiǎng)?chuàng)建新數(shù)組的次數(shù)。但這導(dǎo)致無(wú)法很直接地判斷 append 時(shí)是否創(chuàng)建了新數(shù)組。

如果一次添加多個(gè)元素，容量又會(huì)怎樣變化呢？試比較下面兩個(gè)例子：

那么，是不是說(shuō)，當(dāng)向一個(gè)空切片中插入 2n-1 個(gè)元素時(shí)，容量就會(huì)被設(shè)置為 2n 呢？我們來(lái)試試其他的數(shù)據(jù)類型。

可以看到，根據(jù)切片對(duì)應(yīng)數(shù)據(jù)類型的不同，容量增長(zhǎng)的方式也有很大的區(qū)別。相關(guān)的源碼包括： src/runtime/msize.go ， src/runtime/mksizeclasses.go 等。

我們?cè)倏纯辞衅跏挤强盏那樾巍?/p>

可以看到，與剛剛向空切片添加5個(gè)int的情況一致，向有3個(gè)int的切片中添加2個(gè)int，容量增長(zhǎng)為6。

需要注意的是， append 對(duì)切片擴(kuò)容時(shí)，如果容量超過(guò)了一定范圍，處理策略又會(huì)有所不同?？梢钥纯聪旅孢@個(gè)例子。

具體為什么會(huì)是這樣的變化過(guò)程，還需要從 源碼 中尋找答案。下面是 src/runtime/slice.go 中的 growslice 函數(shù)中的核心部分。

GoLang中的切片擴(kuò)容機(jī)制，與切片的數(shù)據(jù)類型、原本切片的容量、所需要的容量都有關(guān)系，比較復(fù)雜。對(duì)于常見(jiàn)數(shù)據(jù)類型，在元素?cái)?shù)量較少時(shí)，大致可以認(rèn)為擴(kuò)容是按照翻倍進(jìn)行的。但具體情況需要具體分析。