Assignment #6: Threads and Critical Sections and Low-Level Synchronization

This is a tricky assignment that illustrates threads, synchronization, and critical sections. You will write a simulation of the Ticketmaster Phone system. Here we will assume that there are five lines, but only three operators. When a phone call arrives, we see if there is a free line. If so, the phone rings; otherwise it is busy. Once the phone rings, we wait until there is a free operator, and when we get one, we pretend to get service. Each phone call is represented by a thread, and you will have more threads running than phone lines. There are several components to the project.

Semaphor

First you will complete the Semaphor class. Semaphor.java is your starting point. A Semaphor is use to control entry to a critical section with a limit of how many threads are allowed to be simultaneously in the critical section. (With a normal ReentrantLock, this limit is 1).

To enter the critical section you must gain ownership with acquire, and upon leaving the critical section you should release so a waiting thread can enter. Note: there is a Semaphore class in the Java 1.5 library, but please write your own, for the practice. Do it using Lock and Condition objects. (You can also do it via monitors, and synchronized, but that is old style.) The Semaphor is implemented as follows. First, it maintains the limit of threads concurrently allowed in its critical section, and a Map of the threads (in a HashMap) currently in the cricital section. In the Map, the key represents a thread already in the critical section, and the value represents the number of times the thread has called acquire but not release. In other words, the Semaphor is reentrant. The skeleton is already written, you need to follow the embedded comments to complete the code, and you also need to put in the calls to lock and unlock in appropriate places.

The PhoneCall Class and main

A phone call is represented by a PhoneCall class that contains a caller's id as private data member, set in its constructor. PhoneCall will extend Thread and provide a run method. It will also contain a host of static data members, including semaphors and locks that are shared and control the synchronization. To start with, implement a constructor, and provide a run that simply prints a message, so you know that the thread is running, sleeps for a few seconds (use Thread.sleep), and then prints a message before the thread ends. Later you will do the meaty part of the simulation.

Your main routine will declare an array of threads that will represent each phone call. Then, write a loop that constructs PhoneCall objects to initialize the array. Then, write a loop that starts each PhoneCall thread. When main terminates print a message that the simulation is over. If you run the program, you'll notice that the message comes early. You will want main to block until all the other threads complete and to do that, you should have another loop that uses join on each thread.

The Synchronization

Once you have the threads going, you'll want to do the real part of the simulation. Your PhoneCall class should declare the following static data: 
    private static int NUM_OPERATORS = 3;
    private static int NUM_LINES = 5;
    private static int connected = 0;    // Callers that are connected
    private static Lock connectedLock = new ReentrantLock( );
    private static Semaphor operators = new Semaphor( NUM_OPERATORS );
The variable connected tells how many callers are currently connected (a call attempt is declared busy if connected==NUM_LINES). The main issue is that the test of connected and the subsequent update of connected need to be considered an atomic, single operation (much like in the bank account withdraw method). Access to connected can be controlled by a critical section, and is done by using the connectedLock. The operators semaphor is used once a call connects. Here is a sketch of the run method for PhoneCall:
  1. Print that an attempt to connect has been made
  2. Check if the connection can be made
  3. Wait for an operator to be available (use a semaphor)
  4. Print a message that the order is being taken
  5. Simulate an order by sleeping for a few seconds
  6. Print a message that the order is complete (and update the semaphor)
  7. Update connected
  8. Print a message that the call is over

Test Program

Test your program by running with 10 phone calls. In main, delay the last two phone calls enough so that the line will not be busy.