In this lab you will write a program that will simulate the arrival and processing of tasks in a queue over time. The task description will contain the id, arrival time, and transaction time for the task. These will be read in from a le called sim.in. You will have to nd out the average wait times for the tasks from the time they arrive to the time their processing starts. Copy sim.in, Lab.java, TaskQueue.java, Task.java, Node.java, QueueReferenceBased.java, QueueException.java, and QueueInterface.java. In the main function rst a queue is created which is used to store a series of task descriptions from the le sim.in. An instance of a TaskQueue is created which simulates the processing of tasks in a queue. Each task is then inserted into the TaskQueue when that tasks arrival time is reached in the simulation. Each call to the process method of the TaskQueue object simulates one time unit of processing of the task queue and increments the Time variable which is initialized to 0 in the constructor. A new task is enqueued to the task queue when its arrivalTime equals Time. When a task arrives at the front of the queue, i.e., when a task is inserted into an empty queue or the task before it nishes processing at the front of the queue, its startTime is set to Time and the dequeueTime for the task queue is set to the time when this task will be completed (startTime + transactionTime of this task). The wait time for the task is the dierence between its startTime and arrivalTime. When Time equals dequeueTime, the task at the front of the queue is removed.

For each time tick, print out which task, if any, is being processed, started, nished, enqueued. At the end of the simulation, print out the number of tasks processed and the average wait times for all tasks processed. You need to add code only at the places marked with * TO COMPLETE * in the TaskQueue.java le.

NOTE: We believe that it will greatly help your understanding of the lab if you used pen and paper to simulate the arrival and processing of the tasks in sim.in on a timeline, i.e., draw the state of the task queue for each time tick. Increase the number of queues in the TaskQueue class from 1 to 4 and list the average wait time in each case. Use an array of queues and a corresponding array of dequeueTimes. Note that there will still only be a single Time variable, a single tasks variable, and totalWaitTime variable. When there are multiple queues, a newly arriving task should be inserted to one of the queues with minimum number of tasks in it.

Lab.java: Simulating dynamic task arrival and processing in a queue

import java.io.IOException; import java.io.File; import java.util.Scanner;

public class Lab8 { static TaskQueue processingQ; static QueueInterface Q; public static void main(String[] argv) { try { Scanner scanInput = new Scanner(new File("sim.in")); Q = new QueueReferenceBased(); while(scanInput.hasNextLine()){ Scanner scanLine = new Scanner(scanInput.nextLine()); // while(scanLine.hasNext()) { Task X = new Task(); X.id = scanLine.nextInt(); X.arrivalTime = scanLine.nextInt(); X.transactionTime = scanLine.nextInt(); Q.enqueue(X); // } }

scanInput.close(); } catch(IOException e) { System.out.println("Caught IOException: "+ e.getMessage()); } processingQ = new TaskQueue(); while (!Q.isEmpty()){//while more tasks to be added while (!Q.isEmpty() // while more tasks to be added now && processingQ.getTime() == Q.peek().arrivalTime) { processingQ.add(Q.dequeue()); } processingQ.process(); }// all task from the auxiliary queue have been sent to the taskQueue, but they may not have been performed while (!processingQ.isComplete()) // while not all tasks completed processingQ.process(); System.out.println("Number of tasks processed : " + processingQ.getNumTasks() +" " + "Average wait time : " + processingQ.getAvgWaitTime()); } }// end class Lab

Task.java

public class Task { public int id; public int arrivalTime; public int transactionTime; public int startTime; } // end class Task

TaskQueue.java

public class TaskQueue { /** queue of tasks, the task in front of the queue is being processed */ private QueueInterface Q; /** current timer of the class */ private int Time; /** time when the task in front of the queue needs to be removed, * as the transaction is complete */ private int dequeueTime; /** number of tasks processed */ private int tasks; /** total wait time. (for a task, the wait time is the time difference between the moment the task entered the queue and the time when it starts) */ private int totalWaitTime

/** Constructor */ public TaskQueue(){ Time = 0; dequeueTime =-1; tasks = 0; totalWaitTime =0; Q = new QueueReferenceBased(); }

/** get the current time */ public int getTime(){ return Time; }

/** add a task to the queue @param newTask new task to be handled by the queue. */ public void add(Task newTask){ tasks++; System.out.println(Time+ ": Task " + newTask.id + " enqueued (transaction time=" + newTask.transactionTime+")"); // * TO COMPLETE * // enqueue the newTask // if the new task can start immediately, update the dequeue // time and print out that the task is starting } /** get the number of tasks that have been present in the queue @return number of tasks that entered the queue */ public int getNumTasks(){ return tasks;} /** get the current average wait time, i.e. the average time that a task waited between the moment it entered the queue and the moment when it starts to be processed @return the average waiting time */ public double getAvgWaitTime(){ return (double) totalWaitTime/tasks; }

/** tells whether the queue completed all the current task @return return true when all the current tasks have been performed (i.e. the queue is empty; false otherwise (i.e. the queue is not empty) */ public boolean isComplete(){ return Q.isEmpty(); } /** manage the queue. When needed

remove a completed task from the queue

starts a new task

process the current task */ public void process() { System.out.print(Time + ": "); if (Q.isEmpty()) System.out.print("idle"); if (Time==dequeueTime) { // * TO COMPLETE * // Remove task from queue and print out that it has been completed if (!Q.isEmpty()) { // * TO COMPLETE * // Set dequeueTime by looking at the (but not removing) task // at the front of the queue // Set the startTime of this task to Time // Print out that next job starts processing // Increment total wait time by the wait time for this task }} else if (!Q.isEmpty()) System.out.print("Task "+ Q.peek().id+" is being processed,"); System.out.println(); Time++; }// end process }

sim.in 1 2 2 2 2 1 3 7 1 4 8 3 5 8 2 6 8 5 7 9 1 8 9 4 9 10 2 10 11 3

Node.java

public class Node { private E item; private Node next;

public Node(E newItem) { item = newItem; next = null;} // end constructor

public Node(E newItem, Node nextNode) { item = newItem; next = nextNode;} // end constructor

public void setItem(E newItem) { item = newItem;} // end setItem

public E getItem() { return item;} // end getItem

public void setNext(Node nextNode) { next = nextNode;} // end setNext

public Node getNext() { return next; } // end getNext} // end class Node

QueueInterface.java

public interface QueueInterface {

public boolean isEmpty(); public void enqueue(E newItem) throws QueueException;

public E dequeue() throws QueueException;

public void dequeueAll(); public E peek() throws QueueException; } // end QueueInterface

QueueReferenceBased.java

public class QueueReferenceBased implements QueueInterface {

private Node lastNode; public QueueReferenceBased() { lastNode = null; } // end default constructor

/** Determines whether a queue is empty. @return Returns true if the queue is empty; otherwise returns false. */ public boolean isEmpty() { return lastNode == null; } // end isEmpty

/** Removes all items of a queue.

Postcondition: The queue is empty. */ public void dequeueAll() { lastNode = null; } // end dequeueAll

/** Adds an item at the back of a queue.

Precondition: newItem is the item to be inserted.

Postcondition: If the operation was successful, newItem is at the back of the queue. Some implementations may throw QueueException if newItem cannot be added to the queue. */ public void enqueue(E newItem) { Node newNode = new Node(newItem); // insert the new node if (isEmpty()) { // insertion into empty queue newNode.setNext(newNode); } else { // insertion into nonempty queue newNode.setNext(lastNode.getNext()); lastNode.setNext(newNode); } // end if lastNode = newNode; // new node is at back } // end enqueue

/** Retrieves and removes the front of a queue. @return If the queue is not empty, the item that was added to the queue earliest is returned and the item is removed. If the queue is empty, the operation is impossible and QueueException is thrown. */ public E dequeue() throws QueueException { if (!isEmpty()) { // queue is not empty; remove front Node firstNode = lastNode.getNext(); if (firstNode == lastNode) { // special case? lastNode = null; // yes, one node in queue } else { lastNode.setNext(firstNode.getNext()); } // end if return firstNode.getItem(); } else { throw new QueueException("QueueException on dequeue:" + "queue empty"); } // end if } // end dequeue /** Retrieves the item at the front of a queue. @return If the queue is not empty, the item that was added to the queue earliest is returned. If the queue is empty, the operation is impossible and QueueException is thrown. */ public E peek() throws QueueException { if (!isEmpty()) { // queue is not empty; retrieve front Node firstNode = lastNode.getNext(); return firstNode.getItem(); } else { throw new QueueException("QueueException on peek:" + "queue empty"); } // end if } // end peek} // end QueueReferenceBased

QueueException.java

public class QueueException extends RuntimeException {

public QueueException(String s) { super(s); } // end constructor } // end QueueException