Prioritizing Processes

Application Overview

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:

  • Implement three Comparator<Task> classes that allow the scheduler to follow different algorithms for prioritizing the running of Tasks
  • Compare the results of the different scheduling algorithms on a set of 100 Tasks

Representing Tasks

As 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:

  1. String name: the name of the process (computer program) to be scheduled
  2. int priority: the priority level of the process (lower numbers = higher priority)
  3. int availableTime: the time (in ms) after the scheduler begins that the Task will appear and wait to start running
  4. int length: the duration (in ms) that the Task will take to run after it starts
  5. int deadline: the time (in ms) that the Task needs to complete by in order to be successful

We 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.

Implementing Comparators

You will be implementing a variety of OS scheduling algorithms by creating Comparator<Task>s that compare two Tasks on most of these variables.

  1. We have already implemented 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:

  1. 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

  2. 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

  3. 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

Running the Scheduler

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:

  1. The name of a text file of Tasks, and
  2. The name of which comparator to run. The strings that it expects are available, 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.

Scheduling Tasks by 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 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.

Scheduling Tasks by Availability
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.
Scheduling Tasks by Deadline
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.
Scheduling Tasks by Priority
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.

Comparing the Scheduling Algorithms

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):

  1. Which Comparator led to the fewest number of missed deadlines?
  2. Which Comparator led to the fewest milliseconds of missed deadlines?
  3. Which Comparator led to the fewest priority inversions?
  4. What do the answers to your first three questions tell us about the strengths and weaknesses of the different scheduling algorithms (and Comparators)?

Upload the comparison.txt text file to your GitHub repository to finish this assignment.

Committing Your Progress

Don’t forget to frequently save your progress to GitHub using the add/commit/push commands with git.