マルチコア時代の
Lock-free入門
Lock-freeアルゴリズムとは
マルチコアのCPUが当たり前の時代
単にマルチスレッド化するだけではダメ！
並列動作ができないプログラムは悪
アムダールの法則：並列に処理できない部分が
少しでもあると、性能に大きく影響する
並列性を高め、性能をより発揮させるための
手法が重要になってくる
その一つが「Lock-freeアルゴリズム」
サンプルプログラム
int alice = 100;
int bob = 0;
void transfer(int amount) {
alice -= amount;
bob += amount;
}
int sum() {
return alice + bob;
}
関数transferを何度呼び出しても、
関数sumの結果は変わらないはず。
でも、transferとsumを別スレッドが
同時に実行すると、それが崩れる。
つまり…スレッドセーフでない
スレッドセーフにするための手段
ロックによる排他制御
データ構造に対する操作を、同時には1スレッド
だけに制限する
ロックが競合すれば並列性は下がる
Lock-freeアルゴリズム
アトミックな操作の組み合わせで処理を行う
並列実行を妨げない
ポインタを用いたLock-freeの実現
transfer(20) の処理
(1) 現在のデータをもとに、
更新後のデータを格納した
オブジェクトを作る
(2) 更新後のデータオブ
ジェクトを指し示すように
ポインタを更新する
sum() の処理
alice = 100
bob = 0
alice = 80
bob = 20
この操作の前後で、データの
一貫性が保たれていることが
重要！
ポインタ
どちらを指している
かはタイミング次第
(1) ポインタの指し
示すオブジェクトの
参照を得る
(2) 上記オブジェクト
のaliceとbobの合計
を返す
＊重要＊
ポインタの読み書きはアトミック
(不可分)でなければならない
C++0xでの実装例
struct Node {
int alice;
int bob;
};
C++0xで導入された
アトミックなポインタ型
std::atomic<Node*> data = new Node();
// 初期値の設定については省略
void transfer(int amount) {
Node* old = data;
Node* node = new Node();
node->alice = old->alice - amount;
node->bob = old->bob + amount;
data = node;
}
int sum() {
Node* node = data;
return node->alice + node->bob;
}
同時に更新するときの問題点
A
transfer(20)
(1) Aのデータをもとに、更
新後のオブジェクトBを作
る
(2) オブジェクトBを指し
示すように、ポインタを
更新する
alice = 100
bob = 0
transfer(10)
B
alice = 80
bob = 20
ポインタ
(1) Aのデータをもとに、更
新後のオブジェクトCを作
る
(2) オブジェクトCを指し
示すように、ポインタを
更新する
C
alice = 90
bob = 10
この変更結果が
失われてしまう
ポインタの指す先がAからBに
変わっているのに気付かずに、
Cで更新してしまったのが問題
Compare-and-swap命令
「元の値から変わっていなければ、新しい値に
更新する」という操作をアトミックに行う命令
⇒ Compare-And-Swap (CAS)
if (data == old_value) {
data = new_value;
return true;
} else {
return false;
}
比較が一致しなかったときは
dataの現在値を返すような
バリエーションもある
CASを用いた実装例
if (data == old) {
void transfer(int amount) {
data = node;
Node* old = data;
return true;
} else {
Node* node = new Node();
old = data;
do {
return false;
node->alice = old->alice - amount;
}
node->bob = old->bob + amount;
} while (!data.compare_exchange_strong(old, node));
}
CASを使って更新を試み、失敗したらやり直す
⇒ “CAS loop” と呼ばれる基本パターン
Lock-freeアルゴリズムの基本
一貫性を保持したまま、アトミック操作の組み
合わせによってデータを更新していく
⇒ このアルゴリズムがLock-freeのキモ
Compare-and-swap命令は超重要
とりあえず実行してみて、失敗したらやり直す
⇒ いわゆる「楽観的同時実行制御」
Lock-freeアルゴリズムの落とし穴
「リオーダー」の問題
「メモリ回収」の問題
落とし穴その１ － リオーダー
「リオーダー」とは
⇒ コンパイラ、VM、CPUなどにより命令の実行順
序が変えられること
性能向上のために行うことなので、これ自体は悪
いことではない
マルチスレッドプログラムでは、リオーダーの
ために不正な実行結果となることがある
⇒ 悪影響のあるリオーダーを防ぐ仕組みが必要
それが「メモリバリア」
メモリバリアを正しく使うには
メモリバリアが必要な場所はどこか？
基本的にはアトミック命令の前後
C++0xのstd::atomic、JavaのAtomic*型など
は、メモリバリアとしての効果も持つ
とりあえずは、この仕組みに任せておけばOK
より深い話に興味のある方はこちら↓
「そろそろvolatileについて一言いっておくか」
http://d.hatena.ne.jp/bsdhouse/20090720/1248085754
落とし穴その２ － メモリ回収
このオブジェクトが
解放されていない！
transfer() の処理
(1) 現在のデータをもとに、
更新後のデータを格納した
オブジェクトを作る
(2) 更新後のデータオブ
ジェクトを指し示すように
ポインタを更新する
alice = 100
bob = 0
alice = 80
bob = 20
ポインタ
単純にdeleteを加えてみる
void transfer(int amount) {
Node* old = data;
Node* node = new Node();
do {
node->alice = old->alice - amount;
node->bob = old->bob + amount;
} while (!data.compare_exchange_strong(old, node));
delete old;
}
⇒ ダメ。
単純deleteで問題が出るケース
transfer() の処理
(1) 現在のデータをもとに、
更新後のデータを格納した
オブジェクトを作る
(2) 更新後のデータオブ
ジェクトを指し示すように
ポインタを更新する
(3) 更新前のデータオブ
ジェクトをdeleteする
sum() の処理
alice = 100
bob = 0
alice = 80
bob = 20
ポインタ
(1) ポインタの指し
示すオブジェクトの
参照を得る
(2) 上記オブジェクト
のaliceとbobの合計
を返す
deleteされたオブジェクトへ
アクセスしてしまう！
オブジェクトを再利用してみる
単純にdeleteするのはダメ。でも、そのままだ
とメモリリークしてしまう。
⇒ オブジェクトを使いまわしてみては？
transfer() の中で delete せずに、次回の
transfer() 呼び出しのときに再利用してみる
オブジェクト再利用での失敗例(1)
次回再利用するために、
保持しておく
transfer(20)
[1回目]
transfer(20)
[2回目・途中まで]
alice = 60
100
bob = 0
alice = 80
bob = 20
sum()
ポインタ
(1) ポインタの指し
示すオブジェクトの
参照を得る
(2) 上記オブジェクト
のaliceとbobの合計
を返す
2回目のtransferによって書
き換えられている途中の値
が見えてしまう！
オブジェクト再利用での失敗例(2)
A
transfer(20)
[1回目]
transfer(20)
[2回目]
transfer(10)
alice = 60
100
bob = 40
0
B
alice = 80
bob = 20
C
ポインタ
(1) Aのデータをもとに、更
新後のオブジェクトCを作
る
(2) CAS命令を用いて、
Aを指しているポインタ
を、Cを指すように更新
する
alice = 90
bob = 10
「ABA問題」
ポインタの指す先が同じAなので、
その内容が変化しているときでも
CASが成功してしまう。
オブジェクトを安全に再利用するには
更新回数をカウントする「タグ」をポインタに付
ける
ポインタを更新するたびに、タグの値もインクリメ
ントする
操作の途中でタグやポインタの値が変化してい
たらやり直し
⇒ タグとポインタをまとめて一度に扱えるCAS
命令が必要
再利用オブジェクトの管理問題
再利用するオブジェクトをどう管理するか？
スレッド毎に保持するのが基本パターン
⇒ スレッド毎の管理であれば排他の必要が無い
各スレッドで、オブジェクトの生成・破棄に偏りが
ある場合が問題
⇒ 再利用オブジェクトをスレッド間で共有しようとす
ると、そこでも排他制御が必要になってくる
オブジェクト再利用以外の解決方法
C++0xには参照カウンタ方式のスマートポイ
ンタ std::shared_ptr がある！
しかも、マルチスレッドに対応していて、CAS命令
などもある
さっそく使ってみよう！
C++0x shared_ptr による実装
std::shared_ptr<Node> data(new Node());
void transfer(int amount) {
std::shared_ptr<Node> old = std::atomic_load(&data);
std::shared_ptr<Node> node(new Node());
do {
node->alice = old->alice - amount;
node->bob = old->bob + amount;
} while (!std::atomic_compare_exchange_strong(&data, &old, node));
}
int sum() {
std::shared_ptr<Node> node = std::atomic_load(&data);
return node->alice + node->bob;
}
C++0x shared_ptr の効果
参照が無くなったオブジェクトは必ず解放される
メモリリークの心配なし
それを参照するスレッドが一つでも残っている
限り、オブジェクトの再利用はされない
ABA問題も発生しない
これで完璧！ Lock-free完成！！
…とはなりません
マルチコアプログラミングのセオリー
複数のスレッドが同一メモリ領域に対して書
き込みを行うのはコスト大
CASやアトミックな加算・減算などは数百クロック
サイクルを超えることも
パフォーマンスを出すためのセオリー
書き込みを行うメモリ領域はスレッド毎に分散さ
せる
CASなどのアトミック命令は必要最小限にする
C++0x shared_ptr の欠点
std::shared_ptr は参照カウンタ方式
対象オブジェクト毎に参照カウンタがあり、それを
アトミックにインクリメント・デクリメントする
つまり、 std::shared_ptr で管理される
オブジェクトを複数スレッドから扱うのは、
とてつもなく遅い
参照カウンタに対する操作は？
std::shared_ptr<Node> data(new Node());
＋１
void transfer(int amount) {
std::shared_ptr<Node> old = std::atomic_load(&data);
std::shared_ptr<Node> node(new Node());
do {
＋１
CAS
node->alice = old->alice - amount;
node->bob = old->bob + amount;
} while (!std::atomic_compare_exchange_strong(&data, &old, node));
}
－１
－１
－１
＋１
int sum() {
std::shared_ptr<Node> node = std::atomic_load(&data);
return node->alice + node->bob;
}
－１
参照カウンタ方式の限界
参照カウンタ方式である std::shared_ptr の
実行コストは、Lock-freeアルゴリズムのメリッ
トを台無しにする！
マルチスレッド環境において、もっと低コスト
でオブジェクトの安全な破棄を行なう方法は
無いのか？
Hazard pointer
他スレッドのローカル変数内に、用済みオブ
ジェクトへの参照が残っているときが問題
⇒ 用済みオブジェクトの破棄を、他スレッドがそれ
を参照しなくなるタイミングまで遅らせればよい
⇒ でも、他スレッドのローカル変数が何を参照して
いるかを、直接的に調べることはできない
⇒ そこで登場するのが “Hazard pointer”
Hazard pointer とは
スレッド毎に用意されるポインタ変数
書き込みは、それを所有するスレッドだけが
可能
読み込みは、どのスレッドからも自由に行な
える
Hazard pointerのアルゴリズム
transfer() の処理
(1) 現在のデータをもとに、
更新後のデータを格納した
オブジェクトを作る
(2) 更新後のデータオブ
ジェクトを指し示すように
ポインタを更新する
(3) 他スレッドのhazard
pointer全てをスキャンし、
更新前オブジェクトへの
参照があるか調べる
(4-a) hazard pointerに参
照があれば、今回は破棄
せず、後で3以降の処理
を再実行するためにオブ
ジェクトをストックしておく
(4-b) hazard pointerに参
照がなければ、オブジェク
トを破棄する
sum() の処理
alice = 100
bob = 0
ポインタ
alice = 80
bob = 20
alice = 60
bob = 40
Hazard pointer
(1) ポインタの指し示
すオブジェクトの参照
を得る
(2) 1のオブジェクト参
照をhazard pointerに
記録する
(3) ポインタの値を読
み取り、1の値から変
わっていないことを確
認する(変わっていた
ら1に戻る)
(4) 1のオブジェクトの
aliceとbobの合計を
計算
(5) hazard pointerの
内容をクリアする
(6) 4の結果を返す
Hazard pointer の性能
Hazard pointer のオーバーヘッドは？
書き込みはスレッド毎に別々の変数に対して行なわ
れるので、コストは低い
Hazard pointerのスキャンはコストの高い処理だが、
破棄予定オブジェクトを１個ずつ処理するのではなく、
複数個まとめて処理することで低減することが可能
書き込み順が重要なのでメモリバリアが必要
⇒ 総合的には良好な性能を示す
Garbage collection (GC) の利用
GCがあれば、オブジェクト回収の問題は解決
std::shared_ptr のようにオブジェクト参照を逐一
追いかけるよりも、一度にまとめてスキャンするほ
うが総コストは低くなる
⇒ Hazard pointer も同じコンセプト
短命なオブジェクトを使うことの多いLock-freeアル
ゴリズムは、GCと相性が良い
Lock-freeならJavaをやれ
実際、最新のJavaVMに搭載されているGC
アルゴリズムは、マルチプロセッサ上で良好
な性能を発揮する
⇒ Lock-freeアルゴリズムを勉強するなら、
JavaVM上で動く言語にすべき!!
まとめ
Lock-freeアルゴリズムの基本
Compare-and-swap (CAS)
実装上の注意点
リオーダー
メモリバリアで対処
メモリ回収
(参照カウンタ式ではない)GCがある言語を使うべき
それが無理なら「タグ付きポインタ」や「Hazard
pointer」などを使う
© Copyright 2024 ExpyDoc
