Kenny's Blog
Home Archives Tags Categories
筆記 - Golang 撰寫共時性 ( Concurrency )
|筆記

[筆記] 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

    1
    go foo()

離開 Goroutine

  • 當程式碼執行完就會離開 Goroutine

  • 而當 main() 執行完後，所有的 Goroutine 都會結束執行

    • 所以可能因為 main() 較早完成，而存在尚未完成的 Goroutine

      1
      2
      3
      4
      5
      func main()
      {
          go fmt.Printf("New routine")
          fmt.Printf("Main routine")
      }
      • 有可能 Main routine 先完成，也有可能 New routine 先完成
      • 若是 Main routine 先完成，New routine 就不會輸出

  • 解決方法 :

    • 延遲 main() 

      1
      2
      3
      4
      5
      6
      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 來控制執行的相對順序

    1
    2
    3
    x = 1
    x = x + 1
    GLOBAL EVENT

    • Task1

      1
      2
      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() : 等待直到計數器歸零
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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
1
c := make(chan int)

  • 使用 <- 來傳送與接收資料

    • 傳送 :

      1
      c <- 3

    • 接收 :

      1
      x := <- c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 :

      1
      c <- 3

    • Task 2 :

      1
      <- c //receiving 不使用此資料

Buffer Channel

  • 擁有暫存功能的 Channel
1
c := make(chan int, 3)
  • 當 channel 的 buffer 是滿的時，sending 會被鎖住
  • 當 channel 的 buffer 是空的時，receiving 會被鎖住

  • 使用 Buffer Channel 的原因

    • 若沒有 buffer，當 sending 與 receiving 速度不同時，勢必有一方必須等待另外一方
    • 這樣降低了共時性的效果，所以使用 buffer 可以解決這問題

同步通訊

迭代通道

1
2
3
4
for i := range c
{
    fmt.Println(i)
}
  • 持續接收來自通道 c 的數據
  • 將接收到的數據放入 i，在大括弧中做使用
  • 當發送端將通道關閉 close(c)，則此 for 迴圈將會結束，否則將持續執行
  • 通常在發送端確定不會再發送數據時，才會使用 close(c)

從多個通道讀取

  • Goroutine T3 向 Goroutine T1 與 Goroutine T2 獲取資料
1
2
3
a := <- c1
b := <- c2
fmt.Pritln(a * b)
  • 從多個通道讀取，但會互相等待
1
2
3
4
5
6
select{
    case a = <- c1:
        fmt.Println(a)
    case b = <- c2:
        fmt.Println(b)
}
  • 使用 select 從多個通道讀取，不會因為要等待其他通道而被鎖住

select

1
2
3
4
5
6
select{
    case a = <- inchan:
        fmt.Println("received a")
    case outchan <- b:
        fmt.Println("sent b")
}
  • select 可以傳送也可以接收
  • 哪個 case 條件達到，哪個 case 先處理
1
2
3
4
5
6
7
8
9
for
{
    select{
        case a = <- c:
            fmt.Println(a)
        case <- abort:
            return
    }
}
  • 在 select 使用 abort 通道，來中止異常
  • 當 abort 通道 ( 異常通道 ) 有資料進來，for 迴圈將會中止
  • 除此之外，就只是不斷地從 c 通道獲取資料並處理
1
2
3
4
5
6
7
8
select{
    case a = <- c1:
        fmt.Println(a)
    case b = <- c2:
        fmt.Println(b)
    default:
        fmt.Println("nop")
}
  • 在 select 使用 default
  • 當 case 條件都尚未達成時，就執行默認值 default

互斥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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() : 變數沒被使用時，標誌關閉
1
2
3
4
5
6
7
8
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 函式
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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()
}
  • 初始化的基本範例
  • 打印結果為 :
1
2
3
Init
hello
hello

Deadlock

假設有兩個 Goroutines G1、G2，他們互相依賴

  • 當 G1 等待 G2
  • 而 G2 等待 G1
  • 這就是所謂的 Deadlock
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
Author: Kenny Li
Link: https://kennyliblog.nctu.me/2019/10/08/Golang-concurrency/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
筆記 程式語言 Golang
Recommend
筆記 - Golang 基礎
筆記 - Golang 進階
筆記 - CSS 基礎
筆記 - Python 基礎
筆記 - MySQL 基礎
筆記 - Octave 基礎
繁