元記事：Async Tasks in C++11: Not Quite There Yet | Corensic, Bartosz Milewski氏, 2011/10/10
自分自身の理解のために日本語訳を行ったC++11標準ライブラリstd::asyncとタスクベース並列に関する記事。
C++11の非同期タスク：まだその域に達していない
スレッド生成の単なるシンタックスシュガーとしてstd::asyncを期待するなら、これ以上は読む必要がありません。まさに期待通りの働きをします。より多くを望むなら、続きをどうぞ。
誤解しないで欲しいのですが、std::asyncは個々の有用な並行性コンセプトをパッケージ化しています：戻り値のためにstd::futureを提供し、対となるstd::promise側をラップします。またタスクを同期的に実行するオプションも提供します。（訳注：std::asyncの基本についてはid:yohhoy:20120203を参照のこと。）
ただしタスクは、並行プログラミングにおいて若干異なるニュアンス：タスクベース並列の基本部品となります。そしてC++11のタスクはこの意味においては不十分なのです。
タスクベース並列
タスクは、スレッドに関連するパフォーマンスおよびスケーラビリティ問題に対する答えです。オペレーティングシステムのスレッドはどちらかといえば重量(heavy-weight)です；スレッド生成には時間とシステム資源を消費します。もしアルゴリズムを多数の独立した演算、つまりタスクへと自然に分解可能ならば、タスク毎に個別スレッドを生成するのではなく、特定システムの利用可能な並列度（コア数や負荷状況など）に依存したスレッド数へと調整して最良パフォーマンスを達成できるでしょう。これはスレッドプールや負荷分散アルゴリズムを用いて手動で行うこともできますし、タスクベースシステムを利用して行うこともできます。
タスクベースシステムでは、プログラマは何が並列に実行できるか指定しますが、実際に利用する並列度はシステムに決定させます。プログラマがアルゴリズムをタスクに分割し、ランタイムがスレッドへと割り当て ― 普通は1スレッドに対して多数のタスクを割り当てます。
各種言語サポートによる数多くのタスクベース並列実装が存在します。このアプローチの先駆者にはCilk言語があり、Haskell, F#, Scalaでは組み込みサポートがあります。また、Microsoft PPLやIntel TBBといったC++ライブラリも幾つか存在します。
スレッドの生成と異なり、タスク生成は相対的に軽量とされています。そのためプログラマは細粒度の並列化を検討でき、またマルチコアスピードアップの恩恵を得ることができます*1。
タスクベースシステムの中心をなすのはWork-Stealingキューです。あるスレッドがタスクを生成すると、まず該当スレッドを実行するプロセッサ（コア）のキューへ追加します。ただし、他にアイドルなプロセッサがあれば、他キューからタスクのスチール(steal; 盗む)を試みます。こうしてスチールされたタスクが並列に実行されます。
タスクがスレッド間を移行する可能性があることに注意してください。さらにOSスレッドを効果的に活用するには、I/O待ちや他タスク完了待ちなどでブロックされたタスクをスレッドから外し、そのまま別のタスクで再利用することが必要です。
C++11のタスク
std::asyncで生成したC++11の“タスク”は、正にタスクベース並列のそれようにスレッドから抽象化されている、というのが私の期待でした。C++タスクに関するビデオチュートリアルの準備を始めたとき、デモ動作用の簡単なプログラムを書きました。既定の起動ポリシーにて非同期タスク群を生成し、それらの完了を待機するものです。各タスクは1秒間のスリープ後にスレッドIDを出力します。
int main() { std::cout << "Main thread id: " << std::this_thread::get_id() << std::endl; std::vector<std::future> futures; for (int i = 0; i < 20; ++i) { auto fut = std::async([] { std::this_thread::sleep_for(std::chrono::seconds(1)); std::cout << std::this_thread::get_id() << " "; }); futures.push_back(std::move(fut)); } std::for_each(futures.begin(), futures.end(), [](std::future & fut) { fut.wait(); }); std::cout << std::endl; }
その実行結果は意外なものでした。始めの6個のタスクは各スレッドにて並列に実行されました。しかし残りのタスクは1秒置きに1個づつメインスレッドにて実行されたのです。（注記：この振る舞いはJust::Thread v1.7で修正されました ― では続きを。）
Main thread id: 1 2 4 3 6 5 7 1 1 1 1 1 1 1 1 1 1 1 1 1 1タスクテストの出力
この並列化アプローチはどう見ても十分にスケールしません。
ディレクトリの再帰的な一覧出力を行う別のプログラムを書いた時は、サブディレクトリ毎に別々の非同期タスクを生成していました。ただこのときはlaunch::async起動ポリシーを明示的に要求したため、各タスクは新しいスレッドにて開始すると保証されます。このプログラムはある程度まで動作しましたが、ディスク全体を対象として試したときは、Windowsスレッド生成の制限を超えたことで失敗しました。このアプローチもまた十分にスケールしません。
さらに悪い事には、プログラムが失敗しないときも、全タスクを常に逐次実行するlaunch::deferredポリシーの方が、launch::asyncポリシーよりも良好なパフォーマンスを示しました。これは並列化のパフォーマンス利得を容易に打ち消すほどに、Windowsのスレッド生成が高コストな処理であるためです（Windows 7はユーザレベルのスレッドをサポートしますが、それでもこの問題は改善しないでしょう）。
最初に取った対応は、利用したJust::Threadライブラリのダメな実装についてAnthony Williamsに文句を言うことでした*2。これは標準準拠の振る舞いであるとの回答があり、今度はHerb SutterとHans Boehmに確認を取りましたが、彼らもAnthonyと同意見でした。C++11タスクベース並行性の標準化を阻害する深刻な問題が存在すると明らかになったのです。
問題点
タスクベース並列の基礎となるのは、タスク間でスレッドを共有でき、かつスレッド間を移行可能であることです。この共有と移行は透過的であるべきです。
既定の起動タスクに対する要件は次の通りです：
- ランタイムはタスクを非同期的もしくは同期的に実行可能
- 同期的に実行する場合は、親スレッドのコンテキストで実行されるべきである
- 非同期的に実行する場合は、別スレッドで実行されたかのように(as if)振る舞うべきである
厳密に言えば、タスクはthis_thread::get_id()を呼び出せるため、現在のスレッドIDに基づいたスレッド共有や移行をするというバカげた手段もとれます。一般に、sleep関数等を含む名前空間std::this_threadはスレッドに強く紐付いています。
ここでthis_thread名前空間の関数呼び出しを脇に置いて、別スレッドにて実行されたかのように(as if)振る舞う非同期タスクのみが必要と想像してみましょう。それでもなお幾つかの問題があります。
スレッドローカル変数
C++11では新たにthread_local記憶域指定子が導入されました。スレッドローカル変数は各スレッドにてそれぞれ初期化と破棄が行われます。オブジェクトはスレッド生存期間を超えては生存できません。この要件はスレッド共有を困難にします。
意見交換を通じ、Hans Boehmはタスクの終了要件を明確化しました：std::asyncが生成したfuture上でのgetやwait呼び出しから所有スレッドが戻るとき、もしくはfutureデストラクタのうち、いずれか先に実行される処理の前にスレッドローカル変数は完全に破棄されなければならないと。（訳注：この振る舞いについてはid:yohhoy:20120317を参照のこと。）
実際にはもう少し自由度があります：ランタイムで終了タスクのスレッドローカル変数が正しく破棄されると保証するなら、スレッドを再利用することができます。ただしプログラマがWindowsのTlsAlloc等といったOS固有APIを呼び出す場合は、残念ながらこれは不可能に思えます。Anthonyはまた、タスク粒度切り替えに際してDLL内DLL_THREAD_DETACHハンドラの扱いが不明確であるとも指摘しました。
ロック
スレッドに結びつくC++11並行性のもうひとつの側面 ― ロックが存在します。std::mutexオブジェクトはスレッドに紐付いています。つまりlockを行ったスレッドと同一スレッドにてunlockを呼び出す必要があります。なぜこれが問題となるのでしょう？
ここまでに実行途中のタスクを移行する必要性があるとは指摘していませんが、多くのタスクベースシステムがこれを行います。ブロッキングタスクを扱うときの最適化方法なのです。
ブロッキングには大別して2つのシナリオ：外部ブロッキングと内部ブロッキングが存在します。I/O待ちなどのブロックされうるOS関数を（直接的まはた間接的に）呼び出したとき、外部ブロッキングが発生します。私のディレクトリ一覧出力プログラムはこれを数多く行っていました。内部ブロッキングはfuture上でタスクがブロックされると発生しますが、こちらは回避しやすい方です。サブディレクトリ一覧出力を行ったタスクの結果待ちにて、私のプログラムではこれも数多く行っていました。
ブロックタスクはプロセッサ資源を利用しませんが、スレッドを占有しています。このスレッドは他タスクの実行に再利用できたはずです。しかし再利用のためには、スレッドからタスクを取り外し、またブロック解除時には元の状態へ復元することが要求されます。いま、ブロッキング前にタスクがミューテックスのロック保持していたとすると、他スレッドへ移行させることは不可能です。ロック解除を他のスレッドから行うことは出来ないのです。
Herb Sutterの観察によれば、元々のスレッドへのタスク復元を試みてたとして、元スレッドが同一ミューテックスを待機する別タスクで占有されていた場合には、偽のデッドロックが発生します。
またrecursive_mutexの利用でもロック問題が存在します。ロックが解除される前に、スレッドはこのミューテックスに対して複数回ロックできます。一方で、現スレッドが所有するミューテックスのロックを試みた第2のスレッドはブロックされます。タスクが別個のスレッドで実行される限りは正しく動作します。しかし同一スレッドを共有する場合は、同じミューテックスの獲得に成功してデータ破損を引き起こします。
次のシナリオを想像してください。タスクAが共有データ構造を変更しようと再帰ミューテックスのロックを獲得します。そして何らかのOSコールでブロックします（一般的には良いアイデアではありませんが、ありえることです）。タスクは現在のスレッドから外され、今度はタスクBが実行開始されます。そして同ミューテックスのロック獲得は ― 同じスレッドから実行されたために成功し、タスクAが変更途中だったデータ構造を読み／変更します。災害が起きます。
launch::deferredポリシー指定時の振る舞いのように、同スレッドにてタスクが逐次実行される場合は、問題にならないことに注意してください。これは別タスクの実行以前に各タスクが完了するためです。
最後に、この実行中タスクの移行はスレッドローカル変数に対しても大惨事をもたらします。
解決案
既定起動ポリシーの最適化
最も簡単なのは既定ポリシーの実装を変更し、タスクを非同期実行するか遅延実行するかの決定を遅らせることでした。Anthonyはこの解法にすぐ気付き、すぐさまJust::Thread v1.7として修正リリースしました。
アイデアはシンプルです。N個のタスク ― Nは有効コア数に応じてランタイムが決定 ― を非同期にスケジューリングし、残りはキュー上に置きます。キュー上のタスク完了を（future上のgetやwait呼び出しにより）強いられた場合、呼び出したスレッドのコンテキストにて同期的に実行されます ― これはlaunch::deferredポリシー指定に相当します。それ以外では、いずれかの非同期タスクが完了し次第、キューから次タスクを取り出して非同期にスケジューリングします。これはJust::Threadライブラリ変更後の前回テストプログラムの出力です：
Main thread id: 1 2 3 4 7 5 6 9 10 11 1213 14 15 16 17 18 19 20 21 22新ライブラリを用いたテストの出力
今度は既定の起動ポリシーであってもタスク毎に別々のスレッドにて実行され、マルチコアマシンの並列性を有効活用する小さなバッチ処理として動きました。ただしスレッド再利用は行われず、ランタイムは22個のOSスレッドを生成しました。理想的にはオペレーティングシステムがスレッド資源をキャッシュし、2度目のスレッド生成コストは1度目より軽減されるのが望まれます。
（タスクライブラリ実装の評価を行う際はこのテスト実行をお勧めします。）
スレッドの再利用
タスクのパフォーマンス向上に関する次ステップは、スレッドプールの活用と新規生成に代わるスレッド再利用です。スレッドローカル変数の問題があるため、言語ランタイムの助け無しにはスレッド再利用の実装は不可能と考えられます。タスクライブラリはthread_local変数の初期化をフックし、タスク終了時に変数を破棄せねばなりません。
依然としてTlsAlloc等のAPIを直接呼び出すタスクが問題になります。（ライブラリ製作者にとって）魅力的なオプションは問題を無視することでしょう ― 全ての言語がスレッドローカル・ストレージを扱うポータブルな手段を提供するならですが。
タスクの移行
続いて別タスクを実行するために、スレッドからブロックタスクを外せるようにします。これはスレッドローカルとロックの問題から簡単には行きません。
thread_local変数の問題は、実際には変数をタスクローカルだと扱うべきです。または、少なくともタスクローカルである“かのように(as if)”振る舞うべきです。2つのタスクが同じスレッドを共有する場合、間には何らかの“コンテキスト切り替え”機構が存在するはずです。このコンテキストは全スレッドローカル変数の状態を含むべきでしょう。
ロックがスレッドではなくタスクに紐付くならば、ロックを保持したタスクの移行が行えます。興味深いことに、C++標準にはこの振る舞いに対する言及があります。§30.2.5のLockable要件定義は“実行主体(execution agents)”に言及しますが、これはスレッドに限らないとしています。このコメントは特に興味深いものです：
[Note: Implementations or users may introduce other kinds of agents such as processes or thread-pool tasks. -- end note]
［注釈: 実装系およびユーザはプロセスやスレッドプール・タスクといった異なる種別の実行主体を導入してもよい。-- 注釈終り］
しかしながら、標準ライブラリmutexはタスクではなくスレッドに紐付きます。§30.2.5の意図は、タスクローカル変数やミューテックスを備えた独自タスクライブラリを作製した場合でも、lock_guardや条件変数等の標準ユーティリティを利用できるという意味です*3。一方でstd::asyncタスクの実装は、thread_localやstd::mutexと共に動作しなければなりません。
デッドロック
下記はブロック中にスレッドが再利用された場合、2つのタスクがデッドロックするシナリオです。
- タスクAがスレッドT1にて実行されており、ミューテックスM1を保持し、ブロッキング呼び出しを行う
- ランタイムはT1からAを外し（状態の保存などを行って）、ブロックタスク管理キューへ移動する
- 同スレッドT1にてタスクBが開始され、Aでロック中のM1を獲得しようとする
- M1ロック解除のため、タスクAをT1 ― ロックを獲得した同一スレッド ― にて実行しようとするが、T1はBで占有されており、Aの処理を進めることができない
このデッドロックを解消する唯一の手段は、スレッドからBを外すことです。つまりタスク移行システムが行うべきは ― あらゆるブロックタスクがスレッドから外されると保証することです。
一般的に、偽のデッドロックは多数のブロックタスクを伴います。もし全てのタスクがロック上でブロックされたなら、これはどのみち真のデッドロックが発生しています。一方で、ブロッキング呼び出しから戻ったのちに進行可能なタスクが少なくとも1つあるなら、タスク実行を完了したかブロックタスクを外したスレッドへと常に割り当てることができます。
もちろん、ロックがスレッドでなくタスクに関連付いており、ロック移行を許容するならばこの問題は解消します。
結論
既定の起動ポリシーによるstd::asyncを有用なものにできると、この課題から学びました。ただしスレッドとの強い関連性のために、本格的なタスクベース並列の実装は事実上不可能です。タスクベースシステムはライブラリとして実装可能ですが、thread_local変数や標準ミューテックスの利用については厳しい制限が伴います。このシステムではタスクローカル変数やミューテックスの独自バージョンを実装する必要があるでしょう。
Anthony Williams, Hans Boehm, Herb Sutterと、議論したArtur Laksbergに感謝いたします。
*1:訳注：ここでの「スピードアップ」は並列コンピューティング用語。wikipedia:en:Speedup
*2:訳注：Anthony Williams氏はJust::Threadライブラリ http://www.stdthread.co.uk/ の開発／有償販売を行っている。また彼はBoost.Threadライブラリメンテナでもある。
*3:訳注：§30.2.5は特定のオブジェクトではなくLockable要件を定義しており、std::mutexは単にその要件を満たすクラス実装の1つ。独自ライブラリのミューテックスがLockable要件を満たすならば、そのテンプレート引数にLockableを要求するlock_guardといった標準部品と組合せることが可能。
