分散プログラムの手順的デバッグ法に関する研究

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

分散プログラムの手順的デバッグ法に関する研究

太田, 剛

https://doi.org/10.11501/3130974

出版情報：Kyushu University, 1997, 博士（情報科学）, 論文博士 バージョン：

権利関係：

Ro aωR no一O「noコqo一勺えnzwω

回一COOMBコQ『00コ〈o=ogzoa豆mooコS〈〈zzo

。宗弘襲.鍵MO司→玄HE邑侮

-《o

aωR OBV、ωnω一。

85Fω宮司司書変革

3旨

-'"

ω

ω 4注 印

。

分散プログラムの

手順的デバッグ法に関する研究

太田 剛

1997年6月

もくじ

1 序論

1.1 研究の背景と目的

1.2 従来の研究の概観

- ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ .

1 1 2 2 4 5 7 8

- ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・

1.2.1 並行プログラムにおけるデバッグの困難さ .

1.2.2 複数の逐次デバッガの統合

1.2.3 ふるまいの再現

1.2.4 複雑さの増大への対処

1.2.5 静的解析

1.2.6 手順的デバッグ法 . ^{. • . • • • • • . •} . ^{• . • • • • • • • 9}

1.3 研究の特徴 . ^{• • • • • . • • • • . . • • • • • • • • • . • • • • " 10}

1.4 論文の構成 . ^{. . . . • • • • • • • . . . . • . • . . • • • • • • . • 11}

2 手順的デバッグ法の抽象化 ¹⁵

2.1 まえがき . ^{• • . • • • • • • . • • • • • • • • . . . • • • • • . • • 15}

2.2 Shapiroの手順的デバッグ法 ^{• • • • • • • • • . . • • • • • • • • 16}

2.3 GADTの手順的デバッグ法 . . • • • • • • • • . . . • • • • • " 18 2.4 下村の手順的デバッグ法. • • • . • • • • • • • • • . . • • • • • . 21 2.5 手順的デバッグ法の抽象化 ^{• • . • • . • • • • • • • . . • • • " 24}

2.6 あとがき . ^{. • • • • • . . • • • • . . • • • • • • • • • • • • • • • 28}

3 分散プログラムの手順的デバッグ法 ²⁹

3.1 まえがき . ^{• . • . . • • • • . • • • • • • • • • . • • • • • • • " 29}

3.2 準備 ^{• • • • • • . . . • • • • . • • • • . • • • • • • • • • • • " 29}

3.2.1 分散プログラムの定義 . ^{. • • • • • • • • • • • . • • • • • 29}

11 もくじ

3.2.2 仮定 31

3.3 第一段階:誤りを合む部分プログラムの特定 . ^{• . • . • • • • • •} 33 3.3.1 定義 ^{• • • . • . • • • • • • • • • • • • • . • • • • • • • •} 33 3.3.2 同期誤りに関する考察 . . ^{• • . • • • • • • • • . • • • • •} 36 3.3.3 同期誤りを引き起こす部分プログラムの特定方法 ^{• • . •} 38 3.4 第二段階:誤りを合む文の特定 . ^{• • • . . • . • • • • • • • . • •} 40 3.4.1 定義 ^{• • • • • • • . . • • • • . . . • • • • • • • . • • . •} 40 3.4.2 誤りを含む文の特定方法 . . • • • • • • . • • • . • • • • 42 3.5 あとがき . ^{• • • • • • • . • • • . • • • • • • • • • • • . • • • . ，} 46

4 誤り特定のための発見的手法 ⁴⁷

4.1 まえがき . ^{• • • . • • • • • • • . • • • • • • • . • . • • • • • • •} 47 4.2 第一段階における発見的手法 . ^{• • • • • • • . • • • • • • • • . •} 47

4.2.1 プログラムの大域的状態異常にかかわるプロセスを特定 する発見的手法 ^{• • . • • • • • . • • • • • • • • • . • • •} 47 4.2.2 グラフをほぼ半分に分割する発見的手法 . ^{• • • . • • • •} 49 4.2.3 臥閃となる実行時点に関する発見的手法 . ^{• • • • • • • •} 49 4.2.4 表明を用いることによる自動化 . ^{• • • • • • • • • • • •} . 50 4.3 第二段階における発見的手法 . . ^{• • . • • • • • . . • • . • • • .} 50 4.3.1 グラフをほぼ半分に分割する発見的手法 . ^{• • • • • • . •} 50 4.3.2 故初のCtをScの直前に取る発見的手法 ^{• • . • • • • •} 51 4.3.3 受信位置の誤りを基にした発見的手法 ^{• • • • • • • • • •} 52 4.3.4 スライスの共通部分を用いる発見的手法 . ^{• • • . • • . •} 53 4.3.5 ダイスを用いる発見的手法 ^{• • • • • • • • • • • • • • • •} 53 4.4 あとがき . ^{• • • . • . • • • • • • • • • • • • • • • •} . ^{. • • • •} . 54

5 例題 ⁵⁷

5.1 まえがき . ^{• • • • • • • • •} . • • • • • . • . • • • • • • • • • . • 57 5.2 2人の哲学者の食事問題 . ^{• • • • • . . • • • • • • . • • • • • • •} 57 5.2.1 第a段階:誤りを合むきIS分プログラムの特定 . ^{• . • • • •} 58 5.2.2 第一段階:誤りを含む文の特定 . ^{• • • • • • •} . ^{• • • • •} 64

もくじ III

5.3 誤りを含む移動窓プロトコル 66

5.3.1 第一段階:誤りを合む部分プログラムの特定 . • • • • " 66

5.3.2 第二段階:誤りを合む文の特定 . • • . • • . . • • • . " 71

5.4 あとがき 80

6 プログラム変更を前提としたプログラムスライス計算法 81

6.1 まえがき . • • • • • • . . • • • • • • • • • • • • • • • • . • • • • 81 6.2 対象言語と変数依存グラフ . • • • • • • . • . • • • • . • . . • • 82 6.2.1 対象言語 . • • • • • . . • • . • • • • • • • • • . • • . • • 82 6.2.2 変数聞の依存関係

6.2.3 変数依存グラフ

83 84 6.3 変数依存グラフを用いたスライス計算アルゴリズム • • • • • • • 86 6.3.1 スライス計算アルゴリズム • . • • • . . • . • • • • • " 86 6.3.2 スライス計算例 • • • • • • • • • • • • • • . • . • • • • • 88 6.3.3 時間計算量に関する議論 • • • • • • • • • • . • . • • • • 89 6.4 既存アルゴリズムとの時間計算量の比較 . ^• • • • • • • • . . • • 92 6.5 あとがき . • • • • • • • • . • • • • • . • . • . • • • • • • . . . • 93

7 結論 ₉₅

謝辞 ₉₉

参考文献 101

A既存のスライス計算アルゴリズムの時間計算 111

A.1 Weiserのアルゴリズム • • • • • • • • . • • • • • • • . ^{• • • • •} 111 A.2 PDGを用いるアルゴリズム . • • • • • • . • • • . • • • • • . • • 112 A.3μ関係行列を用いるアルゴリズム . • • • . . • . • • • • • • . . • 113

B 英和対照表 ₁₁₅

さくいん 116

lV もくじ

酢見

図

2.1 Shapiroの方法 • • • . . • • • • • ^{• .} . • • . • • • • ^• • • • • • ¹⁷

2.2 GADTにおけるプログラム変換例(Pasca1言語による) • • • • ¹⁹

2.3 手続きsquare_test. . . . . . 20 2.4 sqare_rootの実行経過 . . • . . • • • . . • • • • • . • • . . • • ²¹

2.5 下村の方法における実行経過の表現. • • • . • . • • • • • . • " ²³

2.6 手順的デバッグ法 の抽象的概念 . • • ^. . • • . • • • • • • . • • . ²⁷

3.1 動作タイミングの吸収 . • • • • • . . • . • • • . • • • • • • • • • ³³

3.2 同期誤りの概念 • . . • • • • • • • • • • • • • • • . . • • • . • • ³⁷

3.3 2つの中断点前線の関係 . • • • • ^• • • • . . • • • • • . • • • . • ³⁹

3.4 第三段階で用いられるグラフの例 . • . • ^{• .} . • • • • • • • • • . ⁴³

4.1 メッセージを実際に受理した事象九と受理すべきだ、った事象 Tcとの関係• • • . . • . • • • • • • • . • • • • ^. • • • • • ^• • • • ⁵³

4.2 ダイスの概念. • • ^. . • • • • • • • . • . . • ^• • • . . . • . . • ^{• 54}

5.1 2人の哲学者の食事問題 . . . • ^. • • • • ^• . • • • • • • • • • " ⁵⁸

5.2 2人の哲学者の食事問題のプログラム例 • • . . • . • • • • • . • ⁵⁹

5.3 2人の哲学者の食事問題の一実行例 . . • • ^• • . • • • • . • • • • ⁶⁰

5.4 第一段階のステップ5における実行場面 . • • • ^. • ^. • • • • • • ⁶¹

5.5 第一段階のステップ7における実行場面 . • • • • • • . • • • • • ⁶²

5.6 第一段階のステップ9における実行場面 . • . • • • • • • • • • . ⁶³

5.7 第一段階のステップ10における実行場面 • • . • • • . • • • • • ⁶⁴

5.8 同期誤りを示す実行場面群 • • • • • . • • • • • . . . • • • • ⁶⁵

5.9 文の記述誤りを含む移動窓プロトコル • • • • • • • • . • . • • • ⁶⁷

v

Vl 図一覧

5.10文の記述誤りを合む移動窓プロトコル(つづき) • . • • • . . • • ^{6 8}

5.11プロトコルの実行過程 .• ^{. •} . . . • ^{• •} • ^• • • ^{• .} . • • • • . • ⁶⁹

5.12プロトコルの実行過程(つづき) • . . • • • • • • • • • . • • • • • ⁷⁰

5.13デッドロックした移動窓プロトコルの空間時間図 • • . • • • • • ⁷¹

5.14実行時点133， 変数busy [0]に関する潜在域フローグラフ . • • ⁷²

5.15グラフをほぼ下分に分割してデバッグ作業する際のCtの系列 • 73 5.16実行時点364， 変数recved [0]に関する潜在域フローグラフ .. 76 5.17図5.14と図5.16から求まるダイス.• • • ^{• .} • • • • • • • • " ⁷⁷

5.18ダイスを用いたデバッグ作業におけるCtの系列• • • . • • • • . ^{78 3.1} 第 -段階における定義.• ^{• • •} • • ^. • • • • . • • ^{• •} • ^. . • • • ³⁶

3.2 第て段階における定義. • • • • • • . . • • • . . • • • • • . . • • ⁴²

昨日九 表

6.1 対象とする入力言語の構文 • • • • • • • • . • ^{• .} • • ^• • . • • ^{• 83}

6.2 例題プログラムとその変数依存グラフ • . . • • • . • • • . . . • ⁸⁵

6.3 VDCを用いたスライス計算アルゴリズム • . • • • . • • • • • • ⁸⁷

6.1 スライス計算アルゴリズムにおける時間計算量の比較(文の数

をS， 変数の数をVとする) • . • • . • • • • . . • . • • • . • ⁹²

Vll

Vlll

表 酢見

第1章 序論

1.1

研究の背景と目的

近年の半導体技術の進歩は計算機ハードウェアの高速化， 軽量化をもたら し， 各人が1台のワークステーションを占有できる環境をもたらした. また，

通信技術の発展は， そのようなワークステーションを相互に高速に結び付け，

地理的に遠く離れた2地点間で様々な情報の交換を行うことを可能とする計算 機ネットワークの出現をもたらした.

このような環境では， 地理的に分散された広い範聞に機々な計算機資源‘が丹j 意されることになる. そのため， 特別な支援環境なしでは， 利用者が必要な計 算機資源の存在位置を把握することに手間取ったり， 計算機資源の利用率の不 均衡が生じたりする. そこで， このような環境下で株々な計算機資源を有効利 用するための支援環境として， 分散システムが提案され構築されてきた.

分散システムを実現するためのプログラムは分散プログラムと呼ばれる. 分 散プログラムは， 地理的に隔たった複数の計算機上のプロセス群から成る. こ れらのプロセス群が， 利用者の要求を満たすために， 必要な'情報を計算機ネッ トワークを通じて相互に交換しつつ， 同時並行的に実行される. 例えば， 資源、

を有する計算機上のサーバ・ プロセスと 利用者が利用している計算機上のク ライアント ・ プロセスとが同時に動作し 相互に情報交換をして利用者の要求 を満たすならば， これは簡単な分散プログラムである.

複数プロセスが情報を相互に交換しつつ同時並行的に動作するプログラム は， 特に資源の確保と開放が必須となる場合には， デッドロックに代表される

l

2 第1章序論

fðJ期問題を起こし得る. 逐次プログラムでは， 同 ー人力を与えることによって プログラムの動作を完全に再現することが可能であることから， デバッグ作業 は比較的容易であった. しかし7 同期問題を生じるようなプログラムは， その 性質上， 同期誤りに至る実行過程を正確に再現することが難しいこと， さらに は， 複数プロセスの状態を同時に考慮する必要があること等から， デバッグ作 業は逐次プログラムのそれと比較してはるかに困難である.

このような背景のもとに， 分散プログラムをデバッグするための手法を確立 することが， 本研究の目的である. 本論文では特に， 手順的デバッグ法(al­

gorithmic debugging)を分散プログラムに適用する方法についてまとめた.

伝統的なデバッグ手法ではプログラマが主導権を握り， デバッグ支援システ ムはプログラマからの質問に答える受動的立場にあるのに対して， 手順的デ ノ〈ツグ法はデバッグ支援システムが主導権を握り， 能動的にプログラマに質問 を繰り返すことによって次第に誤り位置を絞り込んでゆく方式である.

なお， 複数のプロセスが同時並行的に動作するプログラムには， 大きく分類 して， 並列処理.計算機上で動作する帯列プログラム， 単一CPU上で時分割方 式によって尖行される複数プロセスから成る並行プログラム， 分散システム内 の復数計算機仁で実行される分散プログラムの3種類がある. これらのプログ ラムはよく似た特性を持ち， テストやデバッグに関する共通した困難があり，

共通した研究課題がある. そこで， 本章においては， 特に断らない限り， これ らを総称して「並行プログラム」と呼ぶことにする.

1.2

従来の研究の概観

1.2.1 並行プログラムにおけるデバッグの困難さ

複数プロセスが[JJ時並行的に動作するプログラムのデバッグには， 解決すべ き次のような課題がある [⁴⁸]^.

1. 競合から生じる非決定性への対処.

2. 探針による擾乱(probe etfect)への対策.

3. 同期のとれた大域時計(global clock)の欠如.

1.2. 従来の研究の概観 3

4. 逐次型プログラムと比較して 複雑さがはるかに大きいことへの対処.

競合とは， 複数プロセスが並列に処理を進めるために， プロセス群の動作の タイミングによっては異なる結果を生じる場合があることを云う. 例えば， 2 つのプロセスから成るプログラムの一方のプロセスがあるメモリに啓き込みを 試み， 別のプロセスが同一メモリを読み出す場合， 後者のプロセスのふるまい は， 書き込みと読み出しの実行順序によって異なる. これにより， プログラム のふるまいに非決定性が生じることになる. したがって， このようなプログラ ムは， たとえ同一入力を与えて再実行したとしても同4の結果が得られるとは 限らない.

透次プログラムをデバッグする古典的方法は， 実行中のプログラムを中断し て状態を調査し， 実行を継続するか， あるいはさらに前の時点で実行を中断す るために先頭から再実行することの繰り返しによっている. このようなデバッ グ方式を繰り返しデバッグ法(cyclical debugging)と呼ぶ. この万式は， 同 一入力を与えたプログラムはそのふるまいが再現されることを前提としている が， 複数プロセスが同時並行的に動作するプログラムにおいては， FHhlJtが{呆 証されないために， この方式を適用することは困難である.

非決定性に対処するために， プログラムのふるまいを観察・記録して再現さ せようとする試みは， 逆に， 誤り発生状況の再現を困難にしてしまうことが ある. これを「探針による援活し」と呼ぶ [²⁶]. 競合を含むプログラムにおいて は， デバッグ用に追加した文の実行や表示行為が， ただでさえ厳しい競合の状 況をさらに変更してしまうことになり， 関心のあるふるまいの発生率を下げて しまうためである.

さらには， このようなプログラムにおける「大域的状態」の概念があやふや であったり， 時に全く存在しないことさえある[⁴¹]. 大域的状態を完全に定義 するためには， すべてのプロセス間で同期のとれた大域時計が必要となるが，

一般にこれは存在し得ない. したがって， 各プロセスで生じた事象(event)の 正確な順序を決定することが困難となり， プログラムのふるまいの再現が困難 なもう1 つの理由となっている.

また， これらの事象が探針による擾乱なしに観測可能であり， それぞれが正 確に順序付けできたとしても， この履歴は膨大な量となる. この大量の情報の

4 第l章序論

中からデバッグに必要な情報を効率良く取り出し， 解析するためのツールが，

プログラマにとって必要となる.

これらの術究課題に対して， これまでに様々な試みが成されてきている. そ れらの試みの概略について， 次節以降に述べる.

1.2.2 複数の逐次デバッガの統合

ここで述べる並列デバッガは 並列プログラムを構成する任意のプロセスに 接続することができる機能を従来の逐次デバッガに持たせて， これを複数のプ ロセスそれぞれに接続して利用するものである. また このようにして接続し たデバッガ群を親デバッガから制御できるようにしたものもある. これらは逐 次デ、パッガの単純な拡張ではあるが， マルチウインドウ環境が普及した現在で は， 実用的な意味を持つ. すなわち， 各ウインドウ上で各プロセス用デバッガ を起動し表示させておくことにより， フログラマは望みのプロセスに望みのコ マンドを与えて観測することが可能となる. しかしながら， この方式では， プ ロセスの数がある程度以kになるとプログラマはこれを使いこなせなくなる.

さらに， 複数のプ口セスに対して同時に命令を与えることが困難であり， 最初 のプロセスと故後のプロセスとの命令投入時間の差が探針による擾乱を引き起 こすことにもなる.

Sun Microsy stemsの dbxtool[72]， GNUの gdb[73] は， いずれもこの範障 に人るデバッガである. それぞれ UNIX上の複数プロセスにそれぞれデバッ ガを後続してデバッグを行なうが， このとき動的プロセス生成(UNIXでは forkシステムコール)には対応できない. また， プロセス群に同時に命令を与 えることができないので， 1つのプロセスを停止する命令を発行しても別のプ ロセスは実行を続け， その結果として探針による擾乱(例えば， 実際には起こ

り作ないタイムアウトが性じる等)が発生する.

Sequent Corp. の pdbxは， マスタデバッガを置き， これが他のデバッガを 制御する方式を採る[60]. ここでは「すべてのプロセスを停止せよJ Iすべて のプロセスを再開せよjという命令によって 上記の探針による擾乱を抑える ことができるが， もちろん， 命令が各プロセスに与えられる時刻が正確に同時 であるわけではないので， 完全ではない. 同様の方式としてGriffinのデバツ

1.2. 従来の研究の概観 5

ガがある. そこでは， カレントプロセス集合を定義することにより， 命令をテ えるプロセス群をプログラマが自由に定義できる[29].

このようなデバッガにおけるブレークポイントの機能に関しても， 特徴的な 研究がなされている. ブレークポイントの設定方式は， ソースプログラム上の 特定の文に到達した場合， ある条件が満たされた場合， 特定のメモリ(変数 領域)がアクセスされた場合， 例外が発生した場合等， 従来の逐次デバッガと 同様である. しかし， 停止直後の動作として， 当該プロセスだけを停止するこ と， 全プロセスを停止することのどちらも必要となる[59]. これに関連して，

メッセージ渡し(messag e pa.ssing)を通信機構として用いる並列プログラム において， 矛盾のない状態ですべてのプロセスを停止させるためのアルゴリズ ムが報告されている[49].

また， 逐次プログラムのデバッガには必要のなかった， 新たなハードウェア やOSへの要求が必要とされる[48]. それは， 任意のプロセス開通信を捕獲す る能力， 任意にメッセージを修正， 挿入， 削除する能力， タイムアウトに使用 される時計を制御する能力である.

1.2.3 ふるまいの再現

プログラム実行時の事象を記録することにより， 実行終了後にこれを調査し てプログラムのふるまいを調べることも， 動作を再現するための補助情報とし て利用することも可能となる. この目的のために記録された事象群のことを事 象履歴(eventhistory)と呼ぶ[48].

プログラム実行時に事象を記録することは， 本来の目的を達成するために行 われる動作ではないので， 当然ながら傑針による擾乱を引き起こす原肉となり 得る. そのため， 最小限の記録によって最大の情報を取り出せることが望まれ る. どのような事象を記録すべきかは 記録した事象履歴をどのように利用す るかに依存する.

1. 視覚化用一事象によってプログラムの状態が連続的に 変化していくさ まをプログラマに見せるために記録する場合は， 各事象についての最小 限の情報があるだけで良い. ある1つのプロセスにおける事象の生起順 序を記録するだけでも， プログラムのふるまいの異常を発見することに

6 第1章序論 役立つ.

2. 再現用一事象履歴を用いてプログラムの実行を再現するために記録す る場合は， 各フ。ロセスにおける事象の生起順序の他に， 別プロセスの2 つの事象聞の順序関係をも記録する必要がある. このためには， プロセ ス開通信， 共有変数アクセスに関する事象のすべてを記録すれば十分で あることは明らかであるが， LeBlanc & Mellor-Crummey はこの情報 を削減できることを示した[43]. その手法は， 再実行時にプログラムが メッセージ内容を再生成できるという事実に基づいている.

3. シミュレーション用一事象履歴を用いて任意の単一プロセスの動作環 境をシミュレートするために記録する場合は そのプロセスから観測で きるすべてのイベントに関するあらゆる情報が必要となる. 例えば， プ ロセス間通信の場合ならメッセージの送受信時刻とともにその内容が必 要である.

事象を記録する手段としては ソースプログラムに適切な文を挿入する方 法， オペレーテイング・システムのシステムサービスに予を加えておく方法，

メモリパスを直接監視する方法がある. 最後の方法を除いて， 記録すること自 体がプログラムのふるまいのタイミングを変えてしまう恐れがあるため， 探針 による援乱に注意を払う必要がある.

事象属医を1記録する場合， これらの事象は半順序によって関係付けられる.

すなわち， 事象を各プロセスごとに独立して見た場合には， そのプロセス内 で令mrur.関係を構成し， これらの全順序関係にある事象同士が， プロセス開 通信あるいは共有変数アクセスの事-象によってさらに関係付けられることに よって， 全体として判IIR序を構成する. LeBlanc & Mellor-Crummeyは， こ の事実を素直に適用した下法を用いて事象履歴を取っている[43]. また， 程と 午ぬ[12] は， 半順序関係を記録する際に生じる探針による擾乱の度合を減少 させるため， 半順序透過性(partial order transparency)の概念を導入した.

これに対して， T ravelerではプログラム中のオブジェクトごとに活動線(life line)と呼ばれる履歴の記録を取る[46]. しかし， 半順序関係を得るための一 般的手法は， 論理時間を示すベクトルを生起事象に対応付けることである[22，

30]. このベクトルはベクトル時計(vectorclock)とも呼ばれる[47].

1.2. 従来の研究の概観 7

このようにして記録した事象履歴を用いてある種の制御実行を行なうことに より， プログラムの再実行， すなわち， ふるまいの再現を行なうことが可能と なる [^17，43]. この機能を再演(replay)と呼ぶ. P}7寅機能を有するデバッガ では， 従来通りの繰り返しデバッグ法を用いたデバッグ作業が可能となる. た だし， 事象履歴の記録の際に探針による擾乱が生じているかもしれないことに 注意しておく必要がある.

また， 事象履歴を自動検査システム， 解析システム， 検証システム等に投入 してデバッグ作業を行なう試みもある. DISDEBはメモリパスを監視し， プ ログラム実行前に記述されたある種の仕様が満たされているかどうかを， 実 時間で検査する[42]. Ada用の同様のシステムHARDもある[19]. IDDで は仕様記述に時相論理を用いることにより， Iいつか・・・・・・が成り立つJと いった検査が可能となっている[31]. T SLはAdaを対象として事象履歴の仕 様に対する検証を行なう[32]. EDLはデバッガと言うよりは事象記述言語で はあるが， これらと若干異なる立場を取っている[6]. このシステムでは， 他 の手法とは逆に， 事象履歴に記録されている低位の事象から， より高伎の十111象 化された事象を定義する手法が提供され， より高位の事象によって検説得を行 なうことを目的としている.

1.2.4 複雑さの増大への対処

膨大な量の事象履歴と関連して， これらをいかにプログラマにとってわかり 易く提示するかという課題がある. 特に並列プログラムの場合には， 複数プロ セスにわたる事象群の関連をプログラマが把握することが困難であるがゆえ に， その提示方法に玉夫が必要となる.

このような目的で利用される代表的な予法に， 時間-プロセス空間(time process space)を用いる方法がある. これは， 表示画面の2次元空間の a方 を時間経過の軸に， 他方を個々のプロセスに割り当てることによって， 各プロ セスのふるまいをプログラマが直観的に把握できるようにしたものである.

Griffinのシステムは， この空間をテキストで表示し[29]， IDDはグラフィッ クスを多用している[31]. 特に IDDでは， メッセージ通信が線で明確に表示 されるため， 情報の流れを掴み易いという特徴がある. また， IDDやPPUTT[24]

8 第1章序論

では， フィルタを用いることによって， 来示すべき情報をプログラマが選択す ることが可能となっている.

時間一プロセス?問を用いる方法は， 大域時計の存在を仮定した方式である が， これを必要としない方式も提案されている. そのためには， メッセージ送 受信事象に恭づいて， 事象の発生!順序だけを考慮して並べる並行状態マップ (concurrency map)を用いる[⁶³]. 並行状態マップも時間と空間の2次元座 標を持つが， 時間軸は正確な時刻を表すものではないことに注意が必要であ る.

時間の流れを画面上の1つの軸として表現するのではなく， アニメーショ ンの形で表現する手法も研究されている. Belvedereでは， 時間の流れに沿っ て各プロセスの状態をアニメーション表示する³⁸[ ]. このとき， プログラマ は， プロセッサの状態， 通信チャネルの状態， データの状態等の視点から表示 させるようにシステムに指示することができる. この視点の考えかたをさらに 進めて， プロセスの存伝を表すアイコンの表示位置や， どの情報を表示させる のかを指示するフィルタ等を統合した「視界(vicw) Jをプログラマが定義し 利月jできるようにするぷみがVoyeurである [⁶²]^.

時[IIJ- プロセス空間jによる表ぷ， アニメーションによる店法いずれも， プロ

グラマがプログラムのふるまいを佐観的に把握することが可能となり， プロ グラムの「あやしい」部分をすみやかに絞り込むことに威力を発揮する. しか しながら， 異常状態に陥る過程を追求し， 原因を特定するためには情報が乏し く， 事象履歴をmいたプログラムの再現手法によらねばならない.

1.2.5 静的解析

探針による擾乱を避けられないのであれば ソースプログラムを静的に解析 することによって， あらかじめ誤りの原因となりそうな部分を特定し修正して おくことは十分に価値のある作業であろう. TaylorとOsterweil は， プログ ラムをフローグラフによって表現し， その各頂点(これはプログラムの文に相

当する)に対して gcn (値の生成) ，kill (値の死滅)なるラベルを付加し，

与えられた頂点において与えられた変数の値が live(死滅していない )，avail (利用可能)であるかどうかを計算するアルゴリズムを与えた [⁶⁴]^{. これによ}

1.2. 従来の研究の概観 9

り，

-初期化されていない変数の参照.

-値の設定と参照が同時に行われ得る変数.

-一度も参照されない変数.

-値が不定となることがある変数.

-スケジュールされていないプロセスの完了を待つプロセス.

-完了済みプロセスの完了を待つプロセス.

-自分自身と並列実行されるようにスケジ、ュールされるプロセス.

を静的解析によって検出できる.

プログラムテキスト上の2点が並列に実行され得るかどうかを解析するこ とも有用である. 例えば 2点が同一メモリへの書き込み操作である場合には 並列アクセス誤りを検出できることになる. これに関しては， 様々なす語での 様々なアルゴリズムが提案されており， 実際のデバッギングツールに組み込ま れているものも多い4，9， 48， 65[ ]^.

1.2.6 手順的デバッグ法

繰り返しデバッグ法に代表される伝統的デバッグ手法は， プログラマが デ バッグ環境に指示を与えで情報を予に入れ， 次にすべき作業を決定することの 繰り返しによって進められる. その意味で， プログラマ主導のデバッグ手法で ある. これに対して， 手順的デバッグ法はデバッグ環境の側が主導権を握り，

デバッグすべきプログラムに関する質問をプログラマに対して繰り返し行なつ ことによって， 誤りを含む範囲を半自動的に絞り込んで、ゆく手法である.

手順的デバッグ法に関する研究は， 論理型プログラムを対象としたShapiro の研究に始まる [⁶¹]. Shapiroのシステムは， プログラムの実行終了後に， 実 行中に利用されたProlog節の正誤についてプログラマに質問を繰り返すこと によって， 誤りを含む節を特定する. この手法を素直に拡張して手続き型言語 に適用したものがGADTである²⁵[ ]. このシステムでは， 対象プログラム中

10 第1 章序論

の大域変数をすべての'f:.続きと関数の引数に埋め込み， その大域変数への参照 を引数への参照へと変換してプログラム中の副作用を消去することによって，

Shapiroの手法を適用できるようにしたものである. しかしながら， この方法 では， 誤りを合む範聞として手続きまたは関数を特定できるだけであり， その 中のどの文が誤りであるのかまでは特定できない. これを， プログラムのスラ イス化技法 [1 ， 68 ， 69]を応用して解決する手法も提案されている[2，40，45].

特に下村は， ある文が誤りであることを特定するだけでなく， 文の記述漏れま で特定することのできる方法を提案した[82，83].

手順的デバッグ法を手続き君!!言語で書かれた並列プログラムに適用する試み は， 研究が緒についたばかりであり， 発表済みの成果はない. これは， 次の理

由によると考えられる.

1. 実行時点の定義がはっきりしないこと.

2. プログラムの再現に困難がともなうこと.

手順的デバッグ法においては， ある実行時点におけるプログラム状態の正誤を プログラマが判断しなくてはならない. したがって 「実行時点Jの定義は重 要である. 逐次プログラムにおけるプログラムの「実行時点jの定義は， 実行 の流れがlつしか存在しないことから， 明確である. しかし， 並行プログラム では実行の流れがプロセスの例数と同じだけ存在する， この場合， 各プロセス の実行時点の匹積をJIjいてプログラムの実行時点を定義することは臼然ではあ るが， プログラムの進行にともなってプロセスの個数は動的に変化し得ること から， その扱いは難しい. しかも， 各プロセスが独立に進行することが可能な ので， その数は組み令わせ論的に増大してゆく. また， プログラマが， ある実 行時点におけるプログラム状態の正誤を判断するためには， その状態を再現で

きなくてはならない. 第1.2.1節で述べた通り 並行プログラムには探針によ る援乱が発生するため， その状態再現は困難である.

1.3 研究の特徴

伝統的な繰り返しデバッグ法を用いる限り， 並列プログラムのデバッグ作業 は逐次プログラムのそれと比較してはるかに困難を伴う. そこで本研究では，

1.4. 論文の構成 11

デバッグ環境の側が主導権を握り， プログラマに質問を繰り返し行なうことに よって誤りの存在する範囲を絞り込む手順的デバッグ法を， 手続き�言1iEで告:

かれた並列プログラムに適用するノJ法について考察した. この手続き型計ü百で は， メッセージ渡しによる情報交換を行ない， 共有メモリはmいないものとす る. また， 本論文では， 簡単のため動的なプロセス生成については扱っていな いが， これに対応するような拡張は谷易である.

本論文で述べる手順的デバッグ法は， 大きく2つの段階から成る. 第一段階 では， デッドロックに代表される同期誤りを引き起こす原因となった部分プロ グラムを特定する. このとき， 前節最後に挙げた両問題に対して， Damodaran­

Kamal _& Francioniの中断点前線(suspend pointfrontier) [18]を用いること によって解決をはかった. 第二段階では， そのようにして特定した部分プログ ラムから， 誤りや記述漏れを文のレベルで特定する. この段階では， 下村の手 法[82，83] を若干拡張して用いた.

手順的デバッグ法を用いれば， プログラマはデバッグ環境の誘導に従って質 問に答えてゆくことで， 誤り部分を半自動的に特定できる. その際， デバッグ の対象となるシステムが， 時間経過にともなってどのようにふるまうかに注 意を向けるのではなく， ある2つの実行時点の問にどのような機能が達成され ていなければならないのかに注意を向けておけば良い. すなわち， 繰り返しデ バッグ法において必要であった， rどのように進行しているか(過程) Jを犯 握するのではなく， r何が達成されたか(機能) Jに注目することによって，

デバッグ作業を行なうことができる. これはある意味で， デバッグの作業プロ セスをプログラマ側からデバッグ環境側に移すことによって， プログラマの負 担を軽減したものと考えることができる.

1.4 論文の構成

本論文は， 全7章から成る.

第1章は序論であり， 研究の背景と目的， 従来の研究の概観と本研究の特徴 について述べた.

第2章では， 既存の予)眼的デバッグ法に関してまとめ これを抽象化する.

Shapiroに始まる手順的デバッグ法は様々な型のプログラミング言語に対し

12 第1章序論

て提案されており， その外見は 」見異なる. しかし， それらを抽象化してみれ ば， プログラムの実行を有向グラフとしてとらえ， 実行状態の正誤を基にして このグラフを刈り込む作業であると45・えられる. すなわち，

1. プログラムの実行を実行時点の集合としてとらえ，

2. 実行時点を半順序によって関係付けて有向グラフに表現し，

3. プログラムの状態をグラフの切断によって表現し，

4. 2つの切断によってこのグラフを

(a)切断以前の状態はすべて正しく， 誤りの存在しない部分 (b) プログラムの誤りが存在する部分

(c) 切断以降の状態はすべて誤りであり， プログラムの誤りが存在し得 ない部分

の 3つ のグラフに切り分け，

5. 4( a)と4(c)の間に新たな切断を設定し， その状態の正訟をプログラマ に問い合わせることによって4(b)の部分を絞ってゆき，

6. 最終的にOないし 1例の実行時点を特定する.

作業であると戸-える. なぜこのことが言えるのかについて， 既存の予法の概略 を述べて明らかにする.

第3市は， 本論文の絞となる章であり， 第2章において抽象化された手順 的デバ、ソグitを分散プログラムに適用するHì-去について述べる.

まず， 本論文において捉-案する手法を正雄に述べるための準備として， 対象 とするプログラミング豆諸の定義 デバッグ環境やプログラマの能力に関する 似定について述べる.

次に， 第一段階として， 同期誤りを引き起こした部分プログラム群を特定す る}j法について述べる. この段階では， 半順序関係としてLamportの肉果先 行(happened before)関係[41]を， 切断としてDamodaran-Kamal& Fran­

cioniのsuspend point frontier[ 18]を用いる. そのため， ここで用いるグラフ

1.4. 論文の構成 13

は， 空間時間凶(space-time diagram)となる. この段階での主日的は， 同期 誤りを引き起こした部分プログラムを特定することなので， 次には， このグラ フにおける同期誤りとは何であるかを定義し， その特性について述べる. 最後 に， 部分プログラムを特定するためのアルゴリズムを提示する.

さらに第二段階として， 第一段階において特定した郎分プログラムから誤り を含む文を特定する方法について述べる. 既に前段階で同期誤りが特定できて いるので， 第二段階における作業は逐次プログラムのデバッグ作業とやiJら変わ りはない. ただし， メッセージ渡しによる値の受け渡しをどのように扱うかが 残された問題である. しかしながら， 前段階において中断点前線を用いている ことによって， メッセージの送信時点と受信時点が正確に再現できるため， こ れを代入文と同様に扱うことが可能となる. したがって， 下村の手法をほぼそ のままの形で適用できる. ここでは， 半順序関係として， 変数値の設定と参照 に関する定義依存関係， 文と文との問での制御定義依存関係， 分岐方向が変化 した場合に変数値が変わり得ることを示す分岐設定漏れ依存関係， 配列の添字 式の値によっては特定の要素の値が変わり得ることを示す配列設定漏れ依存関 係の4積類を用いる. また， グラフの切断については明らかである.

第4 章では， 第 3章において， 誤りの存在範聞を効率良く絞り込むために 利用できる発見的手法をいくつか挙げる.

第3章に提示した誤りの存在範囲を絞るためのアルゴリズムは決して効本的 なものではない. 使い勝手の良い実用的なデバッグ環境を実現するにあたって は， 発見的手法を用いた効率の良い方法を検討することは重要な課題である.

そのような発見的手法を， 本章においていくつか.0í明する.

第5章では， 前章までに述べた方式の実際の動作について， 例題を用いて具 体的に述べる. 用いる例題は， 同期問題として良く知られているís人の村学 者の食事問題J [20]を簡単化したí2人の哲学者の食事問題jと， 文の記述誤 りによってデッドロックが生じるような「移動窓プロトコル (sliding window

protocol)J [35]に関するものである. 前者では， デッドロックが検出された ときに， その原因となる誤りが存在する部分プログラムをどのようにして特定 するのかについて述べ， 1つの解決手法について簡単に触れる. その際， この 方式によって危険領域を特定できることも示す. 後者では， デッドロックの原 因となる誤りを文のレベルで特定するまでの過程について述べ. 第3章に提示