並行システム
システム情報系情報工学域,
システム情報工学研究科コンピュータサイエンス専攻
新城 靖
<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)（縦方向が、時間軸で、下に向って増加）。 正しい系列は、全部で９０個ある。
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履歴から、２つの制約を満たすような、文字列 S を合成する。
制約１：プログラム順序が保たれる。
Hi = ... A .... B .... なら S = ..... A ..... B ....
制約２：メモリの整合性(memory coherence)が保たれる。 ある位置 x に対する読み取りは、常に最近の書込みの値を返す。
これらの制約を満たす S は、今の例では１つだけ。
S = R(x)0 W(x)1 R(x)1いくつかある正しい S のうち、１つを満たせば 順序一貫性を満たしている。
読み取りを速くすると、書込みが遅くなる。
順序一貫性を弱めたもの。
メーリング・リストで、元のメールと、それを引用したメールで、引用した方 が先に届いて目にすることがある。これは、因果一貫性が満たされていない。 こういう状況を無くしたい。
潜在的な因果関係がある: プロセス 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一貫性では、２つのプロセスが止まってしまうことがあり得る例。
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
分散システムでの実装は、２つの方法
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 ![[←]](../icons/screen-return.gif)
% 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
% ![[]](../icons/screen-cursor.gif)
% 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);
}
このプログラムを実行した時に、どのような結果が画面に表示されるか。表示
される可能性のある例を、２つ以上示しなさい。