In this assignment we will build a simulation of what happens when students wait in a queue for access to a professor's office for help with programming assignments. This familiar scenario is a simple example of scheduling access to a resource through a priority queue, and is extremely common in organizing the activities in a computer system or in a network. To just give the most obvious examples, whenever you run a program on CSA, your running program must wait in a job queue for access to a CPU, must wait in a disk queue when reading from the disk, and finally must wait in the printer queue before you can obtain a hard copy of your work.
This assignment will exercise your knowledge of priority queues, inheritance, command line arguments, and file I/O.
Some initial test files for the assignment are here.
We will simulate what happens when students arrive to ask for help during a professor's office hours. The simulation will have the following features:
An important design consideration is how to organize the queue (which is really a priority queue). The default for most waiting queues is First-Come-First-Served (FCFS); however, the professor notices that sometimes a student with a very short question (e.g., "Under what name do we submit the file?") must wait behind a student with a very long question ("My program doesn't work at all, can you explain the whole thing to me once more?"), and wonders one day while waiting in the Express Checkout line at the supermarket how he might avoid this problem. He decides (while paying for a can of dog food and a gallon of milk) to try using a policy of Shortest-Request-First (SRF), i.e., whenever selecting a new student Si from the queue, he should select the student whose request Ri is shortest. Ties may be broken arbitrarily. He decides he will try both and see which is better.
But how should he decide which is better? From an individual student's point of view, the important thing is to spend as little time waiting in the queue as possible; thus the professor decides that he should use the strategy which results in the smallest average wait time for all students who request his help.
Suppose we have Student 0 arriving at time 0 with a request for 30 seconds of help, student 1 arriving at time 10 with a request time of 20 seconds, and student 3 arriving at 30 seconds with a request time of 10 seconds. We could chart the progress of these two policies as follows, where "++++" indicates time waiting in the queue, and "%%%%%" time having a request serviced:
FCFS: Time: 0 10 20 30 40 50 60 Student 0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Student 1: ++++++++++++++++++++%%%%%%%%%%%%%%%%%%%% Student 2: ++++++++++++++++++++%%%%%%%%%% SRF: Time: 0 10 20 30 40 50 60 Student 0: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Student 1: ++++++++++++++++++++++++++++++%%%%%%%%%%%%%%%%%%%% Student 2: %%%%%%%%%%
The average wait time is the sum of the seconds spent in the queue (all the +'s) divided by the number of students, i.e., (20+20)/3 = 13.333... for FCFS and 30/3 = 10 for SRF. Clearly, SRF is better.
Your task in this assignment will be to read a trace file giving a sequence of students (specified by arrival and request times), and to calculate the average wait time under each of these two strategies. You will also, in order to help understand the process (and to debug) provide a verbose trace so that you can see what events happen when during the simulation. As usual, a sample session for illustration will be useful. If the scenario given above were simulated, we would get the following.
csa% cat test.txt // This is the input file 0 30 10 20 30 10 csa% sim fcfs test.txt Time Event ---- ----- 0 Student 0 enters queue 0 Student 0 enters office 10 Student 1 enters queue 30 Student 2 enters queue 30 Student 0 leaves office 30 Student 1 enters office 50 Student 1 leaves office 50 Student 2 enters office 60 Student 2 leaves office Simulation over... Average wait time: 13.3333 csa% sim srf test.txt Time Event ---- ----- 0 Student 0 enters queue 0 Student 0 enters office 10 Student 1 enters queue 30 Student 2 enters queue 30 Student 0 leaves office 30 Student 2 enters office 40 Student 2 leaves office 40 Student 1 enters office 60 Student 1 leaves office Simulation over... Average wait time: 10 csa%
class MinHeapItem {
public:
int priority;
};
which is the minimal information necessary to organize a min-heap (naturally, it will also define the main heap class).
Any code
that wishes to use the heap, say to insert students, should
define a derived class of MinHeapItem, and add whatever other information
it wishes (such as arrival time, etc.). These objects can be inserted into
the heap since they are derived from MinHeapItem
(so they will have a priority); when removing objects
from the heap, in general you need
to cast the object back into the derived class.
Read the next student from the input file (if such exists);
for(time = 0; (next student exists OR heap not empty
OR is a student in the professor's office); time++) {
if( time == arrival time of next student if such exists ) {
Insert this student into the heap;
Report this event;
Read the next student from the input file (if such exists);
}
if( time == departure time of a student in the office ) {
Remove the student from the office;
Report this event;
}
if( no student in office AND heap is not empty ) {
Remove a student from heap and put him/her in the office;
Report this event;
}
}
This pseudo-code leaves the matter of calculating the student number, the departure time, and average wait time intentionally unspecified, but this is not very difficult. As usual, you should follow the sample session as closely as possible.
You should also check for errors in input, as specified by the following example:
csa% sim fcf test.txt // misspelled policy Usage: simulate [fcfs|srf] infile // remind user of usage syntax csa% sim fcfs nofile.txt // error in attempting to open file Can not open file nofile.txt csa% cat error.txt 0 30 10 20 30 // wrong number of integers in file csa% sim fcfs error.txt Time Event ---- ----- 0 Student 0 enters queue 0 Student 0 enters office 10 Student 1 enters queue Error in input file // will find error when reading last line csa%
Be sure to remove all debugging statements before submission. It should follow all the stylistic guidelines as specified in the course web page.
You should submit the following files into your gsubmit directory: heap.cpp , heap.h , simulation.cpp and Makefile. You may break your code into additional separate files if you wish (and write your Makefile accordingly). Your Makefile should compile your code into an executable called "sim" as shown in the sample session above.
You are responsible for thoroughly testing your program to make sure that it works. Use the sample session above as a guide. Your code must run correctly on csa. In grading your program, we will test your program on the test files shown on the class web page.
One problem with time stepping is that it is inefficient, since in many iterations of the loop, nothing is happening. A better way to calculate time is by need, i.e., during each iteration, figure out what the next event is, set the time variable to that time, and perform the next event(s). The simulation is over when there are no more events. For example, if the next student has an arrival time of 30, and the student in the office has a departure time of 25, then the next events are to remove the student from the office, and move a student from the heap to the office if the heap is non-empty. Time in this model occurs in discrete steps corresponding to event times, and hence this is called "discrete event simulation." Rewrite your code using this model for an additional 5 points. Be sure to advertise this fact in your header comment so that the grader sees it!