ガーベージコレクションの迷宮にどこへ向かっているのか分からない

関連: 001_usage_of_signals_in_language_runtime.md, 006_other_reading_materials.md, 007_concurrency_comparison.md 要約 3つの言語 — Go、Kotlin、Erlang/Elixir（BEAM上で動作） — は、同じ問題（少数のOSスレッドで多くの論理タスクを実行する）に対して、1つの質問に対する3つの異なる答えで解決しています。それは、「誰がタスク間の切り替えを制御し、それを安全に行うためにそのコントローラーは何を知る必要があるか？」です。その質問への答えが、すべてを下流で決定します。モデルが協調的かプリエンプティブか、GCが1つのスレッドを一時停止するかプロセス全体を一時停止するか、クラッシュが封じ込められるか破滅的か、などです。このドキュメントは、各モデルを機能のリストとして説明するのではなく、その制約から導き出します。各セクションの最後には、次のセクションに進む前に答えられるはずのチェックポイントの質問があります。 背景: 3つの言語が解決している問題 CPUコアは一度に1つの命令ストリームを実行します。OSスレッドは、コアを多くの命令ストリームにタイムスライスするためのカーネルの抽象化ですが、それらは高価です。Linuxのデフォルトでは、スレッドあたり約8MBのスタックが必要です。コンテキストスイッチは、完全なレジスタファイルを保存/復元し、キャッシュとTLBを乱します。10,000のスレッドは、作業が行われる前にギガバイトのスタック領域を意味します。したがって、安価な並行処理を望むすべてのランタイムは、M:Nスケジューラを構築します。M個の論理タスクをN個のOSスレッドに多重化します（通常、Nはコア数に近似します）。以下の3つのシステムは、3つの異なるM:Nスケジューラであり、切り替えロジックを誰が所有するかについて異なる決定を下したため、それらは異なります。 チェックポイント: 続行する前に、OSスレッドがなぜスケールにおいて論理タスクあたり1つでは高価すぎるのかを1文で述べてください。 パート1 — Go このセクションのソースは直接読み取られています（記憶からの言い換えではありません）: src/runtime/preempt.go, src/runtime/signal_unix.go, src/runtime/proc.go, src/runtime/mgc.go — golang/go, masterブランチ、raw.githubusercontent.comから取得。 1.1 主要概念: これはフォークジョインではなくCSPです Goの並行処理モデルは、HoareのCommunicating Sequential Processes（CSP、1978年）の実装として明示されています。これは、チャネルを介したメッセージパッシングのみで相互作用する独立した逐次プロセスであり、ロックを介してアクセスされる共有ミュータブル状態ではありません。これは設計上の系譜であり、Go自身の資料に直接記載されています。「メモリを共有して通信するのではなく、通信によってメモリを共有せよ。」 CSP自体の起源 Tony Hoareは1978年にCommunications of the ACMで「Communicating Sequential Processes」を発表しました。彼が取り組んでいた問題は、現代のWebサービスの意味での並行処理ではありませんでした。それは、共有変数並行処理（セマフォ、モニター）が支配的なモデルであり、形式的に推論するのが非常に難しいことが証明されていた当時の並行プログラムの正しさでした。共有ミュータブル状態では、2つのプロセスの可能なインターリーブの数は爆発的に増加し、プログラムの正しさを証明することは、それらすべての下で正しいことを証明することでした。Hoareの提案は、プロセス間の唯一の相互作用を明示的で同期的な名前付きイベントにすることでした。プロセスは、送信先/受信先を名前付けし、送信/受信ペア全体が同期プリミティブとなり、個別のロックは不要になります。これには実際の数学的な利点があります。プロセスは何も共有しないため、各プロセスを単独で推論でき、プロセス間の通信イベントを、共有メモリのインターリーブの網羅的なケース分析よりもはるかに小さな問題として、別々に推論できます。これは代数に近いものです。CSPは、Hoare自身の後の作品で完全なプロセス代数として形式化され、Robin MilnerのCCS（Calculus of Communicating Systems、1970年代後半）と並行して独立して形式化されました。これら2つは通常、一般的にプロセス代数の起源として一緒に引用されます。Goの設計者（特にNewsqueakとAlef — すでにCSPスタイルのチャネルを使用していた直接の実験的前身 — で作業した経験のあるRob Pike）は、CSPの通信プリミティブ — 同期的な名前付きチャネルメッセージパッシング — を、Hoareの完全な形式プロセス代数や元の同期専用の制限（Goのバッファ付きチャネルは、Hoareの元の計算にはなかったバッファサイズまでの非同期送信を許可します）を採用することなく取り入れました。したがって、「GoはCSPを実装している」というのは、チャネルを同期の単位として、ロックではなく、というレベルでは正確ですが、Goが完全な形式計算を実装していると見なすと不正確です。これは、Goが行っていない他の2つのモデルと混同しやすいので重要です。 フォークジョイン（JavaのForkJoinPool、Cilk、OpenMP）: タスクは明示的にサブタスクに分割され、すべてを待ってから結合します。並列性は、単一の計算の分割統治形状を中心に構成されます。Goには言語レベルでこれに対する組み込み機能はありません。sync.WaitGroupで手動で実装する必要があります。Goroutineは暗黙的なjoinで生成されるわけではありません。go f()は直ちに返され、自分で同期を追加しない限り何もそれを待ちません。 ロックによる共有メモリスレッド（生のpthreads、Java synchronized）: デフォルトの調整プリミティブは、相互排他によって保護された共有アドレス空間です。Goもこれをサポートしています（sync.Mutexが存在し、ランタイム自体でヘビーに使用されています）が、言語が推奨するイディオマティックな表面ではありません。 チャネル（chan）はCSPプリミティブです。goroutineはチャネルに値を送信し、別のgoroutineがそれを受信します。転送自体が同期ポイントです。そのハンドオフのために個別のロックは必要ありません。 チェックポイント: goroutineが暗黙的にjoinしない場合、go f()呼び出しの効果がmain()が返る前に可視であることが保証されるものは何ですか？（回答: デフォルトでは何もありません — これが、チャネルまたはWaitGroupで明示的に待機しないプログラムが、生成されたgoroutineが完了する前に終了する理由です。これは一般的なバグのソースであり、言語の保証ではありません。） 1.2 GMPスケジューラ proc.goのファイル先頭のドキュメントコメント（約24行目以降）より: スケジューラのジョブは、実行準備のできたgoroutineをワーカー・スレッドに分散することです。G - goroutine。M - ワーカー・スレッド、またはマシン。P - プロセッサ、Goコードを実行するために必要なリソースです。MはGoコードを実行するために関連付けられたPを必要としますが、関連付けられたPなしでブロックされたり、syscall中にあったりすることがあります。設計ドキュメントは https://golang.org/s/go11sched にあります。これはgo11sched設計（Dmitry Vyukov、2012年）です。M:N:Pモデルは、Pごとのローカル実行キューの問題を解決するために特別に存在します。Pを個別のスケジューリングリソースとして持たない場合、作業を競合するすべてのMはグローバルキューにアクセスする必要があり、これは数コアを超えるとスケールしません。各Pはローカル実行キューを所有します。MはGoコードを実行するためにPを取得する必要があります。そのため、syscallでブロックされたgoroutineは、コアをアイドル状態にするのではなく、別のMが拾えるようにPを解放します（proc.goのhandoffp）。 1.3 プリエンプション: 進化の過程と、GCがそれを変更させた理由 Go ≤1.10 — 協調的、関数プロローグで。すべての関数呼び出しは「yieldせよ」フラグをチェックしました（スタック境界チェックを毒することにより実装、preempt.goのヘッダーコメントより：「同期セーフポイントは、関数プロローグでのスタック境界チェックのオーバーロードによって実装されています。」）。ループ本体に呼び出しがないgoroutine（for {}）はこのチェックをトリガーせず、この方法でプリエンプトされることはありませんでした。 これがGCの問題である理由、単なるスケジューリングの公平性の問題ではなく、mgc.goはマーク終了とスイープ終了の両方でstopTheWorldWithSemaを呼び出します（gcMarkTermination, gcStart — mgc.goの現在のソースで約835行目、1066行目）。STWは文字通り、GCフェーズが進む前にすべてのgoroutineがGCが安全と見なす状態に到達する必要があることを意味します。GCはグローバルに一貫した到達可能なビューを必要とするため、1つのgoroutineがまだ任意のコードを実行している状態でマーク/スイープ遷移を開始することはできません。関数呼び出しのないタイトなループでスタックしたgoroutineは、これを無期限にブロックしました。これは、2019年の提案（golang/proposal 24543-non-cooperative-preemption.md）の動機となった実際の測定された本番環境の問題でした — 「公平な」スケジューリングの一般的な願望ではありません。 Go 1.14 — 非協調的、シグナルベース。preempt.go