The purpose of this homework is to help you understand how semaphores, monitors, and condition variables can be used to handle concurrency.

The local laundromat has just entered the computer age. As each customer enters, he or she puts coins into slots at one of several 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 a boolean array available[NMACHINES] to represent if 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.

The available array is initialized to all true, and nfree is initialized to NMACHINES. For each machine that the user has requested from a station, the station invokes the allocate procedure before issuing a token.

int allocate() /* Returns index of available machine.*/
{

P(nfree); /* Wait until a machine is available */
for (int i=0; i < NMACHINES; i++)
    if (available[i] == TRUE) {
        available[i] = FALSE;
        return i;     }
}

void release(int machine) /* Releases machine */
{

available[machine] = TRUE;
V(nfree); }
 
 

After a few weeks of operation, two types of problems have started appearing:
  1. 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 has resulted in several brawls in the laundromat.
  2. Occasionally, people "get stuck" at the request stations waiting for the tokens to be issued. The owner has had to take tokens from one user and give them to another one. This problem usually happens when a large number of people show up and each requests a large number of machines.
You have been called in by the owner to fix these problems. Assume that one thread handles each of the customer stations.
  1. Explain how the first problem can occur: the same washing machine is assigned to two different customers. Modify the code to eliminate the first problem.
  2. Explain what the second problem is and why it occurs: the system fails because people get stuck waiting for machines. Using alternative concurrency control primitives implement allocation and release procedures that ensure both that a person is allocated all the washers they’ve requested at one time, and each washer is allocated to only one person. (Hint: for the convenience of the patrons, the owner is willing to provide patrons with an area for them to "sleep" while they wait for their set of washers).