2005/12/06

演習問題の解答例
演習問題の解答例 1.
1.
並列処理・分散処理では，逐次型処理では考慮する必要のなかった以下のような事項を考慮する必要があるため，逐次型処理よりも困難になる．
z 異なるプロセッサ（計算機）で進んでいく複数の処理の間で，必要なデータを交換しなければならないことがある．このためには，逐次型処理では必要のない通信処理を行ってデータ交換を行わなければならない．
z 複数の処理の間で，他のプロセッサ（計算機）での処理が一定の段階まで終了するのを待ち合わせなければならないことがある．このためには，逐次型処理では必要のない同期処理を行わなければならない．

コンピュータシステムII（９）情報基盤センター
天野 浩文

1

2

演習問題の解答例
演習問題の解答例 2.
2.

演習問題の解答例
演習問題の解答例 3.
3.

z UMA型システム（左下）
メモリのどの位置にアクセスする場合でも同じ時間で処理できるような共有メモリ型並列計算機
z NUMA型システム（右下）
メモリの位置によってアクセス時間に差が生じるような共有メモ
リ型並列計算機

プロセス・スレッドのいずれも，並列処理や分散処理を行うときの処理のまとまりの一種であるが，以下のような違いがある．

プロセッサ

バス

上位の相互結合網プロセッサ

z スレッドはプロセスよりも大きさが小さく，ひとつのプロセスが複数のスレッドから構成されることがある．
z プロセスは固有のメモリ空間を持つのに対して，同一プロセス内のスレッドはそのプロセスのメモリ空間を共有する．
z プロセス間の切り替えは，スレッド間の切り替えに比べて，処理に時間がかかる．
z 異なるプロセスどうしがメモリアクセスによって相互に影響を及ぼすことはないが，同一プロセス内のスレッドどうしは不適切なメモリアクセスを行うと相互に悪影響を及ぼすことがある．

メモリ3

コンピュータシステムII（９）412005/12/06

演習問題の解答例
演習問題の解答例 4.(a)4.(a)

演習問題の解答例
演習問題の解答例 4.(b)4.(b)

分散共有メモリ機構がない場合，リモートメモリへのアクセスは，通信処理を用いた処理依頼あるいはデータ転送依頼を含む，まったく別の処理として記述しなければならない．その一方，分散共有メモリ機構がある場合には，演算ノード内のローカルデータにアクセスする操作と，別の演算ノードのメモリ上にあるリモートデータにアクセスする操作を同じ記述形態で表すことが可能になる．

z コンパイラ方式は，コンパイル時にリモートメモリへのアクセスを通信処理に書き換えて実行可能プログラムを生成する．このため，（コンパイル時にリモートメモリへのアクセスがローカルメモリへのアクセスと区別できるように）リモートメモリへのアクセスを表す特殊な構文を加えて，既存のプログラミング言語を拡張する．
したがって，リモートメモリへのアクセスをある程度意識したプログラミングが必要で，新しいコンパイラも作成しなければならな
い．
z 実行時方式は，プログラム実行時に共有メモリへのアクセスが発生すると，その時点でOSに制御を移し，リモートメモリへのアクセスを代行させる．このため，言語の拡張や新しいコンパイラの作成は不要であるが，コンパイラ方式よりもやや複雑な機構が必要で，OSの機能拡張も必要である．

5

6

演習問題の解答例
演習問題の解答例 4.(c)4.(c)

演習問題の解答例
演習問題の解答例 4.(d)4.(d)(i)および(ii)は，いずれもコンパイラ方式で実現する必要がある．
一方，(iii)は，実行時方式で実現する必要がある．

z データを複写することによって分散共有メモリを実現する場合には，リモートメモリの操作が必要になると，そのデータがローカルメモリにコピーされる．このとき，同じデータのコピーが複数箇所に存在する状態になる．これらのコピーに対する変更操作があると，同じデータの値が複数存在することになり，これを放置すると誤った計算結果を生成する可能性がある．このため，同一のデータのコピーに対する変更操作があった場合，それ以降の同じデータに対する参照操作が常に新しいデータにアクセスできるように保証することが必要となる．

7

コンピュータシステムII（９）822005/12/06

演習問題の解答例
演習問題の解答例 5.
5.

演習についての注意事項
演習についての注意事項

z コピーを行わない方式– 長所：送受信が非常に速い．
– 短所：プロセス間で共有できるメモリ空間が必要となる．送受信するデータのアクセス保護が弱い．
z コピーを行う方式– 長所：送受信するデータのアクセス保護が強い．
– 短所：送受信に時間がかかる．

z 「解答例」に示したもの以外にも正解となる解答はありうる．
– まだ採点を行っていないが，採点時にその他の解答例が見つかれば，次回以降の講義で補足説明を行う．
z 各設問の配点，本科目の成績評価に占める割合は未定．
z 答案は返却しない．

910

処理全体の無矛盾性を考えなければならない例（１-1）
処理全体の無矛盾性を考えなければならない例（１-1）
z 同じ銀行口座に入金や出金処理を行う場合

排他制御機構と同期機構
排他制御機構と同期機構

11コンピュータシステムII（９）/* 入金処理 *//* 出金処理 *//* 口座の残高を調べる*/
READ(A);/* 口座の残高を調べる*/
READ(A);/* 残高に入金額を加える */A=A+200;/* 残高から出金額を引く */A=A-100;/* 口座の残高を書き戻す */WRITE(A);/* 口座の残高を書き戻す */WRITE(A);123

2005/12/06

処理全体の無矛盾性を考えなければならない例（1-2）
処理全体の無矛盾性を考えなければならない例（1-2）

処理全体の無矛盾性を考えなければならない例（1-3）
処理全体の無矛盾性を考えなければならない例（1-3）

z これが複数の演算ノードで処理されると…

z 正しく処理するためには…

A ＝ A＋200;
0

A ＝ A－100;
WRITE(A);300

WRITE(A);300?

個々の読み出し・書き込みは成功しているが，全体では矛盾がある．

READ(A);A ＝ A＋200;
WRITE(A);

100
100
300
300
200200

13READ(A);A ＝ A－100;
WRITE(A);

このような処理を排他制御（相互排除，mutual exclusion）と呼ぶ．

処理全体の無矛盾性を考えなければならない例（2-2）
処理全体の無矛盾性を考えなければならない例（2-2）

z 有限バッファを用いた生産者・消費者問題（bounded-buffer producer/consumer problem）

z タイミングによっては…

生産者:
repeat {バッファが満杯でなければ，品物を１個バッファに格納するカウンタを１増やす} until false;::

バッファ入りきれる品物の個数には上限があるものとする

時間

処理全体の無矛盾性を考えなければならない例（2-1）
処理全体の無矛盾性を考えなければならない例（2-1）

消費者:
repeat {バッファが空でなければ，バッファの品物を１個消費するカウンタを１減らす} until false;::

バッファ（MAX 5）

14

消費者

空ではない！
満杯ではない！

４
４

３
４から１増やそう！

15

コンピュータシステムII（９）生産者

この部分は排他的に実行しなくてはならない

READ(A);

この部分は排他的に実行しなくてはならない

時間時間

100
100
100

READ(A);

条件判断をしてから行動を起こすまでの間に，他のプロセス（スレッド）の条件判断がはさまっている．

４から１減らそう！

５５？

生産者どうし・消費者どうしが衝突すると，許されないはずの処理が行われてしまう可能性もある．
1642005/12/06

処理全体の無矛盾性を考えなければならない例（3-1）
処理全体の無矛盾性を考えなければならない例（3-1）
z 行列積 C=A×B を４プロセッサで計算する場合– プロセッサ１は，自分の受け持ち部分を計算する．
– 計算が終わったら，行列Ａの次の行ベクトルを隣のプロセッサから受け取り，次の担当部分を計算する．
– その計算が終わったら，また，行列Ａの次の行ベクトルを隣のプロセッサから受け取り，次の担当部分を計算する．
– 受け持ち部分が最終行まで来れば，終了．
z 同じような処理を，他のプロセッサでも行う．

＝

処理全体の無矛盾性を考えなければならない例（3-2）
処理全体の無矛盾性を考えなければならない例（3-2）＝×＝×＝

z 第一段の計算が全プロセッサで終了する前に行列Ａの行ベクトルの交換が始まってしまうと…

×– 計算の遅れているプロセッサでは，受け持ち部分の計算が正しく終了できなくなる．
z したがって，右の図の赤い破線のところで，他のプロセッサでの計算の終了を待ち合わせる必要が出てくる．

このような処理をバリア同期（barrier synchronization）と呼
ぶ．

×

17

＝×

＝×

＝×

＝×

18

排他制御と同期処理
排他制御と同期処理

セマフォ（semaphore）
セマフォ（semaphore）

z 排他制御（相互排除）– 複数のプロセス（スレッド）のプログラムコードの中に，共通の資源（例：共有変数など）にアクセスする部分があるとき，その部分を同時に実行できるプロセス（スレッド）がただ一つとなるようにすること．
• 最初のプロセス（スレッド）が上記のような危険区間（critical section）に到達すると，他のプロセス（スレッド）は危険区間の中に入れないように制御する．
z 同期処理– プロセス（スレッド）が，何らかの条件が成り立つまで処理を中断して待つこと．
• ここでいう「条件」とは，自分自身以外のものによって変更される種類のものを指す．

z もともとは相互排除のための機構– 少し工夫すると，ある種の同期にも使える．
z 最も簡単な相互排除機構
z 以下のような性質を持つ整数型変数– 初期化を別にすれば，次のような P および V と呼ばれる2種類の操作によってのみアクセス可能• P: 危険区間の開始を宣言する．他のプロセス（スレッド）が危険区間に入っているときには，先に進まずにここで待つ．
• V: 危険区間の終了を宣言する．同じセマフォに対するP命令で待っている他のプロセス（スレッド）が先に進めるようになる．

19

20

コンピュータシステムII（９）52005/12/06

セマフォによる相互排除の例（１）
セマフォによる相互排除の例（１）/* 入金処理 *//* 出金処理 *//* 危険区間の開始 */P(S);READ(A);
A=A+200;
WRITE(A);V(S);/* 危険区間の終了 *//* 危険区間の開始 */P(S);READ(A);
A=A-100;
WRITE(A);V(S);/* 危険区間の終了 */セマフォによる相互排除の例（２）セマフォによる相互排除の例（２）z 入金処理のほうが先にP(S)を実行したとき入金処理

出金処理

z 出金処理のほうが先にP(S)を実行したとき入金処理

P(S);READ(A);
A=A+200;
WRITE(A);

出金処理
P(S);

P(S);

P(S);

先に進めない先に進めないREAD(A);

READ(A);

A=A-100;

A=A+100;

WRITE(A);WRITE(A);

V(S);

V(S);

V(S);

READ(A);
A=A-100;
WRITE(A);
V(S);

21

22

PV操作の実現法の例（１）PV操作の実現法の例（１）PV操作の実現法の例（２）PV操作の実現法の例（２）P(S): while S<=0 do {};Sを1減らすz セマフォに待ち行列を付随させる方法もある．
– 危険区間に入れないときには，自分自身を待ち行列につないで，休眠状態に入る．
– 危険区間を出るときには，待ち行列の中からプロセス（スレッド）を１つ選んで，休眠状態から覚醒させる．

V(S): Sを1増やす
z S≦0 のときは危険区間に入れない．S＞0 のときは危険区間に入れる．
– 初期値を１にすると…
• 危険区間に同時に入れるプロセス（スレッド）数は１．
• このようなセマフォは，0 （入れない）または 1 （入れる）のいずれかの値しか取らない．
⇒バイナリセマフォ– 初期値を１より大きくすると，危険区間に同時に入れる数が１より大きくなる．
z 危険区間に入れない間は，ずっと空回りを続ける．
23

コンピュータシステムII（９）P(S): if S<=0 then {自分自身を待ち行列に登録する
自分自身を休眠状態にする}
Sを１減らす;教科書 p.62 のセマフォはこの形式

V(S): if S<=0 then {Sを1増やす待ち行列のプロセス（スレッド）を1つ選び覚醒させる
24}

62005/12/06

PV操作の実現法の例（３）PV操作の実現法の例（３）セマフォによる同期処理の例（１）
セマフォによる同期処理の例（１）z セマフォに計数機能を持たせる方法もある．
– セマフォの値は，0，1だけでなく，任意の整数値を取りうる．
• 初期値2以上のときは危険区間に同時に入れる数が1より多い．
• 負の値になったときには，その絶対値が，待っているプロセス（スレッド）数を表す．

z 「処理１が同期ポイントを通過した」という条件が成り立つまで，処理２が同期ポイントで待つようにする– バイナリセマフォの初期値を「危険区間に入れない状態（＝0）」にセットしておく．

P(S): Sを1減らす
if S<0 then {自分自身を待ち行列に登録する
自分自身を休眠状態にする}値の検査よりも先に，Sの値を増減させていることに注意．

V(S): Sを1増やす
if S<=0 then {待ち行列のプロセス（スレッド）を1つ選び覚醒させる
}

処理１

処理２

:
:
:
/* 同期ポイント */
V(S);
:
:
:

:
:
P(S);
/* 同期ポイント */
:
:
:
:

25

26

セマフォによる同期処理の例（２a）セマフォによる同期処理の例（２a）セマフォによる同期処理の例（２b）セマフォによる同期処理の例（２b）z 「処理１，処理２が同期ポイントを通過した」という条件が成り立
つまで，処理３が同期ポイントで待つようにする．
– セマフォの初期値を －1 にセットしておく．

z 「処理１，処理２が同期ポイントを通過した」という条件が成り立
つまで，処理３が同期ポイントで待つようにする．
– バイナリセマフォを2つ用意し，初期値を0にセットしておく．

処理１

処理２

処理３

処理１

処理２

処理３

:
:
:
/* 同期ポイント */
V(S);
:
:
:

:
:
:
/* 同期ポイント */
V(S);
::
:::
P(S);
/* 同期ポイント */
:
:
:
:

:
:
:
/* 同期ポイント */V(S1);::::::/* 同期ポイント */V(S2);::::
P(S2);
P(S1);/* 同期ポイント */
:
:
:
:

27

コンピュータシステムII（９）この順序は入れ替わってもよい28

7

2005/12/06

セマフォの使い方のまとめ
セマフォの使い方のまとめ

バリア同期操作の実現法の概要
バリア同期操作の実現法の概要

z 排他制御に使うとき– 初期状態は，危険区間に入れる状態• セマフォの初期値を１または正の整数にセット– 各プロセス（スレッド）は，危険区間の前後をP操作・V操作ではさんでおく．
z 同期処理に使うとき– 初期状態は，P操作が先に進めない状態• セマフォの初期値は 0 または負の整数– 先行させたいほうにV操作を，後追いさせたいほうにP操作を実行させる．

z 待ち状態のプロセス（スレッド）を１つだけ覚醒させるPV操作とは異なり，N 番目にそれを実行したものが他のすべてを覚醒させる．
– バリア同期すべきプロセス（スレッド）の数 N を初期値とする
共有変数を用いる
Barrier(S): Sを1減らす
if S>0 then {自分自身を休眠状態にする} else {他のすべてのプロセス（スレッド）を覚醒させる
Sを再初期化}29

30

バリア同期の例
バリア同期の例

排他制御とシングルプロセッサ排他制御とシングルプロセッサz すべての処理が同期ポイントに到達するまで，同期ポイントで待つようにする．
処理 N

z 排他制御は，単一のプロセッサ上で複数のプロセス（スレッド）が時分割方式で並行に動作している場合でも，必要になる．
– スライドNo.12～No.16のような議論は，それぞれのプロセス（スレッド）がシングルプロセッサ上で時分割実行されたときにも，そのままあてはまる．
– 実は，２年後期の「オペレーティングシステム」で勉強しているはず．
z ただし，並列処理・分散処理の場合には，排他制御を実現するためのメカニズムはより複雑になる．
– シングルプロセッサ上では，プロセス（スレッド）の切り替えが起きないようにするだけでよかったが…

処理３

処理４

:
:
:
処理１
:
:
:
:
/* 同期ポイント */::::Barrier(S);:/* 同期ポイント */:::/* 同期ポイント*/
Barrier(S);:/* 同期ポイント*/:
Barrier(S);:/* 同期ポイント*/
Barrier(S);:::Barrier(S);
:
:
:
:
:
:
:
:
:
処理２

• 割り込み禁止のマスクをかけるだけでも実現できる．
31

コンピュータシステムII（９）3282005/12/06

P操作の実装に関する注意
P操作の実装に関する注意

ではどうするとよいか？
ではどうするとよいか？

z 「先に進んでよいかどうか」の条件判断と，それに続くセマフォの変更や休眠処理までの間に，他のP操作の条件判断が行われないようにしなければならない．
– この条件が守られないと，スライドNo.13で示したのと同様の不具合が発生する．
z 複数のプロセッサが共有メモリ上の変数にアクセスできる場合

z ①と③の間に他の操作が行われないようにするには…

プロセッサA

①判断
③変更
②判断

プロセッサB

セマフォS

Aで割り込みが禁止されていても，①②③④の順で実行されてしまう可能性がある．

④変更
33

コンピュータシステムII（９）– それが単一の機械語命令で実行されるようにすればよい．
⇒ハードウェア（CPU）にそのような命令が備わっている必要がある．
– 言葉で言うのは簡単だが… もうひとひねり必要．
z Test-and-Set 命令を使ったP操作
while Test-and-Set(lock) do {}z Test-and-Set(lock)• 変数lockの値を返す• lockには trueを書き込む

lockの値が true なら，上のP操作はTS命令の繰り返しになる．
lockの値が false なら，上のP操作は何も実行せずに終了して次に進む． 34

9