|
0
|
1 \chapter{分散デバッグ機能と評価}
|
|
3
|
2 ４章にてJava言語によるLindaサーバーとLinda APIの実装を行った事を報告した。
|
|
|
3 Java言語による実装を得た事により、Federated Lindaへの機能拡張を比較的容易に行う事が可能となった。
|
|
4
|
4
|
|
|
5 Federated LindaによるCompact Routingの実験においては、ルーティングテーブルの構築を例に、
|
|
|
6 分散環境でのスケーラビリティをもった実装を確認しようとしたが、現状のLindaの実装では個々のノードが
|
|
|
7 どのような通信状態をもってスケーラビリティを達成するのか明確に確認することが困難なばかりか、
|
|
13
|
8 格子状のメッシュ型トポロジにおける実験においては、どのような通信状態によってノード全体のスケーラビリティが低下
|
|
4
|
9 しているのかを確認するすべが存在しなかった。これを解決する為には、Federated Lindaの通信を阻害せずに
|
|
|
10 大域的な情報でデバッグが行えるインターフェースが必要である。
|
|
|
11
|
|
13
|
12 よって本章では、分散環境におけるデバッグの難しさと分散デバッグに必要な機能について説明し、
|
|
|
13 そのうちから通信状態の集中を検知するという点において、
|
|
|
14 Java版Lindaサーバーへの通信状態のデバッグインターフェースの実装と、視覚的に通信状態を確認する
|
|
|
15 モニターツール実装の二点を行い、
|
|
|
16 その評価を行う。
|
|
4
|
17 本論文でFederated Lindaに追加する分散デバッグ機能のアプローチは、
|
|
|
18 4章で必要性を述べた通信状態のデバッグをJava版Linda サーバーへの拡張を行う事で実現するものである。
|
|
0
|
19
|
|
3
|
20 %分散アルゴリズムのデバッグの難しさ
|
|
|
21 %逐次アルゴリズムのデバッグ手法 ーー二分法
|
|
|
22 %gdbの全ノードへの手法による限界、ログをprintfするのではダメ
|
|
|
23 %デバッグする対象 デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケット（ACK）
|
|
|
24 %個々の部品が正しく動いていても全体として正しく動かない場合がある。二分法は無力、
|
|
|
25 %スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出
|
|
|
26 %分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定
|
|
|
27 %そうすれば逐次型でデバッグできる
|
|
5
|
28 %重要なのはスナップショット、便利
|
|
3
|
29 %分散デバッグアルゴリズム自体がスケールしなければいけない、一カ所にデータを集めるのはいけない
|
|
5
|
30 %通信の集中は統計で見れる-> 今回はコレ
|
|
3
|
31 %ビジュアライゼーション、意味不明なprintfを視覚的に
|
|
|
32
|
|
|
33 \section{分散環境におけるデバッグ}
|
|
4
|
34 分散環境における分散プログラムのデバッグは逐次型プログラムに比べて困難である。
|
|
|
35 それは、一般的に用いられるgdbやIDE(統合開発環境)のデバッガが逐次プログラムをデバッグする為に
|
|
|
36 機能を提供するのに対して、分散プログラムには、一般的なデバッガではデバッグが困難な特徴が
|
|
|
37 存在する為である。
|
|
0
|
38
|
|
4
|
39 ここでは一般的なデバッガを用いた二分法によるデバッグ手法と、分散プログラム開発での
|
|
|
40 シーケンシャルなデバッグ手法では解決困難な問題点について説明する。
|
|
|
41 \newpage
|
|
3
|
42 \subsection{二分法による逐次アルゴリズムのデバッグ}
|
|
4
|
43 一般的なgdbやIDEのデバッガ等を用いた二分法での逐次アルゴリズムのデバッグは、
|
|
|
44 プログラムの単体試験や結合試験工程では大変有効な手法である。
|
|
3
|
45
|
|
4
|
46 特にこの手法を用いるのにおいて適している状況は、プログラムにおけるバグの存在が既知であり、
|
|
|
47 そのバグを生じさせることが確実であるという場合である。以下に二分法の基本的な方法を示す。
|
|
|
48
|
|
|
49 \begin{center}
|
|
|
50 \begin{itembox}[l]{二分法によるデバッグ}
|
|
|
51 {\small
|
|
|
52 \begin{center}
|
|
|
53 \begin{verbatim}
|
|
|
54 [条件定義]
|
|
|
55 ・バグは既知であり、再現性があること
|
|
|
56 ・バグはプログラムの状態（大域変数と局所変数の値）から判断できること
|
|
|
57
|
|
|
58 [二分法]
|
|
|
59 1. プログラムの初期実行をα = s0とする
|
|
|
60 2. バグが発生している時点の実行ステートメントを β = sN とする
|
|
|
61 3. N' = N/2 とし sN'のプログラムの状態にバグがあるかどうかを調べる
|
|
|
62 4. バグがあるかないかによってα = sN'またはβ = sN'とする
|
|
|
63
|
|
|
64 5. 上記を繰り返す事により α +1 = β となる
|
|
|
65 6. これにより、バグが存在する時点の実行ステートメントとプログラムの状態を得る
|
|
|
66 \end{verbatim}
|
|
|
67 \end{center}
|
|
|
68 }
|
|
|
69 \end{itembox}
|
|
|
70 \end{center}
|
|
|
71
|
|
|
72 上記の手法は簡単ながらも非常に強力なデバッグ手法であり、半ば自動化された作業によってバグの特定を
|
|
|
73 可能とする。
|
|
|
74 しかし、分散プログラムの開発工程においては、上記の手法では解決困難な状況が存在する。
|
|
17
|
75 次は、そのような状況についてFederated Lindaの通信状態のデバッグを例に説明する。
|
|
3
|
76 \subsection{シーケンシャルなデバッグ手法の問題点}
|
|
4
|
77 二分法を用いたシーケンシャルなデバッグ手法を前述したが、分散アルゴリズムの開発においては、
|
|
|
78 二分法では解決できない状況が存在する。
|
|
|
79
|
|
|
80 その状況とは、分散環境の各ノード、つまり全体を構成する個々の部品が正しく動いていても、全体としては
|
|
|
81 正しく動かないという状況が存在する事を指す。
|
|
|
82
|
|
|
83 ここで、Federated Lindaの通信状態を例にシーケンシャルなデバッグ（つまり単体の部品のデバッグ）が
|
|
|
84 有効な場合と、単体のシーケンシャルなデバッグでは全体の動作の正しさをデバッグできない例をそれぞれ
|
|
|
85 示す。
|
|
|
86
|
|
|
87 \newpage
|
|
|
88 \subsubsection{単体のデバッグが有効な例}
|
|
16
|
89 図\ref{seqdeb}に示すのはFederated Lindaにおける通信にて、単体のプロセスに対する逐次デバッグが
|
|
4
|
90 有効な場合の通信状態である。
|
|
|
91 この通信の場合においては１つのInputに対して1つのOutputを持つプロセスのデバッグを行う事で、
|
|
|
92 全体の動作に関係する通信の流れをとらえることが可能であるからである。
|
|
|
93 \begin{figure}[htbp]
|
|
|
94 \begin{center}
|
|
|
95 \includegraphics[width=8cm]{fig/pdf/seqdeb.pdf}
|
|
|
96 \caption{単体のデバッグが有効なFederated Lindaの通信}
|
|
|
97 \label{seqdeb}
|
|
|
98 \end{center}
|
|
|
99 \end{figure}
|
|
|
100
|
|
|
101 \vspace{-1cm}
|
|
|
102 \subsubsection{単体のデバッグでは全体の正しさをデバッグできない例}
|
|
|
103 続いて図\ref{nonseqdeb}に示すのはFederated Lindaにおける通信で、単体のデバッグでは全体の正しさを
|
|
|
104 デバッグできない例である。なぜ全体の動作に対する正しさをデバッグできないかというと、
|
|
|
105 図に示すデバッガを接続したプロセスが１つのInputに対して1つのOutputを正しく出力する事がデバッグ
|
|
|
106 できても、デバッグを行ったプロセスとは関係しない通信の流れが存在する為に、プロセスの全体の通信に対
|
|
|
107 する依存性をデバッグできない為である。
|
|
|
108
|
|
|
109 \begin{figure}[htbp]
|
|
|
110 \begin{center}
|
|
|
111 \includegraphics[width=8cm]{fig/pdf/nonseqdeb.pdf}
|
|
|
112 \caption{単体ではデバッグが困難なFederated Lindaの通信}
|
|
|
113 \label{nonseqdeb}
|
|
|
114 \end{center}
|
|
|
115 \end{figure}
|
|
|
116
|
|
|
117 このような個々のプロセスをデバッグしただけでは全体の正しさが分からない場合、gdbやIDEのデバッガとい
|
|
|
118 った逐次デバッガを全ノードに対して接続することが考えられるが、このような手法は全体を構成するノード
|
|
|
119 が大規模化した場合においてその手間やリソースの集中におけるスケーラビリティの低下や、一度に大量の
|
|
|
120 デバッグ情報が取り扱われる為に、その中から求めている情報を取捨選択することの困難さ等が問題となる
|
|
|
121 ので、全ての分散環境におけるデバッグの手法としては正しくない。
|
|
|
122
|
|
|
123 また、デバッガによるプロセスの停止によってネットワークの遅延や送信データの喪失が起これば、
|
|
|
124 全体の通信の同期に必要とされるデータが揃わないまま同期を取ることになる。
|
|
|
125 そうなると本当の意味での同期が取られていないということになり、バグ再現の為の条件が一定の通信状態
|
|
|
126 を要求する場合において問題がある。
|
|
3
|
127
|
|
6
|
128 \section{分散デバッグ機能の検討}
|
|
4
|
129 これまで二分法による逐次アルゴリズムのデバッグと分散環境におけるデバッグの問題点を述べた。
|
|
|
130 ここでは、Federated Lindaに必要なデバッグ機能を提案するために、分散アルゴリズムにおいてデバッグ
|
|
|
131 すべき要素を挙げ、それらをデバッグ可能な機能としてスナップショットを用いた分散デバッグを説明する。
|
|
|
132 %また、Federated Lindaを用いる事でスケーラビリティを持った分散デバッグ機能を実現することについても
|
|
|
133 %述べる。
|
|
|
134 \subsection{分散アルゴリズムにおいてデバッグすべき対象}
|
|
|
135 %デバッグする対象 デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケット（ACK）
|
|
|
136 分散アルゴリズムにおいてデバッグすべき対象には以下のものがある。
|
|
|
137 {\large
|
|
|
138 \begin{center}
|
|
|
139 \begin{verbatim}
|
|
|
140 ・デッドロック
|
|
|
141 ・ライブロック
|
|
|
142 ・スケーラビリティ
|
|
|
143 ・通信の集中
|
|
|
144 ・大量のパケットの送信
|
|
|
145 \end{verbatim}
|
|
|
146 \end{center}
|
|
|
147 }
|
|
|
148 \subsubsection{デッドロック}
|
|
|
149 デッドロックとは、あるプロセスが永遠にブロックされている状態を示す。そのプロセスはある条件が
|
|
|
150 真になる（例えばある資源がreadできるようになる）のを待っているが、その条件を真にするはずの別の
|
|
|
151 プロセスがその条件を執行しないが為に、どちらも何もできなくなるのである。
|
|
3
|
152
|
|
17
|
153 Federated Lindaにおけるプロセスの通信は、pollingベースの通信ループを持ち、
|
|
4
|
154 通信のパケットは一旦キューに溜め、ある一定のタイミングでまとめて通信を行うことから明確な「待ち」
|
|
|
155 というプロセス状態は発生しないが、ユーザープログラムによる「待ち」処理記述の可能性からデッド
|
|
|
156 ロックの検出は必要である。
|
|
|
157
|
|
|
158 \subsubsection{ライブロック}
|
|
|
159 ライブロックはデッドロックと異なり、プロセスは実行状態にあるものの、適用されるべきプログラム状態
|
|
|
160 の変化が何も成し遂げられない状態を指す。
|
|
|
161
|
|
|
162 例としてFederated Lindaにおけるプロセス間通信で説明すると、あるルーティングテーブルの構築に対
|
|
|
163 して２つのプロセスがそれぞれルーティング情報を保持しており、それぞれが相手のプロセスの
|
|
|
164 保持するルーティング情報を必要としている場合に、両者が相手のルーティング情報を得る為に自身
|
|
|
165 の保持する情報を解放した場合が考えられる。当然ながら、この両方のプロセスは相手の情報を期待して
|
|
|
166 いる為に実質的に何も達成できないという状態になる。
|
|
|
167
|
|
|
168 \subsubsection{スケーラビリティ}
|
|
|
169 スケーラビリティとは、サービスを受けるユーザー数が小規模から大規模に変化しても同じ様に同等
|
|
|
170 の能力を発揮できるという性能基準のことである。
|
|
|
171
|
|
|
172 Federated Lindaにおけるスケーラビリティの確認は、前提としてはノード数の増加に対する
|
|
|
173 プログラムの実行速度やサービス提供能力のパフォーマンスを、実際のアプリケーションを用いて
|
|
|
174 行う事があるが、現在の様に開発途中の段階では、部分的なプログラムの動作を見てその領域における
|
|
|
175 スケーラビリティを検証することが必要である。その点においてデバッグインターフェースによる
|
|
|
176 スケーラビリティの測定を可能とする事は重要であると考えられる。
|
|
|
177
|
|
|
178 \subsubsection{通信の集中}
|
|
|
179 分散プログラムの開発段階においては、通信の集中によるバグの発生は常に起こりうる事態である。
|
|
|
180 事実、Federated LindaによるCompact Routingの実装では、ある１つのノードに対してルーティング情報が
|
|
|
181 集中的に転送されるというバグが発生した。しかもそのようなバグは通常の逐次デバッガを用いた
|
|
|
182 デバッグ手法では、パケット集中を行っている複数のノードに対して複合的なバグ原因を検証することは
|
|
|
183 困難である。やはりこのような事態をデバッグするには従来の逐次デバッグとは異なる、分散デバッグ
|
|
5
|
184 インターフェースをもってデバッグを行う事が必要と考える。
|
|
4
|
185
|
|
|
186 \subsubsection{大量のパケットの送信}
|
|
|
187 前述した通信の集中とは逆に、大量のパケットを単体、または複数のノードに対して通常とは異なる
|
|
|
188 量で送信するバグも起こりうる。このような場合、大量のパケットによる多ノードへの通信集中はもち
|
|
|
189 ろん、送信したノードからのACKnowledgementが大量にネットワーク内に流れる事による、通信効率の
|
|
|
190 低下や輻輳の発生を生み出す可能性がある。この問題をデバッグする為には、
|
|
|
191 プログラムが停止してからではデバッグできない事から、
|
|
5
|
192 輻輳を発生させているプロトコルを動的に検知する必要がある。%###シスコのルーターはそうやってる###
|
|
4
|
193 やはり、この場合も通常の逐次デバッガでは検知が困難なことから、分散デバッグインターフェースを
|
|
|
194 用いてデバッグを行う事が望ましいと考える。
|
|
|
195
|
|
0
|
196
|
|
3
|
197 \subsection{スナップショットによる分散デバッグ}
|
|
5
|
198 %スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出
|
|
|
199 %分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定
|
|
|
200 %そうすれば逐次型でデバッグできる
|
|
|
201 %重要なのはスナップショット、便利
|
|
|
202 %分散デバッグアルゴリズム自体がスケールしなければいけない、一カ所にデータを集めるのはいけない
|
|
|
203
|
|
4
|
204 現在主に用いられている単体の逐次デバッガは分散環境用に作られていないことから、
|
|
|
205 分散環境でのデバッグの場合、１プロセスに対してデバッガを動かすか、
|
|
|
206 複数プロセスに対してそれぞれデバッガを動かしてデバッグを行うかの
|
|
|
207 どちらかのスタイルがとられると述べたが、これではデバッグすべきプロセスが増えるとその
|
|
|
208 手間はかなりの物になり、現実的なデバッグ手法とは言えない。
|
|
3
|
209
|
|
4
|
210 また、分散プログラム環境下ではプログラム状態の非決定性が存在するため通常のデバッグには無い
|
|
|
211 問題があることも述べた。
|
|
|
212 シーケンシャルなデバッグ手法では、通信の到着順序によっても分岐が変化してしまうことから、
|
|
|
213 デバッグ対象のエラーに対して再現性を確保するのが難しいという問題である。
|
|
|
214 通常、分散環境下でのデバッグではこれらの点をふまえて、
|
|
0
|
215
|
|
4
|
216 \begin{itemize}
|
|
|
217 \item {通信におけるプログラムの状態が決定的になるようテストする}
|
|
|
218 \item {非決定性をシミュレートする}
|
|
|
219 \item {バリア同期で通信を止めてメモリ等の状態を調べる}
|
|
|
220 \item {各ノードでスナップショットを取得し、ログを解析する}
|
|
|
221 \end{itemize}
|
|
|
222
|
|
|
223 といった方法がとられる。
|
|
|
224
|
|
|
225 今回、Federated Lindaを用いた分散プログラム開発の為のデバッグインターフェースを考えるにあたって、
|
|
|
226 上記のうちから「各ノードでスナップショットを取得し、ログを解析する」という手法が最も適している
|
|
|
227 と考える。
|
|
|
228
|
|
5
|
229 その理由は、スナップショットを用いる事で、Federated Lindaにおける各ノードの通信を止める事無く
|
|
|
230 デバッグに必要なプログラムの状態を確認できるという点と、各ノードの大域的な状態を保存する事で
|
|
|
231 先に述べた「分散アルゴリズムにおいてデバッグすべき対象」をそれぞれデバッグすることが可能となる
|
|
|
232 からである。
|
|
|
233
|
|
|
234 以下で大域的な状態とはどのような物かを説明し、どのようにスナップショットを用いたデバッグインタ
|
|
|
235 ーフェースを用いるべきかを説明する。
|
|
|
236
|
|
|
237 \subsubsection{大域的なプログラム状態とは}
|
|
6
|
238 Federated Lindaにおける大域的なプログラム状態には二つの要素があり、各ノードのメモリ状態
|
|
|
239 （あるいはそれに類するデータ構造）を持つ事を第一としている。
|
|
|
240 このメモリ状態を各スナップショットでのタイミングごとに正確に
|
|
5
|
241 取得することにより、プログラムの大域変数や局所変数を用いたバグの特定を可能とする。
|
|
|
242
|
|
|
243 例えば、
|
|
|
244 先に述べた様なデッドロックの原因となる排他ロックの要求及び保持を検出する検出器の作成を行い、
|
|
|
245 スナップショットのログからデッドロックの追跡を行う事。または、二分法を用いてバグの存在するプロ
|
|
|
246 グラムの実行ステートメントとプログラム状態を取得する事が可能となる。
|
|
|
247
|
|
|
248 また、大域的なプログラム状態の要素として第二に、スナップショットを取るタイミングで実行中の
|
|
|
249 プロセスが発行した通信に対する状態についても取得すべきと考える。スナップショット取得のタイミングで
|
|
|
250 考えられる通信の状態は４つのパターンに分類され、そのパターンとは、
|
|
|
251 \\
|
|
|
252 \begin{itembox}[l]{-}
|
|
|
253 {\large
|
|
|
254 \begin{center}
|
|
|
255 \begin{verbatim}
|
|
|
256 スナップショット取得のタイミング = T
|
|
6
|
257 通信受信先でのスナップショット取得のタイミング = T'
|
|
5
|
258 \end{verbatim}
|
|
|
259 \end{center}
|
|
|
260 }
|
|
|
261 \end{itembox}
|
|
|
262
|
|
|
263 とすると、
|
|
|
264 \begin{itembox}[l]{-}
|
|
|
265 \begin{itemize}
|
|
|
266 \item {Tの前にパケットを送信し、T'よりも早くパケットを受け取る場合}
|
|
|
267 \item {Tの前にパケットを送信し、T'よりも遅くパケットを受け取る場合}
|
|
|
268 \item {Tの後にパケットを送信し、T'よりも早くパケットを受け取る場合}
|
|
|
269 \item {Tの後にパケットを送信し、T'よりも遅くパケットを受け取る場合}
|
|
|
270 \end{itemize}
|
|
|
271 \end{itembox}
|
|
|
272
|
|
|
273 という４つのパターンである。
|
|
|
274
|
|
|
275 この、スナップショット取得のタイミングに対する通信の状態は、プロセスの再現性や、
|
|
|
276 プロセスの状態がある時点でどのように保たれているかを検知する上での同期処理に密接に関わってくる。
|
|
|
277 通信の状態を同期する処理が行えなければ、ネットワークを介し他のノードと通信を行っている分散
|
|
|
278 プログラムの大域的状態を取得する事は、プログラム状態の決定性に欠けることとなる。
|
|
|
279 よって、分散環境でのスナップショットを考えるにあたっては、上記４パターン通信状態を
|
|
|
280 どのように同期するかが重要である。
|
|
|
281
|
|
|
282 \subsubsection{スナップショットを用いた分散デバッグ手法}
|
|
|
283 %スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出
|
|
|
284 %分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定
|
|
|
285 %そうすれば逐次型でデバッグできる
|
|
|
286
|
|
|
287 ここまで、スナップショットを用いて分散デバッグを行う事と、そのための大域的プログラム状態について
|
|
|
288 説明した。ここでは、分散環境で取得したスナップショットをどのように用いてデバッグを行うべきかを
|
|
|
289 検討する。
|
|
|
290
|
|
6
|
291 \subsubsection{スナップショットのモニターツールと逐次デバッガによるデバッグ}
|
|
|
292 スナップショットを取得した場合、そのスナップショット・ログは膨大である。
|
|
|
293 よって、実際にスナップショット・ログからデバッグを行う為には様々な切り口で
|
|
|
294 情報を取捨選択できるモニターツールが必要であると考える。
|
|
|
295 図\ref{snapdeb}にスナップショットのモニタツールを用いたデバッグの様子を示す。
|
|
5
|
296
|
|
6
|
297 \begin{figure}[htbp]
|
|
|
298 \begin{center}
|
|
|
299 \includegraphics[width=12cm]{fig/pdf/snapdeb.pdf}
|
|
|
300 \caption{スナップショット・ログを用いたデバッグ}
|
|
|
301 \label{snapdeb}
|
|
|
302 \end{center}
|
|
|
303 \end{figure}
|
|
|
304
|
|
|
305 上記の図ではスナップショット・ログより、大域的プログラム状態の項で
|
|
|
306 説明したプログラムのメモリー状態とスナップショット取得のタイミングにおける通信状態を同期させる
|
|
|
307 ことによってFederated Lindaの大域的状態を取得している。
|
|
|
308 また、同期されたスナップショット・ログをモニタツールという、ユーザーが必要なデバッグ情報を取捨
|
|
|
309 選択するツールを用いる事を考える。ユーザーはモニタツールを用いて（例えば二文法によるバグ箇所の
|
|
|
310 検知などを利用）、どのプロセスから出力と入力があったタプルにバグの原因があるのかを特定するこ
|
|
|
311 とができる。そうすれば、その後のバグの修正においては逐次デバッガによるデバッグが可能となる。
|
|
|
312
|
|
|
313 \subsection{分散デバッグ機能のスケーラビリティ}
|
|
|
314 全ノードに対してデバッグプロセスを走らせてデバッグを行うような
|
|
|
315 手法は、デバッグのインターフェースにおけるスケーラビリティを考慮してはいない。
|
|
|
316
|
|
|
317 事実、システム資源の異なるノードに対してネットワークを介したリモートデバッグの手法は
|
|
|
318 数多く開発されていても、それが大規模システムを想定した分散プログラムに対してスケーラビリティを
|
|
|
319 保ったままデバッグ可能という解を得てはいない。
|
|
|
320
|
|
|
321 Federated Lindaはタプルのリレーという、より分散プログラムを意識したモデルであることから、デバッグ
|
|
|
322 インターフェースの大域的状態の取得にもスケーラビリティを持った実装を目指す。
|
|
|
323 その基本的なアイデアは、デバッグ情報を取得するインターフェースに対してもLindaプロトコルによるタプ
|
|
|
324 ルの伝搬を利用して実装するというものである。
|
|
|
325
|
|
|
326 下図\ref{FDLindaDebug}に示すように、Federated Lindaを用いたデバッグインターフェースは、デバッガ
|
|
|
327 プロセスからあるノードに対してデバッグ情報の取得を指示するオペレーションを発行し、デバッグ情報の
|
|
|
328 取得を行うデバッグプロトコルとしてタプル間を伝搬させる。
|
|
|
329 デバッガが受け取る結果はFederared Linda内のスナップショットとしての大域的状態であり、それを元に
|
|
|
330 デバッグを行う。このような仕組みをとる事で、大規模な分散プログラム環境であってもスケーラビリティ
|
|
|
331 を保ったままデバッグを行う事が可能となる。
|
|
|
332
|
|
|
333 \begin{figure}[htbp]
|
|
|
334 \begin{center}
|
|
|
335 \includegraphics[width=14cm]{fig/pdf/FDLindaDebug.pdf}
|
|
|
336 \caption{スケーラビリティを意識したデバッグインターフェース}
|
|
|
337 \label{FDLindaDebug}
|
|
|
338 \end{center}
|
|
|
339 \end{figure}
|
|
|
340
|
|
8
|
341 %\newpage
|
|
6
|
342 \section{通信状態デバッグインターフェースの実装}
|
|
|
343 ここまで、Federated Lindaを用いた分散環境環境における分散デバッグインターフェースの機能の検討
|
|
|
344 を行った。その結果、Federated Lindaで用いられるべき分散デバッグインターフェースはスナップショット
|
|
|
345 を用いて、デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケットの送信、といった
|
|
|
346 要素のデバッグを行う事が必要との結論を得た。
|
|
|
347
|
|
|
348 しかし、検討したスナップショットでのデバッグインターフェースの実装の為には、現実装の
|
|
|
349 Federated Lindaで用いられるProtocol Engineには更なる改良が必要である。なぜならば、現在のProtocol
|
|
|
350 Engineはルーティングテーブルを内部データとして保持することから、Federated Lindaの大域的状態を
|
|
|
351 取得するにはProtocol Engineまでのスナップショットが必要となるからである。
|
|
|
352 これを解消する為にはProtocol Engineの内部状態をステートレスに実装し、その挙動はやり取りするXML
|
|
|
353 に全て埋め込むという実装が求められる。
|
|
|
354
|
|
8
|
355 本論文では、前述した分散アルゴリズムにおいてデバッグすべき対象のうちから、
|
|
6
|
356 通信の集中を検知するデバッグインターフェースについて実装を行った。
|
|
|
357 このデバッグインターフェースを用いる事により、３章で提示したCompact Routingを用いるFederated Linda
|
|
13
|
358 において、格子状のメッシュ型トポロジで起こった、デバッグ困難な通信の集中を伴う状態の検知を行う事を目標とする。
|
|
8
|
359 以下にその詳細を示す。
|
|
4
|
360
|
|
3
|
361
|
|
|
362 \subsection{Java版Linda サーバーへの機能実装}
|
|
8
|
363 通信状態デバッグインターフェースとしてJava版のタプルサーバーへの機能拡張を行った。
|
|
|
364 この実装はFederated Lindaの通信を止めずに、通信のログを取りたい時に各Java版Lindaサーバーへデバッグ
|
|
|
365 タスクを投入し、デバッグタスクを切断してもFederated Lindaの通信状況は変化せず続く、というように
|
|
|
366 Federated Lindaを動かしながらのConnect,Disconnectに対応する。
|
|
|
367 図\ref{comdebug1}にその様子を示す。
|
|
|
368 \begin{figure}[htbp]
|
|
|
369 \begin{center}
|
|
|
370 \includegraphics[width=16cm]{fig/pdf/comdebug1.pdf}
|
|
|
371 \caption{デバッグタスクのConnect,Disconnect処理}
|
|
|
372 \label{comdebug1}
|
|
|
373 \end{center}
|
|
|
374 \end{figure}
|
|
|
375
|
|
|
376 Federated Lindaの通信を止める事無く通信のデバッグタスクを投入できることで、通信ログが欲しい
|
|
|
377 状況に適宜、通信デバッグタスクを投入することができる。また、Federated Linda全体の通信状態の
|
|
|
378 遷移が知りたい場合は、Federated Lindaを構成するLindaサーバーの全てに対して通信デバッグタスクを
|
|
11
|
379 投入し、Federated Linda内部のシーケンス番号やタプルID、または時系列情報をもとにその整合を行う。
|
|
8
|
380 図\ref{comdebug2}に実装したデバッグインターフェースの動作の様子を示す。
|
|
|
381 \begin{figure}[htbp]
|
|
|
382 \begin{center}
|
|
|
383 \includegraphics[width=16cm]{fig/pdf/comdebug2.pdf}
|
|
|
384 \caption{通信状態のデバッグインターフェース}
|
|
|
385 \label{comdebug2}
|
|
|
386 \end{center}
|
|
|
387 \end{figure}
|
|
|
388
|
|
|
389 \newpage
|
|
|
390 \subsection{実装の詳細}
|
|
|
391 今回、Java版タプルサーバーへの機能拡張として追加した、通信状態のデバッグインターフェースは、
|
|
|
392 以下のクラスから構成される。
|
|
|
393 \begin{figure}[htbp]
|
|
|
394 \begin{center}
|
|
|
395 \includegraphics[width=14cm]{fig/pdf/comdebugClass.pdf}
|
|
|
396 \caption{通信デバッグインターフェースのクラス図}
|
|
|
397 \label{comdebugClass}
|
|
|
398 \end{center}
|
|
|
399 \end{figure}
|
|
|
400
|
|
|
401 class ComDebugはJava版Lindaサーバーにおける通信状態のデバッグインターフェースを提供する。
|
|
|
402 通信状態のログはハッシュテーブルであるCom\_Hashtableに蓄えられ、デバッグインターフェースの
|
|
|
403 接続先を表すリンクドリストのReport\_Channellistに対して、Report()メソッドを用いてデバッグクライア
|
|
|
404 ントにLindaのタプルとして送信される。
|
|
|
405
|
|
|
406 class ComDebug\_Clientは通信状態のデバッグインターフェースにおけるクライアントプログラムであり、
|
|
|
407 その実行時にLindaサーバーのホストネームとポート番号を指定して接続する。クライアントプログラムの
|
|
17
|
408 通信ループはclass FederatedLinda.java, class PSXLinda.javaで定義されたSelectorベースのLinda APIの
|
|
8
|
409 通信ループを用いる。クライアントプログラムが受け取る通信パケットはLindaのタプルデータである。
|
|
|
410
|
|
|
411 \subsubsection{機能拡張を行ったLindaサーバーの通信ループ}
|
|
|
412 以下に、今回の通信状態デバッグインターフェース拡張を行った、Java版Lindaサーバーの通信ループ
|
|
|
413 を示す。
|
|
0
|
414 \begin{center}
|
|
|
415 \begin{itembox}[l]{ComDebug機能拡張部分}
|
|
|
416 {\footnotesize
|
|
|
417 \begin{verbatim}
|
|
11
|
418 if (debug) {
|
|
|
419 System.out.println("data from : "+key.channel());
|
|
|
420 }
|
|
|
421 if((mode == '!') || (len == 0)) {
|
|
|
422 ClosewishComDebug(key, command, reportCh_list);
|
|
|
423 }
|
|
|
424 else if(mode == PSX_CHECK) {
|
|
|
425 sendtext = Check(key, command);
|
|
|
426 }
|
|
|
427 else if(mode == PSX_IN || mode == PSX_RD){
|
|
|
428 sendtext = In_Rd(key, command, mode);
|
|
|
429 } else if (mode == PSX_WAIT_RD) {
|
|
|
430 Wait_Rd(key, command, mode);
|
|
|
431 } else if(mode == PSX_OUT) {
|
|
|
432 sendtext = Out(command, data);
|
|
|
433 } else {
|
|
|
434 System.out.println("Uncorrect buffer");
|
|
|
435 System.exit(1);
|
|
|
436 }
|
|
|
437 //COM_DEBUG
|
|
|
438 if(id > PRIVILEGED_ID_START && id < PRIVILEGED_ID_END){
|
|
|
439 ComDebug.addChannel(key, reportCh_list);
|
|
|
440 }
|
|
|
441 //DEBUG用カウンタ
|
|
|
442 String debug_rep = ComDebug.Com_inc(key, com_Loggingtable,
|
|
|
443 mode, id, seq, sendtext);
|
|
|
444 //DEBUG用レポート
|
|
|
445 ComDebug.Report(reportCh_list, command, debug_rep);
|
|
0
|
446 \end{verbatim}
|
|
|
447 }
|
|
|
448 \end{itembox}
|
|
|
449 \end{center}
|
|
13
|
450 通信ループ内において、通信状態のデバッグインターフェースを受け付けるのは、要求があった
|
|
|
451 idがPRIVILEGED(特権的な)\_IDとして確保した領域であった場合である。今回は1〜65535ま
|
|
11
|
452 でのタプルスペースIDのうちidが32769以降の場合において、その要求をデバッグインター
|
|
|
453 フェースの為の特権IDとして用いた。特権IDでの要求を検知した場合、ComDebug.addChannel
|
|
|
454 を行い、通信状態の報告を行うセッションのリストに追加を行う。
|
|
|
455 また、報告を行っていたセッションが切断された場合はコネクションのクローズ処理と共に、
|
|
8
|
456 reportCh\_remove()メソッドによって報告セッションリストから対象の削除を行う。これにより、
|
|
|
457 デバッグインターフェースの動的な接続と切断が実現される。
|
|
|
458
|
|
|
459 ComDebug.Com\_inc(),ComDebug\_Report()においては通信状態の更新と報告を行う。
|
|
11
|
460 これらのコードの追加によって、Java版Lindaサーバーへの通信状態のデバッグインターフェ
|
|
|
461 ース機能拡張を行った。
|
|
|
462
|
|
|
463 \subsubsection{ComDebug\_Clientの出力ログ}
|
|
|
464 最後に、この通信デバッグインターフェースを用いて取得したログを示す。
|
|
|
465 このデバッグインターフェースを用いて取得できるログは以下の様になっている。
|
|
|
466 \begin{center}
|
|
|
467 {\footnotesize
|
|
|
468 \begin{verbatim}
|
|
|
469 start : java -classpath FederatedLinda-Java/bin fdl.ComDebug_Client
|
|
|
470 -h ged.cr.ie.u-ryukyu.ac.jp -p 10000 &
|
|
|
471 Connected:PSXLinda: true
|
|
|
472 COM_DEBUG Connected.[ged.cr.ie.u-ryukyu.ac.jp:10000]
|
|
|
473 1203044062523 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
474 54481 i=2 id=32769 seq=3 data=none
|
|
|
475 1203044071138 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
476 54482 i=1 id=65535 seq=3224368 data=02
|
|
|
477 1203044071266 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
478 54482 i=2 id=1 seq=3224368 data=none
|
|
|
479 1203044071273 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
480 54482 i=3 id=2 seq=3201696 data=none
|
|
|
481 1203044093482 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
482 54488 o=1 id=1 seq=0 data=<graph name = "Graf">
|
|
|
483 <node label = "A" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10000">
|
|
|
484 <destination label = "B"/>
|
|
|
485 </node>
|
|
|
486 <node label = "B" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10001">
|
|
|
487 <destination label = "C"/>
|
|
|
488 <destination label = "D"/>
|
|
|
489 </node>
|
|
|
490 <node label = "C" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10002">
|
|
|
491 <destination label = "D"/>
|
|
|
492 </node>
|
|
|
493 <node label = "D" tsid = "ged.cr.ie.u-ryukyu.ac.jp:10003">
|
|
|
494 <destination label = "A"/>
|
|
|
495 </node>
|
|
|
496 </graph>
|
|
|
497
|
|
|
498 CloseInfo >133.13.57.210:10000--133.13.57.210:54488
|
|
|
499 1203044093772 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
500 54482 i=4 id=1 seq=3224368 data=none
|
|
|
501 1203044094228 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
502 54492 i=1 id=65535 seq=3269152 data=03
|
|
|
503 1203044094427 ged.cr.ie.u-ryukyu.ac.jp:10000--ged.cr.ie.u-ryukyu.ac.jp:
|
|
|
504 54492 o=1 id=2 seq=0 data=ged.cr.ie.u-ryukyu.ac.jp:10001
|
|
|
505 .....
|
|
|
506 \end{verbatim}
|
|
|
507 }
|
|
|
508 \end{center}
|
|
8
|
509
|
|
|
510 \subsection{視覚的に通信状態を確認するツールの開発}
|
|
11
|
511 Lindaサーバーへの通信状態デバッグ機能の追加と、その為のクライアントプログラムによって、
|
|
|
512 Federated Lindaの通信状態のログを取得する事ができた。しかし、取得したログはそれだけではどのよう
|
|
|
513 な通信状態の変化があったのかを直感的に知る事は難しい。よって、前述したデバッグインタ
|
|
13
|
514 ーフェースを用いて取得したログを、視覚的に確認できるツールの開発を行った。
|
|
8
|
515
|
|
12
|
516 このツールは、Federated LindaのLink Configurationに用いたOmni Graffleファイル、
|
|
|
517 同じくLink Configurationに用いたノードリスト、そしてデバッグインターフェースで取得した通信
|
|
11
|
518 状態のログ、をもとにその通信状態をモニターする為のツールである。
|
|
|
519 図\ref{comdeb}にその様子を示す。
|
|
8
|
520
|
|
|
521 \begin{figure}[htbp]
|
|
|
522 \begin{center}
|
|
|
523 \includegraphics[width=14cm]{fig/pdf/comdeb.pdf}
|
|
|
524 \caption{通信状態の表示ツール利用}
|
|
|
525 \label{comdeb}
|
|
|
526 \end{center}
|
|
|
527 \end{figure}
|
|
0
|
528
|
|
11
|
529 ツールの開発はログのパースと格納をPythonによって行い、GUI部分の表示においてはwxPythonを用いて
|
|
|
530 実装した。wxPythonとは、フリーの GUI ツールキット wxWidgets の Python バインディングであり、
|
|
|
531 Windows, MacOSX, その他 GTK ベースの UNIX システムの多くで利用可能である。
|
|
0
|
532
|
|
11
|
533 \subsubsection{バインディングとは}
|
|
|
534 プログラムの実行時間の8割9割がコードの1割2割の部分（ホットスポット）で費されるという
|
|
|
535 経験則は広く知られている。したがって、ホットスポットをCで記述して
|
|
|
536 実行効率の改善を図り、ホットスポット以外をスクリプト言語で記述するという手法が
|
|
|
537 有用である。そうすれば、実行速度と開発速度の双方を高めることができるからである。
|
|
|
538 そこで、CやC++で書かれたモジュールを各種のスクリプト言語から呼び出せるようにする機構が
|
|
|
539 必要になるが、それをスクリプト言語バインディングと呼ぶ。
|
|
|
540
|
|
|
541
|
|
|
542 \subsubsection{通信ログ・モニターツール}
|
|
|
543 今回作成したツールの構成は以下のようになっている。
|
|
|
544 \begin{center}
|
|
|
545 \begin{itembox}[l]{各Pythonスクリプト}
|
|
|
546 %{\footnotesize
|
|
|
547 \begin{verbatim}
|
|
|
548 [Omni Graffleパース担当]
|
|
|
549 ・Graffle2Arrangement.py
|
|
|
550 -- パースされたデータからラベル付けされたノードクラスを生成
|
|
|
551 ・ParseGraffle.py
|
|
|
552 -- Onmi Graffleファイルをパースする
|
|
|
553 ・PListReader.py
|
|
|
554 -- Apple plist XML 形式のデータを読み込む
|
|
|
555
|
|
|
556 [wxPythonによる表示担当]
|
|
|
557 ・run.py
|
|
|
558 -- 実行スクリプト、メイン処理ルーチンとしてVisualizer.pyを呼ぶ
|
|
|
559 ・Visualizer.py
|
|
|
560 -- 描画処理、イベントハンドラ処理を記述
|
|
|
561 ・images.py
|
|
|
562 -- エンコード済みBitmapデータ(Base64エンコード)
|
|
|
563 \end{verbatim}
|
|
|
564 %}
|
|
|
565 \end{itembox}
|
|
|
566 \end{center}
|
|
|
567
|
|
|
568 作成したツールは、通信状態のログを取得したFederated Lindaのトポロジ構成を、
|
|
|
569 Federated LindaのLink Configurationで使用したOmni Graffleファイルとノードリストから生成して表示する。
|
|
|
570 その後、表示したトポロジ図のノードと投入する通信状態のログからそれぞれのマッチングを行い、
|
|
|
571 通信状態の変化をステップ実行で確認できる。
|
|
|
572
|
|
13
|
573 ツール上に表示可能な通信ログのデータは、送信ノードのTSID, 受信ノードのTSID, In/Out/Rd/Ck の
|
|
|
574 モード情報と累積発行回数, タプルID, シーケンス番号, タプルのデータ内容, である。
|
|
11
|
575 図\ref{visual01}に通信ログ・モニタツールの動作状況を示す。
|
|
|
576 \newpage
|
|
0
|
577 \begin{figure}[htbp]
|
|
|
578 \begin{center}
|
|
11
|
579 \includegraphics[width=16cm]{fig/pdf/visual01.pdf}
|
|
0
|
580 \caption{通信量のグラフィカルな表示ツール}
|
|
|
581 \label{visual01}
|
|
|
582 \end{center}
|
|
|
583 \end{figure}
|
|
|
584
|
|
12
|
585 \section{Federated Lindaの実装を用いたデバッグインターフェースの評価}
|
|
|
586 実装した通信状態のデバッグインターフェースの評価として、3章で述べたDistance Vector型及び、
|
|
|
587 Compact Routingの実装を用いるFederated Lindaの通信状態デバッグを行う。
|
|
|
588 この評価の狙いは通信デバッグインターフェースを用いることで、従来のFederated Lindaにおける
|
|
13
|
589 printf情報などを用いたテスト駆動開発では困難であった、通信状態の確認を可能とする事である。
|
|
12
|
590 また、この評価によるバグ要因の特定も目標とする。
|
|
11
|
591
|
|
|
592 \subsection{評価条件}
|
|
12
|
593 \subsubsection{問題点}
|
|
|
594 Federated Lindaは分散アルゴリズムを用いてタプルの伝搬を行うが、先行研究にて開発した
|
|
13
|
595 Distance Vector型及び、Compact Routingの実装は共に格子状のメッシュ型トポロジ上での
|
|
|
596 ルーティングテーブルの構築に問題がある。Distance Vector型はメッシュ型トポロジ上での
|
|
12
|
597 ルーティングテーブル
|
|
|
598 の構築が、ライン型トポロジや、バイナリツリー型トポロジとの場合に比べて、
|
|
|
599 大幅に時間がかかるという問題、
|
|
13
|
600 Compact Routingの実装では格子状のメッシュ型トポロジ上でのルーティングテーブルの構築が、
|
|
12
|
601 通信の集中や、Landmark情報の更新の失敗によって、構築が行えないという問題である。
|
|
13
|
602 図\ref{meshtime}にDistance Vector型において格子状のメッシュ型トポロジでのルーティングテーブルの
|
|
12
|
603 構築時間とバイナリツリー型トポロジによる物を比較した結果を示す。
|
|
|
604
|
|
|
605 \begin{figure}[htbp]
|
|
|
606 \begin{center}
|
|
|
607 \includegraphics[width=14cm]{fig/pdf/exetime.pdf}
|
|
|
608 \caption{ノード数に対してルーティングテーブル構築にかかる時間}
|
|
|
609 \label{meshtime}
|
|
|
610 \end{center}
|
|
|
611 \end{figure}
|
|
|
612
|
|
|
613 結果から分かる様に、ルーティングテーブルの構築時間はノード数に対して2乗オーダー
|
|
|
614 的に増加する。このような結果は、たとえノード間のリンク数がバイナリツリー型トポロジに比べて、
|
|
|
615 メッシュトポロジの方が多いと考えても大きすぎると考える。また、Distance Vector型を元に実装を
|
|
|
616 行ったCompact Routingの実装も格子状のメッシュトポロジ上ではルーティングテーブルの構築に致命的な
|
|
|
617 問題がある。このような問題点は、現実装になんらかのバグが存在する為と考え、今回実装したデバッグ
|
|
|
618 インターフェースによるデバッグを行う。
|
|
|
619
|
|
|
620 \subsubsection{実験を行う Federated Lindaの構成}
|
|
|
621 ルーティングテーブルの構築は6ノードで構成される格子状のメッシュトポロジにおいて行い。
|
|
|
622 その通信状態を、実装した通信状態のデバッグインターフェースでログの取得を行った。
|
|
|
623 図\ref{meshgraffle}にFederated LindaのLink Configurationに用いたOmni graffleファイルを示す。
|
|
|
624
|
|
|
625 \begin{figure}[htbp]
|
|
|
626 \begin{center}
|
|
|
627 \includegraphics[width=14cm]{fig/pdf/clsmesh006.pdf}
|
|
|
628 \caption{Link Configurationに用いたOmni Graffleファイル}
|
|
|
629 \label{meshgraffle}
|
|
|
630 \end{center}
|
|
|
631 \end{figure}
|
|
|
632
|
|
|
633 \subsubsection{通信状態のデバッグを行う実験}
|
|
|
634 実装したデバッグインターフェースによるログ取得を行うのは以下の２実験である。
|
|
|
635 \begin{itemize}
|
|
|
636 \item {6ノードの格子状メッシュトポロジにおけるDistance Vector型のルーティングテーブル構築}
|
|
|
637 \item {6ノードの格子状メッシュトポロジにおけるCompact Routing実装のルーティングテーブル構築}
|
|
|
638 \end{itemize}
|
|
11
|
639
|
|
|
640
|
|
3
|
641
|
|
|
642 \subsection{評価}
|
|
12
|
643 評価条件に示した実験を行い、6ノードで構成される格子状のメッシュトポロジにおける
|
|
|
644 Federated Lindaのルーティングテーブル構築の通信状態ログを取得した。
|
|
3
|
645
|
|
13
|
646 これにより、通信状態ログを用いたモニターツールでのデバッグが可能となった。
|
|
12
|
647 ここで示す通信状態ログによるデバッグとは、Lindaサーバー単体、Lindaサーバー全体、タプルID、
|
|
13
|
648 シーケンス番号などを単位に通信ログをモニターツールに投入し、ステップ実行でタプルの通信を
|
|
12
|
649 確認するデバッグ方法である。
|
|
|
650 図\ref{debug1}と図\ref{debug2}にその様子を示す。
|
|
|
651
|
|
|
652 \begin{figure}[htbp]
|
|
|
653 \begin{center}
|
|
|
654 \includegraphics[width=12cm]{fig/pdf/debug1.pdf}
|
|
|
655 \caption{トポロジ及び通信イベントの表示}
|
|
|
656 \label{debug1}
|
|
|
657 \end{center}
|
|
|
658 \end{figure}
|
|
|
659
|
|
|
660 \begin{figure}[htbp]
|
|
|
661 \begin{center}
|
|
|
662 \includegraphics[width=12cm]{fig/pdf/debug2.pdf}
|
|
|
663 \caption{ステップ実行したシーケンスでの転送タプルを表示}
|
|
|
664 \label{debug2}
|
|
|
665 \end{center}
|
|
|
666 \end{figure}
|
|
|
667
|
|
|
668 \newpage
|
|
|
669 \subsubsection{バグ要因の特定}
|
|
|
670 通信ログ・モニターツールを用いてDistace Vector型、Compact Routing実装のデバッグを
|
|
13
|
671 行った所、Link Configuratin処理が正しく終了していない為に、ルーティングテーブル構築時の
|
|
12
|
672 通信量が増えているというバグを発見した。
|
|
|
673
|
|
|
674 通常、Federated Lindaにおけるルーティングテーブルの構築は、最初にLink Configurationを
|
|
|
675 示したXMLの投入をある1ノードに行い、そのノードから隣接ノードへのLink Configuratin XML
|
|
|
676 の転送とコネクトをもって全ノード間のコネクションのLink Configurationを行う。
|
|
|
677
|
|
|
678 しかし、格子状のメッシュトポロジでは、隣接ノードへの転送から次ノードへ別経路で
|
|
13
|
679 Link Configurationが到達する為、Link Configuratinを行うタプル転送が消滅せずに、
|
|
12
|
680 ルーティングテーブルの構築中でもLink Configurationが発生しているというバグである。
|
|
|
681
|
|
|
682 図\ref{bugfig}にその様子を示す。
|
|
|
683
|
|
|
684 \begin{figure}[htbp]
|
|
|
685 \begin{center}
|
|
|
686 \includegraphics[width=14cm]{fig/pdf/bug.pdf}
|
|
|
687 \caption{格子状メッシュトポロジにおけるLink Configurationのバグ}
|
|
|
688 \label{bugfig}
|
|
|
689 \end{center}
|
|
|
690 \end{figure}
|
|
|
691
|
|
|
692 ルーティングテーブルの構築時においてもLink Configurationのタプル転送が発生していたことで、
|
|
|
693 Distance Vector型での構築時間はバイナリツリー型トポロジに対して大幅に増加していたという
|
|
13
|
694 ことが、今回の通信状態デバッグインターフェースによって特定できた。また、Compact Routing実装の、
|
|
12
|
695 格子状メッシュトポロジにおけるルーティングテーブルの構築失敗もローカルネットワークの構築と
|
|
|
696 Landmark情報の更新にDistance Vector型の転送方法を用いている為に、同様に別経路からの情報更新
|
|
|
697 要求が正常終了せずに流れている為と分かった。
|
|
|
698
|
|
|
699 \subsubsection{デバッグにおけるモニターツールの有用性}
|
|
|
700 なぜこのようなバグをこれまで特定することが出来なかったのかというと、これまでのFederated Linda
|
|
|
701 による分散アルゴリズムの開発は、多数のターミナルによるテスト駆動でプログラム状態の変化を標準出力へ
|
|
|
702 表示させるという手法をとっていたからである。逐次プログラムの開発においては、標準出力へのprintf
|
|
|
703 デバッグは有効なデバッグ手法と言えるが、ノード全体の通信を止めずにテストを行わなければならない
|
|
|
704 状況が存在する分散プログラムの開発では、大量のprintf情報が全ノード分出力されるため、
|
|
|
705 printfデバッグは実用的とは言えない。
|
|
|
706
|
|
15
|
707 今回、通信状態のデバッグインターフェースと、そのログを視覚的に表示し、ステップ実行により通信の
|
|
12
|
708 確かさを確認できるモニターツールを開発したことにより、これまで困難であった通信状態のデバッグ
|
|
|
709 を可能とした。
|
|
3
|
710
|
|
|
711
|
|
|
712
|
|
12
|
713 \section{考察}
|
|
|
714 本章では分散環境(特にFederated Lindaを用いた)におけるデバッグ機能について、その実装を行う為に、
|
|
|
715 最初に二分法を用いた基本的な逐次デバッグ手法と、それではデバッグ困難な分散環境での通信状態を
|
|
|
716 紹介し、それらより分散デバッグ機能の検討を行った。分散アルゴリズムにおいてデバッグすべき対象には、
|
|
|
717 デッドロック, ライブロック, スケーラビリティ, 通信の集中, 大量のパケットの送信, 等があり、
|
|
|
718 それらをデバッグするには大域的なプログラム状態を取得する分散スナップショットが有効であることを
|
|
|
719 示した。
|
|
3
|
720
|
|
12
|
721 Java版Lindaサーバーを開発したことにより、以前のC言語による実装よりも機能拡張を容易に行う事が
|
|
|
722 可能となった。そのため、前述した分散アルゴリズムにおいてデバッグすべき対象のうち、通信の集中
|
|
13
|
723 を検知できるデバッグインターフェースとして、通信状態のログ取得デバッグインターフェースと、
|
|
|
724 そのログを視覚的に表示し、ステップ実行で通信の状態を確かめられるログ・モニターツールを開発した。
|
|
3
|
725
|
|
12
|
726 開発した通信状態のデバッグインターフェースの評価として、6ノードで構成される格子状メッシュトポロジ
|
|
13
|
727 におけるルーティングテーブルの構築を、Distance Vectorg型とCompact Routing実装のFederated Lindaで
|
|
12
|
728 行い、通信状態のデバッグインターフェースを適用した。
|
|
|
729 この結果、正常終了しなかったLink Configurationのタプル転送が別経路から送信されているというバグ
|
|
|
730 要因を特定した。
|
|
3
|
731
|
|
12
|
732 通信状態のログ・モニターツールを用いる事で、これまでprintfによるデバッグでは困難であった通信状態
|
|
|
733 の確認を非常に分かりやすく行うことができる。これは、スナップショットを用いたログデバッグであっても
|
|
13
|
734 同様で、デッドロック, ライブロック, スケーラビリティ, 通信の集中, 大量のパケットの送信,
|
|
|
735 等の効率的な
|
|
|
736 検知を行うには、なんらかのスナップショット・モニターツールの開発が必要であると考える。 |
