CS161 In-Class Exercise 2/3/15

• Find the parts of OS/161 relevant to synchronization.
• Use semaphores to solve increasingly complex problems.

Updating your repository

So, create the shorthand (handout):

        % git remote add handout git@code.seas.harvard.edu:cs161/os161.git

Now, get any changes from the course repository, without merging them into your current tree (because you don't want these changes permanently as part of your operating system).

        % git fetch handout

        % git checkout -b class23 handout/class23

        # You are now working on a branch designed just for today's class.
        # You will not want to do any real work in this branch!

Now, build and install a kernel using the config file CLASS-2-3. To avoid your having to look up how to do this, we'll include it here, but by the end of this week, you should be able to do this in your sleep.

    % cd kern/conf
    % ./config CLASS-2-3
    % cd ../compile/CLASS-2-3
    % bmake depend
    % bmake
    % bmake install

If you now run System/161 with your kernel, you'll see some new entries in the menu.

Finding the synchronization code

This is a bit of a scavenger hunt: you need to find three files/directories:

1. The directory in which we place driver code and solutions for in-kernel synchronization problems.
2. The file in which we define the structures and APIs for accessing OS/161 synchronization primitives.
3. The file in which we place the implementation for synchronization primitives.

So, go find the three files/directories described above.

• Hint 1: "In-kernel"
• Hint 2: In what kind of files do you find structure definitions and APIs?
• Hint 3: In order to test synchronization, we'll need to spawn multiple threads to synchronize.

Once you've found these, examine the file that implements semaphores and become familiar with the API. (The video should have helped explain the use of semaphores.) You'll need to create and use semaphores in the following problems.

1. Warm Up Problem 1: Using binary semaphores

If you have found the answer to question 1, you will find a file called semprob1.c. If you do not see that file, then you did not succeed in checking out the correct branch from the repository. Raise your hand and ask a member of the staff for help.

The driver program spawns some number of ping and pong threads. Your goal is to add proper synchronization so that regardless of how many threads are spawned, and regardless of which of ping and pong get to run first, we will get alternating pings and pongs -- you cannot have two pings in a row or two pongs in a row. You should use only a single semaphore to accomplish this.

If you run the problem as it is now (pp from the command prompt), you should see that you sometimes get repeated hits from the same type of thread (because it is not yet synchronized). If you do not see that behavior, edit your sys161.conf file in your root directory to have your system run with multiple processors (we got improper behavior with two cpus).

2. Warm Up Problem 2: Using counting semaphores

Look in the file semprob2.c. We're going to solve this problem two different ways. The first way will be quite similar to what you did in Problem 1.

We have N_TFS teaching fellows and N_STUDENTS students, all of whom wish to speak with a teaching fellow -- all the time! Your job is to synchronize them so that one TF is helping one and only one student at any time.

Create a solution using only one semaphore that retains the ability to know to which TF a student is talking. (This is the part that is quite similar to the first problem.)

Once you've got that working, modify the problem slightly so that you still use only a single semaphore, but you don't care which TF a student talks to, just that there is, in fact, a TF available for a student with a question (pay attention to the tag line on this problem for a hint).

If you're bored you can combine the two solutions here and both assign a student to a specific TF and block a student until you know that a TF is available. (This avoids the need for the code that checks if i is less than N_TFS.)

3. Having the main thread exit cleanly

You may have noticed that after the main thread spawns its threads, the main thread prints out the kernel prompt again, but it gets garbled with the output of the spawned threads. Design a way to make the main thread wait until all the children have finished. There are several ways to do this, but the cleanest uses a single semaphore.

4. The Classic CS161 Whale Mating Problem (Barrier Synchronization)

This is a classic CS161 problem that comes to us from colleagues at Berkeley. It is both an interesting synchronization problem and a source of endlessly entertaining conversations among CS161 padawans and jedi alike.

You have been hired by the New England Aquarium's research division to help find a way to increase the whale population. Because there are not enough of them, the whales are having synchronization problems in finding a mate. The trick is that in order to have children, three whales are needed; one male, one female, and one to play matchmaker - literally, to push the other two whales together (We're not making this up!).

Your job is to write the three procedures male(), female(), and matchmaker(). Each whale is represented by a separate thread. A male whale calls male(), which waits until there is a waiting female and matchmaker; similarly, a female whale must wait until a male whale and matchmaker are present. Once all three are present, all three return.

The test driver for this program is in the file /kern/synchprobs/whalemating.c. It forks fifteen threads, and has five of them invoke male(), five of them invoke female(), and five of them invoke matchmaker(). Stub routines, which do nothing but print diagnostic messages, are provided for these three functions. Your job will be to re-implement these functions so that they solve the synchronization problem described above. Each whale (thread) should print out a message when it begins, identifying itself, and then again when it has successfully mated (or assisted a couple in mating). You should not take advantage of the fact that you know how many whales of each type you have created. In other words your solution should work in the presence of an infinite number of whales entering and leaving the system.

Before you begin, write the correctness criteria that you need to enforce to properly synchronize our whales! Place this as a comment in the whalemating.c file.

Cleaning up your repository

	% git checkout master
	# You are now back to working in your tree

	% git branch -d class24
	# Deletes the branch from your repository, losing the work you
	# did in class.