タプル空間

並行システム

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

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

■今日の重要な話

並列プログラムの作り方 資料

■協調作業のための基本パラダイム

-- 並列/分散プログラムのパタン。

◆並列プログラムを構築する手順

  1. パラダイムを選ぶ
  2. パラダイムに合った手法(Methods)で書く
  3. プログラム変換する
性能が十分でない場合には、他のパラダイムを使って書き直す

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

並列処理の最終結果に焦点を当る。

例: 家の建築:

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

並列処理を行う作業者に焦点を当る。

例: 家の建築:

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

並列処理の手順に焦点をあてる 例: 家の建築:

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

問題にあったものを使う。

実際の家の建築では、全部の方法が使われている。

◆結果並列法の使い方

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

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

  1. n 要素のベクトルを作る
  2. S[i] は、A[i] と B[i] を加えればわかる。
出力データが不明なもの、結果が1つのもには適していない。
テキスト処理、コンパイラ、
結果が可変
LU分解
繰り返しがある
OS、実時間
結果というよりは作用が大事

◆手順並列法の使い方

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

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

◆専門家並列法の使い方

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

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

■プログラミングの手法

視点

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

関数型言語は、これ。

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

図? ライブデータ構造体

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

マルチスレッドの特殊な場合。ロックを使わずに、TSD (Thread Specific Data) と通信だけでプログラムを書く場合はこれ。

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

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

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

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

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

図? 分散データ構造体

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

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

◆N-体問題:結果並列法

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

M[][0] に最初の位置。

position(i,j), 繰り返し j での 物体 i の位置を計算する。

position(X,j-1) の終了を待つ。

プロセスがデータに化けて行く。

◆N-体問題:専門家並列法

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

◆N-体問題:手順並列法

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

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

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

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

◆並列プログラムを書く方法

  1. 問題に適したパラダイムを選ぶ
  2. パラダイムに適した手法でプログラムを書く
  3. 必要なら効率のよい手法で書き直す
(粒度の調整)

◆手法の相互変換

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

図? 手法の変換

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

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

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

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

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

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

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

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

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

■Linda

協調言語(<−>計算言語)。

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

◆タプル空間(tuple space)

タプルの集合である。

タプルは、型付きの値の並び。

タプルの例:

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

(0,1)

2種類のタプル

データタプル
受動的
ライブタプル(プロセスタプル)
全部が同時に実行している。 データタプルを読み書きする。 終了するとデータタプルに変化する。

◆NUMAとタプル空間

速いローカルメモリと遅い大域的な共有メモリ。 非均質共有メモリ型マルチプロセッサ参照。

◆Lindaの命令

タプル空間を操作する基本4命令
out()
タプルをタプル空間内に生成する。(受動的なタプル)
in()
タプルを取り去る
rd() -- (read)
in と似ているが、タプルがタプル空間に残る。
eval()
out() と似ているが、新たにプロセスが作られて、そのプロセスによりタ プルが評価される。(ライブタプル)
predicate つき(デットロック対策で使う)
inp()
in() と同じだが、見つからなければ 0 を返す
rdp()
rd() と同じだが、見つからなければ 0 を返す

◆formalとactual

out("a string", 10.01, 17, x)

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

「?」付のものは、formal。型が同じものとマッチする。 ついていないものは、actual。型と値が同じものとマッチする。

◆プロセス生成

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

◆同期

in() と out() で同期がとられる。out() はブロックしない。in() は条件に よりブロックする。
out() してから in()
in() したプロセスはブロックしない
out() する前に in()
in() したプロセスはブロックする。 out() されるとブロック解除。

◆基本分散データ構造体

コンテナの分類
  1. 要素が全て同じ、または、要素を区別して取り出す方法がない。 タスクバッグ。集合。
  2. 要素が名前で区別できる。構造体、ハッシュ表。
  3. 要素が位置て区別される。

◆名前付の構造体(連想メモリ)

スクリプト言語(perl,ruby,awkなど)の連想配列と同じ。

タプルの形式: (name,val)

読込み:
    rd(name,?val)

変更:
    in(name,?val)
    val = val + 1 ;
    out(name,val)

◆計数セマフォ

P命令: 
    in("sem-1")

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

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

◆Task Bag

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

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

◆並列DOループ

逐次:
for( i=0 ; i<N; i++ )
{
    func(i,args);
}
並列:
for( i=0 ; i<N; i++ )
{
    eval ("loop-33", func(i,args) ); // プロセス生成
}
for( i=0 ; i<N; i++ )
{
    in("loop-33", 1 ); // 待ち
}

func(i,args)
{
   ...
   return( 1 );
}

◆バリア同期

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

マルチスレッドの マスタ・スレーブ(バリア付き) 参照。

n プロセスのバリア

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

◆配列

A[10];

("A",0,val00)
("A",1,val01)
("A",2,val02)
...
("A",9,val99)
2次元配列の場合。
A[10][10];

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

◆ストリーム(inストリーム)

1人が読むとデータが消える。
ストリームデータ
    ("stream",0,val0)
    ("stream",1,val1)
    ("stream",2,val2)
    ...

ポインタ
    ("stream","head",0)
    ("stream","tail",0)

ストリームに要素を追加:
    int index;
    in("stream","tail",?index);
    out("stream","tail",index+1);
    out("stream",index,new_element);

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

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

◆ストリーム(readストリーム)

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

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

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

◆メッセージ・パッシングのプログラムの書き方

◆ライブ・データ構造体のプログラムの書き方

■素数を求める

よい例題

◆結果並列法とライブデータ構造体

考え方 次のようなベクトルをタプル空間に作る。
("primes", 2, 1 ) // primes[2] = 1 ;
("primes", 3, 1 ) // primes[3] = 1 ;
("primes", 4, 0 ) // primes[4] = 0 ;
("primes", 5, 1 ) // primes[5] = 1 ;
("primes", 6, 0 ) // primes[6] = 0 ;
("primes", 7, 1 ) // primes[7] = 1 ;
..

プログラム

   1: /*
   2:  *      prime-results.c
   3:  */
   4: 
   5: #define LIMIT 1000
   6: 
   7: main()
   8: {
   9:     int count, i, ok;
  10:         for( i=2; i<=LIMIT; i++ )
  11:             eval ("primes", i, is_prime(i) );
  12:         count = 0 ;
  13:         for( i=2; i<=LIMIT; i++ )
  14:         {
  15:             rd("primes", i, ?ok);
  16:             if( ok )
  17:                 count ++;
  18:         }
  19:         printf("%d.\n", count );
  20: }
  21: 
  22: is_prime( int me )
  23: {
  24:     int i, limit, ok;
  25:     double sqrt();
  26:         limit = (int) sqrt( (double)me ) + 1;
  27:         for( i=2; i<limit; i++ )
  28:         {
  29:             rd("primes", i, ?ok);
  30:             if( ok && (me%i == 0) )
  31:                 return( 0 );
  32:         }
  33:         return( 1 );
  34: }
2 から sqrt(n) 以下の素数を rd() して得、割ってみて剰りを調べる。

利点

問題点

◆手順並列法

結果並列のプログラムをアブストラクションやその他のさまざまな工夫により 手順並列に書き換える。 Linda の表記法:object:count 。配列の最初の count 個の要素。in、または、 rd で ? object:count と書くと、count には要素数が入る。

   1: /*
   2:  *      prime-agenda.c
   3:  */
   4: 
   5: #define LIMIT 1000
   6: #define GRAIN 100
   7: #define MAX   1000
   8: 
   9: main( int argc, char *argv[], char *envp[] )
  10: {
  11:     int eot, first_num, i, length, new_primes[GRAIN], np2;
  12:     int num, num_primes, num_workers, primes[MAX], p2[MAX];
  13:         num_workers = atoi( argv[1] );
  14:         for( i=0; i< num_workers; i++ )
  15:             eval ("worker", worker() );
  16: 
  17:         num_primes = init_primes( primes, p2 );
  18:         first_num = primes[num_primes-1] + 2;
  19:         out("next task", first_num);
  20: 
  21:         eot = 0 ; /* end of table */
  22:         for( num=first_num; num<LIMIT; num+=GRAIN)
  23:         {
  24:             in("result", num, ?new_primes:length );
  25:             for( i=0; i<length; i++, num_primes++)
  26:             {
  27:                 primes[num_primes] = new_primes[i];
  28:                 if( !eot )
  29:                 {
  30:                     np2 = new_primes[i] * new_primes[i] ;
  31:                     if( np2 > LIMIT )
  32:                     {
  33:                         eot = 1 ;
  34:                         np2 = -1 ;
  35:                     }
  36:                     out("primes", num_primes, new_primes[i], np2 );
  37:                 }
  38:             }
  39:         }       
  40:         for( i=0; i<num_workers; i++)
  41:             in("worker", ?int);
  42:         printf("%d.\n", num_primes );
  43: }
  44: 
  45: worker()
  46: {
  47:     int count, eot, i, limit, num, num_primes, ok, start;
  48:     int my_primes[GRAIN], primes[MAX], p2[MAX];
  49:         num_primes = init_primes( primes, p2 );
  50:         
  51:         eot = 0;
  52:         while( 1 )
  53:         {
  54:             in("next task", ?num );
  55:             if( num == -1 )
  56:             {
  57:                 out("next task", -1 );
  58:                 return;
  59:             }
  60:             limit = num + GRAIN;
  61:             out("next task", (limit>LIMIT) ? -1 : limit );
  62:             if( limit > LIMIT )
  63:                 limit = LIMIT ;
  64: 
  65:             start = num;
  66:             for( count=0; num<limit; num+=2 )
  67:             {
  68:                 while( !eot && num > p2[num_primes-1] )
  69:                 {
  70:                     rd("primes", num_primes,
  71:                        ?primes[num_primes], ?p2[num_primes] );
  72:                     if( p2[num_primes] < 0 )
  73:                         eot = 1 ;
  74:                     else
  75:                         num_primes++;
  76:                 }
  77:                 for( i=0, ok=1; i<num_primes; i++ )
  78:                 {
  79:                     if( num%primes[i] == 0 )
  80:                     {
  81:                         ok = 0;
  82:                         break;
  83:                     }
  84:                     if( num < p2[i] )
  85:                         break;
  86:                 }
  87:                 if( ok )
  88:                     my_primes[count++] = num ;
  89:             }
  90:             out("result", start, my_primes:count );
  91:         }
  92: }
  93: 
  94: int
  95: init_prime( int primes[MAX], int p2[MAX] )
  96: {
  97:         primes[0] = 2;  p2[0] = 2 * 2;
  98:         primes[1] = 3;  p2[1] = 3 * 3;
  99:         return( 2 );
 100: }

◆専門家並列法

エタトステネスのふるい。 最終的には、次ようなパイプラインを作る。
source | pipe_seg-3 | pipe_seg-5 | pipe_seg-7 | .... | sink
source
整数列を生成する(5以上の奇数だけ)。
sink
見つかった素数 n について、pipe_seg(n,,) を作る(eval)。
pipe_seg(n,next,)
自分宛てのストリーム( ("seg",n,i,?num) )を受け取り、 n で割りきれないものを pipe_seg(next,,) に流す。
各パイプのセグメントは、次のようなストリームが流れる。
("seg", 宛先, ストリームのインデックス, 整数)
たとえば、source の出力(主に pipe_seg-3の入力)は、次のようになる。
("seg", 3, 0, 5 ) // sink が in
("seg", 3, 1, 7 ) // 以下 pipe_seg-3 が in する
("seg", 3, 2, 9 )
("seg", 3, 3, 11 )
("seg", 3, 3, 13 )
...
pipe_seg-3 の出力は、次のようになる。
("seg", 5, 0, 7 )  // sink が in する
("seg", 5, 1, 11 ) // 以下  pipe_seg-5 が in する
("seg", 5, 2, 13 ) 
...
最終的には、次のようなデータがタプル空間に残される。
("source", 1, 2)
("pipe seg", 2, 3)
("pipe seg", 3, 5)
("pipe seg", 4, 7)
...
("sink", MaxIndex, MaxPrime)

この方法は、結果並列や手順並列法よりも、並列性が低い。

   1: /*
   2:  *      prime-specialists.c
   3:  */
   4: 
   5: #define LIMIT 1000
   6: 
   7: main()
   8: {
   9:         eval ("soruce", source());
  10:         eval ("sink", sink());
  11: }
  12: 
  13: source()
  14: {
  15:     int i, out_index=0;
  16:         for( i=0; i<LIMIT; i+= 2)
  17:             out("seg", 3, out_index++, i );
  18:         out("seg", 3, out_index, 0 );
  19: }
  20: 
  21: sink()
  22: {
  23:     int in_index=0, num, prime=3, prime_count=2;
  24:         while( 1 )
  25:         {
  26:             in("seg", prime, in_index++, ?num);
  27:             if( num == 0 )
  28:                 break;
  29:             if( num % prime != 0 )
  30:             {
  31:                 prime_count ++ ;
  32:                 if( num * num < LIMIT )
  33:                 {
  34:                     eval ("pipe seg", pipe_seg(prime, num, in_index));
  35:                     prime = num;
  36:                     in_index = 0;
  37:                 }
  38:             }
  39:         }
  40:         printf("count: %d\n", prime_count );
  41: }
  42: 
  43: pipe_seg( int prime, int next, int in_index )
  44: {
  45:     int num, out_index=0;
  46:         while( 1 )
  47:         {
  48:             in("seg", prime, in_index++, ?num );
  49:             if( num == 0 )
  50:                 break;
  51:             if( num % prime != 0 )
  52:                 out("seg", next, out_index++, num);
  53:         }
  54:         out("seg", next, out_index, num );
  55: }

◆結論

■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", "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 tupple 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]
  22:   p tuple # for debug
  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 )
% []

◆コピー

% wget http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-02-08/ex/make-space.rb [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-02-08/ex/mbox-writer.rb [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-02-08/ex/mbox-reader.rb [←]
% wget http://www.cs.tsukuba.ac.jp/~yas/sie/csys-2007/2008-02-08/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 1.8.6 (2007-03-13 patchlevel 0) [universal-darwin8.0]
% []
実行には、Ruby の 1.8 以降が必要。drb.rb を含んだもの。

◆実行

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

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

Writer を動作させる。

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

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

■JavaSpaces

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

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

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

■課題

この課題では、Linda、Rinda、JavaSpaces、または、類似の仕組みを利用しな さい。

★練習問題(701) WWWアクセスカウンタ

WWW のアクセス・カウンタを実現を使って作りなさい。

次の2つのプログラムを作成する。

(1) 初期化プログラム
    String url = argv[0];
    tuple = [url,0]
    space.write( tuple );

(2) アクセスされた時に動作するプログラム
    値を増やす。現在の値を画面に表示する。

★練習問題(702) Linda の inストリーム

Linda の inストリームを実現しなさい。 次の2つのプログラムを作成しなさい。

★練習問題(703) スタック

Linda の inストリーム(FIFOのキュー)を参考にして、 スタックを実現しなさい。

★練習問題(704) マスタ・スレーブ

マスタ・スレーブで並列処理を行うプログラムをタプル空間を使って書き 直しなさい。

★練習問題(705) RPC

RPC (Remote Procedure Call) を実現しなさい。複数のクライアントを区別し、 要求と応答を対応させるには、どうすればよいか考えなさい。

★練習問題(706) C-Lindaの実行

このページに示された C-Linda のプログラム(そのままでは動作しない) を、 Rinda、JavaSpaces、その他の機能を利用して動作させない。

★練習問題(707) タプル空間自由課題

他の課題と同程度の複雑さを持つ課題を設定し、タプル空間を用いて実現 しなさい。
↑[もどる] ←[2月1日] ・[2月8日] →[2月15日]
Last updated: 2008/02/08 11:17:41
Yasushi Shinjo / <yas@is.tsukuba.ac.jp>