そろそろvolatileについて一言いっておくか

+65

No comments posted yet

Comments

Slide 1

そろそろvolatileについて 一言いっておくか

Slide 2

今回のキーワード アトミック変数 メモリバリア happens before 正しく同期化されたコード volatile

Slide 3

マルチスレッドと排他制御 マルチスレッドプログラミングで苦労する点 同じ変数やオブジェクトが複数のスレッドから 同時にアクセスされる可能性がある。 mutex などの排他制御(ロック)を使って対処 あらゆる変数を排他制御しなければならないの?ロックによるパフォーマンスの劣化も気になる。 ⇒ もっと軽量の仕組みはないの?

Slide 4

スレッド間通信のprimitive スレッド間でデータをやり取りするための最も基本的な仕組み(primitive) それが… volatile アトミック変数とメモリバリア

Slide 5

アトミック変数とは 「アトミック変数」とは 複数スレッドが同時に読み書きなどの操作を行っても、それらの操作が順々に行われているように見えることが保証されている変数

Slide 6

アトミック変数へのloadとstore (1) // 初期値 atomic<int> a = -1 スレッド1: スレッド2: // aに1を代入(store) // aの値を読み出す(load) a.store(1) r = a.load() r の値は -1 または 1 のどちらかになることが保証される

Slide 7

アトミック変数へのloadとstore (2) // 初期値 atomic<int> a = 0 スレッド1: スレッド2: a.store(1) a.store(-1) a の値は 0 ⇒ 1 ⇒ -1 0 ⇒ -1 ⇒ 1 のいずれかの順序で変化することが保証される

Slide 8

load, storeのアトミック性 当たり前のようだが非常に大切な性質 アトミック性が保証されない変数に対して同様にアクセスした場合、たとえば上位bitと下位bitが混ざった値になってしまうかも… (例: 32bitアーキテクチャでの int64_t (long long)型変数への読み書き)

Slide 9

アトミック変数への複雑な操作 多くのアトミック変数の実装には、読み込みと書き込みを同時に行う操作も提供されている r1 = a.exchange(r2) ⇒ { r1 = a; a = r2; } // 読み込みと同時に書き込み r1 = a.fetch_add(r2) ⇒ { r1 = a; a = a + r2; } // 読み込みと同時に加算 など…

Slide 10

アトミック変数のもう一つの性質 アトミック変数への書き込みは、いずれ必ず他スレッドからも見えるようになる atomic<int> a = 0; スレッド1: スレッド2: a.store(1); while (a.load() != 1) { } この場合、スレッド2のwhile文は無限ループにならないことが保証される。

Slide 11

アトミック変数と普通の変数の違い アトミック変数は、複数のスレッドからアクセスされても大丈夫なように設計された変数 ⇒ アトミックではない普通の変数は、最適化などの影響により、マルチスレッドでは予期せぬ実行結果となることがある。 マルチスレッドプログラムでは全ての変数をアトミック変数にしなければならないの? ⇒ No! 普通の変数についても、マルチスレッドでの動作を保証する仕組みが別に存在する!

Slide 12

以後の説明では変数を以下のように 表記します a, a1, a2 … アトミック変数 x, y, z スレッド間でアクセスされる可能性がある アトミック変数以外の普通の変数 r, r1, r2 … ローカル変数(レジスタ) また、明示的に示さない場合の各変数の初期値は0とします

Slide 13

リオーダーとは? 「リオーダー」 プログラム実行速度の向上などの目的で実行順序を入れ替える、最適化手法の一つ コンパイラがプログラムコードを機械語に変換するとき CPUが機械語のコードを実際に実行するとき キャッシュメモリの影響などを考慮して命令の実行順序を入れ替える

Slide 14

リオーダーが出来ない状況 当然ながら、実行結果が変わってしまうようなリオーダーは禁止 x = 1; // …① y = x; // …② ⇒ ①と②を入れ替えると y に代入される値が変わってしまうのでダメ! ⇒でも、②の右辺を定数1に置換する最適化はOK

Slide 15

リオーダーできる例 では、以下の例はリオーダー可能? // 例1 x = 1; // …① y = 1; // …②´ // 例2 r1 = y; // …③ r2 = x; // …④ 最終的な実行結果は変わらないので、 ①と②´、③と④をそれぞれ入れ替えるのはOK

Slide 16

…ただし、シングルスレッドに限る 前述の例をマルチスレッド化すると… // スレッド1 // スレッド2 x = 1; // …① r1 = y; // …③ y = 1; // …②´ r2 = x; // …④ r1 == 1 && r2 ==0 となることはありえない、 …はず。 でも、リオーダーを考慮すると、ありえる。

Slide 17

マルチスレッドでの最適化の困難さ マルチスレッドでは、ちょっとした最適化でも実行結果に影響を及ぼす ⇒ マルチスレッドでの実行結果も変えないようにリオーダーなどを制限すると、最適化する余地がほとんど無くなってしまう!! ⇒ 実行性能と正確性の板ばさみ

Slide 18

マルチスレッドでの最適化の原則 よって、最適化の規則を以下のように定める シングルスレッドでの実行結果が変わらない限り、どんな最適化も基本的には許可する。 最適化がマルチスレッドでの動作に悪影響を及ぼさないよう、最適化を制限する手段を処理系は提供する。 ⇒ それが「メモリバリア(メモリフェンス)」

Slide 19

メモリバリアの基本は2種類 releaseバリア acquireバリア 命令① 命令① release_barrier(); acquire_barrier(); 命令② 命令② releaseバリア 先行する命令が、バリアを超えて後ろにリオーダーされるのを禁止する。 acquireバリア 後続の命令が、バリアを超えて前にリオーダーされるのを禁止する。 OK OK

Slide 20

アトミック変数とメモリバリアの 組み合わせ アトミック変数とメモリバリアは一緒に用いる アトミック変数へのstore + releaseバリア 処理① a.store_release(r); アトミック変数からのload + acquireバリア r = a.load_acquire(); 処理②

Slide 21

アトミック変数とメモリバリアを組み合わせることで、異なるスレッドの命令間に順序付けをすることができる atomic<int> a = 0; int x = 0; スレッド1: スレッド2: x = 1; // …① a.store_release(1); r1 = a.load_acquire(); if (r1 == 1) { r2 = x; // …② } 【実行結果が r1 == 1 だった場合、r2の値は? 】

Slide 22

スレッド1: スレッド2: x = 1; // …① a.store_release(1); r1 = a.load_acquire(); if (r1 == 1) { r2 = x; // …② } store_release()で書き込んだ値をload_acquire()で読み込むことで、 2つの間に前後関係が生まれる。 この関係を “synchronize with” と呼ぶ。 synchronize with

Slide 23

スレッド1: スレッド2: x = 1; // …① a.store_release(1); r1 = a.load_acquire(); if (r1 == 1) { r2 = x; // …② } releaseバリアのため、①の書き込みは必ず store_release() より前に行われる (xへの書き込みを後回しにするのは禁止!) acquireバリアのため、②の読み込みは必ず load_acquire() の後に行われる (xの値の先読みは禁止!) s.w.

Slide 24

スレッド1: スレッド2: x = 1; // …① a.store_release(1); r1 = a.load_acquire(); if (r1 == 1) { r2 = x; // …② } synchronize with関係とメモリバリアの効果により、①と②の間に保証された順序関係が生じる この関係(“happens before” と呼ぶ)が存在することにより r2 == 1 が保証される happens before

Slide 25

スレッド1: スレッド2: スレッド3: x = 1; // …① a1.store_release(1); r1 = a1.load_acquire(); if (r1 == 1) { r = x; // …② a2.store_release(1); r2 = a2.load_acquire(); } if (r2 == 1) { x = 2; // …③ } ①の書き込みは②より前だが、③の書き込みは②より後 ⇒ よって r == 1 となる。 推移的なhappens before関係(1) h.b. h.b.

Slide 26

スレッド1: スレッド2: スレッド3: x = 1; // …① a1.store_release(1); r1 = a1.load_acquire(); if (r1 == 1) { x = 2; // …② a2.store_release(1); r3 = a2.load_acquire(); } if (r3 == 1) { r = x; // …③ } ①で書き込まれた値は、その後の②で書き込まれた値によって上書きされる ⇒ よって r == 2 となる。 推移的なhappens before関係(2) h.b. h.b.

Slide 27

スレッド1: スレッド2: スレッド3: x = 1; // …① a.store_release(1); r1 = a.load_acquire(); r3 = a.load_acquire(); if (r1 == 1) { if (r3 == 1) { r2 = x; // …② r4 = x; // …③ } } ②も③も、①より後なので、 r2 == 1 かつ r4 == 1 となる。 ②と③の間には happens before の関係が無いが、問題ない。 happens before関係がない場合(1) h.b. h.b. ?

Slide 28

スレッド1: スレッド2: スレッド3: x = 1; // …① x = 2 // …② a1.store_release(1); a2.store_release(1); r1 = a1.load_acquire(); r2 = a2.load_acquire(); if (r1 == 1 && r2 == 1) { r = x; // …③ } ①と②の間には happens before の関係がない ⇒このような状態を “data race” と呼ぶ。 happens before関係がない場合(2) ?

Slide 29

スレッド1: スレッド2: x = 1; // …① a.store_release(1); r1 = a.load_acquire(); x = 2; // …③ if (r1 == 1) { r = x; // …② } ②と③の間には happens before の関係がない ⇒これも “data race” である。 happens before関係がない場合(3) ? h.b.

Slide 30

data raceとは アトミック変数ではない普通の変数に対して、異なるスレッド上からの 書き込みと書き込み または 書き込みと読み込み があり、2つの間に happens before の関係がない場合を “data race” と呼ぶ。

Slide 31

data race が起きると? data race の結果はどうなるのか? Javaの場合 「あらゆる最適化を考慮した上で起こり得る、全ての結果候補のうちのいずれか」 C++の場合 undefined (未定義)。「何が起こるかわからない」 要するに、「data raceが起きた時点で負け」 data race が起きないプログラムコードのことを、「正しく同期化されている」と呼ぶ

Slide 32

正しく同期化されたコードとは data raceが起きないように記述されたコード アトミック変数とメモリバリアを組み合わせることで、共有変数への各スレッドのアクセスが適切に順序付けられているコード ⇒ プログラムコードを正しく同期化することで、最適化によるマルチスレッドでの異常な動作を防ぐことができる

Slide 33

正しく同期化されたコードを書くには 正しく同期化されたコードを書くための三か条 変更したデータを、他スレッドからもアクセスできるようにするときは、releaseバリアを発行する。 他スレッドが変更したデータへアクセスするときには、acquireバリアを発行する。 あるデータを他スレッドが読み書きしているタイミングでは、そのデータへの書き込みを行わないようにする。

Slide 34

正しく同期化されたコードの例(1) h.b. Hoge* x; atomic<bool> a = false; スレッド1: スレッド2: x = new Hoge(); a.store_release(true); while (!a.load_acquire()) { } x->foo(); 正しく同期化されているので、Hogeオブジェクトへはスレッド2から安全にアクセスできる

Slide 35

正しく同期化されたコードの例(2) atomic<Hoge*> a = NULL; スレッド1: スレッド2: Hoge* r1 = new Hoge(); Hoge* r2; a.store_release(r1); do { r2 = a.load_acquire(); } while (r2 == NULL); r2->foo(); 正しく同期化されているので、Hogeオブジェクトへはスレッド2から安全にアクセスできる h.b.

Slide 36

スピンロックへの応用 アトミック変数とメモリバリアを用いると、 いわゆる「スピンロック」も実現できる。 atomic<bool> a = false; void spin_lock() { while(a.exchange_acquire(true)) { } } void spin_unlock() { a.store_release(false); }

Slide 37

スピンロックによる同期化 スレッド1: スレッド2: spin_lock(); x = 1; spin_unlock(); spin_lock(); r = x; spin_unlock(); スピンロックのもつメモリバリア効果によりhappens before関係が生まれるので、変数を安全に共有できる

Slide 38

排他制御とメモリバリア スピンロックに限らず、スレッド間の排他制御や同期化を行う仕組み(mutexやセマフォ等)は、メモリバリア効果も持っている ⇒ よって、これらを用いて排他制御を行うことも 「正しく同期化」していることになる ちなみに、“acquireバリア”, “releaseバリア” という名称は、ロック取得と開放のもつメモリバリア効果に対応して名付けられている。

Slide 39

ここまでのまとめ 最適化の影響を考えずにマルチスレッドなプログラムを書くと、予期しない実行結果になることがある。 アトミック変数とメモリバリアを使って正しく同期化されたコードを書けば、マルチスレッドでも安全にデータ共有を行うことができる。 ロックなどの排他制御の仕組みも、メモリバリアの効果を持っている。

Slide 40

volatileの出番は? ここまでアトミック変数とメモリバリアについて説明してきました。 「ところで、 volatile変数ってアトミック変数やメモリバリアの代わりにならないの?」 ⇒ 答: C/C++においては「ならない」

Slide 41

volatileの問題点その1 volatile変数はアトミック性が保証されない ⇒ ++ や += などの演算子はもちろん、単なるloadやstoreも型によってはアトミックとならない volatile long long v; v = 5; movl $5, v movl $0, v+4 64bit変数への代入が2命令に分かれてしまう x86用gccでコンパイル

Slide 42

volatileの問題点その2 volatile変数はメモリバリア効果を持たない volatile int v; int x, y; x = 1; r1 = x; v = 2; r2 = v; y = 3; r3 = y; volatile変数をまたいだリオーダーが自由に起こる

Slide 43

volatileの問題点その2 一応、volatile変数同士では、コンパイラによるリオーダーはされないが… volatile int v1, v2; v1 = 1; r1 = v1; v2 = 2; r2 = v2; これでは、スレッド間で共有される全ての変数にvolatileを付けなければならなくなる!

Slide 44

volatileの問題点その3 CPUによってもリオーダーされることがあるアーキテクチャ(PowerPCなど)では、機械語レベルでも「メモリバリア命令」が必要となる ⇒ が、コンパイラがvolatile変数の読み書きに対してメモリバリア命令を発行してくれる保証は無い つまり、CPUの種類によっては、volatile同士であってもリオーダーされる可能性がある

Slide 45

volatileに関する都市伝説 要するに、C/C++のvolatileはマルチスレッドのことを何も考えていない! 「volatileと宣言された変数はマルチスレッドで安全に使用できます」 「複数のスレッドから読み書きされる変数にはvolatileを付けて最適化を抑制しましょう」 ⇒ NG!! ちゃんと、アトミック性やメモリバリア効果が保証された仕組みを使わなければならない

Slide 46

そしてatomicへ… 次期C++標準である C++0x では、アトミック変数やメモリバリアの仕様が登場する volatileに関する定義はそのままで、アトミック型を別途定義している namespace std { template<class T> struct atomic; }

Slide 47

C++0xでのメモリバリア C++0xのatomic型では、メモリバリアの有無を引数で指定する void store(T, memory_order = memory_order_seq_cst); T load(memory_order = memory_order_seq_cst); デフォルトでは「メモリバリアあり」 「ゼロオーバーヘッド原則」のC++がコストのかかるメモリバリア付きをデフォルトとすることからも、アトミック変数とメモリバリアを一緒に扱うことの重要性がわかる。

Slide 48

Javaのvolatile 一方、Javaのvolatile変数は、load, storeのアトミック性やメモリバリア効果を備えている つまり、C++0xのatomic型に近い使い方ができる。 ただし、 ++ や += 演算子はアトミックではないので、これらのアトミック演算が必要であれば java.util.concurrent.atomic.Atomic* を使う。 C/C++とJavaでは、volatileの意味が全く変わってしまっている

Slide 49

アトミック変数の他の実装 C++0x や Java ではアトミック変数やメモリバリアの仕組みが用意されている。 では、他の言語ではどうなってるのか? 特に、現世代の C/C++ ではどうすればいいのか? ⇒ libpthreadの実装や、OSのkernelのコードが参考になる。 例として、FreeBSD kernelのコードを挙げてみる。

Slide 50

Kernelとマルチスレッド マルチプロセッサに対応したOSのkernelは、巨大なマルチスレッドプログラムでもある Kernel内ではlibpthreadのようなライブラリは使用できない ⇒ スレッド間排他などの仕組み(mutexなど)も自力で実装しなければならない FreeBSD kernelでのスレッド対応コードを追いかけていくと到達するのが… ⇒ atomic.h

Slide 51

FreeBSDのatomic.hとは FreeBSDでは、kernel内スレッド同期のためのprimitiveな部品として、まず「メモリバリア付きアトミック変数」を作った ⇒ それが atomic.h にて定義されるAPI (man 9 atomic) インラインアセンブラやコンパイラの拡張機能を用いて実装されている

Slide 52

atomic.hのAPI(1) 単純なload、store操作 // アトミックなload + acquireバリア u_int atomic_load_acq_int(volatile u_int *p) // アトミックなstore + releaseバリア void atomic_store_rel_int(volatile u_int *p, u_int v)

Slide 53

atomic.hのAPI(2) 複雑なアトミック操作も定義される // Compare-and-Set 命令 int atomic_cmpset_ptr(volatile uintptr_t *dst, uintptr_t old, uintptr_t new) // 以下の操作をアトミックに行う if (*dst == old) { *dst = new; return 1; } else return 0;

Slide 54

atomic.hのAPI(3) アトミック操作の多くに、メモリバリアの有無によるバリエーションが用意されている atomic_cmpset_ptr(…) // メモリバリアなし atomic_cmpset_acq_ptr(…) // acquireバリア付き atomic_cmpset_rel_ptr(…) // releaseバリア付き

Slide 55

atomic.hの利用例 FreeBSD kernelで最もよく使われる排他制御APIが mutex(9) もちろん mutex も atomic.h で定義されているアトミックAPIを用いて作られている

Slide 56

デバッグやプロファイリング関係のコードを取り除くと以下のようになる void mtx_lock(struct mtx *m) { uintptr_t tid = (uintptr_t)curthread; if (!atomic_cmpset_acq_ptr(&m->mtx_lock, MTX_UNOWNED, tid)) _mtx_lock_sleep(m, tid, 0, NULL, 0); // 競合時の処理 } void mtx_unlock(struct mtx *m) { uintptr_t tid = (uintptr_t)curthread; if (!atomic_cmpset_rel_ptr(&m->mtx_lock, tid, MTX_UNOWNED)) _mtx_unlock_sleep(m, 0, NULL, 0); // 競合スレッドがいた場合の処理 } それぞれに「メモリバリア付きアトミック命令」が使用されている

Slide 57

atomic.hによる アーキテクチャ間相違の隠蔽 FreeBSDでは、アトミック変数と acquire / release メモリバリアを最も基本的な部品として用意し(atomic.h)、それらを用いて複雑な同期機構を作っている atomic.hの実装はアーキテクチャ毎に異なるが、それを利用する同期機構のコードは全てのアーキテクチャで同一 ⇒ atomic.hのAPIが、アーキテクチャ間の違いをうまく吸収している

Slide 58

FreeBSDでの実装から学べること FreeBSD kernelで採用された「アトミック変数 + acquire/releaseバリア」というAPIは、マルチスレッドプログラミングにおけるCPUアーキテクチャの違いをうまく隠蔽することができる Java や C++0x が採用した仕組みも同じ ⇒ 抽象化の度合いと実行性能のバランスが取れていることを示している

Slide 59

まとめ アトミック変数とacquire/releaseメモリバリアは、マルチスレッドプログラムを正しく動作させるための重要な仕組みである。 この仕組みは、 C++0x や Java, FreeBSD kernel にも採用されている。 この仕組みを使って「正しく同期化された」プログラムを作ることを心がけましょう!

Summary: マルチスレッドプログラミングにおける重要な概念であるアトミック変数とメモリバリアについて説明します。

Tags: multithreading java c++ freebsd volatile

URL:
More by this User
Most Viewed
Previous Page Next Page