[Threads] Solution 9 : Thread-safe Random Number Generator

This material is part of the course Practical Introduction to Parallel Programming and meant for educational purposes only.

Task

Implement a thread-safe pseudo random number generator using thread-local storage.

Each thread should generate at least ten million random numbers. Run your program with at least four threads.

Verify in a statistical way that all threads generate the same sequence of pseudo random numbers.

Here is a simple pseudo random number generator:

unsigned long  rand_state = 1;

int calc_random ()
{
  rand_state = rand_state * 1103515245 + 12345;

  return ((unsigned) (rand_state / 65536) % 32768);
}

Hints

The variable rand_state can not be a local variable; its value must be preserved between calls to the function calc_random.

Take a small number of samples (ten, say) to verity that all threads have generated the same sequence.

What happens when you do not use thread-local storage?

Paste this command into your terminal:

The password to connect is

Question 1: Thread-safe Random Number Generator

#include <stdio.h>
#include <assert.h>
#include <pthread.h>

/* ---------------------------------------------------------------------
 * constants
 * ------------------------------------------------------------------ */

#define                   NRANDOM     10000000
#define                   NSAMPLES    100
#define                   NTHREADS    4

/* ---------------------------------------------------------------------
 * global variables
 * ------------------------------------------------------------------ */

thread_local unsigned long  rand_state = 1;

/* ---------------------------------------------------------------------
 * calc_random()
 *
 *   Returns a pseudo random number.
 * ------------------------------------------------------------------ */

int                     calc_random ()
{
  rand_state = rand_state * 1103515245 + 12345;

  return ((unsigned) (rand_state / 65536) % 32768);
}

/* ---------------------------------------------------------------------
 * thread_func()
 *
 *   The thread entry point. This function generates a sequence of
 *   pseudo random numbers and returns a few samples from that
 *   sequence to its parent thread.
 * ------------------------------------------------------------------ */

void*                     thread_func

  ( void*                   arg )

{
  int*  samples  = (int*) arg;
  int   interval = NRANDOM / NSAMPLES;
  int   isample  = 0;
  int   i;

  assert ( samples );

  for ( i = 0; i < NRANDOM; i++ )
  {
    int  num = calc_random ();

    if ( ((i % interval) == 0) && (isample < NSAMPLES) )
    {
      samples[isample++] = num;
    }
  }

  return NULL;
}

/* ---------------------------------------------------------------------
 * main()
 * ------------------------------------------------------------------ */

int                       main

  ( int                     argc,
    char**                  argv )

{
  pthread_t  threads[NTHREADS];
  int        samples[NTHREADS * NSAMPLES];
  int        ierror;
  int        i, j;

  for ( i = 0; i < NTHREADS; i++ )
  {
    pthread_create ( &threads[i], NULL, thread_func,
                     &samples[i * NSAMPLES] );
  }

  for ( i = 0; i < NTHREADS; i++ )
  {
    pthread_join ( threads[i], NULL );
  }

  /* Check whether each thread has generated the same sequence of
   * pseudo random numbers. */

  ierror = 0;

  for ( i = 0; i < NSAMPLES; i++ )
  {
    int  ref = samples[i];

    for ( j = 1; j < NTHREADS; j++ )
    {
      if ( samples[i + j * NSAMPLES] != ref )
      {
        ierror++;
      }
    }
  }

  if ( ierror )
  {
    printf ( "ERROR: invalid results.\n" );
  }
  else
  {
    printf ( "Results are OK.\n" );
  }

  return ierror;
}

Question 2: Command Line Argument

Specify the command line arguments that should be passed to your program when it is run. Arguments must be given in quotes and separated by commas. Leave this filed empty if you do not want to specify command line arguments.

Example: "1","int","arg=2" is interpreted as three arguments 1, int, and arg=2.

Author(s)	Erik-Jan Lingen, Matthias Möller
Deadline	Keine Frist
Submission limit	No limitation

Information

Sign in