golang分金幣演算法,GoGo幣

本文目錄一覽：

• 1、手擼golang 基本數據結構與演算法 圖的搜索 深度優先/廣度優先
• 2、【golang詳解】go語言GMP(GPM)原理和調度
• 3、Golang的垃圾回收
• 4、golang變數(二)——map和slice詳解
• 5、golang面試題2之判斷字元串中字元是否全都不同
• 6、（十一）golang 內存分析

手擼golang 基本數據結構與演算法 圖的搜索 深度優先/廣度優先

最近閱讀我的第一本演算法書(【日】石田保輝；宮崎修一)

本系列筆記擬採用golang練習之

graph_visit_test.go

頂點介面

圖的遍歷器介面

頂點的實現

候選節點隊列介面. 候選節點的選擇方式不同, 決定了是深度優先還是廣度優先.

LIFO堆棧, 實現INodeQueue介面

FIFO隊列, 實現INodeQueue介面

遍歷器, 實現IGraphVisitor介面

(end)

【golang詳解】go語言GMP(GPM)原理和調度

Goroutine調度是一個很複雜的機制，下面嘗試用簡單的語言描述一下Goroutine調度機制，想要對其有更深入的了解可以去研讀一下源碼。

首先介紹一下GMP什麼意思：

G ———– goroutine: 即Go協程，每個go關鍵字都會創建一個協程。

M ———- thread內核級線程，所有的G都要放在M上才能運行。

P ———– processor處理器，調度G到M上，其維護了一個隊列，存儲了所有需要它來調度的G。

Goroutine 調度器P和 OS 調度器是通過 M 結合起來的，每個 M 都代表了 1 個內核線程，OS 調度器負責把內核線程分配到 CPU 的核上執行

模型圖：

避免頻繁的創建、銷毀線程，而是對線程的復用。

1）work stealing機制

  當本線程無可運行的G時，嘗試從其他線程綁定的P偷取G，而不是銷毀線程。

2）hand off機制

  當本線程M0因為G0進行系統調用阻塞時，線程釋放綁定的P，把P轉移給其他空閑的線程執行。進而某個空閑的M1獲取P，繼續執行P隊列中剩下的G。而M0由於陷入系統調用而進被阻塞，M1接替M0的工作，只要P不空閑，就可以保證充分利用CPU。M1的來源有可能是M的緩存池，也可能是新建的。當G0系統調用結束後，根據M0是否能獲取到P，將會將G0做不同的處理：

如果有空閑的P，則獲取一個P，繼續執行G0。

如果沒有空閑的P，則將G0放入全局隊列，等待被其他的P調度。然後M0將進入緩存池睡眠。

如下圖

GOMAXPROCS設置P的數量，最多有GOMAXPROCS個線程分布在多個CPU上同時運行

在Go中一個goroutine最多佔用CPU 10ms，防止其他goroutine被餓死。

具體可以去看另一篇文章

【Golang詳解】go語言調度機制 搶佔式調度

當創建一個新的G之後優先加入本地隊列，如果本地隊列滿了，會將本地隊列的G移動到全局隊列裡面，當M執行work stealing從其他P偷不到G時，它可以從全局G隊列獲取G。

協程經歷過程

我們創建一個協程 go func()經歷過程如下圖：

說明：

這裡有兩個存儲G的隊列，一個是局部調度器P的本地隊列、一個是全局G隊列。新創建的G會先保存在P的本地隊列中，如果P的本地隊列已經滿了就會保存在全局的隊列中；處理器本地隊列是一個使用數組構成的環形鏈表，它最多可以存儲 256 個待執行任務。

G只能運行在M中，一個M必須持有一個P，M與P是1：1的關係。M會從P的本地隊列彈出一個可執行狀態的G來執行，如果P的本地隊列為空，就會想其他的MP組合偷取一個可執行的G來執行；

一個M調度G執行的過程是一個循環機制；會一直從本地隊列或全局隊列中獲取G

上面說到P的個數默認等於CPU核數，每個M必須持有一個P才可以執行G，一般情況下M的個數會略大於P的個數，這多出來的M將會在G產生系統調用時發揮作用。類似線程池，Go也提供一個M的池子，需要時從池子中獲取，用完放回池子，不夠用時就再創建一個。

work-stealing調度演算法：當M執行完了當前P的本地隊列隊列里的所有G後，P也不會就這麼在那躺屍啥都不幹，它會先嘗試從全局隊列隊列尋找G來執行，如果全局隊列為空，它會隨機挑選另外一個P，從它的隊列里中拿走一半的G到自己的隊列中執行。

如果一切正常，調度器會以上述的那種方式順暢地運行，但這個世界沒這麼美好，總有意外發生，以下分析goroutine在兩種例外情況下的行為。

Go runtime會在下面的goroutine被阻塞的情況下運行另外一個goroutine：

用戶態阻塞/喚醒

當goroutine因為channel操作或者network I/O而阻塞時（實際上golang已經用netpoller實現了goroutine網路I/O阻塞不會導致M被阻塞，僅阻塞G，這裡僅僅是舉個栗子），對應的G會被放置到某個wait隊列(如channel的waitq)，該G的狀態由_Gruning變為_Gwaitting，而M會跳過該G嘗試獲取並執行下一個G，如果此時沒有可運行的G供M運行，那麼M將解綁P，並進入sleep狀態；當阻塞的G被另一端的G2喚醒時（比如channel的可讀/寫通知），G被標記為，嘗試加入G2所在P的runnext（runnext是線程下一個需要執行的 Goroutine。）， 然後再是P的本地隊列和全局隊列。

系統調用阻塞

當M執行某一個G時候如果發生了阻塞操作，M會阻塞，如果當前有一些G在執行，調度器會把這個線程M從P中摘除，然後再創建一個新的操作系統的線程(如果有空閑的線程可用就復用空閑線程)來服務於這個P。當M系統調用結束時候，這個G會嘗試獲取一個空閑的P執行，並放入到這個P的本地隊列。如果獲取不到P，那麼這個線程M變成休眠狀態， 加入到空閑線程中，然後這個G會被放入全局隊列中。

隊列輪轉

可見每個P維護著一個包含G的隊列，不考慮G進入系統調用或IO操作的情況下，P周期性的將G調度到M中執行，執行一小段時間，將上下文保存下來，然後將G放到隊列尾部，然後從隊列中重新取出一個G進行調度。

除了每個P維護的G隊列以外，還有一個全局的隊列，每個P會周期性地查看全局隊列中是否有G待運行並將其調度到M中執行，全局隊列中G的來源，主要有從系統調用中恢復的G。之所以P會周期性地查看全局隊列，也是為了防止全局隊列中的G被餓死。

除了每個P維護的G隊列以外，還有一個全局的隊列，每個P會周期性地查看全局隊列中是否有G待運行並將其調度到M中執行，全局隊列中G的來源，主要有從系統調用中恢復的G。之所以P會周期性地查看全局隊列，也是為了防止全局隊列中的G被餓死。

M0

M0是啟動程序後的編號為0的主線程，這個M對應的實例會在全局變數rutime.m0中，不需要在heap上分配，M0負責執行初始化操作和啟動第一個G，在之後M0就和其他的M一樣了

G0

G0是每次啟動一個M都會第一個創建的goroutine，G0僅用於負責調度G，G0不指向任何可執行的函數，每個M都會有一個自己的G0，在調度或系統調用時會使用G0的棧空間，全局變數的G0是M0的G0

一個G由於調度被中斷，此後如何恢復？

中斷的時候將寄存器里的棧信息，保存到自己的G對象裡面。當再次輪到自己執行時，將自己保存的棧信息複製到寄存器裡面，這樣就接著上次之後運行了。

我這裡只是根據自己的理解進行了簡單的介紹，想要詳細了解有關GMP的底層原理可以去看Go調度器 G-P-M 模型的設計者的文檔或直接看源碼

參考： ()

()

Golang的垃圾回收

最近垃圾分類的話題熱度一下子就上去了，很多人因為垃圾分類的問題很頭痛。因為垃圾這個話題，那我就想來說說Golang裡面的垃圾，於是就有了這篇博客，golang中的垃圾回收。

現階段網上針對golang垃圾回收的解析已經很多了，所以我也沒有必要仔仔細細的一點點說，還是那個原則，用最直白的話告訴你，垃圾到底是怎麼收的。

首先本文後續都會使用 GC 代替垃圾回收這幾個字。

我們知道創建對象會給他分配內存資源，如果這個對象不使用了，而這個內存資源卻一直被佔用的話，那麼我們的電腦很快就會被放滿，所以需要將這些垃圾對象進行回收。

要回收，那麼我們必須知道什麼才是垃圾，什麼不是垃圾。

在我們看來，一個對象以後都不用了，就是垃圾。

在程序看來，一個對象沒有被引用了，就是垃圾。

首先說明一下，下面說的停，都是STW，stop the world，全世界暫停，所有運行的都停下來了。

先告訴所有人，停一下，我來記錄一下當前狀態。

告訴所有人，你們繼續，該幹嘛幹嘛，我標記一下要用的對象

一開始所有點是白色，首先從根節點出發，標記相連的點為灰色（相連證明有引用），並且將所有灰色的點存起來；

告訴所有人，再停一下，在第二個過程中，因為所有人繼續在工作，那麼就會產生新的垃圾，因為第一個過程記錄了狀態，所以需要標記一下新的垃圾；然後清除所有白色的點，因為白色的點是沒人引用的，也就是垃圾。

你一定會有這樣的疑問：

那麼既然會導致那麼多問題，為什麼不直接停下來，標記完回收完了再開始呢？

因為慢~

所以這樣GC的原因是既要保證GC正常執行，又要保證效率，不能停的時間太長。

其實第一次停的時候，啟動了一個寫屏障 (write barrier)它需要記錄後續過程中新創建的對象

這個過程稱為三色標記，有點類似廣度優先搜索。

這次是必須停，因為在第二個過程中引用會發生變化，從而需要停止後重新掃描一遍；然後關閉寫屏障，最後再清理。

開啟寫屏障時需要stw

關閉寫屏障前需要stw

開啟寫屏障之後的標記過程與其他程序並發執行

關閉寫屏障之後的清掃過程與其他程序並發執行

那畢竟GC還是需要STW的，雖然可能停止時間很短，但是對於程序來說，整個程序停止1秒那對於用戶來說就是致命打擊。所以GC肯定需要一個觸發的條件，不能想來就來。

這是一個觸發的條件，默認GC百分比設置的是100，意思是，如果這次回收之後總共佔用2M的內存，那麼下次觸發的條件時當超過4M的時候；同理，當這次回收之後總共佔用4M，那麼下次觸發條件就是8M。

這個簡單，當一定時間（2分鐘）沒有執行過GC就觸發GC

使用命令 runtime.GC() 手動觸發GC

以上就是在golang中垃圾回收的大致流程，總的來說使用三色標記法進行標記清除，並且標記時與程序運行並行，為了解決問題使用寫屏障來記錄標記過程中對象的變更。總來的來說也是為了提高垃圾回收的效率，並且儘可能的減少STW的時間。

了解下來，與java的分代回收相比，golang中的回收演算法理解起來更加簡單一些。

golang變數(二)——map和slice詳解

衍生類型，interface{} , map, [] ，struct等

map類似於java的hashmap，python的dict，php的hash array。

常規的for循環，可以用for k,v :=range m {}. 但在下面清空有一個坑注意：

著名的map[string]*struct 副本問題

結果：

Go 中不存在引用傳遞，所有的參數傳遞都是值傳遞，而map是等同於指針類型的，所以在把map變數傳遞給函數時，函數對map的修改，也會實質改變map的值。

slice類似於其他語言的數組（list，array），slice初始化和map一樣，這裡不在重複

除了Pointer數組外，len表示使用長度，cap是總容量，make([]int, len, cap)可以預申請 比較大的容量，這樣可以減少容量拓展的消耗，前提是要用到。

cap是計算切片容量，len是計算變數長度的，兩者不一樣。具體例子如下：

結果：

分析：cap是計算當前slice已分配的容量大小，採用的是預分配的夥伴演算法（當容量滿時，拓展分配一倍的容量）。

append是slice非常常用的函數，用於添加數據到slice中，但如果使用不好，會有下面的問題：

預期是[1 2 3 4 5 6 7 8 9 10]， [1 2 3 4 5 6 7 8 9 10 11 12]，但實際結果是：

注意slice是值傳遞，修改一下：

輸出如下：

== 只能用於判斷常規數據類型，無法使用用於slice和map判斷，用於判斷map和slice可以使用reflect.DeepEqual，這個函數用了遞歸來判斷每層的k，v是否一致。

當然還有其他方式，比如轉換成json，但小心有一些異常的bug，比如html編碼，具體這個json問題，待後面在分析。

golang面試題2之判斷字元串中字元是否全都不同

請實現 個演算法，確定 個字元串的所有字元【是否全都不同】。這 我們要求【不允

許使 額外的存儲結構】。 給定 個string，請返回 個bool值,true代表所有字元全都

不同，false代表存在相同的字元。 保證字元串中的字元為【ASCII字元】。字元串的

度 於等於【3000】。

這 有 個重點，第 個是 ASCII字元 ， ASCII字元 字元 共有256個，其中128個是常

字元，可以在鍵盤上輸 。128之後的是鍵盤上 法找到的。

然後是全部不同，也就是字元串中的字元沒有重複的，再次，不準使 額外的儲存結

構，且字元串 於等於3000。

如果允許其他額外儲存結構，這個題 很好做。如果不允許的話，可以使 golang內置

的 式實現。

通過 strings.Count 函數判斷：

使 的是golang內置 法 strings.Count ,可以 來判斷在 個字元串中包含

的另外 個字元串的數量

還有不同的方法同樣可以實現，你了解嗎?

推薦go相關技術 專欄

gRPC-go源碼剖析與實戰_帶你走進gRPC-go的源碼世界-CSDN博客

（十一）golang 內存分析

編寫過C語言程序的肯定知道通過malloc()方法動態申請內存，其中內存分配器使用的是glibc提供的ptmalloc2。 除了glibc，業界比較出名的內存分配器有Google的tcmalloc和Facebook的jemalloc。二者在避免內存碎片和性能上均比glic有比較大的優勢，在多線程環境中效果更明顯。

Golang中也實現了內存分配器，原理與tcmalloc類似，簡單的說就是維護一塊大的全局內存，每個線程(Golang中為P)維護一塊小的私有內存，私有內存不足再從全局申請。另外，內存分配與GC（垃圾回收）關係密切，所以了解GC前有必要了解內存分配的原理。

為了方便自主管理內存，做法便是先向系統申請一塊內存，然後將內存切割成小塊，通過一定的內存分配演算法管理內存。 以64位系統為例，Golang程序啟動時會向系統申請的內存如下圖所示：

預申請的內存劃分為spans、bitmap、arena三部分。其中arena即為所謂的堆區，應用中需要的內存從這裡分配。其中spans和bitmap是為了管理arena區而存在的。

arena的大小為512G，為了方便管理把arena區域劃分成一個個的page，每個page為8KB,一共有512GB/8KB個頁；

spans區域存放span的指針，每個指針對應一個page，所以span區域的大小為(512GB/8KB)乘以指針大小8byte = 512M

bitmap區域大小也是通過arena計算出來，不過主要用於GC。

span是用於管理arena頁的關鍵數據結構，每個span中包含1個或多個連續頁，為了滿足小對象分配，span中的一頁會劃分更小的粒度，而對於大對象比如超過頁大小，則通過多頁實現。

根據對象大小，劃分了一系列class，每個class都代表一個固定大小的對象，以及每個span的大小。如下表所示：

上表中每列含義如下：

class： class ID，每個span結構中都有一個class ID, 表示該span可處理的對象類型

bytes/obj：該class代表對象的位元組數

bytes/span：每個span佔用堆的位元組數，也即頁數乘以頁大小

objects: 每個span可分配的對象個數，也即（bytes/spans）/（bytes/obj）waste

bytes: 每個span產生的內存碎片，也即（bytes/spans）%（bytes/obj）上表可見最大的對象是32K大小，超過32K大小的由特殊的class表示，該class ID為0，每個class只包含一個對象。

span是內存管理的基本單位,每個span用於管理特定的class對象, 跟據對象大小，span將一個或多個頁拆分成多個塊進行管理。src/runtime/mheap.go:mspan定義了其數據結構：

以class 10為例，span和管理的內存如下圖所示：

spanclass為10，參照class表可得出npages=1,nelems=56,elemsize為144。其中startAddr是在span初始化時就指定了某個頁的地址。allocBits指向一個點陣圖，每位代表一個塊是否被分配，本例中有兩個塊已經被分配，其allocCount也為2。next和prev用於將多個span鏈接起來，這有利於管理多個span，接下來會進行說明。

有了管理內存的基本單位span，還要有個數據結構來管理span，這個數據結構叫mcentral，各線程需要內存時從mcentral管理的span中申請內存，為了避免多線程申請內存時不斷的加鎖，Golang為每個線程分配了span的緩存，這個緩存即是cache。src/runtime/mcache.go:mcache定義了cache的數據結構

alloc為mspan的指針數組，數組大小為class總數的2倍。數組中每個元素代表了一種class類型的span列表，每種class類型都有兩組span列表，第一組列表中所表示的對象中包含了指針，第二組列表中所表示的對象不含有指針，這麼做是為了提高GC掃描性能，對於不包含指針的span列表，沒必要去掃描。根據對象是否包含指針，將對象分為noscan和scan兩類，其中noscan代表沒有指針，而scan則代表有指針，需要GC進行掃描。mcache和span的對應關係如下圖所示：

mchache在初始化時是沒有任何span的，在使用過程中會動態的從central中獲取並緩存下來，跟據使用情況，每種class的span個數也不相同。上圖所示，class 0的span數比class1的要多，說明本線程中分配的小對象要多一些。

cache作為線程的私有資源為單個線程服務，而central則是全局資源，為多個線程服務，當某個線程內存不足時會向central申請，當某個線程釋放內存時又會回收進central。src/runtime/mcentral.go:mcentral定義了central數據結構：

lock: 線程間互斥鎖，防止多線程讀寫衝突

spanclass : 每個mcentral管理著一組有相同class的span列表

nonempty: 指還有內存可用的span列表

empty: 指沒有內存可用的span列表

nmalloc: 指累計分配的對象個數線程從central獲取span步驟如下：

將span歸還步驟如下：

從mcentral數據結構可見，每個mcentral對象只管理特定的class規格的span。事實上每種class都會對應一個mcentral,這個mcentral的集合存放於mheap數據結構中。src/runtime/mheap.go:mheap定義了heap的數據結構：

lock： 互斥鎖

spans: 指向spans區域，用於映射span和page的關係

bitmap：bitmap的起始地址

arena_start: arena區域首地址

arena_used: 當前arena已使用區域的最大地址

central: 每種class對應的兩個mcentral

從數據結構可見，mheap管理著全部的內存，事實上Golang就是通過一個mheap類型的全局變數進行內存管理的。mheap內存管理示意圖如下：

系統預分配的內存分為spans、bitmap、arean三個區域，通過mheap管理起來。接下來看內存分配過程。

針對待分配對象的大小不同有不同的分配邏輯：

(0, 16B) 且不包含指針的對象： Tiny分配

(0, 16B) 包含指針的對象：正常分配

[16B, 32KB] : 正常分配

(32KB, -) : 大對象分配其中Tiny分配和大對象分配都屬於內存管理的優化範疇，這裡暫時僅關注一般的分配方法。

以申請size為n的內存為例，分配步驟如下：

Golang內存分配是個相當複雜的過程，其中還摻雜了GC的處理，這裡僅僅對其關鍵數據結構進行了說明，了解其原理而又不至於深陷實現細節。1、Golang程序啟動時申請一大塊內存並劃分成spans、bitmap、arena區域

2、arena區域按頁劃分成一個個小塊。

3、span管理一個或多個頁。

4、mcentral管理多個span供線程申請使用

5、mcache作為線程私有資源，資源來源於mcentral。