並行プログラミング 6

並行プログラミング

CONCURRENT PROGRAMMING

6 ^{ソフトウェア工学}

Software Engineering

マルチコアのプロセッサやネットワーク上の分散システムの計算環境で は複数のプログラムが並行して動くことになるが，思わぬ動作で不具合が 生じることがある

１．並行システム

プロセスとスレッド

並行システムの実行形態

割り込みとプロセスの切り替え 並行システムの利点

プロセスとスレッド

 プロセス： １つの逐次プログラムの実行単位

 スレッド：　１つのプロセス内の処理をさらに細分化した

「軽量プロセス」とも呼ばれるプロセスの一種．

複数のスレッドはメモリ空間を共有する．

 マルチプロセシング：　複数のプロセスを同時に実行すること

 マルチスレッド：　複数のスレッドを同時に実行すること．

process

multi-processing

thread

multi-thread

並行システムの実行形態

並行

concurrent

並列

parallel

擬似並行

quasi-concurrent

分散

distributed

プロセスの切り替え

（インタリーブ）

物理的に結合して同時実行．

ハードウェア，ファームウェア

地理的に分散して同時実行．

情報ネットワーク

１ＣＰＵで見かけ上同時実行．

ＯＳ interleaving

割り込みとプロセスの切り替え

プロセス

別のプロセス

別のプロセス

別のプロセス

時間切れ

（タイマー割り込み）

マウスクリック

（入出力割り込み）

処理デ

ータ切れ

（データ

到着待ち） interruption

並行システムの利点

 資源の有効利用

 入出力のような外部操作の待ち時間に，ほかのプログラム を動かすことができる．

 公平性

 複数のユーザやプログラムが資源を平等に使う仕組みを作 ることができる．

 利便性

 必要なタスクを全部まとめたプログラムを書くよりも，各 タスクごとに書くほうが良い．

２．並行プログラミングの注意点

インタリーブ 相互排他

オブジェクトのロックとスレッドの同期 デッドロック

飢餓，ライブロック

インタリーブ

b

b b

b b

b a

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 となってしま う

オブジェクトのロックとスレッドの同期

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

acquire request

acquire

優先順位の低いプロセス

公平性がない

fairness livelock

starvation

３．

マルチスレッドプログラミング

オブジェクト 　

メソッド

　スレッドの生成と実行

Thread

オブジェクト

Thread worker = new Thread();

worker.start(); スレッドを生成

スレッドを実行

Thread オブジェクトを new で生成して， start() す る．

しかし，これではプログラマが実行させたい動作を書けない

．

run()

メソッド

public void run() {

………

}

実行させたい動作は run() に書く．

スレッドの生成と実行

public class PingPongThread extends Thread {

private String word; 　　　　 //what word to print private int delay; 　　　　 //how long to pause

public PingPongThread(String word, int delay) { this.word = word;

this.delay = delay;

}

コンストラクタ

Thread クラスを拡張したサブクラスを定義し，

そのサブクラスのインスタンスを生成するコンストラクタを定義

スレッドの生成と実行

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() を記

述

スレッドの生成と実行

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

P0 P1