第I部　基礎を固める

並列実行を言語処理系に載せる作業は、いきなりコードを書き換えることから始まるわけではありません。まず「何と戦っているのか」を理解する必要があります。

第I部では、その土台を固めます。並行（concurrency）と並列（parallelism）という、しばしば混同される 2 つの概念の違いから出発し、なぜいま並列化が避けられないのかを歴史的な文脈で押さえます。続いて、私たちのコードが最終的に走るハードウェア——キャッシュ、NUMA、SIMD、GPU——の前提を概観し、並行・並列を記述するためのモデル（共有メモリ、メッセージパッシング、アクター、CSP など）の地図を描きます。

そして本書を通じて最も重要な概念のひとつ、メモリモデルを導入します。「複数のスレッドが素朴に同じ変数を読み書きすると、なぜ壊れるのか」を理解することが、以降のすべての章の前提になります。最後に、本書で繰り返し参照する極小インタプリタを提示し、そこに実際にデータ競合を「踏ませて」みます。

1. 導入：並行と並列、そしてなぜ今なのか

本書の主題は「プログラミング言語の処理系に並列実行の機能を載せる」ことです。しかしその前に、私たちが扱おうとしている対象——並行（concurrency）と並列（parallelism）——を正確に区別しておく必要があります。この 2 つは日常語ではほとんど同義に使われますが、処理系を設計するうえでは決定的に異なる概念だからです。

1.1 並行と並列は別の概念である

並行（concurrency） とは、複数の処理を「同時に進行中の状態として扱う」ことです。実際に同じ瞬間に動いている必要はありません。1 つの CPU コアしかなくても、OS が高速に切り替えれば、ユーザから見れば複数の仕事が同時に進んでいるように見えます。並行は プログラムの構造 に関する概念——独立した複数の仕事をどう分けて記述し、どう調停するか——です。

並列（parallelism） とは、複数の処理が「物理的に同じ瞬間に実行される」ことです。これには複数の実行資源（CPU コア、ベクトル演算器、GPU など）が必要です。並列は 実行（ハードウェアの使い方） に関する概念です。

Go の設計者 Rob Pike の有名な言い方を借りれば、「並行は仕事を構造化する方法であり、並列はその実行のされ方」です。次の図はこの関係を整理したものです。

graph TD
    A[プログラムを並行に書く<br/>独立した仕事に分ける] --> B{実行資源は?}
    B -->|1コア| C[インターリーブ実行<br/>並行だが並列ではない]
    B -->|複数コア| D[同時実行<br/>並行かつ並列]

重要なのは、スレッド・プロセスレベルの並列性は、並行に構造化されたプログラムでなければ引き出せない という点です。逐次的に（1 本の道筋として）書かれたプログラムは、いくらコアを増やしても自動的には速くなりません。プログラムを独立した仕事へ分割する——すなわち並行に構造化する——ことが、マルチコア並列実行の前提になります。本書で「言語に並列機能を載せる」と言うとき、その実態の多くは「ユーザが並行性を表現でき、処理系がそれを並列に実行できるようにする」ことです。

1.2 なぜ今、並列化が避けられないのか

並列化が処理系設計の中心課題になったのは、ハードウェアの歴史的な転換が理由です。

ムーアの法則 は「集積回路上のトランジスタ数が約 2 年ごとに倍増する」という経験則で、これ自体は長く成り立ってきました。問題はもう一つの経験則、デナードスケーリング（Dennard scaling） の終焉です。デナードスケーリングは「トランジスタを小さくすると、単位面積あたりの消費電力が一定に保たれる」という性質で、これが成り立っていた間は、トランジスタの微細化に合わせてクロック周波数を上げても消費電力と発熱が抑えられました。

2000 年代半ば、リーク電流の増大によりデナードスケーリングが崩れ、クロック周波数をこれ以上上げると発熱が手に負えなくなる「パワーウォール（power wall）」に突き当たりました。その結果、増え続けるトランジスタの使い道は「1 コアを速くする」ことから「コアを増やす」ことへと舵を切ります。これが Herb Sutter の言う「フリーランチの終わり」「The Free Lunch Is Over」^{[Herb, 2005]}です。それまでは何もしなくてもクロック向上で勝手にソフトが速くなっていた（フリーランチ）のが、これからはソフト側が並列性を引き出さなければ性能が伸びなくなった、という宣言でした。

この帰結は、言語処理系の作り手にとって重い意味を持ちます。ユーザのプログラムが速くなるかどうかが、処理系が並列実行をどれだけうまく支えられるかにかかってくる からです。

1.3 並列化で何が変わるのか——処理系実装者の視点

逐次的な処理系を作るのは、難しくはあっても見通しのよい仕事です。プログラムカウンタは 1 つ、状態の変化は一直線、ある時点でのプログラムの状態は一意に定まります。バグがあれば、同じ入力で同じように再現します。

並列化はこの前提をすべて壊します。

• 状態が一意でなくなる：複数のスレッドが同時に進むと、「いまプログラムはどの状態か」を一意に言えなくなります。実行のたびに、命令の絡み合い（インターリーブ）が変わります。
• 再現性が失われる：あるインターリーブでだけ起きるバグは、デバッガを当てた瞬間にタイミングが変わって消える（いわゆるハイゼンバグ）ことがあります。
• 「素朴に共有する」と壊れる：複数スレッドが同期なしに同じメモリを読み書きすると、結果は未定義になります。これを データ競合（data race） と呼びます。第4章と第5章でその実体を詳しく見ます。
• 内部状態も危険になる：ユーザコードだけでなく、処理系自身が持つ内部状態（後述するシンボル表や GC、各種キャッシュ）も、複数スレッドから触られると壊れます。これが第III部の主題です。

つまり並列化とは、単に「スレッドを作る API を足す」ことではありません。処理系全体を、複数の実行主体が同時に存在する世界に耐えられるよう作り直す営みです。

1.4 本書の地図

本書は 4 部構成です。

1. 第I部（基礎）：並行・並列の概念、ハードウェア、各種モデル、メモリモデル、そしてデータ競合を体験する極小インタプリタ。
2. 第II部（言語機能）：スレッド、同期プリミティブ、ロックフリー、メッセージパッシング、軽量スレッド、データ並列。ユーザに見える機能の設計と実装。
3. 第III部（内部）：共有状態の棚卸し、GC、キャッシュ、参照カウント、GIL／GVL、オブジェクト共有モデル。一見並列と無関係に見える箇所の作り直し。
4. 第IV部（検証・評価）：データ競合検出、性能評価、そして実在処理系のケーススタディ。

サンプルは主に Ruby で示します。Ruby 自身が、長く単一スレッド前提（GVL あり）で作られた処理系を、RactorRactor のドキュメント^{[Koichi, 2020]}によって後から並列化していった経緯を持つため、本書の問題意識と相性がよいからです。

次章では、私たちのコードが最終的に走るハードウェア——メモリ階層、キャッシュ、NUMA、SIMD、GPU——の前提を概観します。並列実行の正しさと性能は、どちらもハードウェアの性質に強く縛られているからです。

2. ハードウェアの前提

並列処理系を設計するうえで、ハードウェアの性質を完全に無視することはできません。並列実行の 正しさ（同期がなぜ必要か）も 性能（並列化したのに速くならない理由）も、その多くがハードウェアの構造から来ているからです。本章では、言語処理系の実装者として最低限知っておきたいハードウェアの前提を、深入りしすぎない範囲で概観します。

2.1 メモリ階層とキャッシュ

現代の計算機で最も重要な事実のひとつは、CPU はメモリよりもはるかに速い ということです。CPU が 1 命令を実行する時間に対して、主記憶（DRAM）へのアクセスは 100 倍以上かかることも珍しくありません。この速度差を埋めるのが キャッシュ（cache） です。

キャッシュは CPU に近い、小さくて速いメモリです。よく階層化されており、L1（最速・最小）、L2、L3（最大・最も遅い、多くの場合コア間で共有）と段階的に大きく遅くなります。

2.1.1 キャッシュコヒーレンシ

各コアが自前のキャッシュを持つと、「コア A のキャッシュにある値」と「コア B のキャッシュにある値」が食い違う恐れがあります。これを防ぐのが キャッシュコヒーレンシ（cache coherence） プロトコル（MESI など）です。あるコアがある変数を書き換えると、他のコアのキャッシュにある同じラインのコピーは無効化されます。

コヒーレンシのおかげで「最終的には」みなが同じ値を見ます。しかし注意してほしいのは、コヒーレンシは個々の変数の一貫性を保証するだけで、複数の変数にまたがる操作の順序までは保証しない という点です。「いつ他のコアの書き込みが見えるか」「複数の書き込みがどんな順序で見えるか」は、次章以降で扱うメモリモデルの問題として残ります。

2.2 マルチコアと NUMA

複数のコアがメモリをどう共有するかには、大きく 2 つの構成があります。

• UMA（Uniform Memory Access）：すべてのコアが、どのメモリ番地にも同じコストでアクセスできる構成。
• NUMA（Non-Uniform Memory Access、非対称メモリアクセス）：コア（やソケット）ごとに「近いメモリ」と「遠いメモリ」がある構成。近いメモリは速く、遠いメモリ（別ソケットに繋がったメモリ）は遅くなります。

大規模なサーバは NUMA であることがほとんどです。NUMA 環境では、「どのスレッドが、どのコアで動き、どのメモリを使うか」が性能を大きく左右します。処理系の実装者にとっては、スレッドのスケジューリング（第10章）やメモリアロケータ（第13章）の設計で、データを使うコアの近くに確保する（first-touch ポリシーなど）配慮が効いてきます。

graph TD
    subgraph ソケット0
        C0[Core] --- L3a[共有L3]
        C1[Core] --- L3a
        L3a --- M0[ローカルメモリ 速い]
    end
    subgraph ソケット1
        C2[Core] --- L3b[共有L3]
        C3[Core] --- L3b
        L3b --- M1[ローカルメモリ 速い]
    end
    L3a -. 遅い相互接続 .- L3b

2.3 SIMD：1 命令で複数データ

並列性にはコアをまたぐものだけでなく、1 コアの中の並列性もあります。SIMD（Single Instruction, Multiple Data） は、1 つの命令で複数のデータに同じ演算を適用する仕組みです。たとえば「4 つの浮動小数点数を一度に足す」命令があれば、ループの 4 反復分を 1 命令で処理できます。x86 の SSE/AVX、ARM の NEON/SVE などがこれにあたります。

SIMD はデータ並列（第11章）と相性がよく、配列に対する一様な計算を大幅に高速化します。言語処理系から見ると、SIMD の活用は主にコンパイラの自動ベクトル化や、明示的なベクトル型・組み込み関数の提供という形で現れます。本書では深入りしませんが、「コア数を増やす並列化」とは別軸の並列性が CPU 内部にも存在することは押さえておいてください。

2.4 GPU：大量のスレッドで押し切る

GPU（Graphics Processing Unit） は、もともと画像処理のために、単純な演算を膨大なデータに並列適用する用途で発展しました。CPU が「少数の賢いコア」だとすれば、GPU は「大量の単純なコア」です。数千の実行レーンが、同じプログラム（カーネル）を異なるデータに対して一斉に実行します。

GPU は SIMD をさらに推し進めた SIMT（Single Instruction, Multiple Threads） という実行モデルを採り、行列演算や深層学習のような規則的・大規模なデータ並列計算で圧倒的な性能を出します。一方で、条件分岐が多い・データアクセスが不規則・スレッド間で複雑に同期するといった処理は苦手です。汎用言語の処理系が GPU を直接の実行基盤にすることは稀で、多くは CUDA/OpenCL/SYCL のような専用の枠組みや、ライブラリ経由で利用します。本書ではこれ以上は踏み込みませんが、「並列実行の基盤は CPU コアだけではない」という地図の一部として覚えておいてください。

2.5 なぜこれが処理系設計に効くのか

本章の内容は、後の章で繰り返し効いてきます。

• キャッシュとコヒーレンシ → なぜ同期（メモリバリア）が必要か（第4・7章）、false sharing（第13・19章）
• NUMA → スケジューラとアロケータの設計（第10・13章）
• SIMD・GPU → データ並列の実装（第11章）

3. 並行・並列モデルの地図

並列実行を言語に載せるとき、最初に決めなければならないのは「ユーザに、どういう世界観で並行性を書かせるか」です。これを 並行モデル（concurrency model） と呼びます。モデルの選択は、API の見た目だけでなく、処理系内部の作り、性能特性、そしてどんなバグが起きやすいかまでを決定づけます。本章では主要なモデルの地図を描きます。

3.1 2 つの大きな分かれ道：共有メモリとメッセージパッシング

並行モデルの最も根本的な分岐は、複数の実行主体がどうやって情報をやり取りするか です。

共有メモリ（shared memory） モデルでは、複数のスレッドが同じメモリ空間を共有し、同じ変数やオブジェクトを直接読み書きすることで通信します。直感的で、既存の逐次プログラムから移行しやすい一方、「誰がいつどこを触るか」を人間が正しく管理しなければデータ競合に陥ります。C/C++、Java、Ruby のスレッドなどが代表例です。

メッセージパッシング（message passing） モデルでは、実行主体は互いのメモリを直接触らず、メッセージを送り合う ことで通信します。状態は各主体に閉じ込められ、共有されません。「共有しないものは壊れない」という発想で、データ競合を構造的に避けられます。Erlang、Go（チャネル）、Ractor などが代表例です。

graph LR
    subgraph 共有メモリ
        T1[スレッド1] --> M[(共有メモリ)]
        T2[スレッド2] --> M
        T3[スレッド3] --> M
    end
    subgraph メッセージパッシング
        P1[プロセス1] -->|msg| P2[プロセス2]
        P2 -->|msg| P3[プロセス3]
        P1 -->|msg| P3
    end

どちらが優れているという話ではありません。共有メモリは細粒度のデータ共有で性能を出しやすく、メッセージパッシングは正しさを保ちやすく分散にも素直に拡張できます。多くの実用言語は両方を、層を分けて提供します。

3.2 CSP：チャネルを第一級に

CSP（Communicating Sequential Processes、通信逐次プロセス） は、Tony Hoare が 1978 年に提案した理論CSP の原論文^{[C., 1978]}で、メッセージパッシングモデルの古典です。CSP では、独立した逐次プロセスたちが チャネル（channel） を通じて通信します。プロセスは互いの名前を知る必要はなく、チャネルという「管」を介してデータをやり取りします。

CSP の特徴は、送受信が 同期的（rendezvous、ランデブー） であり得る点です。送り手は受け手が受け取るまで待ち、受け手は送り手が送るまで待ちます。この「出会い」が同期点になります。Go の goroutine と channel は CSP の直系の子孫で、select 文で複数チャネルを待つ機構（第9章）も CSP 由来です。

3.3 アクターモデル：状態を持つ独立した主体

アクターモデル（actor model） は、Carl Hewitt らが 1973 年に提案しましたアクターモデルの原論文^{[Carl, 1973]}。アクターは、自分専用の状態を持ち、メッセージを受け取って動く独立した主体です。アクターはメッセージを受け取ると、(1) 他のアクターへメッセージを送る、(2) 新しいアクターを生成する、(3) 次に受け取るメッセージへの振る舞いを変える、という 3 種類のことができます。

CSP との違いは、CSP がチャネル（通信路）を第一級にするのに対し、アクターは アクター（受け手）を第一級にし、各アクターが受信箱（mailbox）を持つ 点です。送信は基本的に非同期で、相手の受信箱に入れたら送り手は先へ進みます。Erlang/Elixir のプロセスArmstrong の学位論文^{[Joe, 2003]}、Akka、そして Ruby の RactorRactor のドキュメント^{[Koichi, 2020]}がこの系譜です。

3.4 タスク並列とデータ並列

通信の軸とは別に、「何を並列の単位にするか」という軸があります。

タスク並列（task parallelism） は、互いに異なる仕事（タスク）を並列に走らせます。「画像をデコードしながら別のタスクで音声を処理する」のように、異種の処理を同時に進めるイメージです。アクターやスレッドプール、後述する work-stealing スケジューラ（第10章）と相性がよい考え方です。

データ並列（data parallelism） は、同じ処理を大量のデータに対して並列に適用します。「100 万要素の配列の各要素に同じ関数を適用する」のように、同種の処理をデータで分割します。並列ループや map/reduce（第11章）、SIMD、GPU がこの系統です。

graph TD
    subgraph タスク並列
        TA[デコード] 
        TB[音声処理]
        TC[ネットワーク]
    end
    subgraph データ並列
        D[大きな配列] --> D1[前半に同じ関数]
        D --> D2[後半に同じ関数]
    end

実際のアプリケーションは両者を組み合わせます。「複数のリクエストを並列に処理し（タスク並列）、各リクエスト内で大きな配列を並列に変換する（データ並列）」といった具合です。

3.5 モデルが処理系に課す要求

処理系の実装者にとって、どのモデルを採るかは内部の作りを大きく左右します。

次章では、これらすべてのモデルの正しさの土台となる メモリモデル に踏み込みます。「素朴に共有すると、なぜ・どのように壊れるのか」を理解しないまま共有メモリモデルを実装すると、再現しないバグの沼に沈むことになるからです。

4. メモリモデル入門：なぜ素朴な共有は壊れるのか

本章は本書で最も重要な章のひとつです。「複数のスレッドが同期なしに同じ変数を読み書きすると、なぜ・どのように壊れるのか」を理解することが、第II部・第III部のすべての設計判断の前提になるからです。結論を先に言えば、ハードウェアもコンパイラも、あなたの書いた順序どおりにメモリを触ってはくれない からです。

4.1 直感が裏切られる例

次の擬似コードを考えます。2 つのスレッドが、初期値 0 の共有変数 x と y を使います。

# 初期状態: x = 0, y = 0
# スレッド A         # スレッド B
x = 1               y = 1
r1 = y              r2 = x

直感的には、「r1 == 0 かつ r2 == 0」は起こり得ないように思えます。A が r1 = y を読むとき y がまだ 0 なら、A はまだ y=1 の前にいるので、B はまだ r2 = x に来ていないはず……という推論です。しかし実際のハードウェアでは、両方とも 0 になる ことが起こり得ます。

理由は、CPU が「自分のスレッドから見て辻褄が合う限り」命令の実行やメモリへの反映を並べ替えてよいからです。A の x = 1 はストアバッファに溜まり、他コアからはまだ見えないうちに、A は先に r1 = y を実行できます。B 側でも同様のことが起きます。結果として両方が相手の書き込みを見ないまま読み取り、ともに 0 になります。

4.2 逐次一貫性：理想だが、現実ではない

私たちが暗黙に期待している「直感どおりの世界」には名前があります。逐次一貫性（sequential consistency, SC） です。Leslie Lamport が 1979 年に定式化しました逐次一貫性の定義^{[Leslie, 1979]}。逐次一貫性とは、

1. 各スレッドの操作は、そのプログラムに書かれた順序どおりに実行され、かつ
2. 全スレッドの操作全体が、何らかの 1 本の順序（グローバルな順序）に並べられる、

という性質です。要するに「複数スレッドの操作をトランプのように 1 列に混ぜ合わせた、どれか 1 つの順序で実行したのと同じ結果になる」世界です。先ほどの例で「両方 0」が起きないのは、この逐次一貫性が成り立つ世界の話です。

問題は、実際のハードウェアは性能のために逐次一貫性を保証しない ことです。各コアはストアバッファを持ち、書き込みを遅延させ、読み込みを先行させ、独立した命令を並べ替えます。逐次一貫性を常に保証しようとすると、これらの最適化がほぼ全部禁じられ、性能が大きく落ちます。そこでハードウェアは、より弱い保証——緩和メモリモデル（relaxed/weak memory model）——だけを提供し、必要な箇所だけ強い順序をプログラマが要求する、という分業にしています。

4.3 リオーダリングの 2 つの出どころ

順序の入れ替え（リオーダリング）は、2 か所で起こります。

1. コンパイラによる並べ替え：最適化コンパイラは、依存関係がないと判断した命令を入れ替えたり、変数をレジスタに載せたまま（メモリに書き戻さずに）使い回したりします。
2. ハードウェアによる並べ替え：CPU が実行時に、ストアバッファや out-of-order 実行によってメモリ操作の見える順序を変えます。

重要なのは、両方を同時に抑えないと意味がない ことです。コンパイラだけ抑えても CPU が並べ替えますし、逆もまた然りです。この「両方を抑える必要がある」という事実こそ、Hans Boehm が「スレッドはライブラリとしては実装できない」Boehm の主張^{[Hans-J., 2005]}と論じた核心です。コンパイラが並行性を知らないまま最適化すると、ライブラリ側でいくらロックを書いても正しさを保証できない——だから並行性のセマンティクスは 言語仕様の一部 でなければならない、という主張です。これは言語処理系の作り手に直接突きつけられた要求です。

4.4 acquire/release とメモリバリア

では、必要な箇所でどう順序を取り戻すのか。鍵は メモリバリア（memory barrier / fence） と、それを抽象化した acquire/release セマンティクス です。

• release（解放）操作：これより前のメモリ操作が、この操作より後ろに（他スレッドから見て）追い越されないことを保証します。データを準備し終えてからフラグを立てる「書き手」側で使います。
• acquire（獲得）操作：これより後のメモリ操作が、この操作より前に追い越されないことを保証します。フラグを確認してからデータを読む「読み手」側で使います。

この 2 つを組にすると、「書き手の release より前の書き込みは、その値を acquire で読んだ読み手から、すべて見える」という保証が得られます。これが happens-before（先行発生） 関係です。スレッドをまたいで「この出来事は、あの出来事より確実に前」と言える唯一の手段が、こうした同期操作で張った happens-before の鎖です。

sequenceDiagram
    participant A as スレッドA(書き手)
    participant B as スレッドB(読み手)
    Note over A: data = 42  (通常の書き込み)
    A->>A: ready.store(true, release)
    B->>B: ready.load(acquire) == true
    Note over B: data を読むと必ず 42 が見える

逆に言えば、同期操作で happens-before の鎖を張らずに、複数スレッドが同じ変数を触り、少なくとも一方が書き込みなら、それはデータ競合 です。そして多くの言語のメモリモデルでは、データ競合を含むプログラムの動作は 未定義（undefined） とされます。「未定義」とは「0 か 1 のどちらかになる」ではなく、「何が起きてもおかしくない（クラッシュも含む）」という意味です。

4.5 言語メモリモデルという発明

ハードウェアごとにメモリモデルが違うと、処理系の実装者は移植のたびに混乱します。そこで現代の言語は、ハードウェアから独立した自前のメモリモデル を仕様として定めます。処理系は、各ハードウェアでそのモデルを実現するために必要なバリアを挿入する責務を負います。

その先駆けが Java メモリモデル（JMM） で、Manson・Pugh・Adve による 2005 年の定式化Java メモリモデル^{[Jeremy, 2005]}が決定版になりました。JMM は「データ競合のないプログラムは逐次一貫性を持つ（DRF-SC: data-race-free implies sequential consistency）」という保証を中心に据えます。つまり「きちんと同期すれば直感どおりに動く。同期しなければ何が起きても文句は言えない」という契約を、言語として明文化したのです。C++11 以降の C++ メモリモデルもこの考え方を継承し、memory_order_seq_cst / acquire / release / relaxed といった段階を提供します。メモリモデルの体系的な入門としては、Adve と Gharachorloo のチュートリアル共有メモリ一貫性モデルのチュートリアル^{[Sarita, 1996]}が今も標準的な参照先です。

4.6 処理系実装者への含意

本章の結論を、実装者の立場でまとめます。

• 自分の言語のメモリモデルを定義する責任がある。「とりあえずスレッドを足す」だけでは、ユーザはどう書けば安全かを知る術がありません。
• DRF-SC を契約の中心に据える のが現代的な定石です。普通のユーザには「適切に同期すれば逐次一貫性、しなければ未定義」を約束し、低レベルの atomic は上級者向けに分けて提供します。
• コンパイラとランタイムの両方でバリアを正しく挿入する。最適化が同期を追い越さないよう、処理系のコード生成と JIT の両方が並行性を意識しなければなりません。

5. 題材：極小インタプリタとデータ競合の体験

ここまで概念を積み上げてきました。本章では、本書を通じて繰り返し参照する 極小インタプリタ を Ruby で実装し、そこに実際にデータ競合を踏ませてみます。手を動かして「壊れる」のを見ることが、以降の章で何を守ろうとしているのかを理解する近道だからです。

5.1 極小スタックマシン「Tiny VM」

題材として、スタックベースの小さな仮想マシン（VM）を使います。命令列を受け取り、内部スタックを操作しながら実行する、ごく単純な処理系です。多くの実用言語処理系（CRuby の YARV、CPython、JVM など）もスタックマシンを基礎にしているので、本物の縮図になっています。

class TinyVM
  def initialize
    @stack = []
    @globals = {}   # グローバル変数表（処理系の共有状態の縮図）
  end

  # program: 命令の配列。各命令は [opcode, *operands]
  def run(program)
    pc = 0
    while pc < program.size
      op, *args = program[pc]
      case op
      when :push   then @stack.push(args[0])
      when :add    then b, a = @stack.pop, @stack.pop; @stack.push(a + b)
      when :store  then @globals[args[0]] = @stack.pop
      when :load   then @stack.push(@globals[args[0]])
      when :print  then puts @stack.last
      end
      pc += 1
    end
    @stack.last
  end
end

vm = TinyVM.new
# (1 + 2) を計算して x に入れ、x を表示する
vm.run([[:push, 1], [:push, 2], [:add], [:store, :x], [:load, :x], [:print]])
# => 3

この VM には、後の章で問題になる要素が凝縮されています。オペランドスタック @stack はスレッドの実行状態（第6章のスタック管理）の縮図で、グローバル変数表 @globals は処理系が抱える共有状態（第12章）の縮図です。逐次実行する限り、これは何の問題もなく正しく動きます。

5.2 共有して走らせると壊れる

では、この VM の上で「カウンタを増やす」プログラムを、複数スレッドで同時に走らせてみましょう。@globals[:counter] を読み、1 を足し、書き戻す、という典型的な read-modify-write です。

INC = [
  [:load, :counter],   # counter を読む
  [:push, 1],
  [:add],              # +1
  [:store, :counter],  # 書き戻す
]

vm = TinyVM.new
vm.run([[:push, 0], [:store, :counter]])  # counter = 0

threads = 10.times.map do
  Thread.new do
    100_000.times { vm.run(INC) }   # 同じ VM を共有して回す
  end
end
threads.each(&:join)

vm.run([[:load, :counter], [:print]])
# 期待値: 1_000_000
# 実際:   毎回違う、たいてい 1_000_000 より小さい値

期待値は 100,000 × 10 = 1,000,000 です。しかし実際に走らせると、たいてい それより小さい、毎回異なる値 が出ます。@stack も @globals も複数スレッドが同時に触っているので、二重に壊れています。

5.3 なぜ値が失われるのか

失われる仕組みを、2 スレッドのインターリーブで追ってみます。counter が 5 のとき、A と B が同時に increment しようとしたとします。

sequenceDiagram
    participant A as スレッドA
    participant G as counter (=5)
    participant B as スレッドB
    A->>G: load → 5 を取得
    B->>G: load → 5 を取得
    A->>A: 5 + 1 = 6
    B->>B: 5 + 1 = 6
    A->>G: store 6
    B->>G: store 6
    Note over G: 2回 increment したのに 6（7 ではない）

A と B の両方が「5」を読んでから、それぞれ「6」を書き戻しています。本来 2 回増えて 7 になるべきところが 6 になり、1 回分の更新が 失われた更新（lost update） になります。これが increment が「アトミックでない（不可分でない）」ことの正体です。counter += 1 という一行が、機械語レベルでは load・add・store の 3 ステップに分かれ、その隙間に他スレッドが割り込めるのです。

5.4 スタックの破壊：もっと深刻な壊れ方

カウンタの値がずれるのはまだ「データが間違う」だけです。@stack を共有した場合はもっと深刻で、処理系そのものがクラッシュ し得ます。A が pop した直後に B も pop し、空の配列から取り出そうとして nil が紛れ込み、nil + 1 で例外になる——といった具合です。

ユーザコードのバグではなく、処理系の内部状態が壊れている ことに注意してください。実行スタックは処理系が握る最も基本的な状態であり、これがスレッド間で共有されてはいけません。第6章では、スレッドごとに独立したスタックを持たせる設計を扱います。

5.5 いちおうの応急処置と、その不満

最も素朴な対処は、VM 全体を 1 つのロックで囲うことです。

require 'monitor'

class TinyVM
  def initialize
    @stack = []; @globals = {}
    @lock = Monitor.new
  end

  def run(program)
    @lock.synchronize do   # 1度に1スレッドしか入れない
      # ...（中身は同じ）...
    end
  end
end

これで値は正しく 1,000,000 になります。しかし代償は大きい。@lock.synchronize の中には一度に 1 スレッドしか入れないので、せっかく複数コアがあっても実質的に逐次実行に戻ってしまう からです。これはまさに第16章で扱う GIL/GVL の縮図です。「全体を 1 つのロックで守る」のは正しさの面では簡単ですが、並列性を捨てています。

本書の残りは、この不満——「正しく、かつ並列に動かしたい」——にどう応えるかの長い旅です。第II部では、ロックの粒度を細かくする、ロックを使わない、そもそも共有しない、といった選択肢を順に検討します。第III部では、ユーザに見えないところで @globals や @stack に相当する処理系の共有状態をどう作り直すかを扱います。

これで第I部は終わりです。並行と並列の区別、ハードウェアの前提、モデルの地図、メモリモデル、そして実際に壊れる体験——並列処理系を作るための土台が揃いました。第II部からは、いよいよこれを「正しく、速く」するための言語機能を実装していきます。

第II部　言語に並列機能を「載せる」

第II部では、いよいよ言語処理系の表側——ユーザから見える並列機能——を設計し、実装していきます。

スレッドの生成と join、そしてその下で動く同期プリミティブ（atomic、CAS、mutex、条件変数、futex）を、上から下へ順に掘り下げます。さらにロックを使わずに正しさを保つロックフリーの世界、チャネルやアクターによるメッセージパッシング、OS スレッドより軽い軽量スレッドとそのスケジューラ、そして並列ループに代表されるデータ並列まで扱います。

ここでの視点は一貫して 「処理系の実装者として、この機能をどう提供し、どう実装するか」 です。ユーザがどう使うかだけでなく、その機能をランタイムがどう支えるのか——スタックの管理、スケジューリング、メモリの再利用——に踏み込みます。

6. スレッドを言語機能にする

第II部の最初の課題は、最も基本的な並列の単位である スレッド（thread） を言語機能として提供することです。ユーザが「この処理を別のスレッドで走らせる」「そのスレッドの終了を待つ」と書けるようにし、その下でランタイムがスタックや実行状態を管理する——その全体像を本章で組み立てます。

6.1 プロセスとスレッド

まず用語を整理します。プロセス（process） は、OS が割り当てる独立したメモリ空間（アドレス空間）を持つ実行単位です。プロセス間ではメモリは共有されません。一方 スレッド（thread） は、1 つのプロセスの中で複数走る実行の流れで、同じアドレス空間（ヒープ、グローバル変数）を共有 します。各スレッドが固有に持つのは、プログラムカウンタ（次に実行する命令の位置）、レジスタの値、そして スタック です。

graph TD
    subgraph プロセス
        H[(共有ヒープ・グローバル)]
        subgraph スレッド1
            S1[専用スタック] 
            R1[専用レジスタ/PC]
        end
        subgraph スレッド2
            S2[専用スタック]
            R2[専用レジスタ/PC]
        end
        S1 -.触れる.-> H
        S2 -.触れる.-> H
    end

「ヒープは共有、スタックは専用」というこの分割が、第4章で見たデータ競合の温床になります。スタック上のローカル変数は基本的に安全ですが、ヒープ上の共有オブジェクトは同期なしに触ると壊れます。

6.2 pthreads：C 言語処理系の足場

多くの言語処理系は C で書かれ、OS スレッドの上に自分のスレッドを載せます。UNIX 系での OS スレッドの標準 API が POSIX threads（pthreads） です。言語処理系の実装者は、たとえ自前の高水準スレッド API をユーザに見せるとしても、その内部では pthreads（や Windows のスレッド API）を直接叩くことになります。だからその基本は押さえておく必要があります。

スレッドの生成と join は次の形です。

#include <pthread.h>

void *worker(void *arg) {
    long id = (long)arg;
    /* このスレッドで行う仕事 */
    return (void *)(id * 2);   /* 戻り値を返せる */
}

int main(void) {
    pthread_t t;
    pthread_create(&t, NULL, worker, (void *)42);  /* スレッド開始 */
    void *result;
    pthread_join(t, &result);   /* 終了を待ち、戻り値を受け取る */
    return 0;
}

pthread_create は新しいスレッドを生成し、指定した関数を走らせます。pthread_join はそのスレッドの終了を待ち、戻り値を回収します。join しないまま放置するとリソースがリークするため、pthread_detach で「join しない（終了時に自動回収する）」と明示する方法もあります。

pthreads が提供するのはスレッドだけではありません。本書の後の章で扱う同期プリミティブの多くも pthreads の一部です。

6.2.1 スレッドスタックのサイズと数の制約

pthreads で見落としがちなのが スタックサイズ です。各 OS スレッドには固定サイズ（典型的には 1〜8 MB）のスタックが割り当てられます。これは 2 つの制約を生みます。第一に、深い再帰はスタックオーバーフローを起こします。第二に、スレッドをたくさん作れない という制約です。1 スレッドあたり 1 MB として、10,000 スレッドで 10 GB——現実的でありません。「接続ごとに 1 スレッド」のようなモデルが OS スレッドでは破綻するのはこのためで、第10章の軽量スレッドが生まれた直接の動機になります。

6.3 スレッドを言語の Thread クラスにする

C の生 API を、ユーザに見せる言語機能へ昇華させましょう。Ruby の Thread を模した API を考えます。

t = Thread.new(10) do |n|
  sum = (1..n).sum   # 別スレッドで計算
  sum                # ブロックの戻り値がスレッドの値になる
end

result = t.join.value   # 終了を待って結果を得る
puts result             # => 55

処理系の実装者として、この Thread.new の裏で起きることを整理します。

1. VM 実行状態の用意：新しいスレッド専用のオペランドスタック・フレームスタック（第5章の Tiny VM で言えば新しい @stack）を確保する。
2. OS スレッドの生成：pthread_create で OS スレッドを作り、その上で渡されたブロックを VM が実行する。
3. スレッドオブジェクトの登録：処理系が全スレッドを把握できるよう、グローバルなスレッドリストに登録する（GC やシグナル処理で全スレッドを止める必要があるため。第13・15章）。
4. 戻り値・例外の受け渡し：ブロックの戻り値や、途中で発生した例外を、join した側へ安全に渡す。

6.4 join とライフサイクル

join は「相手スレッドの終了を待つ」操作で、第4章の用語で言えば happens-before の鎖を張る同期点です。t.join が返った後では、t の中で行われたすべての書き込みが、join した側から確実に見えます。これは「結果を安全に受け取る」ための保証です。

スレッドの一生は、おおむね次の状態を遷移します。

stateDiagram-v2
    [*] --> Runnable: Thread.new
    Runnable --> Running: スケジューラが選択
    Running --> Blocked: ロック待ち / I/O待ち
    Blocked --> Runnable: 待ちが解ける
    Running --> Terminated: ブロック終了 / 例外
    Terminated --> [*]: join で回収

例外の扱いは設計判断が分かれます。Ruby ではデフォルトで、子スレッドで起きた例外は join 時に親へ再送出されます。「黙って死なせる」より「join した人に知らせる」方が、バグを見逃しにくい設計です。第10章の構造化並行性は、この「子の失敗を親が確実に拾う」考え方をさらに徹底します。

6.5 スレッドローカル記憶（TLS）

すべてを共有すると壊れるなら、「このスレッドだけが見える領域」が欲しくなります。それが スレッドローカル記憶（thread-local storage, TLS） です。同じ変数名・キーでも、スレッドごとに別の実体を持ちます。

Thread.current[:request_id] = "abc-123"   # このスレッド固有
# 別スレッドから Thread.current[:request_id] を見ても nil

TLS は処理系の内部実装でも多用されます。たとえば「現在実行中の VM コンテキストへのポインタ」「スレッドごとのアロケータの空きリスト（第13章）」「例外処理の途中状態」などをスレッドローカルに置くことで、ロックなしに高速アクセスできます。共有しないことが最速の同期だ、という発想の最も基本的な形です。

6.6 本章のまとめ

• スレッドはヒープを共有しスタックを専有する。共有部分がデータ競合の温床になる。
• C 処理系の足場は pthreads。生成・join に加え、ミューテックスや TLS も pthreads が提供する。
• OS スレッドは固定サイズのスタックを持ち、大量には作れない。これが第10章の軽量スレッドの動機。
• 言語の Thread 機能の実装は、生成 API だけでなく、VM 実行状態の用意・全スレッド管理・戻り値と例外の受け渡しを含む。
• TLS は「共有しない」ことで安全と速度を得る基本手段。

スレッドを用意したら、次に必要なのはスレッド間の 同期 です。次章では、Thread の下で動く同期プリミティブ——atomic、CAS、spinlock、futex、mutex、条件変数——を上から下へ掘り下げます。

7. 同期プリミティブの内側

第5章で見たとおり、複数スレッドが同じ状態を触ると壊れます。それを防ぐのが 同期プリミティブ（synchronization primitive） です。本章では、ユーザに見える Mutex から、その土台にある atomic 命令まで、層を下りながら「実際どう実装されているのか」を解剖します。同期は魔法ではなく、ハードウェアの atomic 命令の上に積み上げられた工学です。

7.1 最下層：atomic 操作と CAS

第4章で、counter += 1 が load・add・store の 3 ステップに分かれ、その隙間で壊れることを見ました。これを防ぐ最も基本的な道具が、atomic（不可分）操作 です。atomic 操作は「他のスレッドから見て、操作全体が一瞬で起きたか、まだ起きていないかのどちらかにしか見えない」ことをハードウェアが保証します。中途半端な状態が観測されません。

最も重要な atomic 命令が CAS（Compare-And-Swap、比較交換） です。CAS は「あるメモリ番地の値が期待値と等しければ、新しい値に書き換える。等しくなければ何もしない。そして元の値（または成否）を返す」という操作を、不可分に行います。x86 では cmpxchg、ARM では load-linked/store-conditional（LL/SC）として提供されます。Treiber が 1986 年の報告Treiber の報告^{[R., 1986]}で示したように、CAS は並行データ構造の礎です。

CAS を使うと、先ほどのカウンタを正しく増やせます。

# atomic_cas(addr, expected, new) は擬似プリミティブとする
def atomic_increment(cell)
  loop do
    old = cell.value
    new = old + 1
    break if atomic_cas(cell, old, new)   # 誰にも邪魔されず更新できたら成功
    # 失敗 = 間に誰かが書き換えた。読み直してやり直す
  end
end

この「読む → 計算する → CAS で書き戻す → 失敗したらループ」というパターンは、ロックフリープログラミング（第8章）の心臓部です。誰も止めずに、衝突したときだけやり直すので 楽観的（optimistic） な同期と呼ばれます。

7.2 spinlock：待つのではなく回す

atomic を使えば、最も単純なロックを作れます。spinlock（スピンロック） は、ロックが空くまで CAS をひたすら繰り返して「忙しく待つ（busy-wait）」ロックです。

class SpinLock
  def initialize; @locked = AtomicBoolean.new(false); end

  def lock
    # false から true へ CAS できたら獲得成功。できなければ回り続ける
    until @locked.compare_and_set(false, true)
      # スピン（CPU を回しながら待つ）
    end
  end

  def unlock
    @locked.set(false)   # release セマンティクスで解放
  end
end

spinlock は、ロックを保持する時間がごく短く、待ち時間が「他コアで数命令」程度なら効率的です。OS に制御を渡さず、コンテキストスイッチのコストを避けられるからです。しかし保持時間が長いと、待っているコアが無駄に CPU を焼き続けます。さらに、待っているスレッドと保持しているスレッドが同じコアに割り当てられると、保持側が走れず誰も進めない最悪の事態（特にシングルコアやオーバーサブスクリプション時）も起きます。

7.3 futex：ユーザ空間とカーネルの良いとこ取り

spinlock は短い待ちには良いが長い待ちに弱い。逆に「待つときは OS に寝かせてもらう」純粋なカーネルロックは、競合がないときでもシステムコールのコストがかかります。この両者を折衷するのが futex（fast userspace mutex） です。Linux で Franke らが導入しましたfutex の論文^{[Hubertus, 2002]}。

futex の発想はこうです。

1. 競合がない普通のとき：ロックの獲得・解放はユーザ空間の atomic 操作だけで完結する。カーネルに入らないので速い。
2. 競合したときだけ：futex システムコールで「この番地の値が X の間、寝かせてくれ（FUTEX_WAIT）」とカーネルに頼み、解放側が「この番地で寝ている奴を起こせ（FUTEX_WAKE）」と頼む。

sequenceDiagram
    participant U as ユーザ空間(atomic)
    participant K as カーネル(futex)
    Note over U: 競合なし → atomic だけで獲得/解放（高速）
    U->>K: 競合あり → FUTEX_WAIT で待機（寝る）
    Note over K: 解放側が FUTEX_WAKE で起こす
    K-->>U: 起床して再挑戦

「競合がない限りカーネルに入らない」という設計は、現代の高速なロックの定石です。Linux 上の pthread mutex やほとんどの言語の mutex は、内部的に futex（や同等の機構）の上に作られています。

7.4 mutex：相互排他の標準形

mutex（mutual exclusion、相互排他ロック） は、ユーザが最もよく使う同期プリミティブです。「同時に 1 スレッドしか保持できない」ロックで、保持している間はクリティカルセクション（critical section、同時に 1 スレッドしか入れない区間）を独占できます。

mutex = Mutex.new
counter = 0

threads = 10.times.map do
  Thread.new do
    100_000.times do
      mutex.synchronize { counter += 1 }   # ここは一度に1スレッド
    end
  end
end
threads.each(&:join)
puts counter   # => 1_000_000（今度は正しい）

第5章で値がずれたカウンタが、mutex で囲うと正しくなります。mutex の lock は acquire、unlock は release のセマンティクスを持つので、第4章の happens-before の鎖が張られ、保護した変数の更新が他スレッドから正しく見えます。

mutex は spinlock と futex を組み合わせて作られるのが普通です。「まず少しスピンして、それでも取れなければ futex で寝る」というハイブリッド（適応的 mutex）が、短い競合にも長い競合にも対応します。

7.5 条件変数：状態の変化を待つ

mutex は「区間の排他」を提供しますが、「ある条件が成り立つまで待つ」用途には向きません。素朴にループで条件をチェックし続けると、ロックを握ったまま回り続けて誰も状態を変えられなくなります。これを解くのが 条件変数（condition variable） です。

条件変数は mutex と組で使い、「条件が成立するまでロックを手放して寝る（wait）」「条件を変えた側が起こす（signal / broadcast）」という協調を提供します。生産者・消費者のキューが典型例です。

class BoundedQueue
  def initialize(max)
    @max = max; @items = []
    @mutex = Mutex.new
    @not_full  = ConditionVariable.new
    @not_empty = ConditionVariable.new
  end

  def push(x)
    @mutex.synchronize do
      @not_full.wait(@mutex) while @items.size >= @max  # 満杯なら空くまで寝る
      @items.push(x)
      @not_empty.signal   # 「空でなくなった」と消費者を起こす
    end
  end

  def pop
    @mutex.synchronize do
      @not_empty.wait(@mutex) while @items.empty?       # 空なら入るまで寝る
      x = @items.shift
      @not_full.signal    # 「満杯でなくなった」と生産者を起こす
      x
    end
  end
end

7.6 層の全体像

本章で下りてきた層を、上から並べると次のようになります。

言語処理系の実装者は、ユーザにはこの一番上（mutex・条件変数や、もっと高水準のチャネル）を見せつつ、内部実装ではもっと下の層を直接使い分けます。

8. lock-free の世界

ロックは正しさを保つ強力な道具ですが、本質的な弱点を持ちます。ロックを保持したスレッドが（ページフォルトやスケジューラの都合で）止まると、そのロックを待つ全員も止まる——進行が一人の都合に人質に取られるのです。ロックフリー（lock-free） プログラミングは、ロックを使わず atomic 操作だけで並行データ構造を作り、この弱点を克服しようとします。本章は第II部の発展的な内容で、ロックフリーの世界の地図と、その代表的な落とし穴を扱います。

8.1 進行保証の階層

「ロックを使わない」ことの意味を正確にするため、進行保証（progress guarantee） の階層を定義します。これは Herlihy が並行オブジェクトの理論で整理した枠組みHerlihy のwait-free論文^{[Maurice, 1991]}に基づきます。

• blocking（ブロッキング）：あるスレッドの遅延が、他スレッドの進行を無期限に妨げ得る。ロックを使う実装はこれ。
• lock-free（ロックフリー）：システム全体としては、有限ステップで必ずどれかのスレッドが進む。個々のスレッドは（CAS 失敗を繰り返して）飢えることはあるが、全体は止まらない。
• wait-free（ウェイトフリー）：すべてのスレッドが、他スレッドの速度に関係なく、有限ステップで自分の操作を完了する。最も強い保証。

graph TD
    A[wait-free<br/>全スレッドが有限ステップで完了] --> B[lock-free<br/>システム全体は必ず進む]
    B --> C[blocking<br/>誰かが止まると皆止まる]

wait-free が理想ですが、一般に実装は複雑で重くなります。実用上の多くの並行データ構造は lock-free を狙います。Herlihy はまた、どんな同期プリミティブがあれば任意の wait-free オブジェクトを作れるかを コンセンサス数（consensus number） という尺度で分類し、CAS がコンセンサス数 ∞（最強）であることを示しました。第7章で CAS を礎と呼んだのには、こうした理論的な裏付けがあります。

8.2 ロックフリースタックと ABA 問題

最も基本的なロックフリーデータ構造が、Treiber のスタックTreiber の報告^{[R., 1986]}です。先頭ポインタ top を CAS で付け替えるだけの単純な構造です。

# push: 新ノードの next を現在の top にして、top を新ノードへ CAS で付け替える
def push(node)
  loop do
    old_top = @top.value
    node.next = old_top
    break if @top.compare_and_set(old_top, node)
  end
end

# pop: top を、その次のノードへ CAS で付け替える
def pop
  loop do
    old_top = @top.value
    return nil if old_top.nil?
    new_top = old_top.next
    return old_top if @top.compare_and_set(old_top, new_top)
  end
end

一見正しそうですが、ここに有名な落とし穴 ABA 問題 が潜みます。pop が old_top（ノード A）を読み、その next（ノード B）を控えた直後にプリエンプトされたとします。その間に別スレッドが A を pop し、B も pop し、再び A を push し直したとします。すると top は再び A を指しますが、いまや A の next は B ではありません。眠っていたスレッドが目を覚まして CAS すると、「top はまだ A だ」と成功してしまい、top を（もう存在しないかもしれない）古い B に付け替えてしまいます。

sequenceDiagram
    participant T as スレッド(pop中)
    participant S as スタック top
    T->>S: old_top = A, new_top = A.next(=B) を控える
    Note over S: 別スレッドが A→B を pop、その後 A を push し直す
    Note over S: top は再び A だが A.next はもう B でない
    T->>S: CAS(top, A, B) が「A のまま」と誤認して成功
    Note over S: スタックが壊れる

値は A→…→A と戻ったのに「変わっていない」と CAS が誤認するのが ABA です。古典的な対策は、ポインタに 世代カウンタ（tag） を付け、(ポインタ, カウンタ) の組を CAS することです。値が一巡してもカウンタが進むので誤認を防げます。

8.3 メモリ再利用という難問

ABA とも絡む、ロックフリーで最も厄介な問題が 安全なメモリ再利用（safe memory reclamation） です。pop でノードをスタックから外しても、まさにその瞬間に別スレッドがそのノードを読んでいるかもしれません。ロックがあれば「全員が手を離してから解放」できますが、ロックフリーでは「いつ誰も触っていないか」を知るのが難しいのです。早すぎる解放は use-after-free（解放済みメモリへのアクセス）を招きます。

GC のある言語（Ruby、Java など）では、この問題の多くを GC が肩代わりします。「外したノードは、もう誰も参照しなくなったら GC が回収する」ので、実装者は解放のタイミングに悩まなくて済みます。GC はロックフリープログラミングの隠れた味方 なのです。逆に C/C++ のような手動管理の言語では、専用の再利用手法が必要になります。

8.3.1 ハザードポインタ

代表的な手法が ハザードポインタ（hazard pointer） です。Michael が提案しましたハザードポインタの論文^{[Maged, 2004]}。各スレッドは「いま自分が触っているノード」を、グローバルに見える専用スロット（ハザードポインタ）に公示します。ノードを解放したいスレッドは、解放前に全スレッドのハザードポインタを走査し、誰かが公示していたら解放を保留します。「誰も使っていないことを確認してから解放する」を、ロックなしに実現する仕組みです。

8.3.2 RCU（Read-Copy-Update）

もうひとつの重要な手法が RCU（Read-Copy-Update） で、McKenney らが提案しRCU の論文^{[Paul, 1998]} Linux カーネルで多用されています。RCU は「読み手はほぼ無コスト（バリアすら不要なことも）、書き手は新しいコピーを作って差し替え、古いコピーは『すべての読み手が抜けた』と確実に言える猶予期間（grace period）の後に解放する」という分業です。読み込みが圧倒的に多く書き込みが稀なデータ構造（処理系で言えばクラス階層や設定表など、第12章）に絶大な効果を発揮します。

8.4 いつロックフリーを使うべきか

ロックフリーは魅力的ですが、安易に手を出すべきものではありません。

• 正しさの検証が極めて難しい：第4章のメモリモデルを完全に理解し、すべての atomic にメモリ順序を正しく付け、ABA と再利用を漏れなく処理する必要があります。微妙な誤りは、特定のハードウェア・特定のタイミングでしか再現しません。
• 必ずしも速くない：競合が低ければ、適応的 mutex（第7章）の方が速いことも多い。CAS のリトライが多発すると、ロックより遅くなることもあります。

8.5 処理系実装者への含意

言語処理系の内部では、ロックフリー構造が効く箇所が確かにあります。Michael と Scott のロックフリーキューMichael-Scott キュー^{[Maged, 1996]}は、スレッド間のワークキュー（第10章の work-stealing デック）の基礎ですし、メソッドキャッシュ（第14章）やフリーリスト（第13章）の一部にも応用されます。

ただし鉄則は「まず正しく、必要なら速く」です。処理系の共有状態（第12章）をいきなりロックフリー化するのではなく、まず粗いロックで正しく動かし、プロファイル（第19章）でボトルネックを特定してから、その箇所だけをロックフリーや RCU へ置き換える——という順序を強く勧めます。

次章では、共有メモリの難しさから一歩離れ、「そもそも共有しない」メッセージパッシングの実装——チャネル、select、アクター、future/promise——へ進みます。

9. メッセージパッシング：チャネル・アクター・future

ここまでの共有メモリの議論は、「同じメモリを正しく共有する」ための努力の連続でした。メッセージパッシングは発想を反転させます。共有しないものは壊れない のだから、状態を各実行主体に閉じ込め、通信は値のやり取りに限る——そうすればデータ競合は構造的に消える、という考え方です。本章では、その実装手段であるチャネル、select、アクター、future/promise を、処理系の立場から組み立てます。

9.1 チャネル：値が流れる管

チャネル（channel） は、第3章で触れた CSPCSPの原論文^{[C., 1978]}に由来する、値を送受信するための管です。送り手は send、受け手は receive でやり取りし、互いの正体を知る必要はありません。

チャネルには容量（バッファ）の有無で 2 種類あります。

• アンバッファド（同期）チャネル：容量 0。送り手は受け手が受け取るまでブロックし、受け手は送り手が送るまでブロックする。送受信の「出会い」が同期点になる（rendezvous、ランデブー）。
• バッファド（非同期）チャネル：容量 N。バッファに空きがあれば送り手はブロックせず先へ進む。満杯なら空くまで待つ。

実装は、第7章で作った有界キューがほぼそのまま使えます。チャネルとは「ブロッキングなキューに送受信のインタフェースを被せたもの」と見なせます。

ch = Channel.new(capacity: 0)   # 同期チャネル

producer = Thread.new do
  3.times { |i| ch.send(i) }    # 受け手が受け取るまで各 send はブロック
  ch.close                       # もう送らないことを通知
end

consumer = Thread.new do
  while (v = ch.receive)         # close されると nil が返るまで受け取る
    puts "received #{v}"
  end
end
[producer, consumer].each(&:join)

9.2 select：複数チャネルを同時に待つ

実用的な並行プログラムは、複数のチャネルのうち「どれか準備できたもの」を処理したくなります。これを担うのが select（CSP 由来の選択合成）です。select は複数の送受信候補を並べ、準備できたものを 1 つ選んで実行します。複数準備できていればランダムに（公平に）選び、どれも準備できなければブロックする（あるいは default 節があればそれを実行する）のが一般的です。

select do |s|
  s.receive(jobs)    { |job| handle(job) }       # jobs から受け取れたら
  s.receive(quit)    { return }                  # quit が来たら終了
  s.after(1.0)       { puts "timeout" }          # 1秒何も来なければタイムアウト
end

select の実装は意外に難しく、メッセージパッシング処理系の腕の見せ所です。複数チャネルに同時に「待ち」を登録し、どれか 1 つが成立した瞬間に、他の登録を atomic に取り消す 必要があるからです。取り消しに失敗すると、二重受信や取りこぼしが起きます。タイムアウト（after）も、内部的にはタイマーが値を送るチャネルとして表現でき、select に統一的に組み込めます。

9.3 アクター：状態を持つ独立主体

アクター（actor） は、第3章で見たとおりアクターモデルの原論文^{[Carl, 1973]}、自分専用の状態と受信箱（mailbox）を持つ独立主体です。チャネルが「通信路」を第一級にするのに対し、アクターは「受け手」を第一級にします。各アクターは一度に 1 つのメッセージしか処理しないので、自分の状態に関しては自動的に直列化 され、ロックが要りません。

class Counter < Actor
  def initialize; @count = 0; end

  def on_message(msg)
    case msg
    in [:inc]            then @count += 1          # 自分の状態。排他不要
    in [:get, reply_to]  then reply_to.send(@count)
    end
  end
end

c = Counter.spawn
1000.times { c.send([:inc]) }
me = Actor.current
c.send([:get, me])
puts Actor.receive   # => 1000

アクターモデルが最も成功したのは Erlang/Elixir です。Joe Armstrong の学位論文Armstrong の学位論文^{[Joe, 2003]}は、アクター（Erlang ではプロセスと呼ぶ）を「軽量・隔離・メッセージのみで通信・障害は監視して再起動」という設計でまとめ、電話交換機のような高信頼システムを実現しました。隔離されているからこそ、1 つのアクターがクラッシュしても他へ波及せず、監視者が再起動できる——「Let it crash（落ちたら落とせ、そして再起動せよ）」の哲学です。これは並列性そのものより、隔離による堅牢性 が主眼であることに注意してください。

9.4 future と promise：結果の引換券

非同期に始めた計算の「結果」を、後で受け取りたい——これを抽象化するのが future と promise です。呼び方は処理系で揺れますが、典型的には次の役割分担です。

• future：まだ計算中かもしれない結果への「引換券」。value を呼ぶと、結果が出るまで待って受け取る。
• promise：その結果を「あとで埋める」書き込み側のハンドル。計算が終わったら fulfill(value) で値を入れる。

f = Future.new do
  heavy_computation   # 別スレッドで実行
end

do_other_work          # その間、呼び出し側は別の仕事を進められる
puts f.value           # 結果が必要になったら受け取る（まだなら待つ）

future は内部的には「値 ＋ 状態（未完了/完了）＋ 待っているスレッドのリスト」を持つオブジェクトで、第7章の条件変数で実装できます。「未完了の間 wait、fulfill 時に待ち手を signal」という、まさに条件変数の教科書的な用途です。

future の真価は 合成 にあります。then でつないで「結果が出たら次にこれをする」と書けると、コールバックの入れ子（いわゆるコールバック地獄）を平坦化できます。この「結果が出たら次へ」を言語構文に昇華したのが、次章で扱う async/await です。

fetch_user(id)
  .then  { |user| fetch_orders(user) }   # user が得られたら注文を取得
  .then  { |orders| render(orders) }
  .rescue { |err| log(err) }             # どこかで失敗したら

9.5 モデルの選び方と実装コスト

メッセージパッシングの各手段は、得意分野が異なります。

これらの手段はいずれも、大量の実行主体を効率よく走らせる土台——たくさん作れて、ブロック時に安く待たせられる実行単位——を必要とします。OS スレッドでは数が足りません。次章では、その土台となる 軽量スレッドとスケジューラ を実装します。

10. 軽量スレッドとスケジューラ

第6章で見たとおり、OS スレッドは固定サイズのスタックを持ち、数万も作れません。しかし第9章のチャネルやアクターは、数十万・数百万の実行主体が当たり前のように欲しくなります。このギャップを埋めるのが 軽量スレッド（lightweight thread） です。本章では、ファイバー、M:N スケジューリング、work-stealing、async/await、構造化並行性という、現代の並行ランタイムの中核を組み立てます。

10.1 なぜ OS スレッドでは足りないのか

OS スレッドの問題を整理します。第一に メモリ：1 スレッドあたり数 MB のスタックは、数万スレッドで破綻します。第二に 切り替えコスト：OS スレッドの切り替えはカーネルを経由し、レジスタ退避やキャッシュ汚染を伴って重い。第三に ブロッキング：1 スレッドが I/O でブロックすると、その OS スレッドは丸ごと寝てしまいます。

軽量スレッドは、これらを「ユーザ空間で」解決します。スタックを小さく可変サイズにし、切り替えをカーネルなしで行い、ブロックする操作を「実際には OS スレッドをブロックさせない」ものに置き換えます。

10.2 ファイバー：協調的に切り替わる実行

最も基本的な軽量実行単位が ファイバー（fiber）、あるいはコルーチン（coroutine）です。ファイバーは「途中で実行を中断し、後で再開できる関数」です。OS スレッドと違い、自分から明示的に制御を手放す（yield する）まで切り替わらない——協調的（cooperative）スケジューリングです。

fib = Fiber.new do
  puts "A"
  Fiber.yield        # ここで呼び出し元へ制御を返す
  puts "B"
  Fiber.yield
  puts "C"
end

fib.resume   # => A （yield で戻る）
fib.resume   # => B
fib.resume   # => C

ファイバーの実装の核心は スタックの保存と切り替え です。各ファイバーは自分のスタックを持ち、yield/resume の際にスタックポインタとレジスタを退避・復元します。OS を経由しないので切り替えが軽く、スタックを必要なだけ小さく確保できるので大量に作れます。

10.3 M:N スケジューリング

軽量スレッドを並列に走らせる枠組みが M:N スケジューリング です。M 個の軽量スレッド（ファイバー、goroutine、仮想スレッドなど）を、N 個の OS スレッド（多くは CPU コア数）に動的に載せ替えます。N 個の OS スレッドは「ワーカ」として常駐し、その上で M 個の軽量スレッドが代わる代わる走ります。

graph TD
    subgraph LT層["軽量スレッド層 M個"]
        G1[LT]
        G2[LT]
        G3[LT]
        G4[LT]
        G5[...数十万...]
    end
    subgraph OS層["OSスレッド層 N個=コア数"]
        W1[ワーカ1]
        W2[ワーカ2]
    end
    G1 --> W1
    G2 --> W1
    G3 --> W2
    G4 --> W2

M:N の鍵は ブロッキングの扱い です。軽量スレッドが I/O やチャネル受信でブロックするとき、それを載せている OS スレッドまで一緒に寝かせてはいけません。ランタイムはブロック操作を横取りし、(1) その軽量スレッドを「待ち」状態にして脇へ退け、(2) 解放された OS スレッドに別の実行可能な軽量スレッドを載せます。I/O は背後で epoll/io_uring のようなイベント通知に変換され、完了したら待っていた軽量スレッドが再びスケジュール対象に戻ります。これにより「数百万の接続が、それぞれ専用スレッドを持つかのように同期的なコードで書けるのに、消費する OS スレッドはコア数だけ」が実現します。

10.4 work-stealing：負荷を自律的にならす

M:N で次に問題になるのが、ワーカ間の 負荷分散 です。あるワーカに仕事が溜まり、別のワーカが暇、では並列性を活かせません。これを解く定石が work-stealing（仕事の盗み） です。Blumofe と Leiserson がその効率を理論的に裏付けwork-stealing の論文^{[Robert, 1999]}、Cilk が実装で示しましたCilk-5 の論文^{[Matteo, 1998]}。

仕組みはこうです。各ワーカは自分専用の両端キュー（デック、deque）を持ちます。

• 自分の仕事は、デックの 片端（bottom） に push/pop する（LIFO、キャッシュに優しい）。
• 暇になったワーカは、他のワーカのデックの 反対端（top） から仕事を「盗む」（FIFO）。

graph LR
    subgraph ワーカA 忙しい
        DA[bottom で push/pop]
    end
    subgraph ワーカB 暇
        DB[空]
    end
    DB -.top から盗む.-> DA

自分は bottom、盗む側は top と、操作する端を分けることで競合をほぼ避けられます。盗みが起きるのは暇なワーカだけなので、負荷が高いときは盗みが減り、低いときだけ自律的にならされます。この「中央の管理者を置かず、暇な者が自分で仕事を探しに行く」設計が、スケーラビリティの鍵です。Go のランタイム、Java の ForkJoinPool（第20章）など、現代の並列ランタイムの多くが work-stealing を採用しています。

10.5 async/await：CPS とステートマシン化

ファイバーは強力ですが、すべての言語が「任意の関数の途中でスタックを退避する」機構を持てるわけではありません。そこで多くの言語は、async/await という構文で、コンパイラの変換によって中断・再開を実現します。

async def fetch_and_render(id)
  user   = await fetch_user(id)     # ここで中断し得る
  orders = await fetch_orders(user) # ここでも
  render(user, orders)
end

このコードは、見た目は同期的ですが、await のたびに中断・再開できます。その実現方法が CPS 変換（継続渡しスタイル、Continuation-Passing Style） あるいは ステートマシン化 です。コンパイラは async 関数を、await の地点で区切られたステートマシンへと書き換えます。

# コンパイラが概念的に生成するステートマシン（イメージ）
class FetchAndRender
  def step(state, input)
    case state
    when :start
      start(fetch_user(@id)) ; :await_user           # user を待つ状態へ
    when :await_user
      @user = input
      start(fetch_orders(@user)) ; :await_orders      # orders を待つ状態へ
    when :await_orders
      @result = render(@user, input) ; :done
    end
  end
end

await の前後でローカル変数（user など）はステートマシンのフィールドへ「持ち上げ」られ、中断をまたいで保存されます。これは第9章の future/promise と密接で、await は「future が完了するまでこのステートマシンを止め、完了したら次の状態へ進める」操作に対応します。

10.6 構造化並行性

軽量スレッドが安価になると、今度は「作ったはいいが回収を忘れる」「子が失敗したのに親が気づかない」というリーク・取りこぼしが新たな問題になります。これに規律を与えるのが 構造化並行性（structured concurrency） です。

考え方はシンプルで、並行に起動した子タスクの寿命を、ある構文ブロック（スコープ）に閉じ込める ことです。スコープを抜けるときに、起動した全タスクの完了を待ち、どれかが失敗すれば残りをキャンセルして親へ伝播する——関数呼び出しが必ず戻ってくるのと同じ規律を、並行にも持ち込みます。

result = Concurrent.scope do |s|
  a = s.spawn { fetch_user(id) }     # 子タスク
  b = s.spawn { fetch_config }       # 子タスク
  # ブロックを抜けるとき、a と b の両方の完了を待つ。
  # 片方が例外を投げれば、もう片方をキャンセルし、例外を親へ伝える。
  [a.value, b.value]
end

構造化並行性は、第6章で見た「子スレッドの例外を join で拾う」「TLS がタスク移動で消える」といった問題への、現代的な回答です。「並行のライフサイクルをスコープで括る」ことで、リソースリークと迷子のタスクを構造的に防ぎます。

10.7 本章のまとめ

• OS スレッドはメモリ・切り替えコスト・ブロッキングの 3 点で大量並行に向かない。
• ファイバー／コルーチンは、ユーザ空間でのスタック退避により安価な中断・再開を提供する。
• M:N スケジューリングは M 個の軽量スレッドを N 個の OS スレッドに載せ、ブロックを横取りして並列性を保つ。
• work-stealing は中央管理者なしで負荷を自律的にならし、スケールする。
• async/await は CPS／ステートマシン化により中断・再開を構文で表現する。色の伝播という代償がある。
• 構造化並行性は、軽量タスクのライフサイクルをスコープに括り、リークと取りこぼしを防ぐ。

ここまでがタスク並行の世界です。次章では、もう一方の軸——同じ処理を大量のデータに適用する データ並列 を扱います。

11. データ並列：並列ループと map/reduce

第10章までで扱ったのは、互いに異なる仕事を並行に進める タスク並列 でした。本章はもう一方の軸、データ並列（data parallelism）——同じ処理を大量のデータに一斉に適用する並列性——を扱います。データ並列は、規則的で大規模な計算において、最も素直に並列性能を引き出せる形であり、言語に並列機能を載せるうえで「ユーザに最も歓迎されやすい」入り口でもあります。

11.1 なぜデータ並列は扱いやすいのか

第5章では、共有状態を素朴に並列化して痛い目を見ました。データ並列が比較的安全なのは、典型的なケースで 各データ要素の処理が互いに独立 だからです。配列の各要素を 2 乗する処理を考えると、要素 i の計算は要素 j の計算と何も共有しません。独立なら、データを分割して別々のコアに配るだけで、同期をほとんど気にせず並列化できます。

# 逐次版
result = data.map { |x| heavy(x) }

# データ並列版（イメージ）: 同じ処理を分割して並列に適用
result = data.parallel_map { |x| heavy(x) }

「各要素の処理が独立で、副作用がない（純粋関数）」という条件が満たされる限り、データ並列は驚くほど素直に動きます。逆に言えば、本章の落とし穴はほぼすべて「この独立性の仮定が崩れたとき」に集約されます。

11.2 並列ループ：処理系はどう分割するか

最も基本的なデータ並列が 並列ループ（parallel loop） です。「このループの各反復は独立だから、好きに分割して並列に回してよい」とユーザが宣言し、処理系がそれを複数コアに割り振ります。処理系の実装者にとっての設計判断は、主に 分割の粒度 と 負荷の偏り です。

ループを N 個のコアに分けるとき、単純に「前から N 等分」する 静的分割（static scheduling） が最も軽量です。分割のオーバーヘッドがほぼゼロだからです。しかし各反復の処理時間がばらつくと、重い反復が偏ったコアだけ遅れ、他が遊ぶ「負荷の偏り（load imbalance）」が起きます。

これを避けるのが 動的分割（dynamic scheduling） です。ループを小さなチャンクに刻み、各コアが「終わったら次のチャンクを取りに来る」方式にします。負荷は自然にならされますが、チャンクを配る同期のコストが乗ります。両者の中間として、最初は大きく、残りが減るにつれチャンクを小さくする guided scheduling もよく使われます。

graph TD
    subgraph 静的分割
        S[ループ 0..999] --> S1[コア1: 0..249]
        S --> S2[コア2: 250..499]
        S --> S3[コア3: 500..749]
        S --> S4[コア4: 750..999]
    end
    subgraph 動的分割
        D[チャンクの山] -.終わったら取りに来る.-> D1[コア1]
        D -.-> D2[コア2]
    end

11.3 reduce：独立でない集約をどう並列化するか

map は各要素が独立なので素直でした。難しいのは reduce（畳み込み）——多数の要素を 1 つの値に集約する操作です。合計、最大値、ヒストグラムの統合などがこれにあたります。集約は「結果」を共有するので、素朴に並列化すると第5章の lost update に逆戻りします。

並列 reduce の鍵は 結合律（associativity） です。演算 ⊕ が結合的（(a⊕b)⊕c == a⊕(b⊕c)）であれば、計算の「まとめる順序」を自由に変えられます。これにより、各コアが自分の担当範囲を部分集約し、最後にその部分結果同士をまとめる、という木構造の並列化ができます。

# 各コアが部分和を出し（共有なし）、最後に部分和をまとめる
def parallel_sum(data, n_workers)
  chunks = data.each_slice(data.size / n_workers).to_a
  partials = chunks.map do |chunk|
    Thread.new { chunk.sum }   # 各スレッドは自分のローカルな部分和だけ計算
  end.map(&:value)
  partials.sum                  # 部分和をまとめる（ここは小さい）
end

ポイントは、各ワーカが共有変数を更新せず、自分専用の部分結果（partial）を持つ ことです。共有カウンタを全員が atomic に叩く設計より、はるかにスケールします（第19章でこの差を実測の観点から再訪します）。これは「共有を減らすほど速くなる」という、本書を貫く原則の一例です。

graph TD
    D0[部分和A] --> M1[A+B]
    D1[部分和B] --> M1
    D2[部分和C] --> M2[C+D]
    D3[部分和D] --> M2
    M1 --> R[総和]
    M2 --> R

11.4 map/reduce というパターン

map（各要素を独立に変換）と reduce（結合的に集約）を組み合わせた map/reduce は、データ並列の最も汎用的な骨格です。「独立に変換 → 局所的に集約 → 集約結果を統合」という三段構えは、1 台のマルチコアから、何千台ものクラスタ（分散 MapReduce）まで、同じ形でスケールします。言語に parallel_map と parallel_reduce を用意することは、ユーザに「独立性と結合律を意識させる」という教育的な効果も持ちます。

11.5 データ並列が壊れるとき

データ並列の安全性は「各要素の処理が独立」という仮定に全面的に依存しています。この仮定が崩れる典型を挙げます。

• 隠れた共有状態：map のブロックの中で、外側のカウンタやキャッシュ、ログバッファを更新している。見た目は独立でも、実は共有を踏んでいる。
• 要素間の依存：要素 i の計算が要素 i-1 の結果に依存する（漸化式、累積和の素朴な実装など）。これは単純には並列化できず、scan（並列プレフィックススキャン）のような専用アルゴリズムが要る。
• 副作用の順序依存：map のブロックが I/O やグローバル状態を変更し、その順序に意味がある場合。並列化で順序が崩れる。

11.6 SIMD・GPU との接続

第2章で触れた SIMD と GPU は、データ並列の最も先鋭な実行基盤です。並列ループの本体が「各要素に同じ単純な演算をする」形なら、コンパイラはそれを SIMD 命令へ自動ベクトル化でき、さらに規模が大きく規則的なら GPU カーネルへ載せられます。言語処理系から見ると、データ並列は「マルチコアへの分割」と「コア内 SIMD」と「GPU への委譲」という三層の並列性に、同じプログラムから接続できる入り口になります。本書ではこれ以上は踏み込みませんが、データ並列が単一の抽象から複数のハードウェア並列性へ橋渡しする位置にあることは押さえておいてください。

11.7 第II部のまとめ

これで第II部——ユーザに見える並列機能——が一通り揃いました。

• スレッドと同期（第6〜7章）：共有メモリ並列の基礎。
• ロックフリー（第8章）：進行保証を高める発展手法。
• メッセージパッシング（第9章）：共有しないことで競合を避ける。
• 軽量スレッドとスケジューラ（第10章）：大量並行の土台。
• データ並列（本章）：規則的計算を素直に並列化する。

しかし、ここまでの機能をユーザに提供しても、処理系はまだ並列実行に耐えられません。なぜなら、処理系自身の内部にも、第5章の @globals や @stack に相当する共有状態が無数にあるからです。第III部では、その「一見並列と無関係に見える」内部を一つひとつ点検し、並列実行に耐えるよう作り直していきます。

第III部　処理系内部を並列実行に耐えさせる

ユーザに見えるスレッドやチャネルを用意しただけでは、処理系は並列実行に耐えられません。問題は、一見並列とはまったく関係なく見える処理系内部のあちこちに潜んでいます。

逐次実行を前提に作られた処理系には、グローバルに共有される状態が数えきれないほどあります。シンボル表、定数表、クラス階層、インターン文字列、メソッドキャッシュ、遅延初期化されるオブジェクト、参照カウント——これらはどれも、単一スレッドなら何の問題もなく動きますが、複数スレッドから同時に触られた瞬間に壊れます。

第III部では、これら「内部の地雷」を棚卸しし、GC やアロケータの競合、false sharing、そして多くの処理系が採用してきた GIL／GVL という「逃げ」とその代償を扱います。最後に、そもそもオブジェクトを共有させない、という設計（隔離・所有権・型による保護）へとつなげます。

12. グローバル共有状態の棚卸し

第II部までで、ユーザに見える並列機能は揃いました。しかし第5章の最後で予告したとおり、それだけでは処理系は並列実行に耐えられません。逐次実行を前提に作られた処理系は、内部に無数の グローバル共有状態 を抱えているからです。本章は第III部の出発点として、その共有状態を棚卸しします。「一見、並列とは関係ない」これらの箇所こそが、並列化で最初に壊れる場所です。

12.1 「単一スレッド前提」という暗黙の設計

逐次処理系を書くとき、私たちは無意識に多くの仮定を置いています。「ある関数を実行中、他の誰もこの表を触らない」「初期化は起動時に一度だけ、誰も見ていないうちに済む」「このグローバル変数はいつ読んでも整合している」——これらはすべて、単一スレッドだから成り立つ仮定です。

並列化は、これらの仮定を一つ残らず無効にします。問題は、こうした仮定が コードのどこにも明示的に書かれていない ことです。「ここは排他が要る」とコメントされていればまだ良いほうで、たいていは「単に共有されないと思っていた」だけです。だから並列化の第一歩は、新機能の追加ではなく、既存の共有状態を見つけ出して列挙する という地道な棚卸しになります。

12.2 シンボル表とインターン文字列

多くの動的言語は、メソッド名や変数名を高速に比較するため、文字列を インターン（intern） します。同じ内容の文字列を 1 個の正規化された実体（シンボル）に統合し、以後はポインタ比較や整数 ID 比較で済ませる仕組みです。Ruby の Symbol、Java の文字列インターン、Lisp の symbol などがこれです。

インターンの実体は、たいてい「文字列 → ID」のグローバルなハッシュ表です。

# 概念図：グローバルなシンボル表
class SymbolTable
  def initialize; @table = {}; @next_id = 0; end

  def intern(str)
    @table[str] ||= (@next_id += 1)   # 無ければ新 ID を割り当てて登録
  end
end

この intern は、単一スレッドなら完璧です。しかし並列化すると、@table[str] ||= ... という read-modify-write が第5章そのものの競合を起こします。2 スレッドが同じ未登録文字列を同時に intern すると、別々の ID が振られて「同じ文字列に 2 つの ID」という不変条件違反になり、以後のポインタ比較がすべて狂います。最悪、ハッシュ表の内部構造（バケット配列のリサイズ中など）が壊れて処理系がクラッシュします。

シンボル表は典型的に 読み込みが圧倒的に多く、書き込み（新規 intern）は稀 です。この特性は、第8章で見た RCURCUの論文^{[Paul, 1998]} や read-write ロック（読みは共有、書きは排他）が効く場面です。「ほとんど読み、たまに書く」共有状態は、処理系のあちこちに現れる重要なパターンです。

12.3 定数表とクラス階層

オブジェクト指向言語の処理系は、クラスとその継承関係、定数、メソッド定義を表すグローバルな構造を持ちます。Ruby なら定数の探索表やクラスの祖先リスト（ancestors）、メソッドテーブルなどです。

これらが厄介なのは、実行中に変更されうる 点です。静的な言語ならクラス階層は起動後に固定できますが、Ruby のような動的言語では、実行中に class を再オープンしてメソッドを足したり、定数を代入したり、モジュールを include して祖先リストを書き換えたりできます。つまり「読み（メソッド探索）」と「書き（クラス定義の変更）」が同時に起こりえます。

# スレッド A: メソッドを呼ぶ（祖先リストを読みながら探索）
obj.some_method

# スレッド B: 同時にクラスを書き換える（祖先リストを変更）
class SomeClass
  include AnotherModule   # 祖先リストの再構築
end

メソッド探索の途中で祖先リストが組み替えられると、探索が壊れたリストをたどってクラッシュしたり、誤ったメソッドを呼んだりします。これは次章以降のメソッドキャッシュ（第14章）の無効化とも絡む、動的言語の並列化で最も神経を使う箇所のひとつです。

12.4 グローバルな可変状態のその他の例

棚卸しを続けると、処理系には驚くほど多くのグローバル可変状態があります。

これらに共通するのは、「処理系を速く・便利にするための仕掛け」が、ことごとく共有された可変状態である ことです。逐次処理系では、共有とキャッシュは性能の友でした。並列処理系では、それらが正しさの敵に転じます。

12.5 棚卸しの後の選択肢

共有状態を列挙したら、各箇所についてどう手を打つかを選びます。本書の他の章が、それぞれの選択肢に対応します。

1. ロックで守る（第7章）：最も単純。粒度が粗いと並列性を損なう。
2. 読み書き非対称にする（第8章）：read-write ロックや RCU。読みが多い表に有効。
3. スレッドローカルにして共有をやめる（第6章）：各スレッドが自分のコピーを持つ。整合が要らない状態に有効。
4. 不変（immutable）にする：一度作ったら変更しない。読みは同期不要になる。
5. そもそも共有させない（第17章）：オブジェクトを隔離し、共有状態を設計から消す。
6. 大きな 1 個のロックで全部守る（第16章の GIL/GVL）：実装は楽だが並列性を捨てる「逃げ」。

次章では、棚卸しの中でも最大の難物——メモリ管理と GC に踏み込みます。アロケータとガベージコレクタは、すべてのオブジェクト確保・回収に関わる、処理系で最も頻繁に触られる共有状態だからです。

13. メモリ管理と GC

オブジェクトの確保と回収は、処理系で最も頻繁に行われる操作です。だからこそ、メモリ管理は並列化において最大の難所になります。アロケータは全スレッドが叩く共有資源であり、ガベージコレクタ（GC）はヒープ全体——すなわち全スレッドが触るオブジェクト——を相手にするからです。本章では、アロケータの競合、Stop-the-world から並行・並列 GC への発展、write barrier、そして false sharing を扱います。体系的な詳細は GC ハンドブックGC ハンドブック^{[Richard, 2011]}が決定版です。

13.1 アロケータの競合

オブジェクトを確保するたびに、アロケータは「空き領域のどこを使うか」を管理する内部構造を更新します。これが単一のグローバルなフリーリストだと、全スレッドの確保がそこに殺到し、ロック競合の巨大なボトルネックになります。オブジェクトを多用する言語では、確保は秒間に数百万回起こりえます。そこを 1 個のロックで直列化したら、コアを増やすほど競合が悪化しかねません。

定石は スレッドローカルなアロケータ です。各スレッドに専用の小さな割り当て領域（thread-local allocation buffer, TLAB などと呼ばれる）を渡し、その中での確保はロックなしの単純なポインタ加算で済ませます。バッファを使い切ったときだけ、グローバルなヒープからまとめて補充する（このときだけ同期する）のです。第6章の TLS と同じ発想——「共有しないことが最速の同期」——が、アロケータの心臓部に効いています。

# 概念図：スレッドローカルなバンプアロケータ
class ThreadLocalAllocator
  def initialize(global_heap)
    @global = global_heap
    @top = @limit = nil   # 自分専用の領域
  end

  def alloc(size)
    if @top.nil? || @top + size > @limit
      @top, @limit = @global.fetch_chunk   # ここだけグローバルと同期
    end
    addr = @top
    @top += size           # 普段はポインタを進めるだけ。ロック不要
    addr
  end
end

13.2 Stop-the-world GC とその限界

GC の最も単純な実装は Stop-the-world（STW） です。GC を始めるとき、すべてのアプリケーションスレッド（ミューテータと呼ぶ）を安全な地点で完全に停止させ、誰も動いていない静止状態でヒープを走査・回収し、終わったら全員を再開させます。

STW の利点は実装の単純さです。GC 中はヒープが変化しないので、「いまどのオブジェクトが生きているか」を競合を気にせず判定できます。逐次処理系の GC は、ほぼ例外なく STW です。

問題は 停止時間（pause time） です。ヒープが大きくなるほど、全スレッドを止める時間が伸びます。対話的なアプリやサーバでは、この「全員が固まる」時間が応答性を直撃します。さらに並列処理系では、STW のたびに全コアが遊ぶので、せっかくの並列性が GC のたびに帳消しになります。

gantt
    title Stop-the-world GC（全スレッドが GC 中に停止）
    dateFormat X
    axisFormat %s
    section ミューテータ1
        実行 :0, 3
        停止(GC) :crit, 3, 5
        実行 :5, 8
    section ミューテータ2
        実行 :0, 3
        停止(GC) :crit, 3, 5
        実行 :5, 8
    section GCスレッド
        回収作業 :active, 3, 5

13.3 並列 GC と並行 GC

STW を改善する方向は 2 つあり、混同されがちなので用語を厳密に区別します。

• 並列 GC（parallel GC）：STW で全員を止めるのは同じだが、GC 作業そのものを複数の GC スレッドで分担 して、停止時間を短くする。止めること自体は変えず、止まっている時間を縮める。
• 並行 GC（concurrent GC）：ミューテータを動かしたまま GC を進める。停止時間を限りなく小さくする（あるいは無くす）。最も難しい。

graph TD
    A[Stop-the-world GC<br/>全員止めて1スレッドで回収] --> B[並列 GC<br/>全員止めるが複数GCスレッドで分担]
    A --> C[並行 GC<br/>ミューテータを動かしたまま回収]
    B --> D[並列かつ並行 GC<br/>現代の高性能GC]
    C --> D

並行 GC が難しいのは、GC がヒープを走査している最中に、ミューテータがそのヒープを書き換えてしまう からです。GC が「このオブジェクトはもう誰からも参照されていない、回収しよう」と判断した直後に、ミューテータが生きているオブジェクトからそのオブジェクトへの参照を作ったら、生きているオブジェクトを誤って回収してしまいます（use-after-free）。動いている対象を数えながら回収する——走っている列車の車輪を数えるような難しさです。Doligez と Leroy による ML 向けの並行・世代別 GCDoligez-Leroy の並行GC^{[Damien, 1993]} は、この問題に正面から取り組んだ先駆的な研究です。

13.4 write barrier：GC とミューテータの協調

並行 GC（および世代別 GC）の要が write barrier（書き込みバリア） です。これは「オブジェクトの参照フィールドを書き換えるたびに、GC に小さな通知を入れる」仕掛けです。第4章のメモリバリアとは別概念なので注意してください（名前が紛らわしいですが、こちらは GC のための記録です）。

考え方はこうです。GC が走査済みのオブジェクトに、ミューテータが未走査オブジェクトへの新しい参照を書き込むと、GC はその参照を見逃しかねません。そこで参照を書き込む箇所すべてに「いま新しい参照を張ったよ」と GC に記録させるコードを挿入します。GC はその記録を頼りに、見逃しそうなオブジェクトを再走査します。

# 概念図：参照を書き込むたびにバリアを通す
def write_field(obj, field, new_value)
  obj.send("#{field}=", new_value)
  write_barrier(obj, new_value)   # GC へ「参照が変わった」と通知
end

write barrier は すべての参照書き込みに乗る ので、その実装の軽さが処理系全体の性能を左右します。重い barrier は、GC の停止時間を減らした分を、平常時のスローダウンで食い潰してしまいます。「平常時のオーバーヘッド」と「停止時間」のトレードオフが、GC 設計の中心的な緊張関係です。

13.5 false sharing：GC とアロケータに潜む性能の罠

最後に、正しさではなく 性能 の罠を扱います。第2章で触れた false sharing（偽共有） です。キャッシュは 64 バイト程度のキャッシュライン単位で動くので、別々のスレッドが更新する別々の変数が、たまたま同じキャッシュラインに同居すると、ハードウェアがそのラインを互いに奪い合い、激しく性能が落ちます。

GC とアロケータは false sharing の温床です。たとえば、各スレッドの確保カウンタや GC 統計を配列にまとめて置くと、隣り合う要素が同じラインに乗り、スレッドごとの更新が衝突します。対策は パディング（padding）——意図的に隙間を空けて、各スレッドが触るデータを別々のキャッシュラインに分離することです。

# 各スレッドの統計を、キャッシュライン境界に合わせて分離する（イメージ）
class PerThreadStats
  # 1要素を64バイト境界にアラインし、隣同士が同じラインに乗らないようにする
  # （実際の処理系では構造体のアラインメント指定や手動パディングで行う）
end

false sharing は、ソースを読んでも「共有していない」ので見つけにくく、プロファイラ（第19章）でキャッシュミスを測って初めて気づくことが多い罠です。並列化したのに思ったほど速くならないとき、まず疑うべき容疑者のひとつです。

13.6 本章のまとめ

• アロケータはスレッドローカルバッファで競合を避けるのが定石。「共有しない確保」が高速。
• STW GC は単純だが、全スレッドを止めるため並列性と応答性を損なう。
• 並列 GC（止めて分担）と並行 GC（止めずに回収）は別概念。後者が最も難しい。
• 並行 GC は write barrier でミューテータと協調する。平常時コストと停止時間のトレードオフが核心。
• false sharing は GC・アロケータの統計などに潜む性能の罠。パディングで分離する。

次章では、処理系の速度を支えるもうひとつの仕掛け——各種キャッシュと遅延初期化 が、並列化でどう壊れるかを扱います。GC と同じく「速くするための仕掛けが、共有された可変状態である」という構図が再び現れます。

14. 各種キャッシュと遅延初期化

高速な処理系は、キャッシュの塊です。一度計算した結果を覚えておき、次回は計算を省く——この最適化が、メソッド呼び出しから定数参照、正規表現に至るまで、処理系のあらゆる層に仕込まれています。そして第12章で述べたとおり、これらのキャッシュはことごとく共有された可変状態です。本章では、メソッドキャッシュ・インラインキャッシュと、遅延初期化（lazy initialization）が並列化でどう壊れ、どう守るかを扱います。

14.1 メソッドキャッシュ：探索結果を覚える

動的言語では、obj.foo という呼び出しのたびに「obj のクラスから始めて祖先リストをたどり、foo の定義を探す」というメソッド探索（method lookup）が必要です。これは毎回行うには高くつくので、処理系は探索結果をキャッシュします。

最も基本的なのが グローバルメソッドキャッシュ——「(クラス, メソッド名) → 見つかったメソッド」の対応表です。

# 概念図：グローバルメソッドキャッシュ
class MethodCache
  def lookup(klass, name)
    key = [klass, name]
    @cache[key] ||= search_ancestors(klass, name)  # 無ければ探索して記憶
  end
end

並列化すると、この @cache[key] ||= ... が第5章の競合を起こします。さらに深刻なのは 無効化（invalidation） です。第12章で見たとおり、Ruby ではクラスが実行中に書き換わります。include でメソッドが追加されたら、キャッシュは古くなるので捨てなければなりません。マルチスレッドでは「あるスレッドがキャッシュを読んでいる最中に、別スレッドがクラスを書き換えて無効化する」という競合が起き、古いメソッドを呼ぶ・存在しないメソッドを呼ぶ・キャッシュ構造が壊れる といった事態を招きます。

14.1.1 インラインキャッシュ

メソッドキャッシュをさらに高速化したのが インラインキャッシュ（inline cache, IC） です。グローバルな表を引く代わりに、呼び出し箇所そのもの（バイトコードや機械語の命令の隣）に「前回このクラスだったら、このメソッド」という情報を直接埋め込みます。多くの呼び出しは同じクラスのオブジェクトに対して繰り返されるので、これがよく当たります。

# 呼び出し箇所に埋め込まれたインラインキャッシュ（概念）
call_site:  obj.foo
  cached_class:  String     # 前回の受け手のクラス
  cached_method: String#foo  # そのときのメソッド
  # 今回も obj が String なら探索を完全に省ける

インラインキャッシュは、各呼び出し箇所に分散している分、グローバルキャッシュよりロック競合を局所化できる利点があります。しかし無効化の難しさは同じか、それ以上です。クラス階層が変わったら、影響を受ける全呼び出し箇所のキャッシュを無効化しなければなりません。多くの処理系は 世代カウンタ（global serial number） を使い、「クラス階層が変わるたびに大域カウンタを増やし、各 IC は記録時のカウンタと現在のカウンタを比較して、ずれていたら再探索する」という方式で、個別の無効化を避けます。このカウンタの更新と読み取りは atomic に行う必要があります。

14.2 遅延初期化（lazy initialization）

遅延初期化 は、「必要になるまで作らない」最適化です。起動を速くし、使われない資源を作らずに済むので広く使われます。典型は次の形です。

def config
  @config ||= load_config_from_disk   # 初回だけ読み込み、以後は使い回す
end

単一スレッドなら完璧ですが、並列化すると @config ||= ... は危険です。@config がまだ nil のときに 2 スレッドが同時に入ると、両方が load_config_from_disk を実行します。load に副作用があれば二重実行の害が出ますし、戻り値が一意であるべきオブジェクト（シングルトン）なら、2 つできてしまって不変条件が壊れます。

14.2.1 ダブルチェックロッキングの罠

素朴な対策は「nil なら、ロックを取って、もう一度確認してから初期化する」——ダブルチェックロッキング（double-checked locking） です。

def config
  return @config if @config            # (1) ロックなしの速い確認
  @lock.synchronize do
    @config ||= load_config_from_disk  # (2) ロック内で確実に1回だけ
  end
  @config
end

ここに、メモリモデル（第4章）が牙をむく有名な落とし穴があります。(1) のロックなしの読みで「@config が非 nil」を観測したとき、@config が指すオブジェクトの初期化が完了しているとは限らない のです。書き手が「オブジェクトを構築 → @config に代入」の順で行っても、第4章で見たリオーダリングにより、読み手からは「@config に代入済み・しかし中身は未構築」という半端な状態が見えうるからです。ダブルチェックロッキングが「壊れたパターン」として悪名高いのは、まさにこの理由です。Java メモリモデルJava メモリモデル^{[Jeremy, 2005]} の議論は、この問題を正しく扱える保証（volatile や final フィールドの意味論）を整理した動機のひとつでもありました。

14.2.2 「一度だけ」を処理系が保証する

このパターンは頻出なので、多くの環境が「一度だけ確実に初期化する」プリミティブを用意しています。pthreads の pthread_once、C++ のローカル static 変数の初期化保証、各言語の lazy/once 構文などです。処理系の実装者は、危ういダブルチェックロッキングを各所にばらまく代わりに、検証済みの「once」プリミティブを提供し、内部でもそれを使うべきです。

# 処理系が提供すべき安全な once（概念）
@config_once = Once.new
def config
  @config_once.call { load_config_from_disk }  # 何スレッドから来ても初期化は1回
end

14.3 処理系内部に潜む遅延初期化

遅延初期化は、ユーザコードだけでなく処理系内部のいたるところに潜みます。

• 正規表現のコンパイル結果のキャッシュ：同じパターンの再コンパイルを避ける。
• リテラルの正規化：凍結文字列リテラルや、生成済みの定数オブジェクトの使い回し。
• クラスの内部メタデータ：メソッドテーブルの拡張、内部 ID の割り当て。
• JIT のコンパイル済みコード：あるメソッドが「熱く」なったら機械語にコンパイルし、その結果を差し込む。

最後の JIT は特に注意が要ります。あるスレッドがメソッドをコンパイルしている最中に、別スレッドが同じメソッドを実行・あるいはコンパイル結果を差し込もうとすると、実行中のコードを書き換えるという極めて危険な操作になります。コンパイル済みコードの公開（publish）は、第4章の release セマンティクスで「完全に書き終えてから差し込む」ことを保証しなければなりません。

次章では、もうひとつの厄介な共有状態——参照カウント と、I/O・例外・シグナルの排他を扱います。とりわけ参照カウントの atomic 化は、「正しくはできるが、その代償が重い」典型例として、GIL/GVL（第16章）への重要な布石になります。

15. 参照カウント、I/O・例外・シグナルの排他

本章では、並列化で「正しくはできるが、その代償が重い」処理系内部の代表例を 2 つ扱います。ひとつは 参照カウントの atomic 化、もうひとつは I/O・例外・シグナル という、見落とされがちだが排他が必要な箇所です。とくに参照カウントの話は、なぜ多くの処理系が GIL/GVL（第16章）という「逃げ」を選んだのかを理解する鍵になります。

15.1 参照カウント方式の GC

GC の方式には、第13章で扱った「到達可能性をたどる」トレース型のほかに、参照カウント（reference counting） があります。各オブジェクトが「自分を参照している数」を持ち、参照が増えれば +1、減れば −1、0 になったら即座に解放する方式です。CPython がこの方式を採っており、Swift（ARC）や多くの C++ のスマートポインタもこれです。

# 概念図：参照カウント
def incref(obj); obj.refcount += 1; end
def decref(obj)
  obj.refcount -= 1
  free(obj) if obj.refcount == 0   # 0 になったら回収
end

参照カウントの利点は、回収が即座で、停止時間が分散し、実装が比較的素直なことです。欠点は、循環参照を回収できないこと、そして——本章の主題である——並列化のコストが高い ことです。

15.2 なぜ atomic 化が重いのか

obj.refcount += 1 は、第5章でさんざん見た read-modify-write です。複数スレッドが同じオブジェクトを同時に参照・解放すると、カウントの increment/decrement が競合し、カウントが狂います。カウントが過小評価されれば、まだ使われているオブジェクトを解放して use-after-free を起こし、過大評価されればメモリリークになります。前者は処理系のクラッシュに直結する最悪のバグです。

正しくするには、increment と decrement を atomic 操作（第7章の fetch_and_add や CAS）にする必要があります。これ自体は技術的に簡単です。問題はその 頻度 です。

参照カウントは、オブジェクトを触るたびに——変数に代入するたび、関数に渡すたび、コンテナに入れるたび——更新されます。処理系の中で 最も頻繁に実行される操作のひとつ なのです。その一つひとつを atomic 命令にすると、たとえ競合がなくても、atomic 命令自体のコスト（メモリバリアやキャッシュコヒーレンシのトラフィック、第2章）が全体に重くのしかかります。

graph LR
    A[通常の incref/decref<br/>レジスタ操作なみに速い] -->|atomic 化| B[atomic incref/decref<br/>バリア＋コヒーレンシで数十倍遅い]

15.3 代償を減らす工夫

この代償を減らす技法がいくつかあります。

• バイアス付き参照カウント（biased reference counting）：オブジェクトを最初に作ったスレッド（所有者）からの操作は非 atomic な専用カウンタで、他スレッドからの操作だけ atomic な共有カウンタで数える。ほとんどの操作が所有者からなので、atomic を大幅に減らせる。
• 遅延カウント／合体：短命な参照（一時変数など）のカウント増減を、まとめて相殺してから反映する。
• 不変オブジェクトの除外：nil・true・小さな整数・凍結リテラルなど、解放されない不変オブジェクトはカウントを更新しない。

CPython の no-GIL 化（第16・20章）PEP 703^{[Sam, 2023]} は、まさにこの「参照カウントを並列化しても遅くしない」ための工夫の集大成です。バイアス付き参照カウント、不変オブジェクトの恒久化（immortalization）、遅延カウントなどを組み合わせて、GIL を外しても単一スレッド性能を落とさないことを目指しています。「参照カウントの atomic 化の代償」がいかに重く、それを軽くするのにどれだけの工夫が要るかを示す、生きた実例です。

15.4 I/O の排他

参照カウントから話を変えて、見落とされがちな共有資源を扱います。まず I/O です。

複数スレッドが同じ出力先（たとえば標準出力）に同時に書き込むと、出力が混ざります。「Hello\n」と「World\n」が HeWolrllod\n のように交錯するのです。これはバッファが共有された可変状態だからで、第5章のスタック破壊と同じ構図です。処理系（やランタイムライブラリ）は、I/O ストリームへの書き込みをロックで保護し、少なくとも 1 回の書き込みが分割されないようにする責務を負います。

さらに厄介なのが、ファイルディスクリプタの 位置（オフセット） の共有です。同じファイルを複数スレッドが読み書きすると、「read で進んだ位置」が共有され、互いの読み書き位置を踏み合います。対策として、位置を持たない pread/pwrite（読み書き位置を引数で渡す）を使う、ファイルハンドルをスレッドごとに分ける、といった設計が必要です。

15.5 例外とシグナルの排他

最後に、制御の流れに関わる 2 つの厄介者を扱います。

例外 の処理は、巻き戻し（unwinding）の途中状態という、危うい一時状態を持ちます。第6章で触れたとおり、例外がスレッドの境界を越えるときの扱い（子スレッドの例外を join 側へ渡す）は設計判断が要ります。スレッドごとに「現在処理中の例外」の状態を持たせる（TLS、第6章）のが基本で、これを共有すると巻き戻しが交錯して壊れます。

シグナル（signal） はさらに難物です。シグナルは UNIX で非同期にプロセスへ届く通知（SIGINT での中断など）で、2 つの意味で並行性と衝突します。

1. どのスレッドが受けるか：マルチスレッドプロセスでは、シグナルがどのスレッドに配送されるかは制御が難しい。処理系はたいてい「1 本の専用スレッドだけがシグナルを受ける」よう構成し、他スレッドではマスクします。
2. シグナルハンドラの中でできることが極端に限られる：シグナルハンドラは、実行中の任意の地点に割り込みます。その地点でロックを保持していたら、ハンドラ内で同じロックを取ろうとしてデッドロックします。だからハンドラ内では async-signal-safe な操作（限られたシステムコールなど）しか使えません。

定石は self-pipe トリック——ハンドラ内では「パイプに 1 バイト書く」という安全な操作だけ行い、実際の処理は通常のスレッドがそのパイプを読んで行う、という方式です。ハンドラを極限まで薄くし、危険な処理を通常の実行文脈に逃がすのです。

sequenceDiagram
    participant OS
    participant H as シグナルハンドラ(薄い)
    participant T as 通常スレッド
    OS->>H: SIGINT 到来（任意の地点に割り込む）
    H->>H: パイプに1バイト書くだけ（安全）
    H-->>OS: 即座に戻る
    T->>T: パイプを読んで、本来の処理を安全に実行

15.6 本章のまとめ

• 参照カウントの atomic 化は、正しさは簡単だが頻度ゆえに代償が重い。「速いか遅いか」の問題。
• バイアス付き参照カウントや不変オブジェクトの除外で代償を減らす。CPython の no-GIL がその実例。
• I/O は出力の交錯やファイル位置の共有を、ロックや位置指定 API で守る必要がある。
• 例外の途中状態はスレッドローカルに持つ。シグナルは専用スレッドで受け、ハンドラは self-pipe で薄くする。

ここまで第III部で見てきた共有状態——シンボル表、GC、キャッシュ、参照カウント、I/O、シグナル——は、どれも「並列化すると壊れるか、遅くなる」箇所でした。これらすべてを一度に回避する「逃げ」が存在します。次章では、その GIL/GVL という大きな 1 個のロックと、それを外したときに第III部の問題が一斉に噴き出す、という物語を扱います。

16. GIL/GVL という「逃げ」とその代償

第III部でここまで見てきたのは、処理系内部に潜む膨大な共有状態——シンボル表、クラス階層、GC、各種キャッシュ、参照カウント——が、並列化でどれも壊れる、という事実でした。これらを一つひとつ正しく作り直すのは、気の遠くなる作業です。そこで多くの処理系が選んだのが、たった 1 個の巨大なロックで全部まとめて守る という選択でした。それが GIL/GVL です。本章は第III部の山場として、この「逃げ」の正体と代償を物語ります。

16.1 GIL/GVL とは何か

GIL（Global Interpreter Lock） あるいは GVL（Giant VM Lock / Global VM Lock） は、「処理系の中で、一度に 1 つのスレッドしか Ruby/Python コードを実行できない」ようにする、プロセス全体で 1 個の大きなロックです。CPython の GIL、CRuby の GVL が代表例です（呼び名は違いますが本質は同じなので、本章では GVL と総称します）。

第5章の最後で、Tiny VM 全体を 1 つの Monitor で囲って正しくした例を思い出してください。GVL はまさにあれの処理系全体版です。スレッドはコードを実行する前に GVL を取得し、実行を終える（あるいは一定間隔で譲る）と解放します。

# GVL の概念（実際は処理系の C 実装の中にある）
def run_bytecode(thread)
  acquire_gvl   # ここを通れるのは一度に1スレッドだけ
  begin
    # バイトコードを実行（この間、他スレッドは Ruby コードを実行できない）
  ensure
    release_gvl
  end
end

gantt
    title GVL があるときの実行（コード実行は常に1スレッド）
    dateFormat X
    axisFormat %s
    section スレッド1
        実行(GVL保持) :0, 2
        待ち :crit, 2, 4
        実行(GVL保持) :4, 6
    section スレッド2
        待ち :crit, 0, 2
        実行(GVL保持) :2, 4
        待ち :crit, 4, 6

16.2 なぜ GVL は「うまい逃げ」なのか

GVL には、見過ごせない実利があります。

第一に、第III部の問題がすべて消えます。一度に 1 スレッドしかコードを実行しないので、シンボル表もクラス階層もキャッシュも参照カウントも、同時に 2 スレッドから触られることがありません。第12〜15章で苦労した共有状態を、まったく作り直さずに済むのです。

第二に、単一スレッド性能が落ちません。参照カウント（第15章）を atomic にする必要がないので、逐次実行は GVL なしと同じ速度で走ります。ロックの取得・解放のコストは、スレッドが 1 本ならほぼ無視できます。

第三に、C 拡張が安全に書けます。Ruby も Python も、C で書かれた拡張ライブラリの巨大な生態系を持ちます。それらの C コードは「自分が動いている間、処理系の状態は誰も触らない」という GVL の保証に暗黙に依存しています。GVL は、無数の既存 C 拡張を並行性の悪夢から守る防波堤でもあるのです。

第四に、I/O では並行性が活きます。多くの処理系は、ブロックする I/O やスリープの間は GVL を解放します。だから「複数スレッドでファイルを読む・ネットワークを待つ」ようなワークロードでは、GVL があっても並行に進めます。GVL が並列性を奪うのは、あくまで CPU を使う計算 の部分です。

16.3 GVL の代償

利点が大きいぶん、代償も大きい。最大の代償は明白です。CPU バウンドな計算が、コアを増やしても速くならない。8 コアあっても、Ruby/Python コードを実行できるのは常に 1 スレッドだけだからです。第1章で述べた「マルチコアで速くしたい」という根本的な動機に、GVL は真っ向から反します。

xychart
    title "CPUバウンド処理: コア数 vs スループット"
    x-axis ["1コア", "2コア", "4コア", "8コア"]
    y-axis "相対スループット" 0 --> 8
    line [1, 1, 1, 1]
    bar [1, 1, 1, 1]

上の図のように、GVL 下では CPU バウンド処理のスループットはコアを増やしても横ばいです。これは第19章で扱う Amdahl の法則Amdahl の法則^{[Gene, 1967]} の極端な形——並列化できる割合が実質ゼロ——と見なせます。

さらに、GVL は 公平性とレイテンシ の問題も抱えます。GVL を握ったスレッドがいつ手放すか、待っているスレッドにどう渡すか、というスケジューリングが難しい。手放しが遅いと他スレッドが飢え、頻繁すぎると切り替えコストがかさみます。CRuby はタイマースレッドで GVL の保持時間を制限するなど、地道な調整を重ねてきました。

16.4 「外すと第III部が全部問題化する」

ここが本章の核心であり、本書全体の構図を映す物語です。GVL は第III部の問題を「隠して」いただけで、「解決して」はいません。GVL を外そうとした瞬間、第12〜15章で見た問題が 一斉に・すべて 顔を出します。

• シンボル表・インターン（第12章）→ 並行アクセスで破壊される
• クラス階層・定数表（第12章）→ 探索中の組み替えで壊れる
• メソッド／インラインキャッシュ（第14章）→ 無効化が競合する
• 遅延初期化（第14章）→ 二重初期化・未初期化観測
• GC（第13章）→ 並行・並列 GC への作り直し、write barrier
• 参照カウント（第15章）→ atomic 化の重い代償
• 無数の C 拡張 → GVL の暗黙の保証を失い、書き直しが必要

graph TD
    GVL[GVL を外す] --> A[シンボル表が壊れる]
    GVL --> B[クラス階層・キャッシュが壊れる]
    GVL --> C[参照カウントの atomic 化]
    GVL --> D[GC の並行化]
    GVL --> E[既存 C 拡張が動かない]
    A & B & C & D & E --> F[第III部の全課題が一斉に噴出]

つまり GVL とは、第III部全体を「あとで払う」と先送りにした借金のようなものです。借りている間は快適ですが、外す（返す）ときに利息ごと一括で請求されます。Python の no-GIL 化PEP 703^{[Sam, 2023]} が、提案から実装、安定化まで何年もの大仕事になっているのは、この借金の大きさそのものです。

16.5 GVL を外す道、外さない道

処理系がこの借金とどう向き合うかには、いくつかの道があります。

1. GVL を外す（free-threading）：第III部の全課題を正面から解く。CPython の no-GILPEP 703^{[Sam, 2023]} がこの道。互換性（特に C 拡張）の維持が最大の難所。
2. 複数プロセスで回避する：プロセスを分ければアドレス空間が別なので共有状態の問題がない。ただしプロセス間通信とメモリ二重持ちのコストがかかる（Python の multiprocessing、Ruby の多プロセス Web サーバ）。
3. 隔離された複数の処理系インスタンス：1 プロセス内に、状態を共有しない複数の「ミニ処理系」を持ち、それぞれが自分の GVL を持つ。Ruby の RactorRactor のドキュメント^{[Koichi, 2020]} がこの道で、GVL は「Ractor ごと」になります。共有しないことで第III部の問題を回避しつつ、1 プロセス内で並列実行する——第17章のオブジェクト共有モデルへ直結します。

16.6 本章のまとめ

• GVL は「一度に 1 スレッドしかコードを実行できない」大きな 1 個のロック。第III部の共有状態問題を一括で回避する。
• 利点：内部の作り直し不要、単一スレッド性能を保つ、C 拡張が安全、I/O では並行できる。
• 代償：CPU バウンド処理がコア数で速くならない（Amdahl の極端形）、公平性・レイテンシの調整が難しい。
• GVL を外すと、第12〜15章の問題が一斉に噴出する。GVL は第III部を先送りした「借金」。
• 向き合い方は free-threading・多プロセス・隔離インスタンス（Ractor）の 3 つ。四者のトレードオフがある。

最後の「隔離インスタンス」という道——共有させないことで安全と並列を両立する——は、第III部の締めくくりにふさわしい発想です。次章では、この オブジェクト共有モデル（隔離・コピー・所有権・型による保護）を体系的に扱います。

17. オブジェクト共有モデル：隔離・所有権・型で守る

第III部を通じて繰り返し現れた教訓は、「最良の同期は、同期しなくて済むように設計を変えること」でした。本章はその発想を設計原理にまで高めます。すなわち、そもそもオブジェクトを共有させない、あるいは共有してよいオブジェクトを限定し、それを型で強制する ——という、並列処理系の最も根本的な設計判断です。GVL を外す（第16章）難しさの大半が「無秩序な共有」に由来する以上、共有そのものを設計で律することは、問題を末端で潰すのではなく根で断つアプローチです。

17.1 共有の何が問題だったのか

第5章から第16章まで、データ競合のあらゆる事例は、煎じ詰めれば一点に帰着します。可変（mutable）なオブジェクトを、複数スレッドが同時に、同期なしに触る こと——この 3 要素が揃ったときだけ競合は起きます。逆に言えば、3 要素のどれか 1 つでも崩せば競合は構造的に消えます。

graph TD
    A[可変である] --> X{データ競合}
    B[複数スレッドが触る] --> X
    C[同期なし] --> X
    X -.どれか1つ崩せば消える.-> Y[安全]

本章で扱う各アプローチは、この 3 要素のどれを崩すかで整理できます。不変にする（可変を崩す）、隔離・所有権（複数アクセスを崩す）、型で同期を強制（同期なしを崩す）。順に見ていきます。

17.2 不変性：可変であることをやめる

最も単純な解は、オブジェクトを 不変（immutable） にすることです。一度作ったら誰も書き換えないなら、何スレッドが同時に読んでも競合しません。読み取りだけなら同期は不要だからです。関数型言語が並列化と相性がよいのは、データが基本的に不変だからにほかなりません。

Ruby でも、凍結（freeze）した文字列やオブジェクトは安全に共有できます。第16章で触れた RactorRactor のドキュメント^{[Koichi, 2020]} は、深く凍結された不変オブジェクト（および特別な共有可能オブジェクト）だけを、複数の Ractor 間で参照共有してよい、と定めています。

CONFIG = { timeout: 30, retries: 3 }.freeze   # 凍結＝不変
# 不変なので、何スレッド（何 Ractor）から読んでも安全

不変性の代償は、更新がコピーになることです。「1 要素だけ変えたい」ときも新しいオブジェクトを作るので、素朴にやるとコストがかさみます。これを永続データ構造（persistent data structure、変更時に共有部分を再利用する）で緩和するのが、関数型言語の定石です。

17.3 隔離とコピー：複数アクセスをやめる

不変にできない（更新が本質的に必要な）オブジェクトには、隔離（isolation） を使います。各実行主体に状態を閉じ込め、他からは直接触れさせない。第9章のアクター、第16章の Ractor がこれです。隔離されたオブジェクトは、たとえ可変でも、常に 1 つの主体しか触らないので競合しません。

隔離モデルでは、データを渡すときに 2 つの選択肢があります。

• コピー（copy）：送るときに値を複製する。送り手と受け手が別々の実体を持つので、以後どちらが変更しても干渉しない。安全だが、大きなデータでは複製コストが高い。
• 所有権の移動（move / ownership transfer）：実体は 1 つのまま、「触ってよい主体」を送り手から受け手へ移す。送り手は渡した後そのオブジェクトに触れなくなる。コピー不要で速いが、「移動後に送り手が触らない」ことを保証する仕組みが要る。

graph LR
    subgraph コピー
        S1[送り手: A] -->|複製| R1[受け手: A のコピー]
    end
    subgraph 所有権移動
        S2[送り手: A 失効] -.実体は1つ.-> R2[受け手: A を所有]
    end

Ractor のメッセージ送信は、まさにこの 2 つを区別します。send でコピーを渡すか、Ractor.make_shareable や move 送信で所有権を移すか。所有権を移したオブジェクトに送り手が触ろうとするとエラーになります——「移動後は触れない」を実行時に強制するのです。

17.4 所有権を型で守る：Rust の借用

隔離やコピーは安全ですが、「本当はこのデータを複数箇所から効率よく触りたい」場合には窮屈です。Rust は別の道を選びました。共有を許しつつ、コンパイル時の型システムで競合を不可能にする のです。

Rust の所有権システムの核は、次の規則です。

• 各値には唯一の所有者がいる。所有者がスコープを抜けると値は破棄される。
• 値への参照（借用、borrow）には 2 種類ある：不変借用（&T、共有参照） は同時に何個でも持てるが書き換えられない。可変借用（&mut T、排他参照） は同時に 1 つしか持てないが書き換えられる。
• 「複数の共有参照」と「1 つの排他参照」は同時に存在できない。

// Rust: コンパイラが競合を弾く
let mut data = vec![1, 2, 3];
let r1 = &data;        // 不変借用（読み取り）
let r2 = &data;        // 不変借用は同時に複数 OK
// let w = &mut data;  // ← これはコンパイルエラー：
//                        共有借用がある間は可変借用できない

この規則は、まさに第8章で触れた read-write の非対称性（読みは共有、書きは排他）を、実行時のロックではなくコンパイル時の型検査で 強制したものです。「複数の読み手 XOR 1 つの書き手」が型レベルで保証されるので、データ競合は コンパイルが通った時点で原理的に存在しません。Rust はこれを “fearless concurrency（恐れない並行性）” と呼びます。この所有権システムが本当に健全（安全）であることは、RustBeltRustBelt の論文^{[Ralf, 2018]} によって形式的に証明されています。

17.5 型で通信プロトコルを守る：セッション型

所有権が「データを誰が触れるか」を型で守るなら、セッション型（session types） は「通信の順序」を型で守ります。Honda らが提案した概念ですセッション型の論文^{[Kohei, 1998]}。

第9章のチャネル通信には、データ競合とは別種のバグがありました。送受信の食い違い（送るべきときに受けようとする）、プロトコル違反（ログインの前にデータを要求する）、デッドロックなどです。セッション型は、チャネルに「このチャネルでは、まず int を送り、次に string を受け取り、then 終了」といった 通信の筋書き（プロトコル）を型として付与 し、その筋書きから外れた通信をコンパイル時に弾きます。

# セッション型のイメージ（疑似記法）
# サーバ側のプロトコル型: ?Int . !String . end
#   = まず Int を受け取り、次に String を送り、終了する
# クライアント側は、その双対（dual）: !Int . ?String . end
#   = まず Int を送り、次に String を受け取る
# 両者が双対でなければコンパイルエラー

セッション型は、共有メモリの競合ではなく、メッセージパッシングの正しさ を型で保証する道具です。第9章で「メッセージパッシングはバグの種類を移し替える（止まるバグになる）」と述べましたが、セッション型はその移し替えた先のバグすら、型で防ごうとする試みです。

17.6 設計判断の地図

本章で見たアプローチを、「何を犠牲にして何を得るか」で並べます。

これで第III部は終わりです。処理系内部の共有状態を棚卸しし（第12章）、GC・キャッシュ・参照カウントを点検し（第13〜15章）、GVL という逃げとその代償を理解し（第16章）、最後に共有そのものを設計で律する道（本章）を見ました。第IV部では、こうして作った並列処理系を どう検証し、どう評価するか、そして実在の処理系がこれらの選択をどう具現化しているかを扱います。

第IV部　検証・評価とケーススタディ

並列処理系は「動いているように見える」ことと「正しい」ことの隔たりが、逐次処理系よりはるかに大きい世界です。データ競合は、テストでは再現せず、本番の高負荷時だけ顔を出すことがあります。だからこそ、検証と評価の技術が決定的に重要になります。

第IV部では、データ競合を自動検出するツール（ThreadSanitizer など）、決定的実行や record/replay、モデル検査といったデバッグ手法を紹介します。続いて性能評価の基礎——Amdahl の法則と Gustafson の法則、スケーラビリティの測り方、false sharing の実測——を扱います。

最後に、本書で学んだ概念が現実の処理系でどう具現化しているかを、Go ランタイム、Erlang/Elixir の BEAM、Java の仮想スレッド（Project Loom）、Ruby の GVL から Ractor への歩み、そして CPython の no-GIL という 5 つのケーススタディで横断的に振り返ります。

18. デバッグとテスト：競合をどう捕まえるか

並列処理系のバグは、逐次処理系のバグとは質が違います。データ競合は、実行のたびに変わるインターリーブの、特定の組み合わせでだけ顔を出します。テストでは再現せず、本番の高負荷時だけ起き、デバッガを当てるとタイミングが変わって消える——いわゆる ハイゼンバグ（Heisenbug） です。本章では、この捕まえにくい敵を捕まえるための技術を、自動検出・決定的実行・モデル検査の 3 系統に整理します。

18.1 なぜ普通のテストでは足りないのか

逐次プログラムのテストは「同じ入力なら同じ結果」を前提にできます。並列プログラムではこの前提が崩れます。同じ入力でも、スレッドのスケジューリングという観測しにくい要因で結果が変わるからです。

# このテストは「たまたま通る」かもしれない
def test_counter
  counter = SharedCounter.new
  10.times.map { Thread.new { 1000.times { counter.increment } } }.each(&:join)
  assert_equal 10_000, counter.value
end

このテストが通っても、競合が無いことの証明にはなりません。たまたま壊れるインターリーブを踏まなかっただけかもしれない。「テストが通る」は「競合が無い」を意味しない ——これが並列デバッグの出発点です。だから「実行して結果を見る」以外の、より強力な道具が要ります。

18.2 データ競合検出ツール

最も実用的な道具が、データ競合検出器（data race detector） です。プログラムを動かしながら、メモリアクセスと同期操作を監視し、「同期で順序づけられていない並行アクセス（うち少なくとも一方が書き込み）」を見つけ出します。第4章で定義したデータ競合の定義を、そのまま機械が検査するのです。

18.2.1 happens-before 方式と lockset 方式

検出器の中核アルゴリズムには 2 系統あります。

• happens-before 方式：第4章の happens-before 関係を追跡し、2 つのアクセスの間に同期の鎖が無ければ競合と判定する。正確（偽陽性が少ない）だが、実際に踏んだインターリーブでしか検出できない。
• lockset 方式：各共有変数について「アクセス時に共通して保持されていたロックの集合」を追跡し、共通ロックが空になったら「保護されていない」と警告する。実際の競合を踏まなくても疑わしい箇所を見つけられるが、偽陽性が出やすい。

実用ツールは両者を組み合わせたハイブリッドが主流です。Google の ThreadSanitizer（TSan）ThreadSanitizer の論文^{[Konstantin, 2009]} はその代表で、ハイブリッドアルゴリズムでデータ競合を検出します。後継の研究 FastTrackFastTrack の論文^{[Cormac, 2009]} は、happens-before の追跡を「各変数に完全なベクタ時計を持たせる」素朴な方式から、ほとんどの場合に定数サイズの情報（epoch）で済ませる方式へ高速化し、精度を保ったまま実用的な速度を実現しました。

# ThreadSanitizer 的なツールにかけると、第5章の Tiny VM の競合が報告される（イメージ）
#   WARNING: data race
#     Write of size 8 by thread T1 at 0x... (globals[:counter])
#     Previous read of size 8 by thread T2 at 0x...
#     ロック保持: なし

18.2.2 動的検出の限界

ただし、動的検出には原理的な限界があります。実際に実行された経路の競合しか見つけられない こと、そして監視のオーバーヘッドが大きい（TSan で数倍〜十数倍遅くなる）ことです。実行されなかったインターリーブに潜む競合は見逃します。だからこそ、次に述べる「再現性を取り戻す」「網羅的に調べる」技術が補完として重要になります。

18.3 決定的実行と record/replay

ハイゼンバグの最大の苦しみは、再現しない ことです。これに対する 2 つの処方箋があります。

決定的実行（deterministic execution） は、スケジューリングを固定し、同じ入力なら必ず同じインターリーブで走るようにする技術です。スケジューラを制御下に置き、スレッド切り替えの地点を再現可能にします。テスト時にスケジューリングのシード（種）を変えながら多数のインターリーブを系統的に試せば、「運任せ」を「網羅に近い探索」へ変えられます。

record/replay（記録・再生） は、一度の実行で起きた非決定的な出来事（スレッド切り替え、I/O の結果、シグナルの到来など）をすべて記録し、後でそのログを使って まったく同じ実行を再生 する技術です。本番で一度だけ起きたバグを記録できれば、開発環境で何度でも同じ実行を再生し、デバッガでじっくり追えます。「一度起きたバグを二度と逃さない」ための仕組みです。

graph LR
    R[記録: 非決定イベントを<br/>全部ログに残す] --> L[(イベントログ)]
    L --> P[再生: ログ通りに<br/>同じ実行を再現]
    P --> D[デバッガで何度でも追える]

18.4 モデル検査：すべてのインターリーブを調べる

動的検出が「実際に踏んだ経路」しか見ないのに対し、モデル検査（model checking） は 起こりうるすべてのインターリーブを網羅的に探索 し、不正な状態に到達しないことを証明（あるいは反例を提示）します。

考え方は、小さな並行プログラム（や同期プロトコル）を有限の状態遷移系としてモデル化し、全状態を機械的に探索することです。「両方とも 0 になる状態に到達するか？」「デッドロックに陥る状態はあるか？」といった問いに、網羅的に答えます。状態爆発（インターリーブの数が組み合わせ的に増える）を抑えるため、対称性の削減や、等価なインターリーブをまとめる 半順序簡約（partial-order reduction） といった技法が使われます。

モデル検査が特に効くのは、ロックフリーアルゴリズム（第8章）やメモリモデル（第4章）が絡む、小さくて致命的なコアです。これらは経路が複雑で、テストや動的検出では到底カバーしきれませんが、規模が小さいのでモデル検査の網羅探索が現実的です。新しい同期プリミティブやロックフリーデータ構造を処理系に入れる前に、その核をモデル検査で検証するのは、強く推奨される実践です。

18.5 検証技術の使い分け

3 系統の技術は、目的に応じて使い分けます。

次章では、正しさから性能へ視点を移します。「並列化したのに速くならない」のはなぜか——Amdahl と Gustafson の法則、スケーラビリティの測り方、そして第13章で予告した false sharing の実測を扱います。

19. 性能評価：速くならない理由を測る

並列処理系を正しく作っても、それが速いとは限りません。「8 コアにしたのに 2 倍にもならない」は、並列化に取り組んだ誰もが通る道です。本章では、並列性能を理解し測定するための基礎——Amdahl の法則と Gustafson の法則、スケーラビリティの測り方、そして第13章で予告した false sharing の実測——を扱います。性能評価は感覚ではなく、測定と理論に基づくべき営みです。

19.1 Amdahl の法則：直列部分が天井を決める

並列化の効果には、原理的な上限があります。それを定式化したのが Amdahl の法則Amdahl の法則^{[Gene, 1967]} です。プログラムのうち並列化できる割合を p（残り 1-p は本質的に直列）、コア数を N とすると、得られる速度向上（speedup）の上限は次式になります。

この式が突きつける事実は厳しい。コアを無限に増やしても（N → ∞）、速度向上は 1/(1-p) で頭打ちになります。たとえば 5% が直列（p = 0.95）なら、コアをいくら積んでも 20 倍が天井です。直列部分が 5% あるだけで、上限が 20 倍に固定されてしまうのです。

xychart
    title "Amdahl の法則: 並列割合ごとの速度向上の上限"
    x-axis ["1", "2", "4", "8", "16", "32"]
    y-axis "speedup" 0 --> 16
    line [1, 1.9, 3.5, 5.9, 9.1, 12.5]
    line [1, 1.8, 3.1, 4.7, 6.4, 7.8]
    line [1, 1.6, 2.5, 3.4, 4.0, 4.4]

上の図は、並列割合が 95%・90%・75% のときの速度向上です。並列割合が下がるほど早く頭打ちになり、コアを増やす効果が急速に薄れるのが見て取れます。第16章で「GVL は Amdahl の極端形（並列割合が実質ゼロ）」と述べたのは、この曲線が完全に平らになることを指していました。

19.2 Gustafson の法則：問題を大きくすれば希望はある

Amdahl の法則は悲観的に見えますが、前提に「問題サイズが固定」という仮定が隠れています。Gustafson の法則Gustafson の法則^{[John, 1988]} は、この前提を問い直しました。

現実には、コアが増えれば、人はより大きな問題を解こうとします。「同じ問題を速く解く」のではなく「同じ時間でより大きな問題を解く」のです。多くの実用的計算では、コア数を増やすと並列化できる部分（データの量に比例する計算）が増え、直列部分（初期化やまとめ）の相対的な割合は減ります。この スケールする問題 の視点では、速度向上は次のように、コア数に対してほぼ線形に伸び得ます。

graph LR
    A["Amdahl: 問題サイズ固定<br/>「同じ仕事を速く」<br/>→ 直列部分が天井を作る"] 
    B["Gustafson: 問題サイズ可変<br/>「同じ時間で多くを」<br/>→ コア数に線形に伸びうる"]

両者は矛盾しません。同じ現実を、異なる問いで切り取っている のです。Amdahl は「固定した仕事を、何倍速くできるか（strong scaling、強スケーリング）」を、Gustafson は「コアを増やしたぶん、どれだけ大きな仕事をこなせるか（weak scaling、弱スケーリング）」を測ります。処理系の性能を語るときは、どちらの問いに答えているのかを明示する必要があります。

19.3 スケーラビリティの測り方

性能評価で最も大切なのは、正しく測る ことです。素朴な測定は、いとも簡単に誤った結論を導きます。

• strong scaling を測る：問題サイズを固定し、コア数 1, 2, 4, 8, … に対して実行時間を測り、speedup = T(1) / T(N) をプロットする。理想は直線（N 倍）。どこで頭打ちになるかが、直列部分やボトルネックを示す。
• weak scaling を測る：コアあたりの問題サイズを固定し、コア数とともに総問題サイズを増やして、実行時間が一定に保たれるかを見る。
• 効率（efficiency）を見る：efficiency = speedup / N。1.0 に近いほど良い。これが落ちていく点に、競合やオーバーヘッドが現れる。

19.4 false sharing を実測する

第13章で予告した false sharing（偽共有） は、性能評価で必ず疑うべき容疑者です。別々のスレッドが更新する別々の変数が同じキャッシュライン（第2章、典型的に 64 バイト）に同居すると、ハードウェアがそのラインを奪い合い、性能が崩壊します。ソースを読んでも「共有していない」ので、測定でしか見つかりません。

典型的な実験を考えます。スレッドごとのカウンタを「詰めて」並べた場合と、キャッシュライン境界に「離して」並べた場合で、同じ並列カウントの速度を比較します。

# 詰めて配置（false sharing が起きる）: 隣同士が同じ 64 バイトに乗る
counters = Array.new(n_threads, 0)   # 要素が密に並ぶ

# 離して配置（false sharing を避ける）: 各カウンタを別ラインへ
# 各スレッドはまずローカル変数で数え、最後に一度だけ書き戻す、でも回避できる
def worker(local_count)
  local = 0
  iterations.times { local += 1 }    # 共有に触れない
  local_count.value = local          # 最後に一度だけ
end

「詰めた」版は、論理的には各スレッドが別のカウンタを触っているのに、物理的には同じラインを奪い合うため、コアを増やすほど 遅くなる ことすらあります。一方「離した／ローカルに数えてから書き戻す」版は素直にスケールします。両者を実測すると、しばしば数倍の差が出ます。

xychart
    title "false sharing の有無: コア数 vs スループット（イメージ）"
    x-axis ["1", "2", "4", "8"]
    y-axis "相対スループット" 0 --> 8
    line [1, 1.9, 3.7, 7.2]
    line [1, 0.9, 0.8, 0.7]

上の図のように、false sharing があると（下の線）コアを増やしても伸びず、むしろ落ちます。これを見抜くには、perf のようなプロファイラでキャッシュミス（特に HITM: modified line のヒット）を測るのが確実です。「並列化したのに速くならない、むしろ遅い」と感じたら、まず false sharing を疑い、データ配置とパディング（第13章）を見直してください。

19.5 性能評価のまとめ

• Amdahl の法則：直列部分が速度向上の天井を決める。並列化の前に直列部分を削れ。
• Gustafson の法則：問題サイズを増やせる前提なら、コア数に線形に伸びうる。strong/weak scaling を区別せよ。
• 測定は、最良の逐次版を基準に、ウォームアップとばらつきに注意して行う。
• false sharing は測定でしか見つからない性能の罠。データ配置とローカル集約で回避し、プロファイラで実証する。

理論と測定の道具が揃いました。最終章では、本書で積み上げた概念が、現実の処理系——Go、Erlang/BEAM、Java、Ruby、Python——でどう具現化しているかを横断的に振り返ります。

20. ケーススタディ横断：5 つの処理系

最終章では、本書で積み上げた概念が、現実の処理系でどう具現化しているかを横断的に振り返ります。取り上げるのは Go ランタイム、Erlang/Elixir の BEAM、Java の仮想スレッド（Project Loom）、Ruby の GVL から Ractor への歩み、そして CPython の no-GIL です。同じ問題に対して、各処理系が異なるトレードオフ（第16章で挙げた「正しさ・単一スレッド性能・並列性能・互換性」の四者）をどう取ったかを比べることで、本書全体を立体的に見直します。

20.1 Go ランタイム：CSP と work-stealing の実装

Go は、本書の第II部の多くを、言語とランタイムの中核として実装した好例です。

• 並行モデル：CSP（第3章CSPの原論文^{[C., 1978]}）。goroutine（軽量スレッド）と channel、select を言語の第一級機能にしている。
• 軽量スレッド：goroutine は可変サイズの小さなスタックを持ち、数百万作れる（第10章）。
• スケジューラ：M:N スケジューリングと work-stealing（第10章work-stealingの論文^{[Robert, 1999]}）。OS スレッド（M）の上で goroutine（G）を、プロセッサ（P）を介して走らせる「GMP モデル」。ブロックする操作は横取りされ、OS スレッドを遊ばせない。
• GC：並行 GC（第13章）。write barrier を使い、停止時間を極小（典型的にサブミリ秒）に抑えることに注力している。
• 共有モデル：「メモリを共有して通信するな、通信してメモリを共有せよ」を標語に掲げるが、共有メモリ自体は許す。Go のレースは起こりうるので、標準で race detector（第18章ThreadSanitizerの論文^{[Konstantin, 2009]} と同系統）を同梱している点が実践的。

Go の教訓は、第II部の機能群（CSP・軽量スレッド・work-stealing・並行 GC）を最初から統合設計すると、これだけ素直に並列が書ける ということです。後付けではなく設計段階から並列を前提にした強みが出ています。

20.2 Erlang/Elixir の BEAM：隔離による堅牢性

BEAM は Erlang/Elixir の仮想マシンで、アクターモデル（第3・9章アクターモデルの原論文^{[Carl, 1973]}）を最も徹底した処理系です。Joe Armstrong の学位論文Armstrongの学位論文^{[Joe, 2003]} の思想がそのまま実装されています。

• 隔離：Erlang のプロセス（アクター）は完全に隔離され、メモリを一切共有しない（第17章）。各プロセスが自分のヒープを持ち、メッセージは値のコピーで渡される。
• GC：プロセスごとに独立した小さなヒープを GC する。共有しないので、あるプロセスの GC が他を止めない——隔離が GC の並行化（第13章）を自然に解いている。
• スケジューラ：軽量プロセスを M:N で走らせ、各プロセスに実行時間の予算（reduction count）を与えてプリエンプトする。協調任せでない公平なスケジューリング。
• 障害モデル：「Let it crash」。プロセスが落ちても隔離されているので波及せず、監視ツリー（supervisor）が再起動する。並列性そのものより 隔離による堅牢性 が主眼。

BEAM の教訓は、第17章の「共有させない」を設計の根本に据えると、第III部の問題（共有状態・GC の並行化）の多くが最初から発生しない ということです。代償は、すべてがメッセージのコピーになることと、共有メモリ的な細粒度の最適化ができないことです。

20.3 Java 仮想スレッド（Project Loom）：互換性を守る軽量化

Java は長く OS スレッドに 1:1 対応する重いスレッドを使ってきました。Project Loom の 仮想スレッド（virtual threads）JEP 444^{[Ron, 2023]} は、これを後付けで軽量化した、互換性重視の設計の好例です。

• 軽量スレッド：仮想スレッドは JDK が管理する軽量スレッドで、既存の Thread API をそのまま使える（第10章）。ブロックすると、それを載せていたキャリア（OS スレッド）は解放され、別の仮想スレッドを走らせる。
• スケジューラ：デフォルトで ForkJoinPool を使い、work-stealing（第10章Cilk-5の論文^{[Matteo, 1998]} と同系統）で負荷をならす。
• 設計判断：第10章で触れた「ファイバー方式（スタック退避）」を選び、async/await 方式の “function coloring” を避けた。だから既存の同期的なコード（ブロッキング I/O を使うライブラリ）が、書き換えなしに軽量化の恩恵を受けられる。
• TLS の教訓：第6章で触れたとおり、TLS が大量の仮想スレッドで問題になるため、scoped values という別機構が導入された。

Loom の教訓は、膨大な既存資産（同期的なコードとライブラリ）を壊さずに大量並行を実現するには、ファイバー方式の軽量スレッドが有効 ということです。互換性という制約が設計を決めた例です。

20.4 Ruby：GVL から Ractor へ

Ruby は、本書の第III部と第16章の物語を地で行く処理系です。長く GVL（第16章）の下で、単一スレッド性能と C 拡張の安全性を保ってきました。

• GVL 時代：一度に 1 スレッドしか Ruby コードを実行できない。I/O では GVL を解放するので並行は活きるが、CPU バウンドは並列化できない（第16章）。
• RactorRactorのドキュメント^{[Koichi, 2020]}：第16・17章で見た「隔離インスタンス」の道。Ractor ごとに GVL を持ち、Ractor 間でオブジェクトを共有させない（共有できるのは深く凍結された不変オブジェクトなどに限る）。隔離により、第III部の共有状態問題を「発生させない」ことで並列実行を実現した。
• 設計判断：BEAM 的な隔離を、既存の Ruby に後付けで導入した。完全な free-threading（後述の Python の道）より、互換性と安全性を優先したトレードオフ。
• コピーと所有権移動：Ractor 間のメッセージは、コピーするか所有権を移すか（第17章）を選べる。move したオブジェクトに元の Ractor が触るとエラーになる。

Ruby の教訓は、後付けで並列化する処理系にとって、「全部を free-threading にする」より「隔離した単位を並列に走らせる」方が、互換性を保ちつつ並列性を得る現実的な道になりうる ということです。代償は、隔離の制約をユーザが受け入れる必要があることです。

20.5 CPython no-GIL：借金を正面から返す

CPython の no-GIL 化PEP 703^{[Sam, 2023]} は、第16章で述べた「GVL という借金を、正面から一括返済する」最大の事例です。

• 目標：GIL を外し、1 プロセス内で複数スレッドが Python コードを真に並列実行できるようにする。しかも単一スレッド性能を落とさず、既存の C 拡張をできるだけ壊さずに。
• 参照カウント（第15章）：CPython は参照カウント方式の GC を使う。これを atomic 化する重い代償を、バイアス付き参照カウント・不変オブジェクトの恒久化（immortalization）・遅延カウントで緩和した。
• 内部の共有状態（第12〜14章）：辞書・リスト・集合などの組み込み型に細粒度のロックを入れ、メモリアロケータやインターン表を thread-safe 化した。まさに第III部の課題を一つずつ潰す作業。
• 互換性：free-threaded ビルドを当初オプション扱いとし、段階的に展開する慎重な進め方を取った。

no-GIL の教訓は、GVL を外すとは、第12〜16章で見たすべての借金を一度に返すことに他ならない という、本書の構図そのものです。提案から安定化まで長い年月を要していること自体が、その借金の大きさを物語っています。

20.6 横断比較：四者のトレードオフ

5 つの処理系を、第16章で挙げた四者のトレードオフで並べてみます。

graph TD
    Q[並列をどう実現するか] --> S[共有させない設計<br/>BEAM・Ractor]
    Q --> F[共有を許し守る<br/>Go・CPython no-GIL]
    Q --> L[軽量化で大量並行<br/>Go・Loom]
    S --> R[第III部の問題を回避]
    F --> W[第III部の問題を解く]

この表が示すのは、唯一の正解は無い ということです。「最初から並列前提で統合設計する（Go）」「共有させない（BEAM・Ractor）」「既存資産を守りつつ軽量化する（Loom）」「借金を正面から返す（CPython）」——どれも、置かれた制約（新規か既存か、互換性の重さ、ユーザ層）の下での合理的な選択です。第16章で述べたとおり、正しさ・単一スレッド性能・並列性能・互換性の四者は同時には満たせず、何を捨てるかが処理系の個性になります。

20.7 おわりに

本書は、並行と並列の区別（第1章）から始まり、ハードウェア・モデル・メモリモデル（第2〜4章）という土台の上に、データ競合を体験し（第5章）、スレッドから同期、ロックフリー、メッセージパッシング、軽量スレッド、データ並列という言語機能を載せ（第6〜11章）、処理系内部の共有状態・GC・キャッシュ・参照カウント・GVL・共有モデルを点検し（第12〜17章）、最後に検証・評価と実例（第18〜20章）へとたどり着きました。

全体を貫く原則は、繰り返し現れた次の一文に尽きます。最良の同期は、同期しなくて済むように設計を変えること。共有を減らし、不変にし、隔離し、型で守る——競合は、起きてから直すより、起きないように設計する方がはるかに良いのです。