QuestionQuestion

Transcribed TextTranscribed Text

Introduction to Data Structures Programming Assignment 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 that 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 thesuffixes.rptand.trcrespectively. The.rpt(report)filewillcontaintheresultstotalwait,maximumwait, 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 1 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 22 34 56 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. 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) 2 The label 0 is reserved for a 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 jobs finish at the same time, or finish at the same time as some arrival event. In such cases, do the following steps in order. • If any jobs finish at the same time, complete their finish events in the order that they appear in the queue array, i.e. lowest index first. 3 • If any jobs arrive at the same time, complete their arrival events by placing them at the back of the processor queue that is (1) shortest, and if there are multiple shortest queues then (2) choose the one with lowest index in the queue array. Always complete the finish events first, then complete the arrival events. A number of other examples are 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. 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 that are complete. You may choose to implement the simulation with two different queues for these purposes. However you choose to implement the simulation, 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 (not objects) 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(); } 4 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 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))+")"; 5 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 neededtoperformthesimulation. ObservealsothattoString()shouldassembleaStringrepresentationofa 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 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 Simulation.java QueueInterface.java QueueEmptyException.java Queue.java QueueTest.java Job.java Makefile created by you created by you provided, do not alter created by you created by you created by you provided, do not alter provided, alter as you see fit to the assignment name pa4. As always start early and ask plenty of questions. 6

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.io.*;
import java.util.Scanner;

public class Simulation {

    public static Job getJob(Scanner in) {
       String[] s = in.nextLine().split(" ");
       int a = Integer.parseInt(s[0]);
       int d = Integer.parseInt(s[1]);
       return new Job(a, d);
    }

    public static void main(String[] args) throws IOException {
       Scanner scan = null;
       PrintWriter report = null;
       PrintWriter trace = null;

       Queue store = new Queue();
       Queue temp = new Queue();
       Queue completedJobs = new Queue();

       //Job j = null;
       Queue[] processorQueues = null;
       //int[] prevFinishTime = null;
       //int m;
       //int time = 0;

//     1. check command line arguments
       if (args.length != 1) {
            System.out.println("Usage: Simulation <input_file>");
            System.exit(1);
       }

//     2. open files for reading and writing
      
       Scanner in = new Scanner(new File(args[0]));
       PrintWriter rpt = new PrintWriter(new FileWriter(args[0] + ".rpt"));
       PrintWriter trc = new PrintWriter(new FileWriter(args[0] + ".trc"));...

By purchasing this solution you'll be able to access the following files:
Solution.zip.

$30.00
for this solution

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats