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

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

Kyushu University Institutional Repository

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

太田, 剛

https://doi.org/10.11501/3130974

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

権利関係：

第5章 例題

5.1 まえがき

本章では， 具体的な例に基づいて， これまでに述べてきた手法がどのように 適用されるのかを述べる. ここでは2つの題材を取り上げる. ひとつは， 哲学 者の食事問題であり， これはデッドロックを避けるために複数プロセス聞での 資源の排他制御が必要とな るものである. もうひとつは， 誤りを合む移動�70 ロトコルに関する問題であり， 文の記述を誤ったために生じるデッドロックに ついてデバッグできることを示す.

5.2 2人の哲学者の食事問題

並行プログラムの同期問題を説明するためによく用いられる例題に， 5人の 哲学者の食事問題がある

[

20

]

. 本節では， 簡単のため， これを2人に制限した 問題を取り上げる.

2人の哲学者が思考または食事をして暮らしている. これらの哲学 者たちは， 2つの椅子がある円卓を共有している. 椅子はそれぞ れ一人の哲学者に割り当てられている. 円卓の中央にはスパゲツ テイの皿があり， 2本のフォークが置かれている(凶5.1) . 哲学 者が思考しているときは， 別の哲学者とはかかわりがない. 哲学 者はときどき腹が減っ てくる. 食事をするためには， 2人で共有 している2つのフォークを取り上げねばならない. ただし， 取り

57

5.2. 2人の哲学者の食事問題 59 第5章例題

58

.，n

2

・1 r

g e

e

、n

b

ny

。

。 S

‘d o l

e

--u

h

r ny

+Lu qu

OM s

l e n

-­

c i h o σo

w

r e DA

、D RU 守t nO 44 4i 44 1 process philosopher1;

2 begin

3 while true do begin

{ _think }

send(fork2， GET);

recv(fork2， OK);

send(fork1， GET);

recv(fork1， OK);

{ _eat } { _think }

send(forkl， GET);

recv(forkl， OK);

send(fork2， GET);

recv(fork2， OK);

9 0 1 2 3 4 44 n4 nJL n4 qL nd 4・

Fb

￡U 7f au ny

凶5.1: 2人の哲学者の食事問題

上げられるのは， ー時に1つのフォークだけである. すでに他の 官学者が持っているフォークは使えな い. 腹が減った哲学者は同 時に2つのフォークを所有しているならば食事をし， フォークは 開放しな い. 食事が終わると両万のフォークを置き， 再び思考す る.

{ _eat }

25 send(fork2， PUT);

26 recv(fork2， OK);

27 s_en_d(f_or_k1_， PUT);

28 recv(forkl， OK) 29 end

30 end.

10 send(forkl， PUT);

11 recv(fork1， OK);

12 send(fork2， PUT);

13 recv(fork2， OK) 14 end

15 end.

さて， このIIIJ題に ついて， 各哲学者とフォークの娠るまいをプロセスとして

;ね((に'足現したプログラムを凶5.2に示す. なお， プログラムは第3.2節に定 義した要件を満たすPascal J�氏のI i訪で脅かれている. このプログラムを実行 すると， あるー・実.fJ例において， 8， 23， 38， 49行日を同時に実行しようと

してデッドロックに陥ることカfある.

第32節に述べた仮定にしたがって， このデッドロック状態を実行環境が検 出したとしよう. このとき， 次のようにしてデバッグ作業が進められる.

42 process fork2;

43 begin

44 while true do begin 45 { unoccupied }

46 recv(pr， GET);

47 send(pr， OK);

31 process fork1;

32 begin

33 while true do begin 34 { unoccupied }

35 recv(pr， GET);

36 send(pr， OK);

5.2.1 第一段階;誤りを含む部分プログラムの特定 ₃₇ { _occupied } ₄₈ { _occupied }

49 recv(pr， PUT);

50 send(pr， OK);

51 end 52 end.

刈5.2: 2人の官学者の食事問題のプログラム例

38 recv(pr， PUT);

39 send(pr， OK);

1. 手IJ J.H ':者は， このデッドロックが4つのプロセスすべてに関係しているこ

とを特定する1 40 end

41 end.

2. デッドロックが検出された事象からS叩lC -く82，231，382，492 >を得 る. また， 第3.3節に/1ミした}j法に従って， デッドロックの状況を空間

1利J!j呂-にこの能力があることを. 第3.2節において仮定した.

ι「戸 」古 」!;ロ;2立;2 : ↑ 町

6恥I +企-一一T ³⁶¹

J1T""-GET .t

³⁵¹

GET

461

471 t + ⁸¹

471 11} 4

PUT

391

合…J払n

49}

札.州pt h ヱ一九シ uケ

501

凶5.3: 2人の哲学者の食事問題の一実行例

図5.4:第一段階のステップ5 における実行場由.

時間以iにIFす ([文15.3 )， な お， 凶において51は5行日の文の1度目の :先行を， 52は5行uの文の2度目の実行を立I床するものとする. ま た，

見易さのため， P2からF2 へ送信されるメヅセージは灰!の右方向へ出て 左方rflJから入ってくるものとする. F2からP2へのメッセージ も同様で、

ある.

6. Stにおけるプログラムの大域的状態の正誤を判断する. St の衣す;なl味 は次のとおりであるので， これは正し い .

3. S勾町三Seを満たす， 最小の中断点前線を求める. この場合S時間はそ のま ま中断点前線と成り得るので， Se = S$ync である. そしてこれを異 常な実行場面えとする. すなわち， Se =く82，231，382，492^>.

-哲学者1はフォーク1 ， フォーク2を確保し食事を始め た.

・哲学者2はフォーク2を確保し ようとしている.

・フォーク1は使用中.

・フォーク2は使用中.

4. 正常な実行場1M Sc の初期値として， プログラムの初期状態を選ぶ. す なわち， Sc二く21，171，321，431 >.

7. したがって， St以前に問題はないことがわかる， S

c

をS

t

で置き換え

，

新たにScざStござSe なるStを 選ぶ. 今度はPl内の受信事象111を 中断点として選んだとする. これによって求まる中断点前線はSt 二く 111，211，352ぅ491 > となる(図5.5) .

5. Sr; ござふさSe なる安、当な実行場面Stを適切に選ぶ. 今， P1内の受 信事象81を中断点として選び， これ によって定まる中断点前線St =<

81，211，381，491 >を 選んだとする(凶5.4) .

8. Stにおけるプログラムの大域的状態の正誤を判断する， St の表す意味 は次のとおりであるので， これは正しい.

-哲学者1は(食事が終わって)フォーク1を置いた.

2人の哲学者の食事問題 63 5.2.

第5章例題 62

P2 171 Fl

32 1 351 361 Pl

21 GET -

�ーーー一 51

F2 43) P2

171 Fl

321 351 361 Pl

21

GET

�

5.

F2 431

7 1

6

に:ど・;:1tyg-!Jぷ�T

^S

lJ323cこ手

381 391 61

461

e石「

471

- Inl oynA0

4m5

ロ

61

E go - - • -

H・a

•

叫句3…ヲM+sv ;

: : : : : : : :

『・・・

J‘

:

u，a 戸

一8VH3 d

?11t-v ・4

ha 岨 -- i f 3 -山戸 山3

、.•....

4E-、・・・It--11・122・t

-

・J11

一 -wu同1

1 叫1-F -T一一 -圃 2

3-E-

2 叩

…8-

a l l -G4

7

eg--A'fll・-11晶IEEA'BEE--EE--114Y11』.E'w' 一8 - - l

，EFr・-22

〆

・

- p ' p F'} u l-司勘 〆H

;{ - j

::

-T一1

… l -円一;/…

;

・ ;

:

'Ev--t・1・1・・・2割-E

R

『 -G 規一

E---，、

山/

-- 圃明- M' h aF e- &- T H yr

--測-H4，E』E-Ft・-''O・B・守V'

・・ 凶 l，a日 一 日・・

川 ミ J J・-}

Mi ---t ME

-- -

-i M A

421 M 4 -- i

・4

•• ・・

381 ...

39 ti

352

I

²⁰¹

!

_-.

:" 11

^{21 1}

1

_'2ET S ^c 362 ;!::ロェキ�::・...

221 S ^t 461 7 1

47.

こオLによっ 図5.6:第一段階のステップ9における実行場面

Pl内の受信事象 131 を中断点として選んだとする.

て求まる中断点前線はあこく131，231，382，492 >となる 10. 次に，

a段階のステyプ7における実行場面 ク2を確保しようとしている.

-1q-学;(';' 2はフオ、

[詞5.5:第

(図5.7) . フォークlはツEld Eている.

フォーク2は{吏JIJql .

•

Sc とSe のfllJに存 と共通する事象を持つので， 捨てる.

このStはSe

在する受信事象としては， 他に F2内の 462，

• 11.

Pl I付の 131，62， 町内の ScをStで置き換え，

今度はF2内の受信事象491 を St以前に問題はないことがわかる.

したがって，

9.

これらを 中断点として用いたときの中断点 乃内の 211 があるが，

352，

新たにSc 三Stj Se なるStを 選ぶ.

次の組が， I司期誤 したカ王って，

と共通する事象を持つ.

前線もまたSe これによって求まる中断点前線はSt=く

Stにおけるプログラムの大域的 中断点として選んだとする.

りを含むような最小の部分フ。ログラム群として特定される.

(図5.6) . 131，211，352，491 >となる

Stの去す意味は次のとおりであるので， これは 状態のlEt渋を判断する.

く131，211，352，491 >

Sc lF.しし\

く82，231，382，492 >

Se 思索を始めようとしている.

-ヤi-学者lはフォーク2を開放し，

哲学者1が思索し哲学者2がフォーク2を確保 この部分プログラムは，

哲学者1がフォーク1を 哲学者 しようとしているという条件のもとで，

-75・λYTZ-2はフォーク2を硲保しようとしている.

その後ふたりがそれぞれフォーク2，

2がフォーク2を確保してしまい，

フォーク1が開放されるのを待っていることを 意味している.

フォークlは空いている.

フォーク2は開放されて空いた.

•

•

32 t 17.

51 GET 当. 35，

614 361

47:.� _l b』

1 0 8E - 381

4』

PUT 391

司aト

12.

凶5.7:第ー段階のステップ10における実行場面

5.2.2

第二段階:誤りを含む文の特定

えにおける各プロセスについて， 利用者の意凶とは異なる値を持つ変数が ないかどうかを調査する. この例題の場合， メッセージ受信の際にどのプロセ スから送信されてきたのかを保持する変数pr (fork1， fork2それぞれのプ

ロセスにひとつずつ)だけが対象となるが， これに誤りはない. したがって，

ScとSeの1mに， これら4 つのプロセス問でrriJ期を取るための送受信丈が抜け ていることになる.

この[ûJWJ誤りを解消するための， ひとつの具体例を挙げる. ここでは， 第 3.3.2節における考察に基づいて， 同期誤りを[叶避するためのコードをプログ

ラムのどの部分に追加すれば良いのかを考える.

Sc ベSt ベSeなるふとして， 462， 131，62，352，211の5つを中断点とした 5つの中断点前線を取ることができる. これらのうち， 462を中断点とした中 断点前線をS46， 352によるものをお5とする. さらに各プロセスについてこ れら2つの中断点前線J:の事象のうち肉果先行している事象を選択したものを

4₃₁

51 GET

通...+

351

614 -36.

4₆₁ 7 .

471 ^GET

M2181-i381 PUT-39

-‘ 1

49.

図 5.8:同期誤りをホす実行場面群

Sc'とする. すると， Sc" S46， 535， Se の組は， 関3.2における同期誤りの概念 を満たしている(図5.8). したがって， 462と352に到着しているメッセー ジを同時に受理することが このデッドロックを引き起こす原因となっている ことがわかる. これはすなわち， suspend point 462とデッドロソクを検出し た492の間， 同じく352と382の問が危険領域となっていることを意味する.

これを回避するためには， 462と352 (もしくは472と362)との聞に必ず 因果先行関係が成立するようなプログラムとすれば良い. 具体的には， Fl，

F2 が危険領域に入っているかどうかを管理させる新たなプロセス5ync を 用意し， 図5.2における46行自と35行日の直後， 49行日と38行日の直前に Syncとメッセージ交換し， 両者が同時に危険領域に入らないようにするコー

ドとすれば良い.

66 第5章例題 5.3

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

文の記述をi33ったために生じる デッドロックに関して， 本論文の手法によっ てデバッグする桜子を述べる. 題材として， 基本的な通信プロトコルとして有 名な移動窓プロトコルを用いる[35]. 図5.9と凶5.10に， 珂.想的な通信路を 似定して実現した プログラムをポす. このプログラムも第3.2節に定義した要 件を満たすPascal風の戸五百で吉:かれている.

このプログラムを実行し ， 人力として 100， 200， 300と与えた場合を考え る. このとき， 変数pの初期値をまちがえているために(34行め) ， プロセ

スsenderから 3つのデータを送り出すにもかかわらず， プロセスrecverか らは2 つのACKしか返送されな い. これが原因となって， 13行めと 36行 めにおいてデッドロックする. この実行過程を図5.11， 図5.12に示す.

5.3.1 第一段階:誤りを含む部分プログラムの特定

これを実行環境が検出したとすると2 次のようにしてデバッグ作業が進め られる.

1.手IJ川者は， このデッドロックが2つのプロセスに関係していることを特 定する 3

2. デッドロックが検出されたイベントから S�ync -く 133，364 >を得， こ れをSe の初期j仰とする. また， Sc の初期値をSc -く11，301 >とす る.

3. 第3.3節に従って， プログラムの大域的状態が正しく， かつSeに最も接 近した Scを求め， 次を得る.

Sc く131，372 > .

Se < 133) 364 > .

これを空間|時間凶でぶ現すると [�15.13のようになる.

2第3.2節において仮定した.

3利用者にこの能力があることを， 第3.2 節において仮定した.

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

const WSIZE = 3;

BUFLEN = 7;

ACK = 1;

NACK ⁼ 2;

process sender;

var window， h， t， 0， w， m: integer;

store: array [0..BUFLEN-1] of integer;

busy: array [0. .BUFLEN-1] of boolean;

begin

1: window := 0;

2: h := 0;

3: t := 0;

4: while true do begin

5: while window < WSIZE do begin 6: read(o);

7: window :; window + 1;

8: busy[h] := true;

9: store[h] := 0;

10: send(recver， h);

11 : send (recver， 0);

12: h := (h + 1) mod BUFLEN;

end

13: recv(recver， w);

14: recv(recver， m);

15: if w = ACK then 16: busy[m] := false

else

17: if window > 0 then begin 18: send(recver， m);

19: send(recver， store[m]) end

20: while not busy[t] do begin 21: window := window - 1;

22: t := (t + 1) mod BUFLEN;

end end end;

図5.9:文の記述誤りを含む移動窓プロトコル

67

process recver;

var i， 0， p， t: integer;

recved: [0. . BUFLEN-1] of boolean;

buffer: [0..BUFLEN-1] of integer;

function valid(p， i: integer): boolean;

var v: integer;

begin

23: v := p - i;

24: if 0 < v and v <= WSIZE then 25: return true;

26: v := p ^- BUFLEN - i;

27: if 0 < v and v <= WSIZE then 28: return true;

29: return false end

begin 30: t := 0;

31: while t くBUFLEN do begin 32: recved[t]:= false;

33: t := t ⁺ 1 end

34: p := 1;

35: while true do begin 36: recv(sender， i);

37: recv(sender， 0);

38: if recved[i] then begin 39: if valid(p， i) then begin 40: send(sender， ACK);

41: send(sender， i) end

else begin

42: buffer[i] := 0 43: recved[i] := true;

44: recved[(i - WSIZE ⁺ BUFLEN) mod BUFLEN] := false end

45: if recved[pJ then begin 46: write(buffer[pJ);

47: send(sender， ACK);

48: send(sender. p);

49: p := (p + 1) mod BUFLEN;

end end end;

凶5.10:文の記述誤りを合む移動窓プロトコル(つづき)

proc sender 11 window := 0;

21 h : = 0;

31 t := 0;

41 while true do begin

51 while window < WSIZE do begin (0<3)

61 read(O); (0:=100)

7 _l 8 _l 9 1 101 111 121 5 2 6 2 7 2 8 2 9 2 102 112 122 5 ₃ 6) 7 ₃ 8 ₃ 9 ₃ 10) 11) 12) 5 _• 131 141 151 161 201

window := window + 1;

busy[h] := true;

store[h] := 0;

send( recver， h);

send( recver， 0);

h := (h + 1) mod BUFLEN;

(window : = 11 (busy[O]:=true1 [store[O]:=100)

(send(recver，O)}

(send(recver，100)}

(h:=1) while window < WSIZE do begin (1<3)

read(o); (0:=200)

window := window + 1; (window:=2) busy[h] := true; (busy[1]:=true1 store[h] := 0; (store[1] :=200]

send(recver， h); (send(recver，1)}

send(recver， 0); (send(recver，200)}

h := (h + 1) mod BUFLEN; (h:=2) while window < WS工ZE do begin (2<3)

read(o); {0:=300}

window := window + 1;

busy[h] := true;

store[h] := 0;

(window:=3) (busy[2):=true) {store[2] :=300}

send(recver， h); (send(recver，2)}

send(recver， 0); (send(recver，300) h := (h + 1) mod BUFLEN; (h:=3)

while window < WSIZE do begin (3<3) recv(recver， w); {w:=ACK}

recv( recver， m);

if w = ACK then busy[m] := false

while not busy[t} do begin

{m:=l}

{ACK=ACK}

(busy[1]:=false) (not true) 42 while true do begin

55 while window < WSIZE do begin (3<3)

132 recv( recver， w); (w:=及CK)

142 152 162 202 4 ₃ 5 ₆ 13)

recv (recver， m);

if w = ACK then busy[m] := false

while not busy[t] do begin while true do begin

(m:=2) {ACK=ACK]

{busy[2]:=false}

[not true}

while window < WSIZE do begin {3<3}

recv ( recver， w);

図5.11:プロトコルの実行過程

70 第5章例題 5.3. 誤りを含む移動窓プロトコル 71

proc recver sender recver

101 361

111 37 1

102 362

112 _.31_2...

103

ン;

471Sc

113 481

131

.

363

141 37 3

132 47 2

142 482

...・H・...Se 133

t t

³⁶⁴

301 t := 0，

311 while t < BUFLEN do begin 321 331

Jl�

322 332 31) 32J 33) 31. 32.

33. 315 325 335 316 326 336 317 327 337 31&

341 351

361

371 381 42[

431 441 451 352 362 372 382 42]

43]

442 452 46]

471 481 491 35

)

3⁶

)

37) 38) 42) 43) 44) 45) 462 472 482 49]

35

.

36.

recved[t) := false;

(0<7)

[recved(O):=false) [t:=1]

[1<7}

[recved[l].=false]

[t，=2)

n ・lg e b o d N F& L .，p・

3&

HU

RM + ，、t 令Lg ・-e官A

t w h -­

recved[t] := false;

t ，= t + 1;

while t < BUFLEN do begin recved(t] := false;

[2<7)

[recved[2):=false]

[t:=3}

n l q e b o 吊UN E L ;F '・・nuau + ，、t +』一一

z

、ム e

t l

h w [3<7 }

n ・lnヨe .，

hu

; e

e S

O

S

可ム

吊u

'&

a

a eA

F副 M日4L

=

守山

-­

a

・' F‘

••

-A nU 2』

RM

唱』

t +

t

，，‘

，、，ak d t

d

e

t

e

v

=

v

c z e c e

l

e

x t

・- E

h w

[recved[3].=false) (t:=4)

[4<7 )

(recved[4]:=false) (tl=5)

(5<7 )

(recved(5):=false) [t:=6)

[6 <7)

(recved[6]，=false) [t:=7)

[7(7) t .= t + 1;

while t < BUFLEN do begin recved[t] := false;

t := t + 1;

while t < BUFLEN do begin recved[t] := false;

t := t + 1;

while t < BUFLEN do begin

p : = 1; 図 5.13:デッドロックした移動窓プロトコルの空間時間凶

while true do begin

recv(sender， i); [i:=O)

(0:=100)

(recved[O]=false) [buffer[O].=100J

5.3.2 第二段階:誤りを含む文の特定

recv(sender， 0);

if recved[i) then begin buffer[i) := 0;

recved[i) .= true; [recved[O]，-true]

recved[(i-WSIZE+BUFLEN) mod BUFLEN] := false; [recved(4).=王alse) if recved[p) then begin [recved[1]=false]

while true do begin

Se における各プロセスについて， 利用苫の意凶とは異なる値を持つ;変数f ないかどうかを調査する. この例題の場合， プロセスrecver内の変数recved [OJ

がtrueであるにもかかわらず， プロセスsender内の変数busy [OJがfalse であることに問題 がある. よって， 実行時点133， 変数busy [OJについてド

村の手法を適用する.

まず， 実行時点133， 変数busy [0]に関する潜在域フローグラフを求める.

これは図5.14のようになる. このグラフを用いて第二段階の作業を進めると き， グラフをほぼ半分に分割する発見的手法(第4.3.1節)だけを用いる基 本的なデバッグ過程をまず示す. 次に， ダイスを用いる発見的手法(第4.3.5 節)を適用した場合を示し， さらに， スライスの共通部分を刷いる発見的手 法(第4.3.4節)を適用した場合を述べ， それぞれの発見的手法の布効件を示 す.

recv(sender， i); (i.=1]

(0:=200)

(recved[l]=false) (buffer[1).=200) recv(sender， 0);

if recved[i) then begin bUffer[i] ，- 0;

recved[i] ，= true; [recved[l].=true)

recved((i WSIZE+BUFLEN) mod BUFLEN] := false; [recved[5]:=false) if recved[p) then begin [recved(1)=true}

write(buffer(p)); [buffer[l]=200}

send(sender， ACK);

send( sender， p);

p ，= (p + 1) mod BUFLEN;

while true do begin

(p=l) (p:=2]

recv(sender， i); (i:=2]

recv(sender， 0);

if recved(i] then begin buffer[i) : = ^0;

(0:=300)

(recved(2]=false) (buffer[2).=300)

recved(i) :信 true; (recved[2):=true)

recved((i-WSIZE+BUFLEN) mod BUFLEN] := false; [recved[6].=false) if recved[p] then begin (recved[2]=true)

write(buffer[p]); (buffer[2]=300) send(sender， 且CK);

send(sender， p);

p .= (p + 1) mod BUFLEN;

[p=2]

(p:=3) while true do begin

recv(sender， i);

基本的なデバッグ過程 同5.12:プロトコルの実行過程

(

^つづき

)

グラフをほぼ半分に分割しつつデバッグ作業を進めていくとき， 設定される Ctの系列Ct1， Ct2，... を図5.15に不す.

sender recver

ー一一一一.. Dcf -一一一一一ー Def

ーーーー-i> CtIDef ^{ーーー ー-i>} CtlDef

…争OmsArray ^…..þIo OmsArray

�I 5.14:実行時点133• 変数busy[O]に関する潜在域フローグラフ 図5.15:グラフをほぼ半分に分割してデバッグ作業する際のCtの系列

74 第5章例題

1. Nc 士1 1からNe⁼ 133にモる最大経路長が4 なので， 1 }から2つめ の民点 122を基準とし， この直前で分割するCnを設定する. 次に，

Ctlにおいてsenderプロセス単独の状態を評価する. このとき， Ctlに よって切断される 8本の辺について調査する. この結果， ct1は正常状 態を示しているので， これが新たなCcとなる. よって， Ncニ122とな る.

2. 1 22から133に至る経路長は2なので， 83の直前にCt2を設定する.

Ct2はCnが切断する辺以外に新たな1 本の辺を切断するので， これを 評価する. このときのsenderプロセスの状態は正常であり， Ct2が新た にCcとなる. また， Nc ⁼ 83となる.

3 . 83から133への経路長は1 なので， 133の直前にCt3を設定する. Ct3 はさらに新たに2本の辺を切断する. これを評価すると， 48}から1 41 への定義依存辺(senderプロセスにおいては変数m， recverプロセス においては変数pに関する辺)において， 本来の値Oではなく1 が生成 されていることがわかる. また， 482から 14 2への定義依存辺(sender プロセスにおいては変数IIl， recverプロセスにおいては変数pに関す る辺)において， 本米の航l ではなく2が生成されていることもわか る. したがって， Q3における状態は異常であり， これが新たなCeと なる.

4. 2本の辺に異常があるので， 安全のため， 時間j的に後に実行された文482 をNpとする. Nc ⁼ 301からNeへの経路長は5なので， 301から経 路長3 の位匠にある3 82の直前にCtを設定する. Ct4は9本の辺を新 たに切断する. この状態を評価すると， 341から出ていく3本の定義依 存辺において， 本来:0 であるべき値が1 となっていることがわかり， 異 常状態にあることがわかる. したがって， Ct4が新たなCeとなる.

5. Ct4が切断する辺の中で， これ以外に値の誤ったものは存在しない. し たがって， Neとして341が選ばれる. ところが， この頂点への人力辺 はないので， l�15.15のようにCt5を取れば卜分である. Ct5では， 新 たに切断する辺はない. これを評価すると当然ながら正常状態であるの

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

で， 誤りは341に含まれる式にあることが特定される4 実際， 34 の文 はp := 0; であるべきである.

以上のように， 基本的なデバッグ過程ではCtを5回設定し， その問に全部 で20本の辺について評価を行なう.

ダイスを用いる発見的手法を適用したデバッグ過程

前節において潜在域スライスを求める際に， 基準となった変数busy[0]と 最も関係のありそうな変数はrecved[0]であろう. 幸いSeにおいてこの変 数は正常値trueを保持しているので， 第4.3 .5節に述べたダイスを用いる発 見的手法を適用することが可能である.

364においてrecved[O]に関して求めた潜在域スライスを， 図5.16に示 す. この図において， 網かけのある頂点は図5.14 にも含まれている頂点であ る. また， 図5.1 4のスライスから図5.16のスライスに含まれる部分を取り除 いたダイスを図5.1 7 に示す.

このようにして求めたダイスを用い， デバッグ作業をすすめる際の過杭をゲ す(凶5.1 8) .

1 . Nc ⁼ 8}からNe= 133に亘る経路長は1 なので， 133の直前にCtlを 設定する. 次にCt1におけるsenderプロセス単独の状態を評価する.

このときCtlによって切断される2本の辺について調査する. この結果 48}から14 }へ向かう定義依存辺において， 本来Oであるべき航がlと なっており， また， 482から14 2へ向かう定義依存辺において1 である べき値が2となっていることがわかる. したがって， Ct1における状態 は異常であり， これが新たにCeとなる.

2. 2本の辺に異常があるので， 安全のため， 時間的に後に実行された文482 をNeとする. Nc ⁼ 301からNeへの経路長は5なので， 301から経 路長3 の位置にある3 82の直前にCtを設定する. この切断Ct2は7 本

4グラフの頂点が0ないし1になるまで刈り込む原則からすればC絡を設定して評価すべ きである. しかし， Ct4の評価において， 352と362に問題がないことがわかっているので，

そこまでする必要はない.

sender recver

sendcr recver

81

一一一一一ー Def

一一一一-i> CtlOef

……� OmsArray

一一一-- Def

---ー -i> CtlDef

………--IÞ OmsArray

[火15.16:実行時点364• 変数recved [0]に関する潜在域フローグラフ

図 5.17:図5.14と図5.16から求まるダイス

78 第5章例題

一一一一

一竺l

^der一一一一一一一一一一一 一

三竺

^{vcr一一一 Cc}

一一一一ーDef

ー一ーー ..;> CtlDef

…伊OmsArray

[J<j 5.18: ダイスを用いたデバッグ作業におけるCtの系列

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

の辺を新たに切断する. この状態を評価すると， 341から出ていく3本 の定義依存辺において， 本来Oであるべき値が 1となっていることがわ かり， 異常状態にあることがわかる. したがって， Ct2が新たなCeと なる.

3 . Ct2 が切断する辺の中で， これ以外に値の誤ったものは存在しない. し たがって， NEとして 341が選ばれる. ところが， この頂点への入力辺 はないので， 図5.18のようにCt3を取れば十分である. これを評価する と当然ながら正常状態であるので， 誤りは 341に含まれる式にあること が特定される. 実際， 34の文はp := 0; であるべきである.

ダイスを用いる発見的手法を適用する場合， 正しい値を持つ変数を適切に選 択することにより， 前節の基本的なデバッグ過程で用いたグラフよりもかなり 小さなグラフを調査するだけで良いことになる. この例では， 調査すべきグラ フの頂点数はれから21に， 辺数は46から2 6に減少している. また， これ にともなって， 調査すべき切断の数は5から3 に， 調査すべき辺の数は 21か ら10へと減少している.

スライスの共通部分を用いる発見的手法を適用したデバッグ過程

前節において， デバッグ過程の途中で、誤った値を持つ辺が複数発見されるこ とがあった. この場合， 第4.3.4節に述べた手法を適用することによって， 誤 りの存在がより高い部分グラフを特定することができる. 具体的な方法を， 凶 5.18を用いて示す.

1. Cnの評価においてI 481から141へ向かう定義依存辺では， 本来Oで あるべき値がlとなっており， また， 482 から 142へrñJかう定義依存 辺では， 1であるべき値が2 となっていることがわかる. したがって，

481において送出される変数pの値と482において送出される変数pの 値の両方に影響を与える実行時点について， まず最初に調査すべきであ る. そのような実行時点は， 図5.18において， 481と482の両頂点から さかのぼることのできる共通の頂点である. このグラフでは341が唯 局 これを満たす.

3. 341の直前にCt3を設定し， 341への人)J辺を調査する. この場合， そ のような辺は存証しないので， 341自体に問題があることがわかる.

これにより， Ctを設定する数に変化はないが， Ct2， Ct3において新たに調 査すべき辺の数は 7 から 3に減少する.

5.4

あとがき

本章では， 同期誤りを引き起こす代表的な問題として2人の哲学者の食事問 題を取りtげ， 第3章において述べた手順的デバッグ法を適用し， 同期誤りの

!県弘jがどこにあるのかを特定する例を示した. また， 文の記述誤りによって生 じるデッドロックの例として， 基本的な通信プロトコルである移動窓プロトコ ルを用い， どのようにして誤りを文レベルで特定するのかを述べた.

第一段階における"，断点の選択と， それによって構成される中断点前線の lf117:はデバッグ環境が機械的に行なうことのできる作業である. また， デッド ロック等の[íiJ}明誤りは実行環境が検出すると仮定している. したがって， 本論 文で述べた子法では， デバッグ環境から提示される中断点前線がどのような実 行状態で、あるのかを解釈し， そのJE諜を判定する作業を行なうことだけを利 川持に期待している. これはプログラム笑行状況の可視化技術を有効に用いれ ば， どのような利用者にとっても， それほど難しい作業ではないと思われる.

lûJ !tJJ日!?とりの原同となる部分プログラムを特定した後， その解決をはかる一般 的手法-については本品文の範囲を越えている. 本章では， ひとつの例として，

危険領域に入ったプロセス数を管理する新たなプロセスを導入して解決する方 法について述べた.

第三段階における切断の選択方法については， どのような場面でどの発見的 手法が適用でき， それによってどの程度の効果が得られるかについて例を通し て示した.

第6章

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

6.1

まえカずき

プログラムスライスとは， プログラムP中の実行地点ηと変数uが与えら れたとき， ηにおけるuの値に影響を及ぼす可能性のあるP"'Jの文や式の集 合のことを言う. プログラムテキストを基に， あらゆる可能な入jJに対して解 析したものを静的スライス， 特定の入力を与えたある1つの実行例に関して解 析したものを動的スライスと呼ぶ[79]. なお， 本章では静的スライスのみを扱 うので， 以下単にスライスと言えば静的スライスを意味することとする.

当初は逐次プログラムのデバッグ文援を目的として提案されたスライス技術 であったが[69)， 近年になって， テスト， 保守， プログラム環解， プログラム 合成等， 広い範囲へ応用できる技術であることが認識されてきた[79，37]. 文 献[66] は， スライス技術に関する話題を広範囲に扱ったサーベイ論文である.

Weiserは， 手続き呼び出しのないプログラムのスライスを計算するために データフロー方程式を用いた[69]. Ottenstein _& Ottensteinは， プログラム テキストを解析してプログラム依存グラフ(Program Dependence Graph， 以 下PDG と表記する)を構成することによって， スライス計算をグラフの探 索問題へと置き換えられることを示した[55]. Horw itzは， この子法を手続き 呼び出しを含むプログラムへ拡張した[36]. さらに， 再帰呼び出しを含むプロ グラムのスライスを求める手法として， Hwangは最小不動点を用いることを

81

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

[39J. M�山他は最少限必要の情報からこれが収束するまで解析を繰り返す方法 を[85] それそれ提案した. また， Bergeret ti ^& Carréは， 一度プログラムテキ ストからμ関係行列を計算することにより， スライスを線形時間で求めること ができることを示した[7]. さらに. goto文を合む任意の制御構造に適用可能 な子法をBal l ^& Horwitz[5] やAgrawal[3] が提案している. またChengは，

並行プログラムのデバッグ支援のための， 拡張したスライスを定義した[13].

以上のような， より実用的な手法を提案し各積システムへ組み込んで利用 する万向の研究とともに， プログラムスライスの怠味論に関する研究もある [10， 57， 67].

本章では構造化プログラムを対象として， 既存アルゴリズムよりもプログラ ム変更に対する適用性が高い， したがって， デバッグ環境に組み込むことに適 したアルゴリズムについて述べる[53， 78]. まず第6.2節において入力言語を 定義し， プログラム中に現れる変数間に存在する依存関係を表現した変数依存 グラフを定義する. 第6.3節では， この変数依ィ字グラフを用いた新しいスライ ス計符アルゴリズムを提案する. また， そのl時間計算量について， 新規にスラ イスを計算する場合， プログラム変更にともなうスライスの再計算の両面から 議論する. 第6.4節では， 提案したアルゴリズムの時間計算量を既存アルゴリ ズムのそれと比較し， この新手法がプログラム変更が頻繁に起き得る環境にお いて優れていることをぷす. 最後に， 第6.5節においてまとめと今後の課題に ついて述べる.

6.2

対象言語と変数依存グラフ

6.2.1 対象言語

本車で対象とする人)J d;語は， 構造化プログラミングをするために最低限必 要な梢文要素から成るPascal 風の台詩である(図6 .1 ). この言語は一般の手 続き型プログラミング言l活と比較してずいぶん簡単化されていはいるが， 基本 的な構造を全て含み， 般の手続き型プログラミング言語とrpJ等の記述能力を 持つ.

6.2. 対象言語と変数依存グラフ 83

' 空文

v := a + b 代人文

if (cond) ^then...

else... 条件文

endif

while (cond) ^do

. . . 繰り返し文

done

read _v 入力文

write _v 出力文

関数， 手続き なし

変数 スカラ型かつ大域的

図6.1:対象とする入力言語の構文

6.2.2 変数聞の依存関係

プログラムスライスの定義に際して， 既存の計算アルゴリズムの多くは2つ の「文」の聞の依存関係を定義している. すなわち， 文Aがある変数uを定 義し， vを参照している文Bにこの定義が到達する場合に， 丈Aと丈Bと の間にデータ依存(Data Dependence)関係があると言う. また， 文Aが if 文やwhil e文のような制御文であり. Aの条件式の真偽値によって文Bの実 行が行なわれるか否かが決定される場合に， 文Aと文Bとの間に制御依存 (Control Dcpendence)関係があると言う. そして， これら2つの依存関係 をたどって得られる文の集合をプログラムスライスと定義する.

これに対して， 変数値に変化が生じる時点に着目し. 2つの「変数」の間の 依存関係からプログラムスライスを定義することも可能である. すなわち， あ る代入文の左辺に記述された変数と， 右辺に出現する変数群とはデータ依存関 係を持ち， ある制御文の本体内部に出現する代入文において， 左辺に記述され た変数はその制御文の条件式に出現する変数群と制御依存関係を持っと定義す

日íj者は変数値を媒介とした文と文との問の関係に着目した定義であり， 後 者は文を媒介とした変数聞の関係に着目した定義であると言える. すなわち，

両定義はお圧いに双対関係にある. したがって， どちらの定義を用いたとして も， 計算された結果としてのプログラムスライスに違いは生じない.

これまでのプログラムスライス計算アルゴリズムの多くは， 前者の立場から 構成されていた. 本章で述べるアルゴリズムは後者の立場から構成したもので ある. なお， 後述するアルゴリズムの都合上， 2変数聞の制御依存関係を， 分 岐依存関係(if文によって定義される)と繰り返し依存関係(while文によっ て定義される)とに分けて考える.

6.2.3 変数依存グラフ

変数依存グラフ(Variable Dependence Graph， 以ドVDGと表記する)

とは， プログラムIj-lに存在する変数聞の依存関係を表す有向グラフである.

VDGの頂点は変数を， 有111J辺は2変数聞の依存関係を定義している文または 式を去す. 特殊な頂点としてTが存在し これは変数に定数を与える代入文 (例えば初則航設定のための代人文がこれにあたる) における右辺を表す.

右IÎ1J辿としては， 代人文によって生成されるデータ辺と， if 文の then節に よって作成される thcn 辺， else節によって生成される else辺， endif によっ て生成される endif辺， while文のdo節によって生成される do辺， done に よって生成される done辺の6種類がある. なお， read 文は定数を与える代 入丈と同じ扱いをする. データ辺以外の辺をまとめて制御辺と呼ぶ. プログラ ムテキストヒの文(制御文の場合には条件式)とelse， endif， doneには出現)ijr{

に昇順のJビの番号がヲAえられ 各有向辺には対応するその番号がラベル付けさ れている. ただし， then 辺， else辺， endif辺には対応する ifの番号が， do 辺には対応するdoneの番号が， done辺には対応するdoの番号がそれぞれ付 加されている. 以16.2に 例題プログラムとその変数依存グラフを示す.

Ottenstein， Horwitz，植旧らは， スライスを計算するための中間表現として PDGを用いた. Ottenstein のPDG はプログラム中に出現するオペランドと

1 sum:= 0;

2 rainy:= 0;

3 dry:= 0;

4 read(rain);

5 while rain <> 999 do

6 7

8

9 10 11 12 13 14 15 16

sum := sum + raìn;

if rain <> 0 then rainy := rainy + 1

else

dry := dry + 1

endif;

read(rain) done;

write (' sum = 勺 sum);

write('rainy = " rainy);

write('dry = " dry);

( ^a )^{例題プログラム}

Þ data cdgρ ーョー tben cdge

m・H・H・. clsccdgc

..・・...þ endif edge ---ー doedge

一一一.. doneedge

(^{b)変数依存グラフ} 図6.2:例題プログラムとその変数依存グラフ

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

オペレータを全て頂点とし， 各頂点にて表現される値の参照関係を有向辺 で表 現してい る. Horwitzや植田の用いたpnGでは， 頂点は文や条件式を表し，

有向辺は変数値の定義・参照関係を表している.

これに対し， 本章で述べるvnGは変数値の定義・参照の関係をより強く意 識したグラフであり， このこと が プログラム変更 に対する適用性を高くする とい う特徴を生む. 例えば， 文の削除， 挿入， 変更に対し， VnG上では有向 辺の削除や挿入 だけで再構成が可能であるが， pnGでは頂点の削除や追加に 伴い， データフロー解析をして有向辺の継ぎ換え操作をする必要が ある. し たがって， プログラムの変更が頻繁に生じるデバッグ環境を構成するうえで，

vnGはpnGよりも扱い易いグラフであると言える.

6.3

変数依存グラフを用いたスライス計算アルゴリズム

本節では， _VDG 1::でスライスを計算するアルゴリズムを示す. 一般に， ス ライス は プログラム中の文 t における変数集合V に関して 定義される

[

⁶⁹

]

が， Vの各要索について繰り返し スライスを行ない， 和集合を求め ること に よって同等の効果が得られる. したがって， 本節では文tにおける変数uに関 して定義されるスライス基準C^{i， v}

( )

を用いて説明する. なお， 以下では， 特

に泌乱がlJ三じない限り， 変数z に相当する頂点のことを単にzと書く.

6.3.1 スライス計算アルゴリズム

プログラム'1'の文tにおける変数uに関するスライスSlice

(

^{i， v}

)

^は図6.3の

アルゴリズム によって求められる. ただし， 変数uからuへのデータ依存関

係が文香号ηで定義されている場合， データ辺をda(u，v，η)と書く. また，

付加情報をsとしたとき， thcn辺をth(u，v，n，s)， else辺を el(包，v，n，s)，

endif辺をef(u爪 く.

凶6.3 のアルゴリズム では， 文tを開始点として文番号の小さい方向に向 かつて探索を進めていく. ステップ4

(

^a

)

によって データ依存関係を遡る. た だし， '1直前の自分(1身の値を使わずに新たな偵を計算する代入文(例えばv:=u+1) へ到達した場合に は， vに 関するそれ以上の探索を行う必要はない. ステツ

6.3. 変数依存グラフを用いたスライス計算アルゴリズム

Algorithm Slice(i， v)

inputs: VDG， a statement number i， a variable v output: a set of statement numbers S

1. S←{}，

L←descending ordered list S.t. sn(l) < i where 1 is an in-edge to匂 2. oldn←sn( fir州L)).

3. reαched←true.

4. while L -# {}八(reαchedV oldn = sn( 1)) do l←first(L)， L←rest(L) .

oldn←sn(/).

case 1 of (a) da(u，v，η) :

S←su{η} U Slice(n， u).

ifβda(v，v，n) then

間αched←fαlse.

(b) ef (包川，n，s):

ifヨel(u，v，m，s) then

S←S U Slice(m， v).

(c) el(匂九η，s):

l←first(L)， L←rest(L ).

while 1 -#th(u，v，s，s) do l←first(L)， L←rest(L) .

S←S U {s} U Slice(s，包).

。ldn←sn(1) . (d) th(包，v，n，n):

S←s U {n} U S 1 ice (n， u).

(e)血(包，v，n，s):

S←S U Slice(s， u).

(f) do(u，v，η，s) :

S←SU{η} U Slice(s，匂)U Slice(n， u).

done.

5. return S.

first (L): the first element of an ordered list L

rest(L): an ordered list which deletes the first element of L sn(l): the statement number (i.e.，η) of an edge 1

図6.3: VDGを用いたスライス計算アルゴリズム

87

then節を探索しないことを意味する. ステップ4(d)と4(f)では， if文また do文に出会った場合には， その条件節に出現する変数へ依存関係を遡ること を窓味する. さらに， ステップ4(f)では， doに出会ったときには， 条件式に 出現する変数から新たな依存関係を遡り始めること， さらにはむによるデータ 依存関係が繰り返し文の先頭に到達した場合にはその繰り返し文本体の最後の 文へスライス基準を移すことを;意味している.

6.3.2 スライス計算例

凶6.3 のアルゴリズムにしたがって， 図6.2(a )の例題プログラムにおける Slice( 16， dry)を求めてみよう.

アルゴリズムは閃6.2(b) のdry頂点から開始される. この頂点への入力 辺のうち， 16 より小さく最も近い債を持つものはrain頂点から入ってくる

“13点" をラベルに持つdone辺であるので， まずこれが選択される. これによ り， ステップ 4(e) にしたがってSlice(5， rain)が後に計算される. ステップ

4の次の繰り返しでは， “11) 7"とラベル付けされた rainからのendif辺が選 択される. ステップ4(b)にしたがって， この辺と対応するelse 辺がないかど うかがl調べられる. この場合"7，7" のラベルを持つelse辺が存在するので，

後でthen節の部分についてSlice( 9，dry)を求める必要がある. ステップ4の 次の繰り返しでは “10" のラベルが付いたdata 辺が選択される. ステップ 4(a )にしたがって10がスライス Sに加えられる. この辺の入力頂点と出力頂 点がMじdryなので，

dryに関するデータフローはさらに前へと続いている

ため， さらに探索が進められる. ステップ4の次の繰り返しでは， “9，7" のラ ベルがイ.J'いたelse辺が選択される. ステップ4(c)にしたがって， 7がSに加 えられthen節の探索をスキップする. そして， 新たにSlice(7， rain) を求め ることが必要となる. ステップ4の次の繰り返しでは "5， 13"のラベルを持 つ do辺が選択される. ステップ4(f)にしたがって， 繰り返し文の最後から再探 索が始められる(Slice( 13， rain))とともに， 繰り返し文の前の部分に関する 探索(Slice(5，

rain))

も続けられる. ステップ4の次の繰り返しでは"3"の

dryに関する繰り返しが終了した. まだ計算が済んでいない部分については，

再帰的にこのアルゴリズムを適用することで， 最終的にSlice(16， dry) の結果 を得る.

6.3.3 時間計算量に関する議論

前節で示したスライス計算アルゴリズムの時間計算量について述べる. 本章 のアルゴリズムは， プログラムテキストからVDGを構成する部分とVDGを もとにスライスを計算する部分とに分かれるので， それぞれについて議論す る. また， プログラム変更に伴うVDGの再構成に関する計算泣も議論する.

なお， 本章で用いる記号を次のように定義する.

V 変数の数

S 文の数(S⁼ Sι+ Sc) Sa 代入文の数

Sc 制御文(if丈とwhi le文 )の数

N 頂点数

E 有向辺数

また， 議論を始めるに あたって， I平均的なプログラムJの定義を次のよう に決める.

(F1) プログラム中の任意の式に現れる変数の数は， 賞言されている変数の数 V よりずっと少ない.

(F2) 制御文の入れ子構造は， プログラム全体に渡って平均している.

VDG構成の計算量

プログラムテキストからVDGを構成するための計算最は， 頂点と有向辺の 数の和に比例する. 頂点のそれぞれは変数に一対一対応しており， さらにT 頂点が1つ存在するので， 頂点の数はV+lとなる. データ依存辺の数は最 悪の場合( 全代入文の右辺に全変数が出現している )Sa X V， 制御依存辺の