並行システム システム情報系情報工学域, システム情報工学研究科コンピュータサイエンス専攻 新城 靖 <yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-15
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
目的
プロセスが、あるアクセスの仕方を守れば、メモリは「正しく」動作する ことを保証する。
制限が少ないと、遅くなる。使える範囲でいかに手を抜く(コストを下げる) かが大事になる。
以下で「メモリ」は、data store の意味で使う。変数かもしれないし、ファ イルかもしれないし、ページかもしれない。
メモリがページで、プロセスがプロセッサなら、分散共有メモリ(distributed shared memory,DSM)という。
a=1; a=2; print(a);
厳密一貫性では、常に 2 がプリントされる。
厳密一貫性では、「最新」の定義で、ニュートン物理学での絶対的な時間が必 要になる。
3 m 離れたコンピュータでは、光の速さででも 10ns かかる。 a=2; と print(a); 差が 1ns 以内という要求なら、光の 10 倍の速度が必要になる。
3 m P1 <---------> P2 a=1; a=2; print(a);P1、P2 はプロセス。
SMP(集中システム)ですら、キャッシュがあれば、実現不可能。
救い:実際の応用では、そこまで要求されていない。
例:厳密一貫性がある(横方向が時間軸、右に向って増加)
P1: W(x)1 P2: R(x)1例:厳密一貫性がない
P1: W(x)1 P2: R(x)0 R(x)1
いかなる実行の結果は、全てのプロセスによるメモリ(data store)に対する読 み書き操作が、ある逐次的な順序で行われた時と常に同じになる。ただし、個々 のプロセスによる操作は、メモリに対してそのプログラムに書かれた順序で行 われる。
インターリーブは、許されるが、インターリーブのされ方は、全てのプロセス から見て同じでなければならない。
例:厳密一貫性がないが、順序一貫性がある(横方向が時間軸、右に向って増加)
P1: W(x)1 P2: R(x)0 R(x)1例:厳密一貫性も、順序一貫性もある。
P1: W(x)1 P2: R(x)1 R(x)1
P1() { x=1 ; print(y,z); } P2() { y=1 ; print(x,z); } P3() { z=1 ; print(x,y); }
正しい実行系列の例(a),(b),(c),(d)(縦方向が、時間軸で、下に向って増加)。 正しい系列は、全部で90個ある。
Prints: は、画面に時系列で現れた表示、 Signature: は、プロセス P1, P2, P3 の出力をその順で繋げたもの。
(a) x=1 ; print(y,z); y=1 ; print(x,z); z=1 ; print(x,y); Prints: 001011 Signature: 001011 (b) x=1 ; y=1 ; print(x,z); print(y,z); z=1 ; print(x,y); Prints: 101011 Signature: 101011 (c) y=1 ; z=1 ; print(x,y); print(x,z); x=1 ; print(y,z); Prints: 010111 Signature: 110101 (d) y=1 ; x=1 ; z=1 ; print(x,z); print(y,z); print(x,y); Prints: 111111 Signature: 110101考えられる Signature は、26==64 個あるが、全部は許されてい ない。
P1: W(x)1 P2: R(x)0 R(x)1プロセスの履歴
H1 = W(x)1 H2 = R(x)0 R(x)1履歴から、2つの制約を満たすような、文字列 S を合成する。
制約1:プログラム順序が保たれる。
Hi = ... A .... B .... なら S = ..... A ..... B ....
制約2:メモリの整合性(memory coherence)が保たれる。 ある位置 x に対する読み取りは、常に最近の書込みの値を返す。
これらの制約を満たす S は、今の例では1つだけ。
S = R(x)0 W(x)1 R(x)1いくつかある正しい S のうち、1つを満たせば 順序一貫性を満たしている。
読み取りを速くすると、書込みが遅くなる。
順序一貫性を弱めたもの。
メーリング・リストで、元のメールと、それを引用したメールで、引用した方 が先に届いて目にすることがある。これは、因果一貫性が満たされていない。 こういう状況を無くしたい。
潜在的な因果関係がある: プロセス P1 が x に書く。 プロセス P2 が x を読んで y に書く。
並行性がある: 因果関係がないもの。
因果一貫性があるメモリ(data store):
潜在的に因果関係のある書込みは、全プロセスに同じ順序で見えなければならない。 並行性がある書込みは、異なる順序で見えてもよい。
因果一貫性は満たすが、順序一貫性(厳密一貫性も)を満たさない例
P1: W(x)1 W(x)3 P2: R(x)1 W(x)2 P3: R(x)1 R(x)3 R(x)2 P4: R(x)1 R(x)2 R(x)3P2 が、x を Read して Write している。 P1 の W(x)3 と P2の W(x)2 は、並行なので、見え方が違ってもよい。
因果一貫性を満たさない例。
P1: W(x)1 P2: R(x)1 W(x)2 P3: R(x)2 R(x)1 P4: R(x)1 R(x)2P2 が、x を Read して Write している。
因果一貫性を満す。
P1: W(x)1 P2: W(x)2 P3: R(x)2 R(x)1 P4: R(x)1 R(x)2P1 の W と P2 の W は、並行なので、見え方が違ってもよい。
命令と命令の依存関係を追跡しなければならない。
FIFO一貫性を満たす(因果一貫性を満たさない)例。
P1: W(x)1 P2: R(x)1 W(x)2 P3: R(x)2 R(x)1 P4: R(x)1 R(x)2
FIFO一貫性では、2つのプロセスが止まってしまうことがあり得る例。
int a=0; int b=0; P1() { a = 1 ; if( b == 0 ) kill( P2 ); } P2() { b = 1 ; if( a == 0 ) kill( P1 ); }
弱一貫性の特性
2. は、パイプラインのフラッシュの意味。
3. があるので、同期をとってから普通の変数にアクセスすれば最新の状態に なっていることが言える。
弱一貫性を満たす
P1: W(x)1 W(x)2 S P2: R(x)1 R(x)2 S P3: R(x)2 R(x)1 SSは、同期変数のアクセス。
弱一貫性を満たさない
P1: W(x)1 W(x)2 S P2: S R(x)1
プロセスが Acquire した時、メモリは、必要ならそれらの共有変数の全コピー をリモートのコピーと一致させる。
リリース一貫性を満たす
P1: Acq(L) W(x)1 W(x)2 Rel(L) P2: Acq(L) R(x) 2 Rel(L) P3: R(x)1
分散システムでの実装は、2つの方法
T1: R(x)1 pthread_create(T2) T2開始: R(x)1pthread_create() 後に書き込んだものは、新しいスレッドが開始前でも読めな くてもよい。
T1: R(x)1 pthread_create(T2) W(x)2 T2開始: R(x)1
T1: R(x)1 unlock() T2: lock() R(x)1最初のスレッドが unlock 後にメモリが書かれた時、 別のスレッドが lock 後に読めなくても良い。
T1: unlock() W(x)1 T2: lock() R(x)0
T1: R(x)1 exit() T2: join() R(x)1終了後に書かれたものでも、join した時に見えなくてもよい。
T1: R(x)1 exit() T2: join() R(x)1 T3: W(x)2
T1: R(x)1 broadcast() T2: wait()から復帰 R(x)1起した後の書き込みは、見えなくてもよい。
T1: R(x)1 broadcast() W(x)2 T2: wait()から復帰 R(x)1
スレッドA スレッドB pthread_mutex_lock(&mutex1); pthread_mutex_lock(&mutex1); varabileA = 1; varabileB = 2; pthread_mutex_unlock(&mutex1); localA = varabileA; localB = varabileB; pthread_mutex_unlock(&mutex1);スレッドBは、スレッドAと同じ値を見る。 A=1, B=2。
スレッドA スレッドB pthread_mutex_lock(&mutex1); pthread_mutex_lock(&mutex1); varabileA = 1; pthread_mutex_unlock(&mutex1); varabileB = 2; localA = varabileA; localB = varabileB; pthread_mutex_unlock(&mutex1);スレッドBは、スレッドAと同じ値を見ないことがある。 スレッドBでは、A=1だが、Bは2ではないかもしれない。
スレッドA スレッドB int sleeping=1; while(sleeping) continue; sleeping=0;スレッドBは、いつまでたってもループしているかもしれない。 コンパイラが無限ループのコードを出すことがある。
スレッドA スレッドB volatile int sleeping=1; while(sleeping) continue; sleeping=0;コンパイラが無限ループのコードを出さない。 毎回、メモリから読む。 しかし、同期がないので、危ない。
A=1; B=2;メモリには、A, B の順に届くとは限らない。
図? プロセスのアドレス空間(単一スレッド)
機械語を書き換えながら実行するプログラムは、最近は行儀が悪いとされてい る。キャッシュの関係で特別な操作をしないと動かない。
malloc()
で割り当てたヒープ上の変数は、
このセグメントに置かれる。
(
自動変数(auto)
は、次のスタック・セグメントに置かれる。
)
データセグメントは, 次の3つにわかれている。
malloc()
で確保する変数が置かれるところ
static int x=100 ;
と書くと x
はデータセグメントに割りつけられ,
実行形式ファイルに100という整数のビットパタンが含まれる。
BSSとは初期値を指定しない変数が置かれる場所である。 C言語で
static int x ;
と書くと y
はBSSに割りつけられる。実行形式のファイルに
は、BSSの領域はない。これは実行時にカーネルが領域を割り当て、内容
を0に初期化する。
ヒープとは実行時に大きさが決まる変数を置くための領域である。 C言語で
char *p ;
int size ;
...
size = 100;
p = malloc( size );
とすると100バイトの領域がヒープ上に確保される。
ヒープ領域の大きさは、brk()
システム・コールや
sbrk()
システム・コールで変えることができる。これらの
システム・コールは、malloc()
ライブラリ関数から呼び出さ
れる。
C言語で
main()
{
auto int z;
}
とすると、 4バイトの領域がスタックセグメントに割りつけられる。
(auto
というキーワードは、普通省略される。スタックセグメ
ントは、普通、0xffffff (32ビットのアドレス空間の場合)からからアドレス
が小さくなるほうに向かって伸びていく。この部分は、関数呼び出しが続くと
伸びていき、割り当てられたメモリよりも多くなると、カーネルが自動的に拡
張する。
main()
関数が3つの引数で呼び出される
ようになっている。
main( int argc, char *argv[], *envp[] ) { }ここで、
argc
が、引数の数(argv
の数) ,
argv
が、引数のベクタの先頭番地、
envp
が環境変数のベクタの先頭番地である。この引数と環境変数は、スタックセグ
メントのスタックの底、
図?
では上(アドレスが大きいところ)にある。
1: /* 2: vaddr-print.c -- 変数の番地をしらべるプログラム 3: ~yas/syspro/proc/vaddr-print.c 4: Created on: 1997/05/19 22:58:49 5: */ 6: #include <stdlib.h> 7: #include <stdio.h> 8: 9: #if defined(__APPLE__) 10: #include <mach-o/getsect.h> 11: #else 12: extern int etext, edata, end ; 13: #define get_end() (&end) 14: #define get_etext() (&etext) 15: #define get_edata() (&edata) 16: #endif 17: 18: void recursive( int n ); 19: 20: int x1=1 ; 21: int x2 ; 22: 23: 24: main( int argc, char *argv[], char *envp[] ) 25: { 26: auto int x3 ; 27: auto char *x4p ; 28: 29: printf("&main == %016p (text)\n",&main ); 30: printf("&etext == %016p (text)\n",get_etext() ); 31: printf("&edata == %016p (data)\n",get_edata() ); 32: printf("&end == %016p (data)\n",get_end() ); 33: 34: printf("&argv[0] == %016p (stack)\n",&argv[0] ); 35: printf(" argv[0] == %016p (stack)\n", argv[0] ); 36: printf("&envp[0] == %016p (stack)\n",&envp[0] ); 37: printf(" envp[0] == %016p (stack)\n", envp[0] ); 38: 39: printf("&x1 == %016p (data)\n",&x1 ); 40: printf("&x2 == %016p (bss)\n",&x2 ); 41: printf("&x3 == %016p (stack)\n",&x3 ); 42: printf("&x4p == %016p (stack)\n",&x4p ); 43: x4p = malloc( 10 ); 44: printf("x4p == %016p (heap)\n",x4p ); 45: x4p = malloc( 10 ); 46: printf("x4p == %016p (heap)\n",x4p ); 47: recursive( 3 ); 48: } 49: 50: void recursive( int n ) 51: { 52: int x5 ; 53: printf("&x5 == %016p (stack,%d)\n",&x5,n ); 54: if( n<=0 ) 55: return; 56: recursive( n-1 ); 57: }実行例。
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-15/ex/vaddr-print.c
% cc vaddr-print.c -o vaddr-print
% ./vaddr-print
&main == 0x0000000000275c (text)
&etext == 0x00000000002a94 (text)
&edata == 0x00000000003018 (data)
&end == 0x00000000006000 (data)
&argv[0] == 0x000000bffff67c (stack)
argv[0] == 0x000000bffff724 (stack)
&envp[0] == 0x000000bffff684 (stack)
envp[0] == 0x000000bffff732 (stack)
&x1 == 0x00000000003014 (data)
&x2 == 0x000000000030d4 (bss)
&x3 == 0x000000bffff598 (stack)
&x4p == 0x000000bffff59c (stack)
x4p == 0x00000000500130 (heap)
x4p == 0x00000000500140 (heap)
&x5 == 0x000000bffff538 (stack,3)
&x5 == 0x000000bffff4d8 (stack,2)
&x5 == 0x000000bffff478 (stack,1)
&x5 == 0x000000bffff418 (stack,0)
% size vaddr-print
__TEXT __DATA __OBJC others dec hex
8192 4096 0 12288 24576 6000
% otool -L vaddr-print
vaddr-print:
/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 88.1.12)
% uname -mrsv
Darwin 8.11.0 Darwin Kernel Version 8.11.0: Wed Oct 10 18:26:00 PDT 2007; root:xnu-792.24.17~1/RELEASE_PPC Power Macintosh
%
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-15/ex/vaddr-print.c
% cc vaddr-print.c -o vaddr-print
% ./vaddr-print
&main == 0x000000004004d8 (text)
&etext == 0x00000000400746 (text)
&edata == 0x00000000600bb0 (data)
&end == 0x00000000600bc0 (data)
&argv[0] == 0x007fff320f5d08 (stack)
argv[0] == 0x007fff320f7998 (stack)
&envp[0] == 0x007fff320f5d18 (stack)
envp[0] == 0x007fff320f79a6 (stack)
&x1 == 0x00000000600bac (data)
&x2 == 0x00000000600bbc (bss)
&x3 == 0x007fff320f5c1c (stack)
&x4p == 0x007fff320f5c10 (stack)
x4p == 0x00000017c2b010 (heap)
x4p == 0x00000017c2b030 (heap)
&x5 == 0x007fff320f5bdc (stack,3)
&x5 == 0x007fff320f5bac (stack,2)
&x5 == 0x007fff320f5b7c (stack,1)
&x5 == 0x007fff320f5b4c (stack,0)
% size vaddr-print
text data bss dec hex filename
1955 504 16 2475 9ab vaddr-print
% ldd vaddr-print
libc.so.6 => /lib64/libc.so.6 (0x000000367e800000)
/lib64/ld-linux-x86-64.so.2 (0x000000367e400000)
%
int x; f() { int y ; static int z ; }
種類 | スコープ | 寿命 |
---|---|---|
extern 外部変数 | 全プログラム | プログラムの実行開始から終了まで |
auto 普通の局所変数 | 関数内 | その関数の実行中とそこから別の関数を呼んでいる間 |
staticな局所変数 | 関数内 | プログラムの実行開始から終了まで |
static変数(関数の外に定義) | 同一ファイル内 | プログラムの実行開始から終了まで |
(C言語にはない) | (いろいろ) | プログラムの終了後も残る(永続的) |
auto変数のスコープは、関数内。
auto変数より広い範囲で使えるスレッドごとのデータが必要になる。
tsd[thread_id][key];
pthread_key_create()
pthread_setspecific()
pthread_getspecific()
1: 2: /* 3: * tsd-counter.c 4: * Created on: 2001/01/08 08:51:25 5: */ 6: 7: #include <stdio.h> /* stderr */ 8: #include <stdlib.h> /* malloc() */ 9: #include <string.h> /* memset() */ 10: #include <pthread.h> 11: 12: struct tsd_counter 13: { 14: int tc_value ; 15: }; 16: 17: static pthread_key_t tsd_counter_tsdkey ; 18: 19: void 20: tsd_counter_module_init() 21: { 22: pthread_key_create( &tsd_counter_tsdkey,free ); 23: } 24: 25: static struct tsd_counter * 26: tsd_counter_alloc() 27: { 28: struct tsd_counter *tc ; 29: 30: tc = malloc( sizeof(struct tsd_counter) ); 31: if( tc == 0 ) 32: { 33: fprintf(stderr,"no memory for struct tsd_counter\n"); 34: exit( -1 ); 35: } 36: memset( tc, 0, sizeof(struct tsd_counter) ); 37: if( pthread_setspecific( tsd_counter_tsdkey, tc ) != 0 ) 38: { 39: fprintf(stderr, "pthread_setspecific().\n"); 40: exit( -1 ); 41: } 42: return( tc ); 43: } 44: 45: static struct tsd_counter * 46: tsd_counter_gettsd() 47: { 48: struct tsd_counter *tc ; 49: tc = pthread_getspecific( tsd_counter_tsdkey ); 50: if( tc == 0 ) 51: { 52: tc = tsd_counter_alloc(); 53: } 54: return( tc ); 55: } 56: 57: void tsd_counter_reset( int val ) 58: { 59: struct tsd_counter *tc ; 60: tc = tsd_counter_gettsd(); 61: tc->tc_value = val ; 62: } 63: 64: void tsd_counter_up() 65: { 66: struct tsd_counter *tc ; 67: tc = tsd_counter_gettsd(); 68: tc->tc_value ++ ; 69: } 70: 71: int tsd_counter_getvalue() 72: { 73: struct tsd_counter *tc ; 74: tc = tsd_counter_gettsd(); 75: return( tc->tc_value ); 76: }TSD 利用のパタン
pthread_getspecific()
の呼出しを節約するため。
pthread_key_create()
で初
期化する。確実に一度だけ初期化するために、main() から初期化の関数を呼び
出すか、pthread_once()
を使う。
pthread_getspecific()
でポインタを得る。
malloc()
して、初期化して、
pthread_setspecific()
で登録する。
pthread_key_delete()
は、普通、使われない。ダイナミック・リンク
のモジュールを unload する時に必要になる(かもしれない)。
1: 2: /* 3: * tsd-counter-main.c by Y.Shinjo 4: * Created on: 2001/01/08 08:51:25 5: */ 6: 7: #include <stdio.h> /* printf() */ 8: #include <pthread.h> 9: 10: void thread1( int x ); 11: void thread2( int x ); 12: 13: extern void tsd_counter_module_init(); 14: extern void tsd_counter_reset( int val ); 15: extern void tsd_counter_up(); 16: extern int tsd_counter_getvalue(); 17: 18: main() 19: { 20: pthread_t t1 ; 21: pthread_t t2 ; 22: tsd_counter_module_init(); 23: pthread_create( &t1, NULL, (void *)thread1, (void *)10 ); 24: pthread_create( &t2, NULL, (void *)thread2, (void *)20 ); 25: printf("main()\n"); 26: pthread_join( t1, NULL ); 27: pthread_join( t2, NULL ); 28: } 29: 30: void thread1( int x ) 31: { 32: int i ; 33: tsd_counter_reset( x ); 34: printf("thread1(): value=%d \n", tsd_counter_getvalue() ); 35: for( i = 0 ; i<3 ; i++ ) 36: { 37: tsd_counter_up(); 38: printf("thread1(): value=%d \n", tsd_counter_getvalue() ); 39: } 40: } 41: 42: void thread2( int x ) 43: { 44: int i ; 45: tsd_counter_reset( x ); 46: printf("thread2(): value=%d \n", tsd_counter_getvalue() ); 47: for( i = 0 ; i<3 ; i++ ) 48: { 49: tsd_counter_up(); 50: printf("thread2(): value=%d \n", tsd_counter_getvalue() ); 51: } 52: }実行例。
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-15/ex/tsd-counter.c
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-15/ex/tsd-counter-main.c
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2011-12-15/ex/Makefile
% emacs Makefile
% make
gcc -c -o tsd-counter-main.o tsd-counter-main.c
gcc -c -o tsd-counter.o tsd-counter.c
gcc -o tsd-counter-main tsd-counter-main.o tsd-counter.o -lpthread
% ./tsd-counter-main
thread1(): value=10
main()
thread2(): value=20
thread1(): value=11
thread2(): value=21
thread1(): value=12
thread2(): value=22
thread1(): value=13
thread2(): value=23
%
スレッド固有データの特徴
ただし意味が違うので、mutex と相互に書き換えできないことがある。 プロセス全体のデータを扱うものは、mutex で書くしかない。 Time Zoneなど。
スレッドごとに乱数生成器を持ってもいいのか。 再現性が必要か。mutex では、再現性はない。
実行時特化(部分評価)の技術を使うと、pthread_getspecific() の関数呼出 しが消えて、スレッド固有データが普通の extern や static 変数と同じにな る。
Yasushi Shinjo, Calton Pu. "Achieving Efficiency and Portability in Systems Software: A Case Study on POSIX-Compliant Multithreaded Programs," IEEE Transactions on Software Engineering, vol. 31, no. 9, pp. 785-800, September, 2005. http://doi.ieeecomputersociety.org/10.1109/TSE.2005.98
Figure 6: Runtime specialization in Tempo.
pthread_key_t tsdkey1 ; iret_tsd() { int *p ; p = pthread_getspecific( tsdkey1 ); return( *p ); } Figure 4: A function returning a value of a TSD variable. int var1 ; iret_extern() { return( var1 ); } Figure 5: A function returning a value of an external variable entry_point := "iret_tsd()"; static_locations := ["tsdkey1"]; external_functions := EVALUATE["pthread_getspecific"]; lift_all := true ; Figure 10: Hints in ML for specializing iret_tsd() . void set_analysis_context(){ } int var1 ; void *pthread_getspecific(unsigned key) { return( &var1 ); } Figure 11: Hints in C for specializing iret_tsd() . int H0; int tmp_iret_tsd_1(){ return *((int *)(&H0)); } Figure 12: The specialized code of iret_tsd() .
ライブラリを実現する場合、自分自身では Runnable を定義できないことがあ る。その時には、ThreadLocal クラスを使って、Pthread と似たようなことをする。
Java | Pthread |
final | pthread_once() |
java.lang.ThreadLocal() | pthread_key_create() |
get() | pthread_getspecific() |
set() | pthread_setspecific() |
initialValue() | - |
(GC) | pthread_key_delete() |
int x=0; int y=0; int a=0; int b=0; threadA() { a = 1; x = b; printf("threadA: %d,%d\n",a,x); } threadB() { b = 1; y = a; printf("threadB: %d,%d\n",b,y); }このプログラムを実行した時に、どのような結果が画面に表示されるか。表示 される可能性のある例を、2つ以上示しなさい。