6.828/2018 Homework: Barriers

As always, download barrier.c and read it.

main() creates argv[1] number of Pthreads. Each thread does:

static void *
thread(void *xa)
{
  long n = (long) xa;
  long delay;
  int i;

  for (i = 0; i < 20000; i++) {
    int t = bstate.round;
    assert (i == t);
    barrier();
    usleep(random() % 100);
  }
}

Threads should block in barrier() until all threads have called barrier(). bstate is defined as:

struct barrier {
  pthread_mutex_t barrier_mutex;
  pthread_cond_t barrier_cond;
  int nthread;      // Number of threads that have reached this round of the barrier
  int round;     // Barrier round
} bstate;

Without further ado, here’s my solution:

static void 
barrier()
{
  pthread_mutex_lock(&bstate.barrier_mutex);

  if (++bstate.nthread < nthread) {
    pthread_cond_wait(&bstate.barrier_cond, &bstate.barrier_mutex);
  }
  else {
    bstate.nthread = 0;
    bstate.round++;
    pthread_cond_broadcast(&bstate.barrier_cond);
  }

  pthread_mutex_unlock(&bstate.barrier_mutex);
}

Fairly simple. Whenever a thread calls barrier(), it increments bstate.nthread. If bstate.nthread reaches nthread, the current thread is responsible to wakeup all other threads (by calling pthread_cond_broadcast()), set bstate.nthread back to zero and increment bstate.round. Otherwise, the thread simply calls pthread_cond_wait() then goes to sleep.

Of course, since bstate is a global structure, all these read/write accesses to it need to be done while holding a mutex lock acquired by calling pthread_mutex_lock().

Let’s run it:

peilin@PWN:~/6.828/2018/homework/barriers$ make
gcc -g -O2 -pthread -o barrier barrier.c
peilin@PWN:~/6.828/2018/homework/barriers$ ./barrier 10
OK; passed

OK;…

Finally let’s take a look at two more issues mentioned in the homework page:

You have to deal with a succession of barrier calls, each of which we’ll call a round. bstate.round records the current round. You should increase bstate.round when each round starts.

Homework: Barriers

Emm yeah, I believe so, starting from zero. My implementation passed that assert statement in thread().

You have to handle the case in which one thread races around the loop before the others have exited the barrier. In particular, you are re-using bstate.nthread from one round to the next. Make sure that a thread that leaves the barrier and races around the loop doesn’t increase bstate.nthread while a previous round is still using it.

Homework: Barriers

Say we have two threads, A and B. A was waiting, then B waked it up. Now bstate.nthread is set back to zero. Suppose B now just keep on running for no reason. Theoretically, how far can B run ahead of A? It can return from barrier(), jump into the next iteration of for loop, call barrier() again, increment bstate.nthread to one, then it will wait – since nthread > 1… Nothing to worry about!

That’s pretty much it. See you next time!