同時実行

  • [アーティクル]

CLR 4.0 ThreadPool での同時実行の調整

Erika Fuentes

最新リリース (CLR 4.0) の CLR ThreadPool には、CLR 2.0 から大きな変更がいくつか加えられています。メニーコア アーキテクチャの広範な使用と、それに伴う既存アプリケーションの並列化や新たな並列処理コードの作成に対する要望といった、テクノロジ トレンドの最近の変化が、CLR ThreadPool に機能強化を施すきっかけとなった最も大きな動機の 1 つです。

MSDN Magazine 2008 年 12 月号の「CLR 徹底解剖: CLR でのスレッド管理」(msdn.microsoft.com/magazine/dd252943) では、動機の一部と、同時実行制御やノイズなどの関連する問題点について説明しました。今回は、CLR 4.0 ThreadPool でこうした問題にどのように対処しているか、関連する実装の選択肢、およびそれぞれの選択肢が CLR 4.0 ThreadPool の動作に与える可能性がある影響について説明します。また、現在の CLR 4.0 ThreadPool (ここからは、単に「ThreadPool」とします) で同時実行制御の自動化に向けて採用したアプローチに重点を置いて説明します。さらに、ThreadPool アーキテクチャの概要を簡単に紹介し、実装の詳細を取り上げます。この実装の詳細は、将来のバージョンで変更される可能性があります。新しい同時実行アプリケーションの設計と作成に携わっていて、同時実行を利用するか、(CLR 4.0 のコンテキストで) ASP.NET テクノロジまたは Parallel Extensions テクノロジを使用することによって、古いアプリケーションに機能強化を施すことに関心がある読者の方が、現在の ThreadPool の動作を理解して利用するのに、この記事がお役に立つでしょう。

ThreadPool の概要

スレッド プールの目的は、スレッド管理、さまざまな種類の同時実行の抽象化、同時実行操作の調整などの主要サービスを提供することです。スレッド プールが提供するサービスによって、ユーザーはこうした操作を手動で組み込む負担が軽減されます。経験の浅いユーザーにとっては、マルチスレッド環境の詳細について学習および対処する必要がなくなります。経験豊富なユーザーにとっては、信頼できるスレッド システムが手元にあることで、これ以外のアプリケーションの側面の機能強化に力を注ぐことができます。ThreadPool は、マネージ アプリケーション向けにこうしたサービスを提供し、Mac OS で特定の Microsoft .NET Framework アプリケーションを実行している場合など、プラットフォーム間の移植性をサポートします。

同時実行にはさまざまな種類があり、それぞれシステムの異なる部分に関連する可能性があります。最も重要なものは、CPU の並列処理、I/O の並列処理、タイマーと同期、および負荷分散とリソースの使用率です。ThreadPool のアーキテクチャの概要について、同時実行のさまざまな側面から簡単に説明することができます。ThreadPool アーキテクチャと、関連する API の使用方法の詳細については、「CLR のスレッド プール」(msdn.microsoft.com/magazine/cc164139、英語) を参照してください。具体的には、ThreadPool には 2 つの独立した実装があります。1 つは CPU の並列処理に対処し、"ワーカー ThreadPool" と呼ばれます。もう 1 つは I/O の並列処理に対処し、"I/O ThreadPool" と呼ばれます。ここからは、ThreadPool での CPU の並列処理と関連実装作業 (特に、同時実行を調整する方針) に重点を置いて説明します。

ワーカー ThreadPool: ワーカー ThreadPool は、CPU 並列処理レベルでサービスを提供するようにデザインされ、マルチコア アーキテクチャを利用します。CPU の並列処理の主な考慮事項には、作業を迅速かつ最適にディスパッチすることと、並列処理の次数を調整することの 2 つがあります。前者の場合、ThreadPool の実装では、競合を回避するためのロックなしのキューや、負荷分散のためのワーク スティーリングなどを使用します (この記事では、これらの分野は扱いません。これらのトピックの詳細については、msdn.microsoft.com/ja-jp/magazine/cc163340 を参照してください)。後者の場合、つまり並列処理の次数を調整する場合、リソースの競合によって全体的なスループットが低下するのを回避するために、同時実行制御を行う必要があります。

CPU の並列処理は、任意の時点で同時実行できる作業項目数を判断するなど、多くのパラメーターが関連するため、特に困難になる可能性があります。また、コアの数や、さまざまな種類のワークロードに合わせてチューニングする方法といった別の側面の問題もあります。たとえば、(理論上は) CPU ごとに 1 つのスレッドを対応させるのが最適ですが、ワークロードが絶えずブロックされる場合は、より多くの作業を実行するためにさらに多くのスレッドが使用されることになるため、CPU 時間が浪費されます。実際のところ、ワークロードのサイズと種類もパラメーターの 1 つです。たとえば、ワークロードがブロックされる場合、全体的なスループットが最適になるスレッド数を判断することはきわめて困難です。というのも、要求が完了するタイミングを判断するのは困難だからです (要求が到着する頻度は I/O のブロッキングと密接に関連するため、これを判断するのも困難です)。こうした ThreadPool に関連する API は QueueUserWorkItem で、メソッド (作業項目) を実行するためにキューに登録します (QueueUserWorkItem の詳細については、msdn.microsoft.com/library/system.threading.threadpool.queueuserworkitem を参照してください)。QueueUserWorkItem の使用は、(他の作業と) 並列実行できる作業があるアプリケーションにお勧めです。作業が ThreadPool に渡され、作業を実行するタイミングが自動的に "判断" されます。この機能により、プログラマはスレッドを作成する方法とタイミングを気にする必要がなくなります。ただし、このソリューションがどのシナリオでも最も効率的というわけではありません。

I/O ThreadPool: この ThreadPool の実装は I/O の並列処理に関連しており、ワークロードのブロック (つまり、サービスの提供に比較的時間がかかる I/O 要求) または非同期 I/O を処理します。非同期呼び出しでは、スレッドはブロックされず、要求へのサービスの提供中に他の作業を続行できます。この ThreadPool は、要求とスレッドとの間の調整を行います。I/O ThreadPool には、ワーカー ThreadPool と同様に、同時実行を調整するアルゴリズムがあり、非同期操作の完了率に基づいてスレッド数を管理します。ただし、このアルゴリズムはワーカー ThreadPool のアルゴリズムとまったく異なるため、ここでは取り上げません。

ThreadPool での同時実行

同時実行を扱うことには困難が伴いますが、必要な作業で、システムのパフォーマンス全体に直接影響します。システムによって同時実行がどのように調整されるかは、同期、リソースの使用率、負荷分散などの他の作業に直接影響し、反対に、こうした作業も同時実行の調整に直接影響します。

"同時実行制御"、つまりこの記事で扱う "同時実行の調整" の考え方は、特定の時点に ThreadPool 内で機能できるスレッドの数を調整することです。つまり、パフォーマンスに悪影響を与えずに、同時に実行できるスレッドの数を決定するポリシーのことです。ここで説明する同時実行制御は、ワーカー ThreadPool にのみ関連します。同時実行制御は直感的なものではなく、ワーカー ThreadPool のスループットを向上するために並列に実行できる作業項目数を "調整" および "削減" することです (つまり、同時実行の次数を制御することは、作業の実行を防ぐことです)。

ThreadPool での同時実行制御アルゴリズムによって、同時実行のレベルが自動的に選択されます。つまり、一般に最適なパフォーマンスを維持するために必要なスレッド数が決定されます。このアルゴリズムの実装は、ThreadPool の最も複雑で興味深い部分の 1 つです。同時実行レベルのコンテキストで ThreadPool のパフォーマンスを最適化する (つまり、同時に実行するスレッドの "正確な" 数を判断する) には、さまざまな手法があります。ここからは、CLR で考慮または使用されているこうした手法をいくつか紹介します。

ThreadPool における同時実行制御の進化

最初に採用された手法の 1 つは、CPU の使用率を監視し、使用率を基に最適化を行う方法でした。つまり、CPU 使用率を最大限に高める (CPU をビジー状態に維持するため、できる限り多くの作業を実行する) ようにスレッドを "追加" します。長期に渡るワークロードや変化しやすいワークロードを扱うときは、CPU 使用率を指標として使用すると役に立ちます。ただし、この手法では指標を評価する基準に誤解を招く恐れがあったため、適切ではありませんでした。たとえば、メモリのページ切り替えが頻繁に行われているアプリケーションについて考えてみてください。このような状況では、監視される CPU の使用率は低くなります。ここでスレッドが追加されると、メモリの使用量が増加するため、CPU 使用率がさらに低くなります。また、競合が数多く発生しているシナリオでは、実際の作業ではなく、同期を取るために CPU 時間が使用されるため、スレッドを追加しても状況が悪化するだけということも問題です。

別の手法として、OS に同時実行レベルを管理させることが考えられました。実際には、この管理は I/O ThreadPool で行われますが、移植性を高め、リソース管理の効率を向上するために、ワーカー ThreadPool にもより高度な抽象化が求められます。この手法は、シナリオによっては有効に機能する可能性がありますが、それでもプログラマは、リソースの飽和状態を回避するための調整方法を理解しておく必要があります (たとえば、数千個のスレッドが作成される場合、リソースの競合が問題になる可能性があり、このような場合にスレッドを追加すると実際には状況がさらに悪化します)。そのうえ、この手法ではプログラマが依然として同時実行について考慮しなければならないことを示し、スレッド プールを利用する意味がなくなります。

最近採用されている手法は、パフォーマンスをチューニングするための指標として、スループットの概念を導入する方法です。スループットは、時間単位あたりに完了した作業項目数として計測されます。この手法では、CPU 使用率が低いときにスレッドが追加され、その結果スループットが向上するかどうかが確認されます。スループットが向上する場合はさらにスレッドが追加されますが、スループットの向上が認められない場合は追加されたスレッドが取り除かれます。この手法では、リソースの使用方法だけでなく、作業の完了数も考慮されるため、以前の手法に比べれば実用的です。しかし、残念ながら、スループットはアクティブ スレッドの数 (作業項目サイズなど) だけでなく、多くの要因の影響を受けるため、パフォーマンスのチューニングが難しくなります。

同時実行を調整するための制御理論

以前の実装に関するいくつかの制限事項を克服するために、CLR 4.0 では新しい考え方が導入されています。考慮された最初の方法論は、制御理論分野の Hill Climbing (HC) アルゴリズムです。この技法は、入出力フィードバック ループを基盤とする自動チューニング手法です。制御を加えた入力の効果を確認するため、システムの出力を短時間監視および測定します。その監視測定情報がアルゴリズムにフィードバックされ、入力がさらにチューニングされます。入出力を変数と見ることで、システムはこうした変数に関する関数としてモデル化されます。測定された出力を最適化することが目標です。

ワーカー ThreadPool システムのコンテキストでは、作業を同時に実行しているスレッドの数 (または同時実行レベル) が入力で、スループットが出力です (図 1 参照)。

image: ThreadPool Feedback Loop

図 1 ThreadPool フィードバック ループ

スレッドを追加したり削除したりしながら、時間をかけてスループットの変化を監視および測定し、監視しているスループットの低下または向上に応じて、スレッドをさらに追加するか削除するかを決定します。図 2 は、その考え方を示しています。

image: Throughput Modeled as a Function of Concurrency Level

図 2 同時実行レベルの関数としてモデル化されたスループット

スループットを同時実行レベルの (多項式) 関数とすると、このアルゴリズムでは、関数値が最大 (この例では、およそ 20) に達するまでスレッドを追加します。最大に達した時点でスループットが低下するため、アルゴリズムによってスレッドが削除されます。各時間間隔 で、スループットの測定結果をサンプリングし、"平均" を求めます。この平均値が、次の時間間隔 の決定に使用されます。測定結果にノイズが含まれていると、長期にわたってサンプリングが行われている場合を除いて、統計情報が実際の状況を表さないことを把握します。スループットの向上が、同時実行レベルの変化によるものか、ワークロードの変動など、別の要因によるものかを判別するのは容易ではありません。

現実のシステムに当てはまる手法は、かなり複雑になります。わずかな変化を検出したり、ノイズが非常に多い環境から短期間に変化を抽出したりすることは難しいため、この手法を使うことが特に問題になります。この手法で観察される最初の問題は、モデル化した関数 (図 2 の黒い傾向曲線) が現実の静的対象 (グラフの青色の点) と一致しているわけではないため、わずかな変化を測定することが困難なことです。次の問題は、おそらく最も懸念される問題です。つまり、ノイズ (特定の OS アクティビティやガベージ コレクションなどのシステム環境が原因で生じる測定結果の変化) によって、入力と出力の間の関係を判断すること (スループットがスレッド数の関数にならなくなることを判断すること) が難しくなるという問題です。実際、ThreadPool では、スループットは実際に監視している出力のごく一部を構成しているにすぎず、大部分がノイズです。たとえば、アプリケーションのワークロードが多くのスレッドを使用しているとします。このような場合にスレッドをほんの少し追加しても、出力は変化しません。ある時間間隔中に観察されたスループットの向上は、同時実行レベルの変化に関連すらしていないことがあります (この問題については、図 3 を参照してください)。

image: Example of Noise in the ThreadPool, part 1

image: Example of Noise in the ThreadPool, part 2

図 3 ThreadPool におけるノイズの例

図 3 では、x 軸が時間を、y 軸がスループットと同時実行レベルの測定結果を表しています。上のグラフは、一部のワークロードでは、スレッド数 (赤色の線) が一定でも、スループット (青色の線) の変化が観察されることがあることを示しています。この例の場合、青色の線の振動がノイズです。下のグラフは、ノイズが存在していても、スループットが時間の経過と共に全般的に向上していくようすが観察される別の例を示しています。しかし、スレッド数が一定なので、このスループットの向上はシステムの別のパラメーターが原因です。

ここからは、ノイズに対処する手法について説明します。

信号処理を導入する

信号処理は、エンジニアリングの多くの分野で使用されており、信号に含まれるノイズを軽減するための処理です。信号処理の考え方は、出力信号に含まれる入力信号のパターンを検出することにあります。同時実行制御アルゴリズムの入力 (同時実行レベル) と出力 (スループット) を信号と考えれば、この理論を ThreadPool のコンテキストに当てはめることができます。同時実行レベルを意図的に変更して、既知の期間と振幅を備えた "波" として入力し、出力の中に入力した波形パターンを探せば、ノイズと、スループットに実際に影響を与える入力とを区別することができます。図 4 にこの考え方を示します。

image: Determining Factors in ThreadPool Output

図 4 ThreadPool の出力に含まれる要因の判断

ここでちょっと、システムを、ある入力を与えると出力を生成するブラック ボックスだと考えてみましょう。図 4 は、HC の入力と出力 (緑色の線) をシンプルな例として示しています。下の例は、入力と出力がフィルター技法を使用して波のように見える (黒い線) ようすを示しています。

フラットな一定した入力を与えるのではなく、信号を導入し、ノイズを含む出力の中にその信号が含まれているかどうかを検索します。こうした効果は、他の波形から波形を抽出したり、出力に含まれる特定の信号を検出したりするために一般に使用される "帯域フィルター" や "整合フィルター"などの技法を使用すれば実現できます。このことは、入力に変化を加えることで、アルゴリズムが、各時点での最新の少量の入力データを基に決定を下すようになることも意味します。

ThreadPool で使用しているアルゴリズムは、離散フーリエ変換を使用します。これは、波形の振幅や位相などの情報を使用する方法です。この情報を使用して、入力が出力に影響を与えたかどうかや、どのように影響を与えたかを確認できます。図 5 のグラフは、600 秒以上実行されているワークロードでこの手法を使用する ThreadPool の動作の例を示しています。

image: Measuring How Input Affects Output

図 5 入力が出力に与える影響の測定

図 5 の例では、入力波の既知のパターン (位相、周波数、および振幅) を出力でトレースできます。このグラフは、サンプル ワークロードでフィルターを使用する同時実行アルゴリズムの動作を示しています。赤い線が入力に、青い線が出力に対応しています。時間の経過と共にスレッド数を上下に変化させていますが、これはスレッドの作成や破棄を意味するわけではありません。スレッドは保持したままです。

スレッド数の目盛りとスループットの目盛りは尺度が異なりますが、入力がどのように出力に影響を与えるかを対応付けることはできます。スレッド数は時間軸の少なくとも 1 単位ごとに絶えず変化していますが、これは 1 つのスレッドの作成と破棄を意味しているわけではありません。スレッドはプール内に "存在" していても、アクティブに作業を行っていません。

最初の手法は HC を使用し、スループット曲線をモデル化して、その計算に基づいて決定を行うことが目標でしたが、改善された手法では、これとは対照的に、入力に加えた変化が出力の向上に役立ったかどうかを判断するだけです。直感的には、人為的に加えた変化が、出力で観察される効果に影響を与えているという確信が高まります (信号を導入するまでに観察されたスレッドの最大数は 20 で、多くのスレッドを使用するシナリオでは特にきわめて妥当な数です)。信号処理を使用する手法の欠点の 1 つは、導入する人為的な波形パターンが原因で、常に、最適な同時実行レベルが少なくとも 1 スレッドずれることです。また、モデルを安定させるのに十分な量のデータを収集する必要があるため、同時実行レベルの調整は、比較的ゆっくりしたペースで行われます (CPU 使用率の指標に基づアルゴリズムは、速いペースで行われます)。また、このペースは作業項目の長さによって異なります。

この手法は完全ではなく、適切に機能するワークロードとそうでないワークロードがありますが、以前の手法よりは大幅に向上しています。このアルゴリズムが最も適切に機能するワークロードの種類は、個々の作業項目が比較的短いワークロードです。というのも、作業項目が短くなるほど、アルゴリズムを適応できる速度が速くなるためです。たとえば、このアルゴリズムは 250 ミリ秒以下の期間の作業項目でも非常にうまく機能しますが、10 ミリ秒以下になればさらに適切に機能します。

同時実行管理

まとめると、ThreadPool は、プログラマが同時実行管理以外の作業に集中するのに役立つサービスを提供します。こうした機能を提供するために、ThreadPool の実装には、ユーザーのために多くの決定を自動化できるハイエンドのエンジニアリング アルゴリズムが組み込まれています。その一例が、同時実行制御アルゴリズムです。このアルゴリズムは、さまざまなシナリオで示されるテクノロジとニーズ (作業の実行の役立つ進捗状況を測定するニーズなど) を基盤に進化しています。

CLR 4.0 の同時実行制御アルゴリズムの目的は、効率的な方法で同時実行できる作業項目数を自動的に決定し、ThreadPool のスループットを最適化することです。このアルゴリズムは、ノイズや、ワークロードの種類などのパラメーターが原因でチューニングが困難です。また、作業項目はすべて有用な作業であるという仮定に基づいています。現在のデザインと動作は、ASP.NET シナリオと Parallel Framework シナリオに大きな影響を受けています。そのため、これらのシナリオでは、このアルゴリズムは適切に機能します。一般に、ThreadPool は作業を効率的に実行できます。ただし、ワークロードによっては、あるいは複数の ThreadPool が同時に実行されている場合などは、予期しない動作が行われる可能性があることに注意してください。

Erika Fuentes 博士 は、CLR チームでテストを担当するソフトウェア開発エンジニアであり、パフォーマンス チームでスレッドのコア オペレーティング システム分野に重点的に取り組んでいます。科学計算、適応システム、および統計に関するいくつかの学術的な出版物を執筆しています。

この記事のレビューに協力してくれた技術スタッフの Eric Eilebrecht と Mohamed Abd El Aziz に心より感謝いたします。