BOOK USED - Data Structures and Algorithms in Java, 6th Edition, 2014 One of the
ID: 3684760 • Letter: B
Question
BOOK USED - Data Structures and Algorithms in Java, 6th Edition, 2014
One of the main applications of priority queues is in operating systems - for scheduling jobs on a CPU. In this assignment you are to build a program that schedules simulated CPU jobs. Your program should run in a loop, each iteration of which corresponds to a time slice for the CPU. Each job is assigned a priority, which is an integer between -20 (highest priority) and 19 (lowest priority), inclusive. From among all jobs waiting to be processed in a time slice, the CPU must work on a job with highest priority. In this simulation, each job will also come with a length value, which is an integer between 1 and 10, inclusive, indicating the number of time slices that are needed to process this job. When not interrupted, a job, when scheduled on the CPU. runs for a number of time slices equal to its length. Jobs, however, may be preempted. For example, when a new job with a higher priority arrives, execution of the current job will be suspended, with the unfinished time-slices as the new' job length. For simplicity, overhead from context switches will not be accounted for. Also, jobs of the same priority are scheduled on a first-come-first-served (FCFS) basis. Your simulator must output the name of the job running on the CPU in each time slice and must process a sequence of commands, one per time slice, each of which is of the form "add job name with length n and priority p" or "no new job this slice". Implement the Heap-Based Priority' Queue ADT as discussed in Chapter 9. Refer to Code Fragments 9.8 and 9.9 to begin with. Name your main class PQScheduler. Sample Input and Output Your program (PQScheduler) should read inputs from stdin (System, in in Java) and write outputs to stdout (System.out in Java). See Table I for an example. Note the following: Closely follow the I/O format. Contact the TA for questions about the format. Input/Output lines are case-sensitive. Your program should read a line from stdin at a time until tire end of file is reached. Your program should print out as many output lines as input lines. You may assume that a job name contains no spaces. You may assume that no invalid input lines will be given. At any time slice, output an empty line if no jobs are in the queue. Sec lime slice 7 in Table 1 for an example. Your program should ignore the remaining jobs in the queue and terminate after all the input lines are read and processed. To generate the end of file in a terminal (command prompt), press Ctrl + D on *nix or Ctrl + Z followed by Enter on Windows.Explanation / Answer
PQScheduler.java
import java.io.File;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Scanner;
public class PQScheduler
{
public static void main(String[] args)
{
/**
System.out.println("Heap is ");
HeapSort heap = new HeapSort();
heap.insert(0);
heap.insert(-1);
heap.insert(3);
heap.insert(-2);
heap.insert(-5);
System.out.println("The Min value if " + heap.getRoot());
heap.removeRoot();
System.out.println("The Min value if " + heap.getRoot());
heap.removeRoot();
System.out.println("The Min value if " + heap.getRoot());
heap.removeRoot();
System.out.println("The Min value if " + heap.getRoot());
heap.removeRoot();
System.out.println("The Min value if " + heap.getRoot());
heap.removeRoot();
}
}
**/
HeapSort priorityHeap = new HeapSort();
Scanner sc = new Scanner(System.in);
String input;
/**
String part1 = parts[0];
System.out.println(parts[0]);
String part2 = parts[1];
System.out.println(parts[1]);
**/
boolean counter = true;
int[] lengthArray = new int[40];
String[] nameArray = new String[40];
while(counter)
{
input = sc.nextLine();
//System.out.println("Input: " + input);
String[] parts = input.split("\s+");
if(parts[0].equals("add"))
{
String jobName = parts[2];
int length = Integer.parseInt(parts[5]);
int priority = Integer.parseInt(parts[8]);
priorityHeap.insert(priority);
/**Organize data into arrays will use index to get the priority
* that will be extracted from tree (always add 20 from root to
* find the data index **/
int index = priority + 20;
lengthArray[index] = length;
nameArray[index] = jobName;
//CPU doing job
int root = priorityHeap.getRoot();
int dataIndex = root + 20;
int slice = lengthArray[dataIndex];
if(slice == 0)
{
priorityHeap.removeRoot();
root = priorityHeap.getRoot();
dataIndex = root + 20;
slice = lengthArray[dataIndex];
}
slice = slice - 1;
lengthArray[dataIndex] = slice;
//System.out.println("Slice: " + lengthArray[dataIndex]);
//System.out.println(priorityHeap.getRoot());
//"Job Name: " +
System.out.println(nameArray[dataIndex]);
}
else if(parts[0].equals("no"))
{
//EOF: end of file
if(parts[4].equals("sliceEOF"))
{
System.out.println();
counter = false;
}
else
{
int root = priorityHeap.getRoot();
int index = root + 20;
int length = lengthArray[index];
if(length == 0)
{
priorityHeap.removeRoot();
root = priorityHeap.getRoot();
//System.out.println("New root: " + root);
index = root + 20;
length = lengthArray[index];
}
else
{
}
length = length - 1;
lengthArray[index] = length;
//System.out.println(priorityHeap.getRoot());
//"Job Name: " +
System.out.println(nameArray[index]);
//System.out.println("Slice: " + lengthArray[index]);
}
}
else
{
System.out.println("Illegal operator " + input);
}
//System.out.println("The Min Heap is ");
//priorityHeap.print();
//System.out.println("The Min val is " + priorityHeap.getRoot());
}
}
}
HeapSort.java
public class HeapSort
{
private int[] _sequence;
private int _index;
private int _size;
private final int _root = 0;
public HeapSort()
{
_index = 0;
_sequence = new int[0];
_size = _sequence.length;
}
public boolean isEmpty()
{
return _index == 0;
}
public int parent(int position)
{
return position / 2;
}
public int leftChild(int position)
{
return (2 * position);
}
public int rightChild(int position)
{
return (2 * position) + 1;
}
public boolean isLeaf(int position)
{
if(position >= (_index / 2) && position <= _index)
{
return true;
}
else
{
return false;
}
}
public void swap(int pos1, int pos2)
{
int temp;
temp = _sequence[pos1];
_sequence[pos1] = _sequence[pos2];
_sequence[pos2] = temp;
}
public void bubble(int position)
{
if(!isLeaf(position))
{
if(_sequence[position] > _sequence[leftChild(position)] || _sequence[position] > _sequence[rightChild(position)])
{
if(_sequence[leftChild(position)] < _sequence[rightChild(position)])
{
swap(position, leftChild(position));
bubble(leftChild(position));
}
else
{
swap(position, rightChild(position));
bubble(rightChild(position));
}
}
}
}
public void insert(int element)
{
_index = _index + 1;
_size = _size + 1;
int[] newSequence = new int[_sequence.length + 1];
for(int i = 0; i < _sequence.length; i++)
{
newSequence[i] = _sequence[i];
}
_sequence = newSequence;
//System.out.println(_sequence.length);
_sequence[_index - 1] = element;
//System.out.println("Index: " + _index);
//System.out.println(_sequence[_index]);
int current = _index - 1;
while(_sequence[current] < _sequence[parent(current)])
{
swap(current, parent(current));
current = parent(current);
}
//System.out.println(_sequence[_root]);
}
public void print()
{
for(int i = 1; i <= _index / 2; i++)
{
System.out.println("Parent: " + _sequence[i]);
System.out.println("Left Child: " + _sequence[2 * i]);
System.out.println("Right Child: " + _sequence[2 * i + 1]);
System.out.println();
}
}
public void minHeap()
{
for(int position = (_index / 2); position >= 1; position--)
{
bubble(position);
}
}
public int getRoot()
{
return _sequence[0];
}
public void removeRoot()
{
if(isEmpty())
{
System.out.println("Your tree is empty");
}
else
{
int last = _sequence.length - 1;
_sequence[_root] = _sequence[last];
bubble(_root + 1);
int[] newSequence = new int[_sequence.length - 1];
for(int i = 0; i < _sequence.length - 1; i++)
{
newSequence[i] = _sequence[i + 1];
}
_sequence = newSequence;
//System.out.println(newSequence[1]);
_index--;
}
/**for(int z = 0; z < _sequence.length; z++)
{
System.out.println("Sequence: " + _sequence[z]);
}**/
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.