Priority queues are commonly used to schedule tasks in real time: as a task becomes available, you add it to the priority queue, and then when you have resources available, you run the task at the top of the queue. We are going to use your priority queue to simulate an operating system (OS) scheduler picking which program to run on your CPU - however, this same process is also used to schedule things like which patients to attend to in the ER.
We are providing you with three Java classes: Task, Scheduler, and AvailableComparator. Task represents the programs you are scheduling, Scheduler represents your OS scheduler, and AvailableComparator is an example of a Comparator<Task>.
Your assignment in this final part of the lab is to:
Comparator<Task> classes that allow the scheduler to follow different algorithms for prioritizing the running of TasksTasksAs you can see by looking at Task.java, Task is a simple class that only holds information about programs. It contains the following public instance variables:
String name: the name of the process (computer program) to be scheduledint priority: the priority level of the process (lower numbers = higher priority)int availableTime: the time (in ms) after the scheduler begins that the Task will appear and wait to start runningint length: the duration (in ms) that the Task will take to run after it startsint deadline: the time (in ms) that the Task needs to complete by in order to be successfulWe have provided you with two text files that contain information about Tasks: jobs10.txt that contains 10 randomly generated Tasks and jobs100.txt that contains 100 randomly generated Tasks.
The text files contain entries that look like this:
terry-furor 4 0 48 140
ample-roads 1 38 40 192
mixes-tones 8 53 33 135
samba-inked 4 100 87 296
Each entry consists of the Task’s name, the Task’s priority, the time at which the Task becomes available, the length of the Task, and the deadline by which the Task should be run. So the first entry tells us that the Task terry-furor has priority 4, arrives at the scheduler at millisecond 0, takes 48 milliseconds to run, and should be run before millisecond 140.
You will be implementing a variety of OS scheduling algorithms by creating Comparator<Task>s that compare two Tasks on most of these variables.
AvailableComparator.java, which sorts Tasks by the time at which they become available to be scheduled; this is equivalent to the First Come First Serve scheduling algorithm.You will implement the following three comparators:
DeadlineComparator.java, which sorts Tasks by the deadline instance variable so that the Task with the earliest (lowest) deadline should be scheduled first. This is equivalent to the Earliest Deadline First scheduling algorithm
LengthComparator.java, which sorts Tasks by the length instance variable so that the Task with the shortest length should be scheduled first. This is equivalent to the Shortest Job First Scheduling algorithm
PriorityComparator.java, which sorts Tasks by the priority instance variable so that the Task with highest priority (lowest number) should be scheduled first. This is equivalent to the Priority scheduling algorithm
Once you have implemented the above Comparators, you will be able to test them using the provided Scheduler class, which simulates an OS scheduler. Scheduler takes two command line arguments:
Tasks, andavailable, deadline, length, and priority.Tasks are added to the Scheduler’s MyPriorityQueue<Task> at the millisecond they become available to schedule. This means that at each millisecond, the Scheduler can only schedule the Tasks with an available time at or before the current millisecond. Because of this, Tasks will not be completely sorted by your Comparator: rather, only the Tasks available (and unfinished) at a specific millisecond will be sorted by the Comparator, and the best Task available at that time will be chosen to run (where “best” is determined differently for different Comparators.)
ReadMe
To earn full credit, you should use your MyPriorityQueue in the Scheduler (which is already implemented) to complete this part of the lab. However, if your MyPriorityQueue is not quite working, you can still earn partial credit by using Java’s built in PriorityQueue class (by replacing every instance of MyPriorityQueue<Task> with PriorityQueue<Task> in Scheduler.java) since one of the goals of this part is to gain practice using priority queues to solve interesting real-world problems.
To help you debug your Comparator<Task> classes and MyPriorityQueue, here are the results of running each of the scheduling algorithms on jobs10.txt. The number before the colon is the current timestep.
0: running terry-furor priority 4 availability 0 length 48 deadline 140 0 other jobs in queue.
50: running ample-roads priority 1 availability 38 length 40 deadline 192 0 other jobs in queue.
90: running mixes-tones priority 8 availability 53 length 33 deadline 135 0 other jobs in queue.
130: running fetch-strum priority 2 availability 130 length 75 deadline 318 1 other jobs in queue.
210: running snare-ideal priority 8 availability 192 length 18 deadline 358 3 other jobs in queue.
230: running roses-octet priority 5 availability 141 length 52 deadline 365 2 other jobs in queue.
290: running mural-savor priority 4 availability 250 length 36 deadline 313 3 other jobs in queue.
330: running aging-sated priority 2 availability 239 length 75 deadline 436 2 other jobs in queue.
410: running crude-maybe priority 9 availability 172 length 78 deadline 345 1 other jobs in queue.
490: running samba-inked priority 4 availability 100 length 87 deadline 296 0 other jobs in queue.
All jobs have been run. 2 deadlines were missed, by a total of 156 milliseconds. There were 4 priority inversions.
As you can see, at milliseconds 0 through 90 there is only one Task available to run at a time, so they are run in order of availability, not length. After millisecond 130, multiple Tasks are available, so the Task currently in the queue with the shortest length is picked to run. For example, samba-inked is available to run at millisecond 100, but doesn’t run until millisecond 490 because it has the longest length.
0: running terry-furor priority 4 availability 0 length 48 deadline 140 0 other jobs in queue.
50: running ample-roads priority 1 availability 38 length 40 deadline 192 0 other jobs in queue.
90: running mixes-tones priority 8 availability 53 length 33 deadline 135 0 other jobs in queue.
130: running samba-inked priority 4 availability 100 length 87 deadline 296 1 other jobs in queue.
220: running fetch-strum priority 2 availability 130 length 75 deadline 318 3 other jobs in queue.
300: running roses-octet priority 5 availability 141 length 52 deadline 365 4 other jobs in queue.
360: running crude-maybe priority 9 availability 172 length 78 deadline 345 3 other jobs in queue.
440: running snare-ideal priority 8 availability 192 length 18 deadline 358 2 other jobs in queue.
460: running aging-sated priority 2 availability 239 length 75 deadline 436 1 other jobs in queue.
540: running mural-savor priority 4 availability 250 length 36 deadline 313 0 other jobs in queue.
All jobs have been run. 3 deadlines were missed, by a total of 292 milliseconds. There were 4 priority inversions.
0: running terry-furor priority 4 availability 0 length 48 deadline 140 0 other jobs in queue.
50: running ample-roads priority 1 availability 38 length 40 deadline 192 0 other jobs in queue.
90: running mixes-tones priority 8 availability 53 length 33 deadline 135 0 other jobs in queue.
130: running samba-inked priority 4 availability 100 length 87 deadline 296 1 other jobs in queue.
220: running fetch-strum priority 2 availability 130 length 75 deadline 318 3 other jobs in queue.
300: running mural-savor priority 4 availability 250 length 36 deadline 313 4 other jobs in queue.
340: running crude-maybe priority 9 availability 172 length 78 deadline 345 3 other jobs in queue.
420: running snare-ideal priority 8 availability 192 length 18 deadline 358 2 other jobs in queue.
440: running roses-octet priority 5 availability 141 length 52 deadline 365 1 other jobs in queue.
500: running aging-sated priority 2 availability 239 length 75 deadline 436 0 other jobs in queue.
All jobs have been run. 4 deadlines were missed, by a total of 303 milliseconds. There were 5 priority inversions.
0: running terry-furor priority 4 availability 0 length 48 deadline 140 0 other jobs in queue.
50: running ample-roads priority 1 availability 38 length 40 deadline 192 0 other jobs in queue.
90: running mixes-tones priority 8 availability 53 length 33 deadline 135 0 other jobs in queue.
130: running fetch-strum priority 2 availability 130 length 75 deadline 318 1 other jobs in queue.
210: running samba-inked priority 4 availability 100 length 87 deadline 296 3 other jobs in queue.
300: running aging-sated priority 2 availability 239 length 75 deadline 436 4 other jobs in queue.
380: running mural-savor priority 4 availability 250 length 36 deadline 313 3 other jobs in queue.
420: running roses-octet priority 5 availability 141 length 52 deadline 365 2 other jobs in queue.
480: running snare-ideal priority 8 availability 192 length 18 deadline 358 1 other jobs in queue.
500: running crude-maybe priority 9 availability 172 length 78 deadline 345 0 other jobs in queue.
All jobs have been run. 4 deadlines were missed, by a total of 351 milliseconds. There were 0 priority inversions.
To practice comparing the results of different algorithms supported by our data structures, we will compare the results of running the scheduler with the four different Comparators on the provided jobs100.txt text file.
Create a new text file called comparison.txt to store your results and comparisons. First, run the Scheduler with the jobs100.txt input using each of the four Comparators. Save the last line of output from each run of the Scheduler to the top of your comparison.txt file, preceded by the name of the Comparator used.
Hint
As an example of the output we are asking you to save, this is what the top of the comparison.txt file would look like if we instead used the jobs10.txt file as input:
Available: All jobs have been run. 3 deadlines were missed, by a total of 292 milliseconds. There were 4 priority inversions.
Deadline: All jobs have been run. 4 deadlines were missed, by a total of 303 milliseconds. There were 5 priority inversions.
Length: All jobs have been run. 2 deadlines were missed, by a total of 156 milliseconds. There were 4 priority inversions.
Priority: All jobs have been run. 4 deadlines were missed, by a total of 351 milliseconds. There were 0 priority inversions.
Second, answer the following four questions at the end of your comparison.txt text file (based on the results of the input file jobs100.txt):
Comparator led to the fewest number of missed deadlines?Comparator led to the fewest milliseconds of missed deadlines?Comparator led to the fewest priority inversions?Comparators)?Upload the comparison.txt text file to your GitHub repository to finish this assignment.
Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.