並行システム
システム情報系/情報工学域,
システム情報工学研究群/情報理工学位プログラム
システム情報工学研究科/コンピュータサイエンス専攻
新城 靖
<yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
https://www.cs.tsukuba.ac.jp/~yas/cs/csys-2025/2025-05-02
あるいは、次のページから手繰っていくこともできます。
https://www.cs.tsukuba.ac.jp/~yas/cs/
https://www.cs.tsukuba.ac.jp/~yas/
目的 objectives
図? 共有メモリ型マルチプロセッサ(バス共有) (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);
}
可能性がある表示例。
プロセスが、あるアクセスの仕方を守れば、メモリは「正しく」動作する ことを保証する。
制限が少ないと、遅くなる。使える範囲でいかに手を抜く（コストを下げる） かが大事になる。
以下で「メモリ」は、data store の意味で使う。変数(variable)かもしれない し、ファイル(file)かもしれないし、ページ(page)かもしれない。
メモリがページで、プロセスがプロセッサなら、分散共有メモリ(distributed shared memory,DSM)という。
メールサーバの /var/mail を、別のクライアントホストでマウントして いる。 ファイルの属性のキャッシュは無効化(有効期限が0)している。ファイルの本体 のキャッシュの動作がおかしいように見える。
ファイルのロックは、動作している。(分散システムでのロックの実装は非常に 難しい。実際に限界がある。授業の後半で説明する。)
事件の経過
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.)。
救い：実際の応用では、そこまで要求されていない。
例:
---------------------------> time
T1: W(x)1 R(x)1
T2: R(x)0 R(x)1
int x;
T1() {
x = 1
print(x); // 1
}
T2() {
print(x); // 0
...
print(x); // 1
}
T1: R(x)1 pthread_create(T2) T2開始: R(x)1pthread_create() 後に書き込んだものは、新しいスレッドで読めなくてもよい。 たとえその書き込みが新しいスレッドの開始前であったとしても、新しいスレッドで読めなくても良い。
T1: R(x)1 pthread_create(T2) W(x)2 T2開始: R(x)1
T1: R(x)1 pthread_create(T2) W(x)2 T2開始: R(x)2
T1: R(x)1 unlock() T2: lock() R(x)1最初のスレッドが unlock 後にメモリが書かれた時、 別のスレッドが lock 後に読めなくても良い。
T1: unlock() W(x)1 T2: lock() R(x)0
T1: R(x)1 exit() T2: join() R(x)1終了後に書かれたものでも、join した時に見えなくてもよい。
T1: R(x)1 exit() T2: join() R(x)1 T3: W(x)2
T1: R(x)1 broadcast() T2: wait()から復帰 R(x)1起した後の書き込みは、見えなくてもよい。
T1: R(x)1 broadcast() W(x)2 T2: wait()から復帰 R(x)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。
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ではないかもしれない。
Thread1 Thread2
int need_spining=1;
while(need_spining)
continue;
need_spining=0;
Thread2は、いつまでたってもループしているかもしれない。
コンパイラが無限ループのコードを出すことがある。
The compiler can emit infinite loop code.
Thread1 Thread2
volatile int need_spining=1;
while(need_spining)
continue;
need_spining=0;
コンパイラが無限ループのコードを出さない。
volatile があるので、毎回、メモリから読む。
しかし、同期がないので、危ない。
While the compiler does not emit infinite loop code,
it is unsafe because no synchronization primitive is used.
A=1; B=2;メモリには、A, B の順に届くとは限らない。
x86 の例
https://www.usenix.org/legacy/event/osdi10/tech/
図? ad hoc 同期の例
図? ad hoc 同期を条件変数を使ったものに書き換える
図? プロセスのアドレス空間(単一スレッド)
機械語を書き換えながら実行するプログラムは、行儀が悪いとされてい る。キャッシュの関係で特別な操作をしないと動かない。
malloc() で割り当てたヒープ上の変数は、
このセグメントに置かれる。
(
自動変数(auto)
は、次のスタック・セグメントに置かれる。
)
データセグメントは, 次の3つにわかれている。
malloc() で確保する変数が置かれるところ
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() システム・コールが使われることが多い。)
C言語で次のように書くと、4バイトの領域がスタックセグメントに割りつけられる。
main()
{
auto int z;
}
autoというキーワードは、普通省略される。
main()
{
int z;
}
スタックセグメントは、普通、0xffffffff (32ビットのアドレス空間の場合)か
らからアドレスが小さくなるほうに向かって伸びていく。この部分は、関数呼
び出しが続くと伸びていき、割り当てられたメモリよりも多くなると、カーネ
ルが自動的に拡張する。
main()関数が3つの引数で呼び出される
ようになっている。
main( int argc, char *argv[], *envp[] )
{
}
ここで、
argc
が、引数の数(argvの数) ,
argv
が、引数のベクタの先頭番地、
envp
が環境変数のベクタの先頭番地である。この引数と環境変数は、スタックセグ
メントのスタックの底、
図?
では上(アドレスが大きいところ)にある。
int x;
f()
{
int y ;
static int z ;
}
| 種類 variables | スコープ scope | 寿命 lifetime |
|---|---|---|
| extern 外部変数 | 全プログラム global scope | プログラムの実行開始から終了まで |
| auto 普通の局所変数 | 関数内 local | その関数の実行中とそこから別の関数を呼んでいる間 |
| staticな局所変数 | 関数内 local | プログラムの実行開始から終了まで |
| static変数(関数の外に定義) | 同一ファイル内 file | プログラムの実行開始から終了まで |
| (C言語にはない) | (いろいろ) various | プログラムの終了後も残る(永続的) persistent |
auto変数のスコープは、関数内。 (マルチスレッドのプログラミングでは、 auto変数は、スレッド固有データ。)
auto変数以外で使えるスレッドごとのデータが必要になる。
tsd[thread_id][key];
pthread_key_create()
pthread_setspecific()
pthread_getspecific()
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_getspecific() の呼出しを節約するため。
pthread_key_create() で初
期化する。確実に一度だけ初期化するために、main() から初期化の関数を呼び
出すか、pthread_once()を使う。
pthread_getspecific() でポインタを得る。
malloc() して、初期化して、
pthread_setspecific() で登録する。
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-2025/2025-05-02/ex/tsd-counter.c ![[←]](../icons/screen-return.gif)
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2025/2025-05-02/ex/tsd-counter-main.c
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2025/2025-05-02/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
% ![[]](../icons/screen-cursor.gif)
スレッド固有データの特徴 features of thread specific data
ただし意味(semantics)が違うので、mutex と相互に書き換えできないことがある。 プロセス全体のデータ(global data)を扱うものは、mutex で書くしかない。 Time Zoneなど。
スレッドごとに乱数生成器(random number generator)を持ってもいいのか。 再現性(repeatability)が必要か。mutex では、再現性はない。
実行時特化(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
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() .
ライブラリを実現する場合、自分自身では 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() |
ライブラリを実現する場合、自分自身では 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() |
ライブラリを実現する場合、自分自身では 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() |
図? メイン・ルーチン、サブルーチンとコルーチン/ 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レベルのスレッドによるコルーチンの実行/Executing coroutines with OS-level threads.
GNU Pth - The GNU Portable Threads は、API としては、Mutex や条件変数を持っているが、 内部の実装はコルーチンである。
次の言語のコルーチンは、OS レベルのスレッドで実行される。
例：２つの mutex を２つのスレッドが次のようなタイミングでロックしよう とすると、デッドロックになる。
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 );
図? スレッド２個、資源２個で生じるデッドロック/ Deadlock with two threads and two resources.
解決方法(1): 複数の mutex をロックする時に順序を決める。
上の場合、どのスレッドも mutex1, mutex2 の
順でロックを行なうと、デッドロックは起こらない。
解決方法(2): だめな時には最初からやりなおす。
pthread_mutex_trylock() を使って、失敗したら全部をアンロッ
クして最初からやり直す。
ライブロックの危険性がある。
デッドロックの危険性があるコード。
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;
}
}
In the next program, the functions Thraed_A() and Thread_B() are executed in different threads, respectively. These threads use ad hock synchronization. Rewrite the function Thraed_A() to the correct program. No execution result is required.
// ad hock synchronization を使った間違ったプログラム
// The incorrect program that uses ad hock synchronization.
volatile int need_spining=1;
Thread_A() {
while( need_spining ) {
// 何もしない。Do nothing.
}
printf("OK.")
}
Thread_B() {
int c;
c = getchar();
need_spining = 0;
}
// 正しいプログラム。The correct program.
pthread_mutex_t mutex1;
pthread_cond_t condv1;
volatile int need_spining=1;
thread_A() {
// 必要に応じて埋める。Fill here if you need it.
while( need_spining ) {
// 必要に応じて埋める。Fill here if you need it.
}
// 必要に応じて埋める。Fill here if you need it.
printf("OK.")
}
thread_B() {
// 省略
}
典型的なコルーチンとスレッドを比較した時、重要な違いを2つ述べなさい。 When comparing typical coroutines and threads, describe two important differences.
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)*/
}
}