Assigned: May 30
Due: June 8, 11:59pm
| Read the entire assignment before you begin to implement it. You will almost certainly want to read it at least twice, and you will need to come back to it while writing your program. |
| This assignment will take time to write. Do not wait to start on it. Start right away, and try to finish early so that you have time if things do not go according to plan. You will encounter difficulties. If you do not understand something, ask about it. |
| When you read the assignment, you will probably imagine that it is huge, and you might become discouraged in your ability to solve it. It is not as large or difficult as it initially appears. I have written this program, with a total of less than 450 lines, not counting comments, and not counting the part that I provide to you. The methods are short and simple, and most are fairly obvious. In fact, that is the reason that the simulation is broken down the way it is. The architecture makes implementing the simulation easy. |
The assignment is to simulate a bank, with customers arriving and tellers serving them. The simulation should report the following events, along with the times at which they occur.
Report a customer arrival. (When a customer arrives, the customer enters the customer queue.)
Report when a customer steps up to be served by a teller.
Report when a customer is finished being served.
With each event, report the length of the customer queue and the number of idle tellers. For example, a sample run might print the following results. You are not required to use this format, but provide the required information in some readable format.
[ 0.00] Simulation starts [ 0.00] 0 waiting customers [ 0.00] 3 idle tellers [ 5.19] Customer 1 arrives [ 5.19] Teller 1: Start serving customer 1 [ 5.19] 0 waiting customers [ 5.19] 2 idle tellers [ 6.01] Customer 2 arrives [ 6.01] Teller 2: Start serving customer 2 [ 6.01] 0 waiting customers [ 6.01] 1 idle tellers [ 6.36] Customer 3 arrives [ 6.36] Teller 3: Start serving customer 3 [ 6.36] 0 waiting customers [ 6.36] 0 idle tellers [ 6.93] Teller 1: Finished serving customer 1 [ 6.93] 0 waiting customers [ 6.93] 1 idle tellers [ 7.24] Customer 4 arrives [ 7.24] Teller 1: Start serving customer 4 [ 7.24] 0 waiting customers [ 7.24] 0 idle tellers [ 7.64] Teller 3: Finished serving customer 3 [ 7.64] 0 waiting customers [ 7.64] 1 idle tellers [ 8.28] Customer 5 arrives [ 8.28] Teller 3: Start serving customer 5 [ 8.28] 0 waiting customers [ 8.28] 0 idle tellers [ 9.22] Customer 6 arrives [ 9.22] 1 waiting customers [ 9.22] 0 idle tellers [ 10.04] Teller 2: Finished serving customer 2 [ 10.04] Teller 2: Start serving customer 6 [ 10.04] 0 waiting customers [ 10.04] 0 idle tellers [ 10.42] Teller 2: Finished serving customer 6 [ 10.42] 0 waiting customers [ 10.42] 1 idle tellers [ 13.08] Teller 3: Finished serving customer 5 [ 13.08] 0 waiting customers [ 13.08] 2 idle tellers [ 17.22] Teller 1: Finished serving customer 4 [ 17.22] 0 waiting customers [ 17.22] 3 idle tellers [ 17.93] Customer 7 arrives [ 17.93] Teller 2: Start serving customer 7 [ 17.93] 0 waiting customers [ 17.93] 2 idle tellers [ 18.77] Teller 2: Finished serving customer 7 [ 18.77] 0 waiting customers [ 18.77] 3 idle tellers [ 19.86] Customer 8 arrives [ 19.86] Teller 3: Start serving customer 8 [ 19.86] 0 waiting customers [ 19.86] 2 idle tellers [ 22.10] Teller 3: Finished serving customer 8 [ 22.10] 0 waiting customers [ 22.10] 3 idle tellers [ 22.57] Customer 9 arrives [ 22.57] Teller 1: Start serving customer 9 [ 22.57] 0 waiting customers [ 22.57] 2 idle tellers [ 23.97] Customer 10 arrives [ 23.97] Teller 2: Start serving customer 10 [ 23.97] 0 waiting customers [ 23.97] 1 idle tellers [ 24.36] Customer 11 arrives [ 24.36] Teller 3: Start serving customer 11 [ 24.36] 0 waiting customers [ 24.36] 0 idle tellers [ 25.47] Customer 12 arrives [ 25.47] 1 waiting customers [ 25.47] 0 idle tellers [ 26.12] Teller 3: Finished serving customer 11 [ 26.12] Teller 3: Start serving customer 12 [ 26.12] 0 waiting customers [ 26.12] 0 idle tellers [ 26.80] Teller 1: Finished serving customer 9 [ 26.80] 0 waiting customers [ 26.80] 1 idle tellers [ 27.37] Customer 13 arrives [ 27.37] Teller 1: Start serving customer 13 [ 27.37] 0 waiting customers [ 27.37] 0 idle tellers [ 27.40] Customer 14 arrives [ 27.40] 1 waiting customers [ 27.40] 0 idle tellers [ 28.30] Teller 3: Finished serving customer 12 [ 28.30] Teller 3: Start serving customer 14 [ 28.30] 0 waiting customers [ 28.30] 0 idle tellers [ 30.47] Teller 3: Finished serving customer 14 [ 30.47] 0 waiting customers [ 30.47] 1 idle tellers [ 35.46] Customer 15 arrives [ 35.46] Teller 3: Start serving customer 15 [ 35.46] 0 waiting customers [ 35.46] 0 idle tellers [ 36.84] Customer 16 arrives [ 36.84] 1 waiting customers [ 36.84] 0 idle tellers [ 37.16] Teller 3: Finished serving customer 15 [ 37.16] Teller 3: Start serving customer 16 [ 37.16] 0 waiting customers [ 37.16] 0 idle tellers [ 39.40] Teller 3: Finished serving customer 16 [ 39.40] 0 waiting customers [ 39.40] 1 idle tellers [ 39.83] Teller 1: Finished serving customer 13 [ 39.83] 0 waiting customers [ 39.83] 2 idle tellers [ 40.07] Customer 17 arrives [ 40.07] Teller 3: Start serving customer 17 [ 40.07] 0 waiting customers [ 40.07] 1 idle tellers [ 40.27] Customer 18 arrives [ 40.27] Teller 1: Start serving customer 18 [ 40.27] 0 waiting customers [ 40.27] 0 idle tellers [ 42.34] Customer 19 arrives [ 42.34] 1 waiting customers [ 42.34] 0 idle tellers [ 43.62] Teller 2: Finished serving customer 10 [ 43.62] Teller 2: Start serving customer 19 [ 43.62] 0 waiting customers [ 43.62] 0 idle tellers [ 43.78] Customer 20 arrives [ 43.78] 1 waiting customers [ 43.78] 0 idle tellers [ 45.23] Customer 21 arrives [ 45.23] 2 waiting customers [ 45.23] 0 idle tellers [ 45.63] Customer 22 arrives [ 45.63] 3 waiting customers [ 45.63] 0 idle tellers [ 46.07] Customer 23 arrives [ 46.07] 4 waiting customers [ 46.07] 0 idle tellers [ 46.09] Customer 24 arrives [ 46.09] 5 waiting customers [ 46.09] 0 idle tellers [ 48.95] Customer 25 arrives [ 48.95] 6 waiting customers [ 48.95] 0 idle tellers [ 49.38] Customer 26 arrives [ 49.38] 7 waiting customers [ 49.38] 0 idle tellers [ 51.01] Teller 1: Finished serving customer 18 [ 51.01] Teller 1: Start serving customer 20 [ 51.01] 6 waiting customers [ 51.01] 0 idle tellers [ 52.79] Customer 27 arrives [ 52.79] 7 waiting customers [ 52.79] 0 idle tellers [ 54.36] Teller 3: Finished serving customer 17 [ 54.36] Teller 3: Start serving customer 21 [ 54.36] 6 waiting customers [ 54.36] 0 idle tellers [ 54.65] Teller 1: Finished serving customer 20 [ 54.65] Teller 1: Start serving customer 22 [ 54.65] 5 waiting customers [ 54.65] 0 idle tellers [ 54.66] Teller 3: Finished serving customer 21 [ 54.66] Teller 3: Start serving customer 23 [ 54.66] 4 waiting customers [ 54.66] 0 idle tellers [ 56.14] Customer 28 arrives [ 56.14] 5 waiting customers [ 56.14] 0 idle tellers [ 58.87] Teller 3: Finished serving customer 23 [ 58.87] Teller 3: Start serving customer 24 [ 58.87] 4 waiting customers [ 58.87] 0 idle tellers [ 61.22] Customer 29 arrives [ 61.22] 5 waiting customers [ 61.22] 0 idle tellers [ 63.39] Teller 2: Finished serving customer 19 [ 63.39] Teller 2: Start serving customer 25 [ 63.39] 4 waiting customers [ 63.39] 0 idle tellers [ 63.49] Customer 30 arrives [ 63.49] 5 waiting customers [ 63.49] 0 idle tellers [ 63.79] Customer 31 arrives [ 63.79] 6 waiting customers [ 63.79] 0 idle tellers [ 67.13] Customer 32 arrives [ 67.13] 7 waiting customers [ 67.13] 0 idle tellers [ 67.15] Customer 33 arrives [ 67.15] 8 waiting customers [ 67.15] 0 idle tellers [ 67.68] Teller 1: Finished serving customer 22 [ 67.68] Teller 1: Start serving customer 26 [ 67.68] 7 waiting customers [ 67.68] 0 idle tellers [ 68.48] Teller 3: Finished serving customer 24 [ 68.48] Teller 3: Start serving customer 27 [ 68.48] 6 waiting customers [ 68.48] 0 idle tellers [ 71.80] Customer 34 arrives [ 71.80] 7 waiting customers [ 71.80] 0 idle tellers [ 71.99] Teller 1: Finished serving customer 26 [ 71.99] Teller 1: Start serving customer 28 [ 71.99] 6 waiting customers [ 71.99] 0 idle tellers [ 72.71] Customer 35 arrives [ 72.71] 7 waiting customers [ 72.71] 0 idle tellers [ 75.14] Customer 36 arrives [ 75.14] 8 waiting customers [ 75.14] 0 idle tellers [ 75.86] Customer 37 arrives [ 75.86] 9 waiting customers [ 75.86] 0 idle tellers [ 76.84] Customer 38 arrives [ 76.84] 10 waiting customers [ 76.84] 0 idle tellers [ 77.77] Teller 1: Finished serving customer 28 [ 77.77] Teller 1: Start serving customer 29 [ 77.77] 9 waiting customers [ 77.77] 0 idle tellers [ 79.13] Customer 39 arrives [ 79.13] 10 waiting customers [ 79.13] 0 idle tellers [ 80.28] Teller 2: Finished serving customer 25 [ 80.28] Teller 2: Start serving customer 30 [ 80.28] 9 waiting customers [ 80.28] 0 idle tellers [ 80.29] Customer 40 arrives [ 80.29] 10 waiting customers [ 80.29] 0 idle tellers [ 81.17] Teller 1: Finished serving customer 29 [ 81.17] Teller 1: Start serving customer 31 [ 81.17] 9 waiting customers [ 81.17] 0 idle tellers [ 85.06] Customer 41 arrives [ 85.06] 10 waiting customers [ 85.06] 0 idle tellers [ 85.18] Teller 3: Finished serving customer 27 [ 85.18] Teller 3: Start serving customer 32 [ 85.18] 9 waiting customers [ 85.18] 0 idle tellers [ 86.01] Customer 42 arrives [ 86.01] 10 waiting customers [ 86.01] 0 idle tellers [ 86.35] Teller 3: Finished serving customer 32 [ 86.35] Teller 3: Start serving customer 33 [ 86.35] 9 waiting customers [ 86.35] 0 idle tellers [ 86.59] Customer 43 arrives [ 86.59] 10 waiting customers [ 86.59] 0 idle tellers [ 86.94] Customer 44 arrives [ 86.94] 11 waiting customers [ 86.94] 0 idle tellers [ 86.98] Customer 45 arrives [ 86.98] 12 waiting customers [ 86.98] 0 idle tellers [ 87.14] Customer 46 arrives [ 87.14] 13 waiting customers [ 87.14] 0 idle tellers [ 87.17] Customer 47 arrives [ 87.17] 14 waiting customers [ 87.17] 0 idle tellers [ 87.38] Customer 48 arrives [ 87.38] 15 waiting customers [ 87.38] 0 idle tellers [ 90.58] Customer 49 arrives [ 90.58] 16 waiting customers [ 90.58] 0 idle tellers [ 90.83] Teller 2: Finished serving customer 30 [ 90.83] Teller 2: Start serving customer 34 [ 90.83] 15 waiting customers [ 90.83] 0 idle tellers [ 92.85] Customer 50 arrives [ 92.85] 16 waiting customers [ 92.85] 0 idle tellers [ 93.94] Customer 51 arrives [ 93.94] 17 waiting customers [ 93.94] 0 idle tellers [ 94.03] Customer 52 arrives [ 94.03] 18 waiting customers [ 94.03] 0 idle tellers [ 94.65] Customer 53 arrives [ 94.65] 19 waiting customers [ 94.65] 0 idle tellers [ 95.15] Customer 54 arrives [ 95.15] 20 waiting customers [ 95.15] 0 idle tellers [ 95.19] Teller 1: Finished serving customer 31 [ 95.19] Teller 1: Start serving customer 35 [ 95.19] 19 waiting customers [ 95.19] 0 idle tellers [ 98.62] Customer 55 arrives [ 98.62] 20 waiting customers [ 98.62] 0 idle tellers [ 99.62] Customer 56 arrives [ 99.62] 21 waiting customers [ 99.62] 0 idle tellers [ 100.31] Customer 57 arrives [ 100.31] Simulation done
The input format is described below. The input comes from the standard input (cin) and all output should go to the standard output (cout). You can use either cout or printf to do output.
Use an object-oriented approach. There should be objects in your program that correspond to objects in the simulation. For example, each customer should be an object and each teller should be an object. Use the following classes. (You can choose different names for them, but keep the general intent.)
Class SimObject. This is an abstract class that represents an object that can occupy a spot in a queue in the bank. It has no information.
Class Customer. This is a subclass of SimObject. An object of class Customer represents a customer. Its job is to hold a customer number and a transaction duration, indicating how long this customer needs to talk to a teller.
Class Teller. This is a subclass of SimObject. An object of class Teller represents a teller. Its job is to hold a teller number, and to report when it starts and ends a transaction.
Class Event. An object of class Event represents an event that can happen in the simulation. It is an abstract class. Subclasses of Event are particular events.
Class CustomerArrivalEvent. This is a subclass of Event. An object of class CustomerArrivalEvent represents an event in which a customer arrives at the bank and enters the customer queue.
Class CustomerServiceEvent. This is a subclass of Event. An object of class CustomerServiceEvent represents an event in which a customer leaves the customer queue and begins talking to a teller.
Class ServiceEndEvent. This is a subclass of Event. An object of class ServiceEndEvent represents an event in which a customer finishes talking to a teller and leaves the bank.
Class Bank. There will be just one object of class Bank. Its job is to hold: a customer queue; a teller queue (holding idle tellers); and an event queue holding pending events. It has a method that performs the simulation, and a method to schedule an event into its event queue.
Class Queue. An object of class Queue is a queue that can hold SimObjects. There will be one queue for the customer queue (holding objects of class Customer) and another for the teller queue (holding objects of class Teller).
Class PQueue. An object of class PQueue is a priority queue holding objects of class Event. There will be one object of class PQueue: the event queue. The priority is the time at which the event will occur. When you remove an event, you want to remove the next one that will occur, so you want the one with the smallest time.
Class Random. You need to generate apparently random numbers, to choose when customers arrive and how long their transactions take. Class Random provides yo with pseudo-random numbers.
Additionally, there will be a module that contains the main program that starts the simulation.
A customer holds a customer number (type int); a transaction duration (type double), telling how long this customer needs to talk to a teller; and a pointer to the bank.
There should be one constructor that takes two parameters: a pointer to the bank, and an average transaction duration. The constructor should choose a transaction duration at random, with the given average, and should get the next available customer number. Just remember the pointer to the bank.
You can use a global variable in the customer module holding the next available customer number. Add 1 to it every time a customer is created.
Provide a method to get the transaction duration and a method to get the customer number. Also provide a print method that prints "customer k", where k is the customer number.
Write the customer class in file Customer.h, and its implementation in file Customer.cpp.
A teller holds a teller number (type int) and a pointer to the bank.
There should be one constructor that takes one parameter: a pointer to the bank. The constructor should get the next available customer number, and should remember the pointer to the bank.
You can use a global variable in the teller module holding the next available teller number. Add 1 to it every time a teller is created.
Provide a method to get the teller number. Also provide a print method that prints "teller k", where k is the teller number.
Provide two methods for printing events: one that prints that the teller is beginning to serve a customer, and one that prints that the teller is done serving a customer. Each will need to take the customer as a parameter.
Write the customer class in file Teller.h, and its implementation in file Teller.cpp.
The SimObject class is an abstract superclass of the Customer and Teller classes. It should have one pure virtual method, print(), that prints a brief description of the object. See the Customer and Teller classes.
Provide only file simobject.h, holding the class definition. There is no implementation.
You can use the following queue class. It assumes that your SimObject class is called SimObject.
An event holds a pointer to the bank.
There should be one constructor that takes one parameter: a pointer to the bank. It should just install that pointer into the bank pointer variable.
Pure virtual method happen( ) should cause the event to happen. What it does depends on the subclass.
Pure virtual method print( ) should print a brief description of the event. (It is only useful for debugging.)
Write the event class in file Event.h. There is no need for Event.cpp. Just write the constructor in the class.
CustomerArrivalEvent is a subclass of Event.
A customer arrival event object holds a pointer to the customer who is arriving. Since it is a subclass of Event, it also contains a pointer to the bank. (But do not declare that in this class. It is inherited.)
There should be one constructor that takes two parameters: a pointer to a customer and a pointer to the bank. It should run the Event constructor to install the pointer to the bank, and should remember the pointer to the customer.
Method happen( ) should: print that the customer has arrived; put the customer into the bank's customer queue; create a new customer and a new customer event; and schedule the new customer to arrive at a randomly selected time in the future.
To determine when the next customer arrives, ask the bank to tell you its customer average customer arrival interval. (See class Bank.) Get a pseudo-random number from the pseudo-random number generator.
Method print( ) should print a brief description of the event. For example, it might print "Arrival event for customer k".
Write the CustomerArrivalEvent class in file CustomerArrivalEvent.h, and the method implementations in CustomerArrivalEvent.cpp.
CustomerServiceEvent is a subclass of Event.
A customer service event object holds a pointer to the customer who is to be served and a pointer to the teller who is serving the customer. Since it is a subclass of Event, it also contains a pointer to the bank. (But do not declare that in this class. It is inherited.)
There should be one constructor that takes three parameters: a pointer to a customer, a pointer to a teller and a pointer to the bank. It should run the Event constructor to install the pointer to the bank, and should remember the pointer to the customer and the teller.
Method happen( ) should print that the customer is being served, and tell which teller is serving this customer (by asking the teller to do this);
Method print( ) should print a brief description of the event.
Write the CustomerServiceEvent class in file CustomerServiceEvent.h, and the method implementations in CustomerServiceEvent.cpp.
ServiceEndEvent is a subclass of Event.
A service end event object holds a pointer to the customer who has been served and a pointer to the teller who is finished serving the customer. Since it is a subclass of Event, it also contains a pointer to the bank.
There should be one constructor that takes three parameters: a pointer to a customer, a pointer to a teller and a pointer to the bank. It should run the Event constructor to install the pointer to the bank, and should remember the pointer to the customer and the teller.
Method happen( ) should: print that the customer is done being served, and tell which teller is done (by asking the teller to do this printing); and add the teller to the bank's teller queue.
Method print( ) should print a brief description of the event.
Write the ServiceEndEvent class in file ServiceEndEvent.h, and the method implementations in ServiceEndEvent.cpp.
The event queue is a priority queue. You can use the following implementation of class PQueue.
A bank object should hold
There should be one constructor that takes three parameters: the number of tellers, the average customer arrival interval, and the average customer transaction time. It should create the queues and store the information from the parameters. It should create the tellers, and insert them into the teller queue.
Method simulate(startTime, endTime) should perform the simulation, starting at time startTime, and ending at time endTime. It should start by creating a new customer and a new customer arrival event, and inserting the customer arrival event into the event queue. Then it should enter a loop where it does the following.
Provide a method to schedule an event a given amount of time in the future (from the current time). It should take two parameters: a pointer to the event and a real number telling how far in the future the event should happen.
Provide methods to return the average customer arrival time and the average transaction time and the current time of day.
Provide a method to print the time of day, in some standard form, such as "[ t]", where t is the time.
You will probably want other methods to help. Make them sensible, with the goal of making all of the methods clear and fairly short.
Write the Bank class in file Bank.h, and the method implementations in Bank.cpp.
A pseudo-random number generator does not really produce random numbers at all. It returns a sequence of numbers that appear to be random. You can use the following class, which is based on the random method in the C standard library.
A uniform distribution gives the same probability to every number in a given range.
There is a different distribution, however, that tends to model real situations in simulations more accurately. To understand that other distribution, imagine choosing a small interval of time, such as one second, and asking whether a customer arrives during that interval. Suppose that the probability that a customer arrives during a given second is small.
If the customer arrival time were uniformly distributed, then, the more seconds without a customer that you see, the more likely it becomes that a customer will arrive in the next second. For example, imagine that you choose the arrival time to be uniformly distributed between 1 second and 120 seconds. In the first second, the probability of an arrival is 1/120. But if you have waited for 110 seconds, and no customer has arrived, then the likelihood of an arrival in the next second is 1/10. The longer you wait without an arrival, the more likely an arrival in the next second becomes.
A memoryless distribution, on the other time, keeps the probability of an arrival occurring during a given second the same, regardless of what has happened in the past. This is similar to radioactive decay of an unstable atomic nucleus. The nucleus does not remember how long it has existed, and the probability of it decaying in a given interval does not depend on how old the nucleus is.
Customer arrivals at a bank are eratic, not regular. There is nothing that indicates the probability of a customer arrival in the next second should be higher just because there was not one in the previous few seconds. Sometimes, two customers arrive at almost the same moment. Sometimes, there is a longer gap between customers. So we use a memoryless distribution for customer arrivals. It also makes sense to use that distribution for the distribution of transaction times.
A memoryless distribution is also called an exponential distribution. The Random class provides method Random::exponentialRandom(mean), which returns an exponentially distributed pseudo-random value with the given mean. Use that method to get the random time until the next customer arrival, and to select the random transaction time. For example,
double t = Random::exponentialRandom(bank->getAverageTransactionTime());would set t to a random transaction time.
The sequence of numbers produced by a pseudo-random number generator depends on its seed. If you use the same seed twice in a row, you will get exactly the same sequence of numbers. To set the seed, choose an integer n and do
Random::setseed(n);Do this only once, to initialize the random number generator.
The main program should read information from the standard input about the simulation, then create a bank and ask the bank to perform the simulation. The input format should be as follows.
| Number of tellers |
| Average arrival interval |
| Average transaction time |
| Start time |
| End time |
| Seed |
For example, input
2 5.0 10.0 0.0 100.0 7547104requests a simulation with 2 tellers, starting at time 0.0 and ending at time 100.0. The customers arrive, on the average, one every 5.0 minutes. The average transation takes 10.0 minutes. The random number generator is initialized by setting its seed to 7547104.
Here is a makefile that will build your program. It calls the executable program simulate, and assumes that the main program is in file simulate.cpp. You can modify it if you like.
Copy Makefile to the directory where your program is located. To build the program, use commandmakeTo remove all machine-generated files, use
make clean
Put all of your files in a directory for this assignment. Before submitting, move any extraneous .h or .cpp files to a different directory. Log into one of the Unix computers in the lab, and change your directory to the directory that contains your assignment. For example, use command
cd Assignment2Now use the following command to submit the assignment.
~karl/3310/bin/submit L2 *.h *.cpp