The Assignment

1. Implement locks and condition variables. You may either use semaphores as a building block, or you may use more primitive thread routines (such as Thread::Sleep). We have provided the public interface to locks and condition variables in synch.h. You need to define the private data and implement the interface. Note that it should not take you very much code to implement either locks or condition variables.

2. Implement producer/consumer communication through a bounded buffer, using semaphores. (A solution to the bounded buffer problem is described in Silberschatz, Peterson and Galvin, using semaphores.)

   The producer places characters from a text file into the buffer one character at a time; it must wait if the buffer is full. The consumer pulls characters out of the buffer one at a time and prints them to the screen; it must wait if the buffer is empty. Test your solution with a multi-character buffer and with multiple producers and consumers. Of course, with multiple producers or consumers, the output will illustrate the concurrency provided by threads.

3. The local laundromat has just entered the computer age. As each customer enters, he or she puts coins into slots at one of two stations and types in the number of washing machines he/she will need. The stations are connected to a central computer that automatically assigns available machines and outputs tokens that identify the machines to be used. The customer puts laundry into the machines and inserts each token into the machine indicated on the token. When a machine finishes its cycle, it informs the computer that it is available again. The computer maintains an array available[NMACHINES] whose elements are non-zero if the corresponding machines are available (NMACHINES is a constant indicating how many machines there are in the laundromat), and a semaphore nfree that indicates how many machines are available.

   The code to allocate and release machines is as follows:

   
   int allocate()	{         // Returns index of available machine
     int i;
   
     P(nfree);               // Wait until a machine is available
     for (i=0; i < NMACHINES; i++)
       if (available[i] != 0) {
         available[i] = 0;
         return i;
       }
   }
   
   release(int machine) {	  // Releases machine 
     available[machine] = 1;
     V(nfree);               // Signal a machine is free
   }

   The available array is initialized to all ones, and nfree is initialized to NMACHINES.

   (a) It seems that if two people make requests at the two stations at the same time, they will occasionally be assigned the same machine. This problem has resulted in several brawls in the laundromat, and you have been called in by the owner to fix the software. Assume that one thread handles each customer station. Explain how the same washing machine can be assigned to two different customers.

   (b) Modify the code to eliminate the problem.

   (c) Implement your modified code for Nachos.

4. You've just been hired by Mother Nature to help her out with the chemical reaction to form water, which she doesn't seem to be able to get right due to synchronization problems. The trick is to get two H atoms and one O atom all together at the same time. The atoms are threads. Each H atom invokes a procedure hReady when it's ready to react, and each O atom invokes a procedure oReady when it's ready. For this problem, you are to write the code for hReady and oReady. The procedures must delay until there are at least two H atoms and one O atom present, and then one of the procedures must call the procedure makeWater (which just prints out a debug message that water was made). After the makeWater call, two instances of hReady and one instance of oReady should return. Write the code for hReady and oReady using either semaphores or locks and condition variables for synchronization. Your solution must avoid starvation and busy-waiting.