Lab #3
In the previous lab, we designed a discrete event simulator to simulate the changes in the state of a system across
time, with each transition from one state of the system to another triggered via an event. Simulation statistics are also
typically tracked to measure the performance of the system.
Such a system can be used to study many complex real-world systems such as queuing to order food at a fast-food
restaurant. The following illustrates a multi-queue-multi-server system:
● There are n servers with its own queue.
● Each server can serve one customer at a time.
● Each customer has a service time (time taken to serve the customer).
● When a customer arrives (ARRIVE event):
○ the servers are scanned from 1 to n to find the first one that is idle (not serving any customer). This
server starts serving the customer immediately (SERVE event).
○ the server is done (DONE event) after serving the customer.
○ if all servers are serving customers, then the customer that just arrived scans the queues from 1 to
n, joins the first queue that is not full (not necessarily the shortest) and waits in the queue (WAIT
event). Note that a customer that chooses to queue joins at the end of the queue.
○ if all servers are serving customers and all queues are full of waiting customers, then a new
customer that arrives, just leaves (LEAVE event).
● If there is no waiting customer, then the server becomes idle again.
Notice from the above description that 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
In essence, an event is tied to one customer. Depending on the current state of the system, triggering an event will
result in the next state of the system, and possibly the next event. Events are also processed via a queue. At the start
of the simulation, the queue only contains the customer arrival events. With every simultation time step, an event is
retrieved from the queue to be processed, and any resulting event added to the queue. This process is repeated until
there are no events left in the queue.
As an example, given an input of one server with a maximum queue length of 1 (i.e. only one waiting customer is
allowed), followed by the arrival and assuming that service times is 1.0,
1 1
0.500
0.600
0.700
the entire similation run results in the following output:
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 waits at 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 serves by 1
2.500 2 done serving by 1
Finally, statistics of the system that we need to keep track of are:
1. the average waiting time for customers who have been served;
2. the number of customers served;
3. the number of customers who left without being served.
In our example, the end-of-simulation statistics are respectively, [0.450 2 1].
On-Demand Service Time
Moreover, it is unrealistic that service time has to be pre-determined before the customer is being served. In the
above example, customer 3 would not be served and hence a service time need not be specified. To faciliate
on-demand data (or delayed data), we make use of the Supplier interface which specifies an abstract method get() to
be defined by its implementation class.
As an example using JShell, the following Supplier implementation can be defined that generates a service time (say,
a constant 1.0)
jshell> class DefaultServiceTime implements Supplier<Double> {
...> public Double get() {
...> System.out.println("generating service time..."); // output for tracing purposes
...> return generateServiceTime(); // some method that returns 1.0
...> }
...> }
| created class DefaultServiceTime
DefaultServiceTime can be used in a simple Customer class as follows:
jshell> class Customer {
...> private final Supplier<Double> serviceTime;
...> Customer(Supplier<Double> serviceTime) {
...> this.serviceTime = serviceTime;
...> }
...> double getServiceTime() {
...> return this.serviceTime.get();
...> }
...> }
| created class Customer
jshell> DefaultServiceTime serviceTime = new DefaultServiceTime()
serviceTime ==> DefaultServiceTime@52cc8049
jshell> Customer adele = new Customer(serviceTime) // adele is created first
adele ==> Customer@1753acfe
jshell> Customer billie = new Customer(serviceTime)
billie ==> Customer@2a2d45ba
jshell> Customer charlie = new Customer(serviceTime)
charlie ==> Customer@34c45dca
jshell> billie.getServiceTime() // billie is the first to get a service time
generating service time...
$.. ==> 1.0
jshell> adele.getServiceTime()
generating service time...
$.. ==> 1.0
Notice that even though adele is being created first before billie, the latter invokes getServiceTime (and hence
generateServiceTime) first. Moreover, charlie is created but no service time is generated.
Also notice that rather than having Customer depend on DefaultServiceTime directly, it is dependent on the Supplier
interface instead. Doing this allows the program to accept different types of Supplier<Double> implementations. In
this lab, you can make use of DefaultServiceTime since the sample run below assumes a default service time of 1.0.
Task
The utility classes Pair, PQ and ImList have been provided to you. Moreover, the Main client with DefaultServiceTime
are provided for you.
/**
* This utility class stores two items together in a pair.
* It could be used, for instance, to faciliate returning of
* two values in a function.
*
* @author cs2030
* @param <T> the type of the first element
* @param <U> the type of the second element
**/
public class Pair<T, U> {
private final T t;
private final U u;
/**
* Creates a {@code Pair} of items.
*
* @param t first item of the pair
* @param u second item of the pair
**/
public Pair(T t, U u) {
this.t = t;
this.u = u;
}
/**
* Returns the first item of the pair.
*
* @return the first item of the pair
*/
public T first() {
return this.t;
}
/**
* Returns the second item of the pair.
*
* @return the second item of the pair
*/
public U second() {
return this.u;
}
/**
* Returns a string representation of this pair enclosed in ({@code "()"}).
* The two elements are separated by the characters {@code ", "} (comma and space).
* Elements are converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
*/
@Override
public String toString() {
return "(" + this.t + ", " + this.u + ")";
}
}
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* An immutable and unbounded priority queue based on a priority heap.
* The elements of the priority queue are ordered according to their
* a {@link Comparator} provided at queue construction time. A priority
* queue does not permit {@code null} elements.
*
* <p>The <em>head</em> of this queue is the <em>least</em> element
* with respect to the specified ordering. If multiple elements are
* tied for least value, the head is one of those elements -- ties are
* broken arbitrarily. The queue retrieval operation {@code poll},
* access the element at the head of the queue.
*
* <p>A priority queue is unbounded, but has an internal
* <i>capacity</i> governing the size of an array used to store the
* elements on the queue. It is always at least as large as the queue
* size. As elements are added to a priority queue, its capacity
* grows automatically. The details of the growth policy are not
* specified.
*
* @author cs2030
* @param <E> the type of elements held in this queue
*/
public class PQ<E> {
private final PriorityQueue<E> pq;
/**
* Creates a {@code PQ} with the default initial capacity and
* whose elements are ordered according to the specified comparator.
*
* @param comparator the comparator that will be used to order this
* priority queue.
*/
public PQ(Comparator<? super E> comparator) {
this.pq = new PriorityQueue<E>(comparator);
}
private PQ(PQ<E> source) {
this.pq = new PriorityQueue<E>(source.pq);
}
/**
* Returns {@code true} if this collection contains no elements.
*
* @return {@code true} if this collection contains no elements
*/
public boolean isEmpty() {
return this.pq.isEmpty();
}
/**
* Inserts the specified element into this priority queue.
*
* @param element the element to be added to the priority queue
* @return the priority queue with the element added
*/
public PQ<E> add(E element) {
PQ<E> copy = new PQ<E>(this);
copy.pq.add(element);
return copy;
}
/**
* Retrieves and removes the head of this queue,
* or returns {@code null} if this queue is empty.
*
* @return the head of this queue, and the resulting priority queue
* after removal as a {@code Pair}
*/
public Pair<E, PQ<E>> poll() {
PQ<E> copy = new PQ<E>(this);
E t = copy.pq.poll();
return new Pair<E,PQ<E>>(t, copy);
}
/**
* Returns a string representation of this priority queue. The string
* representation consists of a list of elements in the order they are
* returned by its iterator, enclosed in square brackets ({@code "[]"}).
* Adjacent elements are separated by the characters {@code ", "} (comma and space).
* Elements are converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
*/
@Override
public String toString() {
return this.pq.toString();
}
}
import java.util.List;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Iterator;
/**
* An immutable implementation of the {@code ArrayList} using an
* immutable delegation design pattern.
*
* @author cs2030
* @param <E> the type of elements in this list
*/
public class ImList<E> implements Iterable<E> {
private final List<E> elems;
/**
* Constructs an empty list.
*/
public ImList() {
this.elems = new ArrayList<E>();
}
/**
* Constructs a list containing the elements of the specified list of
* type {@code List}, in the order they are returned by the latter's
* iterator.
*
* @param list the list whose elements are to be placed into this list
* @throws NullPointerException if the specified list is null
*/
public ImList(List<? extends E> list) {
this.elems = new ArrayList<E>(list);
}
/**
* Appends the specified element to the end of this list.
*
* @param elem element to be appended to this list
* @return the list with the element added
*/
public ImList<E> add(E elem) {
ImList<E> newList = new ImList<E>(this.elems);
newList.elems.add(elem);
return newList;
}
/**
* Appends all of the elements in the specified immutable list to
* the end of this list, in the order that they are returned by the
* specified list's Iterator.
*
* @param list list containing elements to be added to this list
* @return the list with the all elements of the specified list appended
* @throws NullPointerException if the specified collection is null
*/
public ImList<E> addAll(ImList<? extends E> list) {
return this.addAll(list.elems);
}
/**
* Appends all of the elements in the specified (@code List) list to
* the end of this list, in the order that they are returned by the
* specified list's Iterator.
*
* @param list list containing elements to be added to this list
* @return the list with the all elements of the specified list appended
* @throws NullPointerException if the specified collection is null
*/
public ImList<E> addAll(List<? extends E> list) {
ImList<E> newList = new ImList<E>(this.elems);
newList.elems.addAll(list);
return newList;
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
return this.elems.get(index);
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index {@code i} such that
* {@code Objects.equals(obj, get(i))},
* or -1 if there is no such index.
*
* @param obj element to search for
* @return the index of the first occurrence of the specified element in
* this list, or -1 if this list does not contain the element
*/
public int indexOf(Object obj) {
return this.elems.indexOf(obj);
}
/**
* Returns {@code true} if this list contains no elements.
*
* @return {@code true} if this list contains no elements
*/
public boolean isEmpty() {
return this.elems.isEmpty();
}
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return this.elems.iterator();
}
/**
* Removes the element at the specified position in this list.
*
* @param index the index of the element to be removed
* @return the list after removal of the element
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ImList<E> remove(int index) {
if (index < 0 || index >= this.size()) {
return this;
}
ImList<E> newList = new ImList<E>(this.elems);
newList.elems.remove(index);
return newList;
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param elem element to be stored at the specified position
* @return the list after replacement of the element
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ImList<E> set(int index, E elem) {
if (index < 0 || index >= this.size()) {
return this;
}
ImList<E> newList = new ImList<E>(this.elems);
newList.elems.set(index, elem);
return newList;
}
/**
* Returns the number of elements in this list.
*
* @return the number of elements in this list
*/
public int size() {
return this.elems.size();
}
/**
* Sorts this list according to the order induced by the specified
* {@link Comparator}. The sort is <i>stable</i>: this method must not
* reorder equal elements.
*
* <p>All elements in this list must be <i>mutually comparable</i> using the
* specified comparator (that is, {@code c.compare(e1, e2)} must not throw
* a {@code ClassCastException} for any elements {@code e1} and {@code e2}
* in the list).
*
* <p>If the specified comparator is {@code null} then all elements in this
* list must implement the {@link Comparable} interface and the elements'
* {@linkplain Comparable natural ordering} should be used.
*
* @param cmp the {@code Comparator} used to compare list elements.
* A {@code null} value indicates that the elements'
* {@linkplain Comparable natural ordering} should be used
* @return the sorted list
* @throws ClassCastException if the list contains elements that are not
* <i>mutually comparable</i> using the specified comparator
* @throws UnsupportedOperationException if the list's list-iterator does
* not support the {@code set} operation
* @throws IllegalArgumentException
* (<a href="Collection.html#optional-restrictions">optional</a>)
* if the comparator is found to violate the {@link Comparator}
* contract
*/
public ImList<E> sort(Comparator<? super E> cmp) {
ImList<E> newList = new ImList<E>(this.elems);
newList.elems.sort(cmp);
return newList;
}
/**
* Returns a string representation of this list. The string
* representation consists of a list of elements in the order they are
* returned by its iterator, enclosed in square brackets ({@code "[]"}).
* Adjacent elements are separated by the characters {@code ", "} (comma and space).
* Elements are converted to strings as by {@link String#valueOf(Object)}.
*
* @return a string representation of this list
*/
@Override
public String toString() {
return this.elems.toString();
}
}
import java.util.Scanner;
import java.util.function.Supplier;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ImList<Double> arrivalTimes = new ImList<Double>();
Supplier<Double> serviceTime = new DefaultServiceTime();
int numOfServers = sc.nextInt();
int qmax = sc.nextInt();
while (sc.hasNextDouble()) {
arrivalTimes = arrivalTimes.add(sc.nextDouble());
}
Simulator sim = new Simulator(numOfServers, qmax, arrivalTimes, serviceTime);
System.out.println(sim.simulate());
sc.close();
}
}
import java.util.function.Supplier;
class DefaultServiceTime implements Supplier<Double> {
public Double get() {
return 1.0;
}
}
import java.util.Scanner;
import java.util.function.Supplier;
class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
ImList<Double> arrivalTimes = new ImList<Double>();
Supplier<Double> serviceTime = new DefaultServiceTime();
int numOfServers = sc.nextInt();
int qmax = sc.nextInt();
while (sc.hasNextDouble()) {
arrivalTimes = arrivalTimes.add(sc.nextDouble());
}
Simulator sim = new Simulator(numOfServers, qmax, arrivalTimes, serviceTime);
System.out.println(sim.simulate());
sc.close();
}
}
Sample runs of the program is given below. All of them assumes a default service time of 1.0. You should create your
own input files using vim. You may also create other implementations of Supplier<Double> to test out different service
times. Note that your program will be tested against test cases where the service times could be different when
serving different customers.
$ cat 1.in
1 1
0.500
0.600
0.700
$ java Main < 1.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 waits at 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 serves by 1
2.500 2 done serving by 1
[0.450 2 1]
$ cat 2.in
1 1
0.500
0.600
0.700
1.500
1.600
1.700
$ java Main < 2.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 waits at 1
0.700 3 arrives
0.700 3 leaves
1.500 1 done serving by 1
1.500 2 serves by 1
1.500 4 arrives
1.500 4 waits at 1
1.600 5 arrives
1.600 5 leaves
1.700 6 arrives
1.700 6 leaves
2.500 2 done serving by 1
2.500 4 serves by 1
3.500 4 done serving by 1
[0.633 3 3]
$ cat 3.in
2 1
0.500
0.600
0.700
1.500
1.600
1.700
$ java Main < 3.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 serves by 2
0.700 3 arrives
0.700 3 waits at 1
1.500 1 done serving by 1
1.500 3 serves by 1
1.500 4 arrives
1.500 4 waits at 1
1.600 2 done serving by 2
1.600 5 arrives
1.600 5 serves by 2
1.700 6 arrives
1.700 6 waits at 2
2.500 3 done serving by 1
2.500 4 serves by 1
2.600 5 done serving by 2
2.600 6 serves by 2
3.500 4 done serving by 1
3.600 6 done serving by 2
[0.450 6 0]
$ cat 4.in
2 2
0.500
0.600
0.700
1.500
1.600
1.700
$ java Main < 4.in
0.500 1 arrives
0.500 1 serves by 1
0.600 2 arrives
0.600 2 serves by 2
0.700 3 arrives
0.700 3 waits at 1
1.500 1 done serving by 1
1.500 3 serves by 1
1.500 4 arrives
1.500 4 waits at 1
1.600 2 done serving by 2
1.600 5 arrives
1.600 5 serves by 2
1.700 6 arrives
1.700 6 waits at 1
2.500 3 done serving by 1
2.500 4 serves by 1
2.600 5 done serving by 2
3.500 4 done serving by 1
3.500 6 serves by 1
4.500 6 done serving by 1
[0.600 6 0]
Some design tips...
● Make use of polymorphism instead of checking the type of event in the simulator class:
○ Your event class should have a method that returns another type of event. If you need to return
more values, consider putting into a pair.
○ Each event will transit into the next event, e.g. a serve will transit to a done event after running the
method above.
○ Terminating events (done and leave) can return itself since there is no event to transit to.
● In your design, only invoke getServiceTime() in one location. Invoking in multiple locations may result in
wrong service time.
● Consider how you would emulate a queue for each server.
● Avoid having multiple events with the same customer in the PQ, i.e. the PQ should contain only one event
per customer.
版权所有：编程辅导网 2021 All Rights Reserved 联系方式：QQ:99515681 微信：codinghelp 电子信箱：99515681@qq.com
免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。
