[Threads] Solution 6 : Barrier

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

Task

Implement a struct barrier_t that can be used to synchronise the execution of a group of threads.

That is, this data type should enable multiple threads to wait until they all have reached a certain point in the execution of a parallel program.

Hints

You must implement the following functions: barrier_init, barrier_destroy, and barrier_wait.

/* bar INOUT A pointer to the barrier object to be initialised.                  */
/* nt  IN    The number of threads that will participate in a barrier operation. */

void barrier_init ( barrier_t* bar, int nt );

The function barrier_init initialises the members of the struct barrier_t. It must be called before a barrier operation can be performed.

The parameter nt specifies the number of threads that will participate in a barrier operation. This will be the number of threads that should call the function barrier_wait.

/* bar INOUT A pointer to the barrier object to be destroyed.                    */

void barrier_destroy ( barrier_t* bar );

The function barrier_destroy destroys a barrier object.

It must be called when a barrier object is no longer needed. Each call to barrier_init must be paired with a call to barrier_destroy.

/* bar IN A pointer to a barrier object.                                         */

void barrier_wait ( barrier_t* bar );

The function barrier_wait blocks all calling threads until the last thread in the group has entered this function.

To be precise, this function blocks until it has been called by the number of threads indicated by the nt parameter of the barrier_init function.

The struct barrier_t must contain at least a mutex, a condition variable and a counter that keeps track of the number of threads that have called the function barrier_wait.

You need more members; that is for you to figure out.

Test the program by spawning multiple threads and by performing at least four barrier operations in succession.

Paste this command into your terminal:

The password to connect is

Question 1: Reduction

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

/* ---------------------------------------------------------------------
 * types & constants
 * ------------------------------------------------------------------ */

#define                   NTHREADS  9

/* Note that the member "cycle" flip flops between 0 to 1. It is
 * there to ensure that two successive barrier operations do not
 * interfere with each other. The last thread joining a barrier
 * operation is the one that flips the "cycle" member. */

struct                    barrier
{
  pthread_mutex_t           mutex;
  pthread_cond_t            cond;
  int                       cycle;
  int                       count[2];
};

/* The struct "data" is used to pass data from the main thread to
 * each child thread. */

struct                    data
{
  int                       rank;
  struct barrier*           bar;
};

typedef struct barrier    barrier_t;
typedef struct data       data_t;

/* ---------------------------------------------------------------------
 * barrier_init()
 *
 *   Initialises a barrier object. The parameter "nt" specifies
 *   the number of threads that will participate in a barrier
 *   operation.
 * ------------------------------------------------------------------ */

void                      barrier_init

  ( barrier_t*              bar,
    int                     nt )

{
  assert ( bar && (nt > 0) );

  pthread_mutex_init ( &bar->mutex, NULL );
  pthread_cond_init  ( &bar->cond,  NULL );

  bar->cycle    = 0;
  bar->count[0] = nt;
  bar->count[1] = nt;
}

/* ---------------------------------------------------------------------
 * barrier_destroy()
 *
 *   Destroys a barrier object.
 * ------------------------------------------------------------------ */

void                      barrier_destroy

  ( barrier_t*              bar )

{
  assert ( bar );

  pthread_mutex_destroy ( &bar->mutex );
  pthread_cond_destroy  ( &bar->cond );
}

/* ---------------------------------------------------------------------
 * barrier_wait()
 *
 *   Blocks the calling threads until the last thread has entered
 *   this function.  The number of threads calling this function must
 *   be equal to the parameter "nt" specified in the call to the
 *   barrier_init() function.
 * ------------------------------------------------------------------ */

void                      barrier_wait

  ( barrier_t*              bar )

{
  /* Store the current cycle in a local variable. This is essential
   * as the last thread will change the cycle. */

  int  cycle = bar->cycle;

  assert ( bar );

  pthread_mutex_lock ( &bar->mutex );

  if ( (--bar->count[cycle]) > 0 )
  {
    /* Wait for the last thread. */

    while ( bar->cycle == cycle )
    {
      pthread_cond_wait ( &bar->cond, &bar->mutex );
    }
  }
  else
  {
    /* This is the last thread. Prepare the next cycle and wake the
     * other threads. */

    bar->cycle        = (cycle + 1) % 2;
    bar->count[cycle] = bar->count[bar->cycle];

    pthread_cond_broadcast ( &bar->cond );
  }

  pthread_mutex_unlock ( &bar->mutex );
}

/* ---------------------------------------------------------------------
 * thread_func()
 *
 *   The thread entry point. This function performs a number of
 *   barrier operations.
 * ------------------------------------------------------------------ */

void*                     thread_func

  ( void*                   arg )

{
  const int   niter = 4;

  data_t*     data = (data_t*) arg;
  barrier_t*  bar  = data->bar;
  int         rank = data->rank;

  int         i;

  for ( i = 0; i < niter; i++ )
  {
    barrier_wait ( bar );
  }

  printf ( "thread %d: executed %d barrier operations.\n",
           rank, niter );

  barrier_wait ( bar );

  if ( rank == 0 )
  {
    printf ( "\nbarrier data:\n" );
    printf ( "  cycle    = %d\n", bar->cycle );
    printf ( "  count[0] = %d\n", bar->count[0] );
    printf ( "  count[1] = %d\n", bar->count[1] );
    printf ( "\n" );
  }

  return NULL;
}

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

int                       main

  ( int                     argc,
    char**                  argv )

{
  pthread_t  threads[NTHREADS];
  data_t     data   [NTHREADS];
  barrier_t  bar;
  int        i;

  barrier_init ( &bar, NTHREADS );

  for ( i = 0; i < NTHREADS; i++ )
  {
    data[i].rank = i;
    data[i].bar  = &bar;

    pthread_create ( &threads[i], NULL, thread_func, &data[i] );
  }

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

  barrier_destroy ( &bar );

  return 0;
}

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	No deadline
Submission limit	No limitation

Information

Sign in