Lab 4

2276 words, 12 min read
Last updated on

You have been designing 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. 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 is served with a different service time.
  • When a customer arrives,
    • he/she finds the first idling server (not serving any customer);
    • if all servers are serving customers, then the customer joins the first available queue;
    • if all queues are full, he/she leaves.

This lab comprises only two levels: the first focuses on varying service times (assume each server with queue length of zero); and the second addressing queuing customers.

Level 1 (to be completed during the lab)

We now generate a different service time, only when it is needed. To faciliate such on-demand (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, the following Supplier implementation can be defined that generates service times based on a mutable priority queue.

jshell> PriorityQueue pq = new PriorityQueue( …> List.of(1.0,2.0,3.0)) pq ⇒ [1.0, 2.0, 3.0]

jshell> class ServiceTime implements Supplier { …> public Double get() { …> System.out.println(“generating service time…”); // for tracing purposes …> return pq.poll(); …> } …> } | created class ServiceTime

Each time a service time is needed, we call the supplier’s get method. As an example, suppose we have the following simplified Customer and Server classes.

jshell> class Customer { …> private final int id; …> Customer(int id) { …> this.id = id; …> } …> public String toString() { …> return “customer ” + this.id; …> } …> } | created class Customer

jshell> class Server { …> private final int id; …> private final Supplier serviceTime; …> Server(int id, Supplier serviceTime) { …> this.id = id; …> this.serviceTime = serviceTime; …> } …> void serve(Customer c) { …> System.out.println(this + ” serves ” + c + ” for ” + serviceTime.get()); …> } …> public String toString() { …> return “server ” + this.id; …> } …> } | created class Server

jshell> List customers = List.of( …> new Customer(1), new Customer(2), new Customer(3)) customers ⇒ [customer 1, customer 2, customer 3]

jshell> Server s1 = new Server(1, new ServiceTime()) s1 ⇒ server 1

Now suppose customer 3 is served first then followed by customer 1, and assume customer 2 leaves. Then

jshell> s1.serve(customers.get(2)) generating service time… server 1 serves customer 3 for 1.0

jshell> s1.serve(customers.get(0)) generating service time… server 1 serves customer 1 for 2.0

Notice that the sequence of service times are used on demand, irrespective of the ordering of customer arrivals.

The utility classes InfList, Maybe, Pair and PQ have been provided to you. The Java API for these classes can be found using this link. You will also be making use of the Main class below:

import java.util.Scanner; import java.util.function.Supplier;

void main() { Scanner sc = new Scanner(System.in); int numOfServers = sc.nextInt(); int qmax = 0; // assume no queuing int numOfCustomers = sc.nextInt(); Supplier serviceTime = () → sc.nextDouble();

sc.nextLine(); // removes trailing newline
InfList<Pair<Integer,Double>> arrivals = InfList.iterate(1, x -> x + 1)
    .limit(numOfCustomers)
    .map(x -> new Pair<>(sc.nextInt(), sc.nextDouble()));

new Simulator(numOfServers, qmax, numOfCustomers, arrivals, serviceTime)
    .run().ifPresent(x -> System.out.println(x));

}

Modify your existing implementation so that service times are generated on demand when customers are served.

Use String.format to format the event times to three decimal places.

jshell> double d = 1.2 d ⇒ 1.2

jshell> String.format(“%.3f”, d) $.. ⇒ “1.200”

Sample runs are given below:

$ cat 1.in 1 3 1 0.5 2 1.6 3 3.7 1.0 2.0 3.0

$ cat 1.in | java —enable-preview Main

0.500 customer 1 arrives 0.500 customer 1 serve by server 1 1.500 customer 1 done 1.600 customer 2 arrives 1.600 customer 2 serve by server 1 3.600 customer 2 done 3.700 customer 3 arrives 3.700 customer 3 serve by server 1 6.700 customer 3 done

$ cat 2.in 1 3 1 0.5 2 1.6 3 3.7 4.0 2.0 3.0

$ cat 2.in | java —enable-preview Main

0.500 customer 1 arrives 0.500 customer 1 serve by server 1 1.600 customer 2 arrives 1.600 customer 2 leaves 3.700 customer 3 arrives 3.700 customer 3 leaves 4.500 customer 1 done

$ cat 3.in 1 3 1 0.5 2 1.6 3 3.7 2.0 2.0 3.0

$ cat 3.in | java —enable-preview Main

0.500 customer 1 arrives 0.500 customer 1 serve by server 1 1.600 customer 2 arrives 1.600 customer 2 leaves 2.500 customer 1 done 3.700 customer 3 arrives 3.700 customer 3 serve by server 1 5.700 customer 3 done

$ cat 4.in 2 6 1 0.5 2 0.6 3 0.7 4 1.5 5 1.6 6 1.7 1.1 0.9 0.7 0.1 0.2

$ cat 4.in | java —enable-preview Main

0.500 customer 1 arrives 0.500 customer 1 serve by server 1 0.600 customer 2 arrives 0.600 customer 2 serve by server 2 0.700 customer 3 arrives 0.700 customer 3 leaves 1.500 customer 2 done 1.500 customer 4 arrives 1.500 customer 4 serve by server 2 1.600 customer 1 done 1.600 customer 5 arrives 1.600 customer 5 serve by server 1 1.700 customer 5 done 1.700 customer 6 arrives 1.700 customer 6 serve by server 1 1.900 customer 6 done 2.200 customer 4 done

Pay particular attention to the last two test cases.

Level 2

Let us study the event transitions with queuing customers:

  • 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 three customer arrivals and assuming that service times is 1.0,

1 1 3 0.500 0.600 0.700

the entire similation run results in the following output:

0.500 customer 1 arrives 0.500 customer 1 serves by server 1 0.600 customer 2 arrives 0.600 customer 2 waits at server 1 0.700 customer 3 arrives 0.700 customer 3 leaves 1.500 customer 1 done 1.500 customer 2 serves by server 1 2.500 customer 2 done

Simulation statistics are also typically tracked to measure the performance of the system. The statistics 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]. We can use String.format to format the event times to three decimal places.

Just like in the previous milestone, a State can be used to set up a specific configuration of the simulation, so that the next() method can be used to test the rest of the simulation for correctness. The shop constructor takes in the following parameters in order:

  • the number of servers;
  • the supplier for the service time so that everytime a server in the shop serves a customer, the service time will be generated.
  • the maximum queue length for waiting customers.

In the following, the service time is set constant for illustration purposes.

jshell> PQ pq = new PQ().add(new ArriveEvent(new Customer(1, 1.0), 1.0)). …> add(new ArriveEvent(new Customer(2, 2.0), 2.0)) pq ⇒ [1.000 customer 1 arrives, 2.000 customer 2 arrives]

jshell> new State(pq, new Shop(2, () → 1.0, 0)).next() $.. ⇒ 1.000 customer 1 arrives

jshell> new State(pq, new Shop(2, () → 1.0, 0)).next(). …> next() $.. ⇒ 1.000 customer 1 arrives 1.000 customer 1 serves by server 1

jshell> new State(pq, new Shop(2, () → 1.0, 0)).next(). …> next(). …> next() $.. ⇒ 1.000 customer 1 arrives 1.000 customer 1 serves by server 1 2.000 customer 1 done

jshell> InfList.iterate(new State(pq, new Shop(2, () → 1.0, 0)), …> state → state.next()). …> takeWhile(state → !state.isEmpty()). …> reduce((s1, s2) → s2). …> ifPresent(state → System.out.println(state)) 1.000 customer 1 arrives 1.000 customer 1 serves by server 1 2.000 customer 1 done 2.000 customer 2 arrives 2.000 customer 2 serves by server 1 3.000 customer 2 done

jshell> InfList.iterate(new State(pq, new Shop(2, () → 2.0, 0)), …> state → state.next()). …> takeWhile(state → !state.isEmpty()). …> reduce((s1, s2) → s2). …> ifPresent(state → System.out.println(state)) 1.000 customer 1 arrives 1.000 customer 1 serves by server 1 2.000 customer 2 arrives 2.000 customer 2 serves by server 2 3.000 customer 1 done 4.000 customer 2 done

jshell> InfList.iterate(new State(pq, new Shop(1, () → 2.0, 1)), …> state → state.next()). …> takeWhile(state → !state.isEmpty()). …> reduce((s1, s2) → s2). …> ifPresent(state → System.out.println(state)) 1.000 customer 1 arrives 1.000 customer 1 serves by server 1 2.000 customer 2 arrives 2.000 customer 2 waits at server 1 3.000 customer 1 done 3.000 customer 2 serves by server 1 5.000 customer 2 done

For the purpose of demonstration, we shall use the following Main client. Note that your implementation will eventually be tested with an alternative client.

import java.util.List; import java.util.Scanner; import java.util.function.Supplier;

class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int numOfServers = sc.nextInt(); int qmax = sc.nextInt(); int numOfCustomers = sc.nextInt(); Supplier serviceTime = () → 1.0;

    sc.nextLine(); // removes trailing newline
    InfList<Pair<Integer,Double>> arrivals = InfList.iterate(1, x -> x + 1)
        .limit(numOfCustomers)
        .map(x -> new Pair<>(sc.nextInt(), sc.nextDouble()));

    new Simulator(numOfServers, qmax, numOfCustomers, arrivals,serviceTime)
        .run().ifPresent(x -> System.out.println(x));
}

}

Take note that blank lines will be ignored during testing.

Sample runs of the program is given below. All of them assumes a constant service time of 1.0. You should create your own input files using vim. You may also create other implementations of Supplier 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 customers.

$ cat 1.in 1 1 3 1 0.500 2 0.600 3 0.700

$ cat 1.in | java Main 0.500 customer 1 arrives 0.500 customer 1 serve by server 1 0.600 customer 2 arrives 0.600 customer 2 waits at server 1 0.700 customer 3 arrives 0.700 customer 3 leaves 1.500 customer 1 done 1.500 customer 2 serve by server 1 2.500 customer 2 done [0.450 2 1]

$ cat 2.in 1 1 6 1 0.500 2 0.600 3 0.700 4 1.500 5 1.600 6 1.700

$ cat 2.in | java Main 0.500 customer 1 arrives 0.500 customer 1 serve by server 1 0.600 customer 2 arrives 0.600 customer 2 waits at server 1 0.700 customer 3 arrives 0.700 customer 3 leaves 1.500 customer 1 done 1.500 customer 2 serve by server 1 1.500 customer 4 arrives 1.500 customer 4 waits at server 1 1.600 customer 5 arrives 1.600 customer 5 leaves 1.700 customer 6 arrives 1.700 customer 6 leaves 2.500 customer 2 done 2.500 customer 4 serve by server 1 3.500 customer 4 done [0.633 3 3]

$ cat 3.in 2 1 6 1 0.500 2 0.600 3 0.700 4 1.500 5 1.600 6 1.700

$ cat 3.in | java Main 0.500 customer 1 arrives 0.500 customer 1 serve by server 1 0.600 customer 2 arrives 0.600 customer 2 serve by server 2 0.700 customer 3 arrives 0.700 customer 3 waits at server 1 1.500 customer 1 done 1.500 customer 3 serve by server 1 1.500 customer 4 arrives 1.500 customer 4 waits at server 1 1.600 customer 2 done 1.600 customer 5 arrives 1.600 customer 5 serve by server 2 1.700 customer 6 arrives 1.700 customer 6 waits at server 2 2.500 customer 3 done 2.500 customer 4 serve by server 1 2.600 customer 5 done 2.600 customer 6 serve by server 2 3.500 customer 4 done 3.600 customer 6 done [0.450 6 0]

$ cat 4.in 2 2 6 1 0.500 2 0.600 3 0.700 4 1.500 5 1.600 6 1.700

$ cat 4.in | java Main 0.500 customer 1 arrives 0.500 customer 1 serve by server 1 0.600 customer 2 arrives 0.600 customer 2 serve by server 2 0.700 customer 3 arrives 0.700 customer 3 waits at server 1 1.500 customer 1 done 1.500 customer 3 serve by server 1 1.500 customer 4 arrives 1.500 customer 4 waits at server 1 1.600 customer 2 done 1.600 customer 5 arrives 1.600 customer 5 serve by server 2 1.700 customer 6 arrives 1.700 customer 6 waits at server 1 2.500 customer 3 done 2.500 customer 4 serve by server 1 2.600 customer 5 done 3.500 customer 4 done 3.500 customer 6 serve by server 1 4.500 customer 6 done [0.600 6 0]