Cats and Mice, A Synchronization Problem

Here is our scenario:

A Harvey Mudd E4 team has developed a complex, automated, animal-feeding bowl that can feed a variety of different animals, including cats, mice, and dogs. So far, two prototypes for the automatic feeding bowl design have been built and need to be tested. The bowls do work, but the team has yet to complete a proper formal test due to some unforeseen “animal interactions”, such as cats preferring to eat mice rather than food from the food bowls. After various attempts to arbitrate access to the bowls (including schemes where only one bowl ever seemed to be used, and another where the mice got fat and the cats starved), they have come to you asking for help in developing a synchronization algorithm.

As the E4 team discovered, we cannot allow a free-for-all for the food bowls. Cats will attack mice, and dogs will chase both cats and mice. You need to devise a synchronization scheme that will control access to the bowls in such a way that different species can share the bowls without ever actually seeing each other (i.e., only one species may be using the bowls at a time).

This problem will give you the opportunity to write some fairly straightforward concurrent programs and get a more detailed understanding of how to use threads to solve problems. You will need to solve the problem twice—once using semaphores and once using locks and condition variables.

The code you need to edit is provided in src/kern/synchprobs/catsem.c and src/kern/synchprobs/catlockc. You can run the functions defined in these files from the kernel's main menu via the options sp1 and sp2. (This code is only included in the kernel when the synchprobs configuration is enabled, as it is in the SYNCH configuration.)

Specifically, you need to handle a simulation of two food dishes, six cats, and two mice, where each animal eats ten times.

The provided code does little more than fork the required number of cat and mouse threads—you will need to do the rest.

The original scenario also included dogs, but you can ignore them here, although it is very possible to write generalized code that can handle multiple kinds of animals. If you do implement more flexible code, return the code to having six cats and two mice before you submit—we'll be testing your code, and the tests will fail if you have different animals from the ones we're expecting.

Requirements

All the animals are represented by independent threads that become hungry and want to go to the food-bowl area, eat at a particular food bowl, and then spend a random period satisfied by the food they have eaten before becoming hungry again. In the case of working with just cats and mice, your job is to develop a synchronization scheme where the cat and mouse threads are synchronized such that no mice could be eaten. For example, if a cat is eating at either food dish, any mouse attempting to eat from the other dish would be seen by the cat and could be eaten, so this situation must be avoided. Your synchronization scheme will require you to sometimes make cats or mice wait a moment for their food. Only one mouse or cat may eat at a given dish at any one time, but you should try to ensure that both bowls get used when doing so is practical (i.e., you can have a cat at each of the two bowls, or two mice eating at the bowls). You can assume that the bowls always have plenty of food.

Your solutions

• Must never allow two animals of different species to be at the bowls at the same time;
• Must not be prone to starvation, of either cats or mice (or dogs);
• Must protect the kprintf statements such that a status message from one thread cannot be interwoven into a status message from another thread;
• Must not change the format of the thread status messages from the format given in the skeleton code (although you may output additional messages to provide more information or to assist you in debugging);
• Must have each animal eat exactly ten times (i.e., NUMLOOPS times);
• Must not exit the main catmouselock or catmousesem until all the animal threads have terminated;¹
• Should provide good utilization of the bowls.

Running Your Code Outside of OS/161

To allow you to work on this code even before you have working locks and condition variables in OS/161 (and to allow you more flexibility in debugging), we have provided a way for you to run each of the synchronization problems outside of OS/161.

In the src/kern/synchprobs directory is a header file fake.h that maps the OS/161 in-kernel APIs for both locks and semaphores to standard Unix APIs. At the top of each file are instructions for compiling and running the code outside of OS/161, by compiling with gcc and defining the preprocessor symbol FAKE to include the fake.h header.

Contextual Note

The code you've written in this part is very unusual code.

The way we are using the kernel to run these programs (outside of the fake.h workaround) is not typical. Normally, programs such as these would be written as user-mode programs. We have included the code as a part of the kernel itself for two reasons: First, your lock code is intended to be used by kernel functions that you will write in future assignments, not (directly) by user code, so that code does belong in the kernel—the cats-and-mice code is essentially just test code for that lock implementation, and it is easiest to write kernel code to test kernel code. Second, OS/161 is not yet able to run meaningful user-mode programs, so we have little other choice at present.

(When logged in, completion status appears here.)

Previous Page Go to Parent Page