Write a program which uses an ArrayList to create a priority queue (PQ) of type
ID: 3806946 • Letter: W
Question
Write a program which uses an ArrayList to create a priority queue (PQ) of type PriorityQueue. The data records to be dealt with are simulated process identifiers “pids” which might be managed by the operating system of a computer.
You need to write a method to process records. For our assignment, a process has at least a “pid”, a “priority”, and an “increment” all of which are integer values. It also has a name, which is a String. All the values, pid, priority, increment and name should be stored as a single object in the PQ. This means you will need to store these values inside your class and instantiate the object. Then store those objects in the PQ, but prioritize the process on it’s “priority” value.
The “pid” is the unique identifier given to the process by the operating system when the process is started. The priority is the current priority of the process and is the value on which you are to sort the PQ.
The increment is a value that can be given to a process; this would be the increment to the process’s priority that would be applied by the operating system at the next interval.
In some operating systems, a process that was hogging memory or CPU might
have its priority either raised (to help get the process out of the system and free
up some resources) or lowered (to allow the large number of other processes to
get through the system), and this increment value could be used to change the
priority of a process.
(In a real operating system, the data record that represented the process
would have a number of other attributes, such as memory usage, files open,
parent process, the login id of the user who fired up the process, and such. To
see some of this in action, just log in to any Unix/linux system and run
top to display some of the information. On a Windows machine, the task manager
will display some of this information.)
This assignment will require you to write an insertion sort. Using a PQ (backed by an ArrayList) with an insertion sort to implement a priority queue is only one way to do a priority queue. There are probably better ways, but this is an easy way to learn without making for a huge project.
The main program will do some of the typical things that we have been doing in previous assignments, such as opening/reading files and processing the data in some way, using a class and instantiating and object of your own class, calling methods, etc.
You will need to read in process records (from a file) and insert them into a priority queue (PQ) in descending sorted order based on the value of “key”, which is also the priority. After you finish, you will need to read in another file to delete some processes from the queue. I will publish some example files later. Create your own at first. Call the files “assn4add.txt” and “assn4del.txt” for the items to be added and deleted.
When you add or remove a priority, you will need to keep the list sorted.
NOTE: A PQ requires a “compareTo()” method. You will need to create your own “compareTo” method for this project to work correctly. This may take a little while to figure out, so do not wait until too late to start
“assn4add.txt” text file: https://drive.google.com/open?id=1LusdYPoMyX9jzimgSgLo_PBFNIbZvydsUrSY0HVTYQs
“assn4del.txt” text file: https://drive.google.com/open?id=1YTLyp2qJmQips4Lx6uhLkXbVUB1qW2jeUQZGBvkVTqk
Explanation / Answer
Process.java:
public class Process implements Comparable<Process> {
private int pid, priority, increment;
private String name;
public Process(int pid, int priority, int increment, String name) {
this.pid = pid;
this.priority = priority;
this.increment = increment;
this.name = name;
}
public int getPid() {
return pid;
}
public int getPriority() {
return priority;
}
public int getIncrement() {
return increment;
}
public String getName() {
return name;
}
@Override
public int compareTo(Process p) {
return p.getPriority() < priority ? 1 : p.getPriority() == priority ? 0 : -1;
}
public String toString() {
return name + ", Priority: " + priority + ", pid: " + pid;
}
}
PQ.java:
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
public class PQ {
ArrayList<Process> processQueue;
PQ() {
processQueue = new ArrayList<>();
}
void addProcess(Process p) {
int i=0;
for(i=0; i<processQueue.size(); i++) {
if(processQueue.get(i).compareTo(p) < 0) {
processQueue.add(i, p);
return;
}
}
processQueue.add(i, p);
}
void removeProcess(Process p) {
for(int i=0; i<processQueue.size(); i++) {
if(p.getPid() == processQueue.get(i).getPid()) {
processQueue.remove(i);
return;
}
}
}
void printProcessQueue() {
for(Process p: processQueue) {
System.out.print(p + " => ");
}
System.out.println(" ");
}
ArrayList<Process> readProcesses(String fileName) throws IOException {
ArrayList<Process> list = new ArrayList<>();
BufferedReader reader = new BufferedReader(new FileReader(fileName));
String line;
while((line = reader.readLine()) != null) {
String tokens[] = line.split(",");
list.add(new Process(Integer.parseInt(tokens[1]), Integer.parseInt(tokens[2]), Integer.parseInt(tokens[3]), tokens[0]));
}
reader.close();
return list;
}
public static void main(String[] args) throws IOException {
PQ queue = new PQ();
ArrayList<Process> processAddlist = queue.readProcesses("assn4add.txt");
ArrayList<Process> processDeletelist = queue.readProcesses("assn4del.txt");
for(Process p: processAddlist) {
System.out.println("Going to add Process: " + p);
queue.addProcess(p);
System.out.println("After adding process, Queue:");
queue.printProcessQueue();
}
System.out.println(" ");
for(Process p: processDeletelist) {
System.out.println("Going to Delete Process: " + p);
queue.removeProcess(p);
System.out.println("After deleting process, Queue:");
queue.printProcessQueue();
}
}
}
Sample Output:
Going to add Process: Dog, Priority: 35, pid: 1345
After adding process, Queue:
Dog, Priority: 35, pid: 1345 =>
Going to add Process: Game, Priority: 88, pid: 2355
After adding process, Queue:
Game, Priority: 88, pid: 2355 => Dog, Priority: 35, pid: 1345 =>
Going to add Process: Car, Priority: 98, pid: 3455
After adding process, Queue:
Car, Priority: 98, pid: 3455 => Game, Priority: 88, pid: 2355 => Dog, Priority: 35, pid: 1345 =>
Going to add Process: Barbie, Priority: 32, pid: 9999
After adding process, Queue:
Car, Priority: 98, pid: 3455 => Game, Priority: 88, pid: 2355 => Dog, Priority: 35, pid: 1345 => Barbie, Priority: 32, pid: 9999 =>
Going to add Process: Store, Priority: 44, pid: 2233
After adding process, Queue:
Car, Priority: 98, pid: 3455 => Game, Priority: 88, pid: 2355 => Store, Priority: 44, pid: 2233 => Dog, Priority: 35, pid: 1345 => Barbie, Priority: 32, pid: 9999 =>
Going to add Process: Monkey, Priority: 88, pid: 5555
After adding process, Queue:
Car, Priority: 98, pid: 3455 => Game, Priority: 88, pid: 2355 => Monkey, Priority: 88, pid: 5555 => Store, Priority: 44, pid: 2233 => Dog, Priority: 35, pid: 1345 => Barbie, Priority: 32, pid: 9999 =>
Going to Delete Process: Barbie, Priority: 32, pid: 9999
After deleting process, Queue:
Car, Priority: 98, pid: 3455 => Game, Priority: 88, pid: 2355 => Monkey, Priority: 88, pid: 5555 => Store, Priority: 44, pid: 2233 => Dog, Priority: 35, pid: 1345 =>
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.