模拟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，应该能够等待两个循环内设置的断点，然后使用调试器si（分步指令）命令来模拟两个线程的所有可能的交错。

我的问题是，如果这在技术上是可能的（它是）。我想知道的是：

假设enqueue()函数有10条指令，而dequeue()函数有20条 - 测试需要尝试多少次不同的交错？

Answer 1

让我们来看看...

如果我们只在每个2说明：A，B和A，B：

A，B，A，B
A，A，B，B
一个，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，b，C，b，C
一个，A，b，b，C，C
一个，A ，b，b，C，C
一个，A，b，b，C，C
一个，A，b，b，C，C
一个，A，b，C，b，C
甲，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，一个，b，c

那是20，除非我错过了一些东西。

如果我们将它推广到N个指令（比如N是26），并且每个指令都以... zA开始...Z，那么z（从A之前到Z之后）将有27个可能的位置，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; 
} 

EDIT2：

顺便说一句，你还可以在架空的幅度（或两个）的顺序保存由于接口与调试器，并由于各种上下文切换，如果你模拟伪代码。有关示例实现，请参阅this answer to a somewhat related question。这也可以让你更直观地控制线程之间的切换，而不是直接执行。