マルチスレッド(3)

並行システム

                               システム情報工学研究科コンピュータサイエンス専攻、電子・情報工学系
                               新城 靖
                               <yas@is.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2009/2009-12-25
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/sie/
http://www.cs.tsukuba.ac.jp/~yas/

■今日の重要な話

■プロセスのアドレス空間

Unixのプロセスのメモリは、はテキストセグメント, データセグメント, ス タックセグメントに分類される。ここでセグメントとは、連続したメモリの領 域のことである(x86 アーキテクチャのセグメントとは祖先は同じだが意味は違う)。

テキスト、データ、スタックセグメント

図? プロセスのアドレス空間(単一スレッド)

◆テキストセグメント

機械語命令を置くためのセグメンを テキスト・セグメント ( text segment, ) という。このセグメントは、普通、読み出し専用になっていて, 同じロードモ ジュールのプロセスの間で共有される。例えばシェルは複数のユーザが同時に 使うことが多いが、この場合、テキストセグメントのためのメモリは1セット だけでよい。

機械語を書き換えながら実行するプログラムは、最近は行儀が悪いとされてい る。キャッシュの関係で特別な操作をしないと動かない。

◆データセグメント

データ・セグメント ( data segment, ) は、データを置く領域である. C言語の 静的変数(static)大域変数(extern) malloc() で割り当てたヒープ上の変数は、 このセグメントに置かれる。 ( 自動変数(auto) は、次のスタック・セグメントに置かれる。 ) データセグメントは, 次の3つにわかれている。
データ
静的変数や大域変数のうち、初期値つき変数が置かれるところ
BSS
静的変数や大域変数のうち、初期値を指定しない(初期値が0)が置かれるところ
ヒープ(heap) malloc() で確保する変数が置かれるところ
データの初期値は、実行形式ファイルに含まれている。 例えばC言語で
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() ライブラリ関数から呼び出さ れる。

◆スタックセグメント

スタック・セグメント ( stack segment, ) とはスタックを置くためのメモリ領域である。C言語の 自動変数(auto variable)、 変数は、ここに置かれる。

C言語で

main()
{
    auto int z;
}
とすると、 4バイトの領域がスタックセグメントに割りつけられる。 (autoというキーワードは、普通省略される。スタックセグメ ントは、普通、0xffffff (32ビットのアドレス空間の場合)からからアドレス が小さくなるほうに向かって伸びていく。この部分は、関数呼び出しが続くと 伸びていき、割り当てられたメモリよりも多くなると、カーネルが自動的に拡 張する。

◆mainの引数と環境変数

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/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/sie/csys-2009/2009-12-25/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/sie/csys-2009/2009-12-25/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)
% []
MacOSX では、動的リンク・ライブラリの種類は、otool -L で表示される。 Linux, Solaris 等では、ldd コマンドが使える。

■スレッド固有データ

マルチスレッドでは、変数の考え方が変ってくる。

◆変数の寿命とスコープ

プログラミング言語の変数には、スコープと寿命がある。
スコープ
空間的な概念。 プログラムの字面上、どの範囲から使えるか。 プログラムで、スコープにない変数をアクセスするとコンパイル時にエラーに なる。
寿命
時間的な概念。 「いつ」、その変数がアクセス可能になり、「いつ」、アクセスできなく なるのか。実行時のタイミング。 無効になった変数を無理やり使うと、何が起るかわからない。(C言語では、 ポインタを通じて、無効になった変数をアクセスできてしまうことがある。)
int x;

f()
{
    int y ;
    static int z ;
}
種類 スコープ 寿命
extern 外部変数 全プログラム プログラムの実行開始から終了まで
auto 普通の局所変数 関数内 その関数の実行中とそこから別の関数を呼んでいる間
staticな局所変数 関数内 プログラムの実行開始から終了まで
static変数(関数の外に定義) 同一ファイル内 プログラムの実行開始から終了まで
(C言語にはない) (いろいろ) プログラムの終了後も残る(永続的)
永続的の反対は揮発的。

◆大域変数、静的変数

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

テキスト、データ、スタック複数

図? プロセスのアドレス空間(マルチスレッド)

◆スコープ

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

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

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

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

◆例:tsd_counter

   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_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-2009/2009-12-25/ex/tsd-counter.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2009/2009-12-25/ex/tsd-counter-main.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2009/2009-12-25/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()
thread1(): value=20 
thread1(): value=11 
thread2(): value=21 
thread1(): value=12 
thread2(): value=22 
thread1(): value=13 
thread2(): value=23 
% []

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

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

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

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

◆実行時特化による pthread_getspecific() のオーバヘッドの削減

実行時特化(部分評価)の技術を使うと、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

ソース、Tempo、テンプレート、実行時特化器

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() .

◆Java

Runnable を自分で定義し、かつ、スレッドごとに new すれば、そのオブジェ クトが持っている変数はスレッド固有データである。

ライブラリを実現する場合、自分自身では 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()

■読み書きロック

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

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

普通のロック、読書きロック

図? 普通のロック、読書きロック

読むだけでもロックする必要がある。さもないと、読んでいる途中で変化する ことがある。

◆Unixの読み書きロック

Unix のファイルに対するロックの機能も、読み書きロックがある。

flock(BSD)

int flock( fd,  operation);
int fd, operation;

operation の種類 
    LOCK_SH    shared lock (読み)
    LOCK_EX    exclusive lock (書き)
    LOCK_UN    unlock
    LOCK_NB    ロックと一緒に使って non-blocking

lockf(System V)

#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 */

fcntl()

#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)).

◆Pthreadの読み書きロック

初期の 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);

◆Javaの読み書きロック

Java 2 Platform Standard Ed. 5.0 java.util.concurrent.locks.ReentrantReadWriteLock http://java.sun.com/j2se/1.5.0/ja/docs/ja/api/java/util/concurrent/locks/ReentrantReadWriteLock.html http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

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 lock と mandatory lock

mandatory lock
ロックに関する命令を実行していなくても、操作ができなくなる。
advisory lock
ロックに関する命令を実行している時だけ、ブロックされる。
講義で説明したものは、どれも、advisory lock である。いくら mutex を使っ たり、synchronized をつけたとしても、付け忘れた部分があれば、ロックは 働かない。

読み書きロックでも、読み込みだけ行うスレッドも読み込みで advisory ロッ クを行う必要がある。ロックを行わないでアクセスしてはいけない。

例:銀行口座が円とドルで2種類あった時に、合計の残高を知りたい。

Unix 系、Pthread, Java は、advisory lock。 Windows には、mandatory lock がある。

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

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

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

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

どうしても必要な時:

◆forkとexecの扱い

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

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

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

◆その他のPthreadの機能

■デッドロック対策

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

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

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 );

◆4条件

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

◆対策

◆防止策

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

◆Pthreadでの対応策:防止

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

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

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

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

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

◆ライブロック

スレッドはブロックしていないが、何度やっても決して成功しない試みを繰り 返す。

◆トランザクション

Pthreadでは使えないが、トランザクションの機能を当てにすると、簡単にデッ ドロックの対策をする方法がある。 デッドロックを検出すると、スレッドを kill して、トランザクションを アボートする。

◆Javaでの対応策:防止

解決方法(1): 複数のオブジェクトを synchronized でロックする時、順序を 決める。 http://gee.cs.oswego.edu/dl/cpj/の2.2.5節より:

デッドロックの危険性があるコード。

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;
    }
  }

■練習問題

この日のクイズとして、406 と 407 について回答しなさい。

★問題(401) TSDによるスレッド・セーフな関数

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

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

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

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

★問題(402) 読み書きロックの利用

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

プログラミング言語としては、C言語(+Pthreads)、Java、または、採点者が理 解できるものを用いなさい。

★問題(403) デットロック対策のある送金

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

プログラミング言語としては、C言語(+Pthreads)、Java、または、採点者が理 解できるものを用いなさい。

★問題(404) スレッド固有データの利用

Java 等、C言語+Pthread以外の言語で、 tsd_counterのプログラムを書き直しなさい。

C言語であっても、Pthread ではなく、Visual C++ 等のコンパイラが持つ機能 を用いるものも認める。

★問題(405) デットロック対策のあるCell

Javaでの対応策で述べたデッドロックを防止し た Cell クラスを、C言語+Pthread等のJava 言語以外の言語で実装しなさい。

★問題(406) デッドロック

次のプログラムは、銀行口座を実現したものの一部である。空欄「/*(a)*/」か ら「/*(i)*/」を埋めて、デッドロックが起きないように、口座間で送金する手 続き transfer() を完成させなさい。ただし、このプログラムでは、残高が負 になることを許すものとする。ただし、何も記述するべきではない欄には、 「/**/」と記述しなさい。
class BankAccount {
    long value;
    synchronized long balance() { return value; }
    synchronized void deposit(long n) { value += n; }
    synchronized void withdraw(long n) { value -= n; }

    /*(a)*/ void transfer(BankAccount other,long n) {
        if ( /*(b)*/ )
            return;
        else if ( /*(c)*/  <
                  /*(d)*/  )
            /*(e)*/
        else
            /*(f)*/
    }
    /*(g)*/ void doTransfer(BankAccount other,long n) {
        /*(h)*/
        this.withdraw( n );
        /*(i)*/
    }
}

★問題(407) 読み書きロック

読み書きロックは、単純なロックと比較して1度に実行できるスレッドの数が 多くなることがある。そのようになる例を1つ使って、読み書きロックの利点 を説明しなさい。
Last updated: 2010/02/19 15:11:12
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>