- SlideBoom

C言語で苦しむロックフリー入門
（仮）
熊崎宏樹
@kumagi
C言語
• CPUの息遣いを感じられる良い言語
• ロックフリーなプログラムを書くには避けては通れな
いsafe mamory reclamation問題に一番ダイレクトに
衝突する言語
• スペースの都合上、スライド上のコードはグローバ
ル変数モリモリだから真似しちゃダメ
• メモリ確保も絶対成功する前提で書いてるけど真似
しちゃダメ
• ほんとはキャストが必要な部分もスペースの都合で
省略
Stackについて
• 最初に入れた物が最後に出てくるデータ構造
• 積み重ねるようなデータの持ち方をするから
Stackと呼ばれる
• 今回話すstackがサポートするメソッドはpush()
とpop()のみとする
Stackについて
• void push(int x): x を上に積む。関数は何も返
さない物とする。
• int pop(): 最後に積んだ値を取ってくる。
push(1);
push(2);
push(3);
int x = pop();
int y = pop();
int z = pop();
// => x=3
// => y=2
// => z=1
C言語での実装
•構造体定義
•線形リストでスタック構造を表現
•普通は配列で作るが敢えて線形リスト
typedef struct node{
int data;
node* next;
} node_t;
node_t *head = NULL;
C言語での実装
void push(int x) {
// 初期化して
node_t *new_node =
(node_t*)malloc(sizeof(node_t));
new_node->data = x;
new_node->next = head;
//挿入
head = new_node;
}
C言語での実装
int pop() {
// 獲得して
node_t *got_node = head;
node_t *next_head = got_node->next;
int value = got_node->data;
free(got_node); // 解放して
return value; // 返却
}
並行処理実装
• 近年CPUコアは(中略)マルチスレッド(後略)
void* work(void*) {
for (int i = 0; i < 100; ++i) {
push(i);
}
}
int main(void) {
pthread_t t1, t2;
pthread_create(&t1, NULL, work, NULL);
pthread_create(&t2, NULL, work, NULL);
pthread_join(&t1);
pthread_join(&t2);
}
C言語での並行push実装
void push(int x) {
node_t *new_node =
(node_t*)malloc(sizeof(node_t));
new_node->data = x;
new_node->next = head;
pthread_mutex_lock(&stack_lock);
head = new_node;
pthread_mutex_unlock(&stack_lock);
}
C言語での並行pop実装
int pop() {
pthread_mutex_lock(&stack_lock);
node_t *got_node = head;
head = got_node->next;
pthread_mutex_unlock(&stack_lock);
int value = got_node->data;
free(got_node); // 解放して
return value; // 返却
}
Mutexでだいたい良い
• ぶっちゃけStackでなら一番パフォーマンスが
出る並行処理実装
• 「mutexを使え」が実用上もっとも正しくて賢く
てメンテナンスしやすい
Mutexなしでできるのでは？
• Compare And Swap命令を使えばできる！
Compare And Swap
• 指定したアドレスxが指定した値yだったら新しい値z
で書き換えるまでを不可分に行えるCPU命令
– 以下は疑似コード
int CAS(void** x, void* y, void* z) {
if (*x == y) {
**x = *z;
return 1;
} else {
return 0;
}
}
CASスピン
• CASを使って成功するまで無限ループする
コードを書けばロックが要らない！
Mutexを用いないとどうなるか
• 複数スレッドが同時に行うと
x==1
スレッドA
スレッドB
1.xを読み出す(1)
1.xを読み出す(2)
2.読んだ値に +1
2.読んだ値に +1
3.xを保存する(1)
3.xを保存する(3)
OK!
x==3
Mutexを用いないとどうなるか
• 複数スレッドが同時に行うと破綻する場合がある
x==1
スレッドA
スレッドB
1.xを読み出す(1)
1.xを読み出す(1)
2.読んだ値に +1
2.読んだ値に +1
3.xを保存する(2)
3.xを保存する(2)
数が合わない
x==2
CASの使い方例
int x = 0;
void add_unsafe() {
++x;
}
int x = 0;
void add_cas() {
for (;;) { // spin
int old_x = x;
if (CAS(&x,
old_x,
x+1)) {
break;
}
}
}
CASを使ってみよう
• CASのお陰で衝突しても破綻しない
x==1
スレッドA
スレッドB
1. xを読み出す(1)
2. 読んだ値に +1
3. 値が1なら2へCAS
4. 失敗したので再挑戦
5. xを読み出す(2)
6. 読んだ値に +1
7. 値が2なら3へCAS
1. xを読み出す(1)
2. 読んだ値に +1
3. 値が1なら2へCAS
数が合う！
x==3
Lock-free Stack push
void lock_free_push(int x) {
node_t *new_node =
(node_t*)malloc(sizeof(node_t));
new_node->data = x;
do {
node_t *old_head = head;
new_node->next = head;
} while (!CAS(&head, old_head, new_node));
}
Lock-free Stack Push
• CASによってリトライができるので衝突もセーフ
Lock-free Stack
↓ポインタ
A
Head
CAS
「Headが指している物を指したノードを作ってCAS」
Lock-free Stack
A
B
C
CAS
CAS
CAS
Head
D
失敗した！
Lock-free Stack
A
B
また失敗した！
C
CAS
Head
CAS
D
Lock-free Stack
A
Head
CAS
C
B
D
Lock-free Stack pop
int lock_free_pop() {
node_t *old_head;
for (;;) {
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
free(old_head);
return data;
}
}
}
Lock-free Stackからpop
A
Head
CAS
C
D
B
Lock-free Stack ABA problem
• CASは「値が一致した場合に成功する」事まで
しか確認しない。運悪く一致してしまった場合
に事故る。
Lock-free StackのABA
D
HeadがAを指してた
HeadをAからBに書
からBに書き換えれ
き換えるぞー！
るぞー！やったー！
うおおおおおー
Head
C
push(x)しよっと
もう1回pop()しよっと
Aをpop()しよっと
メモリはAでいいや
B
A
SEGV
よく言われる解決策
• Tagを付ければ解決するよ[1]
• LL/SCを使ってもいいね[1]
– LL/SCはx86系CPUでは使えない
• Double WordのCASを使って、2word目をカウ
ンタに使うとカウンタに充分なビット数が割け
るので安心
– そもそも2wordのatomicなreadが無いじゃん。
でもpushとpopの両方で増やしたら大丈夫になっ
たわ[2]
[1]2004 Maged M. Michaelら ABA Prevention Using Single-Word Instructions1
[2]The difficulty of lock-free programming: a bug in lockfree stack
Lock-free StackのABA
D
HeadがAを指してた
HeadをAからBに書
けどTag値が1じゃな
き換えるぞー！
くて4だからやり直し
うおおおおおー
Head1
Head4
Head3
Head2
C
push(x)しよっと
もう1回pop()しよっと
Aをpop()しよっと
メモリはAでいいや
B
A
大丈夫ぽい！？
だが
SEGV
Lock-free Stack pop
• TagによるABA避けをした実装
int lock_free_pop() {
node_t *old_head;
for (;;) {
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
free(old_head);
return data;
}
}
}
OSへ返却
D
head
C
B
A
返却したメモリ->next; を読む！
int lock_free_pop() {
node_t *old_head;
for (;;) {
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
free(old_head);
return data;
}
}
}
SEGV
そもそも別の解決策しかない
• メモリを適当なタイミングでfree()するのは事故の
もと
– そもそもpop()だけをlockで守る解決策もある
• この問題はガベージコレクションのある言語では
発生しない
– 全てのスレッドが参照しなくなってからfree()されるか
ら
• よし！同一の状況をCでも再現しよう
– 参照カウンタ？
• 参照時のカウンタ更新コストで死ぬ
解決策: Hazard Pointer
• どこのポインタが捨
てられたら困るかを
共有する
• 固定長のグローバル
な配列を用意する
– 1スレッドが1要素使う
• free前に他のス
レッドがそれを
使ったら待機する
volatile node_t *h_ptr[THREADS]; // global
int lock_free_pop() {
for (;;) {
h_ptr[tid] = head;
memory_fence();
if (head != h_ptr[tid]) continue;
node_t *next_head = h_ptr[tid]->next;
if (CAS(&head, h_ptr[tid], new_head)){
int data = h_ptr[tid]->data;
for (int i=0; i<THREADS;)
if (tid == i) {++i; continue}
else if (h_ptr[i] != h_ptr[tid])
++i; else sched_yield();
free(h_ptr[tid]);
return data;
}
}
}
Hazard pointer Lock-free Stack pop
volatile node_t *h_ptr[THREADS]; // global
int lock_free_pop() {
for (;;) {
h_ptr[tid] = head;
memory_fence();
if (head != h_ptr[tid]) continue;
node_t *next_head = h_ptr[tid]->next;
if (CAS(&head, h_ptr[tid], new_head)){
int data = h_ptr[tid]->data;
for (int i=0; i<THREADS;)
if (tid == i) {++i; continue}
else if (h_ptr[i] != h_ptr[tid])
++i; else sched_yield();
free(h_ptr[tid]);
return data;
}
}
}
他の全てのス
レッドが抜けるの
を待つ
D
C
B
A
volatile node_t *h_ptr[THREADS]; // global
int lock_free_pop() {
for (;;) {
h_ptr[tid] = head;
memory_fence();
if (head != h_ptr[tid]) continue;
node_t *next_head = h_ptr[tid]->next;
if (CAS(&head, h_ptr[tid], new_head)){
int data = h_ptr[tid]->data;
for (int i=0; i<THREADS;)
if (tid == i) {++i; continue}
else if (h_ptr[i] != h_ptr[tid])
++i; else sched_yield();
free(h_ptr[tid]);
return data;
解放されないので安心
}
}
}
head
patented US 20040107227
• 2010年に放棄されたとwikipediaにはあるが…
解決策：Pass the buck
• 和訳するなら「なすりつけ法」
• hazard pointerのようにglobalなhazard_ptr配
列を最初に定義するとエントリ数の需要の動
的な増減に耐えられない
• 利用する時だけhazard_ptr配列のどこを自分
のスレッドが使ってよいかをCASで取り合う技
法
• patented: US7194495 B2
– status: 認定と書いてあるので確実に危険
解決策：RCU
• Read-Copy-Updateの略でRCU
• カーネル空間内で、参照頻度の割に更新頻
度が極端に低いデータをロックなしで保護す
る為に使っているアルゴリズム
• 書き換え側のコストがすごい事になったりす
るが実用上の問題はない
RCU Lock-free Stack push
• rcu_read_lockによって
rcuクリティカルセクショ
ンを記述する
– そのセクション内のス
レッドはプリエンプショ
ンされない
• 余計な共有メモ
リを必要としない
しread側の負荷
はかなり小さい
int lock_free_pop() {
node_t *old_head;
for (;;) {
rcu_read_lock();
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
rcu_read_unlock();
synchronize_rcu();
free(old_head);
return data;
}
}
}
RCU Lock-free Stack pop
• RCUでメモリ解放を遅延
int lock_free_pop() {
node_t *old_head;
for (;;) {
rcu_read_lock();
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
rcu_read_unlock();
synchronize_rcu();
free(old_head);
return data;
}
}
}
他の全てのス
レッドが抜けるの
を待つ
D
C
B
A
解放されないので安心！
head
int lock_free_pop() {
node_t *old_head;
for (;;) {
rcu_read_lock();
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
rcu_read_unlock();
synchronize_rcu();
free(old_head);
return data;
}
}
}
RCU: Grace Period
• rcuクリティカルセクション内ではプリエンプショ
ンしなくなる
– 実を言うとプリエンプションしても良い版の実装も存
在するが詳細はまだ追ってない
• synchronize_rcuで他のスレッドが最低1回ずつ
プリエンプションするのを待つ
– 古いheadを観測して走ってるスレッドを邪魔しない
RCU: Grace Period
• プリエンプションを禁じるような操作をユーザ
空間で気軽に使われると危険が危ない
– そもそもユーザに使わせるべきではない
• つまりカーネル空間ならではの解決法であり、
ユーザ空間では使えない
解決策: Quiescent-State-Based-Reclamation
• グローバルなカウントを
増やして、それをみん
なが観測した後ならfree
してOK
– read側はglobal_countを
読むだけ
• 更新が無ければキャッ
シュラインがSステートに
落ちるので最速
– write時は更新した
global_counterが他
の全スレッドに読ま
れるまで待機する
uint64_t global_count = 0;
uint64_t local_count[THREADS] = {0};
int lock_free_pop() {
node_t *old_head;
for (;;) {
local_count[TID] = global_count;
old_head = head;
node_t *next_head = old_head->next;
if (CAS(&head, old_head, new_head)) {
int data = old_head->data;
local_count[TID] =
add_and_fetch(global_count);
for (int i=0; i < THREADS;)
if (local_count[TID] <= local_count[i])
++i; // 読まれた場合だけiが進む
free(old_head);
return data;
}
}
}
速い！
参照するメモリ数nに対して
O(1)のメモリフェンスで済む
Making Lockless Synchronization Fast: Performance Implications of Memory Reclamation
解決策: Quiescent-State-Based-Reclamatfion
• 利点:
– 特許は取られてなさげ
– read側は高速
• 欠点:
– すべてのスレッドが定期的にglobal_countを読む前
提がある
• 状況によっては結構大規模な改修になる
– read側のクリティカルセクションがネストした場合、
外側のセクションは保護対象外になってしまう
• ネスト版のEpoch Based Reclamationもあるけど今回は時
間の都合で話せない
まとめ
• とても簡単なLock-free StackひとつとってもC
言語上でスレッドセーフにするのは非常に大
変
– デバッグの難しさ
– 特許の罠
– 可変スレッド数対応
– メモリバリア厳しい
– Mutex使え

Download Report