Assignment 4 Queue ADT

CMPS 12B
Introduction to Data Structures
Programming Assignment 4
In this project you will implement a Queue ADT in Java based on a linked list data structure. You will use your
Queue ADT to simulate a set of jobs performed by a set of processors, where there are more jobs than processors,
and therefore some jobs may have to wait in a queue. Think of shoppers at a grocery store waiting in line at
check-out stands. In this metaphor, a job is a basket of goods to be purchased and a processor is a clerk at a
check-out stand ringing up the purchase. Abstractly, a job is an encapsulation of three quantities: arrival time,
duration, and finish time. The arrival time is the time at which a job becomes available for processing. This is
analogous to the time at which a shopper reaches the check-out stand area. If there is a free Processor, that job's
"work" may begin. If not, it must wait in a processor queue. The duration of a job is the amount of processor
time it will consume once it reaches a processor. This quantity is analogous to the amount of goods in the
shopper’s basket. Both arrival time and duration are intrinsic to the job and are known ahead of time, whereas
the finish time is only known when the job reaches the head of a processor queue. The finish time can then be
calculated as finish_time = start_time + duration. Before a job is underway its finish time will be
considered undefined. Once a given job’s finish time is known, we can calculate the amount of time spent waiting
in line, not counting processing time. Thus wait_time = finish_time – arrival_time – duration. In
this simulation, time is considered a discrete quantity, starting at 0 and assuming only non-negative integer values.
Note time 0 is reserved for initialization, and all job arrival times will be greater than or equal to 1.
The goal of the simulation will be as follows: given a batch of m jobs, each with specific arrival times and
durations, determine (1) the total wait time (i.e. the total time spent by all m jobs waiting in queues), (2) the
maximum wait time (i.e. the longest wait any of the m jobs endured) and (3) the average wait time over all m jobs.
Furthermore, determine these quantities for n processors, where n ranges from 1 to m-1. Observe that there is no
point in considering m or more processors, since then the wait time for each job is necessarily 0. (If there are as
many or more checkers than shoppers, no one ever has to wait.) The n processors in this simulation will be
represented by an array of n processor queues. The job (if any) at the front of a processor queue is considered to
be underway, while the jobs (if any) behind the front job are waiting. When a job arrives it is assigned to a
processor queue of minimum length. (Shoppers naturally go to the shortest line.) If there is more than one
minimum length processor queue, the job will be assigned to the one whose array index is smallest. (Shoppers
go to the closest among several shortest lines.) It is recommended that your simulation maintain one or more
additional queues for storage of those jobs that have not yet arrived, and for those jobs that have been completed.
Your main program for this project will be contained in a file called Simulation.java. The Simulation class
will contain the main() method where program execution begins. The Simulation class is not to be considered a
stand-alone ADT however. It is the client of two ADTs, one of which (Job) will be provided on the webpage,
and the other (Queue) will be created by you. Your program will take one command line argument giving the
name of an input file, and will write to two output files whose names are the name of the input file followed by
the suffixes .rpt and .trc respectively. The .rpt (report) file will contain the results total wait, maximum wait,
and average wait, for n processors where n ranges from 1 to m-1. The .trc (trace) file will contain a detailed
trace of the state of the simulation at those points in time when either an arrival or finish event occur. Your
Makefile for this project will create an executable jar file called Simulation. Thus your program will be run by
doing
% Simulation input_file
and the result will be the creation of two files in your current working directory called input_file.rpt and
input_file.trc. During the initial design and construction phases of your project it may be helpful to send the
contents of the trace file to stdout for diagnostic purposes. A file called SimulationStub.java is included in
2
the examples section of the course website. It contains a few lines of code and some high level pseudo-code that
you may use as a starting point. A Makefile is also provided on the website which you may alter as you see fit.
Input and Output File Formats
The first line of an input file will contain one integer giving the number m of jobs to be run. The next m lines will
each contain two integers separated by a space. These integers will give the arrival time and duration of a job.
The jobs will appear in the input file ordered by arrival times, with the earliest job first. Here is a sample input
file called ex1 representing a batch of 3 jobs:
3
2 2
3 4
5 6
As usual, you may assume that your project will be tested only on correctly formatted input, i.e. there is no need
to consider what to do if the jobs are not ordered by arrival times, or if the file does not contain at least m+1 lines,
etc. The report file corresponding to the above input file follows.
Report file: ex1.rpt
3 Jobs:
(2, 2, *) (3, 4, *) (5, 6, *)
***********************************************************
1 processor: totalWait=4, maxWait=3, averageWait=1.33
2 processors: totalWait=0, maxWait=0, averageWait=0.00
In the corresponding trace file below, the processor queues are labeled 1 through n. The label 0 is reserved for a
storage queue, which initially contains the jobs sorted by arrival time. Each job is represented as a triple:
(arrival, duration, finish). An undefined finish time is represented as *. As jobs are finished, they are
placed at the back of the storage queue. If more than one job finishes at the same time, they are placed in the
storage queue in order of their appearance in the queue array, i.e. minimum index first. When the simulation is
complete, the storage queue will contain all jobs sorted by finish times. Once the simulation is complete for a
given number of processors, the finish times are reset to undefined, and the same jobs are simulated again with
one more processor.
Trace file: ex1.trc
3 Jobs:
(2, 2, *) (3, 4, *) (5, 6, *)
*****************************
1 processor:
*****************************
time=0
0: (2, 2, *) (3, 4, *) (5, 6, *)
1:
time=2
0: (3, 4, *) (5, 6, *)
1: (2, 2, 4)
time=3
0: (5, 6, *)
1: (2, 2, 4) (3, 4, *)
time=4
0: (5, 6, *) (2, 2, 4)
1: (3, 4, 8)
3
time=5
0: (2, 2, 4)
1: (3, 4, 8) (5, 6, *)
time=8
0: (2, 2, 4) (3, 4, 8)
1: (5, 6, 14)
time=14
0: (2, 2, 4) (3, 4, 8) (5, 6, 14)
1:
*****************************
2 processors:
*****************************
time=0
0: (2, 2, *) (3, 4, *) (5, 6, *)
1:
2:
time=2
0: (3, 4, *) (5, 6, *)
1: (2, 2, 4)
2:
time=3
0: (5, 6, *)
1: (2, 2, 4)
2: (3, 4, 7)
time=4
0: (5, 6, *) (2, 2, 4)
1:
2: (3, 4, 7)
time=5
0: (2, 2, 4)
1: (5, 6, 11)
2: (3, 4, 7)
time=7
0: (2, 2, 4) (3, 4, 7)
1: (5, 6, 11)
2:
time=11
0: (2, 2, 4) (3, 4, 7) (5, 6, 11)
1:
2:
Note that the above trace only prints the state of the simulation when it changes, i.e. when either an arrival or
finish event (or both) occur. It is possible for two or more jobs to have the same arrival time. Such jobs will
necessarily appear next to each other in the input file. In this case, the jobs are assigned to a processor queue in
the order in which they appear in the input file. It is also possible that some job finishes at the same time another
job arrives. In this case, complete the finish event first, then complete the arrival event. A number of other
examples will be posted on the class webpage, including cases in which distinct jobs have the same arrival times,
and in which some finish and arrival events occur simultaneously.
4
The format of the trace file seems to imply that there is one storage queue that contains both those jobs which
have not yet arrived, and those which are complete. You may choose to implement the simulation with two
different queues for these purposes. Whatever you choose as your implementation, the output to the trace and
report files must look exactly as above. In addition to one or more storage queues, it will be helpful to maintain
a backup queue (or perhaps a backup array) that stores the jobs in their original order as they appeared in the
input file. This will facilitate setting up the next simulation. Simply copy Job references from the backup queue
(or array) to the storage queue, resetting finish times as you go, then run another simulation with one more
processor.
The Queue ADT
Your Queue ADT will implement the following interface.
// QueueInterface.java
public interface QueueInterface{
 // isEmpty()
 // pre: none
 // post: returns true if this Queue is empty, false otherwise
 public boolean isEmpty();
 // length()
 // pre: none
 // post: returns the length of this Queue.
 public int length();
 // enqueue()
 // adds newItem to back of this Queue
 // pre: none
 // post: !isEmpty()
 public void enqueue(Object newItem);
 // dequeue()
 // deletes and returns item from front of this Queue
 // pre: !isEmpty()
 // post: this Queue will have one fewer element
 public Object dequeue() throws QueueEmptyException;
 // peek()
 // pre: !isEmpty()
 // post: returns item at front of Queue
 public Object peek() throws QueueEmptyException;
 // dequeueAll()
 // sets this Queue to the empty state
 // pre: !isEmpty()
 // post: isEmpty()
 public void dequeueAll() throws QueueEmptyException;
 // toString()
 // overrides Object's toString() method
 public String toString();
}
There are four main differences between the Queue ADT for this project and the IntegerQueue ADT posted in
the Examples/Lectures section of the website. First, your Queue ADT will be based on an underlying linked list
data structure, not an array. Second, the queue elements are Objects not integers. This means that the item field
in your inner Node class must be of type Object, and several parameter lists and return types are now Object
instead of int. Third, there is an additional access function called length() that merely returns the length of a
5
Queue object. This is necessary so that your simulation can determine which processor queue is shortest, and
therefore where a newly arriving job should be assigned. Fourth, the toString() function has been included in
the interface file. This function should assemble a String consisting of the Objects in the Queue separated by
spaces. It should do this by explicitly calling the toString() function of whatever type of Object is stored in the
Queue. Your Queue ADT will be comprised of three files. File QueueInterface.java above is provided on the
webpage, and must not be altered. You will write the files QueueEmptyException.java, and Queue.java. As
usual, you should write an additional test client for your Queue ADT, called QueueTest.java for independent
testing of its operations.
The Job ADT
The file Job.java below contains the definition of the Job class, and will also be posted on the website.
// Job.java
import java.io.*;
public class Job{
 public static final int UNDEF = -1;
 private int arrival;
 private int duration;
 private int finish;
 // constructor
 public Job(int arrival, int duration){
 this.arrival = arrival;
 this.duration = duration;
 this.finish = UNDEF;
 }
 // access functions
 public int getArrival(){return arrival;}
 public int getDuration(){return duration;}
 public int getFinish(){return finish;}
 public int getWaitTime(){
 if( finish==UNDEF ){
 System.err.println("Job: getWaitTime(): undefined finish time");
 System.exit(1);
 }
 return finish-duration-arrival;
 }
 // manipulation procedures
 public void computeFinishTime(int timeNow){finish = timeNow + duration;}
 public void resetFinishTime(){finish = UNDEF;}
 // toString(): overrides Object's toString() method
 public String toString(){
 return "("+arrival+", "
 +duration+", "
 +(finish==UNDEF?"*":String.valueOf(finish))+")";
 }
}
Observe that this simple ADT has a number of self-explanatory access functions and manipulation procedures.
The methods getWaitTime(), computeFinishTime(), and resetFinishTime() automate some basic tasks
needed to perform the simulation. Observe also that toString() should assemble a String representation of a
Job that is consistent with the output file formats above. Thus if you write the toString() function in your
Queue class correctly, you can print a properly formatted Queue to stdout by just doing:
System.out.println(someQueue). To print to one of your output files, say the report file, do
6
PrintWriter report = new PrintWriter(new FileWriter(args[0]+".rpt"));
then
report.println(myQueue);
Notice that there are no interface or exception files associated with the Job ADT. As previously mentioned the
file Job.java is posted on the webpage. It should not be altered in any way.
What to turn in
You may alter the provided Makefile to include submit and test utilities, or alter it in any other way you see fit,
as long as it creates an executable jar file called Simulation, and includes a clean utility. To repeat however,
you are not to alter the files QueueInterface.java or Job.java. Submit the files:
README created by you
Simulation.java created by you
QueueInterface.java provided, do not alter
QueueEmptyException.java created by you
Queue.java created by you
QueueTest.java created by you
Job.java provided, do not alter
Makefile provided, alter as you see fit
to the assignment name pa4. As always start early and ask plenty of questions.