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

sim.in(for test) 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

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 if (Q.isEmpty()){ dequeueTime = newTask.arrivalTime + newTask.transactionTime; //System.out.println("dequeue time is: " + dequeueTime); System.out.print(Time + ": " + "Task "+ newTask.id+" starts being processed. "); } Q.enqueue(newTask); } /** 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 System.out.printf("The task " + Q.dequeue().id +" has been completed! "); if (!Q.isEmpty()) { // * TO COMPLETE * // Set dequeueTime by looking at the (but not removing) task at the front of the queue dequeueTime = Time + Q.peek().transactionTime; //System.out.println("dequeue time is: " + dequeueTime); // Set the startTime of this task to Time Q.peek().startTime = Time; // Print out that next job starts processing System.out.printf(Time + ": " + "Task "+ Q.peek().id+" starts being processed. "); // Increment total wait time by the wait time for this task totalWaitTime += Q.peek().startTime - Q.peek().arrivalTime; } } else if (!Q.isEmpty()) System.out.print("Task "+ Q.peek().id+" is being processed, "); System.out.println(); Time++; }// end process }