Requirements
- OOP Principles and Design
- Use List and PriorityQueue from the Java Collections Framework to store the servers and events;
- Packaging the classes into the package cs2030.simulator;
- Program style: adherance to CS2030 Java Style Guide
- Java documentation: adherence to CS2030 Javadoc Specification
Problem Description
A discrete event simulator is a software that simulates a system with events and states, and can be used to study many complex real-world systems such as queuing to order food at McDonalds. An event occurs at a particular time, and each event alters the state of the system and may generate more events. States remain unchanged between two events (hence the term discrete), and this allows the simulator to jump from the time of one event to another. A simulator typically also keeps track of some statistics to measure the performance of the system.
Let us simulate a queuing system comprising only one single customer queue and single service point S as shown below.
The system comprises the following:
- There is one server (a person providing service to the customer); the server can serve one customer at a time.
- The service time (time taken to serve a customer) is constant.
- When a customer arrives (ARRIVE event):
- if the server is idle (not serving any customer), then the server starts serving the customer immediately (SERVE event).
- if the server is serving another customer, then the customer that just arrived waits in the queue (WAIT event).
- if the server is serving one customer, and another customer is waiting in the queue, and a third customer arrives, then the third customer leaves (LEAVE event). In other words, there is at most one customer waiting in the queue.
- When the server is done serving a customer (DONE event), the server can start serving the customer waiting at the front of the queue (if any).
- If there is no waiting customer, then the server becomes idle again.
There are five events in the system, namely ARRIVE, SERVE, WAIT, LEAVE and DONE. For each customer, these are the only possible event transitions:
- ARRIVE SERVE DONE
- ARRIVE WAIT SERVE DONE
- ARRIVE LEAVE
Statistics of the system that we need to keep track of are:
- the average waiting time for customers who have been served
- the number of customers served
- the number of customers who left without being served
As an example, given the arrival times (represented as a floating point value for simplicity) of three customers with one server, and assuming a constant service time of 1.0,
0.5000.6000.700
the following events, each of the form <time_event_occurred, customer_id, event_details>, are produced
0.500 1 arrives0.500 1 served by 10.600 2 arrives0.600 2 waits to be served by 10.700 3 arrives0.700 3 leaves1.500 1 done serving by 11.500 2 served by 12.500 2 done serving by 1
with the end-of-simulation statistics being respectively, [0.450 2 1].
Priority Queuing
The PriorityQueue (a mutable class) can be used to keep a collection of elements, where each element is given a certain priority.
- Elements may be added to the queue with the add(E e) method. The queue is modified;
- The poll() method may be used to retrieve and remove the element with the highest priority from the queue. It returns an object of type E, or null if the queue is empty. The queue is modified.
To enable PriorityQueue to order events, instantiate a PriorityQueue object using the constructor that takes in a Comparator object. For more details, refer to the Java API Specifications.
The Task
Given a set of customer arrival times in chronological order, output the discrete events. Also output the statistics at the end of the simulation.
Take note of the following assumptions:
- The format of the input is always correct;
- Output of a double value, say d, is to be formatted with String.format("%.3f", d);
This task is divided into several levels. Read through all the levels to see how the different levels are related.
You have to complete ALL levels.
Level 1The CustomerWrite an immutable Customer class to represent each arriving customer that is tagged with a customer ID (of type int), as well as an arrival time (of type double). You may write other accessor methods as you deem necessary. jshell> /open Customer.javajshell> new Customer(1, 0.5)$.. ==> 1 arrives at 0.5jshell> new Customer(2, 0.6)$.. ==> 2 arrives at 0.6jshell> new Customer(3, 0.7)$.. ==> 3 arrives at 0.7jshell> /exit |
|||
Level 2The ServerWrite an immutable Server class to represent a server. class Server { ... Server(int identifier, boolean isAvailable, boolean hasWaitingCustomer, double nextAvailableTime) { ... }}
The constructor of Server takes in four parameters:
There are only three possible types of servers to be generated for testing:
jshell> /open Server.javajshell> new Server(1, true, false, 0)$.. ==> 1 is availablejshell> new Server(2, false, false, 0.5)$.. ==> 2 is busy; available at 0.500jshell> new Server(3, false, true, 1.5)$.. ==> 3 is busy; waiting customer to be served at 1.500jshell> /exit |
|||
Level 3EventsTill now we have written two independent Customer and Server classes. How do we link them together? Through events!Each event is an association between a customer and a set of servers. An event will also have the event start time, i.e. for ARRIVE events it will be the arrival time; for SERVE event it will be the time service starts; for DONE event, it will be the time the service ends, etc. All events are to be immutable.In this level, we shall test the event transitions for an arriving customer under different Server configurations. Each test starts off with an ArrivalEvent created using the constructor that takes in the arriving customer, and the list of servers. A transition from one event to the next happens whenever the execute method is called. $ jshell your_java_files_in_bottom-up_dependency_orderjshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, true, false, 0))) // server is available$.. ==> 0.500 1 arrivesjshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, true, false, 0))).execute()$.. ==> 0.500 1 served by 1jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, true, false, 0))).execute().execute()$.. ==> 1.500 1 done serving by 1jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))) // server is busy, but no waiting customer$.. ==> 0.600 2 arrivesjshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))).execute()$.. ==> 0.600 2 waits to be served by 1jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))).execute().execute()$.. ==> 1.000 2 served by 1jshell> new ArriveEvent(new Customer(2, 0.6), Arrays.asList(new Server(1, false, false, 1.0))).execute().execute().execute()$.. ==> 2.000 2 done serving by 1jshell> new ArriveEvent(new Customer(3, 0.6), Arrays.asList(new Server(1, false, true, 1.0))) // server is busy with waiting customer$.. ==> 0.600 3 arrivesjshell> new ArriveEvent(new Customer(3, 0.6), Arrays.asList(new Server(1, false, true, 1.0))).execute()$.. ==> 0.600 3 leavesjshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, false, 0), new Server(2, true, false, 0))).execute() // two servers: (1) busy; (2) free$.. ==> 0.500 1 served by 2jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, false, 0), new Server(2, true, false, 0))).execute().execute()$.. ==> 1.500 1 done serving by 2jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, false, 10.0))).execute() // both servers busy, (1) has waiting customer$.. ==> 0.500 1 waits to be served by 2jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, false, 10.0))).execute().execute()$.. ==> 10.000 1 served by 2jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, false, 10.0))).execute().execute().execute()$.. ==> 11.000 1 done serving by 2jshell> new ArriveEvent(new Customer(1, 0.5), Arrays.asList(new Server(1, false, true, 5.0), new Server(2, false, true, 10.0))).execute() // both busy with waiting customer$.. ==> 0.500 1 leavesjshell> /exit |
|||
Level 4Scheduling EventsWe are finally ready to schedule events using the PriorityQueue.As an example, consider the start of a simulation with an initial schedule of three arrival events, and only one server. 0.500 1 arrives0.600 2 arrives0.700 3 arrives The next event to pick is <0.500 1 arrives>. This schedules a SERVE event. 0.500 1 served by 10.600 2 arrives0.700 3 arrives The next event to pick is <0.500 1 served>. This schedules a DONE event. 0.600 2 arrives0.700 3 arrives1.500 1 done serving by 1 The next event to pick is <0.600 2 arrives>This process is repeated until there are no more events.Define a driver class Main.java that reads a series of arrival times, creates the arrival events, and starts the simulation. A skeleton class that simply reads the arrival times is given below: import java.util.Scanner;class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numOfServers = sc.nextInt(); while (sc.hasNextDouble()) { double arrivalTime = sc.nextDouble(); } }}
The following is a sample run of the program. User input is underlined, and starts with an integer value representing the number of servers, followed by the arrival times of the customers. Input is terminated with a ^D (CTRL-d).You will also need to compute the statistics (see problem description above) at the end of the simulation.
All classes dealing with the simulation should now reside in the cs2030.simulator package, with only the Main class importing the necessary classes from the package.Compile your code using javac -d . *.java and run your program to ensure that everything is still in good working order. |
5/5 – (1 vote)
Reviews
There are no reviews yet.