1

デバッガーを使用して競合状態を自動的にテストすることが可能かどうか疑問に思います。

たとえば、マルチスレッドキューをテストするイメージング。とりわけ、とを同時に呼び出すことができることをテストする必要がenqueue()ありdequeue()ます。

単純な単体テストでは、2つのスレッドを開始し、それぞれがループ内で呼び出し、結果を確認することができenqueue()ますdequeue()。

// thread A
for( int i=0; i<count; i+=1 ) {
  enqueue( queue, i );
}

// thread B
for( int i=0; i<count; i+=1 ) {
  ASSERT( i == dequeue( queue ) );
}

gdbこれで、ユニットテストをまたはで実行する巧妙なテストドライバーは、lldb両方のループ内に設定されたブレークポイントを待機し、デバッガーsi（ステップ命令）コマンドを使用して、2つのスレッドのすべての可能なインターリーブをシミュレートできるはずです。

私の質問は、これが技術的に可能かどうかではありません（可能です）。私が知りたいのはこれです：

enqueue()関数に10個の命令があり、関数に20個あると仮定するとdequeue()、テストではいくつの異なるインターリーブを試行する必要がありますか？

4

1 に答える 1

2

どれどれ...

それぞれに2つの命令しかない場合：a、bとA、B：

a、b、A、B
a、A、b、B
a、A、B、b
A、a、b、B
A、a、B、b
A、B、a、b

それは6です。

a、b、cおよびA、B、Cの場合：

a、b、c、A、B、C
a、b、A、c、B、C
a、b、A、B、c、C
a、b、A、B、C、c
a、A、b、 c、B、C
a、A、b、B、c、C
a、A、B、b、c、C
a、A、b、B、C、c
a、A、B、b、C、c
a 、A、B、C、b、c
A、a、b、c、B、C
A、a、b、B、c、C
A、a、B、b、c、C
A、B、a、b 、c、C
A、a、b、B、C、c
A、a、B、b、C、c
A、B、a、b、C、c
A、a、B、C、b、c
A、 B、a、C、b、c
A、B、C、a、b、c

私が何かを逃していない限り、それは20です。

それぞれをN個の命令（たとえば、Nは26）に一般化し、a ... zA ... Zで始めると、zには27個の可能な位置（Aの前からZの後まで）があり、最大で27個になります。 yの位置、xの最大28、wの最大29など。これは、最悪の場合、階乗を示唆します。ただし、実際にはそれよりも少ないですが、私は少し怠惰なので、正確な式を導出する代わりに、可能な「インターリーブ」の数を計算する単純なプログラムからの出力を使用します。

1 & 1 -> 2
2 & 2 -> 6
3 & 3 -> 20
4 & 4 -> 70
5 & 5 -> 252
6 & 6 -> 924
7 & 7 -> 3432
8 & 8 -> 12870
9 & 9 -> 48620
10 & 10 -> 184756
11 & 11 -> 705432
12 & 12 -> 2704156
13 & 13 -> 10400600
14 & 14 -> 40116600
15 & 15 -> 155117520
16 & 16 -> 601080390

したがって、これらの結果から、アイデアは正しいものの、コードの検証に使用するには不当な時間がかかると結論付けることができます。

また、命令の実行順序だけでなく、キューの状態も考慮する必要があることを覚えておく必要があります。これにより、反復回数が増加します。

編集：これがプログラムです（C）：

#include <stdio.h>

unsigned long long interleavings(unsigned remaining1, unsigned remaining2)
{
  switch (!!remaining1 * 2 + !!remaining2)
  {
  default: // remaining1 == 0 && remaining2 == 0
    return 0;

  case 1: // remaining1 == 0 && remaining2 != 0
  case 2: // remaining1 != 0 && remaining2 == 0
    return 1;

  case 3: // remaining1 != 0 && remaining2 != 0
    return interleavings(remaining1 - 1, remaining2) +
           interleavings(remaining1, remaining2 - 1);
  }
}

int main(void)
{
  unsigned i;
  for (i = 0; i <= 16; i++)
    printf("%3u items can interleave with %3u items %llu times\n",
           i, i, interleavings(i, i));
  return 0;
}

EDIT2：

ところで、代わりに擬似コードをシミュレートすると、デバッガーとのインターフェースやさまざまなコンテキストスイッチにより、オーバーヘッドを1桁（または2桁）節約することもできます。実装例については、多少関連する質問に対するこの回答を参照してください。これにより、直接実行よりもスレッド間の切り替えをよりきめ細かく制御できる場合もあります。

于 2013-03-22T09:46:43.937 に答える