Mercurial > hg > Papers > 2008 > fuchita-master
view paper/implementation.tex @ 0:420c2d37b2bf
Initial revision
author | fuchita |
---|---|
date | Tue, 12 Feb 2008 17:18:57 +0900 |
parents | |
children |
line wrap: on
line source
\chapter{実装} ここではFederated Linda の実装について説明する。実装したのは type2 であ る。 \section{type2の実装} Federated Linda は本研究室で開発された非同期型Linda\cite{linda}をベー スに開発した。type 2 では Linda Server と Protocol Engine は別プロセスと して実装する。Protocol Engine では Linda Server との通信を クライアントに 提供されている Linda API を用いて行う。 タプルのIDは、{\tt 16bit}の整数値を用いている。タプルのデータは任意の文字列であ る。Linda Server は C で記述されており、クライアントは C, Perl, Python, Ruby にて記述可能。以下、Linda Server と クライアントへ提供している Linda API の説明をし、分散プログラムの主要素である Local Access, Protocol Engine, Link Configuration の実装について説明する。 \subsection{Linda Server} Linda Server は C で記述している。タプルスペースはメモリ上のキューとして 実装されている。タプルスペースには1から65535までのIDが割り当てられており、 タプルは指定されたIDへのキューへ格納される。 %% タプルの図は入れる? %% in/rd の非同期の説明 非同期型 Linda Server の特徴として、タプルを要求するコマンド (in, read, wait\_read) などを実行する際のコマンド実行の保留が挙げられる。クライアン トからタプルを要求するコマンドを受け取ると、Linda Server は指定されたID にタプルがあるかどうかを調べる。ある場合にはそのコマンドを即実行するが、 無い 場合には、コマンド実行の保留を行う。その後、そのIDへタプルが書き込 まれた( out された) 時に 保留されたコマンドを実行する。(図\ref{async-in} 参照)。このコマンド実行の保留により、コマンド実行の待ちやクライアントが Linda Server へタプルの有無を問い合わせたりすることなく、非同期通信を行 うことができる。 \begin{figure}[htp] \begin{center} \includegraphics[width=13cm]{fig/async-in.eps} \caption{タプルがない場合の in コマンドの実行} \label{async-in} \end{center} \end{figure} プログラムは {\tt ldserv} という名前で提供されている。 起動方法は以下の通りである。``-p''オプションでポート番号を指定している。 %% ldserv の起動方法など \begin{verbatim} $ ldserv -p 10000 \end{verbatim} %% もうちょい説明が欲しぃ \subsection{Federated Linda API} %% Local Access に入れてもいい?? Federated Linda の通信は非同期に行われる。in, read, out などのコマンドの関数 を呼び出した時点では通信は行われず、それらのコマンドを一時的にキュー ({\tt COMMAND}キュー)へ蓄える。蓄えたコマンドは、タプルやコマンドの送受信を行 う関数({\tt sync()})が呼ばれた時点で一斉に各 Linda Server へ送信される。このと き、Linda Server から送信されたタプルの受信も行う。受信されたタプルは {\tt REPLY}キューへ蓄えられ、データを取りだす関数({\tt reply()})で取り出される。 {\tt COMMAND} キューと {\tt REPLY} キューは API により隠蔽されており、直接は見えない。 Federated Linda ではクライアントプログラムへの API として C, Perl, Python, Ruby で実装したインターフェースを提供している。クライアントプロ グラムはこれらの中から好きな言語を選んで記述することになる。提供している API は、C言語とその他のスクリプト言語との間で若干の違いがある。スクリプ ト言語ではオブジェクト指向を意識して実装したため、このような違いが出てい る。 C言語とスクリプト言語に分けて API の説明を行う。 \subsubsection{C言語のAPI} C言語で提供している主な関数群は以下の通りである。 %% CのAPIの説明 \begin{itemize} \item {\tt open\_linda(hostname,port)}\\ Linda Server へ接続する。引数としてホスト名({\tt hostname})とポート番号 ({\tt port})をとる。返り値はタプルスペースの番号 \item {\tt psx\_in(ts\_id,tuple\_id)}\\ 指定したIDのタプルの受け取り要求をするコマンド {\tt in} を {\tt COMMAND}キュー へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と受け 取るタプルのID({\tt tuple\_id})をとる。返り値として{\tt psx\_reply()}でタプル を取り出すときに用いるユニークな番号が返る。受け取ったタプルは、タ プルスペース上からは削除される。 \item {\tt psx\_rd(ts\_id,tuple\_id)}\\ 指定したIDのタプルの受け取り要求をするコマンド {\tt read} を{\tt COMMAND}キュー へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と受け 取るタプルのID({\tt tuple\_id})をとる。返り値として{\tt psx\_reply()}でタプル を取り出すときに用いるユニークな番号が返る。受け取ったタプルは、タ プルスペース上に残る。 \item {\tt psx\_wait\_rd(ts\_id,tuple\_id)}\\ {\tt psx\_rd()}と似ているが、タプルスペース上での挙動に違いがある。タプル スペースにタプルがあった場合、現在あるタプルではなく、新規に{\tt out}され たタプルに対して{\tt read}を行う。それ以外は同じ挙動である。 \item {\tt psx\_out(ts\_id, tuple\_id, data)}\\ 指定したIDのタプルの書き込み要求をするコマンド {\tt out} を{\tt COMMAND}キュー へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と書き 込むタプルのID({\tt tuple\_id})をとる。 \item {\tt psx\_ck(ts\_id,tuple\_id)}\\ 指定したIDのタプルの有無の確認をするコマンド {\tt check} を{\tt COMMAND}キュー へ入れる。引数としてコマンドを送るタプルスペースの番号({\tt ts\_id})と受け 取るタプルのID({\tt tuple\_id})をとる。返り値として{\tt psx\_reply()}でタプル を取り出すときに用いるユニークな番号が返る。タプルのデータ部分には タプルスペース上にあるタプルのサイズが入る。指定したIDのタプルが無 ければ {\tt 0} となる。 \item {\tt psx\_sync\_n()}\\ 接続している全Linda Server とタプルの送受信を行う。{\tt COMMAND}キューに 溜まったコマンドを送信し、Linda Server からのタプルを {\tt REPLY} キュー へ入れる \item {\tt psx\_reply(uid)}\\ {\tt REPLY}キューにあるタプルを取りだす。取り出す際に、{\tt in}, {\tt read}コマンドが返した番号を引数としてとる。返り値はタプル。取り出したタプルからデー タやタプル情報(IDやデータサイズ)を取り出す関数群も用意している。 \end{itemize} まず {\tt open\_linda} を用いて Linda Server へ接続する。この時返る値が Linda Server の ID になる(Tuple Space ID)。この値とタプルのIDを用いて{\tt psx\_in, psx\_rd, psx\_out}などのコマンドを発行する。{\tt psx\_in} や {\tt psx\_rd, psx\_ck} はユニークな番号を返す。この番号は {\tt psx\_reply} の引数として使用し、どの {\tt psx\_in, psx\_rd}の返答を取り出すかを指定するためのものである。通信は {\tt psx\_sync\_n}でのみ発生する。 %まず open\_linda を用いて Linda Server へ接続する。この時返る値が Linda % ^^^^^ こういうのは {\tt } とか \verb+...+ みたいなのを使って % type writer font にする これらのAPIを用いた通信はポーリング型の形を取る。具体的なポーリングベー スのプログラミング例は Local Access の説明で述べる。 \subsubsection{Perl, Python, Ruby の API} %% Perl, Python, Ruby で提供したクラスなどの説明 Perl, Python, Ruby は C の API を拡張して実装している。提供しているモジュー ルは{\tt FederatedLinda, Linda, Reply}というクラスで構成されている(図 \ref{LWLClass}参照)。各スクリプト言語で同じ名前を用いて実装している。 %% FederatedLinda クラスや Reply クラスを、図を入れて説明 \begin{figure}[htbp] \begin{center} \includegraphics[width=15cm]{fig/flinda-class-dig.eps} \caption{Perl, Python, Ruby で拡張したLinda API のクラス図} \label{LWLClass} \end{center} \end{figure} %% 各クラスの説明。 %% FederatedLinda.open() で Linda インスタンス生成、 %% Linda.in(), Linda.rd() で Reply インスタンスが返るとか %% FederatedLinda.sync() で通信 \begin{itemize} \item {\tt FederatedLinda} - {\tt open} や {\tt sync} など、通信やその接 続切断を行うクラス。1プロセスに1インスタンスのみ生成される。 \begin{description} \item[~{\tt open(hostname, port)}]{\tt Linda} インスタンスを返す。引数としてホスト名 ポート番号を取る。 \item[~{\tt sync()}] 接続している全Linda Serverと通信を行う。 \end{description} \item {\tt Linda} - インスタンスを生成する際に Linda Server と接続する。メンバとしてタ プルスペースのIDを保持する({\tt tsid}) \begin{description} \item[~{\tt In(tid)}]{\tt in} コマンドを発行する。引数としてタプルID({\tt tid})を取る。返 り値は、その応答となる{\tt Reply}のインスタンス。 \item[~{\tt Rd(tid)}]{\tt read }コマンドを発行する。引数としてタプル ID({\tt tid})を取る。返り値は、その応答となる{\tt Reply}のインスタンス。 \item[~{\tt WaitRd(tid)}]{\tt wait\_rd} コマンドを発行する。引数としてタプ ルID({\tt tid})を取る。返り値は、その応答となる{\tt Reply}のインスタンス。 \item[~{\tt Out(tid, data)}]{\tt out}コマンドを発行する。引数としてタプル {\tt ID(tid)}と送信するデータを取る。 \item[~{\tt Ck(tid)}]{\tt check} コマンドを発行する。引数としてタプル ID({\tt tid})を取る。返り値は、その応答となる{\tt Reply}のインスタンス。 \item[~{\tt getid()}]タプルID 65535 の値を取得する。この値はLinda Server内部で クライアント数をカウントした値である。 \item[~{\tt close()}]Linda Server との接続を閉じる。 \end{description} \item {\tt Reply} - Linda Server から受け取ったタプルを取得するためのクラス。 \begin{description} \item[~{\tt reply()}]受け取ったタプルを取得する。タプルをまだ受け取っていなかっ たら{\tt null(None)}を返す。 \end{description} \end{itemize} Linda Server への接続は {\tt FederatedLinda} インスタンスの {\tt open} メソッドを使 う。引数として接続したいLinda Serverのホスト名とポート番号を取る。{\tt open}は {\tt Linda}インスタンスが返す。また、Linda Serverとの通信は{\tt sync}メソッドで行う。 {\tt in, read, out}などのコマンドは、{\tt Linda}インスタンスのメンバ関数から行う。 {\tt in, read}などのタプルを受け取るコマンドは、{\tt Reply}インスタンスを返す。Linda Serverからのタプルを取り出したいときは、{\tt Reply}の{\tt reply}メソッドを用いる。 %% 次の「Federated Linda を用いたプログラミング」に入れてもいいかも? \section{Local Access to Protocol} %% Client プログラムでの Linda API の使いかた %% Protocol Engine の使い分け方(タプルIDの切り替え) %% 非同期な Linda API の有効的な使いかた。?? %% ポーリング型のプログラミングを強調 ``Local Access''はプロトコルへアクセスするAPIである。APIの内容は先に説明 したので、ここではクライアントプログラムにおける Linda API を用いたプロ グラミングについて説明する。まず最初に、Linda API を使ったクライアントの ポーリング型のプログラミングについて説明する。次に、タプルスペースを 介した Protocol Engine へのアクセスについて、その利便性について説明する。 \subsection{ポーリング型のプログラミングスタイル} Federated Linda の通信は非同期に行われる。これはポーリング型のプログ ラミングスタイルで記述されることが期待されているということでもある。 Linda API を用いるプログラムではメインループが一度回ると、{\tt sync()}が一回呼 ばれるようなプログラミングスタイルになる。これは、通信が起こる回数を減ら すことと、通信箇所を明確にすることを目的としている。 以下にPerlで記述したプログラミング例を挙げる。 \begin{center} \begin{itembox}[l]{ポーリング型のプログラミング例} \begin{verbatim} # Linda Server と接続する $linda = FederatedLinda->open($hostname, $portnumber); # タプルスペースの TUPLE_ID へタプルの取得を要求する $rep = $linda->in($TUPLE_ID); # メインループ while (1) { # # 通信以外の処理 # if (($data = $rep->reply()) > 0) { # 応答が来ていたら # 繰り返しIDに対してタプルの取得要求を出す $rep = $linda->in($TUPLE_ID); # # 受け取ったデータの処理を記述 # print $data; } # コマンドやタプルの一斉送受信 FederatedLinda->sync(); } \end{verbatim} \end{itembox} \end{center} この例は {\tt \$TUPLE\_ID} で指定されたタプルスペースのタプルを取得し、標準出 力へ書き出すプログラムである。基本的な流れは以下のようになっている。まず Linda Server へ接続する。次に、使用するタプルスペースへ {\tt in} する。 この {\tt in } はその後の {\tt sync()} が実行されるまで Linda Server へは送信されない。メイン ループ内は3つのパートに分かれる。まずは``通信以外の処理''では、クライア ントの処理を行う。ここでデータのin, read, out 等を実行してもよい。次に {\tt reply()} で in/read した時の応答が受け取ったかを確認。受け取っていたなら ({\tt if} 内が実行され)受け取ったデータの処理を行う。そして最後に{\tt sync()}を呼 んで通信を行う。 この例は基本的なプログラミングである。しかし、メインループ内で {\tt sync()} は 一度だけ呼ぶ事、{\tt reply()} でデータの受信を確認する事など、ポーリングを意識 したプログラミングの特徴を表している。 また、{\tt reply()} のデータ取り出し時や {\tt sync()} の通信時で``待ち''に入る事はな い。よって、通信以外の処理が待たされることはないが、逆に通信以外の処理で ``待ち''が入ると、通信が滞る。通信以外の処理においても``待ち''が入らない ようなスタイルを取る必要がある。 \subsection{Protocol Engine へのアクセス} クライアントプログラムは使用する Protocol Engine とはタプルスペースを介 してデータをやり取りする。データのやり取りは Linda をベースにした in, read, out という分かりやすいモデルになっている。 Protocol Engine への依存は低い。実際、タプルIDを各プロトコル毎に割り当て ることにより、使用するプロトコルを切替えるということもできる。この場合、 in, read, out などのコマンドで指定する タプルID を変更するだけでいい。 以下に例を挙げる(図\ref{select_protocol}参照)。 \begin{figure}[htp] \begin{center} \includegraphics[width=8cm]{fig/select_protocol.eps} \caption{使用するプロトコルの切替え} \label{select_protocol} \end{center} \end{figure} この図の場合、タプルIDの 10000 番を Distance Vector 型 Routing Protocol に、タプルID 10001 番を Broad Cast Protocol に割り当てている。クライアン トプログラム(Client Application)は、in, read, out するときの引数として渡す タプルIDを 10000 すると Distance Vector 型 Routing Protocol を用いたデー タ転送を行い、 10001 すると全タプルスペースへ Broad Cast することになる。 プロトコルへのアクセスは in, read, out などの単純なコマンドで行われるの で分かりやすい。また、プロトコル切替えが容易であるので、多数のプロトコル を用いたプログラムを記述しやすい。 \section{Protocol Engine} %% プロトコルエンジンの書きかた %% Replyを受け取ってから、再び同じタプルIDにin/rdするとか %% プログラミングのパターンなどをソース(擬似?)を入れて説明 %% 複数のタプルスペースへのアクセスをどう制御するか?とか type 2 では Protocol Engine は Linda API を用いて実装する。よって実装の スタイル自体は Local Access to Protocol にて説明した通りである。そしてそ の API を用いて分散アルゴリズムを実装する。分散アルゴリズムは多種多様あ り、またその実装方法も多い。しかし、タプルのやり取りの部分はやタプルIDの 使いかたなどは共通しているので、その部分を説明する。 以下にマルチキャストを行うプロトコルのメインループの例を挙げる。 この例では、{\tt \$TUPLE\_ID\_CONNECT, \$TUPLE\_ID\_SEND, \$TUPLE\_ID\_RECV} の3つのタプルIDを使用している。また、接続先の Linda Server を配列を用いて管理している。 {\tt \$TUPLE\_ID\_CONNECT}に投入されたタプルは新しく接続する Linda Server の ホスト名とポート番号が入っており、{\tt getTuplespace()} 内 で {\tt FederatedLinda->open()} している。 {\tt \$TUPLE\_ID\_SEND}に投入されたタプルは、マルチキャストしたいデータを含 んでいる。よって、自分が接続している全Linda Server の{\tt \$TUPLE\_ID\_RECV} へタプルを投入する。クライアントは、データを送りたいときは {\tt \$TUPLE\_ID\_SEND}へタプルを{\tt out}し、受け取りたいときは、 {\tt \$TUPLE\_ID\_RECV}へ{\tt in}する。 \begin{center} \begin{itembox}[l]{マルチキャストのプロトコルの例} \begin{verbatim} @tuplespaces # マルチキャストする相手の Linda インスタンス $linda # 自分が担当する Linda # メインループ while (1) { # 接続に変更があった場合の処理 if (($data = $ConnectRep->reply()) > 0) { $ConnectRep = $linda->in($TUPLE_ID_CONNECT); # $dataから接続相手を得て、@tuplespaces へ加える @tuplespaces = (@tuplespaces, getTuplespace($data)); } # マルチキャスト if (($data = $MultiCastRep->reply()) > 0) { # 繰り返しIDに対してタプルの取得要求を出す $MultiCastRep = $linda->in($TUPLE_ID_MULTICAST); # 全タプルスペースへデータを送信 foreach $t (@tuplespaces) { $t->out($TUPLE_ID_RECV, $data); } } FederatedLinda->sync(); } \end{verbatim} \end{itembox} \end{center} この例では 自分が担当する Linda Server の二つのタプルID( {\tt \$TUPLE\_ID\_CONNECT, \$TUPLE\_ID\_SEND})に {\tt in} をしており、それぞれの タプルIDで取り扱われるデータを分けている。また、クライアントのデータ送信・ 受信をそれぞれ {\tt \$TUPLE\_ID\_SEND, \$TUPLE\_ID\_RECV} へ割り当てている。 このようにタプルID毎に取り扱うデータを決めておき、そのIDからのデータを受 け取ったら、対応する処理を行うということができる。当然タプルのデータ部に プロトコル独自のヘッダなどを入れて、それで行う処理を選択することもできる。 しかしその場合はデータ自身がその Protocol Engine に依存するので、他の Protocol Engine では使えなくなる。 よって、様々な Protocol Engine で使われるデータなどは、その処理の選択は タプルID毎に行うといいだろう。そうでない場合は同一タプルIDを使うとう手段 もある。 \section{Link Configuration} %% タプルスペースとの接続について %% コネクションをどう管理するか。 %% トポロジ生成について。XMLによる生成。Graffle Linda Server 間は Protocol Engine で接続される。その接続の形を規定するの が Link Configuration である。Link Configuration ではタプルスペース間を どのように接続するかを XML で記述しており、それを基にネットワークを構築 する。 図\ref{linkconfig_xml}では Configurator というプロセスが 接続状態を表し た XML を Linda Server へ投入し、そのXMLを元にトポロジを構築している。 このXMLを投入するプロセスはクライアントプログラムでも Protocol Engine で もよい。 \begin{figure}[htp] \begin{center} \includegraphics[width=13cm]{fig/lc.eps} \caption{Configuratorによるトポロジ形成} \label{linkconfig_xml} \end{center} \end{figure} Link Configuration では、取り扱う XML のパーサとトポロジの接続の状態を 表したデータ構造、接続を行う関数などをプロトコルとして Protocol Engine へ組み込めるように、モジュールとして提供している。以下ではその説明を行う。 \subsection{トポロジを表すXML} まず、トポロジを規定するXMLについて説明する。このXMLの形式は独自に定めた ものである。 以下に挙げる例は、ノード数 4 で、Ring トポロジを表した XML である。この 例を用いて XML の形式を説明する。 \begin{center} \begin{itembox}[l]{Ring トポロジを表す XML例} \begin{verbatim} <graph name = "Ring"> <node label = "lindaA" tsid = "localhost:10000"> <destination label = "lindaC"/> <destination label = "lindaB"/> </node> <node label = "lindaB" tsid = "localhost:10002"> <destination label = "lindaD"/> <destination label = "lindaA"/> </node> <node label = "lindaC" tsid = "localhost:10003"> <destination label = "lindaD"/> <destination label = "lindaA"/> </node> <node label = "lindaD" tsid = "localhost:10004"> <destination label = "lindaB"/> <destination label = "lindaC"/> </node> </graph> \end{verbatim} \end{itembox} \end{center} 各タグの説明をする。 \begin{itemize} \item {\tt graph} - トポロジを表すルートタグ \begin{description} \item [~{\tt name}] - トポロジの名前などを表す。任意 \end{description} \item {\tt node} - Linda Server を表すタグ。子要素として、接続先を表した {\tt desitination} タグを持つ。 \begin{description} \item [~{\tt label}] - ノードに付けられたラベル。この属性を元に接続状況を調べる。 \item [~{\tt tsid}] - Linda Server のタプルスペースID。どのタプルスペースがこのノー ドを担当するかを表す。 \end{description} \item {\tt destination} - 接続先を表すタグ。 \begin{description} \item [~{\tt label}] - 接続先のラベル。XML内のどの {\tt node} タグに対応するかを表す。 \end{description} \end{itemize} このXMLは非常に単純な構造をしている。まずルートタグの下には各 Linda Server を表す {\tt node} タグがある。この {\tt node} タグには各々個別の名 前({\tt lable}属性)が付けられている。また、そのノードを担当する Linda Server のタプルスペースID({\tt tsid}属性)が付いている。接続状況などは {\tt lable} を用いて表される。{\tt node} タグは子として {\tt destination} タグを持つ。{\tt destination} タグは、{\tt node} がどのノー ドと接続するかを表している。あて先は {\tt lable}属性を用いて表される。 {\tt node} タグで定義されていない {\tt lable} や、親の {\tt lable} を指定 することはできない。{\tt destination} はあて先を表しており、単方向グラフ になっている。 このXMLは Protocol Engine が解析することになる。Protocol Engine に組み込 むパーサと自身が接続する相手先を取得するモジュールを提供している。次では その説明を行う。 \subsection{接続を行うモジュール} Link Configuration では Link Configuration の XML を変換するパーサと、変 換されたデータ構造を表すクラスを提供している。図\ref{LinkConfig-class}に そのクラス図を示す。 \begin{figure}[htb] \begin{center} \includegraphics[width=13cm]{fig/LinkConfig-class-dig.eps} \end{center} \caption{LinkConfiguration のクラス図} \label{LinkConfig-class} \end{figure} 提供するクラスは、{\tt LinkConfigParser, LinkConfiguration, NodeInfo} の3つで ある。これらのメンバとメソッドの説明を以下に示す。 \begin{itemize} \item {\tt LinkConfigParser} - XMLを解析し、その結果である {\tt LinkConfiguration} インスタンスを返す \begin{description} \item [~{\tt parseLinkConfig(tsid, xmltext)}] - XMLを解析する。引数として自分のタ プルスペース ID({\tt tsid})、解析するXML({\tt xmltext})を取る。解析結果 の {\tt LinkConfiguration} インスタンスを返す。 \end{description} \item {\tt LinkConfiguration} - 各ノードの接続を表すクラス。 \begin{description} \item [~{\tt tsid}] - タプルスペースID \item [~{\tt lable}] - 自分が担当するタプルスペースのラベル \item [~{\tt linklist}] - XMLで示された全ノードの接続をハッシュとして保持。キーと してラベルを使用。値は {\tt NodeInfo} インスタンス。 \item [~{\tt getDstlist(label)}] - 引数で渡したラベルのノードが接続する相 手のラベルの配列を取得 \end{description} \item {\tt NodeInfo} - ノードを表すクラス \begin{description} \item [~{\tt tsid}] - ノードを担当するタプルスペースのID \item [~{\tt lable}] - ノードのラベル \item [~{\tt dstlist}] - ノードが接続するノードのラベルのリスト \end{description} \end{itemize} これらのクラスを使い、XMLより自分が接続する相手先のタプルスペースIDの一 覧を取得し、{\tt FederatedLinda.open} を行うことになる。{\tt Linda} クラスの管理は各 プログラムに任せる。また、{\tt LinkConfiguration} インスタンスを複数持つことに より、一つの Protocol Engine で別々のトポロジに参加することも可能である。 %% 足りない部分(動的に接続を管理)にも触れる >> できれば作りたい