協調型スケジューリング vs. 先取り型スケジューリング
この記事はCooperative vs. Preemptive: a quest to maximize concurrency powerの翻訳・意訳記事になっています。
動機
私のチームはJavaを多用しています。システムを構築するために、ウェブサーバやデータベースドライバなど、多くのものに、スレッドを介した同時実行機能を内蔵した、実績のあるオープンソースのJavaライブラリを使用しています。
また、ビジネス特有のロジックを実装する際には、Javaのスレッド化命令を利用して同時実行を実現しています。
しかし、時間が経つにつれ、パフォーマンスの問題が見えてきました。
Javaアプリには合計1万個のスレッドが実行されていたため、ホストのRAMをすべて占有してしまうサービスがありました。
64ビットのJVMのスレッドのスタックサイズが1024バイトであるため、スレッドが1万もあるとスタックだけで約10GBのメモリを割り当てていました。
また、コンテキストスイッチのため、CPU使用率もかなり高くなっていました。
解決策の1つはサーバーを増強することですが、それは徒にお金をかけるだけです。
最終的に私のチームでは、スレッドプールの使用率を監査することで問題を緩和し、最終的にはサービスをより小さなものに分割しました。
この記事の残りの部分は、この問題を解決するために私たちが行った調査の結果をまとめたものです。
スケジューリング、スレッドモデル、メモリモデルの3つの重要な要素についてお話します。
また、プログラミング言語やライブラリが、実際にどのように並行処理にアプローチしているかを見てみましょう。
Cooperative scheduling vs. Preemptive scheduling
スケジューリングとは、ワーカーにタスクを割り当てる仕組みのことです。
タスクを割り当てるプログラムをスケジューラと呼ぶことが多く、OSでは通常、タスクはスレッド、ワーカーはCPUコアを意味します。
ただし、この概念は必ずしもOSに限ったことではないので、ここではタスクとワーカーの総称で話すことにします。
スケジューリングには、Cooperative(協調型)とPreemptive(先取り型)の2つのスタイルがあります。
1. 協調型:Cooperative
協調型スケジューリングでは、タスクは自分のライフサイクルを管理します。
ワーカーに割り当てられた後、ワーカーから解放するかどうかはタスク次第です。スケジューラの仕事は、空いているワーカーにタスクを割り当てることだけです。
もし空いているワーカーがいなければ、スケジューラができることはワーカーが空くことを待つこと以外には何もありません。これが協調性と呼ばれる理由です。
タスクはお互いに協力し合って、誰もが公平にワーカーを得られるようにするべきです。
あるタスクが悪意を持って1つしかないワーカーを長時間占有している場合、他のすべてのタスクはスケジューリングされず、プロセスがハングアップする可能性があります。
昔、Windows 3.1xやMacOS 9では、協調型スケジューラを使用して同時実行を行っていました。
開発者がプログラムをうまく書けず、タスクに制御を放棄させる処理を忘れてしまったとしたら、OS全体が動作を停止する可能性があります。
協調型スケジューリングによる同時実行は、1つの孤立したプログラムや組み込みシステム用のOSなど、お互いに密接に動作するように設計されているタスクのためによく導入されます。サードパーティのプログラムがインストールされているような多目的なOSでは動作しません。
しかし孤立したプログラムであっても、CPUの処理をさまだける機能を導入しないように技術者には細心の注意が求められます。
では、なぜ協調型スケジューリングを使うのでしょうか？ よく挙げられる理由としては、他の方法に比べてはるかに実装コストが安価だからです。
その前に、次は先取り型スケジューリングの話をしましょう。
2. 先取り型:Preemptive
先取り型スケジューリングでは、スケジューラはタスクをより柔軟にコントロールできます。
スケジューラはタスクをワーカーに割り当てるだけでなく、タスクに一定の実行時間を割り当てます。
タスクは、アイドルになった(実行を終了した、またはI/Oのためにブロッキングした)とき、または割り当てられた実行時間を使い切ったときにワーカーから取り除かれます。
実行時間を使い切ると、スケジューラはタスクを中断(先読み)して別のタスクを代わりに実行させ、元のタスクは再び自分の番を待つようになります。
このアプローチでは、スケジューラはすべてのタスクに対してある程度の公平性を保つことができます。
また、優先順位の高いタスクは、優先順位の低いタスクよりも多くの時間をワーカーに割り当てることができます。
最近のOSのほとんどは、スレッドのスケジューリングに、先取り型スケジューラ方式を採用しています。
OSの場合は、1つのプログラムがハングアップしても、他のプログラムはそれぞれの実行時間を持っているため、正常に動作することができるので、先取り型の方が効果的です。
これは協調型スケジューラでは保証できないことです。
しかし、先取り型スケジューリングは欠点がないわけではありません。
タスクは途中で中断されることがあるので、中断されたタスクが持っていた状態を保存し、復元する必要があります。
タスクが中断された後に再び実行する場合には、ゼロからやり直すのではなく、中断されたタスクが持っていた状態を継続しなければなりません。
このようにタスクの状態を保存したり復元したりする処理をコンテキストスイッチと呼びます。オペレーティングシステムでは、コンテキストスイッチは計算コストがかかります。
あるスレッドから別のスレッドへの切り替えには、レジスタの切り替え、スタックポインタの切り替え、各種テーブルの更新など、ある程度の管理が必要です。
これには時間がかかります。これを通常、コンテキストスイッチのオーバーヘッドと呼んでいます。
協調型スケジューリングでは、タスクが個々でライフサイクルを維持しているので、スケジューラが各タスクの状態を把握する必要がないため、タスクの切り替えが非常に安価で高速になります。
スケジューリング方式を選択するときにはタスク間の公平性とスイッチのオーバーヘッドを考えて適切な選択をする必要があります。
カーネルレベルのスレッド と ユーザーレベルのスレッド
OSから見た場合、スレッドには2つの種類があります。
カーネルレベルのスレッドは、OS自身が管理するスレッドです。OSがスレッドの作成、スケジューリングなどを行います。
これに対してユーザーレベルのスレッドは、ユーザー空間のプログラムが管理するスレッドです。ユーザーレベルのスレッドはOSからは見えないので、OSのスレッド化サポートは必要ありません。これらはグリーンスレッド、ライトウェイトスレッド、コアーチンと呼ばれることもあります。
この2つのタイプに基づいて、プログラムで使用されているスレッドモデルを、カーネルレベルのスレッド、ユーザレベルのスレッド、ハイブリッドスレッドの3つに分類することができます。
1. カーネルレベルのスレッド(1:1)
このスレッドモデルでは、1つのプログラムスレッドは1つのOSスレッドに変換されます。
これは、プログラム内でスレッドを作成するときはいつでも、システムコールを呼び出して OSスレッドを作成することを意味します。
このように、このスレッドモデルでは、必ずOSと同じスケジューラ（多くの場合は先取り型）を使用するという制約に加えて、コンテキストスイッチのオーバーヘッドなどの欠点があります。
2. ユーザーレベルのスレッド(N:1)
ユーザーレベルのスレッドモデルは、1つのOSスレッドにマッピングされた複数のユーザーレベルのスレッドを使用します。
このスレッドモデルを使用するプログラムは通常、スレッドの実行を管理するために独自のスケジューラをランタイムに含める必要があります。
このスケジューラは、先取り型でも協調型のどちらでも大丈夫です。
このスレッドモデルの欠点は、プログラムが基本的に単一のOSスレッドで実行されるため、マルチコアを活用した並列化を実現できない、もしくはカーネルレベルのスレッド化ほど並列化が簡単ではないことです。
3. ハイブリッド(M:N)
このスレッドモデルは、カーネルレベルとユーザレベルのスレッドモデルの両方の長所を組み合わせたものです。
並列化のためにカーネルレベルのスレッドを利用しますが、同時にタスクを"並行"して実行するためにユーザレベルのスレッドも維持します。
次に、並行処理のもう一つの重要な側面であるメモリモデルについての説明をしていきましょう。
メモリモデル
メモリモデルは、メモリを介したスレッドの相互作用とデータの共有使用のモデルです
マルチスレッドプログラムでは、1つのプロセスで多数のスレッドが実行されている可能性があります。
これらのスレッドは同じアドレス空間を共有しています。これは、データ構造や変数などのメモリをスレッド間で共有していることを意味します。
先取り型スケジューリングでは、スレッドはいつでも復帰することができます。
これらのスレッドは、同時に同じ変数にアクセスしたり、更新しているかもしれません。このような場合には、競合状態などの問題が発生する可能性があります。
このようなプログラムは、スレッドセーフではないと言われています。上記のような問題を防ぎ、スレッドセーフを維持するために、プログラムはメモリモデルを定義する必要があります。
メモリモデルとは、メモリを共有した同時実行がどのように動作するかを記述したもので、通常はlockやmutexなどの何らかの同期機能がモデルに含まれています。
しかし、同期化にも問題がないわけではありません。同期化されたコードは、一度に1つのスレッドだけが実行できることを保証しますが、多くのスレッドを持つマルチスレッドプログラムでは、それがいかにパフォーマンスのボトルネックになり得るかを理解できるでしょう。
さまざまな状況でパフォーマンスを出せるようなメモリモデルを考え出すのは簡単ではなく、一部の言語のランタイムがメモリモデルを隠蔽するのはそのためです。
協調型スケジューラを使用すると、スレッドは既知の時点で停止するので、スレッドセーフでないと言われるような問題はおきませんが、スケジューラが先取り型スケジューラの上で実行されている場合（ハイブリッドスレッドモデルなど）、この問題はまだ出てくるでしょう。
各言語のConcurrency
理論的な解説はこれで終了です。ここからは各言語などが実際にどのように並行処理にアプローチしているかを見てみましょう。
具体的には、様々な種類のスケジューリング、スレッドモデル、メモリモデルをどのように組み合わせて同時実行性を提供するかを見てみましょう。
1. カーネルレベルのスレッドモデルを用いたプログラム、先取り型スケジューラを用いたプログラム
例: Java(JVM), C, Rust
このカテゴリのプログラムは、OSのスレッディング機能(1:1)を直接利用しています。
そのため、これらのプログラムに使用されるスケジューラは先取り型であり、lockのようなブロッキングコードを使用したりしてもスケジューラがそのスレッドを占有しないことを保証するため、ブロッキングコードを使用したりしても問題ありません。
Java（JVM threading）と C（pthreads）には、一貫したメモリモデルを保証するための同期機能があります。
一方、Rustは興味深い存在です。GCなしでメモリの安全性を保証する値の所有権の概念のおかげで、無制限の同時実行メモリアクセスに伴う多くの問題に対処する必要がありません。
Rustでは、競合状態などの潜在的な問題は、コンパイル時に検出することができます。彼らはこの機能を Fearless Concurrency と名付けました。
コンテキストスイッチのオーバーヘッドやメモリ割り当てのような、先取り型スケジューリングやカーネルレベルのスレッディングの欠点は、これらのカテゴリのプログラムを開発するときは考えなくてはならないことです。
2. カーネルレベルのスレッドモデルを持つプログラムで、GILを持つプログラム
例. Python, Ruby, OCaml
これらのプログラムは実行されている間、カーネルレベルのスレッドを利用することができます。
しかし、これらのスレッドは GIL によって制約されています。GIL は Global Interpreter Lock の略です。GILの制約下では、プロセス内で一度に実行できるスレッドは1つだけです。
これは、Python、Ruby、OCamlなどの言語で発生します。
なぜGILなのでしょうか？ それはGILを使用することで並行処理の実装が大幅に簡素化されるからです。
一度に1つのスレッドだけしか実行されないことが保証されているので、メモリモデルを定義する必要がそもそもありません。これは目に見えない同期機能と考えることができます。
GILを使った同時実行の欠点は、先取り型スケジューラを使ってOSのスレッドを使っても、（IOタスクを除いて）本当の意味での並列化を実現できないことです。
この種のプログラムでは、通常、複数のプロセスを実行することで並列性の必要性を実現することができます。
しかし、プロセスはスレッドに比べてコストが重く、プロセス間の通信(IPC)はメモリを共有するスレッドよりもコストがかかるため、通常はユーザーレベルのライブラリに頼って並列性を向上させています。
注: RubyはGILを取り除く計画を提案しています。Pythonは実際にCPythonの代わりにJythonを使った場合にGILの問題を解決しています。これらの言語が今後どうなっていくのか興味深いところです。
3. ユーザレベルのスレッドモデルを持つプログラム、協調型スケジューリング
例. Node.js, Twisted, EventMachine, Lwt
このアプローチを使用するプログラムは、軽量スレッドを管理するための独自のランタイムを持っています。
これまで議論してきたように、協調型スケジューリングの実装は、メモリモデルを定義する必要がないため、先取り型スケジューリングよりも簡単です。
このカテゴリのプログラムの重要なポイントの一つは、通常はイベントループを持っていることです。イベントループは、基本的には軽量スレッドのスケジューラです。
Node.jsはこの分野の最大手の1つです。上の例で挙げた他の3つは、実際にはPythonのTwisted、RubyのEventMachine、OCamlのLwtなど、GILを搭載した言語用のユーザーレベルのライブラリです。
このアプローチを採用したプログラムは、(OS的には)シングルスレッドであってもスケーラビリティを誇っています。軽量なユーザレベルのスレッドの性質は、先取り型スケジューラの欠点なしに最大のスループットを実現しています。
軽量スレッドを生成するのは安価なので、何十万ものスレッドがアプリケーション内に存在することは珍しくありません。何十万ものカーネルレベルのスレッドを持とうとすると、マシンに十分なスペックが必要になります。しかし、操作が一般的にノンブロッキングである場合には、それが最適に動作することもあります。
軽量スレッドを利用するこの手のアプローチで重い計算を行うと、イベントループ(シングルスレッドで実行される)のリソースを占有してしまい、最終的には同時実行性が損なわれる可能性があるため、お勧めできません。
4. 先取り型＋協調型のハイブリッドモデル
例. RxJava, Kotlin coroutines, Akka, uThreads, Go(goroutines)
このアプローチは、先取り型のOSスレッドと協調型のユーザレベルのスレッドの両方を組み合わせたものです。カーネルレベルのスレッドの並列性を維持しながら、ユーザレベルのスレッドの高いスループットと効率を達成できるという明らかな利点を持っています。
多くの場合、軽量スレッドを管理するユーザレベルのランタイムが、OSスレッドへの割り当てを管理しているという意味では、カーネルレベルのスレッドの使用はユーザからは見えません。
RxJava、Kotlin coroutines、およびAkkaはすべてJVMの上にあるユーザレベルのライブラリであり、軽量スレッドをJVMのスレッドに割り当てることができます。uThreadsライブラリは、CおよびC++用の協調型のユーザレベルスレッドの実装の一例です。
Go はネイティブに goroutines を持っており、このカテゴリ内では少し異質です。Kotlinのコルーチンと非常によく似ていますが、Kotlinではコルーチンを作成して明示的に協調性を持たせるだけでなく、yieldsやサスペンド関数を使用しなければならないので、コードを書く際にはプログラマが細心の注意を払う必要があります。
Goでは、普通の関数をgoキーワードで呼び出せばいいだけです。
なぜなら、スケジューラは関数の呼び出しごとに制御を移転させるからです。これにより、協調型の同時実行が非常に簡単に行えます。
しかし、関数呼び出しを行わずに長時間のループを実行している場合は、割り当てられたスレッドをずっと使うことができてしまいます。
ループ内にスケジューラを呼び出す命令を追加するという提案がありましたが、タイトなループ(ループごとに行われる処理が少ない場合)ではスローダウンの原因になるかもしれません。(現在進行中の設計案では、Goスケジューラを協調型ではなく先取り型にするという案もあります)。
一般的に、このアプローチには、OSのスレッドを使用するため、競合と同期の問題が伴うという欠点があります。
Kotlin、Akka、Goでは、actorやchannelを使用して、メモリを共有する代わりにメッセージという形でスレッド間の通信を行うことでこれを回避することができますが、スレッドセーフではないコードを誤って書いてしまう可能性があります。
また、ブロッキングコードは、軽量スレッドが割り当てられたOSスレッドをブロックすることになります。
しかし、これらの欠点があっても、標準的なカーネルレベルのスレッディングやユーザレベルのスレッディングからすれば、大幅な改良であるため、このモデルは十分実用的と言えます。
5. 先取り型＋先取り型のハイブリッドモデル
例. Erlang, Elixir, Haskell
以前は、ユーザレベルでスレッド処理のための先取り型スケジューラを実装することは不可能だと思っていましたが、調べてみるとそのようなものは存在することがわかりました。
調べてみたら、Haskell、Erlang、Elixir（Erlangランタイム）では、このようなアプローチで並行処理を行っていることがわかりました。
先取り型スケジューラを実装するのは、コンテキストスイッチや同期プリミティブを考慮しなければならないので難しいと前に言いましたが、HaskellやErlangではどうやって実現しているのでしょうか？
Haskell
Haskellは純粋な関数型言語であるため、ユーザーレベルの先取り型スケジューラの実装が可能になっています。
つまり、IOや変数の更新、グローバルステートなどの副作用が厳密に制御されているということです。
Haskellはデフォルトで不変の値を強制します。そのため、複雑なメモリモデルは必要ありません。
ドキュメントを見る限りでは、Haskell（実際にはGHC）は先取り型スケジューラを使用していると主張しています。
私は、実際にはメモリの割り当てがあるたびに生成される協調型スケジューラだと主張しています。
しかし、通常のプログラムでは（低レベルの最適化を行っていない限り）メモリの割り当ては常に行われているので、先取り型スケジューラとみなしても問題ないと思われます。
Erlang/Elixir
一方、Erlangのアプローチは間違いなく素晴らしいものです。
Erlangのスレッドは "プロセス"と呼ばれ、複数のプロセスがメモリを共有しないOSのプロセスを模倣しています。
Akkaのように（実際、ErlangはAkkaを参考にしています）、Erlangのプロセスはメッセージを渡すことでコミュニケーションをとります。これはすべてランタイムに組み込まれています。
これはElixirにも当てはまります。これはErlang VMの上で動作する比較的新しい言語です（JVM上のScalaやKotlinを考えてみてください）。
プロセスはErlangのビルディングブロックなので、プロセスがメモリを共有する方法はありません。Erlangは先取り型スケジューリングメカニズムを使って簡単にプロセスをスケジュールすることができます。
CPUコアごとに1つのスケジューラを実行することで、Erlang VMは並列性を維持することができます。
Erlang VMは先取り型スケジューラを使っているので、ブロッキングコードを書いても問題ありません。この結果、非常に効率的な並列プログラムを書くことができます。
Discussion