CSc 335

Objectives

• To practice with concurrency controls: semaphores and monitors
• To understand locks and condition variables
• To implement a safe bounded buffer
• To continue learning the Nachos thread system
• To fix your broken Project 1...

Your Mission

Recommendation

Part 1: Locks and Condition Variables

1. Implement the Lock class using semaphores. You'll need to add data members to synch.h and code to synch.cc. 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 synchlist.cc) 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

   • A thread trying to acquire a lock doesn't already hold it
   • A thread trying to release a lock is the same thread that holds it

   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. synchlist.cc 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 list.cc. 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 synchlist.cc) 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

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

class BoundedBuffer {
  public:
    // create bounded buffer with a fixed size
    BoundedBuffer(int maxsize);

    // delete the buffer elements
    ~BoundedBuffer();

    // 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!

Grading

• 20 points for a correct implementation of locks and condition variables.
• 10 points for a correct fix of your doubly-linked list.
• 10 points for a correct implementation of your bounded buffer.
• 10 points for the write-up. The harder it is for me to understand what your test cases are doing, the fewer points you will receive.

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