A more interesting simulation allows us to study the behavior of the printing queue described earlier in this section. Recall that as students send printing tasks to the shared printer, the tasks are placed in a queue to be processed in a first come, first served manner. Many questions arise with this configuration. The most important of these might be whether the printer is capable of handling a certain amount of work. If it cannot, students will be waiting too long for printing and may miss their next class.
Consider the following situation in a computer science laboratory. On any average day, about 10 students are working in the lab at any given hour. These students typically print up to twice during that time, and the length of these tasks ranges from 1 to 20 pages. The printer in the lab is older, capable of processing 10 pages per minute of draft quality. The printer could be switched to give better quality, but then it would produce only five pages per minute. The slower printing speed could make students wait too long. What page rate should be used?
We could decide by building a simulation that models the laboratory. We will need to construct representations for students, printing tasks, and the printer (Figure 3.14.1). As students submit printing tasks, we will add them to a waiting list: a queue of print tasks attached to the printer. When the printer completes a task, it will look at the queue to see if there are any remaining tasks to process. Of interest for us is the average amount of time students will wait for their papers to be printed. This is equal to the average amount of time a task waits in the queue.
We need to use some probabilities to model this situation. For example, students may print a paper from 1 to 20 pages in length. If each length from 1 to 20 is equally likely, the actual length for a print task can be simulated by using a random number between 1 and 20 inclusive. This means that there is equal chance of any length from 1 to 20 appearing.
If there are 10 students in the lab and each prints twice, then there are 20 print tasks per hour on average. What is the chance that at any given second, a print task is going to be created? The way to answer this is to consider the ratio of tasks to time. Twenty tasks per hour means that on average there will be one task every 180 seconds:
For every second, we can simulate the chance that a print task occurs by generating a random number between 1 and 180 inclusive. If the number is 180, we say a task has been created. Note that it is possible that many tasks could be created in a row, or we may wait quite a while for a task to appear. That is the nature of simulation. You want to simulate the real situation as closely as possible, given that you know general parameters.
Subsection3.14.1Main Simulation Steps
Here is the main simulation.
Create a queue of print tasks. Each task will be given a timestamp upon its arrival. The queue is empty to start.
For each second (currentSecond):
Does a new print task get created? If so, add it to the queue with the currentSecond as the timestamp.
If the printer is not busy and if a task is waiting,
Remove the next task from the print queue and assign it to the printer.
Subtract the timestamp from the currentSecond to compute the waiting time for that task.
Append the waiting time for that task to a list for later processing.
Based on the number of pages in the print task, figure out how much time will be required.
The printer now does one second of printing if necessary. It also subtracts one second from the time required for that task.
If the task has been completed—in other words, the time required has reached zero—the printer is no longer busy.
After the simulation is complete, compute the average waiting time from the list of waiting times generated.
Subsection3.14.2Java Implementation
To design this simulation we will create classes for the two real-world objects described above: Task and Printer. The simulation class that contains our main method (PrintSimulation) will create a Queue<Task> named printQueue. We will put all these classes in the same file, which means that only one can be public; that will be the PrintSimulation class.
We will need to generate random numbers and keep a list of waiting times, so the file will begin with these import statements:
The Task class (Listing 3.14.2) will represent a single printing task. When the task is created, a random number generator will provide a length from 1 to 20 pages. We will use a random number generator from the java.util.Random class, as we saw in Section 1.14.
Each task will also need to keep a timestamp to be used for computing waiting time. This timestamp will represent the time that the task was created and placed in the printer queue. The waitTime method can then be used to retrieve the amount of time spent in the queue before printing begins.
class Task {
int timeStamp;
int pages;
// The random number generator is static, as it is
// shared among all tasks.
static Random generator = new Random();
public Task(int timeStamp) {
this.timeStamp = timeStamp;
this.pages = generator.nextInt(20) + 1;
}
public int getPages() {
return this.pages;
}
public int waitTime(int currentTime) {
return currentTime - this.timeStamp;
}
}
Listing3.14.2.The Task Class
The Printer class (Listing 3.14.3) will need to track whether it has a current task. If it does, then it is busy (lines 13–17) and the amount of time needed can be computed from the number of pages in the task. The constructor will also allow the pages-per-minute setting to be initialized. The tick method decrements the internal timer and sets the printer to idle (line 16) if the task is completed.
class Printer {
int pageRate; // pages per minute
int timeRemaining;
Task currentTask;
public Printer(int pageRate) {
this.pageRate = pageRate;
this.currentTask = null;
this.timeRemaining = 0;
}
public void tick() {
if (this.currentTask != null) {
this.timeRemaining = this.timeRemaining - 1;
if (this.timeRemaining <= 0) {
this.currentTask = null;
}
}
}
public boolean busy() {
return this.currentTask != null;
}
public void startNext(Task newTask) {
this.currentTask = newTask;
this.timeRemaining = newTask.getPages() * 60 / this.pageRate;
}
}
Listing3.14.3.The Printer Class
The main simulation (Listing 3.14.4) implements the algorithm described above. The printQueue object is an instance of our existing queue ADT. A boolean helper function, newPrintTask, decides whether a new printing task has been created. We have again chosen to use the nextInt method from Random to return a random integer between 1 and 180. Print tasks arrive once every 180 seconds. By arbitrarily choosing 180 from the range of random integers, we can simulate this random event. The simulation function allows us to set the total time and the pages per minute for the printer.
public class PrintSimulation {
static Random generator = new Random();
int numSeconds;
Printer labPrinter;
Queue<Task> printQueue;
ArrayList<Integer> waitingTimes;
public PrintSimulation (int numSeconds, int pagesPerMinute) {
this.numSeconds = numSeconds;
labPrinter = new Printer(pagesPerMinute);
}
public void performSimulation() {
printQueue = new Queue<Task>();
waitingTimes = new ArrayList<Integer>();
for (int currentSecond = 0; currentSecond < numSeconds;
currentSecond++) {
if (newPrintTask()) {
Task t = new Task(currentSecond);
printQueue.enqueue(t);
}
if ((!labPrinter.busy()) && (!printQueue.isEmpty())) {
Task nextTask = printQueue.dequeue();
waitingTimes.add(nextTask.waitTime(currentSecond));
labPrinter.startNext(nextTask);
}
labPrinter.tick();
}
int totalWaitingTime = 0;
for (int i = 0; i < waitingTimes.size(); i++) {
totalWaitingTime = totalWaitingTime +
waitingTimes.get(i);
}
double average_wait =
(double) totalWaitingTime / waitingTimes.size();
System.out.printf("Average wait %6.2f secs. ", average_wait);
System.out.printf("%d tasks remaining.%n", printQueue.size());
}
public boolean newPrintTask() {
int num = generator.nextInt(180) + 1;
return (num == 180);
}
public static void main(String[] args) {
PrintSimulation sim = new PrintSimulation(3600, 5);
for (int i = 0; i < 10; i++) {
sim.performSimulation();
}
}
}
Listing3.14.4.The Simulation Driver
Note3.14.5.Java Notes.
Lines 5–8 are not static; they are properties of our PrintSimulation class.
The constructor in lines 10–13 doesn’t initialize the print queue and waiting list. That happens in lines 16 and 17, to ensure that we start with a new print queue and an empty list of waiting times every time we perform a simulation.
The main method in lines 51–56 is very different from what we have seen before. Line 52 creates a new instance of a PrintSimulation object in variable sim, and line 54 calls that instance’s performSimulation method. This is a typical pattern that you will see in Java programs: the main method creates an instance of the class it belongs to and then calls methods on that instance.
When we run the simulation, we should not be concerned that the results are different each time. This is due to the probabilistic nature of the random numbers. We are interested in the trends that may be occurring as the parameters to the simulation are adjusted. Here are some results.
First, we will run the simulation for a period of 60 minutes (3,600 seconds) using a page rate of five pages per minute. In addition, we will run 10 independent trials. Remember that because the simulation works with random numbers, each run will return different results.
Average wait 39.56 secs. 2 tasks remaining.
Average wait 226.61 secs. 0 tasks remaining.
Average wait 68.87 secs. 0 tasks remaining.
Average wait 58.65 secs. 2 tasks remaining.
Average wait 126.35 secs. 0 tasks remaining.
Average wait 3.50 secs. 0 tasks remaining.
Average wait 80.33 secs. 0 tasks remaining.
Average wait 52.41 secs. 1 tasks remaining.
Average wait 43.18 secs. 0 tasks remaining.
Average wait 138.00 secs. 1 tasks remaining.
After running our 10 trials, we can see that the mean average wait time is (39.56 + 226.61 + 68.87 + 58.65 + 126.35 + 3.50 + 80.33 + 52.41 + 43.18 + 138.00) / 10 = 83.746 seconds. You can also see that there is a large variation in the average wait time with a minimum average of 3.5 seconds and a maximum of 226.62 seconds. You may also notice that in four of the cases, some tasks weren’t completed.
Now we will adjust the page rate to 10 pages per minute and run the 10 trials again. With a faster page rate, our hope would be that more tasks would be completed in the one-hour time frame.
Average wait 39.77 secs. 0 tasks remaining.
Average wait 18.48 secs. 0 tasks remaining.
Average wait 5.31 secs. 2 tasks remaining.
Average wait 33.00 secs. 0 tasks remaining.
Average wait 9.92 secs. 0 tasks remaining.
Average wait 17.31 secs. 0 tasks remaining.
Average wait 16.06 secs. 0 tasks remaining.
Average wait 9.16 secs. 0 tasks remaining.
Average wait 21.09 secs. 0 tasks remaining.
Average wait 12.00 secs. 0 tasks remaining.
For your reference, here is the entire code for the simulation:
Subsection3.14.3Discussion
We were trying to answer a question about whether the current printer could handle the task load if it were set to print with a better quality but slower page rate. The approach we took was to write a simulation that modeled the printing tasks as random events of various lengths and arrival times.
The preceding output shows that with 5 pages per minute printing, the average waiting time varied from a low of 4 seconds to a high of 226 seconds (about 3.75 minutes). With a faster printing rate, the low value was 6 seconds with a high of only 40. In addition, in 4 out of 10 runs at 5 pages per minute there were print tasks still waiting in the queue at the end of the hour.
Therefore, we are perhaps persuaded that slowing the printer down to get better quality may not be a good idea. Students cannot afford to wait that long for their papers, especially when they need to be getting on to their next class. A four-minute wait would simply be too long.
This type of simulation analysis allows us to answer many questions, commonly known as what-if questions. All we need to do is vary the parameters used by the simulation and we can simulate any number of interesting behaviors. For example,
What if enrollment goes up and the average number of students increases by 20?
What if it is Saturday and students do not need to get to class? Can they afford to wait?
What if the size of the average print task decreases if students program in Python, which tends to be less verbose and lead to shorter source code?
These questions could all be answered by modifying the above simulation. However, it is important to remember that the simulation is only as good as the assumptions that are used to build it. Real data about the number of print tasks per hour and the number of students per hour was necessary to construct a robust simulation.
ExercisesSelf Check
How would you modify the printer simulation to reflect a larger number of students? Suppose that the number of students was doubled. You make need to make some reasonable assumptions about how this simulation was put together but what would you change? Modify the code. Also suppose that the length of the average print task was cut in half. Change the code to reflect that change. Finally, how would you parametertize the number of students? Rather than changing the code, we would like to make the number of students a parameter of the simulation.
