One of the first object oriented languages, Simula, was designed with the purpose of simulating real-life systems. We would be remiss if we did not include at least one simulation in this lab manual.
Create a new directory for the files of this exercise, and in it, save copies of the files ThreadDemo.java, BankLine.java, and CustomerGenerator.java.
Today we will simulate a queuing problem. As customers come into a bank, they will wait in line until a teller can help them. Usually simulations are created to find out some piece of information. For example, a bank manager might like to know how long customers have to wait in line on average. Determining this will be the ultimate goal of our simulation today.
Simulations come in a number of standard forms.
A time slice simulation will take time and split it up into small chunks. During each time slice, all the objects in the simulation in turn will be given a chance to update their state. For example, if we are simulating a rocket, it will update its position and velocity for the new time.
An event driven simulation will use an event queue to moderate what happens when. The event queue stores events in the order in which they are to occur. At each step in the simulation, the first event (earliest in time) in the queue is removed and executed. As a result of that, the appropriate object updates its state and places new events on the queue.
A real time simulation will represent appropriate objects with threads. A thread is a lightweight program. As these threads run, they interact through shared objects. As the threads run they will change the state of objects in the simulation. Often they will put themselves to sleep for a given time if there is nothing they need to do.
As usual, we will apply object-centered design to solve this problem.
Behavior. Customers should come into the bank and be placed in a line. There will be tellers that will take the first person from the front of the line. Our program will periodically report the number of individuals waiting in the line and the average wait time for the ones that have been helped. Our program will keep running until it is stopped.
Objects. Using this behavioral description, we can identify the following objects:
We would like this to be a real time simulation. Therefore, we need to know which of the objects in our simulation will be threads and which will be the objects that they work on. It is easy to see that we want our report generation object to be a thread. We would like a bit of code that at regular intervals prints out a report. This object has the algorithm:
0. Loop
a. Wait N seconds.
b. Print the report.
The customer generation object will also be a thread. Instead of operating at a set interval, however, it should create a new customer at random intervals. As customers are generated they should go into the line.
0. Loop
a. Create a new customer.
b. Put the customer in line.
c. Wait a random number of seconds.
The tellers will be threads in our simulation. As a teller becomes free it will take the first customer in the line. If there are no customers in line, it will wait a short time and look again. They will use the algorithm:
0. Loop
a. Check the line.
b. If there is a customer get it.
A. Determine the transaction time.
B. sleep for the transaction time.
c. otherwise
A. Sleep for a fixed amount of time.
At first glance, it might appear that the customer should be a thread too. But in this simulation, the customer does not need to be an active object. It and the line are serving as the intermediary objects in the simulation. If we where to make the simulation more complicated by allowing a customer to become bored and leave the line, however, it might require a thread.
Therefore, the bank line and the customers will be represented by ordinary classes.
An object will be a thread if it is an instance of a class that extends Thread. Some of the methods that a thread will respond to are:
Usually we would like there to be more than one thread running at a time. On most machines it is not possible for this to happen. Instead, the Java Virtual Machine will moderate, first letting one thread run and then another. The difference between run() and start() is that run does not return until the thread finishes execution. Start will return immediately and allow us to start other threads.
Warning: A number of methods that were originally implemented in the Thread class have been deprecated (in the language but not supported and will be removed eventually) because they were inherently unsafe. If you have old code that uses threads, you should examine it to see if it uses any of those methods.
To see an example of a thread, look at the class CustomerGenerator.java for today's lab. We see that it has a constructor:
public CustomerGenerator(BankLine line, boolean verbose)
which takes in a BankLine and a boolean. The line is the primary object that is shared by all of the threads in the simulation. Each thread needs to have the ability to interact with the line. The boolean variable controls whether the created customer will print a message each time a critical event happens to it. This is useful for testing the simulation.
We also see that it overrides the run() method. The algorithm it uses is:
0. Loop
A. Try
a. Create a new customer.
b. Put the customer in line.
c. Generate a random integer.
d. Sleep the given time.
B. Catch
a. Do nothing.
The argument to the sleep() method is the amount of time in milliseconds that the thread should stop executing. There is no guarantee that the thread will resume executing exactly in that amount of time. The thread may also be interrupted while it is sleeping, in that case an exception of type InterruptedException is thrown and we are forced to handle it.
We do not need to change the start() method, since the one we inherit will do appropriate operations including to invoke the run() method. It is quite typical for a thread to implement just these two methods.
It is time to take a closer look at what our simulation is to do. For this simulation, we will only have one line and two tellers. It will follow the algorithm:
0. Print out a greeting. 1. Create the bank line. 2. Create a teller named Anna. 3. Create a teller named Betty. 4. Create a customer generator. 5. Create a report generator. 6. Start the customer generator. 7. Start the report generator. 8. Start the first teller. 9. Start the second teller.
It is a simple program. We create the bank line first because each of the threads we create will need to interact with it. The threads will each be passed the bank line in their constructor. You can look at the code in ThreadDemo.java.
The primary class that will be used as an intermediary between all our threads is the BankLine class. Each of our threads will need to know about the bank line. We will create it first and pass it as an argument to the constructor of each of the threads we use.
In the design of the BankLine class, we need to know what the responsibilities of the object are. The primary objective of the simulation is to know the average wait time of the customers in the line. Now each customer will be responsible for knowing how long it waited in line, but shouldn't know the average. The customer generator should not need to know when a customer leaves the line. The tellers should not need to know when a customer enters the line. Clearly the bank line will need to know when customers enter and leave the line and so is the natural repository for knowing the number of customers served and the average time that they waited. The list of responsibilities is:
Our class will provide the following methods to support these operations:
Most of these are pretty mundane, but we should take a closer look at the addCustomer() and provideCustomer() methods a little more closely. We will examine the provideCustomer() method first.
synchronized public Customer provideCustomer()
{
if (theLine.size() == 0) return null;
//get the first customer in line
Customer firstInLine = (Customer) theLine.elementAt(0);
theLine.removeElementAt(0);
myTotalWaitTime += firstInLine.outOfLine();
myCustomersServed++;
if(tellAll)
System.out.println("Customer " + firstInLine.name()
+ " was removed from the line " + myName);
return firstInLine;
}
The first thing we notice is that it uses a key word (synchronized) we haven't seen before. Remember that the bank line will be shared by all of the objects in the simulation. This can lead to a situation where more than one thread is executing the same code at the same time. If both our tellers asked the bank line for a customer at the same time we could have serious problems. If both tellers run a copy of the provideCustomer() at the same time, we could have the following situation:
On the face of it, things don't seem too bad. True we have lost one customer and used one twice, but what harm is there in that? But the situation, however, is worse that it seems. We don't operate threads simultaneously but one at a time. Consider the line
myTotalWaitTime += firstInLine.outOfLine();
The first thread could have retrieved the value for myTotalWaitTime in preparation to doing the addition. So some temporary variable will get the value of myTotalWaitTime (call the value X0)
But in the middle of doing this statement, it gets interrupted. Now the other thread runs and it may change myTotalWaitTime many times by adding in wait times for customers. So now the value of myTotalWaitTime will be X1.
Finally, our first thread is woken up again. It asks its customer for the wait time getting some time T. It adds this to the temporary value and then stores the result in myTotalWaitTime. Now myTotalWaitTime has the value X0+ T and all the work done in between has been lost. The two threads have interfered with one another. Clearly, once a thread starts executing the code for provideCustomer(), we don't want it to be interrupted. This is known as a critical section. The synchronized keyword guarantees that only one thread can be in that code at one time.
Similarly, we would like to guarantee that if we put a customer in the line, he won't be removed until we have had a chance to send the inLine() message to the customer. So we will make this method synchronized as well.
synchronized public void addCustomer( Customer newCustomer)
{
theLine.addElement(newCustomer);
newCustomer.inLine();
if(tellAll)
System.out.println("Customer " + newCustomer.name()
+ " was added to line " + myName);
}
We almost have a working simulation. If we create a Customer class we will have enough that we can run a test. A short description of how a customer interacts in the simulation can help us determine the responsibilities. A customer is created by the customer generator and added to the line. The time at which it is added to the line will be recorded. When the customer is taken from the line, that time will be recorded and the difference computed. The customer will interact with a bank teller for some random amount of time.
As always we have choices in our design. Who should be responsible for knowing how long the customer has been waiting in line? We could make that the responsibility of the line. But the line does not have all the needed information. We will decide to make knowing that information the responsibility of the customer. (Note that this is different from knowing the sum of all the wait times, which is the responsibility of the bank line.) Here is a list of the responsibilities for the customer:
Some the methods required are set due to existing code. Implement and add to our project a Customer class in Customer.java. It will need to have the following methods:
public Customer(String name, boolean verbose) - This constructor will need to initialize the private variables and use Math.random() to compute a random transaction time between 1000 and 10000. You can look at the CustomerGenerator for an example. If verbose is true, print that the customer was created along with the transaction time.
public String name() - An accessor for the name of the customer.
public void inLine() - Uses System.currentTimeMillis() to record the time that the customer was placed in line.
public long outOfLine() - Uses System.currentTimeMillis() to record the time that the customer was taken out of the line. It should return the time that the customer has been waiting.
public int serviceTime() - An accessor for the transaction time for the customer.
Compile and test your program. You should see customers being created and added to the line. Do not continue until you get it to work.
We need to create a subclass of Thread for the Teller class. Place the following minimal class definition in Teller.java and add it to your project.
/* Teller.java is a class provides a thread for tellers
*
* Started by: Charles Hoot, for Hands On Java.
* Date: July, 2000
* Finished by:
*****************************************************************/
import Customer;
class Teller extends Thread
{
}
What are the responsibilities of this class?
Define any variables needed to store the attributes of this class and then create the constructor:
public Teller(BankLine line, String name, boolean verbose)
After that implement the method:
public void run(){
using the following algorithm.
0. Loop
A. Try
a. Get a customer from the line.
b. If no customer sleep for some time.
c. If there is a customer
i. If verbose print out helping customer.
ii. Sleep for the transaction time.
iii. If verbose print out finished helping customer
B. Catch
a. Do nothing.
Compile the code for Teller.java to test its syntax. Uncomment the lines in ThreadDemo.java that refer to the Teller class and then compile and test your program. You should see customers being handled by the tellers. Do not continue until you get it to work.
The final task is to create a class that periodically reports on the state of the line. It will need to be a thread and the constructor should have the prototype:
public ReportGenerator(BankLine line, int reportWait)
Implement a run() method for the class as well so that a report will be generated at the interval specified by the reportWait parameter of the constructor.
Uncomment the lines in ThreadDemo.java that refer to the ReportGenerator class and then compile and test your program. If there are errors, correct it, retranslate your source program and then retest your program, until it performs correctly.
Real time simulation, Thread, run(), start(), Interference, Critical section, sleep().
Hard copies of your final versions of Customer.java, Teller.java, and ReportGenerator.java, plus and an execution record showing their execution.
Back to This Lab's Table of Contents
Forward to the Prelab Questions
Forward to the Homework Projects