A barber shop has one barber, one barber chair, and nChairs chairs for waiting customers. If there are no customers present, the barber sits down in the barber chair and falls asleep. When a customer arrives, the customer has to wake up the sleeping barber. If additional customers arrive while the barber is cutting hair, they either sit down (if there are empty waiting chairs) or they leave the shop (if all waiting chairs are full). Customers wait in the waiting chairs until called to the barber chair by the barber.

The following code models this process using a BarberShop object to synchronize the actions of the barber and customer threads:

    barber(BarberShop bs){
      while(true){
        bs.waitForCustomerArrive(); // Post-condition -- barber out of
                                    // chair and at least one customer in shop
        bs.waitForCustomerInBarberChair(); // Post-condition -- customer in
                                          //  barber chair
        cutHair();  
        bs.doneCutting();               // Post-condition -- customer out of
                                        //  barber chair
      }
    }

    customer(BarberShop bs, int customerId){
      action = bs.waitOrLeave(customerId);
      if(action == ACTION_LEAVE){
        return; 
      }
      bs.sitInBarberChair(customerId); // Pre-condition -- barber chair is
                                       // empty
				       // Post-condition -- hair cut and 
				       // out of chair
      return;
    }

Question: Why is cutHair() done outside of the BarberShop monitor?

The function definitions and invariants above are designed to force you to think carefully about the system state. Make sure your code has sufficient interlocks so that a customer doesn't sit down until the barber is awake and out of the chair (e.g., until waitForCustomerArrive() has returned), so that the barber doesn't cut hair until the customer is sitting in the chair, so that the customer doesn't get up until the barber has called doneCutting(), so that doneCutting doesn't return until the customer is out of the chair, etc.

Before you begin the assignment, read Coding Standards for Programming with Threads. You are required to follow these standards for this project. Because it is impossible to determine the correctness of a multithreaded programming via testing, grading on this project will primarily be based on reading your code not by running tests. Your code must be clear and concise. If your code is not easy to understand, then your grade will be poor, even if the program seems to work. In the real world, unclear multi-threaded code is extremely dangerous -- even if it "works" when you write it, how will the programmer who comes after you debug it, maintain it, or add new features? Feel free to sit down with the TA or instructor during office hours for code inspections before you turn in your project.

You should also look at these hints for avoiding common pitfalls.

To simplify your task, we have developed a simple thread package on top of the standard pthread package for your use. The idea is to shield you from the irrelevant detail that inevitably is part of dealing with pthreads. This way, you use the standard package but you also focus on the project at hand.

The files are sthread.h and sthread.cc. The package provides threads, mutex locks, and condition variables. This package is built on the posix thread library. For more information, see the man pages for the library functions used in the sthread.cc code.

The code for this lab should be portable, and you should be able to code, debug, and test on almost any platform. You might find it useful to run on a multiprocessor machine (to, perhaps, trigger a wider variety of thread interactions than you might see on any given uniprocessor). We plan to test on shadowfax.cs.utexas.edu, for example, which is a public machine with four processors (accessible remotely by ssh or via the SunRay machines in the Taylor basement). You can code and debug on any host you like, but you are responsible for ensuring that the code you turn in compiles without errors or warnings and runs on shadowfax.cs.utexas.edu.

A common pitfall on this lab is to use printf (or cout) for debugging and then have things break when the prints are removed. This is because there is underlying synchronization in the prints that can mask other bugs. Thus, you must use assertions instead of printf to be sure your code works correctly. For the purposes of grading, all prints will be commented out, so your code must work without them.

Download the code from labT.tar and untar this file to create the subdirectory labT. Running make ("make" on CS department public Solaris machines) should produce the executable file main with no errors or warnings.

We have provided skeleton files for the BarberShop object as well as a SharedCounter object we will use to aid testing.

A call to SharedCounter::increment() increments the counter and a call to SharedCounter::get() returns the current count. A call to SharedCounter::waitForCountAtLeast(i) blocks until the shared count is at least as large as the parameter i, and then returns.

The BarberShop object is as described above -- it maintains the state of the barber shair and waiting room chairs. It has the five public methods indicated above: waitForCustomerArrive(), waitForCustomerInBarberChair(), doneCutting(), waitOrLeave(), and sitInBarberChair(). Additionally, for testing it has the public method getShopState(), which returns a copy of the current state of the barber shop.

Question: Why does getShopState() return a copy of the current state rather than returning a pointer to the internal state?

Complete the code for SharedCounter and BarberShop and fill in the needed functions in main and BSState. Once you have done this, the two simple tests in mikesTest() should succeed. Feel free to add any additional tests to moreTests().

Create PriorityBarberShop, a variation of BarberShop that more carefully controls the order that customers are served. In particular, whereas the BarberShop specification allows waiting customers to be served in any order, PriorityBarberShop uses the following two rules to decide which waiting customer goes next: (1) if a "VIP" customer is waiting, that customer always is served before a "NORMAL" customer and (2) within a class (VIP or NORMAL), the customer who has been waiting the longest preceeds customers from the same class who have not waited as long.

VIP customers enter the barbershop using the method VIPWaitOrLeave()

Note that an implementation of PriorityBarberShop would be a legal implementation of the specification of BarberShop, so you might be tempted to skip Exercise 1, just write PriorityBarberShop for exercise 2, and use that code for Exercise 1 as well. We strongly discourage this strategy. The BarberShop code will be significantly simpler and easier to get right than the PriorityBarberShop code, so get the simple BarberShop working for exercise 1 before trying to write the code for exercise 2.

You may notice that although BarberShop and PriorityBarberShop have similar interfaces, we have chosen to implement them as separate classes rather than to make one a subclass of the other. This engineering decision reflects (1) our anticipation that internal data structures may be different and (2) our belief that code readability trumps compactness as a priority for this project. Please conform to this decision.

For this exercise, (1) describe in the README file how your design meets the scheduling requirements, (2) implement PriorityBarberShop, and (3) design and implement at least one well-considered test that creates a number of VIP and normal customers and sanity checks your implementation.

This completes the lab.

Create a README.txt file that contains the names of both members of your group and the number of slip days used on this project and the total number of slip days used so far.

The README should also include your answer to the following two questions asked above: Why is cutHair() done outside of the BarberShop monitor?, Why does getShopState() return a copy of the current state rather than returning a pointer to the internal state?

The README should also include a description of how your design of PriorityBarberShop meets the design requirements of exercise 2.

Finally, your README should describe the reasoning behind you sanity check test for exercise 2.

Running "gmake turnin" should create a file containing all of the .h and .cc files you have modified or created. Please do not include any other files in labT.tar. Turn in this file using the command

turnin --submit taID cs372h-labT labT.tar

where taID is the userID of your TA.