![mutex
map<string, string> pages; // global variable
mutex pages_mutex; // global variable
void save_page(const string& url) {
result = (url にアクセスして内容を取得);
pages_mutex.lock(); // 例外安全性はとりあえず置いておく
pages[url] = result;
pages_mutex.unlock();
}
int main() {
// 並列にウェブサイトをクロール
thread t1(save_page, "http://foo");
thread t2(save_page, "http://bar");
t1.join(); t2.join();
}](https://image.slidesharecdn.com/c-150424105445-conversion-gate01/85/C-43-320.jpg)
C++ マルチスレッド 入門
- 1. C++ マルチスレッド 入門 KMC 関東例会 (@ Cookpad) 2015/04/24 野島 裕輔
- 2. 自己紹介 ? 野島 裕輔 ? KMC ID: nojima ? Github: nojima ? Twitter: nojima ? サイボウズ株式会社でインフラ開発をやっています。 ? nginx のパッチを書いて DoS 対策したり SSL セッションキャッシュをホスト間で共有したり ? サーバクラスタの管理ツールを作ったり ? 矢印が判定????に重なる????????で左の??????を踏むッ!!
- 4. しかし…
- 5. CPU の周波数は 3 GHz ぐらいで頭打ちに CPU DB: Recording Microprocessor History - ACM Queue https://queue.acm.org/detail.cfm?id=2181798
- 6. ポラックの法則 ? 「プロセッサの性能は、そのダイサイズの平方根に比例する」 ? Intel のフレッド?ポラックさんの経験則 ? 性能を２倍にするには、ダイサイズを４倍にしないといけない。 ? それならば、単一のコアの性能は増やさずにコアを４つ積め ば４倍の性能になるのでは？ CPU のマルチコア化がトレンドに
- 7. The Free Lunch Is Over タダ飯の時代は終わった Herb Sutter (Microsoft の偉い人)
- 8. マルチコア時代のソフトウェア ? ハードウェアの進化を享受するためには、複数コアを上手く利 用できるようにプログラムを書く必要がある。 ? マルチプロセス化 ? データを共有する必要がないか、少数のデータしか共有しなくていい 場合は複数のプロセスを立ち上げて、プロセス間通信などでデータを 共有するのが安全。 ? マルチスレッド化 ? 多くのデータを共有する場合は、メモリ空間を共有して複数スレッドを 実行するのが効率的。 ? 今回の講座ではマルチスレッドを扱う。
- 9. C++ とマルチスレッド ? C++11 から言語にマルチスレッドのサポートが入った。 ? これにより環境依存のライブラリを利用しなくても、 C++ の標準ライブラリだけでマルチスレッドなプログラムが 書けるようになった。 ? しかも、わりと使い勝手がよい。
- 11. これさえあれば、だれでも簡単に マルチスレッドプログラミングが……！！ ＼＿＿＿＿＿＿ ＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿／ ○ Ｏ ???? o ∧＿∧！ ??! ／￣￣￣￣￣￣￣￣ ＿＿_（ ゜?゜）＿ ＜ という夢を見たんだ | 〃( つ つ | ＼＿＿＿＿＿＿＿＿ |＼ ⌒⌒⌒⌒⌒⌒＼ | ＼＾ ⌒ ⌒ ＼ ＼ ｜⌒⌒⌒⌒⌒⌒ ｜ ＼|＿＿＿＿＿＿__|
- 13. 読み書きの競合 2つのスレッドで x++ を実行 read x calc x + 1 write x x = 0 x = 1 read x calc x + 1 write xx = 2
- 14. 読み書きの競合 2つのスレッドで x++ を実行 read x calc x + 1 write x x = 0 x = 1 read x calc x + 1 write xx = 1
- 15. 読み書きの競合 2つのスレッドで x++ を実行 read x calc x + 1 write x x = 0 x = 1 read x calc x + 1 write xx = 1 タイミングによって最終結果が異なる
- 16. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0
- 17. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0 x 100
- 18. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0 x 100 y 200
- 19. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0 x 100 y 200 y 200
- 20. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0 x 100 y 200 y 200 y 200
- 21. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0 x 100 y 200 y 200 y 200 x 0
- 22. キャッシュによる一貫性の破れ Core 1 Core 2 キャッシュ メモリ x = 100; y = 200; cout << y << endl; cout << x << endl; y 0 x 0 x 100 y 200 y 200 y 200 x 0 x → y という順番で書き込んだはずなのに、y の値しか読めていない！！
- 23. コンパイラによる最適化 // Thread 1 ans = complex_computation(); done = true; // Thread 2 while (!done) /* busy loop */; cout << ans << endl; bool done = false; // global variable double ans = 0.0; // global variable
- 24. コンパイラによる最適化 // Thread 1 ans = complex_computation(); done = true; // Thread 2 while (!done) /* busy loop */; cout << ans << endl; コンパイラ先生 「ループ一周ごとに !done を 評価するのは無駄では？」 bool done = false; // global variable double ans = 0.0; // global variable
- 25. コンパイラによる最適化 // Thread 1 ans = complex_computation(); done = true; // Thread 2 if (!done) { while (true) /* busy loop */; } cout << ans << endl; コンパイラ先生 「最適化しといたで！！！」 bool done = false; // global variable double ans = 0.0; // global variable
- 26. コンパイラによる最適化 // Thread 1 ans = complex_computation(); done = true; // Thread 2 if (!done) { while (true) /* busy loop */; } cout << ans << endl; コンパイラ先生 「最適化しといたで！！！」 無限ループ！！ bool done = false; // global variable double ans = 0.0; // global variable
- 27. 我々はいったいどうすればいいのか？ ? 間違った解決策： ? 全ての変数に volatile をつける ? volatile にデータ競合を防ぐ力はない ? 全ての変数を atomic テンプレートでくるむ ? できない ? プログラム全体を lock で囲う ? マルチスレッドとは… ? コードを書いて神に祈る ? 日頃の行いに依る http://nonylene.net/blog/2014-12/dendengu.html
- 28. 我々はいったいどうすればいいのか？ ? 間違った解決策： ? 全ての変数に volatile をつける ? volatile にデータ競合を防ぐ力はない ? 全ての変数を atomic テンプレートでくるむ ? できない ? プログラム全体を lock で囲う ? マルチスレッドとは… ? コードを書いて神に祈る ? 日頃の行いに依る http://nonylene.net/blog/2014-12/dendengu.html まずはメモリモデルを知ろう
- 29. この講座は ? マルチスレッドプログラミングを安全に行うために 必要なメモリモデルの概念を紹介する ? メモリモデルとは、メモリへの読み書きがどういう性質を満たすべきかを 記述したもの。 ? 时间の制约上、色々端折ってたり误魔化したりしているので注意。
- 30. 用語 ? オブジェクト ? 規格上の定義は region of storage. ? メモリ上に固有の領域を持っている存在。 ? 変数とか配列の要素とか一時オブジェクトとか。 ? 評価 ? 式の値を計算したり、式の副作用を発動させたりすること。 ? 一つの式が複数回評価されたり、一回も評価されなかったりする。 ? 例えば、以下のプログラムの場合、x = 42 は 10 回評価される。 ? for (int i = 0; i < 10; ++i) x = 42;
- 31. happens before ? 評価と評価の間には、happens before 関係という半順序関 係が定義されている。 ? 直感的には、A happens before B とは、B が始まる前に必ず A が完了していることを表す。 ? happens before は半順序関係なので、グラフ的には DAG で表現できる。 x = 0 x y = 1 z = 3 y
- 32. happens before ? 同じスレッド上で実行される評価の間には、 自明な順序で happens before が定義される。 ? たまに例外もあるが… ? 異なるスレッド上で実行される評価の間には、 特別なことがない限り happens before は成り立たない。 ? どういう場合に成り立つかは後述。
- 33. data race ? 2 つの評価 A, B が以下の４条件を満たすとき、 プログラムに data race があるという。 1. A, B が同一の非アトミックオブジェクトに対する操作 2. A, B の少なくとも一方が書き込み操作 3. A happens before B でない 4. B happens before A でない ? プログラムに data race があるとき、undefined behavior が起こる。
- 34. data race bool done = false; // global variable double ans = 0.0; // global variable // Thread 1 ans = complex_computation(); done = true; // Thread 2 while (!done) /* busy loop */; cout << ans << endl; ? 同一の非アトミックオブジェクトに対する操作 ? 一方は書き込み操作 ? お互いに happens before でない
- 35. data race bool done = false; // global variable double ans = 0.0; // global variable // Thread 1 ans = complex_computation(); done = true; // Thread 2 while (!done) /* busy loop */; cout << ans << endl; ? 同一の非アトミックオブジェクトに対する操作 ? 一方は書き込み操作 ? お互いに happens before でない undefined behavior
- 36. atomic ? アトミックオブジェクトは data race を起こさない特別な オブジェクト。 ? std::atomic<T> で T 型のアトミック版が手に入る。 ? 例: ? std::atomic<int> // アトミックな int ? std::atomic<void*> // アトミックな void* ? なんでもアトミックにできるわけではなく、T は trivially copyable なものに制限されている。 ? つまり、T はユーザ定義のコピーコンストラクタ、ムーブコンストラクタ、 代入演算子、デストラクタを持てない。
- 37. atomic std::atomic<int> x; // 0 で初期化される x.store(42); // x に 42 を書き込む cout << x.load() << endl; // x の値を読む x.fetch_add(1); // 値を 1 増やす cout << x.load() << endl; // 43 が出力される // x == y ならば x に 100 を代入 (いわゆるCAS) int y = 43; x.compare_exchange_strong(y, 100);
- 38. atomic と happens before アトミックオブジェクト M に対する書き込み操作 W と M に対する読み込み操作 R があるとする。 もし R が W の書き込んだ値を読んだとすると、 W happens before R が成り立つ。 (このとき W synchronizes with R という) ※ memory_order が relaxed や consume でない場合
- 39. atomic と happens before std::atomic<bool> done = false; // global variable double ans = 0.0; // global variable // Thread 1 ans = complex_computation(); done.store(true); // Thread 2 while (!done.load()) /* busy loop */; cout << ans << endl; ? atomic 変数を使うことにより、done に関する data race を解消。 ? done の store-load により、ans の書き込みと ans の読み込みの 間にも happens before 関係が入る。
- 40. atomic と happens before ans = complex_computation(); done.store(true); done.load() done.load() done.load() done.load() cout << ans << endl; 同一スレッドなので happens before synchronize!! 同一スレッドなので happens before
- 41. atomic と happens before ans = complex_computation(); done.store(true); done.load() done.load() done.load() done.load() cout << ans << endl; 同一スレッドなので happens before synchronize!! 同一スレッドなので happens before
- 42. mutex ? std::atomic<T> では、一回の store や fetch_add など をアトミックに実行できる。 ? しかし、実際にはもっと複雑な計算をアトミックにやらないとい けない場合が多い。 ? std::mutex を使えば、lock() してから unlock() する までの間を排他処理することができる。 ? つまり、lock() から unlock() までの間を複数のスレッドが同時に実 行しないことを保証できる。
- 43. mutex map<string, string> pages; // global variable mutex pages_mutex; // global variable void save_page(const string& url) { result = (url にアクセスして内容を取得); pages_mutex.lock(); // 例外安全性はとりあえず置いておく pages[url] = result; pages_mutex.unlock(); } int main() { // 並列にウェブサイトをクロール thread t1(save_page, "http://foo"); thread t2(save_page, "http://bar"); t1.join(); t2.join(); }
- 44. ロックしてるから安全？ string* pHello = nullptr; // global variable mutex mtx; // global variable // singleton() は複数のスレッドから並列に呼ばれる void singleton() { // double-checked locking pattern のつもり if (pHello == nullptr) { mtx.lock(); // とりあえず例外安全性には目をつぶる if (pHello == nullptr) pHello = new string("Hello"); mtx.unlock(); } // シングルトンなオブジェクトへのアクセス cout << *pHello << endl; }
- 45. ロックしてるから安全？ string* pHello = nullptr; // global variable mutex mtx; // global variable // singleton() は複数のスレッドから並列に呼ばれる void singleton() { // double-checked locking pattern のつもり if (pHello == nullptr) { mtx.lock(); // とりあえず例外安全性には目をつぶる if (pHello == nullptr) pHello = new string("Hello"); mtx.unlock(); } // シングルトンなオブジェクトへのアクセス cout << *pHello << endl; } undefined behavior
- 46. mutex と happens before ? 単一の mutex に対する lock(), unlock() はある全順序 S に従って起こる。 ? スレッドA, B, C, D があるときに、スレッド A から見て C → D の順で ロックを取ったように見えたとしたら、B から見ても C → D の順でロック を取ったように見える。 ? U をある mutex に対する unlock 操作、 L を同じ mutex に対する lock 操作とする。 このとき、S の上で U < L ならば U happens before L である。
- 47. ロックしてるから安全？(再掲) string* pHello = nullptr; // global variable mutex mtx; // global variable // singleton() は複数のスレッドから並列に呼ばれる void singleton() { // double-checked locking pattern のつもり if (pHello == nullptr) { mtx.lock(); // とりあえず例外安全性には目をつぶる if (pHello == nullptr) pHello = new string("Hello"); mtx.unlock(); } // シングルトンなオブジェクトへのアクセス cout << *pHello << endl; } undefined behavior
- 48. happens before 関係を図示すると… pHello == nullptr mtx.lock() pHello == nullptr pHello = new string(..) mtx.unlock() cout << *pHello << endl pHello == nullptr cout << *pHello << endl
- 49. happens before 関係を図示すると… pHello == nullptr mtx.lock() pHello == nullptr pHello = new string(..) mtx.unlock() cout << *pHello << endl pHello == nullptr cout << *pHello << endl
- 50. happens before 関係を図示すると… pHello == nullptr mtx.lock() pHello == nullptr pHello = new string(..) mtx.unlock() cout << *pHello << endl pHello == nullptr cout << *pHello << endl 実際、pHello が読めた としても、pHello が指す 先が読めるとは限らない。
- 51. 直し方 直し方はいろいろある。 1. pHello の型を atomic<string*> にする。 ? こうすると、 pHello.store(new string(...)) と pHello.load() == nullptr の間に happens before 関係が入る。 2. double-checked locking pattern を使わずに、いきなり lock する。 ? mtx.unlock() happens before mtx.lock() となるので OK。 3. Mayers' singleton を使う。
- 52. まとめ ? 非アトミックなオブジェクトに対して、互いに happens before 関係にない読み書きが発生すると data race。 ? 同じスレッド上の評価は自明な順番で happens before 関係 が入る。 ? 同一のアトミックオブジェクトに対する store と load は条件を 満たすと happens before 関係を作る。 ? 同一の mutex に対する unlock と lock は条件を満たすと happens before 関係を作る。
- 53. 参考文献 ? Working Draft, Standard for Programming Language C++ https://github.com/cplusplus/draft ? cppreference.com http://cppreference.com/