如何最好地测试Mutex实现？

Question

如何最好地测试互斥锁的实现是否正确？（需要实现互斥锁，重用不可行）

我想到的最好方法是使用许多（N）并发线程迭代地尝试访问受保护的区域（I）次，这会产生副作用（例如更新全局变量），以便可以计算访问和写入次数，以确保对全局变量的更新次数正好为（N）*（I）。

还有其他建议吗？

- grrussel

---

测试互斥锁（和类似的结构）非常困难。我很想知道为什么您不能使用现有的、经过测试和证明的解决方案。 - anon

Answer 1

正式的证明比测试更适合这种情况。测试只能告诉你 -- 只要你不太倒霉 -- 它都可以工作。但是，测试是一种粗糙的工具；它可能无法执行确切的操作序列来引起故障。在硬件中测试每个可能的操作序列太困难了，以确保您的互斥锁在所有情况下都起作用。测试并非没有价值；它表明您没有犯任何明显的编码错误。但是，您真的需要进行更正式的代码检查，以证明它在正确的时间做正确的事情，以便一个客户端原子性地占用所需的锁资源，以实现正确的互斥锁。在许多平台上，有特殊的指令来实现这一点，如果您正在使用其中之一，则有机会做到正确。同样，您必须证明发布是原子性的。

- S.Lott

Answer 2

使用类似于互斥锁的东西，我们回到了一个古老的规则：测试只能证明错误的存在，而不能证明不存在。一年的测试可能比仅仅将代码提交检查并询问是否有人看到问题要少。

- Jerry Coffin

Answer 3

我和其他人一样，认为这很难被证明，我不知道该怎么做 - 我知道这并没有帮助!

当你说要实现互斥锁并且重用不是一个选项时，是因为技术原因，例如在你使用的平台/操作系统上没有互斥锁实现或者其他原因吗？是否可以包装某种形式的操作系统级别“锁”并将其称为互斥锁实现，例如 Windows 上的 CriticalSection，posix 条件变量？如果您可以包装一个更低级别的操作系统锁定，那么您正确的机会就会大得多。

如果您还没有这样做，请阅读Herb Sutter 的有效并发文章。这些文章中应该有一些对您有用的东西。

无论如何，在测试时需要考虑以下几点：

• 如果您的互斥锁是递归的（即同一线程可以多次锁定它），则确保进行一些参考计数测试。
• 对于您修改的全局变量，最好使用不能原子写入的变量。例如，如果您在 8 位平台上，则使用需要多个汇编指令才能写入的 16 或 32 位变量。
• 仔细检查汇编清单。根据硬件平台的不同，汇编并不能直接转换为代码可能被优化的方式...
• 让其他人（没有编写代码的人）编写一些测试。
• 在尽可能多的具有不同规格的计算机上进行测试（假设这是“通用”的，而不是针对特定的硬件设置）

祝你好运！

- Michael

---

关于写入值的大小，这是一个很好的观点。我的主要问题是要检查使用的处理器操作组合（通过编译器内置函数访问）在理论上和逻辑上是否正确（算法上是否正确），以及在实践中是否正确（编译后的实现是否忠实于逻辑上正确的算法）。 - grrussel

Answer 4

这让我想起了FIFO信号量测试的问题。简而言之，我的答案是：

• 即使你有规范，也可能无法准确传达你的意图
• 你可以证明算法符合规范，但不能证明代码(D. Knuth)
• 测试只能揭示错误的存在，而不能证明其不存在(Dijkstra)

因此，您的建议似乎是最好的选择。如果您想增加信心，请使用fuzzing来随机调度和输入。

- ewernli

Answer 5

如果证明的方法对你来说行不通，那就走测试的路线。一定要测试所有可能的用例。弄清楚这个东西将如何被使用，谁将使用它，同时也要知道它将如何被使用。当你选择测试的方式时，一定要为每个场景运行每个测试很多次（数以百万计、十亿计，尽可能多地利用你所拥有的测试时间）。

尽量随机进行测试，因为随机性将给你在有限数量的测试中覆盖所有情况的最佳机会。确保使用将被使用的数据和可能不被使用但可能被使用的数据，并确保数据不会破坏锁。

顺便说一句，除非你对数学和形式化方法非常了解，否则你根本没有机会真正提出一个证明。

- Brian T Hannan