In all previous assignments we wrote the data structure classes "from scratch", even though we could see that the Java library already contained many similar class. But by writing our own classes when others already existed, we enabled ourselves to implement special purpose data structures which would have all the features we want for a specific application, instead of being restricted to the one-size-fits-all classes in the Java library. Also, but writing the methods we could better appreciate operation efficiency.
But to be well-rounded, at some point we have to learn about the Java library classes. In this lab assignment, we'll use use the java.util.Queue interface. Queue is implemented by the classes java.util.LinkedList and java.util.PriorityQueue. In this assignment we will be using the queue and priority queue classes and interface.
COMPUTER SIMULATION
One particularly useful application of stacks, queues, and priority queues in programming is in the simulation of physical systems.
Simulations have wide application, from the serious, such as simulations of nuclear power plant accidents and atomic bomb explosions, to the entertaining, such as real-time games with life-like Newtonian motion.
Events are stored in priority queues, so that the next event is always readily accessible.
Piles are represented in stacks, for entering and backing out of structures.
Processing of orders is managed by queues, for first-come, first-served processing.
In this assignment you will write a simulation of a customer service operation with multiple servers. The servers are are technical support persons who take phone calls from customers. Each server has his own queue of customers, and line-jumping by customers (when an adjacent line becomes shorter) is not allowed. Servers serve one customer at a time, with no break between customers unless that server's wait queue is empty. Each wait queue has an upper limit in size, and all are the same. When a customer arrives and all queues are full, the customer is turned away (and presumably asked to call back later).
The simulation steps through time minute-by-minute. At the start of any minute, customers may arrive, customers may be moved from their wait queue to a server, and a server may complete a service with a customer. This goes on, and the operator of the simulation observes the results minute-by-minute until the operator chooses to end the simulation.
Customers arrive at the average rate of "n" per minute, where "n" can be a fractional value. Note that if, for example, the average arrival rate of customer calls is 2 per minute, that does not mean that 2 arrive every minute. Sometimes none arrive in a given minute, and other times 5 may arrive -- it's just that the average over time is 2 per minute. Also note that fractional customers cannot happen (without a considerable mess), such as 0.5 per minute (30 per hour). The proper way to handle this is to use the Poisson distribution to generate randoms numbers that represent the #of arrivals each minute.
In the Poisson process, given an average arrival rate of customers, there is a calculable probability of zero arrivals in any given minute, another probability of one, another of two, etc. By the time you add these up towards infility, the total probability is one -- which means one of these is going to happen! In computer simulation we use the random number generator to select the #of arrivals in a minute. It is not the purpose of this assignment to develop this algorithm, so here it is:
private static int getRandomNumberOfArrivals(double averageArrivalsPerMinute)
{
int arrivals = 0;
double probOfnArrivals = Math.exp(-averageArrivalsPerMinute);
for (double randomValue = Math.random();
(randomValue -= probOfnArrivals) > 0.0;
probOfnArrivals *= averageArrivalsPerMinute / (double)++arrivals);
return arrivals;
}
Be sure to test the behavior of this method with a short, separate test, so that you understand how it works.
New customer arrivals are immediately served by any available server. If none are available, the new arrival is placed in the shortest wait queue. If two or more wait queues are of the same size, there is no priority for choosing which to join.
The purpose of the simulation is to determine the average wait time per customer as a function of the number of servers and the time it takes to serve a customer. Here is an excerpt from some representative results:
Time: 400 ---------------------------------- line now servicing waiting queue ---- ------------- --------------- 0 H KPQVYH 1 L RTWZFGL 2 Z BMSXCDIJ 3 F JNOUABEK ---------------------------------- Avg time: 18.962. Turned away per minute: 0.013 Press ENTER to continue, X-ENTER to exit... Time: 401 ---------------------------------- line now servicing waiting queue ---- ------------- --------------- 0 K PQVYHMN 1 L RTWZFGLO 2 Z BMSXCDIJ 3 F JNOUABEK ---------------------------------- Avg time: 18.973. Turned away per minute: 0.012 Press ENTER to continue, X-ENTER to exit...Note that at minute 401 the person being served in line 0 (H) finished being served, and the next in line (K) started being served. Also note that at minute 401 persons M, N, and O arrived, with M and N going to server 0's queue and O going to server 1's. Here are some implementations of this simulation that you can use to familiarize yourself with the way this is to work: UNIX executable and WIN32 executable. Note that these samples get their input from the console, and not from a text file -- your program is to get its input from a text file.
This assignment is worth 40 points, and consists of 1 exercise. Zero points will be awarded for programs with misspelled filenames, or incorrect case. Zero points will be awarded for programs that do not compile or run on the department's UNIX server. Partial points will be awarded for programs that are run but do not conform to all specifications, at the discretion of the grader. Be sure to complete both exercises and post the lab8.jar before midnight of the due date, because there is a 5-point-per-day lateness penalty for late work. Check the course outline for due dates for lab assignments.
Here are the specs:
public static void main
{
// read the input values from a text file, one per line, in the order specified above.
// declare reference variables and create and assign objects to each
create an array of Queue reference objects for the wait queues, and initialize to LinkedLists
create a queue reference for the service event queue, and initialize to a PriorityQueue
create a queue reference for served customers, and initialize to a LinkedList
create an array of customer references, refering to the customers being served at the time by each server
for (int time = 0;; time++)
{
// handle all service events scheduled to take place at this time
while (service event queue is not empty AND time of the top event equals the current time)
{
remove the top service event from the priority queue
determine the server associated with the service event
add this server's current customer to the served customers queue
set that customer's completion time to the current time
set this server's current customer to null
}
// handle new arrivals
get the #of of arrivals from the Poisson process (a whole number >= 0)
for each new arrival
{
if a server is idle, create and add a new customer to that server's wait queue -- in case of a tie, YOU DECIDE WHAT TO DO
else if all lines are full, turn away the customer and add one to the count of turned away customers
else add a new customer to the shortest queue -- in case of a tie, YOU DECIDE WHAT TO DO
}
// for idle servers, move customer from wait queue and begin service
for each server
{
if (server is idle AND server's wait queue is not empty)
{
remove top customer from wait queue and attach to the server
set the customer's servicve time to the current time
use random number generation to determing the amount of time it will take to complete the service
create a new service event for the time that service will be completed for this server and add to priority queue
}
}
// print the summary
print the current time
print a heading for the visual prepresentation of the servers and wait queues
for each server
{
show the ID of the customer being served (or blank if idle)
show the IDs of customers in the wait queue
}
// summarize performance
traverse the queue of served customers to get the average time between arrival and completion, IF ANY
print the rate of customers turned away
// await user decision to continue or exit (SOMETHING LIKE THIS)
String answer;
System.out.println("Press ENTER to continue, X-ENTER to exit...");
answer = cin.readLine();
if (answer.length() > 0 && Character.toUpperCase(answer.charAt(0)) == 'X')
break;
}
}
Create your final version of lab8.jar, with files from this and all previous labs. Post your lab8.jar file to your student UNIX account for grading and credit.
[ Home | Contact Prof. Burns ]