マルチスレッド(3)

並列分散ソフトウェア

                                       電子・情報工学系
                                       新城 靖
                                       <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/2002-01-31
あるいは、次のページから手繰っていくこともできます。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/
http://www.is.tsukuba.ac.jp/~yas/index-j.html
http://www.hlla.is.tsukuba.ac.jp/~yas/index-j.html

■今日の重要な話

■フィードバック

前回の課題[pdsoft/report-thread-2] に対するコメント。

★配列の総和

台数効果を調べること。すなわち、スレッド/CPUの数が増えた時に、実行時間 やスループットどうなるかを調べて報告しなさい。必ずしもよい結果が出る必 要はないが、今日までに出した人でよい結果を出した人はかなりいる。台数効 果が報告されていないものは、来週までに再提出すること。悪い結果が出た時 には、どこに原因があるかを考察すること。

マスタ・スレーブで プログラムを書くこと。 マスタ・スレーブでは、pthread_mutex_lock() もpthread_cond_wait() も出 てこない。バリア同期は、つかってもよいが、この課題では使う必要はない。

■スレッド固有データ

◆大域変数、静的変数

シングルスレッド・プログラムをマルチスレッド・プログラムに変更しようと した時に extern変数や static 変数をどうするか。
auto変数は、スレッドごとにコピーが作られる。 （再帰を考えると関数呼出しごとにコピーが作られる。）

◆スコープ

auto変数のスコープは、関数内。

auto変数より広い範囲で使えるスレッドごとのデータが必要になる。

◆Pthreadでのスレッド固有データの扱い

key-value モデル。 概念的にには、２次元配列。 
tsd[thread_id][key];
pthread_key_create()
スレッド固有データのためのキーを生成する。プログラムの中で、固有 データごとに一度だけ呼び出す。
pthread_setspecific()
スレッド固有データを設定する。スレッドごとに１度だけ呼び出す。
pthread_getspecific()
スレッド固有データを参照する。必要になるたびに呼び出す。

◆例：tsd_counter


----------------------------------------------------------------------
   1: 
   2: /*
   3:  * tsd-counter.c
   4:  * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/tsd-counter.c
   5:  * Start: 2001/01/08 08:51:25
   6:  */
   7: 
   8: #include <stdio.h>      /* stderr */
   9: #include <stdlib.h>     /* malloc() */
  10: #include <pthread.h>
  11: 
  12: struct tsd_counter 
  13: {
  14:         int tc_value ;
  15: };
  16: 
  17: static  pthread_once_t   tsd_counter_alloc_once = PTHREAD_ONCE_INIT ;
  18: static  pthread_key_t    tsd_counter_tsdkey ;
  19: 
  20: static void
  21: tsd_counter_tsdkey_init()
  22: {
  23:     extern void free(void *ptr);
  24:         pthread_key_create( &tsd_counter_tsdkey,free );
  25: }
  26: 
  27: static struct tsd_counter *
  28: tsd_counter_alloc()
  29: {
  30:     struct tsd_counter *tc ;
  31: 
  32:         pthread_once(&tsd_counter_alloc_once,tsd_counter_tsdkey_init);
  33:         tc = malloc( sizeof(struct tsd_counter) );
  34:         if( tc == 0 )
  35:         {
  36:             fprintf(stderr,"no memory for struct tsd_counter\n");
  37:             exit( -1 );
  38:         }
  39:         memset( tc, 0, sizeof(struct tsd_counter) );
  40:         if( pthread_setspecific( tsd_counter_tsdkey, tc ) != 0 )
  41:         {
  42:             fprintf(stderr, "pthread_setspecific().\n");
  43:             exit( -1 );
  44:         }
  45:         return( tc );
  46: }
  47: 
  48: static struct tsd_counter *
  49: tsd_counter_gettsd()
  50: {
  51:     struct tsd_counter *tc ;
  52:         tc = pthread_getspecific( tsd_counter_tsdkey );
  53:         if( tc == 0 )
  54:         {
  55:             tc = tsd_counter_alloc();
  56:         }
  57:         return( tc );
  58: }
  59: 
  60: void tsd_counter_reset( int val )
  61: {
  62:     struct tsd_counter *tc ;
  63:         tc = tsd_counter_gettsd();
  64:         tc->tc_value = val ;
  65: }
  66: 
  67: void tsd_counter_up()
  68: {
  69:     struct tsd_counter *tc ;
  70:         tc = tsd_counter_gettsd();
  71:         tc->tc_value ++ ;
  72: }
  73: 
  74: int tsd_counter_getvalue()
  75: {
  76:     struct tsd_counter *tc ;
  77:         tc = tsd_counter_gettsd();
  78:         return( tc->tc_value );
  79: }
----------------------------------------------------------------------
TSD 利用のパタン pthread_key_delete() は、普通、使われない。ダイナミック・リンク のモジュールを unload する時に必要になる（かもしれない）。 

----------------------------------------------------------------------
   1: 
   2: /*
   3:  * tsd-counter-main.c by Y.Shinjo
   4:  * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/tsd-counter-main.c
   5:  * Start: 2001/01/08 08:51:25
   6:  */
   7: 
   8: #include <pthread.h>
   9: 
  10: void thread1( int x );
  11: void thread2( int x );
  12: 
  13: extern void tsd_counter_reset( int val );
  14: extern void tsd_counter_up();
  15: extern int tsd_counter_getvalue();
  16: 
  17: main()
  18: {
  19:     pthread_t t1 ;
  20:     pthread_t t2 ;
  21:         pthread_create( &t1, NULL, (void *)thread1, (void *)10 );
  22:         pthread_create( &t2, NULL, (void *)thread2, (void *)20 );
  23:         printf("main()\n");
  24:         pthread_join( t1, NULL );
  25:         pthread_join( t2, NULL );
  26: }
  27: 
  28: void thread1( int x )
  29: {
  30:     int i ;
  31:         tsd_counter_reset( x );
  32:         printf("thread1(): value=%d \n", tsd_counter_getvalue() );
  33:         for( i = 0 ; i<3 ; i++ )
  34:         {
  35:             tsd_counter_up();
  36:             printf("thread1(): value=%d \n", tsd_counter_getvalue() );
  37:         }
  38: }
  39: 
  40: void thread2( int x )
  41: {
  42:     int i ;
  43:         tsd_counter_reset( x );
  44:         printf("thread1(): value=%d \n", tsd_counter_getvalue() );
  45:         for( i = 0 ; i<3 ; i++ )
  46:         {
  47:             tsd_counter_up();
  48:             printf("thread2(): value=%d \n", tsd_counter_getvalue() );
  49:         }
  50: }
----------------------------------------------------------------------
実行例。 

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/tsd-counter.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/tsd-counter-main.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/Makefile [←]
% make tsd-counter-main [←]
gcc -D_REENTRANT -g -mcpu=v8 -Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency   -c tsd-counter-main.c -o tsd-counter-main.o
gcc -D_REENTRANT -g -mcpu=v8 -Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency   -c tsd-counter.c -o tsd-counter.o
gcc -D_REENTRANT -g -mcpu=v8 -Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency -o tsd-counter-main tsd-counter-main.o tsd-counter.o -lpthread
% ./tsd-counter-main  [←]
main()
thread1(): value=10 
thread1(): value=11 
thread1(): value=12 
thread1(): value=13 
thread1(): value=20 
thread2(): value=21 
thread2(): value=22 
thread2(): value=23 
% []
----------------------------------------------------------------------

◆スレッド固有データ vs. mutex

スレッド固有データの特徴

ただし意味が違うので、mutex と相互に書き換えできないことがある。 プロセス全体のデータを扱うものは、mutex で書くしかない。 Time Zoneなど。

スレッドごとに乱数生成器を持ってもいいのか。 再現性が必要か。mutex では、再現性はない。

◆Java

Runnable を自分で定義する場合、それか持っている変数はスレッド固有デー タである。

ライブラリを実現する場合、自分自身では Runnable を定義できないことがあ る。その時には、Pthread と同じようなことをする。 

----------------------------------------------------------------------
Java				Pthread
----------------------------------------------------------------------
final				pthread_once()
java.lang.ThreadLocal()		pthread_key_create()
get()				pthread_getspecific()
set()				pthread_setspecific()
initialValue()			-
(GC)				pthread_key_delete()
----------------------------------------------------------------------

■再帰的 mutex

１つのスレッドで１つの mutex を複数回ロックしたい。

◆標準mutexでのデットロック

export している関数の入口で lock, 出口 unlockを入れて、 スレッド・セーフなモジュールを作りたい。 export している関数が、他の export している関数を呼び出すと、デットロッ クになる。 

----------------------------------------------------------------------
   1: /*
   2:  * mutex-reclock-normal.c
   3:  * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/mutex-reclock-normal.c
   4:  * Start: 2001/01/08 09:41:11
   5:  */
   6: 
   7: #include <pthread.h>
   8: 
   9: void thread_A(), thread_B();
  10: int     shared_resource ;
  11: pthread_mutex_t mutex1 ;
  12: 
  13: deposit( int n )
  14: {
  15:         pthread_mutex_lock( &mutex1 );
  16:         shared_resource += n ;
  17:         pthread_mutex_unlock( &mutex1 );
  18: }
  19: 
  20: add_interest()
  21: {
  22:     int i ;
  23:         pthread_mutex_lock( &mutex1 );
  24:         i = shared_resource * 0.05 ;
  25:         deposit( i );
  26:         pthread_mutex_unlock( &mutex1 );
  27: }
  28: 
  29: main() {
  30:     pthread_t t1 ;
  31:     pthread_t t2 ;
  32:         shared_resource = 0 ;
  33:         shared_resource = 1000000 ;
  34:         pthread_mutex_init( &mutex1, NULL );
  35: 
  36:         pthread_create( &t1, NULL, (void *)thread_A, 0 );
  37:         pthread_create( &t2, NULL, (void *)thread_B, 0 );
  38:         pthread_join( t1, NULL );
  39:         pthread_join( t2, NULL );
  40:         printf("main(): shared_resource == %d\n", shared_resource );
  41: }
  42: 
  43: void thread_A()
  44: {
  45:         printf("thread_A(): deposit( 10000 ) ... \n");
  46:         deposit( 10000 );       
  47:         printf("thread_A(): deposit( 10000 ) done. \n");
  48: }
  49: 
  50: void thread_B()
  51: {
  52:         printf("thread_B(): add_interest() ... \n");
  53:         add_interest();
  54:         printf("thread_B(): add_interest() done. \n");
  55: }
----------------------------------------------------------------------
実行例。 

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/mutex-reclock-normal.c [←]
% wget wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/Makefile [←]
% make mutex-reclock-normal [←]
gcc -D_REENTRANT -g -mcpu=v8 -Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency   -c mutex-reclock-normal.c -o mutex-reclock-normal.o
gcc -D_REENTRANT mutex-reclock-normal.o -lpthread -lposix4 -o mutex-reclock-normal
% ./mutex-reclock-normal  [←]
thread_A(): deposit( 10000 ) ... 
thread_A(): deposit( 10000 ) done. 
thread_B(): add_interest() ... 
^C
% []
----------------------------------------------------------------------

◆再帰的mutex


----------------------------------------------------------------------
   1: /*
   2:  * mutex-reclock-recursive.c
   3:  * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/mutex-reclock-recursive.c
   4:  * Start: 2001/01/08 09:41:11
   5:  */
...

  29: static int
  30: my_pthread_mutex_init_recursive( pthread_mutex_t *mutex )
  31: {
  32:     pthread_mutexattr_t attr ;
  33:     int err ;
  34:         if( (err=pthread_mutexattr_init( &attr )) < 0 )
  35:             return( 0 );
  36:         if( (err=pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_RECURSIVE)) <0 )
  37:             return( 0 );
  38:         err = pthread_mutex_init( mutex,&attr );
  39:         return( err );
  40: }
  41: 
  42: main()
  43: {
  44:     pthread_t t1 ;
  45:     pthread_t t2 ;
  46:         shared_resource = 0 ;
  47:         shared_resource = 1000000 ;
  48:         my_pthread_mutex_init_recursive( &mutex1 );
  49: 
  50:         pthread_create( &t1, NULL, (void *)thread_A, 0 );
  51:         pthread_create( &t2, NULL, (void *)thread_B, 0 );
  52:         pthread_join( t1, NULL );
  53:         pthread_join( t2, NULL );
  54:         printf("main(): shared_resource == %d\n", shared_resource );
  55: }
...
----------------------------------------------------------------------
実行例。sakura では動かない。 

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/mutex-reclock-recursive.c [←]
% wget wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2001/examples/Makefile [←]
% make mutex-reclock-recursive [←]
gcc -D_REENTRANT -g -mcpu=v8   -c mutex-reclock-recursive.c -o mutex-reclock-recursive.o
gcc -D_REENTRANT mutex-reclock-recursive.o -lpthread -lrt -o mutex-reclock-recursive
% ./mutex-reclock-recursive [←]
thread_A(): deposit( 10000 ) ... 
thread_A(): deposit( 10000 ) done. 
thread_B(): add_interest() ... 
thread_B(): add_interest() done. 
main(): shared_resource == 1060500
% []
----------------------------------------------------------------------

◆stdio専用再帰的lock

printf(), fputs() などの標準入出力(stdio)ライブラリ自体は、スレッド・ セーフ。一連の入出力をまとめるために、ロックする必要がでてくる。 

----------------------------------------------------------------------
	printf("hello,world\n");
----------------------------------------------------------------------
上と下は、結果が違う。 

----------------------------------------------------------------------
	printf("hello,");
	/* ここに他のスレッドの出力が混じることがある */
	printf("world\n");
----------------------------------------------------------------------
これを避けるには、 flockfile(),funlockfile(),ftrylockfile()を使う。 

----------------------------------------------------------------------
	flockfile(stdout);
	printf("hello,");
	/* ここに他のスレッドの出力が混じることはない */
	printf("world\n");
	funlockfile(stdout);
----------------------------------------------------------------------
putchar()や getchar()は、遅すぎる。 flockfile()/funlockfile()の中で使うための putchar_unlocked(),getchar_unlocked(),putc_unlocked(),getc__unlocked() が用意されている。printf_unsafe() はない。

■読み書きロック

並列性を高めるためには、複数の読み手を同時に実行する方法がある。 読み込みだけなら、並列に実行したい。

これを実現するものが、「複数読み手単一書き手ロック」、あるいは、 「読み書きロック」。

初期の Pthread には、この機能はなかった。新しい標準で採り入れられた。

次のような機能がある。 

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);
sakura (SunOS 5.6) には、pthread_rwlock_rdlock() はない。その代りに rw_rdlock() を使う。pthread_rwlock_rdlock() は、SunOS の rw_rdlock() がPthread 標準に取り込まれたものと思われる。

■モニタ

プログラミング言語レベルでの支援。

Dijkstra, Brinch Hansen にり提唱。Hoare によって発展。

Binch Hansen の Concurrent Pascal、N.Wirth の Modula, R.C.Holt の CSP/k、Xerox社の Mesa、Hoare Simula 。

モニタ内部の関数が呼び出されると、自動的にロックされる。 リターンすると解除される。 

モニタ名: monitor
begin

局所変数

procedure モニタ名(引数の並び);
begin
本体
end

局所手続き
初期化のコード

end

利点

Java のメソッド単位の synchronized は、モニタを実現したものである。 synchronized ブロックは、モニタではない。

■Javaのスレッド

■マルチスレッド・プログラミングのその他の注意点

◆シグナル(ソフトウェア割込みの扱い)

基本的には、スレッドのプログラムでUnix のシグナル(ソフトウェア割込みの 扱い)を使ってはいけない。 マルチスレッドは、ソフトウェア割込みを、より使いやすいものに置き換える ためのもの。

シグナルは、SIGKILL や SIGSTOP などプロセス全体を操作するためだ けに使うべきである。

どうしても必要な時：

◆forkとexecの扱い

マルチスレッドでは fork() の意味が不明 fork() は、直後に exec をする時だけに使うようにする。

どうしても fork() する時必要がある時には、fork() の時に 必要な特殊な処理を行なう手続きを書き、pthread_atfork() で登録する。

execve() には問題がない。 ただし、プロセス間共有メモリを使っている時には、共有メモリ上の mutex をアンロックする。

■デッドロック対策

複数のmutexのロックを取る必要がある時には、デッドロックに気を付ける。

例：２つの mutex を２つのスレッドが次のようなタイミングでロックしよう とすると、デッドロックになる。 


----------------------------------------------------------------------
thread_A()				thread_B()

	:					:
pthread_mutex_lock( &mutex1 );		pthread_mutex_lock( &mutex2 );
	:					:
pthread_mutex_lock( &mutex2 );		pthread_mutex_lock( &mutex1 );
----------------------------------------------------------------------

◆４条件

  1. 相互排除
  2. 待機
  3. 横取り不能
  4. 循環待機

◆対策

◆防止策

防止するには、４条件のどれか１つ（最初以外）を成り立たなくする。
  1. （なし）
  2. プロセスが必要な資源を一度に要求する。全てが許可されるまで進まない。
  3. 資源の要求が受け付けられなかった時には、持っている資源を一度解放して、 最初から取り直す。
  4. 資源の種類によって線形に順序を付け、その順序に従って しか資源を要求できない。

◆Pthreadでの対応策：防止

解決方法(1): 複数の mutex をロックする時に順序を決める。

上の場合、どのスレッドも mutex1, mutex2 の 順でロックを行なうと、デッドロックは起こらない。

解決方法(2): だめな時には最初からやりなおす。

pthread_mutex_trylock() を使って、失敗したら全部をアンロッ クして最初からやり直す。

ライブロックの危険性がある。

◆その他のPthreadの機能

■練習問題

★mutexでのセマフォの実現

mutexを使ってセマフォを実現しなさい。

Java で利用可能なセマフォを実現しなさい。

★TSDによるスレッド・セーフな関数

次のライブラリ関数は、static 変数に結果を保存して返すので、スレッド・ セーフではない。

getlogin() readdir() strtok() asctime() ctime() gmtime() localtime() rand() getgrgi() getgrnam() getpwuid() getpwnam()

これらのライブラリ関数を、スレッド固有データを使うように修正しなさい。 この時、引数の数と型、結果の型は、スレッド・セーフでないものと同じにな るようにしなさい。ただし、名前には、_tsd というサフィックスを付け、ス レッド・セーフではないものと区別すること。実現では、それぞれのリエント ラント版を使ってもよい。たとえば、getlogin_tsd() の実現において、 getlogin_r() を使ってよい。

実現した関数と、mutex を使う方法との性能を比較しなさい。

★読み書きロックの利用

銀行口座として、普通口座と定期口座の２つの口座を考える。その２つの口座 の総合残高を返す手続きを、読み書きロックを使って書きなさい。総合残高以 外にも、それぞれの口座は、単独に預入、引出しができるようにすること。

★デットロックの回避

２つの銀行口座の間で、デットロックが起きないように預金を移動させる手続 きを実現しなさい。

■課題

先週、並列処理の台数効果をきちんと示した人は、今週の課題は出さなくてもよい。

先週、化学反応や狭い路で再提出だった人は、今週は次のいずれかを選択する。

いずれの課題も、きちんと台数効果を調べること。

先週、配列の総和の課題を選択した人で、再提出と指示された人は、再提出する。

締め切りは、2002/02/06 (水曜日) 18:00 とする。(23:59:59 ではない)。

レポートは、次のような形式の電子メールで送ること。 

----------------------------------------------------------------------
To: yas@is.tsukuba.ac.jp
Subject: [pdsoft/report-thread-3] ＜内容に関したサブジェクト＞

学籍番号 000000 (各自の学籍番号で置き換える)
名前 漢字の名前

＜内容＞
----------------------------------------------------------------------
前々回の注意事項も参照のこと。
↑[もどる] ←[1月17日] ・[1月24日] →[1月31日]
Last updated: 2002/01/31 03:16:01
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>