マルチスレッド・プログラミング(2)/ Multithread programming (2)

並行システム

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

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

■重要項目

■一貫性モデル consistency models

◆複製(replication)

コピーを作る。making copies.

目的 objectives

元とコピーが非対称なら、キャッシング、対称的なら、複製と言うことが多い。

◆共有メモリ型マルチプロセッサ、SMP (Shared memory multiprocessor)

(CPU+Cache)*n+メ
モリ

図? 共有メモリ型マルチプロセッサ(バス共有) (Shared memory multiprocessor (with a shared bus))

int x;

Thread1() {
    x = 1;
    ...
    printf("%d,",x);
}

Thread2() {
    x = 2;
    ...
    printf("%d,",x);
}

Thread3() {
    x = 3;
    ...
    printf("%d,",x);
}
可能性がある表示例。

◆一貫性モデル(consistency model)

プロセスとメモリ(データの入れ物)の関わり方。

プロセスが、あるアクセスの仕方を守れば、メモリは「正しく」動作する ことを保証する。

制限が少ないと、遅くなる。使える範囲でいかに手を抜く(コストを下げる) かが大事になる。

以下で「メモリ」は、data store の意味で使う。変数(variable)かもしれない し、ファイル(file)かもしれないし、ページ(page)かもしれない。

メモリがページで、プロセスがプロセッサなら、分散共有メモリ(distributed shared memory,DSM)という。

◆NFSでのメールの紛失事件

2017年10月上旬の事件

メールサーバの /var/mail を、別のクライアントホストでマウントして いる。 ファイルの属性のキャッシュは無効化(有効期限が0)している。ファイルの本体 のキャッシュの動作がおかしいように見える。

ファイルのロックは、動作している。(分散システムでのロックの実装は非常に 難しい。実際に限界がある。授業の後半で説明する。)

事件の経過

  1. クライアントで、/var/mail/yas を、ロックなしでアクセス。 (簡易的な from コマンドで)
  2. クライアントのカーネルは、/var/mail/yas のファイル本体と属性を、サー バから取り寄せ、メモリにキャッシュする。
  3. メールサーバでメールが届く。/var/mail/yas が更新される。(クライア ントの /var/mail/yas のファイル本体と属性のキャッシュが古くなる。)
  4. クライアントのメール・リーダが、/var/mail/yas をロック付きでアクセ スする。
  5. クライアントのカーネルは、/var/mail/yas のファイル属性を再取得する。 ファイルのサイズが増加していることがわかる。 しかし、クライアントのカーネルは、ファイル本体のキャッシュを無効化 していないように見える。ファイルが増大した分は、0 で埋めている。
  6. クライアントのメールリーダは、0 で埋められたファイルを受け取る。
この推測が正しければ、クライアント側のカーネルのバグ。 ロック付きでアクセスしたとしても、問題が生じる可能性もある。 ロック付きでアクセスすれば問題は生じないというのが、今日の Pthread の話。

◆厳密一貫性(strict consistency)

あるメモリ x を読み出すと、そのメモリ x に対する最新の書込みの結果が返 される。

Thread1                Thread2

a=1;
a=2;
                       print(a);

厳密一貫性では、常に 2 がプリントされる。

厳密一貫性では、「最新」の定義で、ニュートン物理学での絶対的な時間が必 要になる。

3 m 離れたコンピュータでは、光の速さででも 10ns かかる。 a=2; と print(a); 差が 1ns 以内という要求なら、光の 10 倍の速度が必要になる。

           3 m
PC1   <------------->  PC2
P1                     P2
a=1;
a=2;
                       print(a);
P1、P2 はプロセス。

SMP(集中システム)ですら、キャッシュがあれば、厳密一貫性を実現することは 不可能 (it is impossible to implement strict consistency in an SMP with cache.)。

救い:実際の応用では、そこまで要求されていない。

◆弱一貫性(weak consistency)

同期(synchronization)に着目する。際どい部分(critical section)から抜けた 時に、そのプロセス上の全書込みが他のプロセスに知らされ、他のプロセスの 全書込みが、そのプロセスから見えるようになる。

◆リリース一貫性(release consistency)

同期を2種類に分類する。 Acquire と Release の間にだけ、共有変数(保護されたた共有変数)の一貫 性が保たれる。

◆エントリ一貫性(entry consistency)

同期変数(synchronization variable)と普通の変数を関連づける。 ある同期変数が Acquire されたら、関連している共有変数だけ 最新のものにする。

■Pthreadのメモリ可視性 / Memory visibility in Pthread

スレッド T1 で 変数 x に write し、スレッド T2 で 変数 x を read したら 何が起きるのか。

◆Pthreadの操作 Pthread operations

◆表記方法 notation

W(x)a
メモリ x に a を書込む。write a into memory x.
R(y)b
メモリ y から読込んだ結果、b が得られた。read memory y and got b.
P1, P2, ...
プロセス P1 による実行, P2 による実行, ...
メモリの初期値(initial value)は、0。

例:

    ---------------------------> time
T1: W(x)1 R(x)1
T2:             R(x)0    R(x)1

◆Pthreadのメモリ可視性の規則 / Memory visibility rules in Pthread

◆Pthreadのメモリ可視性の例(1)/ Pthread Memory Visibility Example (1)

例。時間軸は縦。
Thread1                          Thread2
pthread_mutex_lock(&mutex1);
                                 pthread_mutex_lock(&mutex1);
varabileA = 1;
varabileB = 2;
pthread_mutex_unlock(&mutex1);
                                 localA = varabileA; // 1
                                 localB = varabileB; // 2
                                 pthread_mutex_unlock(&mutex1);
Thread2は、Thread1と同じ値を見る。 A=1, B=2。

◆Pthreadのメモリ可視性の例(2)/ Pthread Memory Visibility Example (2)

Thread1                          Thread2
pthread_mutex_lock(&mutex1);
                                 pthread_mutex_lock(&mutex1);
varabileA = 1;
pthread_mutex_unlock(&mutex1);
varabileB = 2;
                                 localA = varabileA; // 1
                                 localB = varabileB; // ?
                                 pthread_mutex_unlock(&mutex1);
Thread2は、Thread1と同じ値を見ないことがある。 Thread2では、A=1だが、Bは2ではないかもしれない。

◆Pthreadのメモリ可視性の例(3)/ Pthread Memory Visibility Example (3)

Thread1                          Thread2

                                 int need_spining=1;
                                 while(need_spining)
                                     continue;
need_spining=0;
Thread2は、いつまでたってもループしているかもしれない。 コンパイラが無限ループのコードを出すことがある。 The compiler can emit infinite loop code.

◆Pthreadのメモリ可視性の例(4)/ Pthread Memory Visibility Example (4)

Thread1                          Thread2

                                 volatile int need_spining=1;
                                 while(need_spining)
                                     continue;
need_spining=0;
コンパイラが無限ループのコードを出さない。 毎回、メモリから読む。 しかし、同期がないので、危ない。 While the compiler does not emit infinite loop code, it is unsafe because no synchronization primitive is used.

◆メモリへの到達順 order of memory access

他のスレッドが見えるかどうかとは別の話。単一スレッドでも、メモリに到着 する順番が変わるかもしれない。
A=1;
B=2;
メモリには、A, B の順に届くとは限らない。 メモリ・バリア(memory barrier)、または、メモリ・フェンス (memory fence) という特別な命令を使って、mutex のlock や unlock を実装する。

x86 の例

これらの命令は、Pthread ライブラリの実装で使われているので、普通の開発 者は直接使わなくてもよい。普通の開発者は、lock や cond_wait 等のプリミ ティブを呼び出せば良い。

◆Java言語のメモリ可視性、その他

基本的には、Pthread と同じ。synchronized を挟まないと、何がおきるかかわ らない。

■Ad Hoc Synchronization

スレッド間の同期 thread synchronization
普通の同期 normal synchronization
Mutex lock/unlock や 条件変数(condition variables) の wait/signal 等の POSIX スレッドライブラリや独自のインタフェースにあるプリミティブを 直接呼ぶ。 Directly calling some primitives such as "lock/unlock" and "cond wait/cond signal" from standard POSIX thread libraries or using customized interfaces implemented by programmers themselves.
Ad hoc synchronization
その他. Others.
Ad hoc synchronization は、普通、loop を含む。

◆参考文献 references

Weiwei Xiong, Soyeon Park, Jiaqi Zhang, Yuanyuan Zhou, Zhiqiang Ma: "Ad Hoc Synchronization Considered Harmful", 9th USENIX Symposium on Operating Systems Design and Implementation, 2010.

https://www.usenix.org/legacy/event/osdi10/tech/

◆例 examples

PDF、スライドも参照。

ad hoc sync in MySQL Mozilla OpenLDAP

図? ad hoc 同期の例

◆バグ bugs

◆ad hoc 同期を条件変数を使ったものに書き換える / replacing ad hoc synchronizations with synchronization primitives using condition variables

ad hoc sync in MySQL Mozilla OpenLDAP

図? ad hoc 同期を条件変数を使ったものに書き換える

◆Ad hoc を使うな / do not use ad hoc synchronization

新城コメント。Ad hoc を使うな。きちんとした mutex, 条件変数を使え。

■プロセスのアドレス空間/ Address space of process

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

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

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

◆テキストセグメント(text segment)

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

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

◆データセグメント(data segment)

データ・セグメント ( data segment, ) は、データを置く領域である. C言語の 静的変数(static)大域変数(extern) malloc() で割り当てたヒープ上の変数は、 このセグメントに置かれる。 ( 自動変数(auto) は、次のスタック・セグメントに置かれる。 ) データセグメントは, 次の3つにわかれている。
データ data
静的変数や大域変数のうち、初期値つき変数が置かれるところ
BSS
静的変数や大域変数のうち、初期値を指定しない(初期値が0)が置かれるところ
ヒープ(heap) malloc() で確保する変数が置かれるところ
データの初期値は、実行形式ファイルに含まれている。 例えばC言語で
static int x=100 ;
と書くと xはデータセグメントに割りつけられ, 実行形式ファイルに100という整数のビットパタンが含まれる。

BSSとは初期値を指定しない変数が置かれる場所である。 C言語で

static int y ;
と書くと yはBSSに割りつけられる。実行形式のファイルに は、BSSの領域はない。これは実行時にカーネルが領域を割り当て、内容 を0に初期化する。

ヒープとは実行時に大きさが決まる変数を置くための領域である。 C言語で

char *p ;
int size ;
    ...
    size = 100;
    p = malloc( size );
とすると100バイトの領域がヒープ上に確保される。

ヒープ領域の大きさは、brk() システム・コールや sbrk() システム・コールで変えることができる。これらの システム・コールは、malloc() ライブラリ関数から呼び出さ れる。(最近は、mmap() システム・コールが使われることが多い。)

◆スタックセグメント(stack segment)

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

C言語で次のように書くと、4バイトの領域がスタックセグメントに割りつけられる。

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

◆mainの引数と環境変数(arguments and environment variables)

Unixではプログラムを実行するときに, 引数(arguments)環境変数(environment variables) が渡される。 C言語では、次のようにmain()関数が3つの引数で呼び出される ようになっている。
main( int argc, char *argv[], *envp[] )
{

}
ここで、 argc が、引数の数(argvの数) , argv が、引数のベクタの先頭番地、 envp が環境変数のベクタの先頭番地である。この引数と環境変数は、スタックセグ メントのスタックの底、 図? では上(アドレスが大きいところ)にある。

◆共有ライブラリ(shared library)

共有ライブラリは、ヒープとスタック・セグメントの間にある。 どの番地に割り当てられるかは、システムに依存する。 (図には書かれていない。)

◆変数の番地、メモリ・マップ/addresses of variables and memory map

   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: int main( int argc, char *argv[], char *envp[] )
  25: {
  26:     auto int x3 ;
  27:     auto char *x4p ;
  28: 
  29:         printf("&main    == %16p (text)\n",&main );
  30:         printf("&etext   == %16p (text)\n",(void *)get_etext() );
  31:         printf("&edata   == %16p (data)\n",(void *)get_edata() );
  32:         printf("&end     == %16p (data)\n",(void *)get_end() );
  33: 
  34:         printf("&argv[0] == %16p (stack)\n",&argv[0] );
  35:         printf(" argv[0] == %16p (stack)\n", argv[0] );
  36:         printf("&envp[0] == %16p (stack)\n",&envp[0] );
  37:         printf(" envp[0] == %16p (stack)\n", envp[0] );
  38: 
  39:         printf("&x1      == %16p (data)\n",&x1 );
  40:         printf("&x2      == %16p (bss)\n",&x2 );
  41:         printf("&x3      == %16p (stack)\n",&x3 );
  42:         printf("&x4p     == %16p (stack)\n",&x4p );
  43:         x4p = malloc( 10 );
  44:         printf("x4p      == %16p (heap)\n",x4p );
  45:         x4p = malloc( 10 );
  46:         printf("x4p      == %16p (heap)\n",x4p );
  47:         recursive( 3 );
  48:         return( 0 );
  49: }
  50: 
  51: void recursive( int n )
  52: {
  53:     int x5 ;
  54:         printf("&x5      == %16p (stack,%d)\n",&x5,n );
  55:         if( n<=0 )
  56:             return;
  57:         recursive( n-1 );
  58: }
実行例。macOS。
$ wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-12/ex/vaddr-print.c [←]
$ cc vaddr-print.c -o vaddr-print [←]
$ ./vaddr-print [←]
&main    ==      0x10f0dabe0 (text)
&etext   ==      0x100000dcd (text)
&edata   ==      0x10000103c (data)
&end     ==      0x100003000 (data)
&argv[0] ==   0x7fff50b25b00 (stack)
 argv[0] ==   0x7fff50b25c18 (stack)
&envp[0] ==   0x7fff50b25b10 (stack)
 envp[0] ==   0x7fff50b25c26 (stack)
&x1      ==      0x10f0db038 (data)
&x2      ==      0x10f0db03c (bss)
&x3      ==   0x7fff50b25ac4 (stack)
&x4p     ==   0x7fff50b25ab8 (stack)
x4p      ==   0x7ff0d9c03290 (heap)
x4p      ==   0x7ff0d9c032a0 (heap)
&x5      ==   0x7fff50b25a68 (stack,3)
&x5      ==   0x7fff50b25a48 (stack,2)
&x5      ==   0x7fff50b25a28 (stack,1)
&x5      ==   0x7fff50b25a08 (stack,0)
$ size vaddr-print [←]
__TEXT __DATA	__OBJC	others	dec	hex
4096   4096	0	4294971392	4294979584	100003000
$ otool -L ./vaddr-print [←]
./vaddr-print:
	/usr/lib/libSystem.B.dylib (compatibility version 1.0.0, current version 1226.10.1)
$ []
実行例。Linux。
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-12/ex/vaddr-print.c [←]
% cc vaddr-print.c -o vaddr-print [←]
$ ./vaddr-print [←]
&main    ==         0x40057d (text)
&etext   ==         0x4007ad (text)
&edata   ==         0x601040 (data)
&end     ==         0x601048 (data)
&argv[0] ==   0x7ffe93755248 (stack)
 argv[0] ==   0x7ffe9375650f (stack)
&envp[0] ==   0x7ffe93755258 (stack)
 envp[0] ==   0x7ffe9375651d (stack)
&x1      ==         0x60103c (data)
&x2      ==         0x601044 (bss)
&x3      ==   0x7ffe9375515c (stack)
&x4p     ==   0x7ffe93755150 (stack)
x4p      ==        0x1bb0010 (heap)
x4p      ==        0x1bb0030 (heap)
&x5      ==   0x7ffe9375511c (stack,3)
&x5      ==   0x7ffe937550ec (stack,2)
&x5      ==   0x7ffe937550bc (stack,1)
&x5      ==   0x7ffe9375508c (stack,0)
$ size vaddr-print [←]
   text    data     bss     dec     hex filename
   2088     560       8    2656     a60 vaddr-print
$ ldd vaddr-print [←]
        linux-vdso.so.1 =>  (0x00007fff335f2000)
        libc.so.6 => /lib64/libc.so.6 (0x00007f6ccea30000)
        /lib64/ld-linux-x86-64.so.2 (0x000055ead0d21000)
$ []
MacOSX では、動的リンク・ライブラリの種類は、otool -L で表示される。 Linux, Solaris 等では、ldd コマンドが使える。

■スレッド固有データ(Thread specific data)

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

◆変数の寿命とスコープ(lifetime and scope of variables)

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

f()
{
    int y ;
    static int z ;
}
種類 variables スコープ scope 寿命 lifetime
extern 外部変数 全プログラム global scope プログラムの実行開始から終了まで
auto 普通の局所変数 関数内 local その関数の実行中とそこから別の関数を呼んでいる間
staticな局所変数 関数内 local プログラムの実行開始から終了まで
static変数(関数の外に定義) 同一ファイル内 file プログラムの実行開始から終了まで
(C言語にはない) (いろいろ) various プログラムの終了後も残る(永続的) persistent
永続的の反対は揮発的。 以下で説明する「スレッド固有データ」の寿命は、スレッドの寿命と同じ。

◆大域変数、静的変数

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

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

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

◆スコープ

auto変数のスコープは、関数内。 (マルチキャストのプログラミングでは、 auto変数は、スレッド固有データ。)

auto変数以外で使えるスレッドごとのデータが必要になる。

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

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

◆例:tsd_counter

   1: 
   2: /*
   3:  * tsd-counter.c
   4:  */
   5: 
   6: #include <stdio.h>      /* stderr */
   7: #include <stdlib.h>     /* malloc() */
   8: #include <string.h>     /* memset() */
   9: #include <pthread.h>
  10: 
  11: struct tsd_counter 
  12: {
  13:         int tc_value ;
  14: };
  15: 
  16: static  pthread_key_t    tsd_counter_tsdkey ;
  17: 
  18: void
  19: tsd_counter_module_init()
  20: {
  21:         pthread_key_create( &tsd_counter_tsdkey,free );
  22: }
  23: 
  24: static struct tsd_counter *
  25: tsd_counter_alloc()
  26: {
  27:     struct tsd_counter *tc ;
  28: 
  29:         tc = malloc( sizeof(struct tsd_counter) );
  30:         if( tc == 0 )
  31:         {
  32:             fprintf(stderr,"no memory for struct tsd_counter\n");
  33:             exit( -1 );
  34:         }
  35:         memset( tc, 0, sizeof(struct tsd_counter) );
  36:         if( pthread_setspecific( tsd_counter_tsdkey, tc ) != 0 )
  37:         {
  38:             fprintf(stderr, "pthread_setspecific().\n");
  39:             exit( -1 );
  40:         }
  41:         return( tc );
  42: }
  43: 
  44: static struct tsd_counter *
  45: tsd_counter_gettsd()
  46: {
  47:     struct tsd_counter *tc ;
  48:         tc = pthread_getspecific( tsd_counter_tsdkey );
  49:         if( tc == 0 )
  50:         {
  51:             tc = tsd_counter_alloc();
  52:         }
  53:         return( tc );
  54: }
  55: 
  56: void tsd_counter_reset( int val )
  57: {
  58:     struct tsd_counter *tc ;
  59:         tc = tsd_counter_gettsd();
  60:         tc->tc_value = val ;
  61: }
  62: 
  63: void tsd_counter_up()
  64: {
  65:     struct tsd_counter *tc ;
  66:         tc = tsd_counter_gettsd();
  67:         tc->tc_value ++ ;
  68: }
  69: 
  70: int tsd_counter_getvalue()
  71: {
  72:     struct tsd_counter *tc ;
  73:         tc = tsd_counter_gettsd();
  74:         return( tc->tc_value );
  75: }
TSD 利用のパタン pthread_key_delete() は、普通、使われない。ダイナミック・リンク のモジュールを unload する時に必要になる(かもしれない)。
   1: 
   2: /*
   3:  * tsd-counter-main.c
   4:  */
   5: 
   6: #include <stdio.h> /* printf() */
   7: #include <pthread.h>
   8: 
   9: void thread1( long x );
  10: void thread2( long x );
  11: 
  12: extern void tsd_counter_module_init();
  13: extern void tsd_counter_reset( int val );
  14: extern void tsd_counter_up();
  15: extern int tsd_counter_getvalue();
  16: 
  17: int main()
  18: {
  19:     pthread_t t1 ;
  20:     pthread_t t2 ;
  21:         tsd_counter_module_init();
  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:         return( 0 );
  28: }
  29: 
  30: void thread1( long 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( long x )
  43: {
  44:     int i ;
  45:         tsd_counter_reset( x );
  46:         printf("thread2(): 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/cs/csys-2019/2019-07-12/ex/tsd-counter.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-12/ex/tsd-counter-main.c [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-12/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()
thread2(): value=20 
thread1(): value=11 
thread2(): value=21 
thread1(): value=12 
thread2(): value=22 
thread1(): value=13 
thread2(): value=23 
% []

◆スレッド固有データ vs. mutex/ thread-specific data vs. mutex

スレッド固有データの特徴 features of thread specific data

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

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

◆実行時特化による pthread_getspecific() のオーバヘッドの削減/Eliminating the overhead of pthread_getspecific() by runtime specialization

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

◆C11/C++11 Thread-Local Stoppage

Pthread thread-specific data は、コンパイラの支援がなくても使える。 Microsoft や Gcc 等で勝手に Thread-Local Storage の支援が始まる。 C11/C++11 で、Thread-Local Storage が標準化される。

参考: C++11 スレッドローカルストレージ

◆Java

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

ライブラリを実現する場合、自分自身では Runnable を implements する class を定義できないことがある。その時には、ThreadLocal クラスを使って、 Pthread と似たようなことをする。
Java Pthread
final pthread_once()
java.lang.ThreadLocal() pthread_key_create()
get() pthread_getspecific()
set() pthread_setspecific()
initialValue() -
(GC) pthread_key_delete()

◆Ruby

Thread クラスを継承してクラスを定義し、スレッドごとに new すれば、その オブジェクトが持っている変数はスレッド固有データになる。

ライブラリを実現する場合、自分自身では Thread クラスを継承した クラスを定義できないことがあ る。その時には、Thread クラスのメソッド [] を使って、 Pthread と似たようなことをする。
Ruby Pthread
(Giant VM lock(GVL) があるので不用) pthread_once()
なし。キーとして「:名前」でシンボルを使う。 pthread_key_create()
Thread#self[key] pthread_getspecific()
Thread#self[key]=val pthread_setspecific()
(GC) pthread_key_delete()
スレッド固有データで使うシンボルが、複数のモジュールで 衝突したら危ないように見える。

◆Python

threading.Thread クラスを継承してクラスを定義すれば、そのオブジェクトが 持っている変数はスレッド固有データである。

ライブラリを実現する場合、自分自身では threading.Thread クラスを継承し たクラスを定義できないことがある。その時には、threading.local() で得ら れたオブジェクトの属性が、スレッド固有データとして使える。
Python Pthread
(Global Interpreter Lock (GIL) があるので不用) pthread_once()
なし。キーとして threading.local() の属性名を使う。 pthread_key_create()
tsd=threading.local(); tsd.key pthread_getspecific()
tsd=threading.local(); tsd.key=value pthread_setspecific()
(GC) pthread_key_delete()
スレッド固有データで使うシ属性名が、複数のモジュールで 衝突したら危ないように見える。

■コルーチンとスレッド

◆サブルーチンとコルーチン

サブルーチン呼出しでは、メインルーチンが停止する。 コルーチンを作成すると、メインルーチンもコルーチンも同時に動作する。

メイン・ルーチンからサブルーチンの呼出し、2つのコルーチンの交互の実行

図? メイン・ルーチン、サブルーチンとコルーチン/ main routine, subroutine and coroutines

main() {
	int x;
	while( 1 ) {
		...
		subroutine();
		...
	}
}

subroutine() {
	int y;
	...
}
coroutine1() {
	int x;
	while( 1 ) {
		...
		yield();
		...
	}
}

coroutine2() {
	int x;
	while( 1 ) {
		...
		yield();
		...
	}
}

◆コルーチンの実行

複数のコルーチンを、複数の(OSレベルの)スレッドで動作させる実装が多い。

コルーチンをOSレベルのスレッドで実行する。スレッドは、CPUが実行する。

図? OSレベルのスレッドによるコルーチンの実行/Executing coroutines with OS-level threads.

◆コルーチンとスレッドの違い

コルーチン スレッド 軽さだけを求めて、スレッドをコルーチンに置き換えることは一般的にはでき ない。yield() のことを考えると、コルーチンは、スレッドより難しいことが ある。スレッド・プールにスレッドがあるうちは、yield() しなくても動く。 コルーチンを作りすぎたり、I/O等でOSに制御が移り、コルーチンを実行するス レッドが足りなくなると、危ない(yield()入れないと動かなくなる)。

◆プログラミング言語によるコルーチンのサポート

スクリプト言語で、 Giant VM lockGiant VM lock のようなロックを持ち、CPU レベルの並列処理ができないものは、 スレッドといっても、本質的にはコルーチンと同じ。 ただし、スレッドとは別により軽量のものとして fiber と呼んだりすることがある。

GNU Pth - The GNU Portable Threads は、API としては、Mutex や条件変数を持っているが、 内部の実装はコルーチンである。

次の言語のコルーチンは、OS レベルのスレッドで実行される。

■デッドロック deadlocks

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

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

pthread_mutex_t mutex1;
pthread_mutex_t mutex2;

thread_A()
{
    pthread_mutex_lock( &mutex1 );
    pthread_mutex_lock( &mutex2 );
    pthread_mutex_unlock( &mutex2 );  
    pthread_mutex_unlock( &mutex1 );  
}

thread_B()
{
    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 );

thread_A(),thread_B(),resource 1,resource 2,循環待機.

図? スレッド2個、資源2個で生じるデッドロック/ Deadlock with two threads and two resources.

◆4条件 four conditions

次の4つの条件が全て成り立つ時にデッドロックが起きる。 A deadlock situation can arise if the following four conditions hold simultaneously in a system:
  1. 相互排除 mutual excusion
  2. 待機 hold and wait
  3. 横取り不能 no preemption
  4. 循環待機 cirular wait

◆対策

◆防止策

防止するには、4条件のどれか1つ(最初以外)を成り立たなくする。
相互排除 mutual excusion
(なし)
待機 hold and wait
プロセスが必要な資源を一度に要求する。全てが許可されるまで進まない。
横取り不能 no preemption
資源の要求が受け付けられなかった時には、持っている資源を一度解放して、 最初から取り直す。
循環待機 cirular wait
資源の種類によって線形に順序を付け、その順序に従って しか資源を要求できない。

◆Pthreadでの対応策:防止

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

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

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

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

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

◆ライブロック(live lock)

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

◆トランザクション(transaction)

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);
  }
}
class Cell c1, c2;
c1 = Cell.new()
c2 = Cell.new()

....

thread_A()                                      thread_B()
...                                             ...
c1.swapValue(c2);                               c2.swapValue(c1);

c1のロックを得る。                                 c2のロックを取る。
acquire the lock of c1.                         aquire the lock of c2.

c2のロックを確保しようとして止まる。                c1のロックを確保しようとして止まる。
try to acquire the lock of c2 and block.        try to aquire the lock of c1 and block.

デッドロックを防止したコード:

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

■課題(assignment)3 マルチスレッド・プログラミング(2)/ Multithread programming (2)

次の内容を含む「テキスト」ファイルを作成し、 レポート提出ページ から提出しなさい。

以下の課題の「全て」に回答しなさい。 回答は、講義内容にそったものにしなさい。Wikipedia その他の信頼できない ソースから得た情報を回答しないこと。

Answer *all* the following questions. You should find answers from the contents of the class. You should not copy and paste the contents from untested sources, including Wikipedia.

締切りは、2019年7月16日、 23:59:59 とする。

★問題(301) ad hock synchronization

次のプログラムは、正しいプログラムである。これを、ad hock synchronization を使った 間違った プログラムに書直しなさい。 実行結果は、不要である。 The following program is a correct program. Rewrite this program to an incorrect program that uses ad hoc synchronization. No execution result is required.
thread_A()
{
	pthread_mutex_lock( mutex1 );
loop:	if( b->used == BUFFER_SIZE )
	{
	    pthread_cond_wait( condv1,mutex1 );
	    goto loop;
	}
	pthread_mutex_unlock( mutex1 );
}

thread_B()
{
	pthread_mutex_lock( mutex1 );
        b->used -- ;
	pthread_cond_broadcast( condv1 );
	pthread_mutex_unlock( mutex1 );
}

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

次の Java 言語のプログラムは、銀行口座を実現したものの一部である。空欄 「/*(a)*/」から「/*(i)*/」を埋めて、デッドロックが起きないように、口座 間で送金する手続き transfer() を完成させなさい。ただし、このプログラム では、残高が負になることを許すものとする。ただし、何も記述するべきでは ない欄には、「/**/」と記述しなさい。 実行結果は、不要である。

The following program in Java is a part of a bank account program in Java. Fill in the field "/*(a)*/" to "/*(i)*/" and complete the method transfer() that performs sends a given mount of money from one account to the other account. This program includes a deadlock avoidance technique. Note that this program allows negative balance for simplicity. Some fields /*(?)*/ should be empty. In such fields, fill in "/**/". No execution result is required.

class BankAccount {
    long value;

    synchronized void deposit(long n) { value += n; }
    synchronized void withdraw(long n) { value -= n; }

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

Last updated: 2019/08/07 18:00:10
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>