同时生成真正的随机整数？

Question

这个问题很简单，但我相信解决方案(如果存在)是相当复杂的。无论如何，我目前正在开发一个分布式应用程序，它应该实现简单的事务处理(打印、添加、睡眠、分配等)。通过使用线程来并行(我使用Pthread来完成这个任务)。不出所料，在尝试同时处理多个冲突事务(可能高达20个事务)时，我遇到了死锁问题。

现在，我已经决定为每个线程的事务处理实现多次重试，这些重试基本上是使用在该序列中调用的srand(time(NULL))和rand()随机生成的。问题是，当处理多个事务(在多达5个不同的服务器上)时，数字匹配，因为它们基本上是在同一秒内生成的。

所以，我的问题是，有没有一种方法可以完全随机生成整数，而不是使用time()函数，而是使用其他方法？

提前感谢您的帮助，并为(太)长的描述道歉。

Answer 1

要在不同的线程之间拥有独立的伪随机生成器PRG，您必须更加小心。基本上，您必须将生成器的状态保存在每个线程的单独变量中，并使用每个线程不同的东西来初始化每个状态一次。例如，使用时间和线程id进行初始化。

因为您是在POSIX系统上，所以您可以将jrand48作为生成器函数，但是任何允许您将状态作为参数传递的随机生成器都应该可以。

Answer 2

您不应该在每次调用rand()之前都调用srand()。这就是问题的根本原因。相反，您应该只调用srand()一次，在程序启动时，在创建线程之前。

此外，在POSIX上，rand()不一定是线程安全的，因此您应该使用互斥锁来序列化从不同线程对它的访问。

Answer 3

正如您所观察到的，当多个PRNG以相同的值作为种子时，使用PRNG计算退避和重试计时不起作用。如果冲突是破坏性的，则两个会话将使用相同的重试定时，并继续无限期地相互取消。

如果这只是在一台计算机上运行的一个任务多线程应用程序，那么您可以尝试使用线程If作为PRNG种子。

如果分布可以比单个任务更宽，那么您最终会遇到将所有唯一标识符组合成适合种子值大小的单个唯一标识符的问题。虽然独立线程的数量可能足够少，但可预测的唯一转换可能很困难。

也许作为每个线程启动的一部分，您应该连接到争用的资源并获取唯一的会话ID。如果您可以交错不同线程的启动，那么您就不必处理争用问题(只需在第一个线程确认获得其ID之前拒绝启动另一个线程)。如果这是不可能的(例如，在广泛分布的情况下)，你将不得不从其他随机来源计算重试时间，比如/dev/urandom。

但是，如果可以仅为其中一个n并发请求提供服务，则此问题可以自行解决。

在n并发请求中，一个客户端得到响应并继续，而n-1必须重试。失败的客户端将推进其PRNG状态，而其他客户端则不会。如果它们都有相同的PRNG状态，那么它们将再次竞争，但其中一个将通过，其他人将再次尝试。最终，所有人都将通过冲突(一个接一个)，并将拥有独特的PRNG状态。