testing - FIFO セマフォ テスト

Question

FIFO セマフォを実装しましたが、適切に動作していることをテスト/証明する方法が必要です。簡単なテストは、セマフォで待機しようとするいくつかのスレッドを作成し、数字を含むメッセージを出力することです。数字が正しい場合は FIFO である必要がありますが、これはそれを証明するのに十分ではありません。たまたま発生。したがって、それをテストするより良い方法が必要です。
必要に応じて、ロックまたは条件変数も使用できます。
ありがとう

Answer 1

あなたが文章で説明していることは「しかし、その順序は偶然に発生した可能性があるため、これを証明するには不十分です」というのは、どういうわけか既知のジレンマです。

1) 仕様があっても、その仕様が意図と一致するかどうかは保証できません。これを説明するために、 「正しさの限界」から例を挙げます。次の因数分解関数の仕様を考えてみましょう。

A * B = C のように A と B を計算します。

A=1しかし、とを返す実装を持つことができるので、それだけでは十分ではありませんB=C。追加してもとにA,B != 1つながる可能性があるため、唯一の正しい仕様は と述べなければなりません。これは、真の意図に一致する仕様を作成することがいかに複雑であるかを示すためのものです。A=-1B=-CA,B>1

2) アルゴリズムを証明したとしても、実装が実際に正しいことを意味するわけではありません。これは、Donald Knuth からの次の引用で最もよく説明されています。

上記のコードのバグに注意してください。私はそれが正しいことを証明しただけで、試したことはありません。

3)テストは、バグの存在を明らかにするだけで、バグがないことを明らかにすることはできません。この引用はDijkstraに遡ります。

テストは、バグの存在を示すために使用できますが、バグがないことを示すためには使用できません。

結論: あなたは運命づけられており、あなたのコードがその意図に従って正しいことを 100% 確信することはできません! でも物は悪くない。通常、コードに高い信頼を置いていれば十分です。たとえば、複数のスレッドを使用してもまだ十分でない場合は、ファジングを使用して、テストの実行をさらにランダム化することもできます。テストが常にパスする場合は、コードが優れていると確信できます。

Answer 2

その注文は偶然に発生した可能性があるためです。

テストを数回 (たとえば 10 回) 実行し、そのたびに順序が正しいことをテストできます。これにより、偶然ではないことが保証されます。

PS単体テストでの複数のスレッドは通常回避されます