源碼(chan,map,GMP,mutex,context)
- 2022 年 9 月 5 日
- 筆記
1、chan原理
1.1 chan底層數據結構
概念：go中的channel是一個隊列，遵循先進先出的原則，負責協程之間的通信(go語言提倡不要通過共享內存來通信，而提倡通過通信實現內存共享，CSP模型)
使用場景：
停止信號監聽
定時任務
生產和消費解藕
控制並發數
底層數據結構：
通過var或者make創建的channel變量是一個存儲在函數棧幀上的指針，佔用8個位元組，指向堆上的chan結構體
源碼：src/runtime/chan.map定義了hchan的結構體
環形數組好處：
環形數組消費元素只需要移動下標，普通數組消費元素，需要對剩餘的數據前移
底層hchan結構：
type hchan struct {
qcount uint // 循環數組中元素的數量
dataqsiz uint // 循環數組的長度
buf unsafe.Pointer // 底層緩衝環形數組，有緩衝的channel使用
elemsize uint16 // channel中元素的大小
closed uint32 // channel是否關閉標誌
elemtype *_type // channel中元素的類型
sendx uint // 下一次寫下標的位置
recvx uint // 下一次讀下標的位置
//讀取channel或者寫入channel而被阻塞的goroutine，
//包含頭節點尾節點，記錄哪個協程在等待，等待的是哪個channel,等待接收/發送的數據在哪裡
recvq waitq // 讀等待隊列，
sendq waitq // 寫等待隊列
lock mutex //互斥鎖，保證讀寫channel時不存在並發競爭資源問題
}
//recvq的隊列
type waitq struct {
first *sudog
last *sudog
}
//雙向鏈表
type sudog struct {
g *g
next *sudog
prev *sudog
elem unsafe.Pointer //
acquiretime int64
releasetime int64
ticket uint32
isSelect bool
success bool
parent *sudog // semaRoot binary tree
waitlink *sudog // g.waiting list or semaRoot
waittail *sudog // semaRoot
c *hchan // channel
}
1.2 創建channel原理
創建channel有兩種：1.帶緩衝的channel,2.不帶緩衝的channel
帶緩衝:異步，緩衝區沒有滿之前，不會阻塞
不帶緩衝：同步，寫和讀同步。否則阻塞
ch:=make(chan int,1) //帶緩衝
ch:=make(chan int) //不帶緩衝
創建時的策略：
如果是無緩衝的channel，會直接給hchan分配內存
如果是有緩衝的channel，並且元素不包含指針，那麼會為hchan和底層數組分配一段連續的地址
如果是有緩衝的channel，並且元素包含指針，那麼會為hchan和底層數組分別分配地址
1.3 寫入channel原理
寫入操作，編譯時會調用runtime.chansend函數
ch<-10
1.如果channel的讀等待隊列存在讀的goroutine，將數據直接發送給第一個等待的G,喚醒接收的G。
2.如果channel的寫等待隊列不存在讀的goroutine,
如果循環數組buf未滿，那麼將數據寫入到循環隊列隊尾，sendx++
如果循環數組已滿，這時會阻塞寫入到流程，將當前的G加入寫入等待隊列，並掛起等待喚醒
1.4 讀channel原理
讀操作，編譯時會調用runtime.chanrecv函數
<-ch
v:=<-ch
v,ok:=<-ch
for v:=rang ch{
fmt.println(v)
}
讀出到環形隊列buf成功：recvx++，釋放buf鎖
寫入到環形隊列buf成功：sendx++，釋放buf鎖
原理與寫入相似
1.如果channel的寫等待隊列存在G,
如果是無緩衝的channel，直接從第一個寫的G把數據拷貝給接收的G，喚醒寫入的G,recvx++。
如果是有緩衝的G(循環數組有值),將循環數組的首位元素拷貝給接收的G,recvx++,將第一個寫入的G的數據拷貝到循環數組的隊尾，喚醒寫入的G,sendx++。
如果循環數組為空,這時阻塞讀的G,將當前讀的G加入到讀等待隊列，並掛起等待喚醒
1.5 關閉channel原理
關閉channel,編譯時會調用runtime.closechan函數
close(ch)
1.6 總結
hchan結構體主要組成部分有4個：
1.用來保存讀寫G之間傳遞到數據的環形數組：buf
2.用來記錄此循環數組當前發送或者接收數據的下標值：sendx和recvx
3.用於保存該chan讀和寫阻塞被阻塞的goroutine隊列，sendq和recvq
4.保證channel寫入和讀取數據時線性安全的鎖：lock
2、map原理
2.1存儲結構
hmap:
count:字典健值對個數，len時直接返回count的值
B:創建桶(bmap)的個數，2^B
buckets：當前map中桶(bmap)的數組，2^B
hash0:哈希因子，用於對key生成哈希值。這裡hash值為64位二進制（0101001）
bmap:最多8個元素的健值對
tophash:8個元素數組，存儲key的hash值高8位
keys:8個元素數組，存儲key
values:8個元素數組，存儲value
overflow:指針，當前桶存不下時的溢出桶
2.2初始化原理
info:=make(map[string]string,10) //初始化容量為10的map
第一步：創建hmap結構體對象
第二步：生成一個哈希因子hash0並複製到hmap對象中(用於後續為key創建hash值)
第三步：根據容量=10，根據算法規則創建B，當前B為1
第四步：根據B創建桶(bmap)並存放進buckets數組中,當前bmap數量為2
count/B(桶個數)>6.5,翻倍擴容
B的計算：
hint B bmap(桶)數量
0～8 0 1
9～13 1 2
13～26 2 4
2.3寫入數據原理
info["name"]="Jeff"
在map中寫入數據時，內部執行的流程為：
第一步：結合hash因子和健name生成哈希值，01010101011100011001，64位
第二步：獲取哈希值的後B位,(上面的B在初始化已完成B的運算)，並根據後B位的值來決定此健值對存放在哪個桶(bmap)中。
第三步：在上一步確定桶(bmap)之後，接下來就在桶中寫入數據。獲取哈希值的高8位寫入tophash,將tophash,key,value分別寫到桶中的三個數組中。如果桶已滿，則通過overflow找到溢出桶，並在溢出桶中繼續寫入。
第四步：hmap的個數count++（map中的元素個數+1）
2.4讀取數據原理
name:=info["name"]
在map中讀取數據時，內部的執行流程為：
第一步：結合哈希因子和健name生成哈希值。
第二步：獲取哈希值的後B位，並根據後B位的值來確定將此簡直對存放在哪個桶中(bmap)
第三步：確定桶的位置之後，再根據哈希的高8位(tophash值),根據tophash和key去桶中查找數據。當前桶如果沒有找到，則根據overflow再去溢出桶中找，均未找到則表示key不存在。
根據tophash定位到在數組中的下標索引位置，比如tophash的位置在數組第4位，那麼key和value也都在各自數組的第4位。
2.5map擴容原理
在向map中添加數據時，當達到某個條件，則會引發map擴容。
擴容條件：
1.map中健值對個數(count)/B(bmap桶)個數>6.5，引發翻倍擴容。桶的個數=2^B，所以B+1了
2.使用了太多的溢出桶(溢出桶太多會導致map處理速度降低)
B<=15,已使用的溢出桶個數>=2^B時，引發等量擴容
B>15，已使用的溢出桶個數>=2^15時，引發等量擴容。
2.6map遷移原理
擴容之後，必然要伴隨着數據遷移，即：將舊桶中的數據遷移到新桶中。
2.6.1翻倍擴容遷移原理
如果是翻倍擴容，那麼遷移就是將桶中的數據分流至兩個桶中(比列不定)
如何實現這種遷移呢？其實也很簡單：
首先，我們要知道如果翻倍擴容條件(健值對個數(count)/桶(bmap)個數>6.5)，則新桶個數是舊桶的2倍，即：map中的B值要+1(因為桶的個數等於2^B，而翻倍之後桶的個數就是(2^B)*2,也就是2^(B+1),所以新桶的B值=原桶B+1)
遷移時會遍歷某箇舊桶中的所有key(包括溢出桶),並根據key的hash值的低B位來決定將此健值對分流到哪個新桶中。ps:key的前後hash值都一樣，低B位不一樣。因為B已經+1了
擴容後，B的值在原來的基礎上，也就意味着通過多一位來計算此健值對要分流到新桶的位置，如上圖。
當新增位(紅色)的值為0時，二進制表示的數和原來相同，則數據會遷移到與舊桶的編號一致的位置。
當新增位(紅色)的值為1時，二進制表示的數大一倍，則數據會遷移到翻倍後對應的編號位置。
ps:同一個桶中key的哈希值的低B位一定相同，不然不會放在同一個桶中，所有同一個桶中黃色標記的位置都是相同的。
eg:
舊桶個數為32，翻倍後新桶個數為64。
再重新計算舊桶中的所有key哈希值時，紅色為要能是0或1，所以桶中的所有數據的後B位只能是以下兩種情況：
- 000111 [7],意味着要遷移到與舊桶編號一致的位置
- 100111 [39],意味着會遷移到翻倍後對應編號位置
2.6.2等量擴容遷移原理
如果是等量擴容(溢出桶太多引發的擴容),那麼數據遷移機制就會比較簡單，就是將舊桶(含溢出桶)中的健值對遷移到新桶中。
這種擴容和遷移到意義在於：當溢出桶比較多時，而每個桶中的數據又不多時，可以通過等量擴容和遷移讓數據更緊湊，從而減少溢出桶。
eg:
一個桶中有兩個溢出桶，第一個最開始肯定是滿的，第二個也是滿的，這樣才會創建第三個溢出桶，第三個健值對個數為1。之後刪除操作把第一個桶數據刪了7個，第二個刪了七個。那麼總共健值對只有3個，這時候佔用了3個桶。這時來個等量擴容，讓數據更精湊，把兩個溢出桶的數據放在第一個桶中，這樣就減少了2個溢出桶，從而提升效率
ps:等量擴容B不變哦，這裡的桶數量沒有變化哦。桶的數量=2^B次方
3、GMP原理
3.1調度器的設計策略
調度器的設計策略：
復用線程：避免頻繁的創建，銷毀線程，而是對線程的復用，1.當本地G隊列沒有G時，優先從全局隊列獲取G(從全局獲取G時需要加鎖解鎖），如果全局隊列也沒有，就從其他線程綁定的G隊列偷取G,其他線程的G隊列也沒有獲取到G,就睡眠或者銷毀M 2.當M上正在執行的G阻塞了，此時M釋放綁定的P(P和G隊列還是綁定的),把綁定的P轉移給其他空閑的線程執行。原本的M與G睡眠或者阻塞，當G需要執行時再放進G隊列等待執行。
利用並行：GOMAXPROCS設置P的數量，最多有GOMAXPROCS個線程分佈在多個CPU上同時運行。
搶佔：一個goroutine最多佔用CPU 10ms，防止其他goroutine餓死。
全局G隊列：當創建協程時，優先放入P的本地G隊列，當所有的本地G隊列滿了時,256，放入全局G隊列(需要加鎖解鎖),然後從全局隊列獲取G,當全局隊列沒有G時，從其他P的G隊列偷取G。
ps:P本地G隊列大小為256，本地G滿了才放入全局G隊列
從全局隊列獲取的個數：
GQ：全局隊列G的總長度 n=min(len(GQ)/GOMAXPROCS+1,len(GQ/2))
3.2執行go func()調度流程原理
第一步：執行go func()
第二步：創建一個G,優先加入到當前協程的G隊列(如果是這個協程執行的)，如果本地隊列滿了，則把G加入到全局隊列。
第三步：P需要調度一個G給M執行，P優先從本地G隊列獲取一個G,如果本地隊列沒有G,則從其他P綁定的G偷取一個G來執行，如果其他隊列也沒有G,則從全局隊列獲取一個G執行。
第四步：M調度執行G,如果執行到G.func發送阻塞，那麼M和P解綁，把P轉移給其他的M執行。當G阻塞完了，M放入休眠M隊列或者銷毀，G尋找其他G隊列，或者放入全局G隊列，等待下次調度
ps:休眠隊列中長期沒有被喚醒，則被GC回收了
3.3一個G創建很多G的過程原理
首先：假設G的隊列大小為4(實際為256),一個goroutine創建了8個goroutine
此時G隊列已經放滿了，再創建G7時，會把G的前半部分連同G7打亂一起放入全局隊列
此時G隊列G5,G6往前移，已經空了一半。再創建G8,會把G8直接加入G隊列
3.4喚醒正在休眠的M原理
規定：在創建G時，運行的G會嘗試喚醒其他空閑的P和M組合去執行，從休眠的M隊列喚醒M
假定G2喚醒了M2,M2綁定了P2,並運行Go，單P2本地隊列沒有G,M2此時稱為：自旋線程,會優先去全局隊列獲取G,全局隊列沒有，才會去其他P的G隊列偷取G來執行
從全局隊列獲取的個數：
GQ：全局隊列G的總長度 n=min(len(GQ)/GOMAXPROCS+1,len(GQ/2))
3.5被喚醒的M從全局G隊列取G原理
規定：在創建G時，運行的G會嘗試喚醒其他空閑的P和M組合去執行，從休眠的M隊列喚醒M
假定G2喚醒了M2,M2綁定了P2,並運行G，單P2本地隊列沒有G,M2此時稱為：自旋線程,會優先去全局隊列獲取G,全局隊列沒有，才會去其他P的G隊列偷取G來執行
從全局隊列獲取的個數：
GQ：全局隊列G的總長度 n=min(len(GQ)/GOMAXPROCS+1,len(GQ/2))
ps:偷到G了，就不是自旋線程了
3.6M2從M1中偷取G原理
偷取條件：全局隊列沒有G了，就會從其他P的G隊列偷取G.
偷取G的數量：其他P的G隊列數量/2，取隊列的後半部分全偷過來。
3.7自旋線程的最大限制
M的數量=GOMAXPROCS
自旋線程M+執行線程M<=GOMAXPROCS
3.8G發送阻塞時，調度原理
M調度執行G,如果執行到G.func發送阻塞，那麼M和P解綁，把P轉移給其他的M執行。當G阻塞完了，M放入休眠M隊列或者銷毀，G尋找其他G隊列，或者放入全局G隊列，等待下次調度
假設G8阻塞，則G8停留在M2當前系統空間中，因為此時M2全部的堆棧信息都在為G8服務，所以M2不能再為P2服務，所以M2與P2解綁，P2自行去尋找一個M來綁定。先尋找休眠M隊列，如果沒有則把P放進空閑P隊列，等待其他M來調度。
ps：P2為什麼不綁定M3,M4?因為M3,M4是自旋線程，此時已經擁有P了。自旋線程是尋找G的
3.9G阻塞完之後，調度原理
G阻塞完之後：
第一步：M2會找P2(原配),發現P2已經被其他M綁定了
第二步：去找空閑P隊列，沒找到
第三步：M2和G2解綁，G2放入全局G隊列，等待其他P調用
第四步：M2放入休眠隊列
ps:休眠隊列中長期沒有被喚醒，則被GC回收了
4、mutex原理
4.1mutex結構體解析
type Mutex Struct{
state int32 // 互斥鎖的狀態，原子操作actomic包操作該字段
sema uint32 // 信號量，等待隊列
}
state：表示互斥鎖的狀態，後三位表示鎖的狀態，其他表示等待的goroutine數量。
sema表示信號量，協程阻塞等待該信號量來喚醒協程，解鎖的協程釋放該信號量來喚醒阻塞的協程
Locked:表示mutex是否已經鎖定。1：鎖定。 0：沒有鎖定
Woken:表示是否有協程已被喚醒，0：沒有協程喚醒。1：有協程喚醒，正在加鎖過程中
Starving:表示該mutex是否處於飢餓狀態。0：正常模式。1：飢餓模式，表示有協程已經阻塞超過1ms
Waiter:等待等待加鎖的G的隊列個數(自旋之後未搶到鎖會加入到此隊列)，協程解鎖時根據此值來判斷是否需要釋放信號量
4.2正常模式工作原理
首先mutex有兩種狀態：正常模式，飢餓模式
一個加鎖的goroutine搶鎖過程
第一步：首先G進入自旋狀態(最多4次自旋),嘗試通過mutex的原子操作獲得鎖
第二步：若幾次自旋之後仍沒有獲得鎖，則通過信號量排隊等待。所有的等待的G都會按照先入先出的順序排隊
第三步：當鎖被釋放，通過信號量喚醒第一個排隊等待的G,但是第一個等待的G不會直接擁有鎖。而是需要和所有(很多個G)處於自旋狀態的G競爭，這種情況後來的進入自旋狀態的G更容易獲得鎖，因為正在CPU上執行，比剛被喚醒的G(自旋沒有獲得鎖，排隊等待的G)更有優勢，所以被喚醒的G大概率不會搶到鎖，此時把這個G再次放入等待隊列的頭部。
第四步：當等待隊列的G獲取鎖的時間大於1ms時，鎖會進入飢餓模式
ps:正常模式自旋和排隊並行更夠有更高的吞吐量，因為頻繁的掛起和喚醒G會帶來較多的開銷，但是又不能無限制的自旋，要把開銷控制在較小的範圍內。所以在正常模式下mutex有更好的性能，但是隊列尾端的G遲遲搶不到鎖。飢餓模式所有的G都需要排隊。
4.3飢餓模式工作原理
首先mutex有兩種狀態：正常模式，飢餓模式
ps:搶鎖先自旋，自旋沒搶到進入隊列，隊列頭部G喚醒再次搶鎖，搶鎖時間大於1ms鎖進入飢餓模式
飢餓模式搶鎖過程：
第一步：一個協程解鎖，釋放信號量
第二步：通過信號量喚醒等待隊列頭部第一個G直接獲得鎖，後來的G不會自旋，也不會嘗試獲得鎖,而是直接加入到隊列尾部等待。（先把鎖給等待時間大於1ms的G）
飢餓模式切換到正常模式：
1.頭部的G等待的時間小於1ms，鎖進入正常模式
2.等待隊列已經空了(隊列空了，自然沒有飢餓的G了)，鎖進入正常模式
4.4搶鎖/解鎖的代碼原理
搶鎖：
第一步：通過原子操作CASInt32對鎖的最後一位狀態賦值，賦值成功代表搶到鎖。
第二步：沒有搶到鎖(賦值失敗)，進入m.lockSlow(),讓此協程進入等待隊列，並休眠
ps: 原子操作CASInt32：類似樂觀鎖，先判斷這個鎖的狀態是否為0，是0就改變為1，否則不變。
解鎖：
第一步：通過原子操作atomic.AddInt32把鎖的狀態值設置為0。
第二步：判斷new!=0，證明有協程在隊列等待，需要釋放信號喚醒一個協程
func demo() {
var state int32 = 2001
ne := atomic.AddInt32(&state, -1)
fmt.Println(ne) //2000,2表示有兩個G在隊列等待，0表示正常模式，0沒有協程喚醒，0當前鎖沒有被佔用
}
5、context原理
5.1context結構體
type Context interface {
Deadline() (deadline time.Time, ok bool)
Done() <-chan struct{}
Err() error
Value(key interface{}) interface{}
}
Deadline:返回綁定當前context的任務被取消的截止時間；如果沒有設定期限，將返回ok == false。
Done:信號，當綁定當前context的任務被取消時，將返回一個關閉的channel信號；如果當前context不會被取消，將返回nil。
Err:
1.如果Done返回的channel沒有關閉，將返回nil;
2.如果Done返回的channel已經關閉，將返回非空的值表示任務結束的原因。
3.如果是context被取消，Err將返回Canceled；
4.如果是context超時，Err將返回DeadlineExceeded。
Value:返回context存儲的鍵值對中當前key對應的值，如果沒有對應的key,則返回nil。
5.2context核心原理
context包的核心原理：鏈式傳遞context，基於context構造新的context
核心接口：
ctx,err:=context.Background() //通常用於主函數，初始化以及測試，作為頂層的context
ctx:=context.TODO() //不確定使用什麼用context的時候才會使用
ctx:=context.WithValue(context.Background(),"name","jeff")//向context添加鍵值
name := ctx.Value("name") //向context取值
ctx, cancel := context.WithCancel(context.Background()) //可取消的contex，調用cancel()取消，取消之後 <-ctx.Done()可以被觸發，用於監聽
監聽ctx有沒有被關閉
func waitCancel(ctx context.Context, i int) {
for {
time.Sleep(time.Second)
select {
case <-ctx.Done():
fmt.Printf("%d end\n", i)
return
default:
fmt.Printf("%d do\n", i)
}
}
}
OSI7層協議
websocket
http
udp
tcp
內存逃逸
棧：由系統申請和釋放，不會有額外的性能開銷。比如局部變量
堆：在堆上的內存需要GC管理回收，GC將帶來額外的性能開銷。
內存逃逸：由棧逃逸到堆
逃逸條件：變量在函數結束時，仍然想要使用這個變量。比如全局變量
逃逸機制：
編輯器會根據變量是否被外部引用來決定是否逃逸：
1.如果函數外部沒有引用，則優先放到棧中
2.如果函數外部存在引用，則必定放在堆中
3.如果棧放不下，則必定放在堆上
總結：
1.棧上分配內存比堆中分配內存效率更高
2.棧上分配的內存不需要GC處理，因為函數結束就自動釋放了。而堆需要GC處理
3.逃逸分析的目的是決定內存分配地址是堆還是棧
4.逃逸分析是在編譯階段完成
因為無論變量的大小，只要是指針變量都會在堆上分配，所以對於小變量我們還是使用值傳遞效率更高，因為指針傳遞會分配到堆，會增加GC的壓力
