1

我想知道使用调试器自动测试竞争条件是否可行。

例如，要测试多线程队列的映像。除其他外，您还想测试是否可以同时调用enqueue()和dequeue()。

一个简单的单元测试可以启动两个线程，每个线程分别在一个循环中调用和检查结果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 ) );
}

现在，一个聪明的测试驱动程序，在gdbor中运行单元测试lldb，应该能够等待在两个循环中设置的断点，然后使用调试器si（步进指令）命令来模拟两个线程的所有可能的交错。

我的问题不是这在技术上是否可行（确实如此）。我想知道的是：

假设enqueue()函数有 10 条指令，而dequeue()函数有 20 条 - 测试必须尝试多少种不同的交织？

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;
}

编辑2：

顺便说一句，如果您改为模拟伪代码，由于与调试器的接口以及各种上下文切换，您还可以节省一个数量级（或两个）的开销。请参阅this answer to a some related question以获取示例实现。与直接执行相比，这也可以让您对线程之间的切换进行更细粒度的控制。

于 2013-03-22T09:46:43.937 回答