マルチスレッド(3)

並列分散ソフトウェア

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

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

■今日の重要な話

■フィードバック

例題の quick sort を使って、最大値、最小値は再提出。いくら並列化して sort したとしても、線形に計算した方が速い。

■スレッド固有データ

◆大域変数、静的変数

シングルスレッド・プログラムをマルチスレッド・プログラムに変更しようと した時に 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:  * Start: 2001/01/08 08:51:25
   5:  */
   6: 
   7: #include <stdio.h>      /* stderr */
   8: #include <stdlib.h>     /* malloc() */
   9: #include <pthread.h>
  10: 
  11: struct tsd_counter 
  12: {
  13:         int tc_value ;
  14: };
  15: 
  16: static  pthread_once_t   tsd_counter_alloc_once = PTHREAD_ONCE_INIT ;
  17: static  pthread_key_t    tsd_counter_tsdkey ;
  18: 
  19: static void
  20: tsd_counter_tsdkey_init()
  21: {
  22:     extern void free(void *ptr);
  23:         pthread_key_create( &tsd_counter_tsdkey,free );
  24: }
  25: 
  26: static struct tsd_counter *
  27: tsd_counter_alloc()
  28: {
  29:     struct tsd_counter *tc ;
  30: 
  31:         pthread_once(&tsd_counter_alloc_once,tsd_counter_tsdkey_init);
  32:         tc = malloc( sizeof(struct tsd_counter) );
  33:         if( tc == 0 )
  34:         {
  35:             fprintf(stderr,"no memory for struct tsd_counter\n");
  36:             exit( -1 );
  37:         }
  38:         memset( tc, 0, sizeof(struct tsd_counter) );
  39:         if( pthread_setspecific( tsd_counter_tsdkey, tc ) != 0 )
  40:         {
  41:             fprintf(stderr, "pthread_setspecific().\n");
  42:             exit( -1 );
  43:         }
  44:         return( tc );
  45: }
  46: 
  47: static struct tsd_counter *
  48: tsd_counter_gettsd()
  49: {
  50:     struct tsd_counter *tc ;
  51:         tc = pthread_getspecific( tsd_counter_tsdkey );
  52:         if( tc == 0 )
  53:         {
  54:             tc = tsd_counter_alloc();
  55:         }
  56:         return( tc );
  57: }
  58: 
  59: void tsd_counter_reset( int val )
  60: {
  61:     struct tsd_counter *tc ;
  62:         tc = tsd_counter_gettsd();
  63:         tc->tc_value = val ;
  64: }
  65: 
  66: void tsd_counter_up()
  67: {
  68:     struct tsd_counter *tc ;
  69:         tc = tsd_counter_gettsd();
  70:         tc->tc_value ++ ;
  71: }
  72: 
  73: int tsd_counter_getvalue()
  74: {
  75:     struct tsd_counter *tc ;
  76:         tc = tsd_counter_gettsd();
  77:         return( tc->tc_value );
  78: }
----------------------------------------------------------------------

TSD 利用のパタン pthread_key_delete() は、普通、使われない。ダイナミック・リンク のモジュールを unload する時に必要になる(かもしれない)。

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

実行例。

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/tsd-counter.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/tsd-counter-main.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/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 を自分で定義し、かつ、スレッドごとに 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()
----------------------------------------------------------------------

■再帰的 mutex

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

開いたモジュールでは一度外にだたスレッドがもう一度入ってくる。

図? 開いたモジュールと閉じたモジュール

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

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

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

実行例。

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/mutex-reclock-normal.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/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:  * Start: 2001/01/08 09:41:11
   4:  */
...
  28: static int
  29: my_pthread_mutex_init_recursive( pthread_mutex_t *mutex )
  30: {
  31:     pthread_mutexattr_t attr ;
  32:     int err ;
  33:         if( (err=pthread_mutexattr_init( &attr )) < 0 )
  34:             return( 0 );
  35:         if( (err=pthread_mutexattr_settype(&attr,PTHREAD_MUTEX_RECURSIVE)) <0 )
  36:             return( 0 );
  37:         err = pthread_mutex_init( mutex,&attr );
  38:         return( err );
  39: }
  40: 
  41: main()
  42: {
  43:     pthread_t t1 ;
  44:     pthread_t t2 ;
  45:         shared_resource = 1000000 ;
  46:         my_pthread_mutex_init_recursive( &mutex1 );
  47: 
  48:         pthread_create( &t1, NULL, (void *)thread_A, 0 );
  49:         pthread_create( &t2, NULL, (void *)thread_B, 0 );
  50:         pthread_join( t1, NULL );
  51:         pthread_join( t2, NULL );
  52:         printf("main(): shared_resource == %d\n", shared_resource );
  53: }
...
----------------------------------------------------------------------

実行例。deposit() と add_interest() のタイミングによっては、最終結果は 違うことがある。

----------------------------------------------------------------------
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/mutex-reclock-recursive.c [←]
% wget http://www.hlla.is.tsukuba.ac.jp/~yas/sie/pdsoft-2003/2004-01-22/ex/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のロックを取る必要がある時には、デッドロックに気を付ける。

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


----------------------------------------------------------------------
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の機能

◆トランザクション

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

■アトミック・トランザクション

相互排除、デッドロックより高いレベルの抽象が欲しい。

ロックよりも楽にプログラムを作りたい。

特に分散では。集中でも、フォールト・トレランスの実現では必要。

◆トランザクションの意味

商談は、成立するか、しないか。 all or nothing。

歴史:1960年代、テープの時代。 失敗したら、巻き戻す。

銀行口座間の預金の移動。

  1. 口座1から出金
  2. 口座2に入金

◆トランザクション・モデル

仮定 必要なもの リカバリ

◆トランザクション・プリミティブ

◆特性(ACID)

Atomic
外の世界からみると1つ。中間状態が見えない。不可分。
Consistency
不変量(invariant)を保つ。例:口座間の預金の移動。預金の総額は不変。
Isolated
並行するトランザクションは、孤立している。直列化可能(serializable)
Durable
Commit すると永続的。

◆直列化可能(serializable)

注意:Javaの serializable とは意味が全く違う。

複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で逐次的に実行した時と同じ結果 になる。

逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。

◆例

航空券の乗り継ぎの予約のプログラム
Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-JFK");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的 には、ロックは行われる(ことがある)。

途中の reserve() が失敗したら、トランザクション全体を abort() する。

◆入れ子トランザクション(nested transactoin)

目的 親が abort されたら、子供が commit したものも無効になる。

◆トランザクションの実装(集中)

◆プライベート作業空間

全てのデータをコピーすると重たい。

◆先行書き込みログ(write-ahead log)

実行予定リスト(intentions list)

シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶に書き込む。

コミットされると、何もしない。 アボートされると、ログを後ろから前に読み込み undo する。

クラッシュからの回復もできる。

◆トランザクションの実装(分散)

二相コミット(two-phase commit)(二相ロック(two-phase lock)ではない)。

2種類のプロセス

2つの相
第1相
全プロセスを Commit も Abort もできる状態にする。
  1. コーディネータは、ログに「準備」と書く。
  2. コーディネータは、サブオーディネートに「準備」メッセージを送る。
  3. サブオーディネートは、ログに「準備完了」と書く。
  4. サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
第2相
実際に Commit する。
  1. コーディネータは、ログに「コミット」と書く。
  2. コーディネータは、サブオーディネートに「コミット」メッセージを送る。
  3. サブオーディネートは、ログに「コミット完了」と書く。
  4. サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
クラッシュした時には、ログから回復させる。

◆並行性制御

できるだけ効率のよい、直列化可能なスケジューリングを求める。

◆ロッキング

もっとも単純な方法: Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。

注意:プログラマは、ロックを意識しない。

制約が強すぎる。

読み取りロック:read lock と write lock を分ける。

ロックの粒度(granularity)が大事

小さくする
並列性が高まる。ロック自体のオーバヘッドが増える。 デッドロックが起こりやすくなる。
大きくする
2相ロック:デッドロックが起きにくい、直列化可能な方法。
第1相(growing phase)
ロックの数が増える一方
第2相
ロックの数が減る一方
定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。

実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。 第2相で、まとめて全部ロックを解放する(strict two-phase locking)。

利点

2相ロックでも、デッドロックは起きる。

注意:2相ロックと2相コミットは別。

◆楽観的並行性制御

どんどんやって、後でまずかったことがわかつた時点で abort する。 衝突が稀である時に有効。

実現(衝突時の対応):プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。

性質

◆タイムスタンプ

操作にタイムスタンプを付けて、まずいものをアボートする。

前提:

アルゴリズム: 楽観的:同じファイルを独立したトランザクションで同時にアクセスすること は、あまりない。

◆長期トランザクション

直列化可能性という制限はきつすぎる。

■分散システムにおけるデッドロック

デッドロックの扱い 分散では、非常に難しい。回避は、無理。

◆検出

検出して、プロセスを kill する。

kill では済まないものもある。

トランザクションが使える場合には、回復は単に abort すればよい。

◆集中型検出アルゴリズム

集中型のアルゴリズムを、コーディネータを使って模倣する。

情報の収集方法 単純にやると、偽のデッドロックを検出する。

対策:タイムスタンプを使う。

◆分散型検出アルゴリズム

プロセスがブロックする時に起動される。

プローブ・メッセージ:3つ組

  1. プロセスがブロックする時、プローブ・メッセージを送る。
  2. メッセージを受け取ると、他のプロセスを待っていたら、第2、第3フィー ルドを書き換えて転送する。
  3. メッセージが一巡してもどってきたら、デッドロック。
単純に最初のプロセスを殺す方法では、複数のプロセスが同時にこのアルゴリ ズムを起動すると問題になる。

改良:プローブメッセージに待っているプロセスのリストを付ける。 リストの中で犠牲となるプロセスを一意に決める。

理論的には、改善の余地が大きい。

◆分散デッドロック予防

もっとも代表的な方法: 集中システムでも使われている。

大域的な時間とトランザクションを利用した方法(1):待機消滅(wait-die)型 アルゴリズム

トランザクションの時刻の増加方向にしか延びない。

大域的な時間とトランザクションを利用した方法(2):負傷待機(wound-wait) 型アルゴリズム

wait-die型アルゴリズムでは、若者は繰り返し死ぬことがある。

■練習問題

★mutexでのセマフォの実現

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

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

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

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

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

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

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

★読み書きロックの利用

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

★デットロックの回避

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

■課題

なし。再提出になっているものを 2004/1/28 (水曜日) 18:00 までに提出する。(23:59:59 ではない)。
↑[もどる] ←[1月15日] ・[1月22日] →[1月29日]
Last updated: 2004/01/22 04:59:11
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>