+ の

￨

￨ i y G

￨

￨ +仇

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

4 . 2   信頼性評価

テストケースを作成しテストデータを選定するテスト法が「信頼できるJ とは、プログラム に誤りがあるならば、テスト法に従って作成したテストデータにより誤りを必ず発見できるこ とをいう [21]0 したがって、 「信頼できる」テスト法により作成したテスト集合(テストデー タ)に対してテストの実施結果が全て正当であるならば、プログラムは正当である。任意のプ ログラムに対して「信頼できるJテスト法は「徹底テスト (exhaustiyetesting) Jのみである [43

， 

52]0 しかしながら「徹底テスト」は一般に実現不可能であるため、現実に用いられている

テスト法については、ある特定の誤りを含んだプログラムに対する信頼性を議論できるだけで ある。ここでは順序列テスト基準の誤り対する信頼性について述べる。

まず並行処理プログラムの誤りを分類する。並行処理プログラムの誤りは、誤りの発生原因 により次の 3種類に分類することが考えられる [3

，

14

， 

29]0 

( i )

プロセス内誤り・・・逐次処理プログラムにおいて考えられる誤り。

( i i )

通信誤り・・・並行に実行されるプロセス間でのデータの受け渡し時において発生する誤 り。

31 

(iii)同期誤り・・・次の 3種類に分類できる。

(  a )

生存性破壊誤り・・・フ。ログラムが意味のある動作を行わない。デ、ツドロックとも呼 ばれる。

( b )

安全性破壊誤り ・・相互排除の失敗によるデータの一貫性の喪失。

( c )

公平性破壊誤り ・・ある特定のプロセスだけが実行を不当に待たされる。ライブ

ロックとも呼ばれる。

順序列テスト基準は、プロセス聞の通信や同期に着目したテスト基準である。各プロセスの 中で発生するプロセス内誤りは考慮していない。以下に通信誤りおよび生存性破壊誤り (デッ ドロック)、安全性破壊誤りの、 3つの種類の誤りに対する順序列テスト基準の信頼性を考察す る。

4 . 2 . 1  

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

通信誤りに対する順序列テスト基準の信頼性を検討する。通信誤りは次の 2つに分類で、きる [16

，

29]。

【定義】

1 9  

完全通信誤り

プロセス聞における通信の際、常に誤ったデータを受け渡す。

ロ

【定義】 20  部分通信誤り

プロセス間における通信の際、誤ったデータを受け渡す場合がある。 口

P1  P2 

s1 瞳盤ト--\~ーー唱富I s2 

図 4.2:プロセス聞の通信

図4.2に示すように、プロセス聞の通信は通信同期文の2つ 組

? 

‑B EE

‑‑4・

9u

c u    

唱E E

c u   ‑ rl i‑

‑ 

で表現される。ここで8i

，

i=1

，

2は通信文である。第2章では通信を [sync_i(

σ )

，sync_j

( σ ) ]

と記 述していたがここでは簡略化のために単に [81，82]と記述する。この2つ組で表現される通信 が行なわれる場合の、通信同期文の実行順序は、

<81

，

^82>ε TE(05C2) 

， 

< 82

， 

81 > ε TE(05C2) 

， 

の2つで、ある。この2っとも長さ 2の順序列テスト基準

05C

₂の測定事象に含まれている。

まず、通信 [81，82]が完全通信誤りを持つ場合を考える。もしも

05C

₂テスト基準を満足す るならば、プログラム内の2つのプロセス間の全ての通信が少くとも l回は実行されたことに なる。完全通信誤りでは通信の再に必ず誤りが発生するので、

05C

₂テスト基準を満足するな らば、通信[81，82]における完全通信誤りが必ず顕在する。故に、

05C

₂テスト基準を満足する テスト法は、完全通信誤りに対し「信頼できる」テスト法である。

4.1節 の 定 義17に従って、テスト基準

C r 1

と

Cr2

に包含関係

C r 1 コ C r 2

が あ る と 仮 定 す る。仮にテスト基準

C r 2

がある種類の誤りに対し「信頼できる」ならば、

C

7'

2

を包含するテ スト基準

C r 1

も同じ種類の誤りに対し「信頼できる」。図4.1に示す包含関係があるので、

05C_k

， 

k ~ 2，テスト基準を満足するテスト法は、完全通信誤りに対して「信頼できるJテスト 法である。

次に通信 [81，82]が部分通信誤りを持つ場合を考える。

05C

₂テスト基準を満足すれば、上 記の通信は少なくとも 1回実行される。しかしながら、これらの通信が実行される際に誤りが 顕在する保証は無い。同様に列の長さを 3以上にしても誤りが顕在する保証は無い。すなわ

ち、順序列テスト基準は部分通信誤りに対して信頼できない。

通信誤りに対する信頼性を以下にまとめる。

[定理]1  完全通信誤りに対する信頼性

プログラムが完全通信誤りを含むならば、このプログラムの完全通信誤りに対し、順序列テ スト基準 05C_k

，

kど2が「信頼できる」。

[定理]2  部分通信誤りに対する信頼性

順序列テスト基準は部分通信誤りを含むプログラムに対して「信頼できなしリ。

33 

4 . 2 . 2  

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

同期誤りの中で、生存性破壊誤りであるデッドロックに対する順序列テスト基準の信頼性を 検討する。プログラム内の少なくとも 1つのプロセスが実行を終了せずに停止している場合、

あるいは無限ループに陥いり抜けだせない場合、この状態をデッドロックと言う。

デッドロックをその発生要因に基づき次のようにクラス分けする。

【定義】 21  クラス O

通信同期文を実行すれば、必ず発生するデッドロック。

口

【定義】 22  クラス l

変数の値には関わらずに、通信同期文がある特定の順序で実行された場合にのみ発生するデッ ドロック。

口

【定義】 23  クラス 2

通信同期文の実行順序に関らずに、フ。ログラム内の変数がある特定の値を持つ場合に発生する デッドロック。

口

【定義】 24  クラス 3

プログラム内の変数がある特定の値を持ち、かつ通信同期文がある特定の順序列に従う場合に のみ発生するデッドロック。

口

それぞれのクラスのデッドロックに対する順序列テスト基準の信頼性を以下で検討する。

クラス Oのデッドロックならば、通信同期文を少なくとも 1回実行すれば、必ずデッドロッ クが発生する。

05C

₁を満足すれば、全ての通信同期文が少なくとも 1回実行されている。故 に

05C

₁テスト基準を満足するテスト法はクラス

O

のデッドロックに対し信頼できる。

順序列テスト基準では、図4.1に示すように、包含関係 05C_k

コ

^05Ck+1

^，

^{k三1，が成立す}

る。つまり、 05C_k

，

k ~ 1，テスト基準を満足するテスト法はクラス Oのデッドロックに対し 信頼できる。

34 

クラス 1のデッドロックは変数の値には関らず、通信同期文の実行順序により発生する。変 数の値に依存しないために、プロセスの相互依存関係が循環する場合にのみデッドロックに陥 る。プログラム中の並行に動作するプロセス数が n個であるとする。プロセス聞の相互依存関 係の長さは高々

n+l

である。すなわち、プログラムにクラス 1のデッドロックが存在するな らば、通信同期文について長さ

n+l

の実行系列をすべてテストすれば、必ずデッドロックが 発生する。

故に、並行に実行されるプロセス数が ηの場合、

05C

₇₁+₁テスト基準を満足するテスト法 は、通信同期文により発生するクラス 1のデッドロックに対し信頼できる。

クラス 2のデッドロックは、通信同期文の実行順序に関わらず、変数の値に起因するデッド ロックである。順序列テスト基準は通信同期文にのみ着目したテスト基準であるため、プロセ ス内での変数の値の変化を何ら考慮していなし、。故にクラス 2のデッドロックに対して信頼で きない

クラス 3のデッドロックを発生する可能性を持つプログラムとしては、例えば複数のプロセ スが資源を獲得しつつ処理を行い、しかもその資源の必要量が動的に変化するプログラムが考 えられる。クラス 3のデッドロックもクラス 2と同様に、変数の値に起因するデッドロックで あるため順序列テスト基準はクラス 3のデッドロックに対して信頼できない。

まとめると以下のようになる。

[定理]3  生存性破壊誤りに対する信頼性

それぞれのクラスのデッドロックを含むプログラムに対して「信頼できるJ順序列テスト基 準の長さを以下に示す。

‑クラス O

05C_kJ k三lテスト基準が「信頼できる」。

‑クラス 1

05C_kJ 

k

さ

n+l

テスト基準が「信頼できる」 。ただし ηはプロセス数を表す。

‑クラス 2 }

I頃序列テスト基準は「信頼できないj。

35 

.クラス 3

順序列テスト基準は「信頼できなしリ。

4 . 2 . 3  

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

並行処理プログラムの実行において安全性破壊として知られている誤りがある [3

，

30

， 4 1 ] 0

並行処理プログラムを構成するプロセスの lつが占有して使用しなければならない計算機の資 源を使用中に他のプロセスが使用したために変数やファイルの値が利用者の希望通りにならな い誤りである白例えば、プリンタへの印刷において 2つ以上のプロセスが同時に出力を行った 場合、それぞれのプロセスからの出力結果が混在してしまい、別々に取り出すことがができな い。これを別々に取り出すためには、まず、 lつのプロセスがプリンタを占有して使用し、そ の出力が終了した時点で、他方のフ。ロセスが出力を開始する必要がある。

まず2つの用語を定義する。

【定義】

2 5  

資源

フ。ロセスが使用する変数、ファイル、プリンタなどを表す。 口

【定義】 26  操作可能最大プロセス数

lつの資源を同時に操作できるプロセスの最大数を表わす。 口 操作可能最大プロセス数が lである場合、資源、を同時に操作できるプロセスは1つだけであ る。資源を大文字のRで、 Rの操作可能最大フ。ロセス数小文字の rで表記する。

安全性破壊誤りの発生を防止するために、資源を占有するために、相互排除の機構として、

セマフォや資源のロックなどいろいろな実現手段が考えられている

[ 3 ， 1 2 ， 4 1 ] 0

基本的には、

相互排除のために資源を占有して使用しなければならないプロセス内の文の集合を 際どい領 域?として抽出し、際どい領域内の文を実行する間使用している資源を占有するために他のプ

ロセスの際どい領域の文の実行を禁止する。

効率を考えなければ、際どい領域をできるだけ大きくとる方が誤りの発生を防止できるので 望ましい。一方、際どい領域は並行に実行できるプロセスの数を制限するものであるので、際 どい領域をできるだけ狭くする方が効率を高めるために望ましい^D 際どい領域が正しく抽出さ れて、相互排除機構が正常に動作していれば、安全性破壊誤りは発生しない。しかしながら、

実際には際どい領域の抽出を誤って、安全性破壊誤りが発生する。

36 

ドキュメント内 並行処理プログラムのテスト充分性評価法に関する 研究 (ページ 42-113)