+------------+ +------------+
| processor | | processor | load命令, store命令などを実行
+-----+------+ +------+-----+ (IA-32だとメモリオペランドで暗黙な場合が多い)
| |
--+-------+--------+---
|
+------+------+
|shared memory| 値の読み出し(read)，書き込み(write)を処理
+-------------+
のように考えることができる．
あるプロセッサ(コア)がload命令などの実行により
あるアドレスの値を読み出す(read)と，
他のプロセッサ(コア)を含めてstore命令などの実行により最後に
そのアドレスに書き込み(write)した値が読み出せる．
#include <pthread.h>」
gcc -O2 -pthread foo.c -o foo
pthread_mutex_lock でロックを獲得できるまで待ち，
pthread_mutex_unlock でロックを解放
pthread_join)
wait()を用いる。
(pthreadsなら，pthread_cond_wait)
wait()を実行したスレッドは
自分自身を条件変数の待ち集合に入れて、
ロックを解放し、休眠する。
ロックは条件の確認とwait()の実行を，
他のスレッドに邪魔されずに一括して行うために必要であり，
条件確認前に獲得する．
wait()する)
notify()または
notifyAll()を用いる。
(pthreadsなら，pthread_cond_signal
または pthread_cond_broadcast)
notify()は、待ち集合の任意の一つのスレッド、
notifyAll()は、待ち集合のすべてのスレッドを起こす。
(待ち集合から取り除き、休眠状態を解除する)
notify()/notifyAll()
したスレッドがロックを解放するまでは、
伝えられたスレッドはロックを獲得できないので先に進めない。
fprintf で出力するような場合に
スレッド間の相互排他(適当なロックについての
pthread_mutex_lock/pthread_mutex_unlock
)が必要であろう．
なぜなら，
FILE * に排他的アクセスする必要があるから．
pthread_mutex_lock/
pthread_mutex_unlock
呼び出しを書く必要はない．これは自動的に行われる．
そのような関数をスレッド・セーフ関数という．
なお，もともとスレッド・セーフな関数については相互排他はしない．
fprintfの利用などは
逐次プログラムと同じように書ける．ただし，
複数回の呼び出しを「まとめて」出力したいときは，
flockfile/funlockfile
を使う必要がある．
|
| fork ｜
fork +-----+ ｜
+-----+ | ↓ t
| | |
thr3 | |thr1 |thr2
| | |
+-----+ |
join +-----+
| join
|
分担させた仕事の完了は、joinを行うことで待つ。
|
| fork ｜
+-----+--+--+-----+ ｜
| | | | ↓ t
| | | |
| | | |
| | | |
+-----+--+--+-----+
| join
|
[A1,A2,A3,A4], [B1,B2,B3,B4], [C1,C2,C3,C4], [D1,D2,D3,D4] 答案綴り4部
↓
[A1,B1,C1,D1], [A2,B2,C2,D2], [A3,B3,C3,D3], [A4,B4,C4,D4] 問題番号毎
4人でこの作業をすることを考えると、一つには各自が答案用紙1部をとり、
それを問題番号毎に分けた場所においていくということが考えられる。
(分割統治型並列処理)
[A1,A2,A3,A4], [B1,B2,B3,B4], [C1,C2,C3,C4], [D1,D2,D3,D4]
↓
[A1,B1,C1,D1]
+
[A2, A3, A4], [B2,B3,B4], [C2,C3,C4], [D2,D3,D4]
P2さんは、答案用紙4部から2枚目を集めることにする:
[A2,A3,A4], [B2,B3,B4], [C2,C3,C4], [D2,D3,D4]
↓
[A2,B2,C2,D2]
+
[A3, A4], [B3,B4], [C3,C4], [D3,D4]
同様に、P3, P4さんはそれぞれ3枚目, 4枚目を集めることにする。
このままだと、P1さんの仕事が終了してから、
P2さんの仕事が開始できることになるが、
工夫すればパイプライン的に仕事をすることができる。
つまり、P1が1枚目を集めた答案綴りについは、
すぐにP2が処理をすればよい。これを図示すると:
P1
|
[A1] P2
+----->|
| [A2] P3
[B1] +----->|
+----->| [A3] P4
| [B2] +----->|
[C1] +----->| [A4]
+----->| [B3] |
| [C2] +----->|
[D1] +----->| [B4]
+----->| [C3] |
| [D2] +----->|
+----->| [C4]
| [D3] |
+----->|
| [D4]
|
のようになる。
pthread_cond_wait、
pthread_cond_broadcast による同期の場合は、
フラグアクセスを mutexロックを獲得して行う必要があるため、
この二段階はあまり有利ではないかも。
pthread_cond_broadcastで
停止していたスレッドを起こした後に 0にリセットするなら
同じカウンタを再利用できるが，
共有メモリ向けマクロでは同じカウンタはそのまま再利用できない．
なぜなら，まだ待っているスレッドがいるうちに，先に
処理を進めたスレッドが再びバリア同期をとるために，カウンタを
操作すると1度0にリセットしたという情報が失われるから．
|
| fork ｜
+-----+--+--+-----+ ｜
| | | | ↓ t
| | | |
| | | |
| | | |
+-----+--+--+-----+
| join
|
| fork
+-----+--+--+-----+
| | | |
| | | |
| | | |
| | | |
+-----+--+--+-----+
| join
|
以下のようにしてもよい。
|
| fork ｜
+-----+--+--+-----+ ｜
| | | | ↓ t
| | | |
| | | |
| | | |
+-----+-----+-----+ ここでバリア同期
| | | |
| | | |
| | | |
| | | |
+-----+--+--+-----+
| join
|
+------------+ +------------+
| processor | | processor | load命令, store命令などを実行
+-----+------+ +------+-----+
| |
+-----+------+ +------+-----+
| buffer | | buffer | 異なるアドレスについては
+-----+------+ +------+-----+ アクセス順を入れ替える可能性あり
| |
| |
--+-------+--------+---
|
+------+------+
|shared memory| 値の読み出し(read)，書き込み(write)を処理
+-------------+
と考えることができる。
+------------+ +------------+
| virtual C | | virtual C | Cプログラムの(仮想)実行主体
| processor | | processor |
+-----+------+ +------+-----+
| |
+-----+------+ +------+-----+ コンパイラの最適化によって
| optimizer | | optimizer | アクセス順を入れ替える可能性あり
+-----+------+ +------+-----+ アクセスを省略する可能性あり
| |
+-----+------+ +------+-----+
| buffer | | buffer | 異なるアドレスについては
+-----+------+ +------+-----+ アクセス順を入れ替える可能性あり
| |
| |
--+-------+--------+---
|
+------+------+
|shared memory| 値の読み出し(read)，書き込み(write)を処理
+-------------+
コンパイラによるアクセス順の変更やアクセス省略などが行われた後，
さらに
ハードウェアが提供するメモリコンシステンシモデル上許される
アクセス順の変更などが行われることになる．
コンパイラやハードウェアといった細かい点を見ないことにして，
C言語レベルで共有変数や共有データ構造について考えた
モデルは:
+------------+ +------------+
| virtual C | | virtual C | Cプログラムの(仮想)実行主体
| processor | | processor | (スレッド)
+-----+------+ +------+-----+
| |
+-----+------+ +------+-----+
| buffer | | buffer | アクセス順変更
+-----+------+ +------+-----+ アクセス省略など
| |
| |
--+-------+--------+---
|
+-----------+------------+
| shared variables |
| shared data structures |
+------------------------+
のようになる．
ここで，アクセス順変更やアクセス省略は
Cプログラムの(仮想)実行主体(スレッド)が単一であれば
問題ないものであるが，複数である場合は問題になり得る．
共有メモリマクロが使っている volatile 型修飾子について
計算機室の gcc4 (4.0.0) ではうまく扱えていない可能性があること
が分かりました．
(参考:
http://www.jpcert.or.jp/sc-rules/c-dcl17-c.html
)
xread_int などを利用している場合，
(対処a) atomic_read_int_to_finish_readに置き換えるか，
(対処b) gcc version 3.4.3 を用いるか，
(対処c) 対象となるデータのほうに
volatile 型修飾子を使うか，
などを試してみてください．
課題提出済みのプログラムについては(c)によって測定を行っています．
(2009/11/02)