# [筆記] Golang 撰寫共時性 ( Concurrency )
### 為什麼使用共時性
目前的 CPU 時脈已達到上限，硬體大多往多核心發展，然而如果程式碼沒有共時性，則無法真正地發揮平行處理使效能提升
#### 共時性 ( Concurrent ) 與平行處理 ( Parallel ) 的差別
* 共時性 : 每個工作結束後，另外一個工作才會開始
* 平行處理 : 在同個時間運行多個工作
#### 撰寫共時性程式碼要做的事
* 我們需要決定哪個工作可以被平行處理
* 撰寫程式時，我們不需考慮將工作對應到硬體，由這些處理 :
* Operating system
* Go runtime scheduler
#### Hiding Latency
既然共時性無法同個時間運行多個工作，那為何需要共時性呢?
* 就算沒有平行處理，共時性也可以改善效能
* 許多工作需要定期去等待一些東西，例如 :
* 讀取記憶體
* I/O
* 此時再等待的空檔，共時性就可以使程式先運行其他工作
### 共時性基礎
#### 程序 ( Processes )
Processes
* 一個跑程式碼的程序
* 每個程序有自己的 :
* 記憶體
* code
* stack
* heap
* shared libraries
* ...
* 暫存器
* program counter
* data regs
* stack ptr
* ...
Operating system
* 排程並管理程序，確保它們不會相互干擾且合理的使用資源
* 使程序執行擁有共時性
* 因為程序轉換速度很快
* 所以使用者會感受到程序在平行處理
#### 排程
程序排程
* Operating system 負責排程、分配資源 ( CPU、memory... )
* 實現接近平行處理的感覺
Context switch
* 控制程序間的轉換
* 轉換前會儲存狀態與內存，直到下次轉換到自己時能繼續執行
#### Thread 與 Goroutine
Thread 與 Processes 的差別
* 在程序間的轉換內容還是太慢了，於是有了 Thread
* Thread 會共享部分內容
* 一個程序裡可以存在多個 Thread
Goroutine
* Goroutine 類似在 Golang 裡的 Thread
* 在 OS 看來一樣是轉換 Thread
* 但 Go 可以轉換這些 Thread 裡的 Goroutine，就像 OS 轉換 Thread 一樣
Go Runtime Scheduler
* 負責排程 Thread 裡的 Goroutine
* 就像 OS 裡存在較小的 OS
#### Interleaving
* 撰寫共時性程式是困難的，當程式出錯時較難發現錯誤，因為執行順序可能會交錯
* 單一的 task，程式碼的運行順序是知道的
* 共時的多個 task 間，task 的運行順序是未知的
* 多個 task 運行時，各 task 內的程式碼甚至會交錯運行
* 假設有兩個 task
* 所有的交錯都是有可能的
* 必須考慮到所有的可能
* 執行順序是不確定性的
#### 競爭危害 ( Race Condition )
* 因共時性的交錯執行使執行順序是不確定性的，而執行順序影響到執行結果，這就是競爭危害
Task 間的溝通
* 這些執行緒間大程度上必須是獨立的，但並不是完全獨立，他們會共享訊息
* 例如 :
* 網頁伺服器，每個用戶一個執行緒
* 使每個用戶可以同時瀏覽不同的網頁，共享同樣的訊息
* 圖像處理，每個像素一個執行緒
* 使執行緒可以同時處理多個像素，但像是模糊化，必須跟其他執行緒共享鄰近的像素訊息
### Go 裡的執行緒
#### 建立 Goroutine
* `main()` 會自動建立 Goroutine
* 而其他建立方法必須使用關鍵字 `go`
```go=
go foo()
```
#### 離開 Goroutine
* 當程式碼執行完就會離開 Goroutine
* 而當 `main()` 執行完後，所有的 Goroutine 都會結束執行
* 所以可能因為 `main()` 較早完成，而存在尚未完成的 Goroutine
```go=
func main()
{
go fmt.Printf("New routine")
fmt.Printf("Main routine")
}
```
* 有可能 Main routine 先完成，也有可能 New routine 先完成
* 若是 Main routine 先完成，New routine 就不會輸出
* 解決方法 :
* 延遲 `main()`
```go=
func main()
{
go fmt.Printf("New routine")
time.Sleep(100 * time.Millisecond)
fmt.Printf("Main routine")
}
```
* 在 `main()` 裡增加延遲，給其他 Goroutine 完成的機會
* 但這方法不優，因為時間是不確定性的，也許再延遲的這段時間內，OS 在執行其他執行緒或是 Go Runtime Scheduler 在執行其他 Goroutine
* 需要使用較正式的同步結構
#### 同步結構基礎
* 使用 global events 來控制執行的相對順序
```go=
x = 1
x = x + 1
GLOBAL EVENT
```
* Task1
```go=
if GLOBAL EVENT
print x
```
* Task2
* global events 使 `print` 發生在 `x = x + 1` 之後
#### WaitGroup
* 來自 sync package
* 可以強迫 Goroutine 去等待其他 Goroutine
* 包含一個計數器
* 假設要等待的 Goroutine 為 x 個，那計數器就設為 x
* 每當完成一個 Goroutine 就遞減，直到遞減到 0，才執行此正在等待的 Goroutine
* `Add()` : 遞增計數器
* `Done()` : 遞減計數器
* `Wait()` : 等待直到計數器歸零
```go=
func foo(wg *sync.WaitGroup)
{
fmt.Printf("New routine")
wg.Done
}
fun main()
{
var wg sync.WaitGroup
wg.Add(1)
go foo(&wg)
wg.Wait()
fmt.Printf("Main routine")
}
```
* 
#### Goroutine 間的溝通
* 在大型的 Task 裡，Goroutine 間勢必要分享資料來溝通
* 一個簡單的例子，假設要計算四個數的乘積 :
1. 創建兩個 Goroutine，分別執行相乘兩個數
2. Main Goroutine 再將這兩個結果相乘
* main routine 必須將資料傳給兩個 sub-routines
* 而 sub-routines 必須將相乘後的結果傳回給 main routine
* 但資料的傳送不一定是在 Goroutine 的開始或結束，也有可能在中間
* 因此 Goroutine 間的溝通需使用 Channel 來完成
Channel
* 用於在 Goroutine 間傳送資料
* 需要使用某種型別來創建通道，來定義傳送的資料類型
* 使用 `make()` 創建 Channel
```go=
c := make(chan int)
```
* 使用 `<-` 來傳送與接收資料
* 傳送 :
```go=
c <- 3
```
* 接收 :
```go=
x := <- c
```
```go=
func prod(v1 int, v2 int, c chan int)
{
c <- v1 * v2
}
func main()
{
c := make(chan int)
go prod(1, 2, c)
go prod(3, 4, c)
a := <- c
b := <- c
fmt.Println(a * b)
}
```
* channel 默認上並不能暫存資料
* sending 會被鎖住直到 channel 接收到資料
* receiving 會被鎖住直到 channel 將資料送出
* 所以當 receiving 卻不使用此資料時就相當於 WaitGroup `Wait()` 的效果
* Task 1 :
```go=
c <- 3
```
* Task 2 :
```go=
<- c //receiving 不使用此資料
```
Buffer Channel
* 擁有暫存功能的 Channel
```go=
c := make(chan int, 3)
```
* 當 channel 的 buffer 是滿的時，sending 會被鎖住
* 當 channel 的 buffer 是空的時，receiving 會被鎖住
* 使用 Buffer Channel 的原因
* 若沒有 buffer，當 sending 與 receiving 速度不同時，勢必有一方必須等待另外一方
* 這樣降低了共時性的效果，所以使用 buffer 可以解決這問題
### 同步通訊
#### 迭代通道
```go=
for i := range c
{
fmt.Println(i)
}
```
* 持續接收來自通道 c 的數據
* 將接收到的數據放入 i，在大括弧中做使用
* 當發送端將通道關閉 `close(c)`，則此 for 迴圈將會結束，否則將持續執行
* 通常在發送端確定不會再發送數據時，才會使用 `close(c)`
#### 從多個通道讀取
* Goroutine `T3` 向 Goroutine `T1` 與 Goroutine `T2` 獲取資料
```go=
a := <- c1
b := <- c2
fmt.Pritln(a * b)
```
* 從多個通道讀取，但會互相等待
```go=
select{
case a = <- c1:
fmt.Println(a)
case b = <- c2:
fmt.Println(b)
}
```
* 使用 select 從多個通道讀取，不會因為要等待其他通道而被鎖住
#### select
```go=
select{
case a = <- inchan:
fmt.Println("received a")
case outchan <- b:
fmt.Println("sent b")
}
```
* select 可以傳送也可以接收
* 哪個 case 條件達到，哪個 case 先處理
```go=
for
{
select{
case a = <- c:
fmt.Println(a)
case <- abort:
return
}
}
```
* 在 select 使用 abort 通道，來中止異常
* 當 abort 通道 ( 異常通道 ) 有資料進來，for 迴圈將會中止
* 除此之外，就只是不斷地從 c 通道獲取資料並處理
```go=
select{
case a = <- c1:
fmt.Println(a)
case b = <- c2:
fmt.Println(b)
default:
fmt.Println("nop")
}
```
* 在 select 使用 default
* 當 case 條件都尚未達成時，就執行默認值 default
#### 互斥
```go=
var i int = 0
var wg sync.WaitGroup
func inc()
{
i = i + 1
wg.Done()
}
func main()
{
wg.Add(2)
go inc()
go inc()
wg.Wait()
fmt.Println(i)
}
```
* 照這樣共享變數 i 來看，i 應該要是 2
* 以這兩種流程來看也沒什麼問題
* 但事實上流程的交錯是發生在較低階的機器語言上，並不是我們看到的 go 語言
* 在機器語言上，`i = i + 1` 有三個動作，讀取 i、運算加 1、寫入 i
* 這就會導致 i 不等於 2
#### 如何預防互斥
1. 別讓兩個或兩個以上 Goroutine 共享變數
2. 使用 `sync.Mutex`
* 他使用一個二進制的標誌
* 當此變數被使用時，標誌打開
* 變數沒被使用時，標誌關閉
* `Lock()` : 變數被使用時，標誌打開
* `Unlock()` : 變數沒被使用時，標誌關閉
```go=
var i int = 0
var mut sync.Mutex
func inc()
{
mut.Lock()
i = i + 1
mut.Unlock()
}
```
* 將函式改寫成這樣就解決互斥問題了
#### 在使用多個 Goroutines 中如何初始化
* 初始化
* 只執行一次
* 在所有程序前執行
1. 在執行 Goroutines 前先初始化
2. 使用 `sync.Once`
* 可以在需要初始化的 Goroutines 開頭中調用
* 而他只會執行一次
* 其中一個在執行初始化時，其他程序將會阻塞直到初始化完成
* `Do(f)` : 初始化執行 `f` 函式
```go=
var wg sync.WaitGroup
var on sync.Once
func setup()
{
fmt.Println("Init")
}
func dostuff()
{
on.Do(setup)
fmt.Println("hello")
wg.Done()
}
func main()
{
wg.Add(2)
go dostuff()
go dostuff()
wg.Wait()
}
```
* 初始化的基本範例
* 打印結果為 :
```=
Init
hello
hello
```
#### Deadlock
假設有兩個 Goroutines G1、G2，他們互相依賴
* 當 G1 等待 G2
* 而 G2 等待 G1
* 這就是所謂的 Deadlock
```go=
var wg sync.WaitGroup
func dostuff(c1 chan int, c2 chan int)
{
<- c1
c2 <- 1
wg.Done()
}
func main()
{
ch1 := make(chan int)
ch2 := make(chan int)
wg.Add(2)
go dostuff(ch1, ch2)
go dostuff(ch2, ch1)
wg.Wait()
}
```
* Deadlock 的簡單範例
* 當所有 Goroutines 都 Deadlock 時，Golang 將會自動偵測出來
* 但當 Goroutines 的子集 Deadlock 時，Golang 是沒辦法偵測的
#### Dining philosophers problem
* 有五位哲學家要吃飯
* 中間各有一支筷子
* 需要兩支筷子才能吃飯
* 先拿左邊筷子再拿右邊
* 沒辦法一次所有人一起吃飯
* 這就是 Dining philosophers problem
```go=
type ChopS struct
{
sync.Mutex
}
type Philo struct
{
leftCS, rightCS *ChopS
}
func (p Philo) eat()
{
for
{
p.leftCS.Lock()
p.rightCS.Lock()
fmt.Println("eating")
p.leftCS.Unlock()
p.rightCS.Unlock()
}
}
func main()
{
//初始化
CSticks := make([] *ChopS, 5)
for i := 0;i < 5;i++
{
CSticks[i] = new(ChopS)
}
philos := make([] *Philo, 5)
for i := 0;i < 5;i++
{
philos[i] = &Philo{CSticks[i], CSticks[(i + 1) % 5]}
}
//eat
for i := 0;i < 5;i++
{
go philos[i].eat()
}
}
```
* 實作 Dining philosophers problem
* 當出現所有哲學家左手都拿筷子的情形後，所有程序就無法進行，形成 Deadlock
* 解法 : 將筷子依序編號，哲學家必須先拿起便號較低的筷子
* 如此一來編號最低筷子的兩個科學家都會優先拿起這隻筷子
* 這樣就解決了 Deadlock，但可能會造成編號最低筷子與編號最高筷子間的哲學家餓死
###### tags: `筆記` `程式語言` `Golang`
Sign in with Wallet
Connect another wallet