マルチスレッド(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 モデル。概念的にには、粗な２次元配列。

tsd[thread_id][key];

pthread_key_create(): スレッド固有データのためのキーを生成する。プログラムの中で、固有データごとに一度だけ呼び出す。
pthread_setspecific(): スレッド固有データを設定する。スレッドごとに１度だけ呼び出す。
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 利用のパタン

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

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

使い方が簡単。競合がおきない。デットロックの心配がない。
思ったほど遅くはない。pthread_mutex_lock()/pthread_mutex_unlock() の２回の関数呼出しより速いくらい。非常に単純な（スピン）ロックよりは、遅い。
SMP でのスケーラビリティが高い。キャッシュがよく効く。

ただし意味が違うので、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

１つのスレッドで１つの 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

利点

ロックの解除し忘れがない。goto文なしのプログラムに相当。
再帰の禁止、他のモニタの呼出しの禁止ができる。

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

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

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

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

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

どうしても必要な時：

全スレッドでpthread_sigmask()を使ってマスクする。
sigwait(), sigtimewait()を呼び出すようなシグナルを待つ専用のスレッドを作る。

◆forkとexecの扱い

マルチスレッドでは 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)。

◆防止策

防止するには、４条件のどれか１つ（最初以外）を成り立たなくする。

（なし）
プロセスが必要な資源を一度に要求する。全てが許可されるまで進まない。
資源の要求が受け付けられなかった時には、持っている資源を一度解放して、最初から取り直す。
資源の種類によって線形に順序を付け、その順序に従ってしか資源を要求できない。

◆Pthreadでの対応策：防止

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

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

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

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

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

◆その他のPthreadの機能

スケジューリング、優先度
スレッドの消去(取消し(cancel))
スレッドやmutexの属性
1回だけの初期化
リアルタイム・スケジュール、優先度継承

◆トランザクション

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

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

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

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

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

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

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

歴史：１９６０年代、テープの時代。失敗したら、巻き戻す。

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

口座１から出金
口座２に入金

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

仮定

プロセスは、ランダムに故障する。
メッセージの紛失は、タイムアウトと再送で回復されている。

必要なもの

安定記憶(stable storage)。ディスク２台で作る。

リカバリ

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

Begin_Transaction
Commit (End Transaction)
Abort
Read
Write

◆特性(ACID)

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

◆直列化可能(serializable)

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

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

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

◆例

航空券の乗り継ぎの予約のプログラム

Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-JFK");
Commit();

プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的には、ロックは行われる（ことがある）。

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

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

目的

効率
プログラミングの容易さ

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

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

プライベート作業空間。書き換える前にコピーを作り、コピーを更新。
先行書き込みログ。更新作業をログに記録して、後で戻せる(rollback) ようにする。

◆プライベート作業空間

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

読み込みではコピーしない
ファイル全体だけではなく、インデックス(inode)だけをコピーする。シャドー・ブロック。

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

実行予定リスト(intentions list)

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

トランザクションの識別子
古い値
新しい値

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

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

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

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

２種類のプロセス

コーディネータ・プロセス、１つ
サブオーディネート（残りの関連するプロセス）。従属。

２つの相

第１相

全プロセスを Commit も Abort もできる状態にする。

コーディネータは、ログに「準備」と書く。
コーディネータは、サブオーディネートに「準備」メッセージを送る。
サブオーディネートは、ログに「準備完了」と書く。
サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
コーディネータは、全てのサブオーディネートからの応答を待つ。

第２相

実際に Commit する。

コーディネータは、ログに「コミット」と書く。
コーディネータは、サブオーディネートに「コミット」メッセージを送る。
サブオーディネートは、ログに「コミット完了」と書く。
サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
コーディネータは、全てのサブオーディネートからの応答を待つ。

クラッシュした時には、ログから回復させる。

◆並行性制御

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

ロッキング
楽観的並行性制御
タイムスタンプ

◆ロッキング

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

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

制約が強すぎる。

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

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

小さくする: 並列性が高まる。ロック自体のオーバヘッドが増える。デッドロックが起こりやすくなる。
大きくする: 逆

２相ロック：デッドロックが起きにくい、直列化可能な方法。

第１相(growing phase): ロックの数が増える一方
第２相: ロックの数が減る一方

定理：トランザクションの実現で２相ロックを使うならば、インターリーブされることで作られるスケジュールは直列化可能である。

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

利点

中間的な状態を外から見られることがない。無駄な計算が起きない。
連鎖アボート(cascaded abort)が起きない
デッドロックの検出に時間切れが使えることがある。

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

ロックの順番を決める
グラフのループを検出する
時間切れ

注意：２相ロックと２相コミットは別。

◆楽観的並行性制御

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

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

性質

デッドロックがおきない。
並列性が高い。
衝突して失敗する確率が高くなると辛い。

◆タイムスタンプ

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

前提：

Lamport のアルゴリズムでタイムスタンプが一意になっている。

アルゴリズム：

ファイルには、読み取りのタイムスタンプと書き込みのタイムスタンプが付けられる。
あるプロセスがファイルをアクセスする時、トランザクションのタイムスタンプとファイルのタイムスタンプを比較する。ファイルの方が古ければ、問題なし。
ファイルの方が新しければ、トランザクションをアボートする。

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

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

デッドロックの扱い

ダチョウ・アルゴリズム。(問題を無視する。)
検出。デッドロックを起させて、検出し、回復する。
予防。静的に構造的にデッドロックが起きないようにする。
回避。資源を注意深く配置することで回避する。銀行家アルゴリズム。

分散では、非常に難しい。回避は、無理。

◆検出

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

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

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

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

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

各マシンは、ローカルのプロセスの資源要求グラフを管理する。
コーディネータは、大域的なグラフを管理する。サイクルを検出すると、ドットロックと判定する。

情報の収集方法

各マシンが、変更（資源要求、資源確保）があると、コーディネータに通知する。
各マシンが、定期的に前回との差分をコーディネータに通知する。
コーディネータが各マシンに問い合わせる。

単純にやると、偽のデッドロックを検出する。

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

コーディネータがデッドロックを検出したように見えた時に、各マシンにその時刻より前のメッセージをフラッシュさせる。

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

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

プローブ・メッセージ：３つ組

ブロックしたプロセス
メッセージを送信しているプロセス
送信相手のプロセス

プロセスがブロックする時、プローブ・メッセージを送る。
メッセージを受け取ると、他のプロセスを待っていたら、第２、第３フィールドを書き換えて転送する。
メッセージが一巡してもどってきたら、デッドロック。

単純に最初のプロセスを殺す方法では、複数のプロセスが同時にこのアルゴリズムを起動すると問題になる。

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

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

◆分散デッドロック予防

もっとも代表的な方法：

全ての資源を順序づけし、順序どおりに確保させる

集中システムでも使われている。

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

プロセスが別のプロセスが保持している資源を要求してブロックしようとする時、タイムスタンプを比較する。
要求しているプロセスが古い時には、そのプロセスを待たせる。
要求しているプロセスが新しい時には、そのプロセスを殺す。（トランザクションで回復。）

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

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

プロセスが別のプロセスが保持している資源を要求してブロックしようとする時、タイムスタンプを比較する。
要求しているプロセスが古い時には、横取り(preempt)させ、資源を保持しているプロセスを殺す。（トランザクションで回復。）
要求しているプロセスが新しい時には、そのプロセスを待たせる。

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 を使う方法との性能を比較しなさい。

★読み書きロックの利用

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

★デットロックの回避

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

■課題

なし。再提出になっているものを 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>