

Lab 2b: Simulator v1.3

Submission deadline: 2359, Sunday, March 11, 2018.

(Special extension due to Week 7 being the midterms week)

Prerequisites

This lab assumes that students:

• have already attempted Lab 2a
• have an understanding of the customer/server system being simulated
• have an understanding of inheritance and polymorphism
• are familiar the basic interfaces with Java Collections Framework

Learning Objectives

After completing this lab, students should:

• be more comfortable exploring Java Collections Framework API to look for suitable implementation for a particular data structure
• be able to model IS-A relationship with inheritance and differences in behavior with polymorphism
• appreciate how inheritance and polymorphism makes it easier to extend the code with new behavior

Setup

No new skeleton is given. You are to build on top of your Lab 2a solution.

• Login to cs2030-i
• Create a new directory ~/lab2b
• Copy the test data and trace output from ~cs2030/lab2b to ~/lab2b
• Copy the new RandomGenerator.java from ~cs2030/lab2b to ~/lab2b
• Copy your solution from ~/lab2a to ~/lab2b
• Rename the class LabTwoA to LabTwoB and the file LabTwoA.java to LabTwoB.java
• Update your manifest file to point to the new main class

There should be 12 test files (TESTDATA1.txt to TESTDATA12.txt) and trace files (OUTPUT1.txt to OUTPUT12.txt).

Goals

For Lab 2b, you will extend the code to model the more complex behavior of shops, servers, and customers.

Writing and Generating Javadoc

Remember that from Lab 2a onwards, you are required to document your classes and methods with Javadoc comments. You can see examples from the skeleton code given earlier. For more details, see the javadoc guide.

You should document all your methods and classes (including private ones).

Package

All your classes should be in the cs2030.simulator package.

Customer Queues

The shop owner noticed that the shop is still losing customers. As such, he expanded the shop area, so that more customers can queue up.

In your simulator, you should change the shop so that multiple customers can queue up and wait. Each server should now have a queue of customers. A customer that chooses to join a queue joins at the tail. When a server finishes serving a customer, it will serve the next waiting customer at the head of the queue. The queue is a first-in-first-out (FIFO) structure.

Think about which interface from Java Collections Framework should you use for this? Which implementation of this interface is the best?

Each queue has a maximum size $Q_{max}$. A customer cannot join a queue that is full, i.e., has $Q_{max}$ customers inside. (Note: a customer that is being served is not inside the queue).

When a customer arrives, if every queue in the shop is full, then the customer leaves.

Note that if $Q_{max}$ is 1, it is the same scenario that you have been working on for Lab 2a.

Event Queue vs. Customer Queue

Your program will have two types of queues, a priority queue for events, and FIFO queues for customers. Do not mix up the two. You do not need a priority queue for customers.

Taking A Rest

The (human) servers have to take a rest now and then. When a server finishes serving a customer, there is a probability $P_{r}$ that the server takes a rest for a random amount of time $T_{r}$. During the resting break, the server does not serve the next waiting customer, but upon returning from the break, the server serves the next customer in queue immediately.

$P_{r}$ is a parameter read from the input file. To decide if the server should rest, we generate a random number uniformly drawn from between 0 and 1, with RandomGenerator's method genRandomRest(). If the returned value is less than $P_{r}$, the server rests, otherwise, it continues serving the next customer.

$T_{r}$ is a random number generated by RandomGenerator 's method genRestPeriod(). This variable is again an exponential random variable, governed by the resting rate $\rho$. $\rho$ is another parameter to be read from the input file.

To implement this behavior, you should introduce a new event, a "back" event, to signify that the server is back from a rest. This event should be generated and scheduled in the simulator when the server decides to rest.

Self-Checkout

To improve the customer experience and reduce the waiting time, the owner is setting up a number of self-checkout counters, for customers who just need a quick service. The advantage of self-checkout counters is that they never rest! Customers queue up for the self-checkout counter just like for the (human) servers. There is one queue per self-checkout counter. However, only customers with service time lower than a $T_{self}$ can join self-checkout queue. $T_{self}$ is a parameter to be read from the input file.

There are $N_{self}$ self-checkout counters in the shop now. $N_{self}$ is a parameter to be read from the input file.

Customer: Choosing Which Queue

When a customer arrives, he or she has to decide which queue to join.

Like before, the customer will scan through the servers (in order, from 1 to $k$) to see if there is an idle server. If there is one, the customer will go to the server to be served. In this lab, however, the notion of idle is expanded: a server is idle if it is not serving a customer and is not resting.

But, the customers' behavior differs when there is no idle server.

We model two types of customer behavior. A greedy customer always chooses the queue with the fewest customers to join. If there are more than one queues of the same shortest length, the customer breaks a tie by preferring the server with the lowest id (remember that customer scans from 1 to $k$).

A typical, non-greedy, customer just chooses the first queue among all the queues that are still not full to join. An arriving customer is a greedy customer with probability $P_{g}$.

$P_{g}$ is a parameter read from the input file. To decide if we should create a typical or greedy customer, we generate a random number uniformly drawn from between 0 and 1, with RandomGenerator's method genCustomerType(). If the returned value is less than $P_{g}$, a new greedy customer is generated, otherwise, a typical customer is generated.

Debugging

To help with debugging, it would be useful to print out the greedy customer and a typical customer in a different way.

If the customer requires a service time less then $T_{self}$, it will look for an idle self-checkout counter first. Failing which it will look for an idle human server. If the customer fails to find any idle server (self-checkout and human server), it will try to join a queue at the self-checkout counters. The behavior of a customer joining a queue at the self-checkout counters is exactly the same as if the self-checkout counters are human servers.

If all the queues at the self-checkout counters are full, or the customer requires a longer service (service time is no less than $T_{self}$, then the customer joins one of the queues of the (human) servers. The same greedy / no-greedy behavior applies.

Greedy Customer and Self-Checkouts

A greedy customer who is eligible for self-checkout counters will prefer the shortest queue among the self-checkout counters over an even shorter queue for human servers.

Abstraction Principle

You should avoid duplicating your code for customer choosing self-checkout counters and human servers as much as possible. One way is to treat the self-checkout counters and the human servers as in two different (virtual) shops.

If a customer cannot find any queue to join, it will leave the shop.

Summary

To summarize, you need to handle the following additions. The additions below are listed in the order you are recommended to work on.

• FIFO queues for customers with a capacity of $Q_{max}$.
• Two types of customers, "greedy" customers and "typical" customers.
• Two types of servers, "human" servers who may rest after serving a customer and self-checkout counters who never rest.
• Self-checkout counters can only be used by, and always be preferred by, customers with small service time.
• A new type of event, a "back" event for when a server comes back from resting.

Modifiability of OO Programs

While the number of additions above seems like there is a lot of work, using Java Collections Framework, inheritance, and polymorphism, the work needed to extend Lab2a to Lab2b should not be much. Our solution adds only ~250 lines of code (excluding comments) to implement all these complex behaviors of customers, servers, and shops.

The RandomGenerator class

The new RandomGenerator class now has more methods as shown above. Its constructor now takes in a new parameter $\rho$. The list of parameters are:

• int seed is the base seed for the random number generators. Each random number generator uses a different seed derived from this argument.
• double lambda is the arrival rate.
• double mu is the service rate.
• double rho is the resting rate.

Grading

This lab is graded and is worth 7% of your final grade.

• 1 mark for proper javadoc documentation
• 2 marks for correctness
• 4 marks for proper use of OO concepts in modeling the complex shop, customer, and server behaviors.

You no longer receive marks for following Java coding style, but you will be deducted up to 1 marks if you deviate significantly from the required coding style.

Input and Output

The input file format has changed. The input file for Lab 2b contains the following:

• The first line is an integer, which is the base seed to the RandomGenerator object
• The next line is an integer, which is the number of (human) servers
• The next line is an integer, which is the number of self-checkout counters $N_{self}$
• The next line is an integer, which is the maximum queue length $Q_{max}$
• The next line is an integer, which is the number of customers (i.e, the number of arrival events) to simulate
• The next line is a double, which is the parameter $lambda$
• The next line is a double, which is the parameter $mu$
• The next line is a double, which is the parameter $rho$
• The next line is a double, which is the parameter $P_{r}$
• The next line is a double, which is the parameter $P_{g}$
• The last line is a double, which is the parameter $T_{self}$

Remember: you must not change the formatting of the last line of output:

System.out.printf("%.3f %d %d%n", ..")

Given an input, the output might not be deterministic, since if two events occur at exactly the same time, we break the ties arbitrarily. For this reason, we will only test your code with test inputs where no two events occur at exactly the same time.

The test cases and outputs¹ should be:

Test	Output	Customer Types	$Q_{max}$	Server Types	Can Human Server Rest?	Remarks
1	0.706 4 1	Typical	1	Human	No
2	1.042 3 1	Typical	> 1	Human	No
3	0.679 4 0	Greedy	> 1	Human	No
4	8.725 765 235	Mixed	> 1	Human	No
5	0.706 4 1	Typical	1	Self-checkouts	No	Everyone uses self-checkouts
6	0 2 3	Typical	1	Self-checkouts	No
7	1.049 20 0	Mixed	> 1	Mixed	No
8	5.299 867 133	Mixed	> 1	Mixed	No	Based on Test 4
9	1.391 4 1	Typical	1	Human	Always	Based on Test 1
10	1.930 20 0	Mixed	> 1	Mixed	Always	Based on Test 7
11	6.275 792 208	Mixed	> 1	Mixed	Always	Based on Test 8
12	5.608 843 157	Mixed	> 1	Mixed	Maybe	Based on Test 11

We suggest that you implement the required additions one-by-one, and use the appropriate test cases above to verify that one addition is working before moving on to implement the next addition. You can create additional test cases to help you debug.

To help you understand the relatively large number of test cases and parameters above, we have created an Excel spreadsheet, which you can find under ~cs2030/lab2b as well.

As usual, producing the correct output for test cases above does not guarantee that your code is correct.

We have also included traces of the simulation for each of the test cases, which you can find in the files OUTPUT1.txt to OUTPUT12.txt. This should help you debug should your output is different from ours.

Using grep

If you want to focus on a particular server, say, HS4, or a customer, say, GC180, you can use the UNIX grep command to filter out lines containing them from a long output or traces. E.g.,

java lab2b.jar < TESTDATA11.txt | grep HS4

or

grep CS180 OUTPUT12.txt

Submission

When you are ready to submit your lab, on cs2030-i, run the script

~cs2030/submit2b

which will copy all files matching *.java (and nothing else) from your ~/lab2b/cs2030/simulator directory on cs2030-i to an internal grading directory. We will test compile and test run with a tiny sample input to make sure that your submission is OK. We will also check if your code generates javadoc with any warning (should have no warning) and follows the CS2030 Java style guide.

You can submit multiple times, but only the most recent submission will be graded.

---

1. After piping through tail (e.g., jar -cp . lab2b.jar < TESTDATA1.txt | tail -1) ↩