並行システム
システム情報工学研究科コンピュータサイエンス専攻、電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-01-11
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/
図? プロセスのアドレス空間(単一スレッド)
機械語命令を置くためのセグメンを テキスト・セグメント ( text segment, ) という。このセグメントは、普通、読み出し専用になっていて, 同じロードモ ジュールのプロセスの間で共有される。例えばシェルは複数のユーザが同時に 使うことが多いが、この場合、テキストセグメントのためのメモリは1セット だけでよい。機械語を書き換えながら実行するプログラムは、最近は行儀が悪いとされてい る。キャッシュの関係で特別な操作をしないと動かない。
データ・セグメント ( data segment, ) は、データを置く領域である. C言語の 静的変数(static)、 大域変数(extern)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ビットのアドレス空間の場合)からからアドレス
が小さくなるほうに向かって伸びていく。この部分は、関数呼び出しが続くと
伸びていき、割り当てられたメモリよりも多くなると、カーネルが自動的に拡
張する。
Unixではプログラムを実行するときに,
引数(argument)
と
環境変数(environment variable)
が渡される。
C言語では、次のようにmain()関数が3つの引数で呼び出される
ようになっている。
main( int argc, char *argv[], *envp[] )
{
}
ここで、
argc
が、引数の数(argvの数) ,
argv
が、引数のベクタの先頭番地、
envp
が環境変数のベクタの先頭番地である。この引数と環境変数は、スタックセグ
メントのスタックの底、
図?
では上(アドレスが大きいところ)にある。
共有ライブラリは、ヒープとスタック・セグメントの間にある。 どの番地に割り当てられるかは、システムに依存する。 （図には書かれていない。）
1: /*
2: vaddr-print.c -- 変数の番地をしらべるプログラム
3: ~yas/syspro/cc/vaddr-print.c
4: Start: 1997/05/19 22:58:49
5: */
6: #include <stdlib.h>
7: #include <stdio.h>
8:
9: void recursive( int n );
10:
11: int x1=1 ;
12: int x2 ;
13:
14: #if defined(__APPLE__)
15: #include <mach-o/getsect.h>
16: #else
17: extern int etext, edata, end ;
18: #define get_etext() (&etext)
19: #define get_edata() (&edata)
20: #define get_end() (&end)
21: #endif
22:
23: main( int argc, char *argv[], char *envp[] )
24: {
25: auto int x3 ;
26: auto char *x4p ;
27:
28: printf("&main == 0x%08x (text)\n",&main );
29: printf("&etext == 0x%08x (text)\n",get_etext() );
30: printf("&edata == 0x%08x (data)\n",get_edata() );
31: printf("&end == 0x%08x (data)\n",get_end() );
32:
33: printf("&argv[0] == 0x%08x (stack)\n",&argv[0] );
34: printf(" argv[0] == 0x%08x (stack)\n", argv[0] );
35: printf("&envp[0] == 0x%08x (stack)\n",&envp[0] );
36: printf(" envp[0] == 0x%08x (stack)\n", envp[0] );
37:
38: printf("&x1 == 0x%08x (data)\n",&x1 );
39: printf("&x2 == 0x%08x (bss)\n",&x2 );
40: printf("&x3 == 0x%08x (stack)\n",&x3 );
41: printf("&x4p == 0x%08x (stack)\n",&x4p );
42: x4p = malloc( 10 );
43: printf("x4p == 0x%08x (heap)\n",x4p );
44: x4p = malloc( 10 );
45: printf("x4p == 0x%08x (heap)\n",x4p );
46: recursive( 3 );
47: }
48:
49: void recursive( int n )
50: {
51: int x5 ;
52: printf("&x5 == 0x%08x (stack,%d)\n",&x5,n );
53: if( n<=0 )
54: return;
55: recursive( n-1 );
56: }
実行例。
% cp ~yas/syspro/cc/vaddr-print.c .% make vaddr-print
![[]](../icons/screen-cursor.gif)
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()を使
う。(2008/01/11 pthread_once() が MacOSX 10.4 でうまく動かない。)
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("thread1(): 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/sie/csys-2007/2008-01-11/ex/tsd-counter.c
スレッド固有データの特徴
ただし意味が違うので、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 flock( fd, operation);
int fd, operation;
operation の種類
LOCK_SH shared lock (読み)
LOCK_EX exclusive lock (書き)
LOCK_UN unlock
LOCK_NB ロックと一緒に使って non-blocking
#include <unistd.h>
int lockf(int fildes, int function, off_t size);
function の種類
#define F_ULOCK 0 /* unlock previously locked section */
#define F_LOCK 1 /* lock section for exclusive use */
#define F_TLOCK 2 /* test & lock section for exclusive use */
#define F_TEST 3 /* test section for other locks */
#include <fcntl.h>
fcntl(int fd, int cmd, int arg);
struct flock {
off_t l_start; /* starting offset */
off_t l_len; /* len = 0 means until end of file */
pid_t l_pid; /* lock owner */
short l_type; /* lock type: read/write, etc. */
short l_whence; /* type of l_start */
};
The commands available for advisory record locking are as follows:
F_GETLK Get the first lock that blocks the lock description pointed to
by the third argument, arg, taken as a pointer to a struct
flock (see above). The information retrieved overwrites the
information passed to fcntl in the flock structure. If no
lock is found that would prevent this lock from being created,
the structure is left unchanged by this function call except
for the lock type which is set to F_UNLCK.
F_SETLK Set or clear a file segment lock according to the lock
description pointed to by the third argument, arg, taken as a
pointer to a struct flock (see above). F_SETLK is used to
establish shared (or read) locks (F_RDLCK) or exclusive (or
write) locks, (F_WRLCK), as well as remove either type of lock
(F_UNLCK). If a shared or exclusive lock cannot be set, fcntl
returns immediately with EACCES.
F_SETLKW This command is the same as F_SETLK except that if a shared or
exclusive lock is blocked by other locks, the process waits
until the request can be satisfied. If a signal that is to be
caught is received while fcntl is waiting for a region, the
fcntl will be interrupted if the signal handler has not speci-
fied the SA_RESTART (see sigaction(2)).
次のような機能がある。
int pthread_rwlock_init(pthread_rwlock_t *rwlock, const pthread_rwlockattr_t *attr); int pthread_rwlock_destroy(pthread_rwlock_t *rwlock); pthread_rwlock_t rwlock=PTHREAD_RWLOCK_INITIALIZER; int pthread_rwlock_rdlock(pthread_rwlock_t *rwlock); int pthread_rwlock_tryrdlock(pthread_rwlock_t *rwlock); int pthread_rwlock_wrlock(pthread_rwlock_t *rwlock); int pthread_rwlock_trywrlock(pthread_rwlock_t *rwlock); int pthread_rwlock_unlock(pthread_rwlock_t *rwlock); int pthread_rwlockattr_init(pthread_rwlockattr_t *attr); int pthread_rwlockattr_destroy(pthread_rwlockattr_t *attr);
class X {
ReentrantReadWriteLock rwl = new ReentrantReadWriteLock();
void method_read()
{
try {
rwl.readLock().lock();
...
}
finally {
rwl.readLock().unlock();
}
}
void method_write()
{
try {
rwl.writeLock().lock();
...
}
finally {
rwl.writeLock().unlock();
}
}
}
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/ReadWriteLock.html
読み書きロックでも、読み込みだけ行うスレッドも読み込みで advisory ロッ クを行う必要がある。ロックを行わないでアクセスしてはいけない。
例：銀行口座が円とドルで２種類あった時に、合計の残高を知りたい。
Unix 系、Pthread, Java は、mandatory lock。 Windows には、advisory lock がある。
基本的には、スレッドのプログラムでUnix のシグナル(ソフトウェア割込みの 扱い)を使ってはいけない。 マルチスレッドは、ソフトウェア割込みを、より使いやすいものに置き換える ためのもの。
シグナルは、SIGKILL や SIGSTOP などプロセス全体を操作するためだ けに使うべきである。
どうしても必要な時：
pthread_sigmask()を使ってマスクする。
sigwait(), sigtimewait()を呼び出すよ
うなシグナルを待つ専用のスレッドを作る。
fork() の意味が不明
どうしても fork() する時必要がある時には、fork() の時に
必要な特殊な処理を行なう手続きを書き、pthread_atfork()
で登録する。
execve() には問題がない。 ただし、プロセス間共有メモリを使っている時には、共有メモリ上の mutex をアンロックする。
例：２つの mutex を２つのスレッドが次のようなタイミングでロックしよう とすると、デッドロックになる。
pthread_mutex_t mutex1;
pthread_mutex_t mutex2;
f()
{
pthread_mutex_lock( &mutex1 );
pthread_mutex_lock( &mutex2 );
pthread_mutex_unlock( &mutex2 );
pthread_mutex_unlock( &mutex1 );
}
g()
{
pthread_mutex_lock( &mutex2 );
pthread_mutex_lock( &mutex1 );
pthread_mutex_unlock( &mutex1 );
pthread_mutex_unlock( &mutex2 );
}
実行例
thread_A() thread_B() : : pthread_mutex_lock( &mutex1 ); pthread_mutex_lock( &mutex2 ); : : pthread_mutex_lock( &mutex2 ); pthread_mutex_lock( &mutex1 );
解決方法(1): 複数の mutex をロックする時に順序を決める。
上の場合、どのスレッドも mutex1, mutex2 の
順でロックを行なうと、デッドロックは起こらない。
解決方法(2): だめな時には最初からやりなおす。
pthread_mutex_trylock() を使って、失敗したら全部をアンロッ
クして最初からやり直す。
ライブロックの危険性がある。
デッドロックの危険性があるコード。
class Cell {
long value;
synchronized long getValue() { return value; }
synchronized void setValue(long v) { value = v; }
synchronized void swapValue(Cell other) {
long t = getValue();
long v = other.getValue();
setValue(v);
other.setValue(t);
}
}
thread_A() thread_B() a.swapValue(b)を実行するための aのロックを得る。 b.swapValue(a)を実行するための bのロックを取る。 other.getValue()を実行するための other.getValue()を実行するための bのロックを確保しようとして止まる。 aのロックを確保しようとして止まる。 )
class Cell {
long value;
synchronized long getValue() { return value; }
synchronized void setValue(long v) { value = v; }
void swapValue(Cell other) {
if (other == this) // alias check
return;
else if (System.identityHashCode(this) <
System.identityHashCode(other))
this.doSwapValue(other);
else
other.doSwapValue(this);
}
synchronized void doSwapValue(Cell other) {
// 元のデッドロックするものの swapValue と同じ
long t = getValue();
long v = other.getValue();
setValue(v);
other.setValue(t);
}
}
注意：swapValue() には、synchronized を付けてはならない。
若干の高速化:
synchronized void doSwapValueV(Cell other) {
synchronized(other) {
long t = value;
value = other.value;
other.value = t;
}
}
ロックよりも楽にプログラムを作りたい。
特に分散では。集中でも、フォールト・トレランスの実現では必要。
歴史：１９６０年代、テープの時代。 失敗したら、巻き戻す(rollback)。
銀行口座間の預金の移動。
注意：Javaの serializable とは意味が全く違う。
複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。
逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。
Begin_Transaction();
reserve("NRT-SFO");
reserve("SFO-JFK");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的
には、ロックは行われる（ことがある）。
途中の reserve() が失敗したら、トランザクション全体を abort() する。
シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶にログとして書き込む。
クラッシュからの回復もできる。
図? 安定記憶の実現
更新時：3 の前にクラッシュしても、常にディスク１が正しい(図?(b))。 この場合は、ディスク１からディスク１へコピーする。
チェックサムエラーが起きた場合（図?(c)）、他のディスクからコピーして回復する。
もっとも単純な方法： Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。
注意：プログラマは、ロックを意識しない。
制約が強すぎる。
読み取りロック：read lock と write lock を分ける。
ロックの粒度(granularity)が大事
実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。 第２相で、まとめて全部ロックを解放する(strict two-phase locking)。
利点
注意：２相ロックと２相コミットは別。
実現（衝突時の対応）：プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。
性質
アルゴリズム：
getlogin() readdir() strtok() asctime() ctime() gmtime() localtime()
rand() getgrgi() getgrnam() getpwuid() getpwnam()
これらのライブラリ関数を、スレッド固有データを使うように修正しなさい。 この時、引数の数と型、結果の型は、スレッド・セーフでないものと同じにな るようにしなさい。ただし、名前には、_tsd というサフィックスを付け、ス レッド・セーフではないものと区別すること。実現では、それぞれのリエント ラント版を使ってもよい。たとえば、getlogin_tsd() の実現において、 getlogin_r() を使ってよい。
実現した関数と、mutex を使う方法との性能を比較しなさい。