Chromiumの並行処理モデル

注意: この記事について

この記事は、cfredric氏が作成したスライド "Concurrency in Chromium"の内容を日本語に意訳し、ブログ形式に再構成したものです。この記事で使用した画像も、元スライドにあった画像を使用しています。

日本語での理解を優先し、私なりに補足や構成の変更を加えているため、原文の逐次通訳ではありません。そのため、内容のすべてが必ずしも原著作者の正確な意図を反映しているとは限らない点をご了承ください。

Chromiumの並行処理モデルに関する直感的な理解を深める一助となれば幸いです。

Chromiumにおける並行処理

Chromium は安定性・機密性・速度のために複数のプロセスを使って稼動するアプリケーションである。 そしてそのプロセス一つ一つは、以下のようなスレッドにより構成される。

• メインスレッド （ブラウザプロセスではUIスレッドとも呼ぶ）
• IO スレッド （注: IPCのためであって、ファイル／ネットワーク用ではない）
• その他、何かしらのための専用スレッド
• 汎用のスレッドプールのスレッド

これらからわかるに、Chromiumの処理はかなり並列化されている。多くのプロセスやスレッドらが同時並行・並列的に動くため、これを安全かつ正しく処理する必要がある。

また、Chromiumにとってスレッドというのはとても重く粒度が荒いことも問題といえる。抽象的なレベルで説明すると、Chromiumは多くのワークストリームを持ち、これらが多くの場合独立していて並列化が可能だ。つまり、私たちが本当に求めているのは、これら作業ストリームをスレッド間でいかに負荷分散するか、という点である。

ここでは、従来の並列処理手法とChromiumが採用する手法、そしてどのようにそれを扱っていてかつ安全・適切に実現しているか、そしてそれをどのAPIを通じて使用できるのかを説明する。最終的なこの記事の目標は以下の通り。

• Chromiumの並行処理モデルに関する直感的な理解を提供する
• Chromiumにおける並行処理の扱いに関する有用なヒントやコツを示す

（一般的な）プロセス内並列処理

同時並行・並列処理を「安全かつ正しく処理する」とは一体なんなのか。もし私たちがこれに注意しない場合、きっとスレッド間のデータ競合が発生してしまうだろう。プロセスにおける様々なスレッド群は同じメモリ空間にアクセスすることができ、ゆえに私たちはスレッド群がお互いに邪魔しあわないよう協調させる必要がある。

一般に、この課題に関してはいくつかの解決策がある。まず一つが、ミューテックスや条件変数、セマフォ、バリア、そしてその他プリミティブを使うことである。これにより複数のスレッドは同じデータに対し書き込みなどのアクセスが可能になる。このアクセスが同時に二つ以上から行われることはない。これは古典的な手法で私たちの多くが多分親しみがあるだろう。この手法のキャッチフレーズは「記憶を共有することでやりとりをする」といえる。

それ以外のアプローチとしては、データをスレッド間で送るためにコミュニケーションプリミティブを使う、ということが挙げられる。つまり、一度に一つのスレッドしかデータを持たないということだ。この手法のキャッチフレーズは「やりとりをして記憶を共有する」といえる。

もちろん、これらのアプローチは互いに排他的ではなく（つまり、競合しない）、それらを組み合わせてハイブリッドな手法を用いることができます。

Chromiumでのプロセス内並列処理

前述したハイブリッドなやり方をChromiumは採用している。そして、メッセージパッシングの手法を強く推奨している。かといって、もし必要であればミューテックスなどのプリミティブも使用するが、ほとんどの場合に使用されない。

この、ハイブリッドを好みミューテックスなどをあまり使用しない理由は、ロックという処理はオーバーヘッドを少し生むためである。Chromiumは大量の並列処理を行うが、その並列に行われる処理のほとんどは、実際のところ同じメモリにアクセスする必要がない。このため、ロックの処理は無駄に近い。よって私たちはできる限りロックを避けることが多いわけだ。

Chromiumの並行処理における語彙

さて、これまで、一般的な並列処理手法とChromiumがその一般的な手法をハイブリッドに採用している、ということを説明したが、当初のChromiumの目的というのはChromiumの持つ多くのワークロードをどう分散するか、という点だ。これを説明する前にChromiumで使われる語彙を予め説明しておく。

• Task: 基本的な処理の単位、スレッドで実行可能
  • 具体例としてOnceCallbackやRepeatingCallbackが挙げられる
• 物理スレッド: OSスレッド、OSにより管理されるスレッド
  • 例: POSIXのpthreads
  • Chromiumでは恐らく、これに直接やりとりする機会は少ない
• base::Thread: クロスプラットフォームな物理スレッドの抽象
  • これも、基本直接触ることはあまりない
• Sequence: 仮想スレッド／ワークストリーム
  • Chromiumではワークストリームの代わりにシーケンスと呼ぶ
  • 特定の物理スレッドとは紐づかず、基盤となる物理スレッド群のいずれかで処理される
  • 順序通りに処理するタスクのキューを持つ

なお、Chromium の開発者として base::Thread を使用することはまずないだろう。代わりに base::ThreadPool を使用するのが好ましい。

Chromiumのシーケンス処理方法

基本的な語彙を説明したところで、Chromiumのロードバランシングの実現方法をみていこう。以下にいくつかのアプローチが列挙されているが、最後の一つがChromiumで有効なものだ。

• ❌ １つのスレッドと１つのシーケンスを紐づける
  • シーケンス毎に一つのスレッドを作る
  • → シーケンスは大量にあり、大量のスレッドが作成されオーバーヘッド
• ❌ １つのスレッドと複数のシーケンスを紐づける
  • スレッドはシーケンスの集合を持ち、それらを処理する
  • → 一つのスレッドじゃ負荷分散ができない
• ✅ 複数のスレッドが複数のシーケンスを処理する
  • スレッド群はシーケンス群を共有し、次に実行するタスクをスケジュールする時、シーケンスを一つ選び、そこにあるタスクを処理する
  • → シーケンスを忙しいスレッドから暇なスレッドに移動でき、負荷分散が容易
  • → スレッドを大量に作る必要がない（低スペック端末にやさしい）

最後のが一番効率的にタスクを処理することができ、負荷分散ができることがわかる。

シーケンスを安全に使う方法

効率的に処理をする方法をスレッドとシーケンスの数の関係で説明したが、次は安全な処理方法について説明する。

二つ以上のスレッドがデータにアクセスする時にデータ競合が発生しうることと、シーケンスから得たタスクは一度に一つのスレッドでしか実行されないこともこれまでに説明した。ここからわかるに、もしも特定のデータにアクセスする全べてのタスクが同一のシーケンスに属するならば、一度に実行されるタスクは一つであり、そのデータに関しては競合が発生しないといえる。

そして、これがまさに SEQUENCE_CHECKER を使う理由であり、これは GUARDED_BY_CONTEXT マクロを使用して、常に同一シーケンスからアクセスすることを保証するものである。一般に、ほとんどの Chromium コードでは単一スレッドではなく単一シーケンスを使っても、データ競合の観点で問題がない。さらに、単一シーケンスを使用するようにコードを記述することは、単一スレッドよりも柔軟である。なぜなら、シーケンスは任意のスレッドで実行されるため、より優れた効率の良いスケジューリングに繋がる可能性を持つからだ。

ちなみに、ThreadChecker という、メソッドが同じスレッドから呼び出されているか検証できるものがあるかが、これは物理スレッドを考慮することとなり、単一シーケンスを使うことはこれより柔軟性がある。

シーケンスの概略図

この図は、Y軸が別々の物理スレッドを表していて、X軸が時間となっている。オレンジの箇所がシーケンスである。

オレンジ色のシーケンスは二つの別々の物理スレッド上で実行されていて、なおかつ任意の時点でシーケンスを実行しているのは一つの Worker スレッドのみとなっている。GetHistory タスクは UI スレッドから追加された順番通りに実行されていることがわかる。

シーケンスの内部

ここで、私たちにとってシーケンスがどう動いて欲しいのかについて、洞察をいくつか説明しよう。Chromium がどのように処理をこなすのか知るため、少し実装詳細を覗いて見ることにする。

• Sequence クラスは TaskSource を継承する
  • TaskSource: タスクのストリームを提供する
• Sequence クラスは、以下を持つ
  • SequenceToken: 整数をラップした、シーケンスが持つ一意のトークン
  • SequenceLocalStorageMap: スレッド局所記憶（TLS）の Sequence 版

概念的には、シーケンスはタスクを順番に実行するキューと考えることができる。それ以外の部分では、操作を実現するための配線と意図した通りに動作したことを保証するメタデータにすぎない。より具体的にいうと、シーケンス（Sequence）はスケジュール基盤のための TaskSource であり、なおかつ SequenceToken という一意の識別子を持つ。

次に、もう一つ重要なことがある。もし複数のスレッドを扱う時、スレッド局所記憶という概念がある。全てのスレッドが同じアドレス空間を共有しているにも関わらず、各スレッドが自分専用のメモリを持つことができるものだ。Chromiumも同様に、シーケンスに対して同じ概念、いわば"シーケンスローカルストレージ"をサポートしている。このデータを格納する場所が、SequenceLocalStorageMap といえる。

インフラがシーケンスを使う方法

これまで、多くのシーケンスが存在する目的とその用途・実装概要を説明したが、これは実際にどうインフラで使用されているのか、をここで説明したい。

厳密な答えは複雑になるが、要点は次の通り。スケジューラは特定のシーケンスにおいて同時に実行されるタスクが一つになることを保証する。そしてシーケンスからとったタスクをスケジューラが実行する前に、SequenceToken と SequenceLocalStorage をスレッド局所記憶に格納する。つまり、各スレッドは「現在実行中のシーケンス」を示す識別子を持つ、ともいえる。

これにより、処理で必要なものが大体揃う。これにより得られるのは、相互排他を保証するために以前使用したプロパティと、実行時に SEQUENCE_CHECKER を使った相互排他の検証をするのに使うメタデータである。

何がシーケンスを作る？

シーケンスが有用なタスク処理のための抽象であることを知れた今、ではどうやってこれを使うのか。答えは基本作成しない。厳密にいえば、少なくとも、直接的には作成しない、ということだ。

• シーケンスは ThreadPool / TaskRunner の基盤により連携することができる
• シーケンスは以下により自動で作成される
  • base::ThreadPool::Post[Delayed]Task
  • base::Create[Updateable]SequencedTaskRunner
  • base::CreateSingleThreadTaskRunner

Chromium のタスクスケジューリング基盤は、シーケンスを必要に応じて自動で作成する。 例えば、ThreadPool::PostTask を呼び出したとする。これは、特に他タスクとの実行順序に関する保証を特に要求しないため、呼び出す度に新しいシーケンスを作る。

同じように、Sequenced または SingleThread な TaskRunner を作った場合、これらは作成する新しいシーケンスと紐づけられるだろう。

どう自分のシーケンスから別にタスクを送る？

そしたら、沢山の Chromium コードが特定のシーケンスで適切に処理がされているかをチェックしている最中、どうやって自分のコードを別のシーケンスで安全に実行させれば良いのか、次にこれについて述べる。

これをするには、タスクをシーケンスに対して「ポスト」する必要がある。そのために以下の選択肢がある。

• 任意のシーケンスで良い場合: ThreadPool::Post[Delayed]Task
  • 新しいシーケンスが作成される
• 特定のシーケンスがいい場合: SequencedTaskRunner / SingleThreadTaskRunner の Post[Delayed]Task
  • 使用タイミング: サードパーティ製ライブラリがシーケンスに対応していない場合、スレッド局所記憶を使用している場合

また、シーケンスでのやり取りをする際に便利な機能として、SequenceBound<T> があり、これはメソッドやコンストラクタ・デストラクタを特定のシーケンスで呼び出すのに便利だ。

どう自分のシーケンスの管轄でタスクを扱う？

もし今動いてる自分のシーケンスからタスクが離れて帰ってこないことがないよう、実行したいならどうすればいいかも、触れておく。

• タスクを別シーケンスで動かし、終了時に自シーケンスで処理をしたい場合
  • TaskRunner::PostTaskAndReply[WithResult]
  • ThreadPool::PostTaskAndReply[WithResult]
• 自分のシーケンスで非同期的に動かしたい場合
  • base::SequencedTaskRunner::GetCurrentDefault()¹
  • SequencedTaskRunnerHandle::Get()->Post[Delayed]Task（昔の手法）

コールバックに関する文書: https://chromium.googlesource.com/chromium/src/+/main/docs/callback.md

どのシーケンスで動かせばいいかわからない

最後に、Chromium の大量のコードに当てはまるくらい重要なこととして、実行すべきシーケンスが決まっていない場合、基本的には特にすることはない。内部で暗黙的にシーケンスを処理してくれるからだ。

例えば、Mojo は内部でシーケンスを処理するため、Bind が呼び出されたのと同じシーケンスに対して Mojo レシーバーメソッドが呼び出される。Chromiumの色々な箇所で、シーケンスを扱っている実装が既にある、ということだ。

参考資料

• Threading and Tasks in Chrome
• Threading and Tasks FAQ
• Share Memory By Communicating - The Go Programming Language
• The Chromium Chronicle #1: Task Scheduling Best Practices
• Chrome U 2019: Life of a Process (slides)
• Callbacks in Chromium

付録

• Jobs (post_job.h)
  • パワーユーザー向けのAPIで、大量な処理が必要な人向け
  • タスクスケジューラのオーバーヘッドが顕著になった場合に使用可能

---

1. この記事の元となったスライドにはないが、これは SequencedTaskRunnerHandle がなくなった後の新しいやり方であるため、ここに追加した。↩