3.14. Simulation: Printing Tasks¶

3.14.1. Main Simulation Steps¶

Here is the main simulation.

1. Create a queue of print tasks. Each task will be given a timestamp upon its arrival. The queue is empty to start.
2. 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.
3. After the simulation is complete, compute the average waiting time from the list of waiting times generated.

3.14.2. C++ Implementation¶

To design this simulation we will create classes for the three real-world objects described above: Printer, Task, and PrintQueue.

The Printer class (Listing 2) 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 11) if the task is completed.

Listing 2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

class Printer {
    public:
    int pagerate;
    Task *currentTask;
    int timeRemaining;

    Printer(int ppm) {
        pagerate=ppm;
        currentTask=NULL;
        timeRemaining=0;
    }

    void tick() {
        if (currentTask != NULL) {
            timeRemaining--;
            if (timeRemaining <= 0) {
                currentTask=NULL;
            }
        }
    }

    bool busy() {
        if (currentTask != NULL) {
            return true;
        } else {
            return false;
        }
    }

    void startNext(Task *newtask) {
        currentTask=newtask;
        timeRemaining=newtask->getPages()*60/pagerate;
    }
};

The Task class (Listing 3) 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 have chosen to use the rand() function to provide the random number using the format below. srand() is used to give different random numbers each time the program is executed by setting the random numbers based on the computer’s current time.

>>srand(time(NULL));
>>> rand()%21+1;
18
>>> rand()%21+1;
8
>>>

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.

Listing 3

class Task {
    private:
    int timestamp;
    int pages;

    public:
    Task(int time) {
        timestamp = time;
        pages=(rand()%21)+1;
    }

    int getStamp() {
        return timestamp;
    }

    int getPages() {
        return pages;
    }

    int waitTime(int currenttime) {
        return (currenttime - timestamp);
    }
};

The main simulation (Listing 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 randrange function from the random module 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 (line 32), we can simulate this random event. The simulation function allows us to set the total time and the pages per minute for the printer.

Listing 4

#include <iostream>
#include <queue>
#include <vector>
#include <random>
using namespace std;

class Task {
    private:
    int timestamp;
    int pages;

    public:
    Task(int time) {
        timestamp = time;
        pages=(rand()%21)+1;
    }

    int getStamp() {
        return timestamp;
    }

    int getPages() {
        return pages;
    }

    int waitTime(int currenttime) {
        return (currenttime - timestamp);
    }
};

class Printer {
    public:
    int pagerate;
    Task *currentTask;
    int timeRemaining;

    Printer(int ppm) {
        pagerate=ppm;
        currentTask=NULL;
        timeRemaining=0;
    }

    void tick() {
        if (currentTask != NULL) {
            timeRemaining--;
            if (timeRemaining <= 0) {
                currentTask=NULL;
            }
        }
    }

    bool busy() {
        if (currentTask != NULL) {
            return true;
        } else {
            return false;
        }
    }

    void startNext(Task *newtask) {
        currentTask=newtask;
        timeRemaining=newtask->getPages()*60/pagerate;
    }
};

bool newPrintTask() {
    int num = rand()%180+1;
    if (num==180) {
        return true;
    } else {
        return false;
    }
}

void simulation(int numSeconds, int pagesPerMinute) {
    Printer labprinter(pagesPerMinute);
    queue<Task*> printQueue;
    vector<int> waitingTimes;

    for (int i=0; i<numSeconds; i++) {
        if (newPrintTask()) {
            Task *task = new Task(i);
            printQueue.push(task);
        }
        if (!labprinter.busy() &&!printQueue.empty()) {
            Task *nexttask = printQueue.front();
            printQueue.pop();
            waitingTimes.push_back(nexttask->waitTime(i));
            labprinter.startNext(nexttask);
        }
        labprinter.tick();
    }
    float total=0;
    for (int i=0; i<waitingTimes.size(); i++) {
        total+=waitingTimes[i];
    }
    cout<<"Average Wait "<<total/waitingTimes.size()<<" secs "<<printQueue.size()<<" tasks remaining."<<endl;
}

int main() {
    srand(time(NULL));

    for (int i=0; i<10; i++) {
        simulation(3600, 10);
    }

    return 0;
}

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.

>>>for (int i=0; i<10; i++) {
  simulation(3600,5);
}

Average Wait 165.38 secs 2 tasks remaining.
Average Wait  95.07 secs 1 tasks remaining.
Average Wait  65.05 secs 2 tasks remaining.
Average Wait  99.74 secs 1 tasks remaining.
Average Wait  17.27 secs 0 tasks remaining.
Average Wait 239.61 secs 5 tasks remaining.
Average Wait  75.11 secs 1 tasks remaining.
Average Wait  48.33 secs 0 tasks remaining.
Average Wait  39.31 secs 3 tasks remaining.
Average Wait 376.05 secs 1 tasks remaining.

After running our 10 trials we can see that the mean average wait time is 122.09 seconds. You can also see that there is a large variation in the average weight time with a minimum average of 17.27 seconds and a maximum of 376.05 seconds. You may also notice that in only two of the cases were all the tasks 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.

>>>for (int i=0; i<10; i++) {
  simulation(3600,10);
}

Average Wait   1.29 secs 0 tasks remaining.
Average Wait   7.00 secs 0 tasks remaining.
Average Wait  28.96 secs 1 tasks remaining.
Average Wait  13.55 secs 0 tasks remaining.
Average Wait  12.67 secs 0 tasks remaining.
Average Wait   6.46 secs 0 tasks remaining.
Average Wait  22.33 secs 0 tasks remaining.
Average Wait  12.39 secs 0 tasks remaining.
Average Wait   7.27 secs 0 tasks remaining.
Average Wait  18.17 secs 0 tasks remaining.

You can run the simulation for yourself in ActiveCode 2.

3.14.3. Discussion¶

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 output above shows that with 5 pages per minute printing, the average waiting time varied from a low of 17 seconds to a high of 376 seconds (about 6 minutes). With a faster printing rate, the low value was 1 second with a high of only 28. In addition, in 8 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 six-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 are not needing to get to class? Can they afford to wait?
• What if the size of the average print task decreases since C++ is such a powerful language and programs tend to be much shorter?

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.