MC78 Lab 2: Implementing Threads and Synchronization (Fall 1996)

Due: October 15, 1996

Goals of the lab

In this lab, you will get to see how a single processor can divide its attention between multiple threads, and how synchronization primitives to coordinate those threads' activities can be implemented. In fact, although you will be given a working implementation of threads and of some synchronization primitives (semaphores, with their ``down'' and ``up'' operations, also known as P and V), you will be responsible (with your partner or group mates) for implementing other synchronization primitives, namely monitor locks and condition variables.

As a demonstration that you have successfully completed the primary goal (implementing locks and condition variables) and in order to get more practice in the use of monitors and condition variables, you will complete and run a demonstration program which makes use of these facilities; I will provide most of this program, but have left some of the operations in one class for you to write.

The class I provide only parts of implements a bounded-buffer communication channel abstraction, into which a producer can put integers (waiting if the buffer is full), and from which a consumer can then get the integers (waiting if there are none). One additional feature is that the producer can explicitly "shutdown" the communications channel, indicating that no more integers will ever be put into the channel. The consumer's get operation indicates when all the values have been gotten and the channel has been shutdown; if the channel isn't shutdown, the consumer's get operation waits for the producer to either put another value in or shutdown the channel. We'll already have looked at the partial implementation in class, and discussed in general terms the operations that remain for you to implement.

The bounded buffers in turn will be used (by code I provide all of) to support a pipelined style of communication for a large ensemble of threads that are ``sieving'' for prime numbers. (This is purely to demonstrate threads and synchronization, not because this is a very efficient way to find primes.)

Origin of this lab

Most of the code for this lab (everything except the bounded buffer class and its application to sieving for primes) comes from the Nachos simulated operating system developed by Tom Anderson at Berkeley for educational use. The idea of having the threads and semaphores implemented, but the locks and condition variables remaining for you to implement, is also from one of his Nachos assignments.

The files

The files you will need for this lab are in the directory ~max/www-docs/MC78/lab2/code. The simplest thing for you to do is to make a copy of the whole directory by in a shell window doing the following command:
cp -pr ~max/www-docs/MC78/lab2/code .
This will give you your own code directory as a subdirectory of whatever directory you were in when you did the cp command. The relevant files are all in the threads subdirectory. The most interesting are the following:

Compiling and testing the program

Once you have edited the ones you need to change, you can cd to code/threads and then do the command make. This will recompile/assemble/link everything, resulting in a program called nachos, unless, of course, the compiler gives error messages on your code. Once you have fixed the compiler's complaints and are getting an executable nachos program, you can try running it from the shell. It should print out a list of primes, ending with 997 as the 168th prime, and the an explicit message ``end of primes.'' If you get all 168 primes, but no ``end of primes'' message, something is wrong with the way you shutdown the bounded buffers.

Debugging output

To produce debugging output from your code, you can insert lines such as the following one, which is in the ThreadTest procedure in sieve.cc:
DEBUG('t', "Entering SieveTest");
Normally these lines produce no output, but if you run nachos with the command line arguments -d t, then they will be printed out as the program runs. That is, to run the program with debugging output you do:
nachos -d t

What to turn in

Turn in a jointly-authored lab report containing your changes to the three files you needed to change. You should also describe briefly the logic behind your program.

Addendum: shutdown with pending puts

When I designed the bounded buffer (BBuf) class, I forgot completely about the question of what to do if the buffer is shutdown while one or more puts are waiting for space. A student pointed this out to me. My suggestions regarding what to do about this are in an email message I sent to the class.

Instructor: Max Hailperin