並行プログラミング
CONCURRENT PROGRAMMING
6 Software Engineeringソフトウェア工学
マルチコアのプロセッサやネットワーク上の分散システムの計算環境では 複数のプログラムが並行して動くことになるが，思わぬ動作で不具合が生 じることがある
１．並行システム
concurrent systemsプロセスとスレッド 並行システムの実行形態
割り込みとプロセスの切り替え 並行システムの利点
プロセスとスレッド
プロセス： １つの逐次プログラムの実行単位
スレッド： １つのプロセス内の処理をさらに細分化した
「軽量プロセス」とも呼ばれるプロセスの一種．
複数のスレッドはメモリ空間を共有する．
マルチプロセシング： 複数のプロセスを同時に実行すること
マルチスレッド： 複数のスレッドを同時に実行すること．
process
multi-processing
thread
multi-thread
並行システムの実行形態
concurrent並行
parallel並列
quasi-concurrent擬似並行
distributed分散
物理的に結合して同時実行．
ハードウェア，ファームウェア 地理的に分散して同時実行．
情報ネットワーク
１ＣＰＵで見かけ上同時実行．
ＯＳ
割り込みとプロセスの切り替え
プロセス
別のプロセス
別のプロセス 別のプロセス
interruption
並行システムの利点
資源の有効利用
入出力のような外部操作の待ち時間に，ほかのプログラムを 動かすことができる．
公平性
複数のユーザやプログラムが資源を平等に使う仕組みを作る ことができる．
利便性
必要なタスクを全部まとめたプログラムを書くよりも，各タ スクごとに書くほうが良い．
２．並行プログラミングの注意点
インタリーブ
相互排他オブジェクトのロックとスレッドの同期 デッドロック
飢餓，ライブロック
インタリーブ
b b b b b
a
a a
a a
a a
プロセスＡ b
b
プロセスＢ
インタリーブは 予期できない interleaving
相互排他
ｍ=5000 共有変数 プロセスＡ
m = m + 1000; プロセスB
m = m - 1000;
MOV A,m (A=5000)
MOV B,m (B=5000) ADD A,1000 (A=6000)
SUB B,1000 (B=4000) MOV m,A (m=6000)
MOV m,B (m=4000) 1：mの値をAレジスタにコピー
2：Aレジスタに1000を加算
5：Aレジスタの値をmにコピー mの値をBレジスタにコピー：3 Bレジスタから1000を減算：4
Bレジスタの値をmにコピー：6
共有変数は相互排他が必要 mutual exclusion
レジスター A レジスター B
ｍ=４000 となってしまう
オブジェクトのロックとスレッドの同期
lock synchronization預金口座 BankAccount
口座番号 number
預金残高 balance ロック
オブジェクトのロックを取得(acquire) した１つのス レッドだけが，オブジェクトの内部にアクセスできる．
オブジェクトにアクセスしたい他のスレッドは，ロッ
クが開放(release)されるまで待つ． スレッド
同期 スレッド オブジェクト
デッドロック
Scanner
acquire Scanner
acquire Printer Copy
1 2
Printer
プロセス Ａ プロセス Ｂ
acquire Scanner acquire Printer
Copy
デッドロック deadlock
飢餓，ライブロック
Resource
request
プロセス Ｂ
プロセス C プロセス Ａ
acquire request
acquire
request request
優先順位の低いプロセス
公平性がないfairness
livelock starvation
３．Javaマルチスレッドプログラミング
Threadオブジェクトrun()メソッド
スレッドの生成と実行
Threadオブジェクト
Thread worker = new Thread();
worker.start(); スレッドを生成 スレッドを実行
Threadオブジェクトを new で生成して，start()する．
しかし，これではプログラマが実行させたい動作を書けない．
run()メソッド
public void run() {
………
}
実行させたい動作は run()に書く．
スレッドの生成と実行(1/3)
public class PingPongThread extends Thread {
private String word; //what word to print private intdelay; //how long to pause public PingPongThread(String word, int delay) {
コンストラクタ Threadクラスを拡張したサブクラスを定義し，
そのサブクラスのインスタンスを生成するコンストラクタを定義
スレッドの生成と実行(2/3)
public void run(){ try {
for (;;) {
System.out.print(word+ ” ”);
Thread.sleep(delay); //wait until next time } catch (InterruptedException e) {}
return; //when error, end this thread } }
run()メソッド Threadクラスを拡張したサブクラスにrun()を記述
スレッドの生成と実行(3/3)
public static void main(String[] args) {
PingPongThread t1 = new PingPongThread(”ping”, 33);
PingPongThread t2 = new PingPongThread (”PONG”,100);
t1.start();
t2.start();
}}
実行結果
ping PONG ping ping PONG ping ping ping PONG ping …
main()メソッド インスタンスを生成し，start() メソッドを呼び出すことで
PingPongThread クラスの run() メソッドが実行される
演習問題 ６
スキャンとプリントの機能をもつ複合機３台 (M0,M1,M2)およびこれらを利用する３つのプロ グラム(P0,P1,P2)が図のようにリング上に結合さ れている並行システムを考える．
複合機はロックを用いて相互排他が実現されて いるので，１つの複合機に同時に複数のプログラ ムがアクセスすることはできない．
各プログラムはいずれも隣接した１つの複合機 から画像をスキャンし，もう１つの隣接した複合 機にそれをプリントするものである．
ただし，各プログラムが複合機にアクセスする 順序が異なり，P0,P1,P2はそれぞれ，
M0,M1,M2から画像をスキャンし，M1,M2,M0に プリントする．
このシステムの問題点を説明し，その解決策に
ついて考察しなさい． M1
M2 M0
P2
P1 P0
