7. 並列プログラミング

並列プログラミング

並列マシンでは必須

単一CPUのマシンでも有用な場合がある

様々な並列言語が提案されてきた

身の回りの並列プログラミング

マルチタスクOS

Wordとブラウザは同時に動く

全二重通信

受信と送信が同時

c.f. 半二重通信

タイマ割込み

各種のユーザインタフェース

ハードウェア割込み

CPUに信号を送って現在の処理を中断

別の処理を行なってから戻る

ハードウェア割込みが無いと無限ループから抜けられない

code:infinite.c

while(true){

// ハードウェア割り込みがないと終了しない

}

Webと並列プログラミング

独立して動くプロセス多数

ユーザ操作

システムからの出力

バックグラウンド検索

サーバとブラウザの通信

本質的に並列プログラミングが必要なので難しい

並列と並行

並列 (Parallel)

複数の計算機が同時に動作

並行 (Concurrent)

擬似並列

時分割で動作

プリエンティティブと非プリエンティティブ

プリエンプティブ

ハードウェア割り込みによりプロセスを強制切り換え

for(;;) などというプログラムを書いても大丈夫

一般的OSで採用

複数プログラムをOSが調停

ノンプリエンプティブ

プロセスが自主的に処理をシステムに戻す

システムが次のプロセスに処理を渡す

昔のシステム/組み込みシステムなどで使われることもある

ノンプリエンプティブなシステム

某自動車会社のクルマ

プロセスはひとつだけ

様々なセンサを調べて回るプログラムが無限ループ

プリミティブなゲーム

走査周期にあわせて無限ループ

ふた昔前のパソコンOS

AppleII, Windows3.x, MacOS

プリンタを使うと他はすべて止まる

昔のPDA

Zaurus, Palm, ...

並列プログラミングの難しさ

非決定的に動くのでデバッグが大変

動く順番が決まっていない

プログラムが正常に動いたり動かなかったり

正しいことを証明するのが困難

ロジックが難しい

同期の管理が難しい

並列プログラミングの嬉しいところ

並列マシン/マルチCPUが使える

ロジックが明解になることがある

e.g. シミュレーション

複数プレーヤのシミュレーション

簡単な並列プログラミング

Unixのパイプ

% cat slide | grep pipe | wc

cat, grep, wc は同時に動く

8-Queen

http://gyazo.com/942a93103f9ead8908fb3a49800ce68b.png

解を次々と計算して表示するのは簡単

ユーザアクションの応じて次の解を計算するのは難しい

パズルを解くプログラムとユーザアクションを別プロセスにするとよい

8-Queenプログラム例

実行

code:queens1.js

function setup(){

col = [];

qpos = [];

up = {};

down = {};

nqueens = 8;

var i;

for(i=0;i<nqueens;i++){

coli = qposi = 0;

}

for(i= -nqueens;i<nqueens;i++){

upi+nqueens = 0;

downi+nqueens = 0;

}

expand(0);

}

function output(){

var i;

var s = '';

for(i=0;i<nqueens;i++){

s += qposi;

}

console.log(s);

alert(s);

}

function expand(n){

for(var c=0;c<nqueens;c++){

if(colc == 0 && upn+c == 0 && downn-c+nqueens == 0){

qposn = c;

if(n+1 >= nqueens){

output();

}

else {

colc = upn+c = downn-c+nqueens = 1;

expand(n+1);

colc = upn+c = downn-c+nqueens = 0;

}

実行結果

code:result.sh

$ node queens1.js

0 4 7 5 2 6 1 3

0 5 7 2 6 3 1 4

0 6 3 5 7 1 4 2

0 6 4 7 1 3 5 2

1 3 5 7 2 0 6 4

1 4 6 0 2 7 5 3

1 4 6 3 0 7 5 2

...

8-Queenの実行 (サーバ)

ユーザ要求に応じて解が出力される

code:queentest2.rb

require 'socket'

require 'queens'

PORT = 4321

HOST = "localhost"

server = TCPServer.open(PORT)

sock = server.accept

q = Queens.new

q.run { |qpos|

sock.gets

sock.qpos

}

sock.close

server.close

8-Queenの実行 (クライアント)

code:8queen.sh

% telnet localhost 4321

Connected to localhost.

Escape character is '^]'.

0 4 7 5 2 6 1 3

0 5 7 2 6 3 1 4

0 6 3 5 7 1 4 2

0 6 4 7 1 3 5 2

1 3 5 7 2 0 6 4

....

インタフェースと並列プログラミング

並列プログラミングが都合が良い

複数の入力待ち

マウス、キーボード、音声...

別々のプロセスで処理できると都合が良い

突然発生するエラー

複数ユーザ

テストモジュールをプロセスとして扱う

ユーザをプロセスとして扱う

半二重通信 = 極端な同期通信

常に1方向の通信

データのやりとりは交替で行なう

トランシーバ的通信

昔の大型機の端末

システムの仕事中は入力できない

大きなリセットキーというものがある

激しく使いにくい!

単線電車

https://gyazo.com/9ddc4c16d201c1ca16136e5249628e4f.png

メインフレーム計算機のキーボード

http://gyazo.com/b8ae4735ce94e8abdecc5f1364ef34a3.png

現在の端末

全二重通信

常にユーザは入力可能

先行入力可能

処理は順番に行なわれる

全二重通信

複線の電車のようなもの

半二重は単線

最低限の並列プログラミングが必要

e.g. ターミナルエミュレータ

ユーザ入力とシステム出力を両方監視

複線電車

https://gyazo.com/c5f906543e7d6ef7696daa95f4885d33.png

プロセスとスレッド

プロセス

一般的なプログラム

スレッド

ひとつのプログラムの中の軽量プロセス

プロセス

独立したメモリ空間を持つ

他のプロセスの影響を受けにくい

プロセス切り替え/プロセス間通信は遅い/難しい

スレッド

ひとつのメモリ空間に複数存在

同期や通信が高速

最近の軽量スクリプト言語では標準装備

スレッドライブラリ

cthread

Machで導入

pthread

Posixで標準化

Pth

GNUのライブラリ

コルーチン

別スレッドに制御を移動

c.g. サブルーチン

Modula-2言語などで利用できる

山本強氏エッセイ

コルーチン利用例

GNU Pthライブラリによるコルーチンの利用

8-Queenなどに利用できる

http://gyazo.com/3c4cf41a04404b42078db80de9c76486.png

Generator

JavaScriptの新しい機能

returnのかわりに yieldを使う

generator function

function*(){ ... }

Generatorの例

実行

code:gentest.js

function* generator_function(from, to){

while(from <= to) yield from++;

}

var g = generator_function(1, 5); // Generator

for(var num of g) alert(num);

Generator間のタスク切り替え

run this program

code:tasks.js

function* task1(){ // Generator function for task1

while(true) yield "I am task1"

}

function* task2(){ // Generator function for task2

while(true) yield "I am task2"

}

var t1 = task1() // Generator 1

var t2 = task2() // Generator 2

while(true){

alert(t1.next().value)

alert(t2.next().value)

}

プロセスの同期の必要性

変なところでプロセスが切り換わると計算を間違える

一度にひとりしか使えない資源がある

計算が失敗する例

code:count-fail.rb

count = 0;

t1 = Thread.new do

100000.times do

count += 1

end

t2 = Thread.new do

100000.times do

count += 1

end

t1.join; t2.join

puts count

プログラム実行結果

code:result

$ ruby count-fail.rb

142012

$ ruby count-fail.rb

142597

$ ruby count-fail.rb

124374

成功例

http://gyazo.com/cbad66d3f8e1cd3837111c78ddc43352.png

失敗例

http://gyazo.com/2eaec9c77a7c9c36ecbb4b2baffa3aba.png

危険な領域 (Critical Section)

複数の処理が同時に実行されると破綻する部分

上の例では「count += 1」

この部分をアトミック実行する必要あり

修正したもの

count-monitor.rb

countに対して複数プロセスが同時にアクセスしないようにする

lockの中は同時に実行されない

code:count-monitor.rb

require 'Monitor'

lock = Monitor.new

count = 0;

t1 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

t2 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

t1.join; t2.join

puts count

修正したものの実行

code:result

$ ruby count-monitor.rb

200000

$ ruby count-monitor.rb

200000

同期が必要な場合

OSレベルでも普通のプログラムでもアプリケーションでも発生

e.g. Wiki

同時更新すると古い書き込みが消える

有名な同期問題

「眠り床屋」

「哲学者の食事」

こういう問題をうまく解ければよい

哲学者の食事問題

http://gyazo.com/c1099adbf7a3d668e444a29afd772594.png

発生する可能性のある問題

デッドロック

資源分配の片寄り

誰かがずっと食事できないとか

ソフトウェアによる同期プリミティブサポート

Dekkerのアルゴリズム

特殊なハードウェアを利用せずアトミック処理を実現

http://gyazo.com/345ca496d5efc523a8bfe62a84d59f32.png

ハードウェアによる同期サポート

Test and set命令

テストに成功するとビットをセットする

競合してもひとつのCPUだけが成功する

Lock命令

次の命令において割込みを許さない

Compare and swap命令

68000, 80486系, etc.

Fetch and add命令

The Art of Multiprocessor Programming

https://www.amazon.co.jp/dp/0123705916 https://gyazo.com/031fb9eecd436f8249c1076e57cd5227.png

プロセスの待ち方

ビジーウェイト

条件が満たされるまで条件チェックを繰り返す

入力待ち、条件待ち

効率が悪い

待つときはプロセス切り換えすべき

JavaScriptのコールバック関数

ネットから情報取得

時間がかかる可能性がある

待ち続けるのは良くない

実行

code:get.js

// Get data from a Web page

$.get("https://masui.github.io/", function(data){ // callback function

alert("Data: " + data);

});

alert('Done') // really?

コールバック関数が呼ばれる前にDoneが表示される

HTTP通信とメインプログラミングは同時に実行される

コールバック関数がいつ呼ばれるのかは不明

この面倒さがJavaScript界で近年大きな話題になっている

Promiseなど

同期基本命令

mutex

セマフォ

モニタ

mutex

"mutual exclusion"

危険な領域を囲むことによりアトミック処理を保証

セマフォ

Dijkstraが考案した同期基本命令

危険な領域に入れるかどうかを制御

http://gyazo.com/c565aed30ead1e39bb5d8c1f012a9bc2.png

Digkstra

https://gyazo.com/1115c64e4aa56fe0d2b773c07c7e58d6

セマフォの構造

整数sと待ちプロセスのリストを保持

P(Passeren)命令

code:p.txt

(sはいくつかの値に初期化されている)

if(s==0){ 自プロセスを待ちリストに入れる } // put current process to waiting list

else s = s-1;

V(Verhoog)命令

code:v.txt

if(待ちリストあり) 待ちプロセスのひとつを実行可能にする // if(waiting) make one process running

else s = s+1

P, Vはアトミック処理

バイナリセマフォ / 計数セマフォ

セマフォの特徴

P, Vをうまく組み合わせると様々なタイプの同期を実現可能

複雑になるとバグが出やすい

モニタ

危険な領域をブロックとして扱う

Concurrent Pascalで導入

Javaでも使われている

Synchronized

構造化セマフォのようなもの

モニタの例 (Ruby)

code:monitor.rb

require 'Monitor'

lock = Monitor.new

count = 0;

t1 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

t2 = Thread.new do

100000.times do

lock.synchronize do

count += 1

end

t1.join; t2.join

puts count

CSP (Communicating Sequential Processes)

メッセージによる同期/情報交換パラダイム

入出力を備えた逐次プロセスで並行プログラムを構成

共有メモリ利用が普通だった

解説, 書籍

Occam言語で利用

並列処理言語 (Parallel languages)

Occam

CSP (同期メッセージ)

Concurrent Pascal, Edison

モニタ

Modula-2

コルーチン

Erlang

非同期メッセージ

一般言語+並列化

cthread / pthread

Rubyのスレッド

Javaのスレッド

Linda

プロセス間通信

共有メモリ

メッセージ通信

同期と通信の一体化

プロセスは同期させるだけでは無意味

データやりとりの必要あり

データ通信と同期を同時に行なうのが便利

Linda

タプル(データ組)をタプル空間(共有空間)でやりとりする

4種類のプリミティブで同期とデータ交換を実現

out -- タプルをタプル空間に書き出す。

in -- タプルをタプル空間から読む。タプルは消去する。

rd -- タプルをタプル空間から読む。タプルは消去しない。

eval -- プロセスを生成する。

Linda

https://s3-ap-northeast-1.amazonaws.com/masui.org/5/c/5c79a78e3de1dcec20999cedfc5ddfad.png

Linda で8-Quiin

入出力と計算本体を別プロセスで動かす

TSを介して通信

node-linda

HTTPサーバでLindaサーバを動かす

Node-Lindaによる実世界プログラミング

Getting sensor info

exec

code:sensor.js

setup = () => {

createCanvas(400,1000)

// connect to node-linda server and create a tuple space

server = "//linda-server.herokuapp.com"

socket = io.connect(server)

linda = new Linda().connect(socket)

ts = linda.tuplespace("masuilab")

y = 0

linda.io.on("connect", () => { // connected to Linda server

ts.watch({where: "delta"}, (err, tuple) => { // wait for tuples

if(y > 600){

clear()

y = 0

}

y += 20

text(name=${tuple.data.name}, value=${tuple.data.value},20, y)

})

}

Rinda

RubyによるLindaの実装

by 関氏

Rubyで簡単にLindaを利用できる

× Ruby以外の言語が使えない

Rindaによるプログラミング

code:rinda.rb

require 'rinda/rinda'

require 'delicious'

TS_URI = 'druby://localhost:12345'

USER = 'masui'

ts = DRbObject.new(nil,TS_URI) # タプル空間に接続

while true

ts.write('weight',$$,"")　 # 体重値タプル取得

val = ts.take('weight',$$,Float)2

end

LindaRocketIO

Webサーバを利用したLinda実装

RocketIOを利用

RocketIO

Sinatra上のSocket.IO的なもの

Socket.IO = Node.jsの通信ライブラリ

サーバ(Ruby)とクライアント(JS)の間で自由にイベント通信

サーバ側

Sinatra::RocketIO.on “イベント名” でイベント登録して受信

Sinatra::RocketIO.push “イベント名”, “データ” で送信

クライアント側

var io = new RocketIO().connect(); で得たio（RocketIOのインスタンス）を使う

io.on(“イベント名”, コールバック関数) でイベント登録して受信

io.push(“イベント名”, データ) でサーバに送信

特殊な入力装置でブラウザを使う

プロセス1

装置の情報を読んでTSに送出

プロセス2

TSのタプルを読んでブラウザ操作

並列プログラミングと他パラダイム

分散プログラミング

オブジェクト指向プログラミング

並行オブジェクト指向プログラミング

状態遷移プログラミング

拡張状態遷移図、ペトリネット

ビジュアルプログラミング

図は並列性を含んでいる

まとめ

並列プログラミングは難しい

一般的には流行ったことがない

しかし最近の言語は扱いやすいものも多い

適切な言語と環境を使えば利点が多い

参考文献

OSの本棚