Assignment 5

Assigned:
Monday, Mar 5, 2018
Due:
Wednesday, Mar 14, 2018 by 10:30pm
Collaboration:
You may not discuss or work on this assignment with any other students. Mentors can help you if you are confused about the assignment requirements or documentation, but they cannot provide any assistance that would require them to look at your code. Please see the assignments page for detailed assignment policies.
Submitting:
To submit your work, simply commit your final changes and push them to GitHub before the deadline. You do not need to create a pull request to turn in these assignments.

Overview

For this assignment, you will implement a synchronization primitive known as a barrier. When creating a barrier, you specify a number of threads, num_threads. To use the barrier, a thread calls barrier_wait, which will block the thread until num_threads threads have arrived at the barrier. Barriers are a simple and useful synchronization primitive, particularly for scientific computation where some parallel calculation must proceed in phases. Barriers make it easy to guarantee that all threads have completed one phase of a calculation before moving on to the next phase.

Unlike our previous individual assignments, this assignment does not include start code for a useful program. Instead, you will write the barrier as if it was going into a library for other programs to use. The starter code does include scaffolding so you can use the Google Test framework to test your implementatation.

Questions & Answers

Does our barrier have to work if num_threads is less than the number of different threads that call barrier_wait?
No. I will only test programs that match the number of threads to the size of the barrier.
Do we need to keep a list of threads waiting at the barrier?
No, probably not. Condition variables keep track of threads for you, and it’s difficult to do much with a thread’s ID other than join with it, which is not what we want in this case.

Requirements

The interface for your barrier is in the file barrier.h. You should implement each of these functions in barrier.c.

void barrier_init(barrier_t* b, size_t num_threads)
The parameter b points to memory already allocated to hold a barrier. Initialize the barrier so it will block waiters until num_threads threads arrive.
void barrier_wait(barrier_t* b)
A thread calls this to arrive at a barrier. The call should not return until num_threads threads have arrived at the barrier. The barrier can be reused an unlimited number of times, so make sure it is set up to accept new arrivals once waiting threads wake up.
void barrier_destroy(barrier_t* b)
Clean up a barrier b.

When you implement your barrier, make sure you consider the following issues and requirements:

  1. When a thread is waiting at a barrier it should wait on a condition variable. Solutions that repeatedly acquire a mutex instead of sleeping will not receive full credit.
  2. When the last thread arrives at a barrier it should wake all of the waiting threads, not just one.
  3. Barriers are used in cycles, so it is possible that one thread will wake up from the barrier and then call barrier_wait again before previously-waiting threads have woken up. Make sure you wake the older threads from the barrier, not the new arrival.

The POSIX threads library on some systems includes a barrier implementation, which you can read about in the Oracle Pthreads Documentation. You are welcome to use other pthreads primitives like mutexes and condition variables when implementing barriers, but you may not use pthreads barriers in your implementation.