用于单元测试预期和非预期死锁行为的明智策略
我想要一些关于如何测试一些可以阻塞、等待另一个参与者的对象的想法。要测试的特定单元是参与者之间的通道，参与者本身是用于测试目的的模拟装置。
如果能够验证参与者是否在预期时发生了死锁，那就太好了，但这对我来说并不是非常重要，因为死锁之后发生的事情可以合理地描述为未定义。
更重要的是验证参与者定义的交互不会出现死锁。
无论哪种情况，我都不确定最佳的测试策略应该是什么。我当前的想法是让测试运行程序为每个参与者触发一个线程，休眠一段时间，然后发现子线程是否已返回。如果它们没有及时返回，则假设它们已经死锁，并安全地终止线程，并且测试失败（或者如果死锁是预期的，则测试成功）。
这感觉有点概率性，因为可能有各种各样的原因（尽管不太可能）导致线程可能需要比预期更长的时间才能完成。还有其他好的方法来解决这个问题吗？
编辑：我确信测试的健全性会很好，但我认为我不需要它。我正在考虑三个级别的测试确定性。
- “实际行为已证明与预期行为相符” 不会发生死锁 “
- 实际行为与预期行为相符” 在 N 次测试中未发生死锁 “
- 实际行为与预期行为一致” 在预期期限内完成了 N 次测试
第一个当然，这是一个很有价值的测试，但 ShiDoiSi 的回答说明了这一点的不切实际。第二个明显弱于第一个，但仍然很难；如何确定进程网络实际上已经陷入僵局？我不确定这比第一个更容易证明（也许更难）
最后一个更像是我的想法。
I'd like some ideas about how I should test some objects that can block, waiting for another participant. The specific unit to be tested is the channel between the participants, The the participants themselves are mock fixtures for the purposes of the tests.
It would be nice to validate that the participants do deadlock when they are expected to, but this is not terribly important to me, since what happens after the deadlock can reasonably be described as undefined.
More critical would be to verify that the defined interactions from the participants do not deadlock.
In either case, I'm not really sure what the optimal testing strategy should be. My current notion is to have the test runner fire off a thread for each participant, sleep for a while, then discover if the child threads have returned. In the case they have not returned in time, assume that they have deadlocked, and safely terminate the threads, and the test fails (or succeeds if the deadlock was expected).
This feels a bit probabalistic, since there could be all sorts of reasons (however unlikely) that a thread might take longer than expected to complete. Are there any other, good ways of approaching this problem?
EDIT: I'm sure a soundness in testing would be nice, but I don't think I need to have it. I'm thinking in terms of three levels of testing certainty.
- "The actual behavior has proven to match the expected behavior" deadlock cannot occur
- "The actual behavior matched the expected behavior" deadlock did not occur in N tests
- "The actual behavior agrees with the expected behavior" N tests completed within expected deadline
The first of course is a valuable test to pass, but ShiDoiSi's answer speaks to the impracticality of that. The second one is significantly weaker than the first, but still hard; How can you establish that a network of processes has actually deadlocked? I'm not sure that's any easier to prove than the first (maybe a lot harder)
The last one is more like what I have in mind.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
可靠测试死锁的唯一方法是对锁定子系统进行检测并报告死锁。上次我不得不这样做时，我们构建了它的调试版本，记录哪些线程持有哪些锁，并检查每个锁获取调用是否存在潜在的死锁。在存在大量锁定的系统中，这可能是一项重量级操作，但我们发现它非常有价值，因此我们重新组织了子系统，以便我们可以在运行时通过开关打开和关闭它，即使在生产版本中也是如此。
The only way to reliably test for deadlocks is to instrument the locking subsystem to detect and report them. The last time I had to do this, we built a debug version of it that recorded which threads held which locks and checked for potential deadlocks on every lock-obtain call. It can be a heavyweight operation in a system with a lot of locking going on, but we found it to be so valuable that we reorganized the subsystem so we could turn it on and off with a switch at runtime, even in production builds.
学术界可能会告诉你（事实上它现在就在告诉你；）你应该对一些所谓的模型检查框架进行忠实的抽象（CSP，pi 演算）。然后，这将模拟抽象执行（详尽搜索所有可能的调度程序交错）。当然，诀窍是确保抽象实际上是忠实的。您不再检查程序的实际源代码，而是检查其他语言的源代码。
否则，一些严厉的方法，比如使用 Java Path Finder/Explorer （它做了一些事情非常相似），因为我想到了特定的语言。
C 语言、Intel 和 其他公司也使用专门的工具从事这项业务。
您正在研究计算机科学研究的热门话题之一，对于非平凡/真实的系统，详尽的测试和形式验证都不容易适用于真实的代码。
一种有价值的方法可能是检测您的代码，以便它能够真正检测到死锁，并可能尝试恢复。为了检测死锁，FreeBSD 内核 使用一组 C 宏来跟踪锁的使用情况和 通过报告潜在违规行为 a href="http://www.FreeBSD.org/cgi/man.cgi?query=witness&sektion=4" rel="nofollow">
见证(4)机制。但同样，很少发生的错误也很少会被发现。（免责声明：我没有参与上面链接的任何商业工具——我添加它们只是为了让您感受到您所面临的问题的难度。）
The academic community will probably tell you (in fact it IS telling you right now ;) that you should do a faithful abstraction into some so-called model checking-framework (CSP, pi-calculus). That would then simulate abstract executions (exhaustive search through all possible scheduler interleavings). Of course the trick is to make sure that the abstraction IS actually faithful. You are no longer checking the actual source of your program, but the source in some other language.
Otherwise, some heavy-handed approach like using Java Path Finder/Explorer (which does something very similar) for the particular language comes to mind.
Similar research prototypes exist for C, and Intel and other companies are also in this business with specialised tools.
You are looking at one of the hot topics in Computer Science research, and for non-trivial/real systems, neither exhaustive testing nor formal verification are easily applicable to real code.
A valuable approach could be to instrument your code so that it will actually detect a deadlock, and potentially try to recover. For detecting deadlocks, the FreeBSD kernel uses a set of C-macros that track lock usage and report potential violations through the
witness(4)mechanism. But again, errors that only occur rarely, will only be rarely spotted.(Disclaimer: I'm not involved in any of the commercially tools linked above---I just added them to give you a feeling for the difficulty of the problem you are facing.)
为了测试是否存在死锁，您可以使用 NUnit 的 TimeoutAttribute 的等效项，如果执行时间超过上限，该属性将中止测试并使测试失败。您可以想出一个好的超时值，例如，如果测试没有在 30 秒内完成，则表示出现了问题。
我不确定（或者我没有遇到过这种情况）是否断言发生了死锁。死锁通常是不受欢迎的。我对如何编写一个失败的单元测试感到困惑，除非测试块 - 单元测试通常应该是快速且非阻塞的。
For testing if there is no deadlock, you could use the equivalent of NUnit's TimeoutAttribute, which aborts and fails a test if execution time exceeds an upper limit. You could come *up with a good timeout value e.g if the test doesn't complete within 30s - something is wrong.
I'm not sure (or I haven't come across a situation) about asserting that a deadlock has occurred. Deadlocks are usually undesirable. I'm stumped on how to write a unit test that fails unless the test blocks - unit tests are usually supposed to be fast and non-blocking.
既然您已经完成了足够的抽象来模拟参与者，为什么不进一步抽象出线程同步（互斥体、信号量等）呢？
当您考虑什么构成死锁时，您可以在测试中使用专门的死锁感知线程同步器。通过“死锁感知”，我并不是说它应该通过使用超时等方式以暴力方式检测死锁，而是通过标志、计数器等方式了解导致死锁的情况。它可以检测死锁，同时可选地提供预期的线程同步功能。我基本上想说的是，使用仪器化的线程同步进行测试......
这太抽象了，说起来容易做起来难。我并不声称自己已经成功地做到了这一点。我可能只是在这里犯傻了。但也许如果您只能提供一个（不完整的）测试，那么问题就可以用更具体的方式来解决。
Since you've already done enough abstraction to mock out the participants, why not take it further and abstract out your thread synchronization (mutex, semaphore, whatnot)?
When you think about what constitutes a deadlock, you could use a specialized, deadlock-aware thread synchronizer in your tests. By "deadlock-aware", I don't mean that it should detect deadlocks the brute-force way by using timeouts etc., but have awareness of the situations that lead to deadlocks by way of flags, counters etc. It could detect deadlocks, while optionally providing the expected thread synchronization functionality. What I'm basically saying is, use instrumented thread synchronization for your tests...
This is all too abstract and easier said than done. And I don't claim to have successfully done it. I might simply be being silly here. But perhaps if you could provide just one (incomplete) test, the problem can be attacked in more concrete terms.