algorithm - 在并发队列中检测循环

Question

我有一个并发的连接队列有一个ping任务，它周期性地遍历队列中的所有可用连接以执行ping，同时应用程序可以请求队列中的连接以供使用。
什么是检测循环以便ping任务能够完成其当前执行的好方法？
编辑：
示例：假设并发队列有连接A、B和C。
有一个ping任务遍历队列。因此在这个例子中，它将执行A.ping()、B.ping()和C.ping()。现在有一个外部类，当ping任务也在队列上迭代时，它也从队列请求连接。因此，假设a.ping（）已完成，externalClass.getConnection()将返回A。当ping任务完成C.ping（）时，externalClass.releaseConnection(A)发生现在队列的顺序是B,C and A所以ping任务在完成C.ping（）之后将再次找到A，此时任务必须确定A已经被ping过，并且应该完成当前的执行。

Answer 1

首先，你没有一个循环。
循环是指当有一个指向自身的链接列表时。您只需要有一个队列，当您单步执行时，它可能会有另一个线程在队列的末尾添加重复的元素。
检测循环循环的方法是使用hashtable，在每个Ping()之前，检查连接中是否存在连接，如果它确实存在，那么您只需移动到下一个元素，如果不存在，则将其添加到hashtable，然后调用您的Ping操作到服务器。
或者您可以让您的初始ping操作在该准确时间制作队列的快照，而不是跳过它。
尽管如此，如果您可以让两个不同的调用者从队列中得到相同的A结果，那么您的队列就出现了问题。
正确的方法是有两个单独的列表，一个是externalClass.getConnection()请求的连接队列，另一个是Ping的连接列表不管您的Ping操作在做什么，它确实不应该影响任何外部类使用它的连接所做的任何事情，例如假设connection是一个sql connection然后Ping应该执行如下操作：

SELECT TOP 1 1

再也没有了，那就意味着你的关系还活着。因为连接空闲时间太长，并且关闭了自己，所以您很可能实现了这一点。在这种情况下，您真的不应该这样做，因为几乎任何类型的sql dbms都支持连接池，而连接池正是您所要做的。除非您想阻止超过个队列，否则通过让其他执行等待一次计算并发连接数（这本身可以通过保持一个开放连接池的方式做得更好，例如简单的int counter）
除非您保持到不同服务器的连接，并尝试通过在多个服务器之间轮换请求来进行一些临时负载平衡，否则请使用上面的解决方案，其中包含所有连接的列表和可用连接的队列。此解决方案的主要好处是，即使应用程序当前正在处理请求，也可以在应用程序关闭时终止所有连接。
但是，为了完整地回答你的问题：
如果您确实有一个循环，那么它将如下所示：A -> B -> C -> A其中每个元素都指向列表中的下一个元素，而不仅仅是aqueue中的元素。一个很好的例子是ping serverA哪个ping serverB哪个ping serverC哪个ping serverA然后ping.Ping()然后检测如下：
检测循环的简单方法是一次运行两个（或多个）迭代，我们称之为x和y。
每跳一次（或上下文中的Visit）x，就跳一次y。您可能希望创建一个新方法，例如Ping，而不是调用您的A, B, C, A, B...，以便在循环中不会多次调用ping。
假设队列看起来A, B, C, A
几步后x看起来像：A, B而y看起来像Z。你要做的是不存储整个历史，只查看当前值，所以当你进入x时，你要检查新值是否与y的当前值匹配，这样我们最终总会发生冲突。
这不是检测循环循环循环的最快或最有效的方法，但它是最简单的，如果循环通常很小，则比存储过去路由的历史列表更容易（在某些情况下，这需要对代码进行重大更改）。当循环长度超过20步时，可以使用效率更高的算法（它们设计用于处理复杂的分支树等）。必须认识到，这种实现的最坏情况是循环元素的质数。
但是，您可以通过进一步扩展它来获得一个X迭代器来提高平均性能，该迭代器每三个X步骤执行一次，此时，不值得再添加一个每5个步骤或7个步骤执行一次的迭代器，以此类推（在创建每个新迭代器时访问下一个递增质数）。