Goroutineはどうやって動作するのか

## 入る前に
[Gophercon](https://youtu.be/YHRO5WQGh0k)の動画をYoutubeで見れる機会がありました。　その中に、Goroutineについて色々情報があり、今回すごく勉強になったと思いまして、皆さんに共有したくてこの記事を作成するコヨになりました。
もし、間違ってる情報や、勘違いがあれば、コメントしていただければ更に勉強になると思います。

## Intro
Golangの特徴としていつも挙げられるのは、強力な同時性サポートです。   
この強力な同時性に欠かせない要素は `goroutine` です。 開発者は、`go` キーワードをつかって`goroutine` を生成することで簡単に同時性をサポートするプログラムを開発できます。 `Channel` を使えば、`goroutine` 間でデータを簡単に伝えることもできます。

```go
package main

import (
    "fmt"
    "time"
)

func main() {
    go f()

    fmt.Println("hello world")
    time.Sleep(10 * time.Second)
}

func f() {
    for i := 0; i < 5; i++ {
        fmt.Printf("count: %d\n", i)
        time.Sleep(1 * time.Second)
    }
}
// hello world
// count: 0
// count: 1
// count: 2
// count: 3
// count: 4
```
一見すると、`goroutine` は他のプログラミング言語で使用されるThreadと同じだと考えられます。 しかし、[A Tour of Go](https://tour.golang.org/concurrency/1) では`goroutine` を下記のように定義しています。
> “lightweight thread managed by the Go runtime”

直訳してみると、Go Runtimeによって管理される軽量化されたスレッドですが、なぜかThreadとは異なるようなニュアンスを漂わせています。 `goroutine` とは何なのか、そしてどのように動作するのか見てみましょう。

## Goroutine != (Kernel) Thread
`goroutine`はカーネルスレッドとは異なるリソースです。 上で`lightweightthread`と定義づけられただけに、`goroutine`はスレッドより軽量化された同時性のためのリソースです。 スケジューラによって管理され、個別スタックを持ちプロセスとヒップゾーンを共有するなど、多くの部分でスレッドに似た動作をしますが、スレッドと動作方式が異なる部分が存在し、より軽く動作するようになります。

まず、`goroutine`の基本スタック領域は2KB程度で、スレッド基本スタック領域である8KB(32-bit基準)より小さいです。 また、生成・削除及びContext switchの時、スレッドは数μs程度かかる反面、`goroutine`は数十ns程度で完了します。 スレッド生成及び削除にはSystem Callが実行されなければなりませんが、`goroutine`はSystem Callなしにユーザスペースでの動作を完了できるからです。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/2d3c094f-71de-74dd-66b3-2e1499261eef.png)
このように軽いGoroutineはスレッド上でスケジューリングされて動作します。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/816616d3-953b-0127-6d9c-e4fed50b6842.png)

また、上のようにひとつのOSカーネルスレッドにバインディングされた論理的プロセッサで実行され、`goroutine`が実行可能な状態になると、実行キューに追加されて実行されるようになります。

一つ疑問点があります。 カーネルスレッドの場合、OSスケジューラによって管理されているとお話ししました。 それでは`goroutine`は誰が管理してくれるのでしょうか？
## Go Runtime Scheduler
`goroutine`は`Runtime Scheduler`によって管理されます。 `Runtime Scheduler`は、Goプログラムが実行される時点に共に実行され、`goroutine`を効率的にスレッドにスケジューリングさせる役割を果たします。

下のような原則のもとで`goroutine`を適切にスケジューリングさせることになります。

- カーネルスレッドは高いのでできるだけ小さい数を使う。
- 多数の`goroutine` を実行して高い`Concurrency`を維持する。
- Nコアマシンで、N 個の`goroutine`を`Parallel`に動作させる。

内部的にどのような方法を通じてgoroutineをスケジューリングさせるのか見ていきましょう。

## runqueue
まず、`runqueue` というリソースについて見てみましょう。

goroutine作業は、スレッド毎にHeap領域に割り当てられた`runqueue`によって追跡されます。 名前からも分かるように、`runqueue` はFIFO形式のキュー資料構造を持ち、実行可能な状態のgoroutineを保管します。

```go
type schedt struct {
    ...
	// Global runnable queue.
	runq     gQueue
	runqsize int32
    ...
}
// https://github.com/golang/go/blob/3b304ce7fe35b9d1e8cf0b0518ed2550c361a010/src/runtime/runtime2.go#L777
```

## Scheduler Idea
じゃぁ、本格的にGoroutineをスレッドにスケジューリングするアイディアたちを見てみましょう
#### idea I: Reuse threads
> Create threads when needed; Keep them around for reuse

Runtime Schedulerはgoroutineが必要な時、スレッドを生成します。 スレッドにこれ以上実行するgoroutineがなかったらどうすればいいでしょうか。 ご存知のようにスレッドを終了する際にもSystemCall(`pthread_exit`)が必要で、資源返却の過程でのロードが存在します。 また、再びスレッドを生成するときにも、同じ負荷が発生します。 Runtime Schedulerはこの過程を省略し、スレッドを`idle` 状態にします。 スレッドが`idle` 状態になると、CPUコアを使用せずに待機することができます。 このようにidle状態になったスレッドリストは別途保管することになります。

このようにスレッドを再利用するアイデアで、スレッド生成削除に対する負荷なしにゴルティンをスレッドに素早くスケジューリングすることができます。

`goroutine` g1が実行され、終了後にg2が実行される過程

1. `g1`が作成され、local runqueueに追加される。
2. メインスレッドを含め全てのスレッドがbusyなので、新しいスレッド(`T1`)を生成し、`g1`を`T1`にスケジューリング
3. `g1`の作業が終了し、`T1` スレッドは終了せず、idle 状態で保管される。
4. 新しいgoroutine `g2`が生成され、idle状態のスレッド`T1`を再利用して実行

![reuse-thread.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/05748374-b0c3-2d88-77c0-dd2e8736792a.gif)

スレッドを再使用することは本当に良いアイディアのようです。 しかし、ここでも問題があります。 もし、現在の状態で`goroutine`が絶えず生成されたらどうなるでしょう？ すべてのスレッドが`busy`状態なので、スレッドは続けて生成され、こうすると`idle`状態のスレッドが膨大にたまることがあります。 この問題はどう解決すればいいでしょうか。

#### idea II: Limit threads accessing runqueue
簡単に生成できるスレッド数を制限することで解決が可能です。 `特定の条件`でスレッド数を制限すると、それ以上スレッドが生成されないようにすることができ、実行可能な`goroutine`を待機させることで適切にプロセッシングパワーを使用することができます。

この`特定の条件`はどうやって決定するのがいいでしょうか。 Goでは、この条件をCPUコア数に制限します。 作成されるスレッドのCPUコア数だけ作成するようにします。 このようにすべてのCPUコアにスレッドを実行させることで、適正水準のParallelismを達成することができます。

この数は、デフォルト値でCPUコア数に指定されますが、`rumtime.GOMAX PROCS` に設定することが可能です。 この設定は、1つのノードで複数のGoプログラムを実行させる時により良い性能を実現するために調節することもあります。

![limit-thread.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/e2c1adec-6b10-aa69-3d6f-c74dd5e9079e.png)

上図より、CPUコアが2つの状況で`g2`が実行されなければならない時点において、すべてのスレッドが`busy`状態であれば、CPUコア数(2つ)以上にスレッドを生成せずに待機します。 その後、他の`goroutine`のデータを受け取るために`<-ch`にブロックされる時点で`g2`がメインスレッドで動作します。

また、この`Limit`は`goroutine`を実行しているスレッドに制限されます。 System Call で使用されるスレッドは、この条件に含まれません。 この条件はしばらくしてから調べることにします。

今までは`runqueue`がグローバルで一つだけあるという仮定の下でシミュレーションをしました。 しかし、単一の`runqueue`環境では`goroutine`は満足できる性能を出すことができません。 `runqueue`は`Heap領域`にある共同のリソースで、ここにアクセスして`enqueue`,`dequeue`作業をするためには`goroutine`が生成されるたびに`Lockが必要`になるからです。

それでGoではスレッド別に`local runqueue`を使います。

#### idea III: Distributed runqueues
> Use N runqueues on an N-core machine

スレッドは各々`local runqueue`を持ちます。 スレッドはlocal runqueue`に実行する`goroutine`を持ってきて、それらを持ってきて実行することになります。

それでは、上で見てきた過程を`local runqueue`を追加して、もう一度シミュレーションしてみましょう。

1. `g1` goroutineが作成され、`runq A`に追加される。
2. すべて`busy`スレッドであるため、新しいスレッド`T1`を生成
3. `T1`が`g1`を実行しようとするが、`runq B`には`goroutine`がない状態

![local-runqueue-1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/e2c25d72-5e79-aa5f-c295-4ded97e77001.gif "図-5")
[図-5]

ご覧のとおり、`runq B`には、割り当てられた`goroutine`がないので、実行させる`goroutine`はありません。 どうしましょうか？

このような状況で、`Runtime Scheduler`は他の`local runqueue`の`goroutine`作業を盗みます。 自分の`runqueue`が空の場合、別の`local runqueue`をランダムに選択し、`goroutine`作業の`半分`を撮ってきます。

```go
// stealWork attempts to steal a runnable goroutine or timer from any P.
//
// If newWork is true, new work may have been readied.
//
// If now is not 0 it is the current time. stealWork returns the passed time or
// the current time if now was passed as 0.
func stealWork(now int64) (gp *g, inheritTime bool, rnow, pollUntil int64, newWork bool) {
    ...
    				if gp := runqsteal(pp, p2, stealTimersOrRunNextG); gp != nil {
					return gp, false, now, pollUntil, ranTimer
				}
    ...
}
// https://github.com/golang/go/blob/03886707f9e8db668bd1fd7b8f99799dba0408e3/src/runtime/proc.go#L3013
```

上のコードでwork stealingが確認できます。

![local-runqueue-2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/6602ba65-5493-e147-4c29-881e90add29e.gif )
[図-6]

[図-5]の過程をもう一度見てみると、上のように他の`runqueue`の作業を盗んで`T1`スレッドで作動させるところが見られます。 このように、異なる`runqueue`の作業の半分を持ってくることで、全体的に作業も均等に分配されることがあります。

## Blocking System call
次のように、Goroutineを利用すると考えてみましょう。

```go
func process(image) { // g1
    // goroutine 作成 
    go reportMetrics() // g3

    complicatedAlgorithm(image)
    
    // ファイル Write
    f, err := os.OpenFile() // goroutine & thread block
    ...
}
```

`g1`が`g3`を生成し、そしてI/Oジョブ（Blocking system call）を実行します。 これまでの内容をもとに類推してみると、CPUコア数が2つの環境で、上のような状況では`main` goroutineと`g1` goroutineがそれぞれスレッドを使用しているので、`g3`はまだ実行できずに待機するでしょう。 そして`g1`は`os.OpenFile()`関数を使ってI/O作業を行います。 Blocking system callを実行すると、応答が来るまでスレッドはBlockingされます。 したがって、`g3` goroutineはsystemcallが完了するまで待機することになります。

このような状況でRuntime Schedulerはどのようにしてこの問題を解決するのでしょうか？
#### Hand off
Runtime SchedulerはBackgroundモニタースレッドを通じて一定時間ブロッキングされたスレッドを感知します。 ブロッキングスレッドを検知し、`idle`スレッドがなければ、モニタはスレッドを新規に作ります。
> 上のスレッドLimitは、goroutineを実行しているスレッドに制限されるとお話ししましたが、Systemcallで使用されるスレッドは、この条件に含まれないとお話ししました。 ですから、Blocking system callを実行するスレッドは、このLimitに含まれません。

このように、新しく作られたスレッドの runqueueに、既存に貯められてたGoroutine作業たちをHandsoffさせます。

![runqueue-handoff.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/76353/8633f1e6-a439-97fc-2976-f6d231855b8f.png)

このhandoffを利用して　goroutineのstarvationを抑えられます。

## まとめ
Goの`Runtime Scheduler` は多様なアイデアを基に軽量化されたスレッドを最適化してスケジューリングすることができる方法を考案しました。

- スレッドの再使用
- Goroutineこの動作するスレッド数の制限(GOMAXPROCS)
- 分散されたrunqueue
- work stealing、handoff

`runqueue`がLinuxスケジュルロのように`priority`を提供することができない問題、実際`system topology`を反映することができない問題などまだ解決しなければならない問題が多いです。しかし、`goroutine`と`runtime scheduler`に実装された概念が強力なアイデアなのは間違いなさそうです。  
Kavya Joshiの発表は本当に簡単で楽しく、そして相次ぐ問題点とその解決法を基に行われ、興味津々に聞くことができて勉強にとても役立ったと思います。  
ぜひ、みなさんもこの機会にGoroutineについて色々勉強になるチャンスになると嬉しいです。