# HG changeset patch # User fuchita # Date 1202941607 -32400 # Node ID c6eefabf35c02ea768d82ce9950669c2cb4c9345 # Parent 633fe343d3a73535345c593551243f3fa2698511 Chapter 5 fix diff -r 633fe343d3a7 -r c6eefabf35c0 paper/evaluation.tex --- a/paper/evaluation.tex Thu Feb 14 05:31:26 2008 +0900 +++ b/paper/evaluation.tex Thu Feb 14 07:26:47 2008 +0900 @@ -21,11 +21,11 @@ %デバッグする対象　デッドロック、ライブロック、スケーラビリティ、通信の集中、大量のパケット（ACK） %個々の部品が正しく動いていても全体として正しく動かない場合がある。二分法は無力、 %スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出 -%通信の集中は統計で見れる-> 今回はコレ -%重要なのはスナップショット、便利 %分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定 %そうすれば逐次型でデバッグできる +%重要なのはスナップショット、便利 %分散デバッグアルゴリズム自体がスケールしなければいけない、一カ所にデータを集めるのはいけない +%通信の集中は統計で見れる-> 今回はコレ %ビジュアライゼーション、意味不明なprintfを視覚的に \section{分散環境におけるデバッグ} @@ -179,7 +179,7 @@ 集中的に転送されるというバグが発生した。しかもそのようなバグは通常の逐次デバッガを用いた デバッグ手法では、パケット集中を行っている複数のノードに対して複合的なバグ原因を検証することは 困難である。やはりこのような事態をデバッグするには従来の逐次デバッグとは異なる、分散デバッグ - インターフェースを持ってデバッグを行う事が必要と考える。 + インターフェースをもってデバッグを行う事が必要と考える。 \subsubsection{大量のパケットの送信} 前述した通信の集中とは逆に、大量のパケットを単体、または複数のノードに対して通常とは異なる @@ -187,12 +187,18 @@ ろん、送信したノードからのACKnowledgementが大量にネットワーク内に流れる事による、通信効率の 低下や輻輳の発生を生み出す可能性がある。この問題をデバッグする為には、 プログラムが停止してからではデバッグできない事から、 - 輻輳を発生させているプロトコルを動的に検知する必要がある。 + 輻輳を発生させているプロトコルを動的に検知する必要がある。%###シスコのルーターはそうやってる### やはり、この場合も通常の逐次デバッガでは検知が困難なことから、分散デバッグインターフェースを 用いてデバッグを行う事が望ましいと考える。 \subsection{スナップショットによる分散デバッグ} +%スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出 +%分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定 +%そうすれば逐次型でデバッグできる +%重要なのはスナップショット、便利 +%分散デバッグアルゴリズム自体がスケールしなければいけない、一カ所にデータを集めるのはいけない + 現在主に用いられている単体の逐次デバッガは分散環境用に作られていないことから、 分散環境でのデバッグの場合、１プロセスに対してデバッガを動かすか、 複数プロセスに対してそれぞれデバッガを動かしてデバッグを行うかの @@ -218,9 +224,74 @@ 上記のうちから「各ノードでスナップショットを取得し、ログを解析する」という手法が最も適している と考える。 +その理由は、スナップショットを用いる事で、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{スナップショットを用いた分散デバッグ手法} +%スナップショットがあれば二分法が使える、量はかなり多い、デッドロックの検出も可能、循環した依存性の検出 +%分散デバッガでおかしなぶぶんを見つけて、入力タプルと出力タプルを特定 +%そうすれば逐次型でデバッグできる + +ここまで、スナップショットを用いて分散デバッグを行う事と、そのための大域的プログラム状態について +説明した。ここでは、分散環境で取得したスナップショットをどのように用いてデバッグを行うべきかを +検討する。 + + + %\subsection{分散デバッグ機能のスケーラビリティ} + + \section{通信状態のデバッグインターフェース} \subsection{Java版Linda サーバーへの機能実装} diff -r 633fe343d3a7 -r c6eefabf35c0 paper/master_paper.aux --- a/paper/master_paper.aux Thu Feb 14 05:31:26 2008 +0900 +++ b/paper/master_paper.aux Thu Feb 14 07:26:47 2008 +0900 @@ -147,21 +147,23 @@ \@writefile{toc}{\contentsline {subsubsection}{通信の集中}{55}} \@writefile{toc}{\contentsline {subsubsection}{大量のパケットの送信}{55}} \@writefile{toc}{\contentsline {subsection}{\numberline {5.2.2}スナップショットによる分散デバッグ}{56}} -\@writefile{toc}{\contentsline {section}{\numberline {5.3}通信状態のデバッグインターフェース}{57}} -\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.1}Java版Linda サーバーへの機能実装}{57}} -\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.2}視覚的に通信状態を確認するツールの開発}{57}} -\@writefile{toc}{\contentsline {section}{\numberline {5.4}Compact Rotingの実装を用いた評価}{57}} -\@writefile{toc}{\contentsline {subsection}{\numberline {5.4.1}通信量のスケーラビリティ}{57}} -\@writefile{toc}{\contentsline {subsection}{\numberline {5.4.2}評価}{57}} -\@writefile{toc}{\contentsline {section}{\numberline {5.5}考察}{57}} -\@writefile{lof}{\contentsline {figure}{\numberline {5.3}{\ignorespaces 通信量のグラフィカルな表示ツール}}{58}} -\newlabel{visual01}{{5.3}{58}} -\@writefile{toc}{\contentsline {chapter}{\numberline {第6章}結論}{59}} +\@writefile{toc}{\contentsline {subsubsection}{大域的なプログラム状態とは}{56}} +\@writefile{toc}{\contentsline {subsubsection}{スナップショットを用いた分散デバッグ手法}{57}} +\@writefile{toc}{\contentsline {section}{\numberline {5.3}通信状態のデバッグインターフェース}{58}} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.1}Java版Linda サーバーへの機能実装}{58}} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.3.2}視覚的に通信状態を確認するツールの開発}{58}} +\@writefile{toc}{\contentsline {section}{\numberline {5.4}Compact Rotingの実装を用いた評価}{58}} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.4.1}通信量のスケーラビリティ}{58}} +\@writefile{toc}{\contentsline {subsection}{\numberline {5.4.2}評価}{58}} +\@writefile{toc}{\contentsline {section}{\numberline {5.5}考察}{58}} +\@writefile{lof}{\contentsline {figure}{\numberline {5.3}{\ignorespaces 通信量のグラフィカルな表示ツール}}{59}} +\newlabel{visual01}{{5.3}{59}} +\@writefile{toc}{\contentsline {chapter}{\numberline {第6章}結論}{60}} \@writefile{lof}{\addvspace {10\p@ }} \@writefile{lot}{\addvspace {10\p@ }} -\@writefile{toc}{\contentsline {section}{\numberline {6.1}まとめ}{59}} -\@writefile{toc}{\contentsline {section}{\numberline {6.2}今後の課題}{59}} -\@writefile{toc}{\contentsline {chapter}{謝辞}{60}} +\@writefile{toc}{\contentsline {section}{\numberline {6.1}まとめ}{60}} +\@writefile{toc}{\contentsline {section}{\numberline {6.2}今後の課題}{60}} +\@writefile{toc}{\contentsline {chapter}{謝辞}{61}} \bibcite{linda}{1} \bibcite{globalid}{2} \bibcite{dinamicrouting}{3} @@ -174,5 +176,5 @@ \bibcite{overlayweaver}{10} \bibcite{tomcat}{11} \bibcite{grizzly}{12} -\@writefile{toc}{\contentsline {chapter}{参考文献}{61}} -\@writefile{toc}{\contentsline {chapter}{発表文献}{62}} +\@writefile{toc}{\contentsline {chapter}{参考文献}{62}} +\@writefile{toc}{\contentsline {chapter}{発表文献}{63}} diff -r 633fe343d3a7 -r c6eefabf35c0 paper/master_paper.lof --- a/paper/master_paper.lof Thu Feb 14 05:31:26 2008 +0900 +++ b/paper/master_paper.lof Thu Feb 14 07:26:47 2008 +0900 @@ -29,5 +29,5 @@ \addvspace {10\p@ } \contentsline {figure}{\numberline {5.1}{\ignorespaces 単体のデバッグが有効なFederated Lindaの通信}}{53} \contentsline {figure}{\numberline {5.2}{\ignorespaces 単体ではデバッグが困難なFederated Lindaの通信}}{53} -\contentsline {figure}{\numberline {5.3}{\ignorespaces 通信量のグラフィカルな表示ツール}}{58} +\contentsline {figure}{\numberline {5.3}{\ignorespaces 通信量のグラフィカルな表示ツール}}{59} \addvspace {10\p@ } diff -r 633fe343d3a7 -r c6eefabf35c0 paper/master_paper.log --- a/paper/master_paper.log Thu Feb 14 05:31:26 2008 +0900 +++ b/paper/master_paper.log Thu Feb 14 07:26:47 2008 +0900 @@ -1,4 +1,4 @@ -This is pTeX, Version 3.14159-p3.1.5 (euc) (Web2C 7.4.5) (format=platex-euc 2005.5.19) 14 FEB 2008 05:57 +This is pTeX, Version 3.14159-p3.1.5 (euc) (Web2C 7.4.5) (format=platex-euc 2005.5.19) 14 FEB 2008 07:44 **master_paper (./master_paper.tex pLaTeX2e <2005/01/04>+0 (based on LaTeX2e <2001/06/01> patch level 0) @@ -513,23 +513,25 @@ File: emblem-bitmap.eps Graphic file (type eps) [56] +File: emblem-bitmap.eps Graphic file (type eps) + [57] File: fig/pdf/visual01.pdf Graphic file (type eps) - ) (./conclusion.tex -File: emblem-bitmap.eps Graphic file (type eps) - - [57] + ) +(./conclusion.tex File: emblem-bitmap.eps Graphic file (type eps) [58] -第 6 章(59ページ) -) (./thanx.tex [59 +File: emblem-bitmap.eps Graphic file (type eps) + [59] +第 6 章(60ページ) +) (./thanx.tex [60 -]) (./bibliography.tex [60 +]) (./bibliography.tex [61 -]) (./appendix.tex [61 +]) (./appendix.tex [62 ]) No file master_paper.ind. -[62 +[63 ] (./master_paper.aux) @@ -545,4 +547,4 @@ 14 hyphenation exceptions out of 1000 33i,12n,24p,300b,631s stack positions out of 1500i,500n,5000p,200000b,5000s -Output written on master_paper.dvi (68 pages, 214760 bytes). +Output written on master_paper.dvi (69 pages, 220500 bytes). diff -r 633fe343d3a7 -r c6eefabf35c0 paper/master_paper.toc --- a/paper/master_paper.toc Thu Feb 14 05:31:26 2008 +0900 +++ b/paper/master_paper.toc Thu Feb 14 07:26:47 2008 +0900 @@ -75,16 +75,18 @@ \contentsline {subsubsection}{通信の集中}{55} \contentsline {subsubsection}{大量のパケットの送信}{55} \contentsline {subsection}{\numberline {5.2.2}スナップショットによる分散デバッグ}{56} -\contentsline {section}{\numberline {5.3}通信状態のデバッグインターフェース}{57} -\contentsline {subsection}{\numberline {5.3.1}Java版Linda サーバーへの機能実装}{57} -\contentsline {subsection}{\numberline {5.3.2}視覚的に通信状態を確認するツールの開発}{57} -\contentsline {section}{\numberline {5.4}Compact Rotingの実装を用いた評価}{57} -\contentsline {subsection}{\numberline {5.4.1}通信量のスケーラビリティ}{57} -\contentsline {subsection}{\numberline {5.4.2}評価}{57} -\contentsline {section}{\numberline {5.5}考察}{57} -\contentsline {chapter}{\numberline {第6章}結論}{59} -\contentsline {section}{\numberline {6.1}まとめ}{59} -\contentsline {section}{\numberline {6.2}今後の課題}{59} -\contentsline {chapter}{謝辞}{60} -\contentsline {chapter}{参考文献}{61} -\contentsline {chapter}{発表文献}{62} +\contentsline {subsubsection}{大域的なプログラム状態とは}{56} +\contentsline {subsubsection}{スナップショットを用いた分散デバッグ手法}{57} +\contentsline {section}{\numberline {5.3}通信状態のデバッグインターフェース}{58} +\contentsline {subsection}{\numberline {5.3.1}Java版Linda サーバーへの機能実装}{58} +\contentsline {subsection}{\numberline {5.3.2}視覚的に通信状態を確認するツールの開発}{58} +\contentsline {section}{\numberline {5.4}Compact Rotingの実装を用いた評価}{58} +\contentsline {subsection}{\numberline {5.4.1}通信量のスケーラビリティ}{58} +\contentsline {subsection}{\numberline {5.4.2}評価}{58} +\contentsline {section}{\numberline {5.5}考察}{58} +\contentsline {chapter}{\numberline {第6章}結論}{60} +\contentsline {section}{\numberline {6.1}まとめ}{60} +\contentsline {section}{\numberline {6.2}今後の課題}{60} +\contentsline {chapter}{謝辞}{61} +\contentsline {chapter}{参考文献}{62} +\contentsline {chapter}{発表文献}{63}