CONCURRENT PROGRAMMING 6 ソフトウェア工学 Software Engineering 並行プログラミング CONCURRENT PROGRAMMING

プロセスとスレッド 並行システムの実行形態 割り込みとプロセスの切り替え 並行システムの利点 １．並行システム Concurrent Systems プロセスとスレッド 並行システムの実行形態 割り込みとプロセスの切り替え 並行システムの利点

プロセスとスレッド プロセス： １つの逐次プログラムの実行単位 マルチプロセシング： 複数のプロセスを同時に実行すること Process プロセス：　１つの逐次プログラムの実行単位 Multi-processing マルチプロセシング：　複数のプロセスを同時に実行すること Thread スレッド：　１つのプロセス内の処理をさらに細分化した「軽量プロセス」とも呼ばれるプロセスの一種．複数のスレッドはメモリ空間を共有する． Multi-thread マルチスレッド：　複数のスレッドを同時に実行すること．

並行システムの実行形態 並列 並行 分散 擬似並行 プロセスの切り替え （インタリーブ） Parallel 物理的に結合して同時実行． ハードウェア，ファームウェア 並列 Concurrent 地理的に分散して同時実行． 情報ネットワーク Distributed 並行 分散 Quasi-concurrent １ＣＰＵで見かけ上同時実行． ＯＳ 擬似並行 Interleaving プロセスの切り替え （インタリーブ）

割り込みとプロセスの切り替え Interruption 時間切れ （タイマー割り込み） 別のプロセス マウスクリック （入出力割り込み） 処理データ切れ （データ到着待ち） 別のプロセス

並行システムの利点 資源の有効利用 公平性 利便性 入出力のような外部操作の待ち時間に，ほかのプログラムを動かすことができる． 複数のユーザやプログラムが資源を平等に使う仕組みを作ることができる． 利便性 必要なタスクを全部まとめたプログラムを書くよりも，各タスクごとに書くほうが良い．

インタリーブ 相互排他 オブジェクトのロックとスレッドの同期 デッドロック 飢餓，ライブロック ２．並列プログラミングの注意点 インタリーブ 相互排他 オブジェクトのロックとスレッドの同期 デッドロック 飢餓，ライブロック

インタリーブ Interleaving a プロセスＡ b プロセスＢ b a インタリーブは 予期できない 制御できない 膨大な数の実行経路を生じる

相互排他 共有変数は相互排他が必要 m = m + 1000; m = m - 1000; MOV A,m (A=5000) Mutual exclusion 共有変数は相互排他が必要 プロセスＡ m = m + 1000; 共有変数 ｍ=5000 プロセスB m = m - 1000; レジスター A レジスター B MOV A,m (A=5000) 1 ADD A,1000 (A=6000) 2 3 MOV B,m (B=5000) 4 SUB B,1000 (B=4000) MOV m,A (m=6000) 5 6 MOV m,B (m=4000)

オブジェクトのロックとスレッドの同期 スレッド 預金口座 BankAccount オブジェクト 同期 スレッド 口座番号 number Lock Synchronization オブジェクトのロックを取得(acquire) した１つのスレッドだけが，オブジェクトの内部にアクセスできる． オブジェクトにアクセスしたい他のスレッドは，ロックが開放(release)されるまで待つ． スレッド 預金口座 BankAccount オブジェクト 同期 スレッド 口座番号 number ロック 預金残高 balance

デッドロック acquire Scanner acquire Printer acquire Printer acquire Printer Deadlock プロセス　Ａ Scanner プロセス　Ｂ Printer acquire Scanner 1 acquire Printer 2 デッドロック acquire Printer acquire Printer acquire Scanner acquire Scanner acquire Scanner Copy Copy

飢餓，ライブロック request request request acquire fairness acquire request Starvation Livelock Resource プロセス　Ａ 優先順位の低いプロセス プロセス　Ｂ プロセス　C request request request acquire acquire fairness request 公平性がない acquire Printer acquire request acquire Scanner acquire Scanner プロセスＣは決して資源を獲得できない acquire

Threadオブジェクト run()メソッド スレッドの生成と実行 ３．Ｊａｖａマルチスレッドプログラミング 　Threadオブジェクト 　run()メソッド 　スレッドの生成と実行

Threadオブジェクト Thread worker = new Thread(); worker.start(); スレッドを生成 Threadオブジェクトを new で生成して，start()する． Thread worker = new Thread(); worker.start(); スレッドを生成 スレッドを実行 しかし，これではプログラマが実行させたい動作を書けない．

run()メソッド 実行させたい動作は run()に書く． public void run() { ……… }

スレッドの生成と実行(1/3) Threadクラスを拡張したサブクラスにrun()を記述し，そのサブクラスのインスタンスを生成 public class PingPongThread extends Thread { private String word; //what word to print private int delay; //how long to pause public PingPong(String whatToSay, int delayTime) { word = whatTosay; delay = delayTime; } コンストラクタ

スレッドの生成と実行(2/3) Threadクラスを拡張したサブクラスにrun()を記述 public void run() { try { for (;;) { System.out.print(word + ” ”); Thread.sleep(delay); //wait until next time } } catch (InterruptedException e) { return; //end this 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 …

演習問題 ６ スキャンとプリントの機能をもつ複合機３台(M0,M1,M2)およびこれらを利用する３つのプログラム(P0,P1,P2)が図のようにリング上に結合されている並行システムを考える． 複合機はロックを用いて相互排他が実現されているので，１つの複合機に同時に複数のプログラムがアクセスすることはできない． 各プログラムはいずれも隣接した１つの複合機から画像をスキャンし，もう１つの隣接した複合機にそれをプリントするものである． ただし，各プログラムが複合機にアクセスする順序が異なり，P0,P1,P2はそれぞれ，M0,M1,M2から画像をスキャンし，M1,M2,M0にプリントする． このシステムの問題点を説明し，その解決策について考察しなさい． P2 M2 M0 P0 P1 M1