スライド 1

技術発表 10/19
che
Threads Cannot Be
Implemented As a Library
ACM SIGPLAN PLDI ’05
SESSION: Threads
はじめに

近年、マルチスレッドでプログラムを実装するこ
とが多くなってきた



ウィンドウプログラミングなどで並列性を持たせたい
今後マルチプロセッサが普及するという見方が強い
どうやってマルチスレッドを実装するか？

言語レベルでスレッドをサポートするのが理想


Java, Ada, C#
言語レベルでスレッドをサポートしていない場合は？

C, C++
ライブラリによるスレッドサポート

CやC++では、言語レベルではスレッドをサポー
トしていない

ライブラリによってスレッドを実現する


Pthreadsが有名
ライブラリレベルではスレッドは実現できない！
スレッドの実装１

以下のような状況を考える
全ての変数は0で初期化される
あるスレッドが次のコードを実行
x = 1; r1 = y;
もう１つのスレッドが次のコードを実行
y = 1; r2 = x;

r1とr2のどちらかは1になるはず

ところが、両方とも0になる可能性がある
スレッドの実装２

マルチスレッドで処理結果がおかしくなるのは最
適化が行われるため

最近のコンパイラとハードウェアはコードを効率の良
い形に整えようとする



命令順序の入れ替え
シングルスレッドだと問題ないが、マルチスレッドだと
結果が不定になる可能性
Pthreadsなどでは、このような最適化を妨げるこ
とにより並列性を確保している

例えばpthread_mutex_lock()などの関数
Pthreadsが正しく動かないケース１

以下のようなコードを考える
変数は０で初期化
if(x == 1) ++y;
if(y == 1) ++x;


このコードは競合が起きないはず
ところが最適化されると
++y; if(x != 1) --y;
++x; if(y != 1) --x;

競合が起きる！
Pthreadsが正しく動かないケース２
struct { int a:17; int b:15 } x;
x.a = 42;
↓ コンパイル後のコード
{
tmp = x;
tmp &= ~0x1ffff;
tmp |= 42;
x = tmp;
}
Pthreadsが正しく動かないケース３
struct {
char a; char b; char c; char d;
char e; char f; char g; char h; } x;
//aをロックで保護
x.b = ‘b’; x.c = ‘c’; x.d = ‘d’;
x.e = ‘e’; x.f = ‘f’; x.g = ‘g’; x.h = ‘h’;
↓ コンパイル後のコード
x = ‘hgfedcb\0’ | x.a; //ロックの意味がない
Pthreadsが正しく動かないケース４
for(…) {
…
if(mt) pthread_mutex_lock(…);
x=…x…
if(mt) pthread_mutex_unlock(…);
}
↓コンパイル後のコード
r = x;
for(…) {
if(mt) { x = r; pthread_mutex_lock(…); r = x; }
r=…r…
if(mt ) { x = r; pthread_mutex_unlock(…); r = x; }
}
x = r;
Pthreadsのパフォーマンス１
Pthreadsのロックは効率が悪い
 例えば以下のようなコードを考える
//Sieve Of Eratosthenes implementation
for(my_prime = start; my_prime < 10000; ++my_prime)
if(!get(my_prime)) {
for(multiple = my_prime; multiple < 100000000; multiple +=
my_prime)
if(!get(multiple)) set(multiple);
}
//getとsetは配列へのアクセス
//get(i) は A[i], set(i) はA[i] = true;
//Aはbooleanの配列で、素数かどうか判定する際のデータ置き場

Pthreadsのパフォーマンス２

上記「エラトステネスのふるい」のプログラムは、
スレッドが増えれば増えるほど効率が上がる

色々な状況下で実行してみて時間を計測した

Mutex, spilnlock, volatile access, cmpxchg, unsafe
access
Pthreadsのパフォーマンス３
Pthreadsのパフォーマンス４

ロックを有効にしてスレッドを増やしても、シング
ルスレッドにパフォーマンスで負けた
まとめ



ライブラリによるスレッドの実現は非現実的であ
り、非効率でもある
言語レベルでのスレッドサポートが望まれる
みんなJava Memory Modelみたいにすれば解
決するよ

Download Report