マルチスレッド(1)

並列分散ソフトウェア

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

このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08
あるいは、次のページから手繰っていくこともできます。
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

■スレッド・プログラミング

◆スレッドとは

スレッド(thread) あるいは、 軽量プロセス(lightweight processes) とは、 1つの保護の単位としての プロセス(タスク,あるいは,アドレス空間) 内部にふくまれている論理的な並列処理の単位。

シングルスレッドのプログラム
1度に1つの手続き(Cの関数)しか動かない。
マルチスレッドのプログラム
1度にスレッドの数だけの手続きが論理的には同時に動く。 (同期でブロックされているものも含む)

図? シングルスレッドのプロセスとマルチスレッドのプロセス

図? シングルスレッドのプロセスとマルチスレッドのプロセス

軽量プロセスというと、内部にループを含むような語感がある。

◆スレッドの利用目的

◆本当にスレッドが必要か

John K. Ousterhout, "Why Threads Are A Bad Idea (for most purposes)", Invited Talk at the 1996 USENIX Technical Conference (January 25, 1996). [PDF] [PowerPoint]

マルチスレッドプログラミングは、非常に難しい。

シングルスレッドのイベント駆動で書けるなら、その方がいい。 GUI、分散など。

どこでスレッドを使うべきか。

◆スレッドの内容

個々のスレッドごとに持つもの プロセス全体で共有

■Pthread

Pthread は、POSIX 1003.1c-1995という標準に準拠したスレッド・ライブラリ。 POSIX Thread とも呼ばれる。

◆Pthreadを利用したプログラムのコンパイル

Pthread を利用したプログラムを書く時には、次のようなヘッダ・ファイルを 読み込む。


#include <pthread.h>

Solaris (Unix International系)でのコンパイルとリンク。 -D_REENTRANT-lpthread を付ける。


----------------------------------------------------------------------
% cc -D_REENTRANT -o create create.c -lpthread [←]
% ./create [←]
...
% []
----------------------------------------------------------------------
セマフォを使う時、Solaris 6 (SunOS 5.6, sakura) では、リンク時に -lposix4 オプションを付ける。Solaris 7-9 (SunOS 5.7, 5.8, 5.9) では、リンク時に -lrt オプションを付ける。

SGI (O2, Origin) でのコンパイルとリンク。-lpthread を付ける。


----------------------------------------------------------------------
% cc -o create create.c -lpthread [←]
% ./create [←]
...
% []
----------------------------------------------------------------------

■スレッドの生成・消滅

スレッドは、普通のプログラムの、 サブルーチン(C言語の関数、手続き) に近い。 サブルーチンの場合,呼び出すと、呼び出された方が動き、自分自身は,止ま る。スレッドでは,新たにスレッドを生成した場合,生成した方と生成さ れた方は,論理的には2つとも同時に動く。

■fork-joinモデル

図? fork-joinモデルの実現

図? fork-joinモデルの実現

  1. 逐次処理(スレッド/プロセスが1つ)の状態から始まる
  2. 並列性が必要になった時、fork命令で複数のスレッド/プロセスに分か れて並列処理を行う。
  3. 並列に動作できる部分が終ると join 命令で再び逐次処理に戻る。

◆Unixのfork

fork() システムコールでコピーが作られる。 join の代わりに、子どもは exit()、親は wait()。

◆Pthreadはcreate

Pthread では、コピーではなく create で新たにスレッドを作る。同じ関数を 実行したい時には、直接 call する。(別の関数を実行するなら呼ばなくても よい。) 子スレッドでは、pthread_exit() (トップの 手続きからリターン)、 親は、pthread_join() する。

後で join する必要がない時には、pthread_detach() を使って切り離す。 (joinしなくてもゾンビが残らない。)

◆スレッドの生成とjoin


----------------------------------------------------------------------
   1: 
   2: /*
   3:         create-join-2.c -- スレッドを2つ作るプログラム
   4: */
   5: 
   6: #include <pthread.h>
   7: 
   8: void func1( int x );
   9: void func2( int x );
  10: 
  11: main()
  12: {
  13:     pthread_t t1 ;
  14:     pthread_t t2 ;
  15:         pthread_create( &t1, NULL, (void *)func1, (void *)10 );
  16:         pthread_create( &t2, NULL, (void *)func2, (void *)20 );
  17:         printf("main()\n");
  18:         pthread_join( t1, NULL );
  19:         pthread_join( t2, NULL );
  20: }
  21: 
  22: void func1( int x )
  23: {
  24:     int i ;
  25:         for( i = 0 ; i<3 ; i++ )
  26:         {
  27:             printf("func1( %d ): %d \n",x, i );
  28:         }
  29: }
  30: 
  31: void func2( int x )
  32: {
  33:     int i ;
  34:         for( i = 0 ; i<3 ; i++ )
  35:         {
  36:             printf("func2( %d ): %d \n",x, i );
  37:         }
  38: }
----------------------------------------------------------------------

実行例。

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/create-join-2.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/Makefile [←]
% make create-join-2 [←]
gcc -D_REENTRANT -g   -c create-join-2.c -o create-join-2.o
gcc -D_REENTRANT -g -o create-join-2 create-join-2.o -lpthread
% ./create-join-2  [←]
main()
func1( 10 ): 0 
func1( 10 ): 1 
func1( 10 ): 2 
func2( 20 ): 0 
func2( 20 ): 1 
func2( 20 ): 2 
% []
----------------------------------------------------------------------
この例では、次の3つのスレッドが作られる。
  1. main を実行しているスレッド
  2. func2 から作られたスレッド t2
  3. func1 から作られたスレッド t1
マルチスレッド・プログラミングでは、main関数もまた1つのスレッドが実行 していると考える。これを 初期スレッド 、あるいは、 メインスレッド とよぶ。Pthrad では、 メインスレッド以外のスレッドは、 pthread_create() により作られる。

どういう順序で実行されるかは、決まっていない。 決まっていない。スレッドは、もともと順番を決めないような処理、 非同期的(asynchronous) な処理を表現するためのもの。どうしても他のスレッドと同期を行なう必要が 出てきた時には、mutex や条件変数といった同期機能を使う。

pthread_create()で指定された関数からリターンすると、そ のスレッドが終了する。pthread_exit() を呼び出してもよい。 ただし、 初期スレッド が終了すると、プロセス全体が終了する。 exit() システムコールを呼び出しても終了する。

■mutexによるスレッド間の同期

◆共有資源

複数のプロセス/スレッドで共有しなければならないもの。

プロセスの場合、ファイル、端末、ウインドウ、主記憶、CPU時間。

主記憶やCPU時間といった資源は、横取りしても平気なので、あまり問題になりない。

スレッドの場合は、プログラミング言語の変数。

変更されない変数の値を読むだけなら、特に問題は起きない。それ意外の時、 特に、複数のスレッドで値を読み書きする時に問題が起きる。

◆複数のスレッドによる共有資源のアクセス(ロックなし)


----------------------------------------------------------------------
   1: 
   2: /*
   3:  * mutex-nolock.c -- 共有資源をロックなしでアクセスするプログラム
   4:  */
   5: 
   6: #include <pthread.h>
   7: 
   8: void thread_A(), thread_B();
   9: int     shared_resource ;
  10: 
  11: main() {
  12:     pthread_t t1 ;
  13:     pthread_t t2 ;
  14:         shared_resource = 0 ;
  15:         pthread_setconcurrency( 2 );
  16:         pthread_create( &t1, NULL, (void *)thread_A, 0 );
  17:         pthread_create( &t2, NULL, (void *)thread_B, 0 );
  18:         pthread_join( t1, NULL );
  19:         pthread_join( t2, NULL );
  20:         printf("main(): shared_resource == %d\n", shared_resource );
  21: }
  22: 
  23: void thread_A()
  24: {
  25:     int i, x ;
  26:         for( i = 0 ; i<1000000 ; i++ )
  27:         {
  28:             x = shared_resource ;
  29:             x = x + 1 ;
  30:             shared_resource = x ;
  31:         }
  32: }
  33: 
  34: void thread_B() {
  35:     int i, x ;
  36:         for( i = 0 ; i<1000000 ; i++ ) {
  37:             x = shared_resource ;
  38:             x = x + 1 ;
  39:             shared_resource = x ;
  40:         }
  41: }
----------------------------------------------------------------------

pthread_setconcurrency() は、利用したい CPU 数をシステムに要求するもの。 Solaris 6 (SunOS 5.6, sakura) では、thr_setconcurrency() を使う。

◆実行結果(ロックなし)

共有メモリ型マルチプロセッサでの実行結果(sakura,icho)。

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/mutex-nolock.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/Makefile [←]
% make mutex-nolock [←]
gcc -D_REENTRANT -g -mcpu=v8 -Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency   -c mutex-nolock.c -o mutex-nolock.o
gcc -D_REENTRANT mutex-nolock.o -lpthread -lposix4 -o mutex-nolock
% ./mutex-nolock [←]
main(): shared_resource == 1004100
% ./mutex-nolock [←]
main(): shared_resource == 1003470
% ./mutex-nolock [←]
main(): shared_resource == 1003316
% ./mutex-nolock [←]
main(): shared_resource == 1003143
%
----------------------------------------------------------------------
thread_A(), thread_B()と2つのスレッドが作 られている。整数型の変数 shared_resource は、その2つの スレッドの両方からアクセスされる。2つのスレッドで合計2000000 増える予 定だが、実際に実行すると、そうはならない。実行する度に答えが違う。

◆考察(ロックなし)

このプログラムが共有メモリ型マルチプロセッサで動いているとして、動きを 考えてえる。


----------------------------------------------------------------------
thread_A()			thread_B()
	:				:
	:				:
28: x = shared_resource ;
				37: x = shared_resource ;
29: x = x + 1 ;
				38: x = x + 1 ;
30: shared_resource = x ;
				39: shared_resource = x ;
	:				:
	:				:
----------------------------------------------------------------------

shared_resource++と書いてもだめ。複数の機械語命令に分割 されるので。

◆相互排除

相互排除(mutual exclusion): ある資源をアクセスできるスレッドの数を 多くても1つにする。

プログラムの字面上、相互排除が必要な部分を 際どい部分(critical section) ( クリティカルセクション ) という。

◆Pthreadでの相互排除

Pthread では、相互排除を行なうために、 mutex という仕組みがある。次のようにして、相互排除を行ないたい部分を lock と unlock で囲む。

    pthread_mutex_t mutex1 ;
	:
	:
    pthread_mutex_lock( &murex1 );
	<相互排除したい部分(際どい部分)>
    pthread_mutex_unlock( &mutex1 );

◆複数のスレッドによる共有資源のアクセス(ロック付き)

ロックなしのプログラムを、mutex を使っ て書き直したもの。

----------------------------------------------------------------------
   1: /*
   2:  * mutex-lock.c -- 共有資源をロックしながらアクセスするプログラム
   3:  */
   4: 
   5: #include <pthread.h>
   6: 
   7: void thread_A(), thread_B();
   8: int     shared_resource ;
   9: pthread_mutex_t mutex1 ;
  10: 
  11: main() {
  12:     pthread_t t1 ;
  13:     pthread_t t2 ;
  14:         shared_resource = 0 ;
  15:         pthread_mutex_init( &mutex1, NULL );
  16:         pthread_setconcurrency( 2 );
  17:         pthread_create( &t1, NULL, (void *)thread_A, 0 );
  18:         pthread_create( &t2, NULL, (void *)thread_B, 0 );
  19:         pthread_join( t1, NULL );
  20:         pthread_join( t2, NULL );
  21:         printf("main(): shared_resource == %d\n", shared_resource );
  22: }
  23: 
  24: void thread_A()
  25: {
  26:     int i, x ;
  27:         for( i = 0 ; i<1000000 ; i++ )
  28:         {
  29:             pthread_mutex_lock( &mutex1 );
  30:             x = shared_resource ;
  31:             x = x + 1 ;
  32:             shared_resource = x ;
  33:             pthread_mutex_unlock( &mutex1 );
  34:         }
  35: }
  36: 
  37: void thread_B() {
  38:     int i, x ;
  39:         for( i = 0 ; i<1000000 ; i++ ) {
  40:             pthread_mutex_lock( &mutex1 );
  41:             x = shared_resource ;
  42:             x = x + 1 ;
  43:             shared_resource = x ;
  44:             pthread_mutex_unlock( &mutex1 );
  45:         }
  46: }
----------------------------------------------------------------------

◆実行結果(ロック付き)


----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/mutex-lock.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/Makefile [←]
% make mutex-lock [←]
gcc -D_REENTRANT mutex-lock.o -lpthread -lposix4 -o mutex-lock
% ./mutex-lock  [←]
main(): shared_resource == 2000000
% ./mutex-lock [←]
main(): shared_resource == 2000000
% ./mutex-lock [←]
main(): shared_resource == 2000000
% []
----------------------------------------------------------------------

◆考察(ロック付き)

このプログラムが共有メモリ型マルチプロセッサで動いているとして、動きを 考えてえる。

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

	:					:
29: pthread_mutex_lock( &mutex1 );		:
					40: pthread_mutex_lock( &mutex1 );
30: x = shared_resource ;		<他のスレッドが実行中なので
31: x = x + 1 ;				 この状態でしばらく待たされる>
32: shared_resource = x ;			:
33: pthread_mutex_unlock( &mutex1 );		:
	:				<実行再開>
	:				41: x = shared_resource ;
					42: x = x + 1 ;
					43: shared_resource = x ;
					44: pthread_mutex_unlock( &mutex1 );
----------------------------------------------------------------------

後から来た thread_B() は、他のスレッドが実行中は、待たさ れる。

■条件変数によるスレッド間の同期

スレッドでプログラムを作っていると、あるスレッドが別のスレッドの仕事の 完了を待つ必要が出がある。

◆パイプと循環バッファ

Unix のパイプのようなことをスレッドを使って実行するしたい。

----------------------------------------------------------------------
thread_A | thread_B
----------------------------------------------------------------------
2つのスレッドの間には、バッファを置く。

図? 環状バッファ、生産者スレッド、消費者スレッド

図? 環状バッファ、生産者スレッド、消費者スレッド

バッファが空の時、thread_B() は、thread_A() が何かデー タをバッファに入れるのを待つ。バッファがいっぱいの時、thread_A() は、thread_B() がバッファから何かデータを取り出すのを待つ。

◆条件変数

条件変数(condition variable) で、ある条件が生じたことを待つ。

条件変数の操作:

wait
ある条件が満たされるまで待つ
signal
ある条件が満たされたことを伝える。待っているスレッドが1つだけ起き上がる。
broadcast
ある条件が満たされたことを伝える。待っているスレッドが全て起き上がる。

◆条件変数を使った環状バッファ


----------------------------------------------------------------------
   1: 
   2: /*
   3:  * condv-buffer.c -- 条件変数を使った環状バッファ
   4: */
   5: 
   6: #include <pthread.h>
   7: 
   8: void thread_A(), thread_B();
   9: 
  10: #define BUFFER_SIZE     4               /* バッファの大きさ */
  11: struct circular_buffer
  12: {
  13:         int rp ;                        /* 読み出す位置 */
  14:         int wp ;                        /* 書き込む位置 */
  15:         int used ;                      /* バッファ内の要素数 */
  16:         int data[BUFFER_SIZE];          /* データを保存する場所 */
  17:         pthread_mutex_t mutex ;         /* この構造体の相互排除のための mutex */
  18:         pthread_cond_t  not_full ;      /* バッファが一杯ではない状態を待つための条件変数 */
  19:         pthread_cond_t  not_empty ;     /* バッファが空ではない状態を待つための条件変数 */
  20: };
  21: 
  22: void put( struct circular_buffer *b,int x )
  23: {
  24:         pthread_mutex_lock( &b->mutex );
  25: loop:   if( b->used == BUFFER_SIZE )
  26:         {
  27:             pthread_cond_wait( &b->not_full,&b->mutex );
  28:             goto loop;
  29:         }
  30:         b->data[ b->wp++ ] = x ;
  31:         if( b->wp >= BUFFER_SIZE )
  32:             b->wp = 0 ;
  33:         b->used ++ ;
  34:         pthread_cond_signal( &b->not_empty );
  35:         pthread_mutex_unlock( &b->mutex );
  36: }
  37: 
  38: int get( struct circular_buffer *b )
  39: {
  40:     int x ;
  41:         pthread_mutex_lock( &b->mutex );
  42: loop:   if( b->used == 0 )
  43:         {
  44:             pthread_cond_wait( &b->not_empty,&b->mutex );
  45:             goto loop;
  46:         }
  47:         x = b->data[ b->rp++ ] ;
  48:         if( b->rp >= BUFFER_SIZE )
  49:             b->rp = 0 ;
  50:         b->used -- ;
  51:         pthread_cond_signal( &b->not_full );
  52:         pthread_mutex_unlock( &b->mutex );
  53:         return( x );
  54: }
  55: 
  56: main()
  57: {
  58:     pthread_t t1 ;
  59:     pthread_t t2 ;
  60:     struct circular_buffer *b  ;
  61:         b = (struct circular_buffer *)malloc(sizeof(struct circular_buffer));
  62:         if( b == NULL )
  63:         {
  64:             perror("no memory for struct buffer\n");
  65:             exit( -1 );
  66:         }
  67:         b->rp = 0 ;
  68:         b->wp = 0 ;
  69:         b->used = 0 ;
  70:         pthread_mutex_init( &b->mutex, NULL );
  71:         pthread_cond_init( &b->not_full,NULL );
  72:         pthread_cond_init( &b->not_empty,NULL );
  73:         pthread_setconcurrency( 2 );
  74:         pthread_create( &t1, NULL, (void *)thread_A, (void *)b );
  75:         pthread_create( &t2, NULL, (void *)thread_B, (void *)b );
  76:         pthread_join( t1, NULL );
  77:         pthread_join( t2, NULL );
  78: }
  79: 
  80: void thread_A( struct circular_buffer *b )      /* producer */
  81: {
  82:     int i,x ;
  83:         for( i = 0 ; i<10 ; i++ )
  84:         {
  85:             x = i ;
  86:             printf("thread_A(): put( %d )\n",x );
  87:             put( b,x );
  88:         }
  89: }
  90: 
  91: void thread_B( struct circular_buffer *b )      /* consumer */
  92: {
  93:     int i, x ;
  94:         for( i = 0 ; i<10 ; i++ )
  95:         {
  96:             x = get( b );
  97:             printf("thread_B(): get() %d.\n", x );
  98:         }
  99: }
----------------------------------------------------------------------

put() は、バッファにデータを追加する時に使う手続き。

基本的には、入口で pthread_mutex_lock() し、 出口で pthread_mutex_unlock() する。

バッファが一杯の時には、条件変数b->not_full で、 一杯でないという条件になるまで待つ。

待っている間は、mutex のロックは解除される。

pthread_cond_wait() からリターンして来る時には、もう一度 ロックされた状態に戻るが、待っている間に、他の変数 (rp,wp,data)が書き換えられている可能性があるので、もう一 度最初から調べる。

get() は、バッファからデータを取り出す時に使う手 続き。put()とほぼ対称形。バッファが空の時に、wait し、バッファがもはや一杯ではないことをsignal する。

thread_A() は、10回バッファにデータを書き込むスレッド。 thread_B() は逆に、10回バッファからデータを読み出すス レッド。

◆実行結果


----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/condv-buffer.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-08/ex/Makefile [←]
% make condv-buffer [←]
gcc -D_REENTRANT -g -mcpu=v8 -Dpthread_setconcurrency=thr_setconcurrency -Dpthread_getconcurrency=thr_getconcurrency   -c condv-buffer.c -o condv-buffer.o
gcc -D_REENTRANT condv-buffer.o -lpthread -lposix4 -o condv-buffer
% ./condv-buffer  [←]
thread_A(): put( 0 )
thread_A(): put( 1 )
thread_A(): put( 2 )
thread_A(): put( 3 )
thread_A(): put( 4 )
thread_A(): put( 5 )
thread_B(): get() 0.
thread_B(): get() 1.
thread_B(): get() 2.
thread_B(): get() 3.
thread_B(): get() 4.
thread_A(): put( 6 )
thread_A(): put( 7 )
thread_A(): put( 8 )
thread_A(): put( 9 )
thread_B(): get() 5.
thread_B(): get() 6.
thread_B(): get() 7.
thread_B(): get() 8.
thread_B(): get() 9.
% []
----------------------------------------------------------------------
複数のスレッドが同時に動いている。バッファにためられるのは、最大4なの に、put() が 5 回連続して成功しているように見える。printf() の順番と put(), get() の順番は違うことがある。

◆ダブルバッファリング

整数を1つバッファに書き込むだけでロック/アンロックを行なっていると、 実際の並列処理では重たい。ロックの回数を減らすために、ダブルバッファリ ングと呼ばれる技術がよく使われる。読み手と書き手で別々にバッファをもう け、1つのバッファの処理をしている間は、ロックを行なわない。

◆signalかbroadcastか

バッファに要素を「1つずつ」追加しているので、 pthread_cond_signal() でもよい。 pthread_cond_broadcast() に変えても動くようにプログラムを 作る。

pthread_cond_wait() で待っている間に条件が変わっているかもしれないので、 最初から調べ直す。signal で1人だけしか起き上がらないと仮定してはいけ ない。

「1つずつ」ではなく、複数個同時に読み書きする時には、 pthread_cond_broadcast() でないとだめ。

迷った時には、pthread_cond_broadcast()

■スレッドとメモリ

◆Pthreadのメモリモデル

一種の弱い一貫性(weak consistency)。release consistency に近い。 同期を使えば問題がないが、同期をとっていないと何が起きるか予想できない。

◆auto変数

各スレッドには、独立したスタックが割り当てられる。C言語の auto 変数は、 スレッドごとにコピーが作られる。

<−>再帰呼出し

スレッド間でポインタを渡す時には、スレッドの寿命にも注意。

◆static変数

シングルスレッドのプログラムでは、static変数は、プログラムのモジュール性 を高めるために有効に使われてきた。

マルチスレッドと相性が非常に悪い。static変数もextern変数と同様に複数の スレッドで共有される。変更する場合には、mutex でロックが必要になる。

◆static変数を使ったライブラリ関数

TCP/IP でプログラムを書く時に使う gethostbyname() は、 static変数に値をセットして、リターン・バリューとして返してる。

----------------------------------------------------------------------
struct hostent *gethostbyname( char *name ){
    static struct hostent ret ;
	.....
	return( &ret );
}
----------------------------------------------------------------------

複数のスレッドが同時にこの関数を呼び出した場合、同じstatic変数が使われ る。

◆スレッド・セーフ

複数のスレッドで呼び出してもきちんと動作することを、 スレッド・セーフ(thread-safe) という。 MT-Safe(multi-thread-safe)再入可能(reentrant) ということもある。

externやstaticを使わず、auto変数やmalloc()だけを使っているような手続き は、スレッド・セーフ。

別のスレッド・セーフでない手続きを呼んでいれば、それはスレッド・セーフ ではない。

◆スレッド・セーフなインタフェース

スレッド・セーフになるようにするには、インタフェースを変更する必要があ る。
Sun のマニュアルより:
----------------------------------------------------------------------
struct hostent *gethostbyname(const char *name);

struct hostent *gethostbyname_r(const char *name,
     struct hostent *result, char *buffer, int buflen,
     int *h_errnop);

----------------------------------------------------------------------
O2には、gethostbyname_r() はない。

◆スレッド・セーフではない手続きを使う

一見無関係の手続きが内部で変数を共有している場合がある。

■Pthreadでのセマフォの利用

Pthread には、実時間機能を実現することを目的として、セマフォが使えるよ うになっている。実時間以外の目的でも、セマフォを使ってもよい。

次のような関数が利用可能である。


#include <semaphore.h>

int sem_init(sem_t *sem, int pshared, unsigned int value)
初期化。psharedが0だとプロセス内で有効。valueは初期値。
int sem_wait(sem_t * sem)
P命令。値を減らす。0の場合は止まる。
int sem_trywait(sem_t * sem)
非ブロックのsem_wait()。0でも止まらずエラーを返す。
int sem_post(sem_t * sem)
V命令。値を増やす。
int sem_getvalue(sem_t * sem, int * sval)
現在の値を返す。普通は役には立たない。次の瞬間には他のスレッドがP/Vしているかもしれないので。
int sem_destroy(sem_t * sem)
セマフォを破棄する。
注意: SystemV 由来のセマフォ(semget(),semop(),semctl())とは違う。

注意:名前付きのセマフォもある。sem_open() で作成/初期化し、 sem_unlink() で削除する。

注意:Solaris には、POSIX のセマフォとは別に、カーネル内でのデバイス・ ドライバ作成のためのセマフォが用意されている。

■Javaのスレッド

Java には、最初から言語のレベルでスレッドの機能が入っている。

----------------------------------------------------------------------
Java			Pthread
----------------------------------------------------------------------
new Thread(); start();	pthread_create()
join()			pthread_join()
synchronized		pthread_mutex_lock()とpthread_mutex_unlock()の組
wait()			pthread_cond_wait()
wait(long timeout)	pthread_cond_timedwait()
notify()		pthread_cond_signal()
notifyAll()		pthread_cond_broadcast()
----------------------------------------------------------------------

Java の synchronized は、再帰可能。PTHREAD_MUTEX_RECURSIVE 相当。 1つのスレッドが2度同じオブジェクトをロックしてもよい。

Pthreads のプログラムで、1つの mutex と1つの条件変数を使ったものなら、 Java で簡単に書き直せる。

循環バッファのプログラムは、1つの mutex で2つの条件変数を使っているので、単純には Java で書き直せない。 生産者側と消費者側が同時に待つことはないという性質を利用する。

Java で書かれたスレッドのプログラムは、汚いものがけっこうある。スレッ ド「間」の同期で、対称系になるべき所を、片方のスレッドのメソッドにして、 非対称になっていることがある。Java でプログラムを書く時にも、active object (thread) と passive object (threadなし)をきちんと分けた方がよい。

◆Javaのメモリモデル

スレッド内は逐次と同じだが、スレッド間は volatile を除いて何がおきるか わからない。

long と double 以外の型は、原始的。 volatile long, volatle double は原始的。

一種の弱い一貫性(weak consistency)。release consistency に近い。

同期を使えば問題がないが、同期をとっていないと何が起きるか予想できない。

◆条件変数を使った環状バッファ(Java)


----------------------------------------------------------------------
   1: 
   2: /*
   3:  * CircularBuffer.java -- Java による環状バッファ
   4: */
   5: 
   6: class CircularBuffer
   7: {
   8:     static final int BUFFER_SIZE = 4 ;
   9:     int rp ;            // 読み出す位置
  10:     int wp ;            // 書き込む位置
  11:     int data[];         // データを保存する場所
  12:     int used ;          // バッファ内の要素数
  13:     CircularBuffer()
  14:     {
  15:         data = new int[BUFFER_SIZE];
  16:         rp = 0 ;
  17:         wp = 0 ;
  18:     }
  19: 
  20:     public synchronized void put( int x ) throws InterruptedException
  21:     {
  22:         while( used == data.length )
  23:             wait();
  24:         data[ wp++ ] = x ;
  25:         if( wp == data.length )
  26:             wp = 0 ;
  27:         if( used++ == 0 )
  28:             notifyAll();
  29:     }
  30: 
  31:     public synchronized int get() throws InterruptedException
  32:     {
  33:         int x ;
  34:         while( used == 0 )
  35:             wait();         
  36:         x = data[ rp++ ] ;
  37:         if( rp >= data.length )
  38:             rp = 0 ;
  39:         if( used-- == data.length )
  40:             notifyAll();
  41:         return( x );
  42:     }
  43: 
  44:     static void thread_A( CircularBuffer b )    // Producer
  45:     {                           
  46:         int i,x ;
  47:         try {
  48:             for( i = 0 ; i<10 ; i++ )
  49:             {
  50:                 x = i ;
  51:                 System.out.println("thread_A(): put( "+x+" )");
  52:                 b.put( x );
  53:             }
  54:         }
  55:         catch( InterruptedException e )
  56:         {
  57:             System.err.println("thread_A(): Interrupted");
  58:         }
  59:     }
  60: 
  61:     static void thread_B( CircularBuffer b )    // Consumer
  62:     {
  63:         int i, x ;
  64:         try {
  65:             for( i = 0 ; i<10 ; i++ )
  66:             {
  67:                 x = b.get();
  68:                 System.out.println("thread_B(): get() "+x+".");
  69:             }
  70:         }
  71:         catch( InterruptedException e )
  72:         {
  73:             System.err.println("thread_B(): Interrupted");
  74:         }
  75:     }
  76: 
  77:     static void main(String argv[])
  78:     {
  79:         final CircularBuffer b = new CircularBuffer();
  80:         Thread t1 = new Thread( new Runnable()
  81:                                  { public void run() {thread_A(b);} } );
  82:         t1.start();
  83:         Thread t2 = new Thread( new Runnable()
  84:                                  { public void run() {thread_B(b);} } );
  85:         t2.start();
  86:         try {
  87:             t1.join();
  88:             t2.join();
  89:         }
  90:         catch( InterruptedException e )
  91:         {
  92:             System.err.println("main(): Interrupted");
  93:         }
  94:     }
  95: }
----------------------------------------------------------------------

■練習問題

★スレッドの数

相互排除のプログラムや条件変数プログラムでスレッドの数を増やしてみなさい。

★手続きとスレッド

1つの手続き(C言語の関数)から複数のスレッドを生成してみなさい。

★ダブルバッファリング

循環バッファのプログラムダブルバッファリングを行なうプログラムに 変更しなさい。

★条件変数の削減

循環バッファのプログラムで、条件変数を1つになるように変更しなさい。

一度に wait する必要があるのは、put() 側か get() のどちらか一方だけである。 よって、両方とも同じキューにつないでも、動作する。

■課題

次の課題から1つを選んで提出しなさい。問題を難しい方に変えてもよい。締 め切りは、2004年1月/14 (水曜日) 18:00 とする。(23:59:59 ではない)。

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

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

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

<本文>
----------------------------------------------------------------------

<内容>

注意:sakura の新城のログイン名は、yshinjo である。 レポートは、yas@is.tsukuba.ac.jp に送ること。 Subject: には、pdsoft という文字とレポートの番号(report-thread-1)を必 ず含めなさい。

電子メールの本文の先頭に学籍番号と名前(漢字の名前がある人は、漢字で) を書きなさい。

内容は、文法的に正しい、日本語、または英語で書くこと。文章には、述語を 付ける。体言止めは、使ってはいけない。単にプログラムを含めるのではなく、 「以下に○○のプログラムを示す」と書く。実行結果を必ず付ける。

送られたレポートには、最初の締切り以降にまとめて確認応答(acknowledge) を返す。メッセージの紛失、クラッシュ等に対応するために、時間切れによる 再送などのリカバリは適宜やること。

送ったレポートは、講義が終るまで保存しなさい。

★狭い橋

1度に1方向の車しか通さない狭い橋がある。橋の上に同時に3台の車が通る と橋が落ちる。この橋が落ちないように、車の交通整理を実現するプログラム を書きなさい。車は、スレッドで実現されるものとする。そして、次のような 手続きを呼び出す。


vehicle(int direction)
{
	arrive_bridge( direction );
	cross_bridge( direction );
	exit_bridge( direction );
}


このコードで direction は、0 または 1 であり、橋のどの方向に車 が渡ろうとしているかを示している。 手続き arrive_bridge()exit_bridge() を、mutex と条件 変数を使って書きなさい。arrive_bridge() は、安全にその方向で車 が通れるまでリターンしてはならない。衝突したり、重量オーバーで橋が落ち たりすることがないようにしなければならない。デバッグのためのメッセージ を適宜画面に出力する。exit_bridge() は、橋を渡り終えことを告げ るために呼ばれる。この時、可能ならば、待っている車を渡らせ始める (arrive_bridge() からリターンさせる)。

ここでは、公平性は実現しなくてもよい。また、飢餓状態にならないことを保 証しなくてもよい。

完成したプログラムにおいて、新しい車が来た時、既に別の車が待っていたと する。この場合、新しい車が先に橋を渡るか、それとも古い車が先に橋を渡る か、それとも、予想できないか(非決定的か)。その理由を簡単に説明しなさ い。

★化学反応

酸素原子と水素原子から水が作られる反応を、スレッドを使って書きなさい。 このような手続きを、mutex と条件変数、または、セマフォを使って書きなさい。

水素原子や酸素原子ではなく、水素分子 (H2)や酸素分子 (O2)を使ってもよい。



pthread_create( ..., NULL, (void *)H_func, ... );
pthread_create( ..., NULL, (void *)H_func, ... );
pthread_create( ..., NULL, (void *)H_func, ... );
pthread_create( ..., NULL, (void *)H_func, ... );
pthread_create( ..., NULL, (void *)O_func, ... );
pthread_create( ..., NULL, (void *)O_func, ... );
pthread_create( ..., NULL, (void *)O_func, ... );

H_func( ... )
{
    printf(...);
    H_Ready(...);
}

O_func( ... )
{
    printf(...);
    O_Ready(...);
}

H2O_func( ... )
{
    printf(...);
}

H_Ready(...)
{
    ....
}

O_Ready(...)
{
    ....
}

make_water()
{
    pthread_create( ..., NULL, (void *)H2O_func, ... );
}


★循環バッファをセマフォで実現する

循環バッファのプログラムを、セマフォを使って書き直しなさい。

セマフォを使った循環バッファのプログラムの作成は、次の教科書の練習問 題にもなっている。

清水謙多郎: "オペレーティングシステム",岩波書店 (1992). ISBN: 4000078526.


↑[もどる] ←[12月25日] ・[1月8日] →[1月15日]
Last updated: 2004/01/08 03:16:06
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>