並行プログラミング言語(1)

並行システム

                               システム情報系情報工学域,
			       システム情報工学研究科コンピュータサイエンス専攻
                               新城 靖
                               <yas@cs.tsukuba.ac.jp>

このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2011/2012-02-09
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/

■今日の重要な話

• 並行プログラミング言語
• 永続プログラミング言語
• 分散プログラミング言語

参考文献

R.E. フィルマン, D.P. フリードマン著, 雨宮 真人, 尾内 理紀夫, 高橋 直 久 (訳): "協調型計算システム -- 分散型ソフトウェアの技法と道具立て", マグロウヒル (1986). ISBN-10: 4895010309.

Marko Boger: Java in Distributed Systems: Concurrency, Distribution and Persistence, John Wiley & Sons, 2001. ISBN: 0471498386

■Concurrent Pascal

• プロセス（スレッド）
  • 逐次プログラム
  • 固有データ
  • アクセス権
• モニタ。プロセス間の同期。条件変数含む。
• クラス。コードを実行するプロセスが高々１つ。コンパイラによる。
• 条件変数とキュー。

◆参考文献

Per Brinch Hansen著, 田中英彦訳: "並行動作プログラムの構造", 日本コン ピュータ協会 (1980).

◆プロセス

type procA_t = process(引数・・・);
   var
      局所データの宣言
   procedure proc1(引数・・・);
   procedure proc2(引数・・・);
begin
   cycle
       ・・・
   end;
end

var procA1 : procA_t ;
init procA1(引数);

◆モニタ

type monA_t = monitor(引数・・・);
   var
      局所データの宣言
   procedure entry proc1(引数・・・);
   procedure entry proc2(引数・・・);
begin
   ローカルデータの初期化;
end

var monA1 : monA_t ;
init monA1(引数);

◆条件変数とキュー

  cv1 : condition;
  cv1.wait;      呼び出したプロセスを待たせる。
  cv1.signal;   待っているプロセスがいれば全て再開させる。

  q1 : queue;
  delay(q1);      呼び出したプロセスをそのキューで待たせる。
  continue(q1);   そのキューで待っているプロセスがいれば１つだけ再開させる。

◆有限バッファ

producer | consumer

バッファが空の時、consumer() は、producer() が何かデータをバッ ファに入れるのを待つ。バッファがいっぱいの時、producer() は、 consumer() がバッファから何かデータを取り出すのを待つ。

手続き

• put(x:integer)
• get(result x:integer);

   1: const BUFFER_SIZE = 4;
   2: type circular_buffer =
   3: monitor
   4: var
   5:     rp : integer ;
   6:     wp : integer ;
   7:     data: array [0..BUFFER_SIZE-1] of integer;
   8:     used: integer;
   9:     not_empty : condition;
  10:     not_full  : condition;
  11: 
  12:     procedure entry put(x:integer);
  13:     begin
  14:         while( used = BUFFER_SIZE ) do
  15:             non_full.wait;
  16:         data[wp] := x;
  17:         wp := wp + 1 ;
  18:         if( wp >= BUFFER_SIZE )
  19:             wp := 0 ;
  20:         used := used + 1 ;
  21:         not_empty.signal;
  22:     end
  23: 
  24:     procedure entry get(result x:integer);
  25:     begin
  26:         while( used = 0 ) then
  27:             not_empty.wait;
  28:         x := data[rp];
  29:         rp := rp + 1 ;
  30:         if( rp >= BUFFER_SIZE )
  31:             rp := 0 ;
  32:         used := used - 1 ;
  33:         not_full.signal;
  34:     end
  35: begin
  36:     rp := 0 ;
  37:     wp := 0 ;
  38:     used := 0 ;
  39: end;
  40: 
  41: ...
  42: var buf : circular_buffer ;
  43: init buf;
  44: ...
  45: 

• 外から呼び出せる手続きには、entry と付ける。
• 手続きの引数や局所変数は、それが呼び出されている時だけ使える。
• モニタ内の変数は、呼び出されていない時もずっと存在する。
• モニタを呼び出せるプロセスは高々１つ（相互排除がなされる）。
• ロック、アンロックは明示的には書かない。
• モニタでは再帰呼出し禁止。コンパイラによるチェック。デッドロックを防ぐ。
• プロセス間のデータの交換は、モニタを通じてのみ行える。
• モニタは、条件変数やキューが複数持てる。
• 任意の変数で待てるのではなく、条件変数やモニタでだけ待てる。
• init 文が実行されると、モニタの begin と end の間が実行される。init は１回だけ。

■Communicating Sequential Processes

• CSP は、モデル言語（処理系がない）
• CSPのプログラムは、明示的に通信するプロセスの集合。プロセスは静的 で、増減しない。再帰呼出しは禁止。
• 出力文（メッセージの送信）、入力文（メッセージの受信）がある。
• ガード付きコマンドで非決定性を記述する。

◆通信とプロセス

Process A:

...
B ? x;   -- プロセス B からの通信を待つ。
         -- メッセージを受け取り、変数 x へ保存。
B ! x*2; -- プロセス B へ値 x * 2 を送る。
...

Process B:

...
y := 5;
A ! y + 1; -- プロセス A へ値 5 を送る。
...
A ? y;     -- プロセス A からの通信を待つ。
           -- メッセージを受け取り、変数 y へ保存。

プロセスを指定する名前付けでは、ライブラリが作れない。マクロでごまかす。

◆制御構造、ガード付きコマンド、非決定性

ガード → 節

ガード付き節。条件式。 「→」の左がすべて真なら、「→」の右を実行する。

* [ <test> → <action> ]

繰り返し。while test do action <test>の部分は、ガード(guard)と呼ばれる。 ガードには、単純な条件式の他に、入力（受信）が書ける。出力（送信）は書けない。

名前::...

プロセスの名前付け。

||

並行実行。A || B で、プロセス A と B が並行に実行される。

□　(正方形ではなく、縦長に書くのが正確。)

alternative command。非決定性の記述。

name ( val1, val2 )

構造体の定義。name が構造体の名前。val1, val2 は値。 フィールドには名前がつけられない。

(x,y) := (y,x)

名前がない構造体の代入。 並行に実行されるので、これで変数のswapが可能。

マクロ名 ≡ 本体

マクロ定義。

プロセスの配列 P(0..n)

意味としては、プロセスがマクロ展開される。 プロセスは添字で区別される。

Merge:: c:character;
        *[    X ? c → Sink ! c
           □ Y ? c → Sink ! c
           □ Z ? c → Sink ! c ]

◆有限バッファ

   1: [ Buffer::
   2:     buf(0..bufsize-1): buffer_element;
   3:     first, last : integer;
   4:     j,k         : integer;
   5:     first :=0;
   6:     last :=0;
   7:     * [ (j: 1..numprod)
   8:         (last + 1) mod bufsize ≠ first;
   9:         Producer(j) ? buf(last) →
  10:             last := (last +1) mod bufsize
  11:         □
  12:         (k: 1..numcons)
  13:         first ≠ last;
  14:         Consumer(k) ? more() →
  15:             Consumer(k) ! buf(first);
  16:             first := (first + 1) mod bufsize
  17:       ]
  18: || (i:1..numprod) PRODUCER -- 生産者のプログラム
  19: || (i:1..numcons) CONSUMER -- 消費者のプログラム
  20: ]

• プロセス Buffer は、Producer からデータを受け取り、 配列 buf(last) に入れる。
• プロセス Buffer は、Consumer から more() というメッセージを 受け取った時に、 Consumer に対して、データ buf(first) 入れる。

◆Occam

■Ada

• 米国国防省(DoD)が決定した組み込みシステムを記述するための言語。
• 例外処理、平行処理、分散処理、実時間処理を容易に記述できる ことが目的
• Pascal 風の文法
• ACM SIGPLAN Notices 誌で、紙上討論。

◆タスク

• task型のインスタンスを生成できる。
• 局所変数と局所手続きを持つ。
• 生成されると、実行を開始する。
• プログラムの終わりに来ると終了。明示的に終了させられる。エラーで 異常終了することがある。
• タスクの中にタスクが書ける。
• 再帰呼出しも可能。再帰で暗黙的にタスクが生成されることがある。

◆仕様と本体

仕様(specification)

インタフェースの記述。プログラムの他の要素から参照できる。仕様だ けわかれば、分割コンパイルできる。

本体(body)

プログラムのコード、変数など。

◆エントリ

仕様の例。１行のバッファ。

task line_block is
    entry add( c: in character);
end  line_block;

受け側の例

accept add( c: in character) do
    thisline(i) := c;
end add;

呼出し側の例

    line_block.add("d");

◆ランデブ

• ランデブは、２つのタスクが共に並んで実行していることを連想させる。 宇宙船のランデブと同じ。 ただし、プログラムは、accept側に書く。
• Adaのランデブは、相互排除に利用される。ランデブ中は、際どい領域 (critical section)であり、１つのタスクしか動かない。

◆select文

select
    when  条件 =>
        accept ... do ... end;
or
    when  条件 =>
        accept ... do ... end;
or
    when  条件 =>
        delay seconds;
end

• 「when 条件 =>」は、書かなくてもよい。
• accept 分の代わりに、delay 文(時間切れ記述)も書ける。
• else で、何も選ばれない時の動作が書ける。

開いているエントリ

when の条件が真

閉じているエントリ

when の条件が偽

◆ラインプリンタのバッファ

• エントリ add() で、文字を受け取る。
• 120文字溜めてプリンタに送る。
• プリンタが印刷中で受け付けない時には、add() を受け付けない。

   1: type line is array (1..120) of character;
   2: 
   3: task line_block is
   4:     entry add( c: in character);
   5:     entry plese_print( ln: out line);
   6: end  line_block;
   7: 
   8: task body line_block is
   9:     printer_trouble_time  : constant integer := 300;
  10:     print_line, fill_line : line;
  11:     nextfree              : integer;
  12:     print_ready           : boolean;
  13: begin
  14:     nextfree    := 1;
  15:     print_ready := false;
  16:     loop
  17:         select
  18:             when (nextfree < 121 ) =>
  19:                 accept add( c: in character) do
  20:                     fill_line(nextfree) := c;
  21:                 end add;
  22:                 nextfree := nextfree + 1;
  23:                 if( next_free = 121 ) and not print_ready then
  24:                     print_ready := true;
  25:                     nextfree    := 1;
  26:                     print_line  := fill_line;
  27:                 end if;
  28:         or
  29:             when print_ready =>
  30:                 accept please_print( ln: out line ) do
  31:                     ln := print_line;
  32:                 end please_print;
  33:                 if nextfree = 121 then
  34:                     print_line := fill_line;
  35:                     nextfree   := 1;
  36:                 else
  37:                     print_ready := false;
  38:                 end if;
  39:         or
  40:             when print_ready and (nextfree > 120) =>
  41:                 delay printr_trouble_time;
  42:                     printer_trouble;
  43:         end select;
  44:     end loop;
  45: end line_block;

■分散型プログラミング言語一般論

プログラミング言語は、ネットワークの存在や通信をさまざまな度合いで隠し ている。

問題:

• どこまで隠せば分散型プログラミング言語と呼んでもよいか？

◆分散型ＯＳとネットワークＯＳ

ネットワークの機能はある。

利用者は、常にどの計算機を使っているのかを意識する必要がある。

コマンド

• sh <-> rsh
• cp <-> rcp
• ls, less <-> WWW ブラウザ

• pipe <-> socket
• /../host1/usr/local/bin (スーパーディレクトリ)

分散型オペレーティング・システム

利用者は、仮想的な１台の計算機を使っているように感じ、計算機と計算機の 境界線が見えなくなる。分散透明性（network transparency）が実現されてい る。

目標

• 負荷均衡(load balncing)。プログラムを走らせると、自動的に空いてい る計算機に送られ、実行される。
• フォールト・トレランス。障害が発生したとしても、自動的に復旧させ たり、自動的に他の計算機に仕事を回す。
• 集中型システムで開発されたプログラムを一切変更することなく、ネッ トワーク上の資源を利用することができるようになる。

• NFS。ネットワーク・ファイル・システム。 分散型ファイルシステムではない。
• NIS。パスワード・ファイルの共有。

注意: 負荷分散の分散(load sharing/balancing)とこの講義のタイトルの分散 (distributed)は意味が違う。

◆ローカルとリモートの統合

A note on Distributed Computing [Waldo 1994]

• 呼出しがローカルでもリモートでも「形式的な正しさ」は同じ。 オブジェクトの位置は、プログラムの正しさには影響しない。
• オブジェクトのインタフェースは、オブジェクトが使われるコンテキス トから独立している。
• 分散アプリケーションは、ローカルアプリケーションと同じ方法で 実現できる。
• 故障や性能の側面を考える必要がある。（初期段階では考えなくてもよい。）

◆ローカルのプログラミングと分散のプログラミングの違い

• 1970年代。socket()。CSP、Occam。
• 1980年代。RPC。
• 1990年代。ORB。
• 2000年代。コンポーネント。

◆分散の難しい問題

例:

• 部分的に落ちている(partial failure)
• レイテンシ。光の速度は越えられない
• 参照。ポインタを動するか
• 並行性
  • 非決定性の扱い
  • 同期の難しさ

◆RMI付Javaは、分散型プログラミング言語か

• public しか呼べない。
• オブジェクト・マイグレーションはない。
• リモートのコンストラクタが呼べない。名前サービスを通じてアクセス する。factory object (オブジェクトを生成するオブジェクト)を使えばよい が、ローカルとリモートの透明性は下がっている。
• 非同期的な呼出しはできない。スレッドでエミュレート可能ではある。 標準で並列性がまったく出ない。

◆分散型プログラミング言語の要件

1. 位置と型の直行。
2. 遠隔オブジェクト生成
3. ローカルとリモートを区別したい時には区別できる
4. ローカルとリモートを区別したくない時には区別しないでよい
5. Garbage colection
6. オブジェクト・マイグレーション
7. グループ化
8. 同期呼出しと非同期呼出しの両方の支援
9. 分散でも、並行性を言語で支援したい

分散の難しい問題は、まだ汎用的に解ける技術はない。 汎用性がないと、プログラミング言語には採り入れにくい。

◆分散型プログラミング言語で分散システムが作れるか

■Emerald

一般的な特徴

• 純粋なオブジェクト指向。全てのデータ型、構造体がオブジェクト。
• 強い型付け。abstract type (インタフェース)
• 動的なオブジェクトの追加が可能。
• 多態(polymorphism)
• クラスはない。継承もない。手続きを繰り返し定義する。

Emerald の目標。

• 分散透明性。メソッド呼出しは、ローカルとリモートで同じ。
• オブジェクトレベルの移動性。 オブジェクトは、いくつねに、 コンピュータの境界を越えて移動可能である。 オブジェクトが自分自身を移動(migrate)させることがある。
• 効率。ローカル・オブジェクトへのアクセスは、(分散ではない言語と同 じように)可能な限り直接的に効率よく行われる。ネットワーク通信なしにロー カルの呼出しかリモートの呼出しかを決められる。

◆Emeraldの参照

メソッド呼出しの引数も参照で渡される。オブジェクトの場所が違うと、重た い。コピーの方が速い。

◆Emeraldのオブジェクト・マイグレーション

move X to Y

オブジェクト X を、オブジェクト Y のあるホストに移動。ヒント (システムは実際には移動させないこともある)。

fix X at Y

オブジェクト X を、オブジェクト Y のあるホストに移動して、 さらに動かないように固定する。

unfix X

オブジェクト X を、再び移動可能にする。

refix X at Z

fix されているオブジェクト X を、オブジェクト Z のあるホストに移 動して、さらに動かないように固定する。全体が atomic に行われる。

Call by reference が重たい。

call by move

引数をオブジェクトの方に移動させる。

call by visit

メソッドがリターンすると、オブジェクトも戻ってくる。

call by move return

結果のオブジェクトも戻ってくる。

■Voyager

• 遠隔にオブジェクトの生成ができる。Factory.create()。
• (Glue同様に) 名前がついたオブジェクトを アクセスもできる。Namespace.lookup()。
• 分散GCを含む。
• オブジェクトの移動ができる。自分自身の移動もできる。
• アプレット間通信通信を支援。voyager がハブになる。
• マルチキャストができる。
• オブジェクトをメモリから追い出してデータベースに保存できる。
• CORBA, DCOM, RMI ともつながる。
• 2001 年、ObjectSpace 社から Recursion Software 社へ。 http://www.recursionsw.com/products/voyager/voyager-intro.html

◆Voyagerのオブジェクトの公開

import com.objectspace.voyager.*;

public class BallMachine  {

    public static void main(String[] args) {
		try {
			Voyager.startup("8000"); // als Server starten
			Ball ball = new Ball();
			Namespace.bind("EinBall",ball);
		} catch( Exception exception ) {
			System.err.println( exception );
		}
    }
}

◆Voyagerのオブジェクトの利用

import com.objectspace.voyager.*;

public class Bat {

    public void play(IBall ball) {
		System.out.println("Hitting the new Ball");
		ball.hit();
    }

    public static void main(String[] args) {
		try {
		    Voyager.startup(); // als Client starten
			Bat bat = new Bat();
			IBall ball = (IBall) Namespace.lookup("//vsyspc5.informatik.uni-hamburg.de:8000/EinBall");
			bat.play(ball);
		} catch( Exception exception ) {
			System.err.println( exception );
		}
		Voyager.shutdown();
    }  
}

◆Voyagerのリモート・リファレンスと移動

    IMobility mobileObj = Momility.of(obj);
    mobileObj.moveTo("url");

import com.objectspace.voyager.*;
import com.objectspace.voyager.mobility.*;

public class Bat {

   public void play(IBall ball, String url) {
	  try {
		 ball.hit();
		 System.out.println("Ball bewegen?");
		 Mobility.of(ball).moveTo(url);
		 System.out.println("Ball bewegt");
	  } catch (MobilityException e) {
		 System.out.println(e);
		 e.printStackTrace();
	  }
   }

   public static void main(String[] args) {
      try {
		 Voyager.startup("9001"); 
		 ClassManager.enableResourceServer();
		 Bat bat = new Bat();
		 //Ball newball= new Ball();
		 IBall ball = (IBall) Proxy.of(new Ball());
		 bat.play(ball,"//vsyspc5:8000");
		 System.out.println("Ball 1ste mal gespielt");
		 bat.play(ball,"//localhost:9001");
      } catch( Exception exception ) {
	    System.err.println( exception );
      }
      Voyager.shutdown();
   }
}

◆Voyagerの非同期メソッド呼出し

    IA a1 = (IA) Factory.create("A","//sun:8000");
    a1.method(param1,param2);  // 同期 

    Result r1 = Future.invoke(object, "method", // 非同期
        new Object [] {param1,param2});
...
    if( result.isAvailable() )
    {
       int x = r1.readInt();
    }

◆Voyagerのマルチキャスト

    ISubspace subspace = (ISubspace) Namespace.lookup("//sun:9000/Subspace");

    A a1 = new A();
    subspace.add(a1);
    A a2 = new A();
    subspace.add(a2);

    a1.method1( param1, param2 );
    a2.method1( param1, param2 );

    Object [] params = new Object [] { param1, param2 };
    Multicast.invoke(subspace,"method1",params,"A");

■Dejay

• 分散Javaの１つ。ソース・プログラム一見、Javaに見えるが、Javaではない。 Java のコンパイラでは通らないものがある。
• Dejay コンパイラが出力する オブジェクト・コードとしては、 Java のバイトコード(.class) を使う。
• 実行時には、Voyager の機能を利用している。
• コンパイラの実装には、OpenJava [Tatsubori 1997] が使われている。

◆Dejeyのオブジェクト

• 拡張子 .dj。
• 遠隔で実行するものは、java.io.Serializable を implementsする。

public class Hello implements java.io.Serializable  {
    public void sayHello(java.lang.String name) {
        System.out.println("Hello " + name);
    }
}

• Hello.class
• DjHello.class (-l オプション つけると、ローカル専用となり、 生成されない)

◆Dejeyの起動コード

	
import dejay.base.*;
public class HelloStartup {
    public static void main(String args[])
    {
        try {
	    DjProcessor p1 = new DjProcessor("//localhost:8000");
	    DjHello hello1 = new DjHello(p1);
	    hello1.sayHello("Thorsten");
	    p1.moveTo("//localhost:9000");
	    hello1.sayHello("Jan");
	    hello1.moveTo("//mac:9000");
        } catch (ConstructProcessorFailedException e) {
            System.out.println("Creating Virtual Processor failed."+e);
        }
    }
}

• DjHello型 (遠隔参照型) 。ローカルと同じに扱えるが、 実行は遠隔になる。moveTo() メソッドを持つ。
• DjProcessor 型。オブジェクトを実行するプロセッサを抽象化したもの。 voyager デーモンを起動したホスト。
• moveTo() メソッドで移動できる。 DjProcessor 単位でも、オブジェクト単位でも移動できる。

◆DjProcessor

    DjProcessor p1 = new DjProcessor("hostname:port");

◆遠隔オブジェクト

    DjA a1 = new DjA( Aの引数・・・, DjProcessor );

    DjA a2 ;
    a2 = ... ;
    ...
    if( a2 == a1 ) // 遠隔のオブジェクトではなくてローカルのスタブの比較
    {
       ...
    }

ローカル・オブジェクトを引数にして、 リモート・オブジェクトを呼ぶと、自動的に遠隔にコピーが渡される。 （遠隔オブジェクトが作られて、遠隔参照が渡されるのではない。）

DjX 型のオブジェクトを 遠隔にリターンすることはできる。 DjX がみつからなければ、 Xのコピーが返される。

remote.getCopy() で、ローカルのコピーが得られる。

    DjA a1 = new DjA(p1);
    A a2 = a1.getCopy();

◆メソッド呼出しのセマンティクス

    DjA a1 = new DjA(p1);
    B b1 = a.method1( 10 );		 // 同期
    B b2 = a.method1( 10, Dejey.ASYNC ); // 非同期
    a.method1( 10, Dejay.ONEWAY );       // 一方向

    B b1 = a.method1( 10, Dejey.ASYNC );
    b1.method2(); // wait by nesessity

    B b2 = a.method1( 10, Dejey.ASYNC );
    if( b2.isAvailable() )
    {
        b2.method2();
    }
    else
    {
        // do something
        b2.waitForResult();
        b2.method2();
    }

◆Dejeyの名前サービス

２レベルの名前。

• 仮想プロセッサの名前
• 仮想プロセッサ内の名前

    DjProcessor p1 = new DjProcessor("lin:8000");
    p1.registerByName("p1");
    DjA a1 = new DjA(p1);
    a1.registerByName("a1");

    DjProcessor p1 = Dejay.getProcessorByName("p1");
    DjA a1 = p1.getObjectByName("a1");

◆永続性

• 分散ができれば、ネットワークに送る代りにファイルの保存すれば永続になる。
• 永続ができれば、ファイルを共有することで、分散になる。

    DjProcessor p1 = new DjProcessor("PersistProc","ProcesssorDB","lin:8000");
    DjA a1 = new DjA();
    if( p1.isPersistable ) {
       p1.persist();
       p1.flush();
    }

persist() でデータベースに保存されたオブジェクトも、 使われる自動的にデータベースから回復される。

仮想プロセッサ全体がデータベースに保存できる。 次のようにして回復できる。

    DjProcessor p1 = Dejay.getProcessorFromDB("PersistProc",
        "ProcesssorDB","lin:8000");

◆制限

• Java 標準クラス、final がついているものは、 遠隔参照で送れない。String などは必ずコピーになる。
• final とついたメソッドもスタブには含まれない。
• (メソッド呼出しではなく) 変数の直接アクセスができない。
• static 変数は、仮想プロセッサごとにコピーが作られる。移動もできない。
• Object クラスのメソッドは全部遠隔に送られる。
• Dejay での並行性は、本来は、スレッドはなく仮想プロセッサで表現すべきだが、 スレッドも使える。 複数のスレッドを含んだ仮想プロセッサを移動させると おかしくなる。
• synchronized は、リモートではなくローカルのスタブで働く。
• ローカル・オブジェクトをリモートオブジェクトにする方法がない。
• DjA の生成で、DjA のコンストラクタと A のコンストラクタの 両方が呼ばれる。

練習問題

★問題(801) CSPとAda

★問題(802) Voyager

★問題(803) VoyagerとDejay