Threading Lab

About this lab

In this lab you will get practice with locks, condition variables, and the pthread library by writing two multi-threaded programs.

Getting the starter code

You can get and extract the starter code with the commands below.

cd cs334
wget --no-check-certificate https://cs334.cs.vassar.edu/labs/threadlab.tar
tar xf threadlab.tar
rm threadlab.tar
cd threadlab

This tarfile contains the starter code for the threading lab. The included Makefile will compile your solutions to the train and reaction synchronization problems. The resulting binaries will try to stress test what you wrote and should hopefully help you to shake out any bugs.

You’ll need to fill in train.c and reaction.c appropriately to complete this assignment (the tests will certainly fail before you do so).

You are to use the lock and condition variable APIs shown below. The following types are defined already for your use:

struct lock
struct condition

As are the following functions:

void lock_init(struct lock *lock);

void lock_acquire(struct lock *lock);

void lock_release(struct lock *lock);

void cond_init(struct condition *cond);

void cond_wait(struct condition *cond, struct lock *lock);

void cond_signal(struct condition *cond, struct lock *lock);

void cond_broadcast(struct condition *cond, struct lock *lock);

No other files need to be modified. Compile using make. To run a bunch of tests, you can try make run. These programs have been tested on the machines in the Asprey lab and the machines in SP309.

Problem 1: Train Automation

For this problem we will model a subway station using threads. Your task is to write synchronization functions that will guarantee an orderly loading of trains. Each passenger and each train is controlled by a thread. You must define a structure struct station, plus the functions described below.

When a train arrives in the station and has opened its doors, it invokes the function:

void station_load_train(struct station *station, int count)

where count indicates how many seats are available on the train. The function must not return until the train is satisfactorily loaded (all passengers are in their seats, and either the train is full or all waiting passengers have boarded).

When a passenger thread arrives in a station, it first invokes the function:

void station_wait_for_train(struct station *station)

and this function must not return until a train is in the station (i.e., a call to station_load_train() is in progress) and there are enough free seats on the train for this passenger to sit down. Once this function returns, the passenger boards the train and into a seat (you do not need to worry about how this mechanism works). Once the passenger is seated, the passenger thread will call the function:

void station_on_board(struct station *station)

to let the train know that they are on board.

You will modify the file train.c for this part of the assignment. This file contains a declaration for struct station and defines the three functions above, plus the function station_init(), which will be invoked once at the start (before anything else is called) to initialize the station object. In addition:

  • You must write your solution in C using only functions listed below. You should not call any other functions.

    void lock_init(struct lock *lock)
    
    void lock_acquire(struct lock *lock)
    
    void lock_release(struct lock *lock)
    
    void cond_init(struct condition *cond)
    
    void cond_wait(struct condition *cond, struct lock *lock)
    
    void cond_signal(struct condition *cond, struct lock *lock)
    
    void cond_broadcast(struct condition *cond, struct lock *lock)
  • Use only these functions (e.g., no semaphores or other synchronization primitives).

  • You may not use more than a single lock in each struct station.

  • You may assume that there is never more than one train in the station at once, and that all trains (and all passengers) are going to the same destination (i.e., any passenger can board any train).

  • Your code must allow multiple passengers to board simultaneously In other words, it must be possible for several passengers to have called station_wait_for_train(), and for that function to have returned for each of the passengers, before any of the passengers calls station_on_board().

  • Your code must not result in busy-waiting and your code should not call cond_signal() unnecessarily.

Problem 2: Chemical Reaction

You have been hired by Mother Nature to help her out with the chemical reaction to form water, which she doesn’t seem to be able to get right due to synchronization problems. The trick is to get two H atoms and one O atom together at the same time. Each atom is represented by a thread. Each H atom invokes the function

void reaction_h(struct reaction *r)

when it is ready to react, and each O atom invokes the function

void reaction_o(struct reaction *r)

You must write the code for these two functions. The functions must delay until there are at least two H atoms and one O atom present, and then exactly one of the functions must call the procedure make_water() (which you needn’t write; Mother Nature has already gotten this part figured out). After each make_water() call, two instances of reaction_h() and one instance of reaction_o() should return.

You will modify the file reaction.c for this part of the assignment. This file contains a declaration for struct reaction and defines the two functions above, plus the function reaction_init(), which will be invoked once at the start (before anything else is called) to initialize the reaction object. In addition:

  • Your code must invoke make_water() exactly once for every two Hydrogen atoms and one Oxygen atom that call reaction_h() and reaction_o(), and only when these calls are active (i.e., the functions have been invoked but have not yet returned).

  • Write your solution in C using the functions for locks and condition variables listed in the train problem above.

  • You may not use more than a single lock in each struct reaction.

  • Your code must not result in busy-waiting and your code should not call cond_signal() unnecessarily.

Testing Your Code

We have created a test framework that you can use to test your code. Typing

make run

will compile and test your solutions for both problems. These programs have been tested on the machines in the Asprey lab and the machines in SP309.

The tests have a lot of randomness built in and are not flawless (their passing doesn’t guarantee a perfectly correct implementation). You may want to run the tests many times to get better assurance of your solution’s sanity. You are welcome to extend the tests any way you see fit, but they wii not be submitted. You should refrain from using any other libraries or functions in your solutions.

Note that hard timeouts are used to catch some issues like deadlock. It’s possible that on busy shared machines they’re too conservative. If you are sure your code is correct and the tests still don’t pass, come by my office hours and I’ll try to help you figure out what’s going wrong.

Grading

This lab is worth 100 points. You will receive 50 points for passing the tests for problem 1 and 40 points for passing the tests for problem 2. Synchronization code is hard to get right, so it’s important that it be clean, simple, and obvious. Unfortunately, solutions can end up long and complicated; such solutions rarely work, and in real life they would be brittle and hard to maintain. 10 points of your grade is based on how clear and easy to read your program is. My solution for train.c has 63 lines and my solution for reaction.c has 48 lines (not including comments). Note: your goal should be simplicity, not just line count; simple programs are usually shorter than complex ones, but the shortest program isn’t always the simplest.

Submitting the Lab

To submit your solutions, type the following:

make submit

This will create the file threadlab-submit.tar which you can then upload to gradescope.