Microsoft PowerPoint - erlang-parallel100216

Size: px

Start display at page:

Download "Microsoft PowerPoint - erlang-parallel100216"

ひろじしどり
4 years ago
Views:

1 Erlangの並列計算の入り口 2007/OCT/ /FEB/16 たけおか

2 Erlan はコミッティドチョイス言語だ 2010/FEB/16 追記コミッティドチョイス言語節の頭にガードがあるガードを超えた節だけが選ばれて走行する Erlan ではガード部分がパターンマッチングになっている多くのプロセスがチャンネル通信する Erlang は Occam 言語とそっくり詳しくは中身を読もう

3 RPC RPC: Remote Procedure Call 遠隔手続き呼び出し遠隔にある手続きを同期的に呼び出す ( 最近は非同期的な RPC もある ) 遠隔の手続きは仕事が終わると返り値をもどす同期的呼ばれた側の仕事が終わるまで呼び出し側は止まるバグが出にくい素朴な実装の場合呼ばれる側の関数は同時に複数入ってこないため簡単で良い ( 再入可能性の検討など不要 ) 非同期的呼ばれた側は呼び出し側と無関係に仕事を進める終了の通知方法は? 仕事の結果を置く場所は? 呼び出し側は正しくハンドリングするか

4 チャンネル通信 CSP Communicating Sequential processes Hoare( ホーア ) が考えたチャンネルで通信する普通のプログラム排他制御の問題とか出ない基本の構想は RPC に近い CSP は戻り値もチャンネル通信で返さねばならないが非同期的な呼び出しも可能デッドロックが起こりにくいデッドロック発生の検出が容易最近の TCP コネクションごとに thread を貼り付けるのも近い考え

5 P3 プロセス P1 P2 受信待ちガード1 実行 1 ガード2 実行 2 シーケンシャルなプログラム ( プロセス ) の集まりで仕事をする主に RPC を用いて

6 CSP をもとにした現実システム Inmos 社 ( 英 ) Transputer と Occam を実現して販売していたイギリスの国策会社 ST Micro に吸収された Occam プログラミング言語 Transputer Occam と同時に考えられたハードウェア CPU をトランジスタのごとく並べて使用

7 Transputer CSP をもとにした現実システム Occam と同時に考えられたハードウェア CPU をトランジスタのごとく並べて使用 Transputer は Transistor + Computer という造語 4~8 本のシリアル通信ハードウェアを持つ多数の CPU を 2 次元のメッシュ or3 次元以上のハイパーキューブ状に配置しシリアルリンクで近傍を接続遠くへの通信は近傍の CPU に順次リレーしてもらう Transputer は CPU コア上にタスク ( スレッド ) をハードウェアレベルで実装 jump 命令を実行するたびにスケジューリングとタスクスイッチデフォールトのスケジューラはハードウェアラウンドロビン方式ユーザがソフトウェアで書いたスケジューラに切り替えることも可能あるベクトルにユーザのスケジューラルーチンの先頭のポインタを置くとそのスケジューラルーチンが呼び出される全盛期は FPU が高速でコストパフォーマンス良し C 言語でプログラミング ST-20 は Transputer のこと

8 Occam CSP をもとにした現実システムプログラミング言語 Occam のかみそり不要なものはそぎ落とせから来た名前チャンネル通信 Communicating Sequential Processes Committed Choice 言語ガードがあるインデントに意味がある区切り記号が少ない専用の構造化エディタでプログラムを書いた

9 ALT Occam のプログラム断片例この辺がガードと言える input1? packet output! packet input2? packet output! Packet ALT が ComminttedChoice の指定プリミティブ複数の候補のうちガード ( 上記では受信 ) を満たした先着の一つだけが選ばれその実行部が実行される Occam のガードは通信しか書けない

10 Committed Choice ガードを設けてガードを超えたものが実行を開始する CSP/Occam 通信もガード条件の一種 GHC: Guarded Horn Clause 上田さんが考えた ( 当時 NEC) AND 並列 Prolog の一種 Prolog の節のコミットバー! までをガードとする GHC ではコミットバーはガード記号と呼ばれるチャンネル通信をしていると考えるべし通常はバックトラックしない

11 Erlang ST Micro がハードウェア設計 / 検証のために作ったと言われている変数を使用したチャンネル通信ガードがありガードを超えた節が排他的に実行されるパターンマッチングにユニフィケーションを使用節のヘッドでのパターンマッチングは prolog のようだが実行の意味は違う型がない関数呼び出し時にパターンマッチングする言語としては ML が有名だが ML は強い型の言語テレコムアプリケーションを書いた実績あり

12 Erlang のプログラム例 rcv_messages() -> receive {foo, X} -> io:fwrite( foo~n"), ture; {bar, X} -> io:fwrite( bar~n"), ture; rcv_messages(). ここがガードガードは -> の直前まで receive の受けの部分は単純変数, 定数タプルなどのパターンが書ける. 単純変数を書くと Occam などのチャンネルからの受信変数になる

13 RPC 指向の言語の排他制御 1 つのシーケンシャルプロセスに資源を持たせそのプロセスのみが資源をアクセスするいわゆるサーバサーバに資源を持たせれば排他制御の問題は起こらない何でもかんでも安全というわけではない例えばサーバの中から別なサーバを呼び出すようなことをするとデッドロックが起きるかも知れない広い意味でモニタを構成しているとも考えることができるメッセージパッシングするオブジェクト指向風モニタ

14 用語

15 並行計算用語並行と並列並行 concurrent 論理的に同時に計算が行われていると考えられる場合プロセスは理論的な言葉で並行とともに用いられることが多い (UNIX はタスクというべきものをプロセスと名付けた ) 並列 parallel, simultaneous 実際に同時に複数のものが動作する on the fly という場合もまれにある ( 放っておいても動作するハードウェアに対していうことがほとんど )

16 並行計算用語再入可能 reentrant いくつものプロセスが同時に呼び出し可能 thread safe とはすなわち再入可能であるということどうやって実現するのか?

17 排他制御並行計算用語複数のプロセスが同時に使用できない資源などを守る OS 的には排他制御と待ちは組である同期と排他は本質的には同じ排他は同期の問題にも還元可能きわどい領域 critical section 排他制御の必要な領域 ( 主にプログラムコード上 ) 不可分 atomic 基本操作マルチプロセス動作するときこれ以上分割すると不条理なことが起こる時不可分であるという不可分操作 atomic operation 機械語レベルであると割り込みに邪魔されないということ ( 単一 CPU の時 )

18 デッドロック dead lock 並行計算用語資源を取り損なってシステムが止まる排他制御の失敗による排他制御の必要な資源の設計のミスによる一般に排他的な資源を複数押さえることが可能なシステムでは起きる誰が資源を押さえているか調べるライブロック live lock 広義のデッドロックに含まれるシステムとしては生きているが一部の資源がとれずに一部の仕事が永遠に遅延 ( 封鎖 ) される資源を押さえる手順がレーシング追いかけ状態に陥っている

19 代表的な排他制御 / 同期のプリミティブセマフォ (semaphore) セマフォが得られれば資源の使用権を得られたと考えるオランダ人の Dijkstra( ダイクストラ ) の発案 P/V (Wait/Signal) 命令が基本 Wait でセマフォを得る /Signal でセマフォを返す腕木信号の用語しかもオランダ語 1bit のバイナリセマフォカウンティングセマフォ ( カウンタが 0 でなければ資源を使用可能 ) mutex はセマフォの一種モニタ (monitor) きわどい領域を一つの手続きにしそこに一人 ( または許された数 ) しか入れないようにシステムが制御 Java が採用ランデブー (rendezvous), バリア (barrier) 全員がそろうまで待つその他交換変数 (Exchange) などもあるがあまり知られていない実用性もない待ちには spin lock などがある

20 より低位な排他制御 / 同期のプリミティブ test and set 命令メモリの内容をアトミックに書き換え書き換え前の状態をテストするセマフォを test and set 命令で実現するでもそれがそのままプロセスの待ちに使用できるか? Read modified write 命令である load-store アーキテクチャの RISC システムにそんなものはない CISC には好んで付けられた LL/SC (Load and Link/Store Conditional) 命令 ( 近代的な ) キャッシュメモリの機能使用法 1) load link を行って古い値を得る 2) 権利が得られそうか? 得られなければもっと違うレベルの待ちへ 3) 更新する値を作る 4) SC で新しい値を書き込む 5) SC の結果が失敗であれば 1 へ LL はキャッシュに CPU コアからのアクセスがあったことを記憶 SC の実行前に他の CPU コアで LL アクセスがあれば SC が失敗するキャッシュ同士が LL アクセスがあったことを通信する

21 セマフォは協調型 semaphore みんながセマフォアクセスを正しく行わねばならないセマフォを見ない人がいたら競合が起こるセマフォを返さない人が居たら資源は永久封鎖デッドロック解析が難しい ( と一般に思われている ) 普通の人は解析手法を持たない

22 monitor モニタは出るときに権利を失うのでたちがいい協調型ではないので馬鹿な人が居ても間違いは起きにくい実行時間がかかりすぎるとか永久封鎖とかがモニタ中に存在すると問題モニタから他の資源を押さえに行って押さえられないとかそれが原因でデッドロックとかアプリケーションが馬鹿だと何を使ってもデッドロックする Java のモニタはモニタから他のモニタを呼べない ( はず ) よって単純なデッドロックは起こらない

並列計算

並列計算 OS 系低レイヤな人のための Transputer とか CSP Occam Erlang 2011/MAY/22 ( 訂正版 2) たけおか 1 前置き本筋とまったく関係ない 2 代表的な排他制御 / 同期のプリミティブセマフォ (semaphore) セマフォが得られれば資源の使用権を得られたと考えるオランダ人の Dijkstra( ダイクストラ ) の発案 P/V (Wait/Signal)