はじめに
実は9月に転職しまして、新しくGo言語を使用しています。個人的に goroutine が少し理解しづらく、自分の中で腑に落ちなかったため、スケジューリングについて調べてみました。
内容の多くは GopherCon2018 の素敵な動画と、書籍『Go言語100Tips』をもとに自分の言葉でまとめ直したものになっています。ぜひこちらもご覧ください。
goroutine とは
goroutine とは Go の runtime によって管理される軽量なアプリケーションスレッド です。プログラムによって生成された goroutine は、 Go の runtime scheduler によって自動的にカーネルスレッドに割り当てられます。カーネルスレッドと比べて軽量であり、作成コストやコンテキストスイッチングを低く抑えることができます。
以下は Effective Go より引用
A goroutine has a simple model: it is a function executing concurrently with other goroutines in the same address space. It is lightweight, costing little more than the allocation of stack space. And the stacks start small, so they are cheap, and grow by allocating (and freeing) heap storage as required.
Effective Go - The Go Programming Language
goroutine のスケジューリングの特徴
タスクとスケジューラ
goroutineは、独立したタスクとしてプログラムによって生成されます。これらのgoroutineを適切に管理し、実行する責任を持つのがGoランタイムのスケジューラです。スケジューラの目的は、利用可能なリソース（CPUコアやスレッド）を最大限に活用し、全てのgoroutineが均等に処理されるようにすることです。
つまり、なるべく少量のカーネルスレッドを使用して、以下を達成することを目指します。
- 高い並行性 (concurrency) を実現する
- CPU core 数（もしくはそれ以上）の並列性 (parallelism) を実現する
M:N スケジューリング
Goランタイムでは、M:N スケジューリングモデルが採用されています。これは、M個のgoroutineをN個のカーネルスレッドにマッピングすることを意味し、1つのカーネルスレッドが複数のgoroutineを切り替えながら実行することができます。このモデルは、リソースの利用効率を高め、スレッドのオーバーヘッドを最小限に抑えることを可能にします。
スケジューリングの透過性
Goを使用する開発者は、スケジューリングの詳細を気にする必要がありません。プログラマは単にgoキーワードを使ってgoroutineを起動するだけで、後はランタイムが適切にスケジューリングを行います。これにより、開発者は内部の並行処理の複雑さを自らハンドリングする必要がなくなります。
二種類の Queue とその活用
スケジューリングでは、Global QueueとLocal Queueが存在します。
よくあるモデルとしては、一つの Global Queue を全てのスレッドで共有する方式ですが、この方法だと多くのスレッドから一つの Queue にアクセスする必要があります。データ競合状態を解決するため、一時的なロックを取る必要が出てきます。これは全体のパフォーマンス低下を招くため、Goではスレッド固有の Local Queue で基本的にタスクを管理します。
スケジューラーは目的を達成するために、いくつかの方法で Global Queue と Local Queue の二種類の Queue を活用しています。
Work Stealing
各スレッドは主にLocal Queueを使用してgoroutineを処理し、これが空になると他のLocal Queueからgoroutineを「盗んで」きます。このメカニズムを Work Stealing と呼びます。これにより、全てのCPUコアを効率的に利用しようとします（厳密には、継続単位でstealしているらしいのでもう少し調べたい）。
Handoff
バックグランドで動いているスレッドが、ブロックされているスレッドを見つけると、そのスレッドの Local Queue が持っているタスクを他のスレッドの Local Queue へと委譲します。これを Handoff と呼びます。これにより、長い時間 Queue で待たされているタスクが存在しないようにしています。
Preemption
Global Queueは全てのスレッドが共有するバックアップのようなキューであり、必要に応じてここからgoroutineが割り当てられます。その代表的な例が、Preemption による利用です。Goランタイムは、一定の実行時間が経過したgoroutineを一時停止させることがあります。これにより、他のgoroutineがCPU時間を公平に使用できるようになります。この仕組みを Preemption と呼んでいます。その際に中断されたタスクは Global Queue に割り当てられます(Preemption が起こり得るため、プログラムの厳密な実行時間を予測することは難しいとされています)。
最後に
実は、goroutine は fork-join モデルに従っています。goroutine のスケジューリングは、以前まとめたJVM の ForkJoinPool における挙動と非常によく似ているものと捉えられそうです。
hiramekun.hatenablog.com
