在多线程c程序中的随机函数

7

请看完整问题

我知道srand()应该只调用一次,但我的第二个代码段显示这并不能解决问题!!!

我编写的程序给我输出,我无法理解为什么会这样。不同的代码段变化会产生不同的输出。

代码目标:
该代码使用omp简单地运行一个3个线程的代码片段。每个线程都必须使用rand()函数打印3个随机值。因此,总共会有9个输出。线程0是主线程/主程序的运行流程。线程1和线程2是在代码开始时为线程创建的新线程。
代码:

#include<omp.h>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int main()
{


     #pragma omp parallel num_threads(3)
    {
        srand(time(NULL));
        int i=0;
        for(i=0;i<3;i++)
        {
            printf("\nRandom number: %d by thread %d", rand(), omp_get_thread_num());
        }
    }

    return 0;
}


输出结果:

Random number: 17105 by thread 0
Random number: 30076 by thread 0
Random number: 21481 by thread 0
Random number: 17105 by thread 1
Random number: 30076 by thread 1
Random number: 21481 by thread 1
Random number: 17105 by thread 2
Random number: 30076 by thread 2
Random number: 21481 by thread 2

但如果我把srand(time(NULL))放在线程代码之前,像这样:

 srand(time(NULL));  
 #pragma omp parallel num_threads(3)
{
    int i=0;
    ......
    ......(rest is same)

输出结果为:输出结果:
Random number: 16582 by thread 0
Random number: 14267 by thread 0
Random number: 14030 by thread 0
Random number: 41 by thread 1
Random number: 18467 by thread 1
Random number: 6334 by thread 1
Random number: 41 by thread 2
Random number: 18467 by thread 2
Random number: 6334 by thread 2

问题和我的疑惑:
将`srand`放在外面后,所有线程的第一次调用`rand()`都会得到相同的随机数,它们的第二次调用也会得到相同的随机数,对于第三次调用也是如此。
将`srand`放在内部后,主线程的调用结果与其他线程不同。但是,其中的两个新线程在它们各自调用`rand()`时得到了相同的随机数。
那么,
这里实际上正在发生什么?为什么仅对主线程(线程0)放置`srand()`函数会有影响?
为什么无论哪种方式,其他2个新线程总是输出相同的随机数?
`srand()`和`rand()`是如何关联起来导致这种异常?
我尝试给每个线程提供等待间隔,以消除`rand()`函数被不同线程同时调用可能导致相同的随机数的可能性,但问题与之前完全相同。输出没有变化(只是输出发生的时间不同)。
请帮助我理解整个过程。

srand()移到代码块外部。程序启动时只应调用一次。 - Iharob Al Asimi
第二段代码展示了这一点。它并没有产生太大的差异,但却通过使主线程显示不同的值来显示另一个异常。 - powersource97
2
我会说这是一种RTFM情况:手册明确说明rand()不是线程安全的,并提供了一种替代方案。 - Ulrich Eckhardt
@UlrichEckhardt 它是线程安全的,但它不是可重入的。但实际上,OP似乎想利用其不可重入性。 - Iharob Al Asimi
1
@iharob,它明确指出>>函数rand()不是可重入的,因为它使用了隐藏的状态,在每次调用时都会被修改。这可能只是下一次调用要使用的种子值,也可能是更复杂的东西。为了在线程应用程序中获得可重现的行为,必须显式地表示此状态;可以使用可重入函数rand_r()来实现这一点。因此,rand()不是线程安全的,需要使用rand_r(),但这是UNIX特定的。 - powersource97
显示剩余3条评论
4个回答

7
更新:插入了对原帖中列举问题的直接回答。

这里到底发生了什么?

虽然某些版本的 rand() 函数在某种程度上可能是“线程安全”的,但没有理由相信或期望,在没有任何外部内存同步的情况下,由不同线程执行的多个 rand() 调用返回的值集合将与同一线程执行的相同数量的调用返回的值集合相同。特别地,rand() 保持内部状态,该状态在每次调用时被修改,如果没有任何内存同步,则完全有可能一个线程将看不到其他线程执行的对该内部状态进行的更新。在这种情况下,两个或多个线程可能生成部分或完全相同的数字序列。

为什么只有主线程(线程 0)的 srand() 函数的放置位置会产生差异?

唯一可以确定的是,如果 srand() 在并行块之外,则仅由主线程执行,而如果在其中,则由每个线程单独执行。由于您的代码未经过适当同步,因此无法从源代码预测每种情况的影响,因此我接下来的评论大多是推测性的。

假设 time() 具有(唯一的)一秒精度,在并行区域内放置 srand() 确保每个线程看到相同的初始随机数种子。然后,如果它们不看到彼此的更新,则它们将生成相同的伪随机数序列。但是请注意,您既不能安全地依赖于线程看到彼此的更新,也不能安全地依赖于它们不看到彼此的更新。

然而,如果将 srand() 放在并行区域之外,以便仅由主线程执行,则存在其他可能性。如果 OMP 维护一个线程池,其成员在进入并行部分之前已经启动,则可能是线程 1 和 2 完全看不到线程 0 的 srand() 调用的效果,因此两者都使用默认种子继续进行。还有其他可能性。

为什么无论哪种方式,另外两个新线程总是输出相应调用 rand() 的相同随机数?

无法确定。但我倾向于猜测,涉及的所有线程都没有看到对 rand() 的内部状态的更新。

为什么这个 srand()rand() 会导致这种异常?

这两个函数密切相关。 srand() 的目的是修改 rand() 的内部状态(即“种子”它,因此 “srand” 中的 “s”),以便在不同(但仍然是确定性的)点开始生成伪随机数序列。


这个问题可以通过应用同步解决,就像解决涉及多线程访问共享变量的任何问题一样。在这种情况下,最直接的同步形式可能是用互斥锁来保护 rand() 调用。由于这是 OMP 代码,您最好使用 OMP 锁来实现互斥锁,因为混合明确的 pthreads 对象和 OMP 声明似乎有风险。


说得非常好。非常感谢!我查看了文档,即使它们声称rand()修改了内部状态,因此它不是线程安全的。现在我更好地理解了。为了解决这个问题,我添加了线程ID和time()到每个种子生成中。但实际上我想要理解这种行为,现在我终于明白了!我完全忘记了使用mutex进行同步... - powersource97

4
随机数生成器实际上并不是那么随机。它们采用一些内部状态(“种子”),从该状态中确定性地提取一个整数,并确定性地改变该状态,以便在下一次调用时它将不同。
通常,所涉及的计算包括复杂的位操作,旨在保证输出序列“看起来”随机,分布在可能范围内,并满足其他要求。但基本上,它是一个全局内部状态上的确定性函数。如果没有复杂的计算,它与以下内容并没有太大区别:
# File: not_so_random.c
static unsigned seed = 1;
void srand(unsigned newseed) { seed = newseed; }
int  rand(void)              { return seed++; }

([注意 1])

很容易看出,如果在并行线程中执行,这将产生竞争条件。

您可以通过使seed原子化来使其“有点”多线程安全。即使突变比原子递增更复杂,使访问原子化也将确保下一个种子是由某个 rand调用所做的突变的结果。但仍然可能存在竞争条件:两个线程可能同时拾取种子,然后它们将接收相同的随机数。其他奇怪的行为也可能发生,包括一个线程两次获得相同的随机数,甚至是先前的随机数。如果同时调用srandrand,则可能出现特别奇怪的行为,因为这总是一种竞争条件。

另一方面,您可以使用互斥锁保护对randsrand的所有调用,只要在线程启动之前调用srand即可避免所有竞争条件。(否则,一个线程中对srand的任何调用都会重置其他每个线程中的随机数序列。)但是,如果多个线程同时消耗大量随机数,则会看到很多互斥锁争用和可能的同步问题。[注2]。
在多处理器世界中,依赖全局状态的库函数并不是很好,许多旧接口都有多线程安全的替代品。Posix需要rand_r,它类似于rand,但它期望作为参数传递种子变量的地址。使用此接口,每个线程可以简单地使用自己的种子,线程将有效地拥有独立的随机数生成器。[注3]
当然,这些种子必须以某种方式初始化,显然将它们全部初始化为相同的值是不可取的,因为这将导致每个线程获得相同的随机数序列。
在这个示例代码中,我使用了系统/dev/urandom设备为每个线程提供几个种子字节。 /dev/urandom由操作系统实现(或者至少被许多操作系统),它产生高度随机的字节流。通常,此流的随机性通过混合随机事件来增强,例如键盘中断的时间。这是一种相对昂贵的生成随机数的方式,但它将生成相当好的随机数。因此,这非常适合为每个线程生成随机种子:我希望种子是随机的,并且我不需要太多种子。【注4】

因此,这里有一个可能的实现:

#define _XOPEN_SOURCE
#include<omp.h>
#include<stdio.h>
#include<stdlib.h>
// This needs to be the maximum number of threads.
// I presume there is a way to find the correct value.
#define THREAD_COUNT 3
// Hand-built alternative to thread-local storage
unsigned int seed[THREAD_COUNT];

int main() {
  FILE* r = fopen("/dev/urandom", "r");
  if (fread(seed, sizeof seed, 1, r) != 1) exit(1);
  fclose(r);

#pragma omp parallel num_threads(3)
  {
    // Get the address of this thread's RNG seed.
    int* seedp = &seed[omp_get_thread_num()];
    int i=0;
    for(i=0;i<3;i++) {
      printf("Random number: %d by thread %d\n",
             rand_r(seedp), omp_get_thread_num());
    }
  }

  return 0;
}

注释:

  1. While that example is roughly as random as the famous xkcd on the subject, the following is an example of a rand implementation taken (with minor edits) straight from the C standard (§7.22.2 para.5), which is judged to be a "sufficiently-random" implementation of rand. The similarity with my example is evident.

    /* RAND_MAX assumed to be 32767. */
    static unsigned long next = 1;
    int rand(void) {
        next = next * 1103515245 + 12345;
        return((unsigned)(next/65536) % 32768);
    }
    
    void srand(unsigned seed) { next = seed; }
    
  2. Neither the C standard nor Posix requires rand to be thread-safe, but it is not prohibited either. The Gnu implementation of the standard C library mutex protects rand() and srand(). But obviously that is not the rand implementation being used by OP, because glibc's rand() produces much larger random numbers.

  3. If your system does not have rand_r, you could use a simple modification of the sample code from Note 1 above:

    int rand_r(unsigned *seedp) {
        *seedp = *seedp * 1103515245 + 12345;
        return((unsigned)(*seedp/65536) % 32768);
    }
    
  4. If your OS does not provide /dev/urandom, then it is quite possible that your OS is Windows, in which case you can use rand_s to generate the one-time seed.


非常感谢您的帮助。内部状态修改正在破坏它。感谢您指出过多使用互斥锁的问题,当计算许多数字时以及原子化rand的问题。此外,dev \(u)random也是一个非常酷的方法。非常感谢您告诉我这个方法。 - powersource97

2
原因是time()只有秒级精度,因此每个线程都使用相同的种子调用srand(),导致生成相同的伪随机数序列。
只需在程序开头调用一次srand()而不是在每个线程中调用,这将使每次运行程序生成3个不同的序列,每个线程一个。

第二段代码也展示了这一部分。它仍然表现不正常!! - powersource97
当您调用srand()一次时,我期望会生成一个伪随机数序列,每次调用rand()都会更改内部静态状态数据并为每个调用生成一个新数字,无论哪个线程调用它。 - Iharob Al Asimi
1
@iharob,我的Linux手册页中明确指出,“函数rand()不是可重入或线程安全的”(已加粗)。 - John Bollinger
请阅读这里,我认为MT-Safe表示线程安全 - Iharob Al Asimi
1
@iharob,那是与我的手册页面不同的版本。即使你解释它声称rand()的文档版本是线程安全的 - 这似乎是合理的 - 但必须解释文档的另一个版本中明确矛盾的文档存在会削弱rand()是线程安全的一般声明。无论如何,OP的实现显然不是线程安全的。 - John Bollinger
显示剩余8条评论

1
在您的平台上,rand()是线程安全的,因为每个线程都有自己的PRNG,在创建线程时进行了种子处理。您可以通过为每个线程生成一个种子,然后让每个线程在调用rand之前使用其种子调用srand来使此平台按照您的要求运行。但这可能会在其他具有不同行为的平台上出现问题,因此您不应该使用rand

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接