並行処理プログラムのテスト充分性評価法に関する 研究

並行処理プログラムのテスト充分性評価法に関する 研究

伊東, 栄典

九州大学システム情報科学研究科情報工学専攻

https://doi.org/10.11501/3123030

出版情報：Kyushu University, 1996, 博士（情報科学）, 課程博士 バージョン：

権利関係：

評価法に関する研究

伊 東 栄 典

システム情報科学研究科情報工学専攻

九州大学

すべての工業製品はテストにより製品の品質を評価される。計算機のプログラムも例外ではな い。プログラム開発者はプログラムを作成すると、そのプログラムが正しく動作することを確 かめるためにテストを開始する。しかしながら、テストによりプログラムの正しさを証明する ことは不可能である。なぜなら、 E.¥Y. Dijkstl'aが言うように、 「テストによりプログラムの 中に誤りが存在することを示すことはできるけれども、プログラムの中に誤りが存在しない事 を示すことはできなしリのである。しかしながら、開発者は正しいプログラムに近づくために テストを繰り返す。

「フ。ログラムを作成する場合、プログラム開発費の約 50o/cがテストに費されるj といわれて いる [39，49]0 これはテスト作業の多くを人手に頼っているからである。このため、テストの 効率化やテストの品質向上がテストの研究において重要な課題となってきている。効率化とし ては、被テストプログラムの実行や、出力結果の誤り判定などの作業を計算機で支援する研究 が行なわれてきた [50

，

25

， 

38. 4i]o 

い く ら テ ス ト を 繰 り 返 し て も 、 同 種 の テ ス ト デ ー タ を 用 い た の で は 発 見 可 能 な 誤 り は 限 定 さ れ て し ま う 。 そ の た め テ ス ト 品 質 向 上 と し て は 、 テ ス ト 基 準 の 提 案 、 そ れ に よ る テ ス ト ケ ー ス や テ ス ト デ ー タ の 作 成 方 法 テ ス ト 充 分 性 評 価 方 法 な ど が 研 究 さ れ て き た [10

，

11

，

20

，

21

，

22

，

33^ぅ15

，

39

，

51

，

48

，

52]。

テストによりプログラムの正しさを証明できないため、テストをいっ終了するのかが問題と なる。テストの進捗状況を定量的に評価する方法の lつが、テスト充分性評価である。これ は、事前に定義されたテスト基準に基づ、いてフ。ログラムの構造(ソースコード)や仕様からテス トすべき事象(測定事象)を抽出し、実際に入力データ(テストデータ)を用いて行なうテスト 実施において、実行された測定事象の割合(被覆率)を用いて充分性を評価する方法である。

近年、計算機のハードウェアデバイスの低価格化、高性能化が進んでいる。また計算機の

状況により、並行処理プログラムが実際にさまざまな場面で利用されるようになってきている [2

，

4

，

46]。並行処理プログラムにおいても信頼性向上の手法としてテストは重要である。

逐次処理プログラムで用いられているテスト法をそのまま並行処理プログラムに適用するの では、並行処理プログラムの特性を充分にテストできない。しかしながら、並行処理プログラ ムに対するテスト法は充分な研究がなされているとは言い難く、またプログラム開発現場で実 用に耐え得るツールも少ない。このため並行処理プログラムに対するテスト法の研究およびテ スト支援ツールの開発が必要である。

本論文では、並行処理プログラムのためのテスト充分性評価法について述べる。並行処理プ

ログラムに対するテスト充分性評価に用いるテスト基準として順序列テスト基準(

O r d e r e c l   S e q u e l l c e  C r i t e r i a  :  OSC )

を提案する

[ 2 6 .2 7

^う

2 8

，

2 9

， 30， 31]0提案する順序列テスト基準と、

他のテスト基準との関係、順序列テスト基準の誤りに対する信頼性とについて定性的な分析を 行う。また試作したテスト充分性評価ツールについて、実験およびその結果について議論す

る。

本論文は

7

章と付録からなる。第1章では、プログラムのテスト及びテスト充分性評価につ いて述べる。第2章では、並行処理プログラムの動作モデ、ルについて述べる。第 3章では、提 案する順序列テスト基準について述べる。第4章では、順序列テスト基準についての定性的分 析を行なう。 順序列テスト基準と既存のテスト基準との関係、順序列テスト基準の誤りに対す る信頼性、を検討する。第5章では、試作したテスト充分性評価ツールについて述べる。ツー ルの概要と、実際に並行処理プログラムをツールに適用しテスト充分性を評価した結果を述べ る。第6章では、提案する順序列テスト基準と他のテスト基準との比較を行なう。また試作し たツールの機能拡張について考察する。最後に第7章でまとめと今後の課題を述べる。

まえがき ¹ 

1.1 ソフトウェアテストの位置付け 1.2 テスト充分性評価

1.

2 . 1  

被 覆 率 .

噌i

q J F

hu

1 序論

。

1.3 テスト基準

1.

3 . 1  

逐次処理プログラムのテスト基準 1.

3 . 2  

並行処理プログラムのテスト基準 •

円 ︒ ハ

hu

nk

u

2 並行処理プログラムの動作モデル 13 

2 . 1  

並行処理プログラム • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••

1 3  

2.2  実行経路および実行系列 • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 15 

2 . 3  

通信同期制約.• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••

1 7  

3  )1慎序列テスト基準

3 . 1  

定義

3 . 2  

意味 3.3 例

3 3 5 6  

2 2 2 2  

4 定性的分析 29 

4 . 1  

テスト基準聞の関係.• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • 29 

4 . 2  

信頼性評価.• • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • • ••

3 1  

4 . 2 . 1  

通信誤りに対する信頼性評価.• • • • • • • • • • • • • • • • • • • • ••

3 2  

4.2.2  4.2.3 

生存性破壊誤りに対する信頼性評価 安全性破壊誤りに対する信頼性評価

34  36 

5 テスト充分性評価支援ツールの試作 5.1 並行処理に関するシステムコール . 5.2 テスト充分性評価システムの概要 •

5.2.1  プログラム変換部 5.2.2  実行部

5.2.3  5.3  実験

5.3.1  phoneプログラム 被覆率計算部

v h d n U

OR U

ハU

1 i q J A

斗A

A

斗AR

U

? i A ι I A

吐i斗

A F lhd k u F

hdえukυRUにυ

5.3.2  結果 5.4  結果の分析

6 議論および評価

6.1  他の手法との比較

6.2  テスト充分性評価システムの機能拡張 6.3  探針の影響

6.3.1 正当性

6.3.2  実行時間の問題

6.4 テスト充分性評価システムの応用.

6.5  測定事象数

q u q ο F hUウi円iゥ

i n u n u 氏Uハb氏U

ハ む ハ

O氏Uウi﹃i

7 結論

7.1  成 果

7.2 今後の課題.

同i司i

Q d

円t司iゥi

付録 A プログラム1.哲学者2人の食事問題 91 

付録 B探針プログラム probe.c 95 

4 . 1  

安全性破壊誤りに対する順序列テスト基準の信頼性

4 3   5 . 1   p h o n e

のソースコードに含まれる通信同期文

5 7  

5 . 2  

実行された通信同期文

5 8  

5 . 3  

実行された順序対 ‑ ・

5 8  

5 . 4  

¹⁾頂序対の分析

5 9  

5 . 5   p h o n e

プログラム内の順序対 .

6 1   6 . 1  

プログラム実行時間の比較 ‑ ・ ・ ・ ・ ・ ・

6 8  

V 

l.1 ソフトウェアのライフサイクノレ(¥，'モデル)("Software Engineering Standards" 

より。) 2 

l.2 非決定的な実行を行う並行処理プログラムの例 8 

2.1 並行処理プログラムの例 21 

3.1  並行処理に関連のある文に注目した実行系列の例 24  3.2  プロセスの動的生成の例 ‑ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ 25  3.3  「哲学者2人の食事問題」のフローグラフ 27 

4.1  テスト基準聞の包含関係 31 

4.2 プロセス聞の通信 32 

4.3  際どい領域の例 38 

4.4  際どい領域の例2 39 

4.5 際どい領域を正しく認識していない例 41 

5.1 ストリーム型ソケットの通信手順 47 

5.2  データグラム型ソケットの通信手1)慎. .  47  5.3  テスト充分性評価システムの概要. 49  5.4  プログラムの変換(探針の挿入)• ‑ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ ・ . 50  5.5  探針を挿入したソースコード 51  5.6  モ ニ タ の 動 作 .• 52  5.7  Phoneプログラム(同一計算機上) 55 

Vll 

6.1  実行履歴をファイノレに記述 ^良)

Q d

つ釘 円︑ U F U FO

円

︒ ヴ

i司i門i

5.8  phoneプログラムに含まれる通信同期文(第1フィールド:関数名?第2フィー

ルド:行番号?第3フィールド:ソケット名) • • • • • • • • • • • • • • • • • • 56 

6.2  メモリに実行を記録 . 6.3  生産者消費者問題 6.4  事象グラフの例

6.5  実行不可能な実行系列の関係

序論

ソフトウェアエンジニアリングという言葉は

NATO

の科学委員会の中に設けられた COlnputer ScIence Study Groupにより 1968年に作られた。ソフトウェアの開発から保守に至るまで の活動や生産物を より 工学的 に 体 系 化 す る と い う 目 的 を 象 徴 化 す る た め の 言 葉 で あ る [25. 

4 7 ] 0  

ソフトウェアに対する要求(ニーズ)が発生してから、そのソフトウェアが形を成し、使用さ れ、廃棄されるまでの過程を、ソフトウェアのライフサイクルと言う。ソフトウェアの歴史の 初期においては、コード・アンド・フィックス (code‑anιfix)(コーデ、イングして修正)という 工程でソフトウェアは開発されていた。これはコーディングしてから要求を確かめて修正する というものである。この方法では修正が多いとプログラムの構造が乱れて修正が難しくなる。

またソフトウェアへの要求をよく確認しないでいきなり開発してしまうので、テストや修正の ことが考慮されていなし、。ソフトウェアの規模が小さい場合はコード・アンド・フィックスで

も良かった。しかしながら、ソフトウェアの規模が大きくなると、ソフトウェアに対する要求 定義を明示的にしていないため開発が進んでから仕様が変更される、修正の際の費用が大きく なる、などの問題がでてきた。そこでソフトウェアの開発段階を明示したライフサイクルが提 案されてきた。

現在まで、に幾つかのソフトウェアのライフサイクルが考案されている。最も一般的に用いら れてきたのはウォーターフォールモデルである。これはソフトウェアの開発を、要求定義、設 計、コーディング、テスト、デバッグ、保守、の各段階に分けて詳細化する開発方法である。

工程の順位を水の流れに例えて上流工程、下流工程とも呼ぶ。しかしながら、ワオーター フォールモデルでは下流工程から上流工程へのフィードパックが考慮されていないため、下流

工程で大きな誤りが発見されると上流に戻って作業を行なわなければならない。そこで現在で は要求定義や設計などの上流工程においてテストやデ、バッグなどの下流工程を考慮するライフ サイクルが考案されている。図l.1は Vモデルと呼ばれるソフトウェアのライフサイクルモデ

ルで、ある

[ 3 8 ]

。いずれのライフサイクノレにおいてもソフトウェアの信頼性向上の手法としてテ ストが組込まれている。

SVVP : Software Verlflcatlon and  Valldatlon Plan 

Product 

一 一. . . .  

Ac川

SVVP/AT 

SVVP/ST 

SVVPIIT 

図l.

1 :

ソフトウェアのライフサイクノレ(¥Tモデノレ)

( S o f t w a r e  E n g i n e e r i n g  S t a n d a r d s "

よ り。)

1 . 1   ソフトウェアテストの位置付け

「ソフトウェアを開発する場合、ソフトウェア開発費の約 50%が テ ス ト に 費 さ れ るJ [39，49]といわれている。テストの費用を抑えソフトウェア開発全体の費用を抑えるためにテ ストの研究が進められてきた。また同時にソフトウェアの品質を向上するために、テスト技法 の確立やテストツールの開発、ソフトウェアの正当性の証明法の研究などが現在までに行われ

てきた [10，11，20，21

，

22，25，33ぅ15，39，47，51，48，52]。

構造化プログラミングの提唱者である E，，¥

y 

，Dijkstraが明言したように、 「テストによって 誤りの存在を示すことはできるが、プログラムの正しさを証明することは不可能である。 Jな ぜならテストにおいて、プログラムの正当性はテストを実施した際の入力データおよび実行系 列に対してのみ証明されるからである。つまり信頼できるテスト基準は、すべての入力データ

を選択する「徹底テスト (exhausti，で何叶)J しかない [43，52]。一般にプログラムの考えうる 入力データの数は膨大なものになるため、すべてを試みることは不可能である。そのため、テ ストの目的を次のように表すことができる。

‑プログラムの誤りの存在を示す。

‑誤りの存在を示さないまでも、プログラムの正しさに対する確信を増す。

限られた費用と時間の中で、より高い品質保証をソフトウェアに与えるために、プログラム の機能に基づいた機能テストと構造に基づいた構造テストとの2つの技法が用いられてきた [25

，

22、39

，

49]0 

(i)，機能テスト

機能テストはブラックボックステスト、または仕様テストとも呼ばれる。プログラム をブラックボックスと考え、プログラムを外から見た機能に基づいてテストを行う。機 能テストの目標は仕様で定義された入力条件の組合せを可能な限り尽すことである。し かしながら組合せの数は膨大なものになるため、現実には組合せの一部をテストデータ として用いることになる。同値分割法、限界分析法、原因・結果グラフ法 [15]などの方 法がある [40

，

^49]0 

(  i i )

，構造テスト

3 

構造テストはホワイトボックステストとも呼ばれる。ソースコードを解析しプログラ ム内部の構造を明らかにして、テストを行う方法である。

近年のハードウェアデバイスの発達は計算機の低価格化および高性能化を進めた。デバイス の低価格化はマルチフ。ロセッサシステムの普及を、計算機の低価格化および高性能化は計算機 ネットワークの普及を進めている。このような普及に伴い様々な場面で、並行処理フ。ログラムが 実際に用いられるようになってきている [4，44、i‑6]。逐次フ。ログラムの開発におけるテストと 同様に、並行処理プログラムの開発においても信頼性向上の手法としてテストは重要である。

逐次処理、並行処理プログラムに関わらず、また機能テスト、構造テストに関わらず、 一般 にプログラムのテストは以下の手順で行われる。

(1) .テストケースの作成

プログラムの仕様や構造に基づいて、被テストプログラムの入力に関する条件(入力条 件)と、その条件に対し、被テストプログラムが正しい時の出力 (期待結果)をテスト ケースとして作成する。

( 2 )

テストデータの選定

テストケースの条件を満す、被テストプログラムの入力データ (テストデータ)を選定す る。

( 3). テストの実施

テストデータを用いて被テストプログラムを実行する。

(  4 ) .

実行結果の判定

テストデータを用いて実行した被テストプログラムの出力結果を期待結果と比較する。

( 5 

).テスト評価

テストを終了するかどうかを判定する。

テストではプログラムの正しさを証明できないため、いつテストを終了させるのかがテスト に関する研究課題の1つである。テスト評価の1っとして、テストの充分性をプログラムの構 造と実行時の測定とに基づいて評価するのがテスト充分性評価法である。テストの目的の 1つ であるプログラムの信頼性向上は、テストの終了条件をどのように定めるかに依存する。

4 

テスト評価の方法として、信頼性成長モデ、ルを利用する方法もある [25

，

47]0テストにおい て誤りが検出され、その誤りが修正されれば、プログラムの信頼性が向上したと言える。そこ で、発見された誤りの数が増加すれば、信頼性が向上していると評価する信頼性成長曲線を作 成する。信頼性の値を評価する曲線をうまく選定すると、ある水準の信頼性を満足する地点を 見積ることが可能である。これによりテストの終了を判定することが可能になる。しかしなが ら、適切な信頼性成長曲線を選定することは困難であるし、また誤り数を人為的に操作できて しまうため客観的な判断が難しい。

この方法に対して、構造テストにおけるテスト充分性評価では被覆率を用いることにより客 観的に充分性を評価することができる。被覆率とは、次節で述べるように、テストの実施前に 定めた実行すべき事象(測定事象)に対する、テスト実施の際に実行された測定事象の割合であ る。測定事象はテスト基準により定められる。

従来の逐次処理プρログラムに対しては様々なテスト基準が提案されている。しかしながら並 行処理プログラムのテスト基準に対しては充分研究されたとは言い難い。そこで本論文では並 行処理プログラムの構造に基づいたテスト充分性評価法を研究する。

1 . 2   テスト充分性評価

プログラムの構造に基づいたテスト充分性評価と、既存のテスト基準について考察する。テ ストの充分性をプログラムの構造と実行時の測定とに基づいて評価するのがテスト充分性 評価法である。本研究では、逐次処理プログラムのテスト充分性評価に用いている被覆率

( Cov e r a g e )

を並行処理フ。ログラムのテスト充分性評価にも用いる。

ここでは被覆率と既存のテスト基準について述べる。

1 . 2 . 1  

被覆率

構造テストにおいてテスト充分性は、被覆率により客観的に評価することができる。被覆率 とは、テストの実施前に定めた実行すべき事象(測定事象)に対する、テスト実施の際に実行さ れた測定事象の割合である。測定事象はテスト基準により定められる。テスト基準

Cr

により 定められる測定事象の集合を次の表記法で表わす。

5 

【定義】 1  測定事象集合:

TE(C け

テスト基準 Cγ によって定められる測定事象の集合。 ロ

たとえば、後で述べる文被覆(all‑statenlentS)テスト基準を考える。文被覆テスト基準は C_o とも表記される。この文被覆テスト基準の測定事象集合は、

TE(C o )  = 

{プログラム内の全ての文}•

となる。

テスト基準により定められる測定事象の集合

T E ( C r )

の中で、テスト実施で実際に実行され た測定事象の割合が被覆率である。被覆率Covの形式的な定義は次の通りである。

【定義】 2  被覆率:Cov 

Cov

^二

￨ W I

I T E ( C T ) I  

ここで

TE(C γ )

はテスト基準

C r

により定められる測定事象集合を、 W は実行された測定事 象の集合を、 1.  1は集合の要素数を表す。

ロ

被覆率を求めるためにはテストを実施する前に測定事象が抽出できなければならない。この 測定事象はテスト基準により定義される。構造テストでは、被テストプログラムのソースコー

ドから測定事象を定める。算出される被覆率によってテスト充分性を客観的に評価する。

1 . 3   テスト基準

現在までに、逐次処理プログラムに対しては様々なテスト基準が提案されている。並行処理 プログラムに対してもいくつかのテスト基準が提案されている。この節では現在までに提案さ れているテスト基準について述べる。

1 . 3 . 1  

逐次処理プログラムのテスト基準

従来の逐次処理プログラムに対しては、現在までに以下のようなテスト基準が提案されてい る[10

， 5 2 ] 0  

‑文被覆

( a l l ‑ s t a t e m e n t s )

テスト基準

c

。テスト基準とも呼ばれる。プログラム内のすべての文の少なくとも 1回実行すること を要求するテスト基準。

TE(Co

)={

プログラム内の全ての文}.

‑枝被覆

( a l l ‑b r a n c h e s )

テスト基準

C₁テスト基準とも呼ばれる。プログラム内にあるすべての分岐を少なくとも 1回実行す ることを要求するテスト基準。

TE(C

I)={

制御フローグラフ内の全制御枝}.

‑全路

( a l l ‑ p a t h s )

テスト基準

C∞テスト基準とも呼ばれる。プログラム内に存在するすべての実行経路を少なくとも 1 回実行することを要求するテスト基準。

TE(C∞) 

= 

{制御フローグラフ内の全ての路}.

C∞テスト基準の測定事象は一般に膨大な数になる。プログラムに無限ルーフ。が存在する と、

C

∞テスト基準の測定事象は無限大個になる。

‑定義使用被覆

( a l l ‑ D U ‑ p a t h s )

テスト基準

プログラムのデータフローグラフを考えた場合における、すべてのデータフローを少な くとも 1回実行することを要求するテスト基準。

T 

E ( a l l ‑ D U ‑ p a t h s )   = 

{データフローグラフにおける、全ての定義、使用の対}.

ここに挙げたテスト基準に基づいて算出される被覆率がそれぞれ 100%に達しでも、被テス トプログラムの正しさを証明するものではない。しかしながら、これらの被覆率はテスト充分 性を定量的に表す実用的な指標の 1っとして用いられているロ

1 . 3 . 2   並行処理プログラムのテスト基準

逐次処理プログラムのテスト基準を用いて、並行処理プログラムのテスト充分性を評価する のは妥当ではない。これは逐次処理プログラムのテスト法が並行処理プログラム特有の同期や 通信、非決定性を考慮に入れていないためである。このことを簡単な例で示す。

Pl  P2 

1: begin  4: begin  2: m~l; 5: m ~2;

3:  end;  6; end; 

図1.2:非決定的な実行を行う並行処理フ。ログラムの例

図l.2のように、並行処理プログラムPが2つのプロセス P₁、P₂を持っとする。このプロ グラムはプロセス P₁がメモリ mにいl引を、 P₂が同じmに 2"を書き込むものである。 P をl度実行すればP₁、P₂内のそれぞれの全実行経路が被覆されたことになり、

C

∞テスト基 準を満足する。逐次処理プログラムの場合、 C∞テスト基準の被覆率が 100%に達すれば必ず プログラム内のすべての誤りを検出することができる。しかしながら、プログラム

P

の正しさ を証明できてはいない。 2つのプロセスの代入文の実行順序が 2つあるのでそのどちらもテス トしなければならない。このように逐次処理フ。ログラムのテスト基準だけで並行処理プログラ ムのテスト充分性を評価するのは妥当ではない。

並行処理プログラムのテスト充分性を評価するためには、並行処理プログラム特有の非決定 的な実行を考慮に入れたテスト基準が必要である。テスト基準は、定量的に評価が可能でかつ 利用が容易であることが必要である。

並行処理プログラムにおける被覆率を用いたテスト充分性評価についてはいくつかの提案が 行われている。以下に並行処理プログラムに対する既存のテスト基準について述べる。

8 

‑広域データフローテスト基準

古川らはAda並行処理プログラムを対象に、広域データフローテスト基準を提案して いる

[ 1 7 ] 0

これは定義使用被覆テスト基準を並行処理プログラムに拡張したものであ る。並行処理プログラム内で用いられている共有変数に着目し、共有変数のタスク間に

おけるデータフローを測定事象とする。このテスト基準は共有変数にのみ着目している ために一般の並行処理プログラムのテスト充分性を評価するものとは言い難いロ

‑ランデブー通路テスト基準

古川らはAda並行処理プログラムを対象に、タスク間の通信をランデブ一通路として 定義し、このランデブ一通路をテストにおける測定事象とするテスト充分性評価法を提 案している [16]。これはAda並行処理プログラムにおけるランデブーにのみ注目したテ スト基準であるため一般の並行処理プログラムのテスト充分性を評価するものとは言い 難い。

‑事象グラフ (EG)、事象相互作用グラフ (EIλG)、協調路

片山らはAda並行処理プログラムを対象に、次のようなテスト基準を用いたテスト ケース作成法を提案している [32.33

， 

34]0  (1)タスク聞のランデブーによる通信を少な くとも 1回実行する。 (2)事象グラフの節点を少なくと 1回実行する。この 2つの基準 を満足するテストケースを協調路としてAclaソースコードから機械的に作成する方法を 提案している。このテスト基準では、タスク(プロセス)開通信についてのテストは可能 であるが、共有変数についてのテストは考慮されていなし、。

‑フ。ロセス従属ネット

(PDN)

程は並行処理プログラムにおける従属性を表現するモデルとしてプロセス従属ネット を提案している [7

，

8、

9 ] 0

またこのプロセス従属ネットに基づく統合的プログラム開発支 援環境を考案している。

程は、非決定的並列制御フローネット

(CFN)

、非決定的並列定義使用ネット

(DUN)

も提案している。非決定的並列制御フロ}ネット

(CFN)

および非決定的並列定義使用 ネット

(DUN)

は、逐次処理フ。ログラムのモデルとして考案されてきた制御フローグラフ や定義使用グラフを並行処理プログラムに適用できるように拡張したものである。

このプロセス依存ネット上で、並行処理プログラムの開発を支援する様々な方法を提案 している。テストについても、ネット(グラフ)の枝を被覆するテスト基準を提案してい

10 

.同期列

Taiらは同期列 (SYN‑Sequence)を定義し、並行処理プログラムにおける非決定的な 実行を同期列に従い決定的に再実行させる方法を提案している

[ 4 8 ] 0

並行処理プログラ ムを決定的に再実行させることにより誤りを再現することが可能になる。これによりプ ログラムのデバッグを容易にする。またデバッグだけでなく、ある並行処理プログラム おいて実行可能は同期列の全てをテストにおける測定事象と考える 到達可能性テスト (Reachability Testing)も提案している

[ 2 3 ] 0

このテスト基準では測定事象の数が膨大な ものになるため、実用的とは言い難い。

.並行状態グラフ

Taylorらはプログラムのプロセスの状態の組合せ(並行状態)を節点とし、並行状態を 変更する事象を枝とする並行状態グラフ (ConcurrencyGraph)を定義した

[ 5 1 ] 0

テスト を実施したときに実現された並行状態グラフの節点や枝の被覆率によってテスト充分性 を評価する。しかしながら並行状態グラフには次の2つの問題点がある。

( 1 )

並行状態グラフの節点や枝の数がフ。ロセス数に対して組合せ論的に増大するために、

被覆率を 100%にすることが困難である。

( 2 )

並行状態グラフを定義するためにはプロセスの数が静的に決まっていなければならな

し、。

並行処理プログラムには、動的にプロセスが生成され、生成されたプロセス間で同期 や通信を行いながら処理を進めるプログラムが多い。このためプロセス数が静的に決 まっていなければならない並行状態グラフは実用的とは言い難い。

‑トレースフローグラフ (TFG)

M. B. Dwyerおよび L.A. Clarkeはプログラムの制御フローグラフに通信枝および MIP(May Immediately Predecessor)枝を付加したトレースフローグラフを定義した。

これはAda並行処理プログラムを対象にしている。このTFGを基に並行処理プログラ ムのデータフローを解析する手法を提案している

[ 1 1 ]

。しかしながら、 TFGには次にの ような問題がある。

( 1 )  TFG

において枝の数は最悪の場合節点数の

3

乗に比例する。(

I E I  

= 

O ( I N I

³) 

，  E

は

校集合、 Nは節点集合を表わす。)節点数はプログラムの文数に比例しているため、プ ログラムが複雑になれば

TFG

も巨大なものになってしまう。

( 2 )

ソースコードから

TFG

を定義するため、フ。ロセス数が動的に生成される場合が考慮 されていない。

( 3 )  TFG

自体が複雑であるため、

TFG

解析の計算量が大きい。

本論文で提案する順序列テスト基準は、ソースコードに基づくテスト基準である。プロセス 数がテストの実施前に決まっていなくとも、テストの実施前に順序列の長さを決めておけば ソースコードからテストにおける測定事象が抽出できる。従って

T a y l o r

の並行状態グラフにお ける問題点の (2)や、

C l a r l

日の

TFG

における問題点(2)を回避できる。

並行処理プログラムの動作モデル

順序列テスト基準を定義する前に、 並行処理プログラムの動作モデ、ルおよびその記述法を定義 する。ここではインターリーフ、モデルを用いる

[ 3 ]

。インターリーブモデルは、並行処理フ。ログ ラムを単一のプロセッサで実行する場合を表わすためのモデ、ルで、ある。

インターリーブモデル上で、は並行処理フ。ログラムの動作を次の様に考える。並行処理プログ ラム

P

は複数のフ。ロセスから成るとする。プロセスは逐次的に命令を実行する。プロセッサは 実行可能な命令を 1つ選択して実行する。プロセス間の通信や同期に関する命令とそれらによ る制約とを除き、どの命令を選出するかは任意である。フ。ロセッサが実行する命令はフ。ログラ ム内のフ。ロセスに記述されている命令のみであり、その他の命令が実行されることはない。プ ログラム

P

全体での命令の実行系列は、プロセッサの状態により変化する。

2 . 1   並行処理プログラム

並行処理プログラムは、逐次処理を行う単位であるプロセスが互いに通信や同期を行いなが ら処理を進めるプログラムである。以降、プロセス問で通信や同期を行う文を通信同期文と記 述する。

インターリーブモデ、ル上で、並行処理フ。ログラムP を以下のように η個のフ。ロセスの集りと して定義する。

【定義】 3  並行処理プログラム :P

p 

= =   {P

1

，

九γ・.

， P n } ， 

13 

ここでP_i

，

1 ~ i ~ n

，

はプロセス、 ηはプロセス数である。

口

プロセスは文を節点、 制御の移行を枝とするグラフとして定義する。

【定義】 4  プロセス:Pi. 1 ~ i ~ n. 

~. = (Si

， 

Ei) 

ここで、ふはPi^{内の文の集合、} Eiは久内の枝の集合を表す。ただしく仏b>は順序列を表 す。また、

ぶ ={Sj 

I 

^Sj = 

s t

αrti V Sj

ε

SY入〉 V

S J ε

RE.¥I!i}う

Ei 

=  {< 

u

， 

v 

>  I  u .  

l'

ε

S

i } ， 

である。ここで、

s t

α

r t

_iはPi^{の開始文、} SY̲Yi^はPi内の通信同期文の集合、 REJdi^は通信 同期文以外の文の集合を表す。

口

通信や同期の際の識別子をσ、フ。ロセス聞の通信同期文をsync_j(σ)(ただし jはプログラム 内での通信同期文の通し番号を表す)と表す。プロセス間の通信や同期を次のように定義す る。

【定義】 5  通信や同期

フ。ロセス P_A とP_Bが、 P_A内の文sync_x(

σ )

とP_B内の

s y n c ν ( σ )

で通信や同期を行う場合、こ れを次に示す対で表現する。

[sync_x(

σ ) ， 

sync_y(

σ )  ] 

m

個のプロセスが文sync_x1(

σ) ，

sync_x2(

σ ) ， '   .  .  ，

sync_xm(

σ )

で通信や同期を行う場合、これを次 に示す組で表現する。

[ s y n c1 ( σ ) ，  S yn c2 ( σ ) ，  • • "  s y n c バ σ )] 

口

プログラムの中でσに同じ値を持つ文が、プロセス間で互いに通信や同期を行う。セマフオ 変数やAdaのエントリ名が σに相当し、セマフォ変数を操作する P

，

V命令や、 Adaエントリ 呼出文やエントリ呼出受付文などがsyncj (

σ )

に相当する。共有変数の場合は変数名が

σ

に対応

し、変数を操作する文がsync^j 

( σ )

に相当する。

プログラム

P

内のすべての通信同期文を集めた通信同期文集合5YJVCをつぎのように定義 する。

【定義】 6  通 信 同 期 文 集 合 :511"八℃

5YJVC 

= 

5Y入‑1U 

5 1 ‑

入、

u.  .  . 

U 

5 1 ‑

八二l・

ここで、 5YN_i

， 

1 :S; i 三月.はプロセス P_i内の通信同期文の集合である。

口

通信同期文集合

5

1'入℃は以下のようにも表すことができる。

5YNC= {sync_j(σ)} 

2 . 2   実行経路および実行系列

並 行 処 理 プ ロ グ ラ ム

P

の 実 行 系 列 を 定 義 す る 。 ま ず 、 各 プ ロ セ ス 内 で の 実 行 経 路 を 定 義 す る。プロセス

P

i

，

1 :S;  i :S; 

n ，

における実行経路の集合を Pαtんとして定義する。

【定義】 7  実 行 経 路 集 合 :Path_i; 1 :S; i ::;  n. 

Pαthi = { <α1

，

α2

， ' "   ，

αた

> 1

αl二 stCLTt

i

^αた

ε S i

八

(1

三

j:S;

k‑l :

α3ε

S i

八 <αj

，

^aj+l >巴

E i ) }  . 

ここで、ふはプロセス

Pi

^{の文の集合、}

E i

はプロセス

Pi

^{の枝の集合である。}

口

並行に実行されるプロセスの実行経路をシャツフル

[ 1 ]

した列をプログラム全体の実行系列 として定義するために、シャツフル演算子を定義する。シャツフル演算後に生成される集合の 要素である列は、元の列における要素の順序関係を保存している。

【定義】 8  シャツフル演算子 :EB

2つ の 列 seql==<α1

，

α2γ ・1向 >;とseq2==< b1

， 

b2^γ・.

，

bz ^>と を シ ャ ツ フ ル す る こ と を seql EB seq2と表す。このシャツフルした結果は列の集合となり、次のように定義する。

seq1 EB seq2  ==  {sも==<C^ト C2， Ck+l>

I 

1三

t

三k

+ 

1 : Ci

ε { α

^ト

α

^{子 、}

α

ゎb1

，

b2ぅ ，b

t }  

^ 

0^1'de^1'ed( S(jj ) } 

ここで、列sqjに対する順序関係

0 7

^・de

，

^{'ed( sqj )は次の述語である。}

Ordered( sqj)  ==  (  主ざ

;y^

(C:r 

= 

α1 八Cy

= 

^(li+l) 二今

(C:L"+トん+2^司 、Cy‑1~ {α1

，

α2

，  • • • ，

αん}))八 ( Cx^二 bi^八Cy== bi+I)今

(C^:L>+トC叶 2、 Cν‑1ヂ{b1

，

b2

，  • • • ， 

bl }) ) 

シャツフル演算子の被演算項の 1つが列の集合Seqs == {seq

i }

であるときは集合の各要素と のシャツフルによってできた集合の和集合であるとする。すなわち、

S叩 EBseq == 

U 

seqi EB何 ? i=l，…ISeqsl 

である。同様に、列の集合の聞のシャツフノレの結果は、それぞれの要素の間でシャツフルした 結果の集合の和集合とする。

Seqs1 EB Seqs2 == 

U 

i=l，，，，，ISeqsll， 

j=l，…，ISeqs21 

seqi EB seqj 

口

プロセス P₁と 乃 の 実 行 経 路 の 集 合

P α

th₁と

P α

th₂のシャツフルした集合であるシャツフ ル実行系列集合Shuffled̲Pαth (Pαth₁

，

Pαth₂₎を以下のように定義する。

16 

【定義】 9  シャツフル実行系列集合:Sh^'l1f fledY^αth(P^αth1

， 

P^αth2) 

Shuf fledYαth(Pαth1ぅ

P

ぱh₂₎

= =  

Path₁ ED Path₂ 

ここで、

P α

th_il

i  = =  

1，

2

，はプロセス P_iの実行経路集合である。

口

プログラム

P

を構成するプロセス P_i、1:::; 

i

三爪の実行経路をシャツフルしたものがプロセ スの実行系列である。プログラム P の実行系列の集合を全シャツフル実行系列集合と呼び? AlLShuf fledYαth(P)として表す。

【定義】 10  全シャツフル実行系列集合:AlLSh II f fl ed Yαth(P) 

AILShuf fled̲Path(P) 

= =  

P^(lth ^1⑦ Path₂ EB . . . EB Path^{η .} 

ととで、

P α

th_iJ

1 

~

i 

~η. はプロセス Pi の実行経路集合である。

口

シャツフル実行系列集合の要素をシャツフル実行系列といい、全シャツフル実行系列集合の要 素を全、ンャッフル実行系列とする。

2 . 3   通信同期制約

全シャツフル実行系列には、通信や同期により実際の実行で発生しないものがある。このよ うに通信や同期による実行系列の制約を通信同期制約と呼び、述語Sync̲Consで表す。

通信同期制約を定義する前に、準備として部分系列関数Sub̲Seqおよび通信同期選出関数

E x

̲Pαthを定義する。

系列seq==く α1，α2γ・，α，>から長さ kの部分系列を取り出す部分系列関数S^'Ub ̲S e q ( s e q) k )  を次のように定義する。

【定義】 11  部分系列関数:Sllb̲S eq( seq

， 

k) 

Sub̲Seq(seq

， 

k) 

= = <  

b1

， 

b2γ・"bk >， 1三k三l^う

17 

ただし、

( seq ==<α1

， 

^Q2

， "  ， ， 白 >  ) 八

( 1三

t

三[

‑ k  + 

1

， 

1三j三

k‑l

( αi == b₁ )  二今 ( αi+j == b1+j ) 

) ， 

である。

口

系列 α

s p

==<α1

，

α2

， ' "   ，

α

1>

から1)慎序関係を保存しつつ通信同期文のみを取り出す通信同期 選出関数

Ex

̲P

a t h (αs p )

を次のように定義する。

【定義】

1 2  

通信同期選出関数:

E l : ̲P

αth(α

s p )  

E.T̲P

a t h (

α

s p )  

== 

<  b

₁

，  b

₂

，  • . 

. 

• b 

k 

> 

ただし、

(α

s p

二 く α1

，

α2

， • • •

^)α

，>)八

( b_jεSYJYC

， 

1三j三ん)八 ( 1三

t

三

[‑l ， l : : : ; j

三

k‑1

(向==

bj 

α ^

^{i+x == bj+1 )キ 1三z三l‑i+1)，}

である。

口

以上の関数の定義を用いて通信同期制約を定義する。まず、 2つのプロセス間で通信同期を 行う場合の通信同期制約を考える。次にそれを拡張して m 個のプロセス問で通信を行う場合

の通信同期制約を考える。

( 1 )  2

つのプロセス間で通信や同期を行う場合

フ。ログラムP内のフ。ロセス

P

_A

， P

_s， 1:::; 

A ， B

三ηが、通信同期文 sync_x

( σ ) ， 

syncy(σ)で通 信や同期

[ sync_x(σ)

，

sync_y(σ) ] 

， 

を行うものとするD すなわち、

s y n cx( σ ) ε SY^ T A

^八

s y n c

_y(

σ ) ε SYN

_B

， 

である。ただし、 SY~ 八iA ， Sy'jVB ^{はそれぞれプロセス PA ， P}B 内の通信同期文の集合を表す。

プ ロ セ ス

PA ， P

Bの 実 行 経 路 集 合

PathA ， P α t h

Bか ら シ ャ ツ フ ル 実 行 系 列 集 合

Shv  f  f l e d

̲Fα

th(P

α

t hA

^、

Path

_B)を作り、その 1要素を

shufp

とする。すなわち、

shufp ε Shuf  f l e d

̲F

a t h ( P a t hA

^、

P αt h

_B

  ， )

で あ る 。 識 別 子 σを 持 つ 通 信 同 期 文 が 列 の 先 頭 に あ り 、 か っ 同 じ 識 別 子 を 持 つ 通 信 同 期 文 が 列 の 最 後 尾 に あ る 長 さ kの 部 分 系 列

s u b ̲ p =< 

C1 、

C 2

，• ・ . ，

C k 

>を 系 列

shufp

か ら 関 数

S u b ̲ S e q ( s h u f p ，  k )

を用いて取り出す。すなわち、

( s y n c x  (

σ) = C1  八

s y n c

_y(σ)= 

C k )  

V 

( s y n c

_x 

( σ )

二 九 八

s y n c

_y

( σ )   =  c d .  

が成立する。

シャツフル実行系列

shufp

に対する通信同期制約 (

Sync̲Cons(shufp) )

を述語として定義 する。

【定義】

1 3  

通 信 同 期 制 約 :

Sy

口

c ̲ C o n s ( s h

^'l1

f p )

Sync̲Cons(shufp) 

=  ( 

( s y n c

_x

( σ )

^{二 C1}

^  ^{s y n c} y ( σ )  

= 

C k )  

今 (C2

，

C3 ，・ . ， Ck-1~SA)

)

八

( s y n c

_x(σ)^二

C k

八

s y n c

_y(σ)

= 

^C1) 

今( C 2 ， 

C3

，  • • • ， C k ‑ 1  

~

S 

^{B )  )} 

口

シャツフル実行系列

shufp

の通信同期文は通信同期制約を 1回満せばよい。

( 2 )   m

個のプロセス間で通信同期を行う場合

プロセス

PA 1 ， _{PA 2} ， ・ ・ ・ ， _PAm ，

1三Aj:5nが文

s y n c

_X1

( σ ) ，  .  .  .  ，  s y n c x m   ( σ )

で通信や同期

[  s y n c

_x1 

( σ ) ・ ， s y n c

_{X m}

( σ )  ]   ，

を行うものとする。すなわち、

synczj(σ)εSY 

N_Aj

， 

1三j三m

，

である。ただし、 SYJV_Ajはプロセス P_A)内の通信同期文の集合を表す。

プログラム

P

の全シャツフル実行系列集合を作り、その 1要素を α

s p

とする。すなわち

α

s p ε

AlL幻

で あ る 。 識 別 子σを 持 つ 通 信 同 期 文 が 列 の 先 頭 に あ り 、 か っ 同 じ 識 別 子 を 持 つ 通 信 同 期 文 が 列 の 最 後 尾 に あ る 長 さ kの 部 分 系 列

s u b ̲ p = = <   C l ，  C 2 ・ . ・ ， ，

^Ck >を 、 系 列

α s p

か ら関数

S u b ̲ S e q (

α

s p ， k )

を 用 い て 取 り 出 す 。 た だ し 、 部 分 系 列 に は 通 信 や 同 期 を 行 う 文

s y n c

_X1 

( σ ) γ

・.

， s y n c

_xm 

( σ )

がすべて含まれているものとする。すなわち、

が成立する。

(  (  V s y n c

_x] 

( σ ) ， 

1

三

j::::;  m  : 

s y n c

_Xj(

σ )ε{ C l ， 

C2， .・.

，

Ck} )八

(  Clε{  s y n c

_x1 

( σ ) .   s y n c .

_r2 

( σ ) 、， s y n c

_{X m}

( σ ) }   ) 八

( Ck

ε{sync

_x1 

( σ )

、

s y n c '

₁'2

( σ )

.  

， s y n c

_xm (

σ)})    ， )

このとき、全シャツフル実行系列

α s p

に対する通信同期制約

Syn c ̲ C o n s (αs p )

を述語として 定義する。

【定義】 14  通信同期制約:

S y n c ̲ C o n s ( a s p )  

S y n c ̲ C o n s (

α

s p )   = =  

( s y n c

_x1 

( σ )   = =   C l  

二今 C2

，  C 3 ， 

. . . 

，

Ck・

  t r S 

Al )  八

( s y n c

_X2 

( σ )

二

C l

二今

C 2 ，  C 3 ，  .  .  .  ) 

Ck 

  t r S 

A2) 

ハ

( s y n c

_{X m}  

( σ )   = =   C l  

キ

C 2 ， C 3 ，  • • • ，

^Ck 

  t r S 

Am ) 

口

全シャツフル実行系列α

s p

の通信同期文は通信同期制約を 1回満せばよい。

通信同期制約により、プログラム内の実行可能な実行系列を定義できる。 すなわち、通信同 期制約を満足する全シャツフル実行系列が実行可能な実行系列で、あるo

20 

Pl 

1:  begin  2: m.‑l; 

3: end; 

P2 

4:  begin  5: m骨 ー2;

6:  end; 

図2.1:並行処理プログラムの例

例えば、図

2 . 1

の並行処理プログラム

P

を実行する際、インターリーブモデ、ル上で、実現可能 な実行系列の集合は、次のようになる^o

AlLShげfled̲Path(P) = { 

<  1 2 3 4 5 6 

>， 

<  1 2 4 3 5 6  

>， 

<  1 2 4 5 3 6  

>， 

<  1 2 4 5 6 3  

>， 

く

1 4 2 3 5 6

> く

1 4 2 5 3 6

>、く

1 4 2 5 6 3

>， 

<  1 4 5 2 3 6  

>，く

1 4 5 2 6 3

>，く

1 4 5 6 2 3

>， 

<  4 1 2 3 5 6  

>， 

<  4 1 2 5 3 6  

>， 

<  4 1 2 5 6 3  

>， 

<  4 1 5 2 3 6  

>ぅく

4 1 5 2 6 3

>ぅ<

4 1 5 6 2 3  

>， 

く

4 5 1 2 3 6

>，く

4 5 1 2 6 3

>，く

4 5 1 6 2 3

>， 

<  4 5 6 1 2 3   >  } 

順序列テスト基準

3 . 1   定義

並行処理プログラムをインターリーブで解釈する場合、実現可能な実行系列をすべて実行さ せればプログラム内のすべての誤りを検出できる可能性がある。しかしながら、一般の並行処 理フ。ログラムにおいて、実現可能な実行系列の数は組み合わせ論的に増大するし、無限ループ がある場合には無限になる。実行可能な実行系列をすべて実行することは現実的に不可能であ

る。実用的時間内にテストを終了するためにはより簡易なテスト基準が望ましい。

逐次処理プログラムと異なり、並行処理プログラムには次のような特徴がある。プロセスの 実行順序が非決定的である並行処理プログラムでは、同一の入力データに対して複数の実行結 果を取る場合が起りうる。この非決定性が問題となる。次にフ。ロセス間でデータを受け渡すプ ロセス聞の通信がある。またプロセス間で同期もある。並行処理プログラムのテスト充分性評 価法を考える場合、これらの特徴を考慮したテスト基準が必要である。

インターリーブモデルで、は、入力データが同じ場合、局所変数への代入文や参照文のプロセ ス聞における実行順序がプログラム全体の実行結果を変化させることはない。通信、同期、共 有変数への代入あるいは参照、といった並行処理に関する文の実行順序は結果を変化させる可 能性がある。そこで、これらの並行処理に関する文を通信同期文として定義する [27

，

29

，  3 1 ] 0  

【定義】

1 5  

通信同期文

並行処理プログラム内にあるプロセス聞の通信文、同期文、および共有資源を操作する文を 23 

Pl  P2  P3  Pl  P2  P3  ^{実 行 系 列} .

.

  一一ー、 ^{... トーー『}

f 

1 2 4  2 4 1 

2

総同ゆ 偽 4 1 I  3 3 2 … 

4 1 3 

• ^1 4 4 

2 1  3 2 

図 3.1:並行処理に関連のある文に注目した実行系列の例

通信同期文という。資源を操作する文とは変数などの資源の作成、内容の変更(代入)、内容の

参照、削除、を行なう文を意味する。 口

図3.1のように、プロセス聞の通信同期文だけに注目し、これらの命令を組合せた順序列を 考える。この列をテストにおいて実行すべき事象とする。測定事象数を有限にするため、有限 長の通信同期文の列を測定事象とする

[ 2 7 . 2 9

、31]0

並行処理プログラムの特徴として、 lつのソースコードから複数のプロセスを生成するプロ セスの動的生成がある。図

3 . 2

は、ソースコードでは

1

つのプロセスであるけれども、実行時 に複数のプロセスが生成され、互いに通信を行うプログラムである。このプログラムでは、通 信同期文3が連続して実行される。同一の通信同期文を複数個含む列も測定事象に含める必要 がある。

順序列テスト基準の形式的な定義は以下の通りである。

【定義】 16  順序列テスト基準:

OSC

_k 

通信同期文を要素とする長さ kの順序列を考える。この順序列が少なくとも 1回実行される ことを要求するテスト基準。

OSC

_kの測定事象集合を以下のように表わす。

T  E(OSC

k) = 

{< 

S1

， 

S2

， '   .  .  ，

Sk 

> 

ISj

ε

SYNC

， 

1三j:S; 

k  } .  

口 24 

/ 一 一 ¥ 、 Proc1  Proc2 

図 3.2:プロセスの動的生成の例

第2章の定義を用いると、順序列テスト基準とプログラムについて以下の等式が成り立つo

TE(05C

k)  = { ^S

ω ̲ s e q   I δ

ゆ

j j P q ε { S u b ̲ S e q ( e x ̲ p . k )   I 

x ̲ p ε {Ex

̲F

α t h ( α s p )   I 

α

s p ε A l L S h u f  f l e d Y a t h ( P )   }  }  } 

3 . 2   意味

順序列テスト基準

05C

_kの kに具体的な値を与えた場合、順序列テスト基準の持つ意味は以 下の通りである口

• k 

= 

^1の場合

TE(05C

1

)={<s>} 

05C

₁ではプログラム内に存在するすべての通信同期文の1つ1つがテストにおける測定 事象になる。

05C

₁は、プログラム内のすべての通信同期文を少なくとも

1

回実行する

ことを要求するテスト基準である。

C _o

テスト基準が満足されたならば、

05C

₁テスト基 準も満足される。

• k  = =  

2の場合

TE(05C₂₎ 

=  { く

81

，

82

>} 

05C2では、プログラム内の通信同期文の長さ 2の順序列がテストにおける測定事象にな る。 05C2テスト基準を満足すれば、プログラム内における 2つのプロセス間の同期や 通信を少なくとも 1回実行することになる。 Ada並行処理プログラムにおけるランデ ブ一通路テスト基準 [16]や共有変数のデータフローテスト基準 [17]は、この 05C₂テス

ト基準の特別な場合である。

.k=3

の場合

T E(05C₃₎ 

=  {< 

Sl

，

句、S3

>} 

05C₃では、プログラム内の通信同期文の長さ 3の順序列がテストにおける測定事象にな る。 05C₃テスト基準を満足するならば、プログラム内における 3つのプロセス間の同 期や通信を少なくとも 1回実行することになる。

• k 

=

∞ の 場 合

TE(05C

∞)  =  {< 

Sl，S2，"'，Sわ > }

ノレープが存在するプログラムでは、無限長の実行系列が存在する可能性がある。その場 合、実行系列から通信同期文だけを抽出した列も無限長になる可能性がある。無限長の 順序列をテストにおける測定事象にするのが 05C∞テスト基準である白 05C∞テスト基 準は、プログラム実行時に起り得る通信同期文の全順序列を少なくとも 1回実行するこ とを要求するテスト基準であるロしかしながら無限長の順序列が測定事象であるため、

05C∞テスト基準を満足する事は現実的には不可能である。

3 . 3 例

この節では、順序列テスト基準を具体的なフ。ログラムに適用する。例題として「哲学者2人 の食事問題J を用いる。 i哲学者

2

人の食事問題Jのフローチャートを図3.3に示す。並行処 理の部分である同期にはセマフォ

[ 1 2 ， 1 3 ]

を用いた。

UNIX

上の

C

言語で記述した哲学者の食 事問題プログラムを付録

A

に付ける。

26 

Philosopher1  ^Pilosopher2 

P(forkl)  P(fork2)  5 

2  P(fork2)  P(forkl)  6 

ド ロ 巨 ド

3  V(fork2)  V(forkl)  7 

4  V(forkl)  V(fork2)  8 

図 3.3: I哲学者2人の食事問題」のフローグラフ

この例ではセマフォの P 命令や V 命令が通信同期文集合 SY~~-C の要素となる。まず、 P，V

命令に通し番号 1‑‑‑8を付ける(図 3.3参照)。通し番号を用いてsync_i

( σ )

， 1 :::;  i三8，をiと表 すと、哲学者の食事問題における順序列テスト基準の測定事象は以下のようになる。

l. 

k  = 

1 

T  E(OSC I )   = 

{< 1 >， < 2 >司<3>ぅ<4 >，く5>， < 6 >， < 7 >， < 8 >} 

測定事象の総数は m = 8、m =

I S

1"八

‑ C I

である。

2. k 

= 

2 

T  E  (  0  S  C

2) 

=  { 

< 1， 1 >， < 1， 2 >， < 1， 3 >， 

< 

1、7>， 

< 

1，8>， 

< 2，1 >， < 2，2 >，  <2、8>， 

<8，1>， <8，2>，く8，3>，  く 8

，

8> } 

測定事象の総数は

m

²

= 

⁶⁴である。