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

入る前に

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

Intro

Golangの特徴としていつも挙げられるのは、強力な同時性サポートです。

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

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 では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なしにユーザスペースでの動作を完了できるからです。

このように軽いGoroutineはスレッド上でスケジューリングされて動作します。

また、上のようにひとつの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を保管します。

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が実行される過程

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

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

idea II: Limit threads accessing runqueue

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

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

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

上図より、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を追加して、もう一度シミュレーションしてみましょう。

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

[図-5]

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

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

// 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が確認できます。

[図-6]

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

Blocking System call

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

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させます。

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

まとめ

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

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

runqueueがLinuxスケジュルロのようにpriorityを提供することができない問題、実際system topologyを反映することができない問題などまだ解決しなければならない問題が多いです。しかし、goroutineとruntime schedulerに実装された概念が強力なアイデアなのは間違いなさそうです。

Kavya Joshiの発表は本当に簡単で楽しく、そして相次ぐ問題点とその解決法を基に行われ、興味津々に聞くことができて勉強にとても役立ったと思います。

ぜひ、みなさんもこの機会にGoroutineについて色々勉強になるチャンスになると嬉しいです。