並列分散ソフトウェア
電子・情報工学系
新城 靖
<yas@is.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/2001-02-01
あるいは、次のページから手繰っていくこともできます。
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
シングルスレッド・プログラムをマルチスレッド・プログラムに変更しようと
した時に extern変数や static 変数をどうするか。
-
- 全スレッドで共有する(標準)
- スレッドごとにコピーを持たせる(スレッド固有データ)
auto変数は、スレッドごとにコピーが作られる。
（再帰を考えると関数呼出しごとにコピーが作られる。）
auto変数のスコープは、関数内。
auto変数より広い範囲で使えるスレッドごとのデータが必要になる。
key-value モデル。
概念的にには、２次元配列。
tsd[thread_id][key];
-
pthread_key_create()
- スレッド固有データのためのキーを生成する。プログラムの中で、固有
データごとに一度だけ呼び出す。
-
pthread_setspecific()
- スレッド固有データを設定する。スレッドごとに１度だけ呼び出す。
-
pthread_getspecific()
- スレッド固有データを参照する。必要になるたびに呼び出す。
----------------------------------------------------------------------
1:
2: /*
3: * tsd-counter.c
4: * $Header: /home/hlla/yas/cvs/sie-pdsoft-2000-examples/tsd-counter.c,v 1.1 2001/01/08 00:14:21 yas Exp $
5: * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/tsd-counter.c
6: * Start: 2001/01/08 08:51:25
7: */
8:
9: #include <stdio.h> /* stderr */
10: #include <stdlib.h> /* malloc() */
11: #include <pthread.h>
12:
13: struct tsd_counter
14: {
15: int tc_value ;
16: };
17:
18: static pthread_once_t tsd_counter_alloc_once = PTHREAD_ONCE_INIT ;
19: static pthread_key_t tsd_counter_tsdkey ;
20:
21: static void
22: tsd_counter_tsdkey_init()
23: {
24: extern void free(void *ptr);
25: pthread_key_create( &tsd_counter_tsdkey,free );
26: }
27:
28: static struct tsd_counter *
29: tsd_counter_alloc()
30: {
31: struct tsd_counter *tc ;
32:
33: pthread_once(&tsd_counter_alloc_once,tsd_counter_tsdkey_init);
34: tc = malloc( sizeof(struct tsd_counter) );
35: if( tc == 0 )
36: {
37: fprintf(stderr,"no memory for struct tsd_counter\n");
38: exit( -1 );
39: }
40: memset( tc, 0, sizeof(struct tsd_counter) );
41: if( pthread_setspecific( tsd_counter_tsdkey, tc ) != 0 )
42: {
43: fprintf(stderr, "pthread_setspecific().\n");
44: exit( -1 );
45: }
46: return( tc );
47: }
48:
49: static struct tsd_counter *
50: tsd_counter_gettsd()
51: {
52: struct tsd_counter *tc ;
53: tc = pthread_getspecific( tsd_counter_tsdkey );
54: if( tc == 0 )
55: {
56: tc = tsd_counter_alloc();
57: }
58: return( tc );
59: }
60:
61: void tsd_counter_reset( int val )
62: {
63: struct tsd_counter *tc ;
64: tc = tsd_counter_gettsd();
65: tc->tc_value = val ;
66: }
67:
68: void tsd_counter_up()
69: {
70: struct tsd_counter *tc ;
71: tc = tsd_counter_gettsd();
72: tc->tc_value ++ ;
73: }
74:
75: int tsd_counter_getvalue()
76: {
77: struct tsd_counter *tc ;
78: tc = tsd_counter_gettsd();
79: return( tc->tc_value );
80: }
----------------------------------------------------------------------
TSD 利用のパタン
- TSD として必要なデータを、構造体にまとめる。key や
pthread_getspecific() の呼出しを節約するため。
- pthread_key_t 型の変数を用意する。
pthread_key_create() で
初期化する。確実に一度だけ初期化するために、pthread_once()を使
う。
- スレッド固有データを使う関数では、最初に
pthread_getspecific() でポインタを得る。
- ポインタが 0 なら、
malloc() して、初期化して、
pthread_setspecific() で登録する。
pthread_key_delete() は、普通、使われない。ダイナミック・リンク
のモジュールを unload する時に必要になる（かもしれない）。
----------------------------------------------------------------------
1:
2: /*
3: * tsd-counter-main.c
4: * $Header: /home/hlla/yas/cvs/sie-pdsoft-2000-examples/tsd-counter-main.c,v 1.1 2001/01/08 00:14:21 yas Exp $
5: * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/tsd-counter-main.c
6: * Start: 2001/01/08 08:51:25
7: */
8:
9: #include <pthread.h>
10:
11: void thread1( int x );
12: void thread2( int x );
13:
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: pthread_create( &t1, NULL, (void *)thread1, (void *)10 );
23: pthread_create( &t2, NULL, (void *)thread2, (void *)20 );
24: printf("main()\n");
25: pthread_join( t1, NULL );
26: pthread_join( t2, NULL );
27: }
28:
29: void thread1( int x )
30: {
31: int i ;
32: tsd_counter_reset( x );
33: printf("thread1(): value=%d \n", tsd_counter_getvalue() );
34: for( i = 0 ; i<3 ; i++ )
35: {
36: tsd_counter_up();
37: printf("thread1(): value=%d \n", tsd_counter_getvalue() );
38: }
39: }
40:
41: void thread2( int x )
42: {
43: int i ;
44: tsd_counter_reset( x );
45: printf("thread1(): value=%d \n", tsd_counter_getvalue() );
46: for( i = 0 ; i<3 ; i++ )
47: {
48: tsd_counter_up();
49: printf("thread2(): value=%d \n", tsd_counter_getvalue() );
50: }
51: }
----------------------------------------------------------------------
実行例。
----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/tsd-counter.c ![[←]](../icons/screen-return.gif)
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/tsd-counter-main.c
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/Makefile
% make tsd-counter-main
gcc -D_REENTRANT -g -mcpu=v8 -c tsd-counter-main.c -o tsd-counter-main.o
gcc -D_REENTRANT -g -mcpu=v8 -c tsd-counter.c -o tsd-counter.o
gcc -D_REENTRANT -g -mcpu=v8 -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
% ![[]](../icons/screen-cursor.gif)
----------------------------------------------------------------------
スレッド固有データの特徴
- 使い方が簡単。競合がおきない。デットロックの心配がない。
- 思ったほど遅くはない。pthread_mutex_lock()/pthread_mutex_unlock()
の２回の関数呼出しより速いくらい。非常に単純な（スピン）ロックよりは、
遅い。
- SMP でのスケーラビリティが高い。
ただし意味が違うので、mutex と相互に書き換えできないことがある。
プロセス全体のデータを扱うものは、mutex で書くかない。
Time Zoneなど。
スレッドごとに乱数生成器を持ってもいいのか。
再現性が必要か。mutex では、再現性はない。
１つのスレッドで１つの mutex を複数回ロックしたい。
- 使い勝手。相互に呼び出してもよい。
- 開いたモジュール。もう一度自分自身に戻ってくる。
◆標準mutexでのデットロック
export している関数の入口で lock, 出口 unlockを入れて、
スレッド・セーフなモジュールを作りたい。
export している関数が、他の export している関数を呼び出すと、デットロッ
クになる。
----------------------------------------------------------------------
1: /*
2: * mutex-reclock-normal.c
3: * $Header: /home/hlla/yas/cvs/sie-pdsoft-2000-examples/mutex-reclock-normal.c,v 1.1 2001/01/08 00:55:02 yas Exp $
4: * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/mutex-reclock-normal.c
5: * Start: 2001/01/08 09:41:11
6: */
7:
8: #include <pthread.h>
9:
10: void thread_A(), thread_B();
11: int shared_resource ;
12: pthread_mutex_t mutex1 ;
13:
14: deposit( int n )
15: {
16: pthread_mutex_lock( &mutex1 );
17: shared_resource += n ;
18: pthread_mutex_unlock( &mutex1 );
19: }
20:
21: add_interest()
22: {
23: int i ;
24: pthread_mutex_lock( &mutex1 );
25: i = shared_resource * 0.05 ;
26: deposit( i );
27: pthread_mutex_unlock( &mutex1 );
28: }
29:
30: main() {
31: pthread_t t1 ;
32: pthread_t t2 ;
33: shared_resource = 0 ;
34: shared_resource = 1000000 ;
35: pthread_mutex_init( &mutex1, NULL );
36:
37: pthread_create( &t1, NULL, (void *)thread_A, 0 );
38: pthread_create( &t2, NULL, (void *)thread_B, 0 );
39: pthread_join( t1, NULL );
40: pthread_join( t2, NULL );
41: printf("main(): shared_resource == %d\n", shared_resource );
42: }
43:
44: void thread_A()
45: {
46: printf("thread_A(): deposit( 10000 ) ... \n");
47: deposit( 10000 );
48: printf("thread_A(): deposit( 10000 ) done. \n");
49: }
50:
51: void thread_B()
52: {
53: printf("thread_B(): add_interest() ... \n");
54: add_interest();
55: printf("thread_B(): add_interest() done. \n");
56: }
----------------------------------------------------------------------
実行例。
----------------------------------------------------------------------
% make mutex-reclock-normal
gcc -D_REENTRANT -g -mcpu=v8 -c mutex-reclock-normal.c -o mutex-reclock-normal.o
gcc -D_REENTRANT mutex-reclock-normal.o -lpthread -lrt -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: * $Header: /home/hlla/yas/cvs/sie-pdsoft-2000-examples/mutex-reclock-recursive.c,v 1.1 2001/01/08 00:55:02 yas Exp $
4: * http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2000/examples/mutex-reclock-recursive.c
5: * Start: 2001/01/08 09:41:11
6: */
...
30: static int
31: my_pthread_mutex_init_recursive( pthread_mutex_t *mutex )
32: {
33: pthread_mutexattr_t attr ;
34: int err ;
35: if( (err=pthread_mutexattr_init( &attr )) < 0 )
36: return( 0 );
37: if( (err=pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_RECURSIVE)) <0 )
38: return( 0 );
39: err = pthread_mutex_init( mutex,&attr );
40: return( err );
41: }
42:
43: main()
44: {
45: pthread_t t1 ;
46: pthread_t t2 ;
47: shared_resource = 0 ;
48: shared_resource = 1000000 ;
49: my_pthread_mutex_init_recursive( &mutex1 );
50:
51: pthread_create( &t1, NULL, (void *)thread_A, 0 );
52: pthread_create( &t2, NULL, (void *)thread_B, 0 );
53: pthread_join( t1, NULL );
54: pthread_join( t2, NULL );
55: printf("main(): shared_resource == %d\n", shared_resource );
56: }
...
----------------------------------------------------------------------
実行例。
----------------------------------------------------------------------
% 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
%
----------------------------------------------------------------------
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);
プログラミング言語レベルでの支援。
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
利点
- ロックの解除し忘れがない。goto文なしのプログラムに相当。
- 再帰の禁止、他のモニタの呼出しの禁止ができる。
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 相当。
１つのスレッドが２度同じオブジェクトをロックしてもよい。
Pthreads のプログラムで、１つの mutex と１つの条件変数を使ったものなら、
Java で簡単に書き直せる。
循環バッファのプログラムは、１つの mutex で２つの条件変数を使っている
ので、単純には Java で書き直せない。
Java で書かれたスレッドのプログラムは、汚いものがけっこうある。スレッ
ド「間」の同期で、対称系になるべき所を、片方のスレッドのメソッドにして、
非対称になっていることがある。Java でプログラムを書く時にも、active
object (thread) と passive object (threadなし)をきちんと分けた方がよい。
基本的には、スレッドのプログラムでUnix のシグナル(ソフトウェア割込みの
扱い)を使ってはいけない。
マルチスレッドは、ソフトウェア割込みを、より使いやすいものに置き換える
ためのもの。
シグナルは、SIGKILL や SIGSTOP などプロセス全体を操作するためだ
けに使うべきである。
どうしても必要な時：
- 全スレッドで
pthread_sigmask()を使ってマスクする。
-
sigwait(), sigtimewait()を呼び出すよ
うなシグナルを待つ専用のスレッドを作る。
マルチスレッドでは fork() の意味が不明
- 内部のスレッドも全部コピーされる
- 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 );
----------------------------------------------------------------------
◆４条件
- 相互排除。
- 待機。
- 横取り不能。
- 循環待機。
◆対策
- 防止(prevention)。ドットロックがいっさい起きないようにシステムを設計する。
- 回避(avoidance)。防止よりも資源の使用効率を高めようとする。資源の要求があった
時に、安全な時に鍵って割り当てる。銀行家アルゴリズム。
- 検出(detection)。
- 無策(crash)。
◆防止策
防止するには、４条件のどれか１つ（最初以外）を成り立たなくする。
- （なし）
- プロセスが必要な資源を一度に要求する。全てが許可されるまで進まない。
- 資源の要求が受け付けられなかった時には、持っている資源を一度解放して、
最初から取り直す。
- 資源の種類によって線形に順序を付け、その順序に従って
しか資源を要求できない。
解決方法(1): 複数の mutex をロックする時に順序を決める。
上の場合、どのスレッドも mutex1, mutex2 の
順でロックを行なうと、デッドロックは起こらない。
解決方法(2): だめな時には最初からやりなおす。
pthread_mutex_trylock() を使って、失敗したら全部をアンロッ
クして最初からやり直す。
ライブロックの危険性がある。
- スケジューリング、優先度
- スレッドの消去(取消し(cancel))
- スレッドやmutexの属性
- 1回だけの初期化
- リアルタイム・スケジュール、優先度継承
★Javaへの書き直し
循環バッファのプログラムを Java で書き直しなさい。
★mutexでのセマフォの実現
mutexを使ってセマフォを実現しなさい。
Java で利用可能なセマフォを実現しなさい。
次の課題から１つを選んで提出しなさい。問題を難しい方に変えてもよい。締
め切りは、2001/02/07 (水曜日) 18:00 とする。(23:59:59 ではない)。
レポートは、次のような形式の電子メールで送ること。
----------------------------------------------------------------------
To: yas@is.tsukuba.ac.jp
Subject: [pdsoft/report-thread-3] ＜内容に関したサブジェクト＞
学籍番号 000000 (各自の学籍番号で置き換える)
名前 漢字の名前
＜本文＞
----------------------------------------------------------------------
＜内容＞
前々回の注意事項も参照のこと。
★TSDによるスレッド・セーフな関数
次のライブラリ関数は、static 変数に結果を保存して返すので、スレッド・
セーフではない。
getlogin() readdir() strtok() asctime() ctime() gmtime() localtime()
rand() getgrgi() getgrnam() getpwuid() getpwnam()
これらのライブラリ関数を、スレッド固有データを使うように修正しなさい。
この時、引数の数と型、結果の型は、スレッド・セーフでないものと同じにな
るようにしなさい。ただし、名前には、_tsd というサフィックスを付け、ス
レッド・セーフではないものと区別すること。実現では、それぞれのリエント
ラント版を使ってもよい。たとえば、getlogin_tsd() の実現において、
getlogin_r() を使ってよい。
実現した関数と、mutex を使う方法との性能を比較しなさい。
★読み書きロックの利用
銀行口座として、普通口座と定期口座の２つの口座を考える。その２つの口座
の総合残高を返す手続きを、読み書きロックを使って書きなさい。総合残高以
外にも、それぞれの口座は、単独に預入、引出しができるようにすること。
★デットロックの回避
２つの銀行口座の間で、デットロックが起きないように預金を移動させる手続
きを実現しなさい。
↑[もどる]
[1月18日]
[1月25日]
[2月1日]
Last updated: 2001/02/01 00:08:41
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>