\chapter{分散デバッグ機能と評価}
４章にてJava言語によるLindaサーバーとLinda APIの実装を行った事を報告した。
Java言語による実装を得た事により、Federated Lindaへの機能拡張を比較的容易に行う事が可能となった。

Federated LindaによるCompact Routingの実験においては、ルーティングテーブルの構築を例に、
分散環境でのスケーラビリティをもった実装を確認しようとしたが、現状のLindaの実装では個々のノードが
どのような通信状態をもってスケーラビリティを達成するのか明確に確認することが困難なばかりか、
格子状のメッシュ型トポロジにおける実験においては、どのような通信状態によってノード全体のスケーラビリティが低下
しているのかを確認するすべが存在しなかった。これを解決する為には、Federated Lindaの通信を阻害せずに
大域的な情報でデバッグが行えるインターフェースが必要である。

よって本章では、分散環境におけるデバッグの難しさと分散デバッグに必要な機能について説明し、
そのうちから通信状態の集中を検知するという点において、
Java版Lindaサーバーへの通信状態のデバッグインターフェースの実装と、視覚的に通信状態を確認する
モニターツール実装の二点を行い、
その評価を行う。
本論文でFederated Lindaに追加する分散デバッグ機能のアプローチは、
4章で必要性を述べた通信状態のデバッグをJava版Linda サーバーへの拡張を行う事で実現するものである。

%分散アルゴリズムのデバッグの難しさ
%逐次アルゴリズムのデバッグ手法　ーー二分法
%gdbの全ノードへの手法による限界、ログをprintfするのではダメ
%デバッグする対象　デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケット（ACK）
%個々の部品が正しく動いていても全体として正しく動かない場合がある。二分法は無力、
%スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出
%分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定
%そうすれば逐次型でデバッグできる
%重要なのはスナップショット、便利
%分散デバッグアルゴリズム自体がスケールしなければいけない、一カ所にデータを集めるのはいけない
%通信の集中は統計で見れる-> 今回はコレ
%ビジュアライゼーション、意味不明なprintfを視覚的に

\section{分散環境におけるデバッグ}
分散環境における分散プログラムのデバッグは逐次型プログラムに比べて困難である。
それは、一般的に用いられるgdbやIDE(統合開発環境)のデバッガが逐次プログラムをデバッグする為に
機能を提供するのに対して、分散プログラムには、一般的なデバッガではデバッグが困難な特徴が
存在する為である。

ここでは一般的なデバッガを用いた二分法によるデバッグ手法と、分散プログラム開発での
シーケンシャルなデバッグ手法では解決困難な問題点について説明する。
\newpage
  \subsection{二分法による逐次アルゴリズムのデバッグ}
一般的なgdbやIDEのデバッガ等を用いた二分法での逐次アルゴリズムのデバッグは、
プログラムの単体試験や結合試験工程では大変有効な手法である。

特にこの手法を用いるのにおいて適している状況は、プログラムにおけるバグの存在が既知であり、
そのバグを生じさせることが確実であるという場合である。以下に二分法の基本的な方法を示す。

\begin{center}
\begin{itembox}[l]{二分法によるデバッグ}
{\small
\begin{center}
\begin{verbatim}
[条件定義]
・バグは既知であり、再現性があること
・バグはプログラムの状態（大域変数と局所変数の値）から判断できること

[二分法]
1. プログラムの初期実行をα = s0とする
2. バグが発生している時点の実行ステートメントを β = sN とする
3. N' = N/2 とし sN'のプログラムの状態にバグがあるかどうかを調べる
4. バグがあるかないかによってα = sN'またはβ = sN'とする

5. 上記を繰り返す事により α +1 = β となる
6. これにより、バグが存在する時点の実行ステートメントとプログラムの状態を得る 
\end{verbatim}
\end{center}
}
\end{itembox}
\end{center}

上記の手法は簡単ながらも非常に強力なデバッグ手法であり、半ば自動化された作業によってバグの特定を
可能とする。
しかし、分散プログラムの開発工程においては、上記の手法では解決困難な状況が存在する。
次は、そのような状況についてFederated Lindaの通信状態のデバッグを例に説明する。
  \subsection{シーケンシャルなデバッグ手法の問題点}
二分法を用いたシーケンシャルなデバッグ手法を前述したが、分散アルゴリズムの開発においては、
二分法では解決できない状況が存在する。

その状況とは、分散環境の各ノード、つまり全体を構成する個々の部品が正しく動いていても、全体としては
正しく動かないという状況が存在する事を指す。

ここで、Federated Lindaの通信状態を例にシーケンシャルなデバッグ（つまり単体の部品のデバッグ）が
有効な場合と、単体のシーケンシャルなデバッグでは全体の動作の正しさをデバッグできない例をそれぞれ
示す。

\newpage
\subsubsection{単体のデバッグが有効な例}
図\ref{seqdeb}に示すのはFederated Lindaにおける通信にて、単体のプロセスに対する逐次デバッグが
有効な場合の通信状態である。
この通信の場合においては１つのInputに対して1つのOutputを持つプロセスのデバッグを行う事で、
全体の動作に関係する通信の流れをとらえることが可能であるからである。
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=8cm]{fig/pdf/seqdeb.pdf}
\caption{単体のデバッグが有効なFederated Lindaの通信}
\label{seqdeb}
\end{center}
\end{figure}

\vspace{-1cm}
\subsubsection{単体のデバッグでは全体の正しさをデバッグできない例}
続いて図\ref{nonseqdeb}に示すのはFederated Lindaにおける通信で、単体のデバッグでは全体の正しさを
デバッグできない例である。なぜ全体の動作に対する正しさをデバッグできないかというと、
図に示すデバッガを接続したプロセスが１つのInputに対して1つのOutputを正しく出力する事がデバッグ
できても、デバッグを行ったプロセスとは関係しない通信の流れが存在する為に、プロセスの全体の通信に対
する依存性をデバッグできない為である。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=8cm]{fig/pdf/nonseqdeb.pdf}
\caption{単体ではデバッグが困難なFederated Lindaの通信}
\label{nonseqdeb}
\end{center}
\end{figure}

このような個々のプロセスをデバッグしただけでは全体の正しさが分からない場合、gdbやIDEのデバッガとい
った逐次デバッガを全ノードに対して接続することが考えられるが、このような手法は全体を構成するノード
が大規模化した場合においてその手間やリソースの集中におけるスケーラビリティの低下や、一度に大量の
デバッグ情報が取り扱われる為に、その中から求めている情報を取捨選択することの困難さ等が問題となる
ので、全ての分散環境におけるデバッグの手法としては正しくない。

また、デバッガによるプロセスの停止によってネットワークの遅延や送信データの喪失が起これば、
全体の通信の同期に必要とされるデータが揃わないまま同期を取ることになる。
そうなると本当の意味での同期が取られていないということになり、バグ再現の為の条件が一定の通信状態
を要求する場合において問題がある。

\section{分散デバッグ機能の検討}
これまで二分法による逐次アルゴリズムのデバッグと分散環境におけるデバッグの問題点を述べた。
ここでは、Federated Lindaに必要なデバッグ機能を提案するために、分散アルゴリズムにおいてデバッグ
すべき要素を挙げ、それらをデバッグ可能な機能としてスナップショットを用いた分散デバッグを説明する。
%また、Federated Lindaを用いる事でスケーラビリティを持った分散デバッグ機能を実現することについても
%述べる。
  \subsection{分散アルゴリズムにおいてデバッグすべき対象}
%デバッグする対象　デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケット（ACK）
分散アルゴリズムにおいてデバッグすべき対象には以下のものがある。
{\large
\begin{center}
\begin{verbatim}
・デッドロック
・ライブロック
・スケーラビリティ
・通信の集中
・大量のパケットの送信
\end{verbatim}
\end{center}
}
   \subsubsection{デッドロック}
   デッドロックとは、あるプロセスが永遠にブロックされている状態を示す。そのプロセスはある条件が
   真になる（例えばある資源がreadできるようになる）のを待っているが、その条件を真にするはずの別の
   プロセスがその条件を執行しないが為に、どちらも何もできなくなるのである。

   Federated Lindaにおけるプロセスの通信は、pollingベースの通信ループを持ち、
   通信のパケットは一旦キューに溜め、ある一定のタイミングでまとめて通信を行うことから明確な「待ち」
   というプロセス状態は発生しないが、ユーザープログラムによる「待ち」処理記述の可能性からデッド
   ロックの検出は必要である。

   \subsubsection{ライブロック}
   ライブロックはデッドロックと異なり、プロセスは実行状態にあるものの、適用されるべきプログラム状態
   の変化が何も成し遂げられない状態を指す。

   例としてFederated Lindaにおけるプロセス間通信で説明すると、あるルーティングテーブルの構築に対
   して２つのプロセスがそれぞれルーティング情報を保持しており、それぞれが相手のプロセスの
   保持するルーティング情報を必要としている場合に、両者が相手のルーティング情報を得る為に自身
   の保持する情報を解放した場合が考えられる。当然ながら、この両方のプロセスは相手の情報を期待して
   いる為に実質的に何も達成できないという状態になる。

   \subsubsection{スケーラビリティ}
   スケーラビリティとは、サービスを受けるユーザー数が小規模から大規模に変化しても同じ様に同等
   の能力を発揮できるという性能基準のことである。

   Federated Lindaにおけるスケーラビリティの確認は、前提としてはノード数の増加に対する
   プログラムの実行速度やサービス提供能力のパフォーマンスを、実際のアプリケーションを用いて
   行う事があるが、現在の様に開発途中の段階では、部分的なプログラムの動作を見てその領域における
   スケーラビリティを検証することが必要である。その点においてデバッグインターフェースによる
   スケーラビリティの測定を可能とする事は重要であると考えられる。

   \subsubsection{通信の集中}
   分散プログラムの開発段階においては、通信の集中によるバグの発生は常に起こりうる事態である。
   事実、Federated LindaによるCompact Routingの実装では、ある１つのノードに対してルーティング情報が
   集中的に転送されるというバグが発生した。しかもそのようなバグは通常の逐次デバッガを用いた
   デバッグ手法では、パケット集中を行っている複数のノードに対して複合的なバグ原因を検証することは
   困難である。やはりこのような事態をデバッグするには従来の逐次デバッグとは異なる、分散デバッグ
   インターフェースをもってデバッグを行う事が必要と考える。

   \subsubsection{大量のパケットの送信}
   前述した通信の集中とは逆に、大量のパケットを単体、または複数のノードに対して通常とは異なる
   量で送信するバグも起こりうる。このような場合、大量のパケットによる多ノードへの通信集中はもち
   ろん、送信したノードからのACKnowledgementが大量にネットワーク内に流れる事による、通信効率の
   低下や輻輳の発生を生み出す可能性がある。この問題をデバッグする為には、
   プログラムが停止してからではデバッグできない事から、
   輻輳を発生させているプロトコルを動的に検知する必要がある。%###シスコのルーターはそうやってる###
   やはり、この場合も通常の逐次デバッガでは検知が困難なことから、分散デバッグインターフェースを
   用いてデバッグを行う事が望ましいと考える。


  \subsection{スナップショットによる分散デバッグ}
%スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出
%分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定
%そうすれば逐次型でデバッグできる
%重要なのはスナップショット、便利
%分散デバッグアルゴリズム自体がスケールしなければいけない、一カ所にデータを集めるのはいけない

現在主に用いられている単体の逐次デバッガは分散環境用に作られていないことから、
分散環境でのデバッグの場合、１プロセスに対してデバッガを動かすか、
複数プロセスに対してそれぞれデバッガを動かしてデバッグを行うかの
どちらかのスタイルがとられると述べたが、これではデバッグすべきプロセスが増えるとその
手間はかなりの物になり、現実的なデバッグ手法とは言えない。

また、分散プログラム環境下ではプログラム状態の非決定性が存在するため通常のデバッグには無い
問題があることも述べた。
シーケンシャルなデバッグ手法では、通信の到着順序によっても分岐が変化してしまうことから、
デバッグ対象のエラーに対して再現性を確保するのが難しいという問題である。
通常、分散環境下でのデバッグではこれらの点をふまえて、

\begin{itemize}
\item {通信におけるプログラムの状態が決定的になるようテストする}
\item {非決定性をシミュレートする}
\item {バリア同期で通信を止めてメモリ等の状態を調べる}
\item {各ノードでスナップショットを取得し、ログを解析する}
\end{itemize}

といった方法がとられる。

今回、Federated Lindaを用いた分散プログラム開発の為のデバッグインターフェースを考えるにあたって、
上記のうちから「各ノードでスナップショットを取得し、ログを解析する」という手法が最も適している
と考える。

その理由は、スナップショットを用いる事で、Federated Lindaにおける各ノードの通信を止める事無く
デバッグに必要なプログラムの状態を確認できるという点と、各ノードの大域的な状態を保存する事で
先に述べた「分散アルゴリズムにおいてデバッグすべき対象」をそれぞれデバッグすることが可能となる
からである。

以下で大域的な状態とはどのような物かを説明し、どのようにスナップショットを用いたデバッグインタ
ーフェースを用いるべきかを説明する。

\subsubsection{大域的なプログラム状態とは}
Federated Lindaにおける大域的なプログラム状態には二つの要素があり、各ノードのメモリ状態
（あるいはそれに類するデータ構造）を持つ事を第一としている。
このメモリ状態を各スナップショットでのタイミングごとに正確に
取得することにより、プログラムの大域変数や局所変数を用いたバグの特定を可能とする。

例えば、
先に述べた様なデッドロックの原因となる排他ロックの要求及び保持を検出する検出器の作成を行い、
スナップショットのログからデッドロックの追跡を行う事。または、二分法を用いてバグの存在するプロ
グラムの実行ステートメントとプログラム状態を取得する事が可能となる。

また、大域的なプログラム状態の要素として第二に、スナップショットを取るタイミングで実行中の
プロセスが発行した通信に対する状態についても取得すべきと考える。スナップショット取得のタイミングで
考えられる通信の状態は４つのパターンに分類され、そのパターンとは、
\\
\begin{itembox}[l]{-}
{\large
\begin{center}
\begin{verbatim}
スナップショット取得のタイミング = T
通信受信先でのスナップショット取得のタイミング = T'
\end{verbatim}
\end{center}
}
\end{itembox}

とすると、
\begin{itembox}[l]{-}
\begin{itemize}
\item {Tの前にパケットを送信し、T'よりも早くパケットを受け取る場合}
\item {Tの前にパケットを送信し、T'よりも遅くパケットを受け取る場合}
\item {Tの後にパケットを送信し、T'よりも早くパケットを受け取る場合}
\item {Tの後にパケットを送信し、T'よりも遅くパケットを受け取る場合}
\end{itemize}
\end{itembox}

という４つのパターンである。

この、スナップショット取得のタイミングに対する通信の状態は、プロセスの再現性や、
プロセスの状態がある時点でどのように保たれているかを検知する上での同期処理に密接に関わってくる。
通信の状態を同期する処理が行えなければ、ネットワークを介し他のノードと通信を行っている分散
プログラムの大域的状態を取得する事は、プログラム状態の決定性に欠けることとなる。
よって、分散環境でのスナップショットを考えるにあたっては、上記４パターン通信状態を
どのように同期するかが重要である。

\subsubsection{スナップショットを用いた分散デバッグ手法}
%スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出
%分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定
%そうすれば逐次型でデバッグできる

ここまで、スナップショットを用いて分散デバッグを行う事と、そのための大域的プログラム状態について
説明した。ここでは、分散環境で取得したスナップショットをどのように用いてデバッグを行うべきかを
検討する。

\subsubsection{スナップショットのモニターツールと逐次デバッガによるデバッグ}
スナップショットを取得した場合、そのスナップショット・ログは膨大である。
よって、実際にスナップショット・ログからデバッグを行う為には様々な切り口で
情報を取捨選択できるモニターツールが必要であると考える。
図\ref{snapdeb}にスナップショットのモニタツールを用いたデバッグの様子を示す。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=12cm]{fig/pdf/snapdeb.pdf}
\caption{スナップショット・ログを用いたデバッグ}
\label{snapdeb}
\end{center}
\end{figure}

上記の図ではスナップショット・ログより、大域的プログラム状態の項で
説明したプログラムのメモリー状態とスナップショット取得のタイミングにおける通信状態を同期させる
ことによってFederated Lindaの大域的状態を取得している。
また、同期されたスナップショット・ログをモニタツールという、ユーザーが必要なデバッグ情報を取捨
選択するツールを用いる事を考える。ユーザーはモニタツールを用いて（例えば二文法によるバグ箇所の
検知などを利用）、どのプロセスから出力と入力があったタプルにバグの原因があるのかを特定するこ
とができる。そうすれば、その後のバグの修正においては逐次デバッガによるデバッグが可能となる。

\subsection{分散デバッグ機能のスケーラビリティ}
全ノードに対してデバッグプロセスを走らせてデバッグを行うような
手法は、デバッグのインターフェースにおけるスケーラビリティを考慮してはいない。

事実、システム資源の異なるノードに対してネットワークを介したリモートデバッグの手法は
数多く開発されていても、それが大規模システムを想定した分散プログラムに対してスケーラビリティを
保ったままデバッグ可能という解を得てはいない。

Federated Lindaはタプルのリレーという、より分散プログラムを意識したモデルであることから、デバッグ
インターフェースの大域的状態の取得にもスケーラビリティを持った実装を目指す。
その基本的なアイデアは、デバッグ情報を取得するインターフェースに対してもLindaプロトコルによるタプ
ルの伝搬を利用して実装するというものである。

下図\ref{FDLindaDebug}に示すように、Federated Lindaを用いたデバッグインターフェースは、デバッガ
プロセスからあるノードに対してデバッグ情報の取得を指示するオペレーションを発行し、デバッグ情報の
取得を行うデバッグプロトコルとしてタプル間を伝搬させる。
デバッガが受け取る結果はFederared Linda内のスナップショットとしての大域的状態であり、それを元に
デバッグを行う。このような仕組みをとる事で、大規模な分散プログラム環境であってもスケーラビリティ
を保ったままデバッグを行う事が可能となる。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=14cm]{fig/pdf/FDLindaDebug.pdf}
\caption{スケーラビリティを意識したデバッグインターフェース}
\label{FDLindaDebug}
\end{center}
\end{figure}

%\newpage
\section{通信状態デバッグインターフェースの実装}
ここまで、Federated Lindaを用いた分散環境環境における分散デバッグインターフェースの機能の検討
を行った。その結果、Federated Lindaで用いられるべき分散デバッグインターフェースはスナップショット
を用いて、デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケットの送信、といった
要素のデバッグを行う事が必要との結論を得た。

しかし、検討したスナップショットでのデバッグインターフェースの実装の為には、現実装の
Federated Lindaで用いられるProtocol Engineには更なる改良が必要である。なぜならば、現在のProtocol
 Engineはルーティングテーブルを内部データとして保持することから、Federated Lindaの大域的状態を
取得するにはProtocol Engineまでのスナップショットが必要となるからである。
これを解消する為にはProtocol Engineの内部状態をステートレスに実装し、その挙動はやり取りするXML
に全て埋め込むという実装が求められる。

本論文では、前述した分散アルゴリズムにおいてデバッグすべき対象のうちから、
通信の集中を検知するデバッグインターフェースについて実装を行った。
このデバッグインターフェースを用いる事により、３章で提示したCompact Routingを用いるFederated Linda
において、格子状のメッシュ型トポロジで起こった、デバッグ困難な通信の集中を伴う状態の検知を行う事を目標とする。
以下にその詳細を示す。


  \subsection{Java版Linda サーバーへの機能実装}
通信状態デバッグインターフェースとしてJava版のタプルサーバーへの機能拡張を行った。
この実装はFederated Lindaの通信を止めずに、通信のログを取りたい時に各Java版Lindaサーバーへデバッグ
タスクを投入し、デバッグタスクを切断してもFederated Lindaの通信状況は変化せず続く、というように
Federated Lindaを動かしながらのConnect,Disconnectに対応する。
図\ref{comdebug1}にその様子を示す。
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=16cm]{fig/pdf/comdebug1.pdf}
\caption{デバッグタスクのConnect,Disconnect処理}
\label{comdebug1}
\end{center}
\end{figure}

Federated Lindaの通信を止める事無く通信のデバッグタスクを投入できることで、通信ログが欲しい
状況に適宜、通信デバッグタスクを投入することができる。また、Federated Linda全体の通信状態の
遷移が知りたい場合は、Federated Lindaを構成するLindaサーバーの全てに対して通信デバッグタスクを
投入し、Federated Linda内部のシーケンス番号やタプルID、または時系列情報をもとにその整合を行う。
図\ref{comdebug2}に実装したデバッグインターフェースの動作の様子を示す。
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=16cm]{fig/pdf/comdebug2.pdf}
\caption{通信状態のデバッグインターフェース}
\label{comdebug2}
\end{center}
\end{figure}

\newpage
  \subsection{実装の詳細}
今回、Java版タプルサーバーへの機能拡張として追加した、通信状態のデバッグインターフェースは、
以下のクラスから構成される。
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=14cm]{fig/pdf/comdebugClass.pdf}
\caption{通信デバッグインターフェースのクラス図}
\label{comdebugClass}
\end{center}
\end{figure}

class ComDebugはJava版Lindaサーバーにおける通信状態のデバッグインターフェースを提供する。
通信状態のログはハッシュテーブルであるCom\_Hashtableに蓄えられ、デバッグインターフェースの
接続先を表すリンクドリストのReport\_Channellistに対して、Report()メソッドを用いてデバッグクライア
ントにLindaのタプルとして送信される。

class ComDebug\_Clientは通信状態のデバッグインターフェースにおけるクライアントプログラムであり、
その実行時にLindaサーバーのホストネームとポート番号を指定して接続する。クライアントプログラムの
通信ループはclass FederatedLinda.java, class PSXLinda.javaで定義されたSelectorベースのLinda APIの
通信ループを用いる。クライアントプログラムが受け取る通信パケットはLindaのタプルデータである。

\subsubsection{機能拡張を行ったLindaサーバーの通信ループ}
以下に、今回の通信状態デバッグインターフェース拡張を行った、Java版Lindaサーバーの通信ループ
を示す。
\begin{center}
\begin{itembox}[l]{ComDebug機能拡張部分}
{\footnotesize
\begin{verbatim}
   if (debug) {
      System.out.println("data from : "+key.channel());
   }
   if((mode == '!') || (len == 0)) {
      ClosewishComDebug(key, command, reportCh_list);
   }
   else if(mode == PSX_CHECK) {
      sendtext = Check(key, command);
   }
   else if(mode == PSX_IN || mode == PSX_RD){
      sendtext = In_Rd(key, command, mode);
   } else if (mode == PSX_WAIT_RD) {	
      Wait_Rd(key, command, mode);						
   } else if(mode == PSX_OUT) {
      sendtext = Out(command, data);		
   } else {
      System.out.println("Uncorrect buffer");
      System.exit(1);
   }	
   //COM_DEBUG
   if(id > PRIVILEGED_ID_START && id < PRIVILEGED_ID_END){
      ComDebug.addChannel(key, reportCh_list);
   }
   //DEBUG用カウンタ
   String debug_rep = ComDebug.Com_inc(key, com_Loggingtable, 
                                       mode, id, seq, sendtext);
   //DEBUG用レポート
   ComDebug.Report(reportCh_list, command, debug_rep);
\end{verbatim}
}
\end{itembox}
\end{center}
通信ループ内において、通信状態のデバッグインターフェースを受け付けるのは、要求があった
idがPRIVILEGED(特権的な)\_IDとして確保した領域であった場合である。今回は1〜65535ま
でのタプルスペースIDのうちidが32769以降の場合において、その要求をデバッグインター
フェースの為の特権IDとして用いた。特権IDでの要求を検知した場合、ComDebug.addChannel
を行い、通信状態の報告を行うセッションのリストに追加を行う。
また、報告を行っていたセッションが切断された場合はコネクションのクローズ処理と共に、
reportCh\_remove()メソッドによって報告セッションリストから対象の削除を行う。これにより、
デバッグインターフェースの動的な接続と切断が実現される。

ComDebug.Com\_inc(),ComDebug\_Report()においては通信状態の更新と報告を行う。
これらのコードの追加によって、Java版Lindaサーバーへの通信状態のデバッグインターフェ
ース機能拡張を行った。

\subsubsection{ComDebug\_Clientの出力ログ}
最後に、この通信デバッグインターフェースを用いて取得したログを示す。
このデバッグインターフェースを用いて取得できるログは以下の様になっている。
\begin{center}
{\footnotesize
\begin{verbatim}
start : java -classpath FederatedLinda-Java/bin fdl.ComDebug_Client
 -h ged.cr.ie.u-ryukyu.ac.jp  -p 10000 &
Connected:PSXLinda: true
COM_DEBUG Connected.[ged.cr.ie.u-ryukyu.ac.jp:10000]
1203044062523 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54481 i=2 id=32769 seq=3 data=none
1203044071138 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54482 i=1 id=65535 seq=3224368 data=02
1203044071266 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54482 i=2 id=1 seq=3224368 data=none
1203044071273 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54482 i=3 id=2 seq=3201696 data=none
1203044093482 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54488 o=1 id=1 seq=0 data=<graph name = "Graf">
  <node label = "A" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10000">
        <destination label = "B"/>
  </node>
  <node label = "B" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10001">
        <destination label = "C"/>
        <destination label = "D"/>
  </node>
  <node label = "C" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10002">
        <destination label = "D"/>
  </node>
  <node label = "D" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10003">
        <destination label = "A"/>
  </node>
</graph>

CloseInfo >133.13.57.210:10000--133.13.57.210:54488
1203044093772 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54482 i=4 id=1 seq=3224368 data=none
1203044094228 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54492 i=1 id=65535 seq=3269152 data=03
1203044094427 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
54492 o=1 id=2 seq=0 data=ged.cr.ie.u-ryukyu.ac.jp:10001
.....
\end{verbatim}
}
\end{center}

  \subsection{視覚的に通信状態を確認するツールの開発}
Lindaサーバーへの通信状態デバッグ機能の追加と、その為のクライアントプログラムによって、
Federated Lindaの通信状態のログを取得する事ができた。しかし、取得したログはそれだけではどのよう
な通信状態の変化があったのかを直感的に知る事は難しい。よって、前述したデバッグインタ
ーフェースを用いて取得したログを、視覚的に確認できるツールの開発を行った。

このツールは、Federated LindaのLink Configurationに用いたOmni Graffleファイル、
同じくLink Configurationに用いたノードリスト、そしてデバッグインターフェースで取得した通信
状態のログ、をもとにその通信状態をモニターする為のツールである。
図\ref{comdeb}にその様子を示す。

\begin{figure}[htbp]
\begin{center}
\includegraphics[width=14cm]{fig/pdf/comdeb.pdf}
\caption{通信状態の表示ツール利用}
\label{comdeb}
\end{center}
\end{figure}

ツールの開発はログのパースと格納をPythonによって行い、GUI部分の表示においてはwxPythonを用いて
実装した。wxPythonとは、フリーの GUI ツールキット wxWidgets の Python バインディングであり、
Windows, MacOSX, その他 GTK ベースの UNIX システムの多くで利用可能である。

\subsubsection{バインディングとは}
プログラムの実行時間の8割9割がコードの1割2割の部分（ホットスポット）で費されるという
経験則は広く知られている。したがって、ホットスポットをCで記述して
実行効率の改善を図り、ホットスポット以外をスクリプト言語で記述するという手法が
有用である。そうすれば、実行速度と開発速度の双方を高めることができるからである。
そこで、CやC++で書かれたモジュールを各種のスクリプト言語から呼び出せるようにする機構が
必要になるが、それをスクリプト言語バインディングと呼ぶ。


\subsubsection{通信ログ・モニターツール}
今回作成したツールの構成は以下のようになっている。
\begin{center}
\begin{itembox}[l]{各Pythonスクリプト}
%{\footnotesize
\begin{verbatim}
   [Omni Graffleパース担当]
   ・Graffle2Arrangement.py
     -- パースされたデータからラベル付けされたノードクラスを生成
      ・ParseGraffle.py
        -- Onmi Graffleファイルをパースする
         ・PListReader.py
           -- Apple plist XML 形式のデータを読み込む

   [wxPythonによる表示担当]
   ・run.py
     -- 実行スクリプト、メイン処理ルーチンとしてVisualizer.pyを呼ぶ
      ・Visualizer.py
        -- 描画処理、イベントハンドラ処理を記述
         ・images.py
           -- エンコード済みBitmapデータ(Base64エンコード)
\end{verbatim}
%}
\end{itembox}
\end{center}

作成したツールは、通信状態のログを取得したFederated Lindaのトポロジ構成を、
Federated LindaのLink Configurationで使用したOmni Graffleファイルとノードリストから生成して表示する。
その後、表示したトポロジ図のノードと投入する通信状態のログからそれぞれのマッチングを行い、
通信状態の変化をステップ実行で確認できる。

ツール上に表示可能な通信ログのデータは、送信ノードのTSID, 受信ノードのTSID, In/Out/Rd/Ck の
モード情報と累積発行回数, タプルID, シーケンス番号, タプルのデータ内容, である。
図\ref{visual01}に通信ログ・モニタツールの動作状況を示す。
\newpage
\begin{figure}[htbp]
\begin{center}
\includegraphics[width=16cm]{fig/pdf/visual01.pdf}
\caption{通信量のグラフィカルな表示ツール}
\label{visual01}
\end{center}
\end{figure}

\section{Federated Lindaの実装を用いたデバッグインターフェースの評価}
実装した通信状態のデバッグインターフェースの評価として、3章で述べたDistance Vector型及び、
Compact Routingの実装を用いるFederated Lindaの通信状態デバッグを行う。
この評価の狙いは通信デバッグインターフェースを用いることで、従来のFederated Lindaにおける
printf情報などを用いたテスト駆動開発では困難であった、通信状態の確認を可能とする事である。
また、この評価によるバグ要因の特定も目標とする。

  \subsection{評価条件}
  \subsubsection{問題点}
  Federated Lindaは分散アルゴリズムを用いてタプルの伝搬を行うが、先行研究にて開発した
  Distance Vector型及び、Compact Routingの実装は共に格子状のメッシュ型トポロジ上での
  ルーティングテーブルの構築に問題がある。Distance Vector型はメッシュ型トポロジ上での
  ルーティングテーブル
  の構築が、ライン型トポロジや、バイナリツリー型トポロジとの場合に比べて、
  大幅に時間がかかるという問題、
  Compact Routingの実装では格子状のメッシュ型トポロジ上でのルーティングテーブルの構築が、
  通信の集中や、Landmark情報の更新の失敗によって、構築が行えないという問題である。
  図\ref{meshtime}にDistance Vector型において格子状のメッシュ型トポロジでのルーティングテーブルの
  構築時間とバイナリツリー型トポロジによる物を比較した結果を示す。

  \begin{figure}[htbp]
   \begin{center}
    \includegraphics[width=14cm]{fig/pdf/exetime.pdf}
    \caption{ノード数に対してルーティングテーブル構築にかかる時間}
    \label{meshtime}
   \end{center}
  \end{figure}

  結果から分かる様に、ルーティングテーブルの構築時間はノード数に対して2乗オーダー
  的に増加する。このような結果は、たとえノード間のリンク数がバイナリツリー型トポロジに比べて、
  メッシュトポロジの方が多いと考えても大きすぎると考える。また、Distance Vector型を元に実装を
  行ったCompact Routingの実装も格子状のメッシュトポロジ上ではルーティングテーブルの構築に致命的な
  問題がある。このような問題点は、現実装になんらかのバグが存在する為と考え、今回実装したデバッグ
  インターフェースによるデバッグを行う。

  \subsubsection{実験を行う Federated Lindaの構成}
  ルーティングテーブルの構築は6ノードで構成される格子状のメッシュトポロジにおいて行い。
  その通信状態を、実装した通信状態のデバッグインターフェースでログの取得を行った。
  図\ref{meshgraffle}にFederated LindaのLink Configurationに用いたOmni graffleファイルを示す。

  \begin{figure}[htbp]
   \begin{center}
    \includegraphics[width=14cm]{fig/pdf/clsmesh006.pdf}
    \caption{Link Configurationに用いたOmni Graffleファイル}
    \label{meshgraffle}
   \end{center}
  \end{figure}

  \subsubsection{通信状態のデバッグを行う実験}
  実装したデバッグインターフェースによるログ取得を行うのは以下の２実験である。
\begin{itemize}
\item {6ノードの格子状メッシュトポロジにおけるDistance Vector型のルーティングテーブル構築}
\item {6ノードの格子状メッシュトポロジにおけるCompact Routing実装のルーティングテーブル構築}
\end{itemize}



  \subsection{評価}
  評価条件に示した実験を行い、6ノードで構成される格子状のメッシュトポロジにおける
  Federated Lindaのルーティングテーブル構築の通信状態ログを取得した。

  これにより、通信状態ログを用いたモニターツールでのデバッグが可能となった。
  ここで示す通信状態ログによるデバッグとは、Lindaサーバー単体、Lindaサーバー全体、タプルID、
  シーケンス番号などを単位に通信ログをモニターツールに投入し、ステップ実行でタプルの通信を
  確認するデバッグ方法である。
  図\ref{debug1}と図\ref{debug2}にその様子を示す。

  \begin{figure}[htbp]
   \begin{center}
    \includegraphics[width=12cm]{fig/pdf/debug1.pdf}
    \caption{トポロジ及び通信イベントの表示}
    \label{debug1}
   \end{center}
  \end{figure}

   \begin{figure}[htbp]
   \begin{center}
    \includegraphics[width=12cm]{fig/pdf/debug2.pdf}
    \caption{ステップ実行したシーケンスでの転送タプルを表示}
    \label{debug2}
   \end{center}
  \end{figure}
  
  \newpage
  \subsubsection{バグ要因の特定}
  通信ログ・モニターツールを用いてDistace Vector型、Compact Routing実装のデバッグを
  行った所、Link Configuratin処理が正しく終了していない為に、ルーティングテーブル構築時の
  通信量が増えているというバグを発見した。

  通常、Federated Lindaにおけるルーティングテーブルの構築は、最初にLink Configurationを
  示したXMLの投入をある1ノードに行い、そのノードから隣接ノードへのLink Configuratin XML
  の転送とコネクトをもって全ノード間のコネクションのLink Configurationを行う。

  しかし、格子状のメッシュトポロジでは、隣接ノードへの転送から次ノードへ別経路で
  Link Configurationが到達する為、Link Configuratinを行うタプル転送が消滅せずに、
  ルーティングテーブルの構築中でもLink Configurationが発生しているというバグである。

  図\ref{bugfig}にその様子を示す。

   \begin{figure}[htbp]
   \begin{center}
    \includegraphics[width=14cm]{fig/pdf/bug.pdf}
    \caption{格子状メッシュトポロジにおけるLink Configurationのバグ}
    \label{bugfig}
   \end{center}
  \end{figure}
 
 ルーティングテーブルの構築時においてもLink Configurationのタプル転送が発生していたことで、
 Distance Vector型での構築時間はバイナリツリー型トポロジに対して大幅に増加していたという
 ことが、今回の通信状態デバッグインターフェースによって特定できた。また、Compact Routing実装の、
 格子状メッシュトポロジにおけるルーティングテーブルの構築失敗もローカルネットワークの構築と
 Landmark情報の更新にDistance Vector型の転送方法を用いている為に、同様に別経路からの情報更新
 要求が正常終了せずに流れている為と分かった。

 \subsubsection{デバッグにおけるモニターツールの有用性}
 なぜこのようなバグをこれまで特定することが出来なかったのかというと、これまでのFederated Linda
 による分散アルゴリズムの開発は、多数のターミナルによるテスト駆動でプログラム状態の変化を標準出力へ
 表示させるという手法をとっていたからである。逐次プログラムの開発においては、標準出力へのprintf
 デバッグは有効なデバッグ手法と言えるが、ノード全体の通信を止めずにテストを行わなければならない
 状況が存在する分散プログラムの開発では、大量のprintf情報が全ノード分出力されるため、
 printfデバッグは実用的とは言えない。

 今回、通信状態のデバッグインターフェースと、そのログを視覚的に表示し、ステップ実行により通信の
 確かさを確認できるモニターツールを開発したことにより、これまで困難であった通信状態のデバッグ
 を可能とした。



\section{考察}
本章では分散環境(特にFederated Lindaを用いた)におけるデバッグ機能について、その実装を行う為に、
最初に二分法を用いた基本的な逐次デバッグ手法と、それではデバッグ困難な分散環境での通信状態を
紹介し、それらより分散デバッグ機能の検討を行った。分散アルゴリズムにおいてデバッグすべき対象には、
デッドロック, ライブロック, スケーラビリティ, 通信の集中, 大量のパケットの送信, 等があり、
それらをデバッグするには大域的なプログラム状態を取得する分散スナップショットが有効であることを
示した。

Java版Lindaサーバーを開発したことにより、以前のC言語による実装よりも機能拡張を容易に行う事が
可能となった。そのため、前述した分散アルゴリズムにおいてデバッグすべき対象のうち、通信の集中
を検知できるデバッグインターフェースとして、通信状態のログ取得デバッグインターフェースと、
そのログを視覚的に表示し、ステップ実行で通信の状態を確かめられるログ・モニターツールを開発した。

開発した通信状態のデバッグインターフェースの評価として、6ノードで構成される格子状メッシュトポロジ
におけるルーティングテーブルの構築を、Distance Vectorg型とCompact Routing実装のFederated Lindaで
行い、通信状態のデバッグインターフェースを適用した。
この結果、正常終了しなかったLink Configurationのタプル転送が別経路から送信されているというバグ
要因を特定した。

通信状態のログ・モニターツールを用いる事で、これまでprintfによるデバッグでは困難であった通信状態
の確認を非常に分かりやすく行うことができる。これは、スナップショットを用いたログデバッグであっても
同様で、デッドロック, ライブロック, スケーラビリティ, 通信の集中, 大量のパケットの送信, 
等の効率的な
検知を行うには、なんらかのスナップショット・モニターツールの開発が必要であると考える。