CSc 335

Project 2 -- Fix that Code
Due Monday, April 27, 2009


Your Mission

Now that you've broken your code in many ways, it's time to implement concurrency controls to fix the problems. While semaphores have been implemented for you in NACHOS, generic locks and condition variables have not. So there are no monitors yet. In this project, you will remedy that situation by implementing locks and condition variables. Then, you will turn your doubly-linked list into a monitor to stop the concurrency errors from occurring. As further practice, you will also implement a bounded buffer monitor.


Before starting any new project, I recommend doing some version control so you always have a checkpoint that you can go back to. Copy your entire Nachos code directory (i.e. your finished Project 1) into a separate place in your antipasto account. Then use the copy as the starting point for this project. That way, if something goes horribly wrong, you have backup files from a known starting point.

Part 1: Locks and Condition Variables

Take a look at synch.h in the threads directory. You'll find the definitions of three classes: Semaphore, Lock, and Condition. Only Semaphore, which is implemented as a general counting semaphore, is fully coded for you in Towards the bottom of, you'll see the empty functions of Lock and Condition that need to be implemented. That's your first task.

  1. Implement the Lock class using semaphores. You'll need to add data members to synch.h and code to Do not disable interrupts directly to do this (the semaphore does it for you). You may not change the public interface at all. NACHOS was nice enough to provide a protected list data structure (in so you can see how the Lock class will be used. Look at it to help you write the code.

    PITFALL ALERT: Be sure to use ASSERT statements to make your debugging life easier. In particular, make sure that

    There are other places where ASSERTing things that you know should be true at that point will help you in the long run. Use it. Note: you'll have to #include utility.h which is where ASSERT is defined.

  2. Implement the Condition class to provide Mesa-style condition variables, again using semaphores. Don't disable interrupts and don't change the public interface. also demonstrates condition variable usage, so use it again for guidance. Note that you are also asked to implement the Broadcast function, which is kind of a global Signal. We probably won't be using Broadcast too much but go ahead and implement it anyway. Hint: NACHOS has also been kind enough to implement the List class for you in It sure makes defining a queue easier...

    POOR DESIGN ALERT: In the Condition class, the lock associated with the condition (the one that lets this thread be in the monitor) is passed as a parameter all over the place. I have no idea why the lock isn't a data member and initialized in the constructor. But don't try to "fix" it. Other code (like depends on it working as is.

    PITFALL ALERT: Implementing Lock and Condition should not require a lot of code, but typing the right code is tricky. Make sure to account for the starvation problem of Mesa-style monitors that we talked about in class.

Part 2: Repair Project 1

Use your new locks and condition variables to turn your DLList class into a monitor. That is, modify the functions so that (1) multiple threads can access a shared list without causing concurrency errors and (2) underflow is prevented (i.e. RemoveHead will now always remove something.) You'll do both of these by adding locking, waiting, and signaling calls at the right places.

Rerun all of your tests from Project 1 to make sure that all of your concurrency problems have been fixed. Document your fixes in your write-up by summarizing each original problem and then showing how your code now prevents the error (showing the corrected output for this part is fine).

Part 3: Bounded Buffer

Finally, make a bounded buffer monitor with two files: bbuffer.h and Here's the definition that goes in bbuffer.h:
class BoundedBuffer {
    // create bounded buffer with a fixed size
    BoundedBuffer(int maxsize);

    // delete the buffer elements

    // Read a character from the buffer, blocking until there is a char
    // in the buffer to satisfy the request. Copy the char into already
    // allocated memory location c.
    void Read(char *c);

    // Write a character c into the buffer, blocking until enough space
    // is available to satisfy the request.
    void Write(char c);

    // Prints the contents of the buffer; for debugging only
    void Print();

To test (and debug) your protected bounded buffer, add a few test cases to DLListTest() (where all your Project 1 tests are). Be sure to test cases with multiple threads that would have caused problems if the monitor was not in place. Document these new tests (and what the errors would have been) in your write-up. Be sure to test your wait and signal calls by forcing what would normally be underflow and overflow without the protection!


This project is worth 50 points:

On paper, please turn in your write-up and source code for all code you have written for this project. Turn in a copy of your output for all your tests. Be sure to label what tests are for what part of the project.

Electronically, please turn in your entire code directory using our submit script:

/home/csc335pub/submit csc335 <full path to your code directory>

Having trouble? Don't wait until the last minute! Come see me and get your $80 worth.

Administrative statement

Programming assignments, like homework assignments, are individual projects. I encourage you to talk to others about the general nature of the project and ideas about how to pursue it. However, the technical work, the writing, and the inspiration behind these must be substantially your own. If any person besides you contributes in any way to the project, you must credit their work on your homework. Similarly, if you include information that you have gleaned from other published sources, you must cite them as references. Looking at, and/or copying, other people's programs or written work is inappropriate, and will be considered cheating.
Return to Project Index