はじめに

今年に入ってから仕事でGolang書いてるのでスケジューラあたりについて調べた。ググってもあんまり資料が多くなかったんでまとめる。ソースコードを参照する時はGo 1.9.3を見た。わかりやすさを重視してあえて雑に説明しているところがあるけどご了承ください。
多分間違ってるところあるんで詳しい人は優しく教えてください。

goroutineあたりの基本的な話

goroutineはグリーンスレッド、つまりOSのスレッドは直接使ってない。なので、goroutineを作ることはネイティブスレッドを作る処理よりもはるかにコストが安い。このgoroutineを複数作るとランタイムが勝手にマルチスレッドで実行する。詳細は後述。
また、メインルーチンもgoroutineとして管理される。

スケジューリングの登場人物

重要な登場人物はM, G, Pの3人。

M(Machine)
- OSのスレッドに対応する。
G(Goroutine)
- そのまま。
P(Processor)
- Gを貯めておくdequeと呼ばれる特殊なキューを持ち、GをMに割りあてる役割を持つ。
- GOMAXPROCS環境変数はこれに対応する。
  - デフォルトで実行環境のコアの数が設定される¹

これらはソースコード上でm, g, pで定義されている。²

スケジューリングの基本的な仕組み

GOMAXPROCSの数だけM, Pのセットが用意される。GOMAXPROCSが2の場合、大まかには以下のような仕組みで実行される。

で、片方がGを全部実行してしまって暇になると、他のPから半分Gを奪い取る。

このスケジューリングアルゴリズムをwork stealingアルゴリズムと言う。このwork stealingアルゴリズム、CPUバウンドな処理は非常に効率が良いが、io waitなどの無駄にブロックする処理とは相性が悪い。そこで、いくつかの工夫がなされており、これから説明する。

詳細に入る前の準備

詳細の前に必要な事前知識を簡単に説明。

グローバルキュー
- Pが持つGのキューとは別にグローバルキューというものがある。
- 通常Gが実行待ち状態になるとPの持つキューに入るが、いくつかの状況ではグローバルキューに入る。
- このグローバルキューは、以下の時に取り出される。
  - Mの自分のキューが空の時に取り出す
  - Mの自分のキューがまだあったとしても61回に1度取り出す（そうやってグローバルキューがずっと実行されないことを防ぐ）
sysmon
- 基本的にGOMAXPROCSの数だけのMとPのセットが動いてる、という説明をしてきたが、それとは別にsysmonという関数を実行し続ける特別なMが存在する。これはP無しで実行される。
- このsysmonは処理本体は無限ループになっており、そのループの中で後述するnetpollのチェックや、実行時間の長いGのプリエンプト、必要があればGC用のGをグローバルキューに追加、などを行っている。
P idle list
- Pは他にやることがなければP idle listに入れられる。
M idle list
- Mも他にやることがなければM idle listに入れられる。

syscallを実行した時

syscallを使ったとき、そのsyscallがすぐ返ってくるものなら普通の処理とほとんど変わらない。
syscallを使って時間がかかる場合(少なくとも20nsec以上)、sysmonがそれを検知し、そのMとGをPから切り離し、別のMとPを紐付けて処理を進める³。

↓

syscallが終わったら、まず暇なPがいたらそれを取ってきて処理を進めようとする。

↓

それが無理ならグローバルキューに追加する。MはM idle listに追加される。

ネットワーク処理した時

ネットワーク処理にはnetpollerと呼ばれる仕組みが導入されている。Goのライブラリが提供するネットワーク処理のAPI的にはブロッキングするが、このnetpollerというやつが実行時にノンブロッキングな処理にしてくれる。そのノンブロッキングな処理は中身的にはLinuxならepoll, BSDならkqueueなどOSが提供する機能を使っている。

実際の仕組みは、ネットワークの待ちになった時にGがMから切り離されnetpollerに登録される。sysmonがnetpollerを定期的にチェックし、ネットワーク処理が準備完了していたら、そのGをグローバルキューにエンキューする。

これらはepollを使った実装の場合、登録部分にepoll_ctl, 取得部分にepoll_waitを使っている。

Gの実行時間が長い時

Mがずっと同じGを実行し続けていたら(少なくとも10ms以上)そのGをプリエンプトする機能もある。
sysmonが10ms以上かかっているGを見つけると、そのGのpreemptフラグをtrueにする。この時点ではプリエンプトはしない。
実際にプリエンプトするのはフラグをつけられた側。フラグがつけられたGが関数呼び出しをする際、自分のpreemptフラグを見てtrueならグローバルキューにエンキューする。

channelをreceive/sendした時

Gがchannel(channel1とする)のreceiveを待つと、channel1の待ちGリストにエンキューされる。
別のGがchannel1にsendすると、channel1の待ちGリストからデキューされ、sendしたGのPのキューにエンキューされる。

Golangのソースコードの歩き方

ここまででランタイムの動きの話は終わり。
Goのライブラリのソースコードを読んでいると、途中で宣言はあるけど実装がない関数が出てくることがある。これはgo:linknameディレクティブが使われている場合と、アセンブリ言語で定義されている場合とがある⁴。
go:linknameディレクティブの場合、^//go:linkname \S* importpath\.nameで検索すると出てくる。例えば、poll. runtime_pollWaitはそれで、^//go:linkname \S+ internal/poll\.runtime_pollWaitで検索するとわかる。

$ grep -P -r '^//go:linkname \S+ internal/poll\.runtime_pollWait' .
./runtime/netpoll.go://go:linkname poll_runtime_pollWait internal/poll.runtime_pollWait
./runtime/netpoll.go://go:linkname poll_runtime_pollWaitCanceled internal/poll.runtime_pollWaitCanceled

つまり、実装はこれ

https://github.com/golang/go/blob/go1.9.3/src/runtime/netpoll.go#L164

参考: https://golang.org/cmd/compile/#hdr-Compiler_Directives

アセンブリ言語で定義されている場合は、^TEXT.*·Name\(で検索すれば出てくる（Nameの手前は.ではなく·(U+00B7)であることに注意）。例えば、syscall.Syscallがそれで、こんな感じ。

$ grep -P -r '^TEXT.*·Syscall\('
syscall/asm_darwin_386.s:TEXT   ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_darwin_amd64.s:TEXT ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_darwin_arm.s:TEXT   ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_darwin_arm64.s:TEXT ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_freebsd_arm.s:TEXT  ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_linux_386.s:TEXT    ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_linux_amd64.s:TEXT  ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_linux_arm.s:TEXT    ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_linux_arm64.s:TEXT  ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_linux_mips64x.s:TEXT    ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_linux_mipsx.s:TEXT  ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_linux_ppc64x.s:TEXT ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_linux_s390x.s:TEXT ·Syscall(SB),NOSPLIT,$0-56
syscall/asm_nacl_386.s:TEXT ·Syscall(SB),NOSPLIT,$12-28
syscall/asm_nacl_amd64p32.s:TEXT ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_nacl_arm.s:TEXT ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_netbsd_arm.s:TEXT   ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_openbsd_arm.s:TEXT  ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_plan9_386.s:TEXT    ·Syscall(SB),NOSPLIT,$0-32
syscall/asm_plan9_amd64.s:TEXT  ·Syscall(SB),NOSPLIT,$0-64
syscall/asm_plan9_arm.s:TEXT    ·Syscall(SB),NOSPLIT,$0-32
syscall/asm_solaris_amd64.s:TEXT ·Syscall(SB),NOSPLIT,$0
syscall/asm_unix_386.s:TEXT ·Syscall(SB),NOSPLIT,$0-28
syscall/asm_unix_amd64.s:TEXT   ·Syscall(SB),NOSPLIT,$0-56

参考: https://golang.org/doc/asm#directives

また、ファイル名でOS, アーキテクチャの指定ができて、name_GOOS_GOARCHという文法になっている。
参考: https://golang.org/pkg/go/build/#hdr-Build_Constraints

参考

主な参照したソースコード

https://github.com/golang/go/blob/go1.9.3/src/runtime/proc.go
- sysmon, entersyscall, exitsyscall, scheduleらへん
https://github.com/golang/go/blob/go1.9.3/src/runtime/runtime2.go
- G, M, Pの定義
https://github.com/golang/go/blob/go1.9.3/src/runtime/chan.go
- channel
https://github.com/golang/go/blob/go1.9.3/src/runtime/netpoll.go
https://github.com/golang/go/blob/go1.9.3/src/runtime/netpoll_epoll.go
- netpoll
https://github.com/golang/go/blob/master/src/runtime/stack.go
- newstack(preemptの話のところ)

Go1.5から。それ以前はデフォルト１。あと論理的なコアの数なので、ハイパースレッディングがあれば２倍。 ↩
ソースコード読むとき検索しづらいからやめてほしい。 ↩
なので、この場合GOMAXPROCSが2でもMは(sysmonと合わせて)4以上になる。 ↩
他にもあるかもしれないけど、僕はその２パターンに遭遇した。 ↩

Golangのスケジューラあたりの話