タプル空間(Tuple Space)、Linda、JavaSpaces、Ruby Linda(Rinda)

並行システム

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

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

■今日の重要な話

並行(並列)プログラムの作り方 how to write concurrent (parallel) programs 参考文献 References

■並行プログラミングのパラダイム paradigms for concurrent programming

並列/分散プログラムのデザイン・パタン。 Design patterns for parallel and distributed programs.

◆並列プログラムを構築する手順 Steps to write parallel programs

  1. 問題に適したパラダイムを選ぶ Choose the paradigm that is most natural for the problem.
  2. パラダイムに合った手法(Methods)でプログラム書く Write a program using the method that is most natural for that paradigm.
  3. 性能が十分でない場合には、プログラムを変換する。 if the resulting program is not acceptably efficient, transform it methodically into a more efficient version by switching from a more-natural method to a more efficient one.

◆パラダイム1(Paradigm 1):結果並列法(Result Parallelism)

並列処理の最終結果に焦点を当る。 we might envision parallelism by starting with the finished product, the result.

例: 家の建築: House building

◆パラダイム2(Paradigm 2):専門家並列法 (Specialist Parallelism)

並列処理を行う作業者に焦点を当る。 we might envision parallelism by starting with the crew of workers who will do the building.

例: 家の建築:

◆パラダイム3(Paradigm 3):手順並列法 (Agenda Parallelism)

並列処理の手順(agenda、課題)に焦点をあてる。 we might envision parallelism in terms of an agenda of activities that must be completed in order to build a house.

例: 家の建築:

◆どのパラダイムを使うか Choose a paradigm

問題にあったものを使う。 Choose the paradigm that is most natural for the problem.

実際の家の建築では、全部の方法が使われている。 All paradigms are used in real house building.

◆結果並列法の使い方 Useing result parallelism

簡単。 結果のデータ構造を得るための依存関係が予めわかっている時に便利。

うまく行く例:ベクトルの足し算(adding vectors): S[i] = A[i] + B[i]

  1. n 要素のベクトルを作る
  2. S[i] は、A[i] と B[i] を加えればわかる。
以下のようなもの適していない。 Not suitable for following applications.
テキスト処理(text processing)、コンパイラ(compilers)
結果が可変
LU分解 (LU decomposition)
繰り返しがある
OS、実時間システム(realtime systems)
結果というよりは作用が大事

◆専門家並列法の使い方

プロセスのネットワークが作られる。単純な例。

プロセス、矢印、線形

図? パイプラインの例/An example of a pipe line

プロセス、2次元配列、メッシュ

図? シスとリックアレイの例(1)/An example of a systolic array (1)

プロセス、2次元配列、メッシュ、斜め回線

図? シスとリックアレイの例(2)/An example of a systolic array (2)

複雑な例:輸送時間見積もり
プロセス
道路(都市)
データ
トラック
道路が並列。複数のデータが流れる。

◆手順並列法の使い方 Using agenda parallelism

マスタ・ワーカ master-worker
  1. マスターが計算を始める
  2. 同一のワーカ・プロセスの集合を作る
  3. ワーカ、どの仕事でもやる。
  4. 仕事がなくなれば終わり
うまく行く例: データベースの項目から、ある関数の値が最小のものを探す

  1. マスターは、袋(task bag)の中にデータ・レコードを全部入れる
  2. 各ワーカは、袋から取り出して(複雑な)関数の計算を行い、 結果をマスターに返す
  3. マスターは、ワーカから送られてきたものの最小のものを記録する。
  4. 全部が終われば終わり。

タスクバッグ、ワーカ、タスク

図? タスクバッグ

◆その他の並列パラダイム Other paradigm

■プログラミングの手法 Programming methods

視点

◆手法1(Method 1):ライブデータ構造体(Live Data Structure)

関数型言語は、これ。

データの中にプロセスが活動する。

図? ライブデータ構造体 live data structure

◆手法2(Method 2):メッセージパッシング(Message Passing)

共有メモリなしで、並列処理をするものは、これ。 マルチスレッドの特殊な場合。ロックを使わずに、TSD (Thread Specific Data) と通信だけでプログラムを書く場合はこれ。

プロセス中にデータがある。

図? メッセージ・パッシング message passing

◆手法3(Method 3):分散データ構造体(Distributed Data Structure)

共有メモリのマルチスレッドは、TSD (Thread Specific Data) をのぞいてだいたいこれ。

データとプロセスが独立。

図? 分散データ構造体 distributed data structures

◆N-体問題シミュレータ N-body problem simulator

N個の物体の位置をq時間単位分計算する。

◆N-体問題:結果並列法 N-body problem: result parallelism

ライブデータ構造体の図 参照。

位置の配列: M[i][j]、i=0..N-1, j=0..q、M[][0] に最初の位置。

position(i,j), 繰り返し j での 物体 i の位置を計算する。 その時、一つ前のステップの位置 position(i,j-1) (i=0..N-1) の処理が終了するのを待つ。

プロセスは、position(i,j) の計算をするとデータに化けて行く。 ライブデータ構造体の図 で、 赤い丸は活動中のプロセス。黒い丸は終了したプロセス。

◆N-体問題:専門家並列法 N-body problem: specialist parallelism

物体に対応したプロセスを作る。

◆N-体問題:手順並列法 N-body problem: agenda parallelism

手順(ワーカの仕事):集合に含まれている全ての物体について、次の位置を 計算する。

マスタで、N 個の物体を作る。

ワーカを作る。ワーカの数は、N 個ではなくて、もっと少ない(CPU数と同じに する)。

物体の位置を分散データ構造体(共有メモリ)に置く。

◆並列プログラムを書く方法 構築する手順 Steps to write parallel programs

  1. 問題に適したパラダイムを選ぶ Choose the paradigm that is most natural for the problem.
  2. パラダイムに合った手法(Methods)でプログラム書く Write a program using the method that is most natural for that paradigm.
  3. 性能が十分でない場合には、プログラムを変換する。 if the resulting program is not acceptably efficient, transform it methodically into a more efficient version by switching from a more-natural method to a more efficient one.
(粒度の調整)

◆パラダイム間の関係 relationship among paradigms

分散データ構造体、ライブデータ構造体、メッセージパッシング

図? パラダイム間の関係 relationship among paradigms

アブストラクション(abstraction)
データとプロセスの結び付きを切る
スペシャリゼーション(specialization)
データとプロセスから分離して分散データ構造体におく
クランピング(clumping)
通信を明示的に行うようにする
デクランピング(declumping)
通信を暗黙的に行うようにする
問題1: ライブデータ構造体でプログラムを書いたらプロセス生成が多くて 性能が出ない。

解決1:ライブデータ構造体を、受動的な構造体に書き換える。プロセスを複数 の構造体に対応させる。

問題2:分散データ構造体で書いたプログラム(共有空間が必要)が、 NORMA で うまく動かない。

解決2:メッセージ・パッシングに変換する。

Carriero と Gelernter の主張:分散データ構造体がいい。

Java では、スレッド、RMI、Javaspaces、ラムダの順に導入された。

◆プログラミング言語とライブラリ

1. ライブデータ構造体 live data structures
データフロー: Id Nouveau
関数型言語: Multilisp, Sisal
2. 分散データ構造体 distributed datat structures
言語:HPF (High Performance Fortran)
共有メモリとロック/セマフォ
DSM: Orca, Munin, Midway, Linda
3. メッセージパッシング message passing
特殊言語:CSP/Occam
RPC、ランデブ:Ada
ライブラリ:PVM, MPI
モニタ(Monitors):Concurrent Pascal, Modula

モニタは、メッセージパッシングの仲間か分散データ構造体か。

■Linda

Linda は、協調言語。 Linda is a coordination language. 計算言語と協調言語参照 See also computational languages and coordination languages

タプルペースモデル(tuple space model)で分散データ構造体(distributed datat structures)を支援。(メッセージ・パッシング(message passing)やラ イブデータ構造体(live data structures)的なプログラムも書ける。)

◆タプル空間(tuple space)

タプル空間は、タプルの集まり。 A tuple space is a collection of tuples.

タプルは、型付きの値の並び。 A tuple is a series of typed values.

タプルの例 Examples of tuples:

("a string", 10.01, 17, 10)

(0,1)

2種類のタプル two kinds of tuples

データタプル data tuples
受動的 passive
ライブタプル(プロセスタプル) live tuples (process tuples)
全部が同時に実行している。 データタプルを読み書きする。 終了するとデータタプルに変化する。 The process tuples (which are all executing simultaneously) exchange data by generating, reading, and consuming data tuples. A process tuple that is finished executing turns into a data tuple, indistinguishable from other data tuples.

◆NUMAとタプル空間

速いローカルメモリと遅い大域的な共有メモリ。 Fast local memory and slow shared memory. 非均質共有メモリ型マルチプロセッサ(shared memory multiprocessor with non-uniform memory access)参照。

◆Lindaの命令/ Linda operations

タプル空間を操作する基本4命令
out(t)
タプルtをタプル空間内に生成する(データタプル)。 causes tuple t to be added to TS. (a data tuple).
in(s)
テンプレート s にマッチするタプル t を取り去る。 タプルがなければ、呼び出し側はブロックする。 in(s) causes some tuple t that matches template s to be withdrawn from TS. If there is no tuple, the caller blocks.
rd(s) -- (read)
in と似ているが、タプルがタプル空間に残る。 タプルがなければ、呼び出し側はブロックする。 rd(s) is the same as in(s) except that the matched tuple remains in TS. If there is no tuple, the caller blocks.
eval(t)
out() と似ているが、新たにプロセスが作られて、そのプロセスによりタ プルが評価される(ライブタプル)。 eval(t) is the same as out(t), exept that t is evaluated by a new process. (a live tuple).
術語(predicate)つきの命令。デッドロック(deadlock)対策で使う。 (今日の課題では使わない。)
inp(s)
in(s) と同じだが、見つからなければ 0 を返す。 inp(s) is the same as in(s), exept that this returns 0 immediately if it fails.
rdp(s)
rd(s) と同じだが、見つからなければ 0 を返す rdp(s) is the same as rd(s), exept that this returns 0 immediately if it fails.

◆formal and actual variables

in(), rd() では、「?」付きの変数 formal 変数が使える。 「?」が着いていなものは、actual 。
float f; int i,x;
out("a string", 10.01, 17, x)

in("a string", ?f, ?i, y)

◆プロセス生成 process creation

eval("e", 7, exp(7))
新しくプロセス(スレッド)が作られ、exp(7) を計算しはじめる。プロセスが 終了すると、最終結果は、値に変わり、out() されたのと同じになる。

◆同期 synchronization

in()/rd() と out() で同期がとられる。out() はブロックしない。in() は条件に よりブロックする。
out() し、タプルがある状態で in()/rd()
in() したプロセスはブロックしない
out() する前、タプルがない状態で in()/rd()
in() したプロセスはブロックする。 out() されるとブロック解除。

◆大域的なカウンタ変数の例 / An example of a global counter valiable

初期化:
    out("counter-17",0)

読込み read:
    int val;
    rd("counter-17",?val)

変更 update:
    int val;
    in("counter-17",?val)
    val = val + 1 ;
    out("counter-17",val)
Pthread では、mutex が必要になる所、Linda では不要。
宣言:
    int counter_17;

読込み read:
    int val;
    pthread_mutex_lock( &mutex1 );
    val = counter_17;
    pthread_mutex_unlock( &mutex1 );

変更 update:
    int val;
    pthread_mutex_lock( &mutex1 );
    val = counter_17;
    val = val + 1 ;
    counter_17 = val;
    pthread_mutex_unlock( &mutex1 );

◆計数セマフォ counting semaphores

初期化:
    out("sem-1"); /*初期値が 4 の場合。*/
    out("sem-1");
    out("sem-1");
    out("sem-1");

P命令/down/aquire/wait: 
    in("sem-1")

V命令/up/release/signal:
    out("sem-1");
同じタプルを out したら溜る。

注意:in() したデータは、1プロセスでしかアクセスされないので、セマフォ などによるロックは不要。

初期値が 1 なら、バイナリ・セマフォ。

今日の課題のアクセスカウンタでは、セマフォは使わない。 大域的なカウンタ変数の例 を真似する。

◆Task Bags

仕事を入れる add a task:
    out("task",TaskDescription);

仕事を取り出す remove a task:
    in("task",?NewTask);

◆並列DOループ/ parallel do-loop

逐次プログラム a sequential program:
for( i=0 ; i<N; i++ )
{
    func(i,args);
}
並列プログラム a parallel program:
for( i=0 ; i<N; i++ )
{
    eval ("loop-33", func(i,args) ); // プロセス生成 process creation, fork
}
for( i=0 ; i<N; i++ )
{
    in("loop-33", 1 ); // 待ち, join
}

func(i,args)
{
   ...
   return( 1 );
}
これは並列処理の fork-join モデルを実現した物。

single-fork==multi==join-single-thread

図? fork-join model

◆バリア同期 barrier synchronization

全部のプロセスが到着してから次に進む。

single-fork==multi==join-single-thread

図? fork-joinの繰り返し

single-fork===barrier==barrier===barrier===

図? fork-joinの繰り返し

n プロセスのバリア

初期化:
    out("barrier-37",n)
各プロセス: 1減らして、0になるのを待つ。
    in("barrier-37",?val)
    out("barrier-37",val-1)
    rd("barrier-37",0)

◆配列 arrays

C言語 C language
    A[10];

Linda tuple space
    ("A",0,val00)
    ("A",1,val01)
    ("A",2,val02)
    ...
    ("A",9,val99)
2次元配列 an two-dimensional array.
C言語 C language
    A[10][10];

Linda tuple space
    ("A",0,0,val00)
    ("A",0,1,val01)
    ("A",0,2,val02)
    ...
    ("A",9,9,val99)

◆ストリーム(inストリーム) / in-streams

1人が読むとデータが消える。 容量が無限のバッファ(unbounded buffer)と同じ。 スレッドの例で示したのは、容量が有限の 有限バッファ(bounded buffer)

three sources,an in-stream,threee sinks

図? Linda in-stream

ストリームデータ stream data
    ("stream",0,val0)
    ("stream",1,val1)
    ("stream",2,val2)
    ...

ポインタ pointers
    ("stream","head",0)
    ("stream","tail",0)
ストリームに要素を追加 add an element to a stream:
    int index; // ローカル変数
    in("stream","tail",?index);
    out("stream","tail",index+1);
    out("stream",index,new_element);

ストリームから要素を取り出す take an element from a stream:
    int index; // ローカル変数
    in("stream","head",?index);
    out("stream","head",index+1);
    in("stream",index,?element);
これは、複数source、複数sink。

source、sinkが1つなら、head, tail をタプル空間に置かなくてもよい。

◆ストリーム(readストリーム) / read-streams

1つのストリームを、複数の読み手でアクセスできる(マルチキャスト(multicast))。

head の代わりに、局所変数でアクセスする。

ストリームから要素を取り出す take an element from a stream:
    int index=0 ;
    ...
    rd("stream",index++,?element);

rd() しかなされず、in() する人がいないので、タプル空間にストリームのデー タが残ってしまう。

◆メッセージ・パッシングのプログラムの書き方/ how to write programs with message passing

◆ライブ・データ構造体のプログラムの書き方/ how to write programs with live data strucures

■JavaSpaces

Linda のタプル空間 の考え方を Java で実現したもの。

interface JavaSpace を実現したオブジェクト
Linda JavaSpace 説明
out write タプルをタプル空間内に生成する。
in take タプルを取り去る
rd read in/takeと似ているが、タプルがタプル空間に残る。
ライブタプル(eval命令)は、ない。

write, read, take を使う部分のプログラムは簡単だが、space を利用可能に するのには苦労する。

JavaSpaces が提供する空間の特徴

◆interface Entry

空間に置くことができるオブジェクトは、interface Entry を implements し たもの。

net/jini/core/entry/Entry.java:
public interface Entry extends java.io.Serializable {
}

◆interface JavaSpace

net/jini/space/JavaSpace.java:
public interface JavaSpace {
    Lease write(Entry entry, Transaction txn, long lease)
        throws TransactionException, RemoteException;
    long NO_WAIT = 0;
    Entry read(Entry tmpl, Transaction txn, long timeout)
        throws UnusableEntryException, TransactionException, 
               InterruptedException, RemoteException;
    Entry readIfExists(Entry tmpl, Transaction txn, long timeout)
        throws UnusableEntryException, TransactionException, 
               InterruptedException, RemoteException;
    Entry take(Entry tmpl, Transaction txn, long timeout)
        throws UnusableEntryException, TransactionException, 
               InterruptedException, RemoteException;
    Entry takeIfExists(Entry tmpl, Transaction txn, long timeout)
        throws UnusableEntryException, TransactionException, 
               InterruptedException, RemoteException;
    EventRegistration
        notify(Entry tmpl, Transaction txn, RemoteEventListener listener,
               long lease, MarshalledObject handback)
        throws TransactionException, RemoteException;
    Entry snapshot(Entry e) throws RemoteException;
}

notify() では、マッチするテンプレートが write された時、 RemoteEventListener の notify(RemoteEvent theEvent) が呼ばれる。

snapshot() では、エントリのスナップショットが返される。元のエントリが 更新されても、変化しない。read(), take() のテンプレート用。

◆チュートリアルとLookupクラス

JavaSpace オブジェクトの作成方法やプログラム中での空間の入手方法は、実 行環境に依存する。

次のチュートリアルが参考になる。

[1] Qusay H. Mamoud: "Getting Started With JavaSpaces Technology: Beyond Conventional Distributed Programming Paradigms", July 12, 2005. http://www.oracle.com/technetwork/articles/javase/javaspaces-140665.html (リンク切れ http://java.sun.com/developer/technicalArticles/tools/JavaSpaces/ )

[2] The Blitz Project: "HelloWorld Example", https://github.com/dancres/blitzjavaspaces/tree/master/examples/helloworld

両方とも、後者のサイトにある Lookup.java を使っている。

◆Jini

JavaSpaces は、Java 技術では、Jini (講義では後述) の一部として位置付け られている。JavaSpaces を動作させるには、まず Jini に関連するクラスライ ブラリ等をインストールする必要がある。

Jini は、以前は、"Jini Technology Starter Kit" という名前のパッケージで 配布されていた。現在は、Apache River として開発が続けられ配布されている。

JavaSpaces の例題を実行する前に、Apache River に含まれているいくつかの サーバを実行する必要がある。

■Java Spaces による Message Box の例題/Message box example with JavaSpaces

References

◆class Message

空間に String を置くためのクラス。
   1: // From the JavaSpaces book
   2: //package jsbook.chapter1.helloWorld;
   3: 
   4: import net.jini.core.entry.Entry;
   5: 
   6: public class Message implements Entry {
   7:     public String content;
   8: 
   9:     public Message() {
  10:     }
  11: }
テンプレートでオブジェクトが null なら、ワイルドカードの意味になる。

◆HelloWriter

空間にタプルを書込むプログラム
   1: //
   2: // HelloWriter.java
   3: // 
   4: 
   5: import net.jini.space.JavaSpace;
   6: 
   7: class HelloWriter {
   8:     public static void main(String[] argv)
   9:     {
  10:         Lookup finder = new Lookup(JavaSpace.class);
  11:         JavaSpace space = (JavaSpace) finder.getService();
  12:         if( space == null )
  13:         {
  14:             System.err.println("No JavaSpace found.");
  15:             System.exit( 1 );
  16:         }
  17:         Message msg = new Message();
  18:         msg.content = "Hello" ;
  19:         try
  20:         {
  21:             space.write(msg, null, net.jini.core.lease.Lease.FOREVER);
  22:             System.out.println("HelloWriter: wrote["+msg.content+"]");
  23:         }
  24:         catch( Exception e )
  25:         {
  26:             System.err.println("JavaSpace write error "+e.getMessage());
  27:             e.printStackTrace();
  28:             System.exit( -1 );
  29:         }
  30:         System.exit( 0 );
  31:     }
  32: }
write() のインタフェース
    Lease write(Entry entry, Transaction txn, long lease)
        throws TransactionException, RemoteException;
txnはトランザクションにより複数の操作をグループ化するもの。null を 指定すれば、その機能は使われない。

lease は、時間を指定する。その時間だけは、空間がそのエントリを記憶して いる。空間が Garbage Collection に使う。Lease.FOREVER は、無限に覚えて いることを意味する。単位は、ミリ秒。

◆HelloReader

空間からタプルを読込むプログラム。タプルは、空間に残される。
   1: //
   2: // HelloReader.java
   3: // 
   4: 
   5: import net.jini.space.JavaSpace;
   6: 
   7: public class HelloReader {
   8:     public static void main(String[] argv)
   9:     {
  10:         Lookup finder = new Lookup(JavaSpace.class);
  11:         JavaSpace space = (JavaSpace) finder.getService();
  12:         if( space == null )
  13:         {
  14:             System.err.println("No JavaSpace found.");
  15:             System.exit( 1 );
  16:         }
  17: 
  18:         Message template = new Message();
  19:         Message result;
  20:         try
  21:         {
  22:             result = (Message)space.read(template, null, Long.MAX_VALUE);
  23:             System.out.println("HelloReader: read ["+result.content+"]");
  24:         }
  25:         catch( Exception e )
  26:         {
  27:             System.err.println("JavaSpace read error "+e.getMessage());
  28:             e.printStackTrace();
  29:             System.exit( -1 );
  30:         }
  31: 
  32:         System.exit( 0 );
  33:     }
  34: }
read() のインタフェース
    Entry read(Entry tmpl, Transaction txn, long timeout)
        throws UnusableEntryException, TransactionException, 
               InterruptedException, RemoteException;
read の最初の引数は、テンプレートである。 read は、空間からテンプレートとマッチするエントリを読み出す。

read() は、マッチするエントリがなければ、timeout するまで待つ。 Long.MAX_VALUE は、無限に待つことを意味する。待ちたくない時には、 JavaSpaces.NO_WAIT を使うか、readIfExists() を使う。

◆read() におけるテンプレートとタプルのマッチング/ maching tuples with a template in read()

次の2つの条件を満たした時に、テンプレートとエントリはマッチする
  1. テンプレートの型が、エントリの型とまったく同じである、または、エ ントリの型の部分型(サブクラス)である。
  2. テンプレートの中の各フィールドが、対応するエントリ中のフィールドと マッチする。
null は、ワイルドカード(*)の意味する。 任意のオブジェクトとマッチする。Linda の formal (?付き) に相当する。

例:


public class Vegetable implements Entry {
}

public class Fruit implements Entry {
}

public class Apple extends Fruit {
}

public class Orange extends Fruit {
}

「同じ値」は、serialize (マーシャリング)してバイトレベルで同じという意 味。エントリは、タプル空間にある時にはserialize された形で保存されてい る。

null をワイルド・カードに使う問題点は、「本当に null の値を持つエントリ 探す」ということができないこと。 区別したい時には、Boolean を添える。


public class NotePtr implements Entry {
    public Boolean ptrIsNull;
    public Node ptr;
}

...

NodePtr template = new NodePtr();
template.ptrIsNull = new Boolean(true);
template.ptr = null; // for completeness; null by default

null をワイルドカードに使ったので、空間に置くエントリのフィールドは、 オブジェクトにする。int, boolean, float, double などは、Integer, Boolean, Float, Double などの wrappe クラスを使う。

注意:連続する read() が同じオブジェクトを返す保証はない。

◆HelloTaker

空間からタプルを読込むプログラム。タプルは、空間から取り去られる。
   1: //
   2: // HelloTaker.java
   3: // 
   4: 
   5: import net.jini.space.JavaSpace;
   6: 
   7: public class HelloTaker {
   8:     public static void main(String[] argv)
   9:     {
  10:         Lookup finder = new Lookup(JavaSpace.class);
  11:         JavaSpace space = (JavaSpace) finder.getService();
  12:         if( space == null )
  13:         {
  14:             System.err.println("No JavaSpace found.");
  15:             System.exit( 1 );
  16:         }
  17: 
  18:         Message template = new Message();
  19:         Message result;
  20:         try
  21:         {
  22:             result = (Message)space.take(template, null, Long.MAX_VALUE);
  23:             System.out.println("HelloTaker: took ["+result.content+"]");
  24:         }
  25:         catch( Exception e )
  26:         {
  27:             System.err.println("JavaSpace read error "+e.getMessage());
  28:             e.printStackTrace();
  29:             System.exit( -1 );
  30:         }
  31: 
  32:         System.exit( 0 );
  33:     }
  34: }

% diff HelloReader.java HelloTaker.java
2c2
< // HelloReader.java
---
> // HelloTaker.java
7c7
< public class HelloReader {
---
> public class HelloTaker {
22,23c22,23
<           result = (Message)space.read(template, null, Long.MAX_VALUE);
<           System.out.println("HelloReader: read ["+result.content+"]");
---
>           result = (Message)space.take(template, null, Long.MAX_VALUE);
>           System.out.println("HelloTaker: took ["+result.content+"]");
% 

take() は、read() と同じだが、エントリを空間から取り去る所が異なる。

◆Apache River のインストール/Installing Apache River

例題をコンパイルする前に、Apache River をインストールする。
  1. ダウンロード・ページ(download page) で bin ( apache-river-2.2.2-bin.zip or apache-river-2.2.2-bin.tar.gz ) を入手する。 (3.0, 2.3 は、ソース・コードなので、そのままでは実行できない。)
  2. 入手したパッケージを展開する(expand the package)。すると、apache-river-2.2.2 という ディレクトリができる。
    $ ls -l [←]
    total 0
    drwxr-xr-x@ 7 yas  wheel  374  6 20  2013 apache-river-2.2.2
    $ ls apache-river-2.2.2/ [←]
    LICENSE		NOTICE		configentry	lib		lib-ext
    LICENSE.txt	NOTICE.txt	examples	lib-dl
    $ []
    
  3. コンパイルには、lib 以下にある次のファイルが 必要になる。これを classpath で指定する。 You will need following jar files in lib/.
  4. さらに、次のディレクトリにあるスクリプトや設定ファイルが必要になる。 You will also need following scripts and configuration files in examples/hello/.
    $ cd apache-river-2.2.2/examples/hello/ [←]
    $ ls [←]
    config		index.html	lib		scripts
    doc				krb-setup.html	prebuiltkeys
    $ []
    

◆Jiniサーバの実行 / Running Jini servers

See also Getting Started With River. We need to run three servers

Jini関連のサーバ用にウインドウを 3 枚開く。Apache River の examples/hello に cd する。 Open three windows. Change directory to examples/hello in Apache River.

$ cd apache-river-2.2.2/examples/hello/ [←]
$ ls [←]
config  doc  index.html  krb-setup.html  lib  prebuiltkeys  scripts
$ []
最初のウインドウでHTTP server を実行する。.sh は、Unix 用。.bat は、 Windows 用。
$ tail -1 ./scripts/httpd.sh   [←]
java -jar ../../lib/classserver.jar -port 8080 -dir lib:../../lib-dl $*
$ tail -1 ./scripts/httpd.bat [←]
java -jar ..\..\lib\classserver.jar -port 8080 -dir lib;..\..\lib-dl %1
$ ./scripts/httpd.sh  [←]
+ java -jar ../../lib/classserver.jar -port 8080 -dir lib:../../lib-dl
Jan 25, 2012 9:54:13 PM com.sun.jini.tool.ClassServer run
INFO: ClassServer started [[lib/, ../../lib-dl/], port 8080]
^Cで終了
2番目のウインドウで Service Registrar (Lookup Service) を実行する。
$ tail -4 scripts/jrmp-reggie.sh [←]
java -Djava.security.policy=config/start.policy \
     -Djava.ext.dirs=../../lib-ext/     \
     -jar ../../lib/start.jar   \
     config/start-reggie.config
$ tail -3 scripts/jrmp-reggie.bat [←]
java -Djava.security.policy=config\start.policy ^
     -jar ..\..\lib\start.jar ^
     config\start-reggie.config
$ ./scripts/jrmp-reggie.sh  [←]
+ java -Djava.security.policy=config/start.policy -Djava.ext.dirs=../../lib-ext/ -jar ../../lib/start.jar config/start-reggie.config
Jan 25, 2012 9:58:14 PM com.sun.jini.reggie.RegistrarImpl init
INFO: started Reggie: 6879dd38-7782-4f43-a172-baffff666af7, [nonsecure.hello.example.jini.sun.com], jini://example.com/
^Cで終了

Tips 1: java.net.UnknownHostException が出たら /etc/hosts に `hostname` を登録してみる。
$ hostname  [←]
sharon
$ egrep `hostname` /etc/hosts [←]
127.0.0.1       localhost sharon sharon.domainname
$ []
Tips 2: com.sun.jini.start.ServiceStarter checkResultFailuresException creating servicecom.sun.jini.start.ServiceStarter checkResultFailures が出たら、 -Djava.rmi.server.useCodebaseOnly=false を試すと良い。 river-user mailing list の記事参照Java Release Note の Changes to RMI 参照
$ java -Djava.rmi.server.useCodebaseOnly=false -Djava.security.policy=config/start.policy -Djava.ext.dirs=../../lib-ext/ -jar ../../lib/start.jar config/start-reggie.config [←]

Tips 3: Java 12 では次の方法で動作した。

$ java -Djava.rmi.server.hostname=127.0.0.1 -Djava.security.policy=config/start.policy -classpath ../../lib-ext/ -Djava.rmi.server.useCodebaseOnly=false -jar ../../lib/start.jar  config/start-reggie.config [←]

3番目のウインドウで Java Space サーバを実行する。配布されているスクリ プトに .bat バグがあり、うまく実行できない。config/policy.all というファ イルは存在しない。また、.sh は、そもそも含まれていない。
$ tail -3 scripts/jrmp-outrigger-group.bat [←]
java -Djava.security.policy=config\policy.all ^
     -jar ..\..\lib\start.jar ^
     config\start-outrigger-group.config
$ ls config/policy.all [←]
ls: config/policy.all: No such file or directory
$ ls scripts/jrmp-outrigger-group.sh   [←]
ls: scripts/jrmp-outrigger-group.sh: No such file or directory
$ []
次のように手で引数を与えて実行する(Unix)。
$ java -Djava.security.policy=config/start.policy \ [←]
     -jar. ./../lib/start.jar \
     config/start-outrigger-group.config
^Cで終了
Tips 4: 上と同じように、 com.sun.jini.start.ServiceStarter checkResultFailuresException creating service が出たら、 上と同じように、 -Djava.rmi.server.useCodebaseOnly=false を試すと良い。
java -Djava.security.policy=config/start.policy -Djava.rmi.server.useCodebaseOnly=false -jar ../../lib/start.jar config/start-outrigger-group.config
Tips 5: Java 12 で、次の方法で動いた。
$ java -Djava.rmi.server.hostname=127.0.0.1 -Djava.security.policy=config/start.policy -Djava.rmi.server.useCodebaseOnly=false -jar ../../lib/start.jar config/start-outrigger-group.config [←]

◆例題のコンパイル compilating the example

% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/Lookup.java [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/Message.java [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/HelloWriter.java [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/HelloReader.java [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/HelloTaker.java [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/Makefile [←]
% emacs Makefile (jinilibを、自分の環境に合わせて書き換える。change jinilib) [←]

% make hello [←]
javac -classpath .:/jini-core.jar:/jini-ext.jar:/reggie.jar:/outrigger.jar Lookup.java
javac -classpath .:/jini-core.jar:/jini-ext.jar:/reggie.jar:/outrigger.jar Message.java
javac -classpath .:/jini-core.jar:/jini-ext.jar:/reggie.jar:/outrigger.jar HelloWriter.java
javac -classpath .:/jini-core.jar:/jini-ext.jar:/reggie.jar:/outrigger.jar HelloReader.java
javac -classpath .:/jini-core.jar:/jini-ext.jar:/reggie.jar:/outrigger.jar HelloTaker.java
% ls  [←]
HelloReader.class       HelloWriter.class       Makefile
HelloReader.java        HelloWriter.java        Message.class
HelloTaker.class        Lookup.class            Message.java
HelloTaker.java         Lookup.java
% []

◆例題の実行 Running examples

実行する前に、Jiniサーバの実行 の説明で述べたように、3つのサーバを実行しておくこと。 You need to run three Jini servers before executing these examples.

一方のウインドウを2枚開く。 Open two windows.

一方のウインドウで Writer を動作させる。

$ PS1='Writer$ ' [←]
Writer$ make run-HelloWriter[←]
HelloWriter: wrote[Hello]
Writer$ []
もう一方のウインドウで Reader や Taker を動作させる。
$ make run-HelloReader [←]
HelloReader: read [Hello]
$ make run-HelloReader [←]
HelloReader: read [Hello]
$ make run-HelloReader [←]
HelloReader: read [Hello]

$ make run-HelloTaker  [←]
HelloTaker: took [Hello]
$ make run-HelloTaker [←]
(固まる)
タプルがない状態先に take/read すると、止まる。この状態で、write すれば、 read/take は先に進む。
Writer$ make run-HelloWriter[←]
HelloWriter: wrote[Hello]
Writer$ []

◆serialization

エントリが空間にある時には、serialize された形で保存されている。

read() でのマッチングは、serialize(marshaling) された形で比較される。

一度空間に入れて出すと、オブジェクトが増えることがある。


public class E1 implements Entry {
    public Integer obj1;
    public Integer obj2;
}

Integer obj = Integer(0);
E1 e = new E1();
e.obj1 =obj;
e.obj2 =obj;

引数なしのコンストラクタが必要である。

read(), take() でのエントリの復元

  1. serialize されたエントリのコピーを得る
  2. 1. から型を得る
  3. 引数なしのコンストラクタでオブジェクトを作る
  4. 1. から、public のフィールドを deserialize する。
  5. 4. の値を、オブジェクトのフィールドに代入する。
実は、Entry 全体は Serializable である必要はなかった。

read(), take() のテンプレートがループの中で不変な場合、 snapshot() を作ると効率が良くなる。

■Rinda

Linda のタプル空間 の考え方を Ruby で実現したもの。

Linda Rinda 説明
タプル() 配列[] タプル空間に置くことができるデータ構造
out write タプルをタプル空間内に生成する。
in take タプルを取り去る
rd read in/takeと似ているが、タプルがタプル空間に残る。
ライブタプル(eval命令)は、Rinda にはない。 配列の要素が nil なら、formal (ワイル ドカード, Linda の ?)の意味になる。

Rinda が提供する空間の特徴

タプルのマッチング Ruby の === 演算子
% ruby -e 'p 1 === 1' [←]
true
% ruby -e 'p Integer === 1' [←]
true
% ruby -e 'p String === 1' [←]
false
% ruby -e 'p /[abc]xy/ === "axy"' [←]
true
% ruby -e 'p /[abc]xy/ === "Axy"' [←]
false
%

■Rinda による Message Box の例題/ Message Box example in Rinda

次のようなタプルをタプル空間に置く。
["Message Box", "Hello" ]

◆make-space.rb

タプル空間を作るプログラム。
   1: #!/usr/bin/env ruby
   2: # make-space.rb -- Make a tuple space and print its URI
   3: 
   4: require 'rinda/tuplespace'
   5: 
   6: def usage()
   7:         $stderr.printf("Usage: %% %s portno\n", $0)
   8:         exit( 1 )
   9: end
  10: 
  11: def main(argv)
  12:         if( argv.length != 1 )
  13:             usage()
  14:         end
  15:         portno = argv[0]
  16:         space = Rinda::TupleSpace.new()
  17:         DRb.start_service("druby://:"+portno, space)
  18:         uri = DRb.uri()
  19:         $stdout.printf("%s\n",uri)
  20:         $stdout.printf("Type ^C to stop this program.\n")
  21:         DRb.thread.join()
  22: end
  23: 
  24: main(ARGV)
このプロセスを終了すると、タプル空間とその中のタプルは消える。

◆mbox-writer.rb

タプルを書込むプログラム。
   1: #!/usr/bin/env ruby
   2: # mbox-writer.rb -- Write a message to the message box in a tuple space.
   3: 
   4: require 'rinda/tuplespace'
   5: 
   6: def usage()
   7:         $stderr.printf("Usage: %% %s uri message\n", $0)
   8:         exit( 1 )
   9: end
  10: 
  11: def main(argv)
  12:         if( argv.length != 2 )
  13:             usage()
  14:         end
  15:         uri = argv[0]
  16:         message = argv[1]
  17: 
  18:         space = DRbObject.new_with_uri( uri )
  19: 
  20:         tuple = ["Message Box", message ]
  21:         space.write( tuple )
  22:         printf("mbox-writer: wrote[%s]\n",message)
  23: end
  24: 
  25: main(ARGV)

◆mbox-reader.rb

空間からタプルを読込むプログラム。タプルは、空間に残される。
   1: #!/usr/bin/env ruby
   2: # mbox-reader.rb -- Read a message from a message box in a tuple space.
   3: 
   4: require 'rinda/tuplespace'
   5: 
   6: def usage()
   7:         $stderr.printf("Usage: %% %s uri\n", $0)
   8:         exit( 1 )
   9: end
  10: 
  11: def main(argv)
  12:         if( argv.length != 1 )
  13:             usage()
  14:         end
  15:         uri = argv[0]
  16:         DRb.start_service()
  17:         space = DRbObject.new_with_uri( uri )
  18: 
  19:         template = ["Message Box",nil]
  20:         tuple = space.read( template )
  21:         message = tuple[1]
  22:   p tuple # for debug
  23:         printf("mbox-reader: read [%s]\n", message )
  24: end
  25: 
  26: main(ARGV)
space.read()で、タプル空間からタプルを取り出す。 最初の引数は、テンプレートである。 read() は、空間からテンプレートとマッチするエントリを読み出す。

read() は、マッチするエントリがなければ、タイムアウトするまで待つ。 第2引数に秒単位で待ち時間を指定できる。

注意:連続する read() が同じオブジェクトを返す保証はない。

◆mbox-taker.rb

空間からタプルを読込むプログラム。タプルは、空間から取り去られる。
   1: #!/usr/bin/env ruby
   2: # mbox-taker.rb -- Take a message from a message box in a tuple space.
   3: 
   4: require 'rinda/tuplespace'
   5: 
   6: def usage()
   7:         $stderr.printf("Usage: %% %s uri\n", $0)
   8:         exit( 1 )
   9: end
  10: 
  11: def main(argv)
  12:         if( argv.length != 1 )
  13:             usage()
  14:         end
  15:         uri = argv[0]
  16:         DRb.start_service()
  17:         space = DRbObject.new_with_uri( uri )
  18: 
  19:         template = ["Message Box",nil]
  20:         tuple = space.take( template )
  21:         message = tuple[1]
  23:         printf("mbox-taker: took [%s]\n", message )
  24: end
  25: 
  26: main(ARGV)
take() は、read() と同じだが、エントリを空間から取り去る所が異なる。複 数の take() が重なったとしても、エントリは1つにしか取られない。
% diff mbox-reader.rb mbox-taker.rb [←]
2c2
< # mbox-reader.rb -- Read a message from a message box in a tuple space.
---
> # mbox-taker.rb -- Take a message from a message box in a tuple space.
20c20
<       tuple = space.read( template )
---
>       tuple = space.take( template )
23c23
<       printf("mbox-reader: read [%s]\n", message )
---
>       printf("mbox-taker: took [%s]\n", message )
% []

◆コピー Copying

% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/make-space.rb [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/mbox-writer.rb [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/mbox-reader.rb [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2019/2019-07-30/ex/mbox-taker.rb [←]
% chmod +x *.rb [←]
% ls -l [←]
total 32
-rwxr-xr-x   1 yas  yas  463  2  7 23:42 make-space.rb
-rwxr-xr-x   1 yas  yas  485  2  7 23:48 mbox-reader.rb
-rwxr-xr-x   1 yas  yas  484  2  8 00:06 mbox-taker.rb
-rwxr-xr-x   1 yas  yas  406  2  7 23:40 mbox-writer.rb
% which ruby [←]
/usr/local/bin/ruby
% ruby -v [←]
ruby 2.1.7p400 (2015-08-18 revision 51632) [x86_64-darwin13]
% []
実行には、Ruby の 1.8 以降が必要。drb.rb を含んだもの。

◆例題の実行 Running examples

ウインドウを3枚開く
  1. タプル空間用
  2. writer 用
  3. reader/taker用

$ ./make-space.rb 1231 [←]
druby://ホスト名:1231
Type ^C to stop this program.
(最後に ^C で止める)
引数のポート番号(1231)は、ぶつからないような番号にする。自動的に終了し ないので、実験が終わったら ^C (Control-C) で殺す。

Writer を動作させる。

$ ./mbox-writer.rb druby://localhost:1231 hello [←]
mbox-writer: wrote[hello]
$ ./mbox-writer.rb druby://localhost:1231 hi    [←]
mbox-writer: wrote[hi]
$ []
最後のウインドウで Reader や Taker を動作させる。
$ ./mbox-reader.rb druby://localhost:1231 [←]
["Message Box", "hello"]
mbox-reader: read [hello]
$ ./mbox-reader.rb druby://localhost:1231 [←]
["Message Box", "hello"]
mbox-reader: read [hello]
$ ./mbox-reader.rb druby://localhost:1231 [←]
["Message Box", "hello"]
mbox-reader: read [hello]
$ ./mbox-taker.rb druby://localhost:1231 [←]
["Message Box", "hello"]
mbox-taker: took [hello]
$ ./mbox-taker.rb druby://localhost:1231 [←]
["Message Box", "hi"]
mbox-taker: took [hi]
$ ./mbox-taker.rb druby://localhost:1231 [←]
...
3回目の take は止まる。別ウインドウで write すれば、先に進む。

タプルがない状態先に take/read すると、止まる。この状態で、write すれ ば、read/take は先に進む。

◆阿波連流 Aharen-style

タプルは、生存期間が過ぎると、自動的にタプル空間から消える。

LinuxTuples64Bit

LinuxTuples は、 C言語によるタプル空間のサーバの実装。現在のコンパイラでは動作しない。

LinuxTuples64Bit は、最近のコンパイラでもコンパイルできる。 (macOS でもコンパイルできた。) fft のリンクでエラーが出た時には、-lm を最後に付けると良い。

$ cc -L/usr/lib/python2.7/config -lpython2.7 -L/usr/lib  fft.o tuple.o -lm  -o fft [←]
C言語の他に Python2 や Rust言語 からも利用できる。

TOCTOU (Time Of Check to Time Of Use)

次のようなプログラムは、並行プログラムではうまく動かない。 The following programs do not work well in a concurrent system.
if( check() == OK ) /* time of check */
{
    /* other threads can change the condition after checking. */
    do_action() /* time of use */
}
if( access("file", W_OK) == 0 ) /* time of check */
{
    /* other processes can create the file after checking. */
    fd = open("file", O_WRONLY); /* time of use */
}
static struct s1 *p;

thread() {
    if( p == NULL ) /* time of check */
    {
	/* other processes can allocate memory after checking. */
	p = malloc( sizeof(struct s1) );  /* time of use */
    }
}
url = "http://www.tsukuba.ac.jp";
if( rdp("counter-31", url, ?val) == 0 ) /* time of check */
{
    /* other processes can create the tuple after checking. */
    out("counter-31", url, 0); /* time of use */
}

練習問題

以下の問題(701-704)の中で、1つを選び、回答しなさい。 この課題では、Linda、Rinda (Ruby Linda)、JavaSpaces、または、 類似の タプル空間 の実装必ず利用しなさい。 ただし、Ruby では、read_all() を使ってはならない。 プログラミング言語としては、C言語、Java、Ruby、Python、Go、Rust、または、Kotolin を用いなさい。 このWebページで示した、タプル空間を作成するプログラムをそのまま利用しても良い。

Choose one question and answer it from the following questions (701-704). You must use Linda, JavaSpaces, Rinda (Ruby Linda), or other similar tuple spaces implementation. You must not use read_all() in Ruby. You can use the C, Java, Ruby, Python, Go, Rust, or Kotlin language. You may reuse a program that creates a tuple space in this Web page.

ポレートには、次のものを含めなさい。 A report must include following.

この内容を含む「テキスト」ファイルを作成し、 レポート提出ページ から提出しなさい。

締切りは、2019年8月2日、 23:59:59 とする。

★問題(701) WWWアクセスカウンタ/WWW Access Counter

タプル空間の仕組みを使ってWWW のアクセス・カウンタのような動きをするプ ログラム使って作りなさい。 Write programs that implement an access counter in WWW by using a tuple space.

次の2つのプログラムを作成しなさい。 Write following two programs.

(1) 初期化プログラム the initialization program
引数として URL を取る。 This program must take a URL as an argument.
    String url = argv[0];
    tuple = ["counter", url,0]
    space.write( tuple );
$ ./init-counter http://www.example.com/ [←]
$ ./init-counter http://www.example.com/hello.html [←]
$ []
(2) カウンタプログラム the counter program.
$ ./counter http://www.example.com/ [←]
1
$ ./counter http://www.example.com/ [←]
2
$ ./counter http://www.example.com/ [←]
3
$ ./counter http://www.example.com/hello.html [←]
1
$ []
なお、(2) のプログラムは、コマンドラインから実行すれば十分であり、CGI にする必要はない。 Note that you can execute the program (2) from the command line, and you do not have to write a CGI program.

★問題(702) Linda の inストリーム / Linda in-steams

Linda の inストリームを実現しなさい。 3つのプログラムを作成しなさい。 Relize Linda in-streams. Write following three programs.

★問題(703) タスクバッグを用いる並列プログラム/A parallel program using a task bag

手順並列法に基づく並列プログラムを書きなさい。 この並列プログラムは、タプル空間上のタスクバッグを利用しなければならない。 この並列プログラムは、逐次プログラムよりも高速でなければならない。

Write a parallel program based on the agenda parallelism. The parallel program must use a task bag in a tuple space. The parallel program must faster than a sequential program.

★問題(704) fork-join modelに基づく並列プログラム/A parallel program based on the fork-join model

タプル空間を使って、fork-joinモデルに基づく並 列プログラムを書きなさい。 この並列プログラムは、逐次プログラムよりも高速でなければならない。

Write a parallel program based on the fork-join model, using a tuple space. The parallel program must faster than a sequential program.

★問題(705) client-server-model

タプル空間を使ってクライアント・サーバ・モデルを実現しなさい。複数のク ライアントを区別し、要求と応答を対応させるには、どうすればよいか考えな さい。

Realize a client-sever model by using a tuple space. You must support multiple clients, and match a request message with a reply message.

★問題(706) スタック Stack

Linda の inストリーム(FIFOのキュー)を参考にして、 スタックを実現しなさい。 Relize stacks like Linda in-streams which are queues (FIFOs).
Last updated: 2019/07/31 12:51:29
Yasushi Shinjo / <yas@cs.tsukuba.ac.jp>