Random function in multi-threaded c program

Question

PLease see the whole question

I know that srand() should be called only once, but my 2nd code segment shows that that does not solve the issue!!!!

The program I have written is giving me outputs which I can't quite make out why is it so. Different alterations of code segments give different outputs.

Objective of code:
The code uses omp to simply run a piece of code for 3 threads. Each thread has to print 3 random values using the rand() function. So, a total of 9 outputs would come. Thread 0 is the main thread/ the main program's run flow. Thread 1 and Thread 2 are the fellow new threads created at the start of code for the threads.
The code:

#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;
}

The output:

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

But if I make keep the srand(time(NULL)) before the code for thread like,

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

The output is, The output:

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

The Problem, and my doubts:

• By placing the `srand` outside, all the threads' 1st call to `rand()` gave the same random number, all of their 2nd call gave the same random number, and similarly for their 3rd call also.
• By placing the `srand` inside, the main thread's calls resulted in different random numbers than the others. BUT, the 2 new other threads among them gave the same random number for their respective calls to `rand()`.

So,

• What is actually happening here? How come the placement of the `srand()` function make a difference only to the main thread (thread `0`)?
• Why is it that either ways the the other 2 new threads always output same random number for the respective call to `rand()`?
• How is this `srand()` and `rand()` even linked, to cause this abnormality?
• And I tried giving wait intervals to each thread to remove that possibility of the `rand()` function being called by different threads at the same time, which might result in same random number maybe. But the problem was exactly like before. No change in the output (just the time at which output occurred was different).

Please help me understand this whole thing..

Answer 1

Updated: Inserted direct answers to the OP's enumerated questions.

What is actually happening here?

Although some versions of the rand() function may be "thread safe" in some sense, there is no reason to believe or expect that without any external memory synchronization, the set of values returned by multiple rand() calls executed by different threads will be the same as the set of values returned by the same number of calls all executed by one thread. In particular, rand() maintains internal state that is modified on each call, and without any memory synchronization, it is entirely plausible that one thread will not see updates to that internal state that are performed by other threads. In that case, two or more threads may generate partially or wholly the same sequence of numbers.

How come the placement of the srand() function make a difference only to the main thread (thread 0)?

The only thing that can be said for certain is that if the srand() is outside the parallel block then it is executed only by the main thread, whereas if it is inside then it is executed separately by each thread. Inasmuch as your code is not properly synchronized, the effects of each case are not predictable from the source code, so my next comments are mostly speculative.

Supposing that time(), with its (only) one-second precision, returns the same value in each thread, placing srand() inside the parallel region ensures that every thread sees the same initial random number seed. If they then do not see each other's updates then they will generate the same sequences of pseudo-random numbers. Note, however, that you can neither safely rely on the threads seeing each other's updates nor safely rely on them not seeing each others updates.

If you put the srand() outside the parallel region, however, so that it is executed only by the main thread, then there are additional possibilities. If OMP maintains a thread pool whose members are already started before you enter the parallel section, then it may be that threads 1 and 2 fail to see the effect of thread 0's srand() call at all, and therefore both proceed with the default seed. There are other possibilities.

Why is it that either ways the the other 2 new threads always output same random number for the respective call to rand()?

It's impossible to say with any certainty. I'm inclined to guess, however, that none of the threads involved see each other's updates to rand()'s internal state.

How is this srand() and rand() even linked, to cause this abnormality?

The two functions are intimately linked. The purpose of srand() is to modify rand()'s internal state (to "seed" it, hence the "s" in "srand"), so as to start the psuedo-random number sequence it generates at a different (but still deterministic) point.

---

This problem can be solved in the same way that any problem involving multi-threaded access to shared variables can be solved: by applying synchronization. In this case, the most straightforward form of synchronization would probably be to protect rand() calls with a mutex. Since this is OMP code, your best bet might be to use OMP locks to implement a mutex, as it seems dicey to mix explicit pthreads objects with OMP declarations.

Answer 2

Random number generators are actually not so random. They take some internal state (the "seed"), deterministically extract an integer from that state, and deterministically mutate the state so that it will be different on the next call.

Normally, the computations involve are complex bit manipulations intended to guarantee that the sequence of outputs "looks" random, is well-distributed over the possible range, and satisfies other requirements. But at base, it is a deterministic function on a global internal state. Without the complicated computations, it would not be much different from this:

# File: not_so_random.c
static unsigned seed = 1;
void srand(unsigned newseed) { seed = newseed; }
int  rand(void)              { return seed++; }

([Note 1])

It's pretty easy to see how that would produce a race condition if it were executed in parallel threads.

You could make this "kind of" multithread safe by making seed atomic. Even if the mutation were more complicated than an atomic increment, making access atomic would ensure that the next seed was the result of the mutation made by some call to rand. Still, a race condition is possible: two threads could both pick up the seed at the same time, and then they would receive the same random number. Other odd behaviours are also possible, including the one where a thread gets the same random number twice, or even an earlier one. And particularly odd behaviours are possible if srand is being called simultaneously with rand, since that is always a race condition.

On the other hand, you could protect all calls to rand and srand with a mutex, which would avoid all race conditions as long as srand is called before threading starts. (Otherwise, any call to srand in one thread will reset the random number sequence in every other thread.) However, if multiple threads are simultaneously consuming lots of random numbers, you'll see a lot of mutex contention and possibly synchronization artefacts. [Note 2].

In a multiprocessing world, library functions which depend on global state are not so great, and many of the old interfaces have multithread-safe alternatives. Posix requires rand_r, which is similar to rand except that it expects as an argument the address of a seed variable. With this interface, each thread can simply use its own seed, and the threads will effectively have independent random number generators. [Note 3]

Of course, these seeds have to be initialized in some way, and it would obviously be counterproductive to initialize them all to the same value, since that would result in each thread getting the same random number sequence.

In this sample code, I used the system /dev/urandom device to provide a few seed bytes for each thread. /dev/urandom is implemented by the operating system (or, at least, by many OSs); it produces a highly-random stream of bytes. Usually, the randomness of this stream is reinforced by mixing in random events, like the timing of keyboard interrupts. It's a moderately expensive way to generate a random number, but it will generate quite a good random number. So that's perfect for producing random seeds for each thread: I want the seeds to be random, and I'm not going to need very many of them. [Note 4]

So here's one possible implementation:

#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;
}

Notes:

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.

Answer 3

The reason is that time() has seconds precision, so each thread is calling srand() with the same seed leading to the same pseudo random number sequence.

Just call srand() once at the begining of the program and not in each thread, that would make every run of the program generate 3 different sequences one for every thread.

Answer 4

It looks like, on your platform, rand() is thread safe because each thread gets its own PRNG that is seeded when the thread is created. You could get this platform to do what you want by first generating a seed for each thread and then having each thread call srand with its seed before it calls rand. But that might break on other platforms with different behavior, so you just shouldn't use rand.