並行プログラミング言語、トランザクション/Concurrent Programming Languages

並行システム

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

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

■連絡事項

次回、5月30日の連絡が、Manaba でなされることがある。 次回の授業の前に、Manaba を見ること。

■今日の重要な話

参考文献 References

■Concurrent Pascal

2016年4月18日

■Communicating Sequential Processes

C. A. R. Hoare: "Communicating sequential processes", Communications of the ACM, Volume 21 , No.8 pp.666-677, 1978. http://portal.acm.org/citation.cfm?doid=359576.359585

◆CSPの通信とプロセス/Communication and processes in CSP

直接名前付けの通信(direct naming)。通信相手のプロセスを明示的に指定する。 (<−>間接では、メール・ボックスを指定する。)

Process A:

...
B ? x;   -- プロセス B からの通信を待つ。 Wait for a message from Process B.
         -- メッセージを受け取り、変数 x へ保存。 Receive a message and store it into the variable x.
B ! x*2; -- プロセス B へ値 x * 2 を送る。Send the value x * 2 to Process B.
...

Process B:

...
y := 5;
A ! y + 1; -- プロセス A へ値 6 を送る。Send the value 6 to Process A.
...
A ? y;     -- プロセス A からの通信を待つ。Wait for a message from Process A.
           -- メッセージを受け取り、変数 y へ保存。Receive a message and store it into the variable y.

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

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

ガード(guard) → コマンド(command)
ガード付きコマンド。条件式。 「→」の左がすべて真なら、「→」の右を実行する。
* [ <test> → <action> ]
繰り返し。while test do action <test>の部分は、ガード(guard)と呼ばれる。 ガードには、単純な条件式の他に、入力(受信)が書ける。出力(送信)は書けない。
名前::...
プロセスの名前付け。
||
並行実行。A || B で、プロセス A と B が並行に実行される。
 (正方形ではなく、縦長に書くのが正確。 (Unicode ▯))
alternative command。非決定性の記述。
name ( val1, val2 )
構造体の定義。name が構造体の名前。val1, val2 は値。 フィールドには名前がつけられない。
(x,y) := (y,x)
名前がない構造体の代入。 並行に実行されるので、これで変数のswapが可能。
マクロ名 ≡ 本体
マクロ定義。
プロセスの配列 P(1..n)
意味としては、プロセスがマクロ展開される。 プロセスは添字で区別される。
マージ・プロセスの例。プロセスX, Y, Zのいずれかから送られてきたメッセー ジを受け取り、それをプロセス Sink に送る。
Merge:: c:character;
        *[   X ? c → Sink ! c
           □ Y ? c → Sink ! c
           □ Z ? c → Sink ! c ]

◆有限バッファ/bounded buffer in CSP

   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: ]

◆Occam

Occam は、Inmos 社が CSP を元にして開発した言語。 Transputer は、Occam を実行するためのハードウェア。

■並行オブジェクト指向モデル/Concurrent object-oriented models.

オブジェクト指向の一種。世の中をオブジェクトとして扱う。

◆アクタモデル/The Actor models

1977年 C.Hewitt らによって提唱された並行計算モデル。 アクタと呼ばれる計算主体が独立に、かつ、並列に計算を行う能力を持つ。 アクタ内部も可能な限り並列に実行できる枠組みを持つ。

言語としては、何種類か(Plasma、Act-1、Act-2、Act-3、Omega、Ether)ある。 各言語で見かけがけっこうちがう。

アクタ、メッセージ、メールボックス

図? アクタの基本概念/Basic concepts of the Actor model

アクタは、メッセージを受け取り、それに対して行為を行うような、通信を行う エージェントである。行為の種類には、次のようなものがある。

アクタは、メッセージを受信するために1つのメールボックスを持つ。 メッセージは、アクタに直接届くというよりは、メールボックスに間接的に届 く。メールボックスは、バッファリングの機能がある。メールボックスにある メッセージは、FIFO に処理されるとは限らない。

アクタがメッセージを受け取ると、いったんロックされる。ロックされるとメッ セージは処理されない。次のアクタに become したら、新しい後継のアクタが 同じメールボックスからメッセージを読み出して処理を続ける。

要素

アクタは、メッセージを送受信できる。 メッセージ自身も、アクタの一種。

◆アクタの継続/Continuations in Actor

継続(continuation、継続点ともいう)を用いる。 究極の goto 文。C 言語の関数で
    goto f(1, 2, 3);
のようなもの。

通常の階乗(in Scheme)

(define (fact n)
    (if (= n 0) 1
        (* n (fact (- n 1)))))
継続を取るような階乗
(define (fact-c n c)
  (if (= n 0)
      (c 1)
      (let ((c2 (lambda (x) (c (* n x)))))
        (fact-c (- n 1) c2))))

実行例

> (fact 3)[←]
6
> (fact 4)[←]
24
> (fact-c 3 print)
6> (fact-c 4 print)[←]
24> []

◆階乗/Factorial in Actor

[Hewitt 77a]
factorial≡λm.
  match m <n c>
    if n = 1 then
      (send c <1>)
    else if n > 1 then
      (send factorial <(n-1) (λk.(send c <n * k>))>)
3の階乗を計算して、継続print_answerに送りたい時には、 次のように書く。
   (send factorial <3 print_answer>)

◆階乗/Factorial in Actor

(define (Factorial( ))
  (Is-Communication (a doit (with customer =m)
		       (with number =n)) do
      (become Factorial)
      (if (NOT (= n 0))
	(then (send m 1))
	(else (let (x = (new FactCust (with customer m)
			     (with number n)))
		(send Factorial (a doit (with customer x)
				   (with number (- n 1)))))))))
(define (FactCust (with customer =m)
		  (with number =n))
  (Is-Communicaton (a number k) do
    (send m (* n k))))
振る舞い記述
    (define (名前 (with id パタン))
      通信ハンドラの並び)

通信ハンドラ
    (Is-Communication パタン do コマンド)

letコマンド
    (let (変数名 = 式) do コマンド)

条件コマンド
    (if 式 (then do コマンドの並び) (else do コマンドの並び))

メッセージ送信コマンド
    (send メールボックス 値)

becomコマンド
    (become 式)

新しいアクタの生成
  (new 式)

◆銀行口座/A bank account in Actor

(define (Account (with Balance =b))
  (Is-Request (a Balance) do 
    (become (Account (with Balance b)))
    (reply b))
  (Is-Request (a Deposit (with Amount =a)) do
    (become (Account (with Balance (+ b a))))
    (reply (a Deposit-Receipt (with Amount a))))
  (Is-Request (a Withdrawal (with Amount =a)) do
    (if (> a b)
      (then do 
        (become (Account (with Balnce b)))
        (complain (an Overdraft)))
      (else do 
        (become (Account (with Balnce(- b a))))
	(reply (a Withdrawal-Receipt (with Amount =a)))))))

◆カウンタ(Scala)/Counter actor in Scala

Ted Neward: "多忙な Java 開発者のための Scala ガイド: Scala の並行性を掘り下げる", IBM DeveloperWorks, 2009年 4月 10日. http://www.ibm.com/developerworks/jp/java/library/j-scala04109.html

Ted Neward: "The busy Java developer's guide to Scala: Dive deeper into Scala concurrency", IBM DeveloperWorks, 10 Apr 2009. http://www.ibm.com/developerworks/java/library/j-scala04109.html

リスト 9. Counter の例 (アクターによる方法) より。

object CountingSample
{
  case class Incr
  case class Value(sender : Actor)
  case class Lock(sender : Actor)
  case class UnLock(value : Int)

  class Counter extends Actor
  {
    override def act(): Unit = loop(0)

    def loop(value: int): Unit = {
      receive {
	case Incr()   => loop(value + 1)
	case Value(a) => a ! value; loop(value)
	case Lock(a)  => a ! value
			 receive { case UnLock(v) => loop(v) }
	case _        => loop(value)
      }
    }
  }

  def main(args : Array[String]) : Unit =
  {
    val counter = new Counter
    counter.start()
    counter ! Incr()
    counter ! Incr()
    counter ! Incr()
    counter ! Value(self)
    receive { case cvalue => Console.println(cvalue) }    
    counter ! Incr()
    counter ! Incr()
    counter ! Value(self)
    receive { case cvalue => Console.println(cvalue) }    
  }
}

■Voyager

Glue 2002年 の Graham Glass より作成されたJava 用の分散オブジェクト。 (Voyager の方が古い。1998年。) 現在の Java RMI よりも、優れている点がある。

◆Interface and local objects

import com.objectspace.voyager.*;

public interface IBall {

public void hit();

}
import com.objectspace.voyager.*;

public class Ball implements IBall {

	public void hit() {
		System.out.println("Ball has been hit");
    }
}

◆Voyagerのオブジェクトの公開/Publishing objects in 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のオブジェクトの利用/Using remote objects in 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のリモート・リファレンスと移動/ Remote references and object migration in Voyager

Proxy.of(obj) で、リモートリファレンスを生成する。 Mobility.of(obj)で、移動可能なオブジェクトを動的に生成する。

    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の非同期メソッド呼出し/Asynchronous object invocation

非同期メソッド呼出しがある。

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

    Result r1 = Future.invoke(a1, "method", // 非同期 asynchronous
        new Object [] {param1,param2});
...
    if( r1.isAvailable() )
    {
       int x = r1.readInt();
    }
メソッド名を文字列で渡す。結果として、Result 型を返す。isAvailable() メソッドで終了を待つ。readInt(), readByte(), readObject() で、int, byte, オブジェクトに戻す。

◆Voyagerのマルチキャスト/Multicast in Voyager

Voyager Space を使ってマルチキャストができる。
    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");

■トランザクション/Transaction

相互排除、デッドロックより高いレベルの抽象が欲しい。 We need better abstracts than mutual exclusion and dead locks.

ロックよりも楽にプログラムを作りたい。 We would like to write programs more easily than that with locks.

特に分散では。集中でも、フォールト・トレランスの実現では必要。 Especially in distributed systems. Transaction is essential to realize fault tolerance.

◆トランザクションの意味/Transaction semantics

商談は、成立するか、しないか。 all or nothing。

歴史:1960年代、テープの時代。 失敗したら、巻き戻す(rollback)。

銀行口座間の預金の移動。

  1. 口座1から出金
  2. 口座2に入金

◆トランザクションを実現するための命令/Transaction operations

◆ACID

Atomic
外の世界からみると1つ。中間状態が見えない。不可分。
Consistency
不変量(invariant)を保つ。例:口座間の預金の移動。預金の総額は不変。
Isolated
並行するトランザクションは、孤立している。直列化可能(serializable)
Durable
Commit すると永続的。

◆直列化可能(serializable)

注意:Java の serializable とは意味が全く違う。

複数のトランザクションは、並行に実行可能。しかし、その複数のトランザク ションの最終結果は、それらを「ある順序」で「逐次的に」実行した時と同じ結果 になる。

逆に、トランザクションは、直列化可能なスケジュールが存在するなら、並行 に実行してもよい。直列化可能でないなら、トランザクションは、開始を遅ら せるか、アボートする。

トランザクション、複数並行実行

図? トランザクションの処理(並行実行)/Concurrent execution of transactions

トランザクション、直列化

図? トランザクションの処理(直列化の例その1)/A serialized execution of transaction No.1

トランザクション、直列化

図? トランザクションの処理(直列化の例その2)/A serialized execution of transaction No.2

トランザクション、直列化

図? トランザクションの処理(直列化の例その3)/A serialized execution of transaction No.3

◆例/An example

航空券の乗り継ぎの予約のプログラムの例。 成田からサンフランシスコ経由でオーランドまで行きたい。
Begin_Transaction();
  reserve("NRT-SFO");
  reserve("SFO-MCO");
Commit();
プログラムの記述としては、これだけ。どこにもロックは出てこない。内部的 には、ロックは行われる(ことがある)。

途中の reserve() が失敗したら、トランザクション全体を abort() する。

◆入れ子トランザクション(nested transactoin)

目的 親が abort されたら、子供が commit したものも無効になる。

◆トランザクションの実装(集中)/Implementation of transaction in centralized systems

◆プライベート作業空間/Private work space

全てのデータをコピーすると重たい。

ファイルのコピー、インデックス、ブロック、copy-on-write

図? ファイルの変更されたブロックだけをコピー)

◆先行書き込みログ(write-ahead log)

実行予定リスト(intentions list)

シャドー・コピーを作らず、ファイルのその場所を書き換える。 その前に、次の情報を安定記憶にログとして書き込む。

コミットされると、何もしない。 アボートされると、ログを後ろから前に読み込み undo する。

クラッシュからの回復もできる。

◆安定記憶(stable storage)

RAM
電源が落ちると消える
ディスク
ディスクヘッドのクラッシュで消える
安定記憶
洪水や地震でも生き残るように設計されている。
安定記憶の実現方法:2個のディスクの組みを使う(図?(a))。

テキスト、データ、スタック複数

図? 安定記憶の実現

更新時:
  1. ディスク1のあるセクタに書き込む。
  2. ディスク1からそのセクタを読み込む。
  3. 内容を比較する。同じなら、ディスク2の同じ位置に書き込む。

3 の前にクラッシュしても、常にディスク1が正しい(図?(b))。 この場合は、ディスク1からディスク1へコピーする。

チェックサムエラーが起きた場合(図?(c))、他のディスクからコピーして回復する。

◆並行性制御/Concurrency Control

できるだけ効率のよい、直列化可能なスケジューリングを求める。

◆ロッキングによるトランザクションの実装/Implementing transactions by locking

もっとも単純な方法: Begin Transaction で、ファイルをロックする。 Commit/Abort でアンロックする。

注意:プログラマは、ロックを意識しない。

制約が強すぎる。

読み取りロック:read lock と write lock を分ける。

ロックの粒度(granularity)が大事

小さくする
並列性が高まる。ロック自体のオーバヘッドが増える。 デッドロックが起こりやすくなる。
大きくする

◆2相ロック/Two phase locking

デッドロックが起きにくい、直列化可能な方法。
第1相(growing phase)
ロックの数が増える一方
第2相
ロックの数が減る一方

横軸、時刻、縦軸、ロックの数、第1相、増える、第2層、減る

図? 2相ロック/Two-phase locking

定理:トランザクションの実現で2相ロックを使うならば、インターリーブさ れることで作られるスケジュールは直列化可能である。

実際のシステムでは、Commit/Abort するまで、一度確保したロックをはなさない。 第2相で、まとめて全部ロックを解放する(strict two-phase locking)。

横軸、時刻、縦軸、ロックの数、第1相、増える、第2層、一発で減る

図? 2相ロック/Strict two-phase locking

利点

2相ロックでも、デッドロックは起きる。

注意:2相ロックと2相コミットは別。

◆楽観的並行性制御/Optimistic concurrency control

どんどんやって、後でまずかったことがわかった時点で abort する。 衝突が稀である時に有効。

実現(衝突時の対応):プライベート作業空間を使う実現が便利。 どんどんプライベート作業空間上のファイルを更新して、最後にコミットする か削除する。

性質

◆タイムスタンプによるトランザクションの実装/Implementing transactions with time stamps

操作にタイムスタンプを付けて、まずいものをアボートする。

アルゴリズム:

楽観的:同じファイルを独立したトランザクションで同時にアクセスすること は、あまりない。

Lamport のアルゴリズム等でクロックが同期されていれば、分散システムでも 使える。

◆分散システムにおける2相コミットによるトランザクションの実装/Implementing transactions with Two-phase commit in distributed sysems

2相コミット(two-phase commit)は、分散システムにおけるトランザクション の実装方法。(注意: 2相ロック(two-phase lock)ではない)。

2種類のプロセス

2つの相
第1相
全プロセスを Commit も Abort もできる状態にする。
  1. コーディネータは、ログに「準備」と書く。
  2. コーディネータは、サブオーディネートに「準備」メッセージを送る。
  3. サブオーディネートは、ログに「準備完了」と書く。
  4. サブオーディネートは、コーディネータに「準備完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
第2相
実際に Commit する。
  1. コーディネータは、ログに「コミット」と書く。
  2. コーディネータは、サブオーディネートに「コミット」メッセージを送る。
  3. サブオーディネートは、ログに「コミット完了」と書く。
  4. サブオーディネートは、コーディネータに「コミット完了」メッセージを送る。
  5. コーディネータは、全てのサブオーディネートからの応答を待つ。
クラッシュした時には、ログから回復させる。

■Argus

トランザクション機能を内部に含む言語。 発音は、英語読みでアーガス。ギリシャ神話読みでは、アルゴス。

Barbara Liskov: "Distributed programming in Argus", Communications of the ACM, Vol.31, No.3, pp.300-312, 1988. http://dl.acm.org/citation.cfm?id=42399

文法は、CLU 言語に似ている。

参考:

◆ガーディアン(guardian)

並行に動作するオブジェクト(現在の用語ではスレッド)を実現する。

◆安定な変数(Stable variable)

ガーディアンは、2種類の局所変数を持つ。
安定(stable)
クラッシュ(再起動)しても、生き残る。
揮発(volatile)
クラッシュ(再起動)すると、値が失われる。

◆アクション(action)

安定な変数に対するトランザクションを実現する。安定な変数を、整合性がと れた状態から、次の整合性がとれた状態へ遷移させる。( 途中でクラッシュしたら、元に戻す。)

トップアクション
トップレベルのトランザクションを実現する。commit するか abort するか。 内部にサブアクションを持つ。 abort したら、内部のサブアクションもすべて abort。
サブアクション
ネストしたトランザクションを実現する。
他のガーディアンのハンドラの呼出し(遠隔手続き呼び出し)は、 サブアクションになる。

◆Argusにおけるトランザクションの実装/Implementation of Transaction in Argus

◆ガーディアンの宣言/Declaration of guardians

  1. 名前 Name
  2. 生成ルーチン。引数の取得。Routines
  3. 安定な変数。Stable variables
  4. 揮発的な変数。Volatile variables
  5. ハンドラ手続き(外から呼ばれるエントリ)。Handlers
  6. バックグランド・ルーチン。ガーディアン自身のプログラム。 Backgroud routines.
  7. 復旧手続き。クラッシュ後に実行され、揮発的な変数を状態に戻す。 Recovery procedures.
安定な変数については、システムが自動的に整合性が取れた状態に復旧する。

◆銀行の支店/A bank branch in Argus

   1: branch = guardian is create handles total, open, close, deposit, withdraw
   2:   % type definitions
   3:   htable = atomic_array[bucket]
   4:   bucket = atomic_array[pair]
   5:   pair = atomic_record[num: account_number, acct: acct_info]
   6:   acct_info = atomic_record[bal: int]
   7:   account_number = atomic_record[code: string, num: int]
   8:   intcell = atomic_record[val: int]
   9: 
  10:   stable ht: htable    % the table of accounts
  11:   stable code: string  % the code for the branch
  12:   stable seed: intcell % the seed for generating new account numbers
  13: 
  14:   create = creator (c: string, size: int) returns (branch)
  15:     code := c
  16:     seed.val := 0
  17:     ht := htable$new()
  18:     for i: int in int$from_to(1, size) do
  19:       htable$addh(ht, bucket$new())
  20:     end
  21:     return (self)
  22:   end create
  23: 
  24:   total = handler () returns (int)
  25:     sum: int := 0
  26:     for b: bucket in htable$elements(ht) do
  27:       for p: pair in bucket$elements(b) do
  28:         sum := sum + p.acct.bal
  29:       end
  30:     end
  31:     return (sum)
  32:   end total
  33: 
  34:   open = handler () returns (account_number)
  35:     intcell$write_lock(seed) % get a write lock on the seed
  36:     a: account_number := account_number${code: code, num: seed.val}
  37:     seed.val := seed.val + 1
  38:     bucket$addh(ht[hash(a.num)], pair${num: a, acct: acct_info${bal: 0}})
  39:     return (a)
  40:   end open
  41: 
  42:   close = handler (a: account_number) signals (no_such_acct, positive_balance)
  43:     b: bucket := ht[hash(a.num)]
  44:     for i: int in bucket$indexes(b) do
  45:       if b[i].num != a then continue end
  46:       if b[i].acct.bal > 0 then signal positive-balance end
  47:       b[i] := bucket$top(b) % store topmost element in place of closed account
  48:       bucket$remh(b) % discard topmost element
  49:       return
  50:     end
  51:     signal no_such_acct
  52:   end close
  53: 
  54:   lookup = proc (a: account_number) returns (acct_info) signals (no_such__acct)
  55:     for p: pair in bucket$elements(ht[hash(a.num)]) do
  56:       if p.num = a then return (p.acct) end
  57:     end
  58:     signal no_such_acct
  59:     end lookup
  60: 
  61:   deposit = handler (a: account_number, amt: int) signals (no_such_acct, 
  62:                                                                 negativ_amount)
  63:     if amt < 0 then signal negative_amount end
  64:     ainfo: acct_info := lookup(a) resignal no_such_acct
  65:     ainfo.bal := ainfo.bal + amt
  66:   end deposit
  67: 
  68:   withdraw = handler (a: account_number, amt: int) signals (no_such_acct, 
  69:                                          negative_amount, insufficient_funds)
  70:     if amt < 0 then signal negative amount end
  71:     ainfo: acct_info := lookup(a) resignal no_such_acct
  72:     if ainfo.bal < amt then signal insufficient_funds end
  73:     ainfo.bal := ainfo.bal - amt
  74:   end withdraw
  75: end branch

■投機的実行/Speculative execution

投機的実行(speculative execution)、将来利用されるか利用されないか確定さ れる前に実行を開始してしまうこと。楽観的実行(optimistic execution)とも言う。

    if( a() ) {
        b();
    }
    else {
        c();
    }

if( a ) then b else c

図? 投機的実行 Speculative execution

この例では、a() が完了した時には、b()、c() が終わっていた時には、見かけ 上、即座に終わる。

■Jini

Jini (ジニー)は、Java を中核にした、情報家電製品を相互接続するための通 信技術。

1999年に、サン・マイクロシステムズ社のビル・ジョイらによって開発され発 表された。

Jini の目標は、ネットワークで Plug & Play を実現すること。 機器をネットワークに接続しただけで、特別な設定 をしなくてもすぐに利用可能になること。

目標

サービスには、ハード的なもの(プリンタ、ディジタルカメラ、CD Player) の他に、ソフト的なもの(スペルチェック、翻訳、アドレス帳)がふくまれる。

JavaSpaces は、内部的に Jini のルックアップ・サービスの実現で使われて いる。JavaSpaces も、Jini でアクセス可能なサービスの1つと考えることも できる。

Jini のクラスライブラリは、 JavaSpaces の回 で紹介した Apache River が利用できる。

◆UPnP (Universal Plugand Play)

Microsoft の、Jini に対抗した技術。

◆ルックアップ・サービス/Loockup service in Jini

Jini中心的な技術が、ルックアップ・サービス。

サービスの登録と検索

ルックアップ・サービス自身も、最初から知られている必要はない。 ネットワーク上で自動的に探される。 Discovery と Join。

◆リース/Leasing

サービスは、永続的に登録されるではなくて、 特定の時間だけ利用可能になる。

Java のオブジェクトが Lease。

リース期間は、延長することができる。 延長されなかった lease は、ルックアップ・サービスから削除される。 登録されているサービスを明示的に削除する仕組みは、存在しない。

サービスが削除された時には、分散型イベント配送サービスにより関係してい る所に知らされる。

トランザクションのインタフェースは定められているが、具体的な実現は各サー ビスにまかされている。

◆Jiniを使うのに必要とされているもの/Requirements to run Jini

IPアドレスの割り当ては、Jiniの一部ではない。

◆サービス/Services

サービスは、Java のオブジェクトで実現される。

サービスの提供者とサービスの利用者の間は、最終的にはに RMI で接続される。

ServiceIDLister インタフェースを implements する。

package com.sun.jini.lookup;
public interface ServiceIDListener extends java.util.EventListener {
    void serviceIDNotify(net.jini.core.lookup.ServiceID serviceID);
}
ルックアップ・サービスからコールバックされる。

◆Discovery と Join/Discovery and Join

各ネットワークには、ルックアップ・サーバを置く。

Discovery
Jini を使うには、まず、ルックアップ・サーバを探す。
Join
サービスの提供者が、インタフェースと属性をルックアップ・サーバに 登録する。

Discovery の実現方法

ルックアップ・サーバは、起動時、再起動時、224.0.1.84:4160 にMulticast Announcement Protocol で、利用可能性を広告する。

サービスの提供者がネットワーク上のルックアップサービスをマルチキャストで探す。

図1 マルチキャストによる Discovery/Discovery by multicast

サービスの提供者がルックアップサービスにサービスオブジェクトを登録する。

図2 Join

◆サービスのグループ/Grouping services

サービスは、1つ以上のグループに属する。

グループは、名前(文字列)で区別される。

名前としては、DNS 風の表記のものが推奨されている。

◆JoinManager(サーバ側)/JoinManager at the server-side

Discovery と Join は、規格上は、ネットワーク・プロトコルになっている。

Jini パッケージは、JoinManager という参照クラスを含む。

    public JoinManager(Object obj,  Entry[] attrSets,
                       ServiceIDListener callback,
                       LeaseRenewalManager leaseMgr)
        throws IOException
    public JoinManager(Object obj, Entry[] attrSets, String[] groups,
                       LookupLocator[] locators,
                       ServiceIDListener callback,
                       LeaseRenewalManager leaseMgr )
        throws IOException

◆Jiniのサーバの例/Example of a Jini server

import java.rmi.*;

public interface RemoteBall extends Remote {
   public void hit() throws java.rmi.RemoteException;
}
import java.rmi.*;
import java.rmi.server.*;
import net.jini.core.lookup.*;
import com.sun.jini.lookup.*;

public class Ball extends UnicastRemoteObject 
                  implements RemoteBall, ServiceIDListener {
   public Ball() throws RemoteException {
      super();
   }
   public void serviceIDNotify(ServiceID id) {
      System.out.println("ServiceId is "+id);
   }
   public void hit() {
      System.out.println("Ball has been hit");
   }
}

import java.rmi.*;
import net.jini.core.entry.*;
import net.jini.lookup.entry.*;
import com.sun.jini.lookup.*;
import com.sun.jini.lease.*;

public class BallStarter {
   public static void main(String[] args) {
      try {
         System.setSecurityManager(new RMISecurityManager());
         RemoteBall ball = (RemoteBall) new Ball();
         LeaseRenewalManager renewal = new LeaseRenewalManager();
         Entry[] attributes = new Entry [] { new Name("Jini enabled ball")};
         JoinManager join = new JoinManager( ball, attributes, (Ball) ball, renewal );
         System.out.println("Ball started and registered at Lookup-Server");

      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}

◆Lookup(クライアント側)/Lockup in a client

クライアントは、サービスを探す。

サービスの利用者がルックアップサービスに対してサービスオブジェクトを検索する。

図3 Lookup

サービスは、次の3つで区別される。 サービスを検索する時に ServiceTemplate のオブジェクトを作成する。 JavaSpaces のように、null を指定すれば、ワイルドカードを意味する。
    public ServiceTemplate(ServiceID serviceID,
                           Class[] serviceTypes,
                           Entry[] attrSetTemplates)
サービス(オブジェクト)の探し方
  1. LookupLocator により、マルチキャスト、または、 ユニキャストで ルックアップ・サービスを探す。
  2. ルックアップ・サービスのプロキシ ServiceRegistrar を作る。
  3. テンプレートを作り、ServiceRegistrar に渡す。
サービスを見つける過程で、サービス(オブジェクト)のRMI のスタブ(クライ アント側スタブ)が転送される。

◆サービスの利用/Using a service

最終的にクライアントは、サービス・プロバイダを RMI で呼び出す。

サービスの利用者がサービスオブジェクトを通じてサーバを利用する。

図4 Invoke

◆Jiniのクライアントの例

import java.rmi.*;
import net.jini.core.discovery.*;
import net.jini.core.lookup.*;

public class Bat {

   public Ball ball;

   public void play(RemoteBall ball) {
      try {
         ball.hit();
         System.out.println("I hit the ball");
      } catch (RemoteException e) {
         System.out.println(e);
      }
   }

   public static void main (String[] args) {
      Bat bat = new Bat();
      try {
         System.setSecurityManager(new RMISecurityManager());
         LookupLocator locator = new LookupLocator("jini://localhost");
         ServiceRegistrar registrar = locator.getRegistrar();
         Class[] classes = new Class[] { RemoteBall.class  };
         ServiceTemplate template = new ServiceTemplate( null, classes, null);
         RemoteBall remoteBall = (RemoteBall) registrar.lookup(template);
         bat.play(remoteBall);
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}

◆Leasing

信頼性が低いネットワークと、どう戦う方法の1つ。

lease には、期限がある。

期限の長さは、交渉可能。 期限が短い(1分以下、数秒)というのは、あまり想定されていない。

リースの利点

Jini のサービスを提供しているオブジェクトは、Lease インタフェースを実 装している。

public interface Lease {
    long FOREVER = Long.MAX_VALUE;
...
    long getExpiration();
    void renew(long duration)
        throws LeaseDeniedException, UnknownLeaseException, RemoteException;
    void cancel() throws UnknownLeaseException, RemoteException;
...
}
getExpiration() で、リースの残り時間がわかる。ミリ秒単位。

renew() で延長する。 延長できない時には、LeaseDeniedException が返される。

もう使わなくなった時には、cancel() できる。 期限切れと同じことになる。

リースの管理には、LeaseRenewalManager を使う。

練習問題

次の内容を含む「テキスト」ファイルを作成し、 レポート提出ページ から提出しなさい。 締切りは、2016年5月29日、 23:59:59 とする。 以下の *全て* の問いについて答えなさい。 Answer *all* of the following questions.

★問題(501) CSP and Concurrent Paccal

CSP と Concurrent Paccal を比較し、本質的な類似点と本質的な相違点を簡単に説明しなさい。

Compare CSP and Concurrent Paccal, and describe an essential similarity and an essential difference.

★問題(502) Actorの並列性/Concurrency in Actor

Actorモデルで、並行性をどのように表現しているか。簡単に説明しなさい。

How does the Actor model express concurrency? Explain it briefly.

★問題(503) Argus

Argus 言語のガーディアンと次のどれかと対比しなさい。本質的な類似点1つ と本質的な相違点1つを述べなさい。 Compare guardians in the Argus language with elements in one of the following languages. Describe an essential similarity and an essential difference.
Last updated: 2016/05/23 15:03:06
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>