multithreading - 用 gdb/lldb 模拟竞争条件是否可行？

Question

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

比如想象你要测试一个多线程队列。除其他外，您可能希望测试是否可以同时调用 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 ) );
}

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

我的问题不是这在技术上是否可行(是)。我想知道的是:

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

Answer 1

让我们看看...

如果每个指令只有 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 之后)，y 最多 27 个位置，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;
}

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