Topic: Priority Queue assignment

In this assignment, you implement a min-heap, use the heap to implement a priority queue, and finally use the priority queue to schedule real-time processes.

You must also design a class Record and a class satisfying the Comparator interface, based on the description below.

For your heap and priority queue, you may take inspiration from the book (chapter 6.6), but your heap will differ from the one in the book. You should implement your min-heap as a class supporting the two methods add (as defined in the interface Collection) and remove (as defined in the interface Queue).

The constructor for both your heap and priority queue classes should take two arguments: an initial capacity, and a Comparator. This is similar to one of the constructors for the standard Priority Queue class.

Your heap add method should use a loop to re-heapify from the bottom up. This is what the code in the textbook does, and you may take inspiration from the book. If the array is full, your code should allocate a larger array and copy the existing heap into the new array, then use the larger array for the heap storage.

Your heap remove method should use a recursive method to re-heapify. This is different from the way the book does it.

Every time you add or remove an element, your heap code must print:

the number of levels in the tree traversed to re-heapify the tree, as well as

the time taken for the entire operation.

To record the time taken, your code should call System.nanoTime at the beginning of each of the two methods and save the value as the start time. It should then call System.nanoTime again at the end, and print the difference between the two times.

The difference may be zero if your system clock does not update the time quickly enough, but otherwise should accurately report how many nanoseconds (billionths of a second) it took to execute your code.

Your priority queue class uses the heap class to provide the priority queue operations add and poll defined in the standard Java class PriorityQueue.

Finally, you must provide a driver class which creates a priority queue (after creating an appropriate comparator), reads a file (specified on the command line), and adds or removes things from the priority queue. The file has lines that have one of two forms:

schedule process deadline duration, or

run time.

where:

process is an arbitrary string,

deadline, duration, and time are longs representing time.

For example, your program might be given a file with the following contents:

schedule lunch 1300 30 schedule work 7200 2300 schedule homework 2359 300 run 2400 

It doesn't really matter what the units of time are in this file, since the scheduler works the same either way. If it helps, you can think of the first two digits as hours and the last two digits as minutes, so that in this example lunch would be scheduled to complete no later than 13:00 (1pm) and 30 minutes are needed for lunch, whereas homework would be scheduled with a deadline of 23:59 (11:59pm), and 3:00 (three hours) must be allowed to complete the homework (for most people, 3 hours is not enough to complete this project!)

Each line beginning with schedule tells your program to insert the corresponding item into the priority queue, with a priority corresponding to its deadline. Items with earlier (smaller) deadlines should be executed first -- this is called Earliest Deadline First scheduling, and is often used in real-time systems (you can read about it in wikipedia if you are interested).

Your program must have a long integer variable to represent time. That variable is initially set to zero, and is increased as the program runs.

Each line beginning with run time tells your program to advance your internal time variable until it reaches time. You do this by repeatedly removing the first item from the priority queue, and advancing the internal time variable by the duration of the process, until the time is reached. If the process completes before the time is reached, a new process is taken from the priority queue. If there are no processes left in the priority queue, the internal time is simply set to time. If, on the other hand, the current process would run past time, it is re-inserted in the priority queue with a duration equal to the remaining time.

So in the example above, time starts at zero, and when your program reads the line that says

 run 2400 

it starts to run the first process in the queue, which will be "lunch". Lunch takes 30 minutes, so your program will remove "lunch" from the queue and set its time variable to 30. The next item removed from the queue will be "homework" (with an earlier deadline than "work"), which takes time 300. So, the time variable is set to 330.

Finally, "work" is removed from the queue. The time is now 330, and work is scheduled to take 2300 time units. But, this run ends at time 2400, whereas if all the work was done now, the run would end at time 2630. So, the time variable is set to 2400, and your program must re-insert "work" into the priority queue with a deadline of 7200 (the deadline hasn't changed) and a duration of 230 (which is 2300 - (2400 - 330), the duration minus the difference between the end time and the start time).

Every time a process is removed from the queue, your program should print current time: busy with process with deadline deadline and duration duration, where current time is the value of the time variable when the process is first removed from the queue.

When a process completes, your program should print current time: done with process. If the process completes after its deadline, your program should print current time: done with process (late).

Every time a process is inserted into the queue, your program should print current time: adding process with deadline deadline and duration duration.

Some examples

Given the above example file, your program should print:

0: adding lunch with deadline 1300 and duration 30 0: adding work with deadline 7200 and duration 2300 0: adding homework with deadline 2359 and duration 300 0: busy with lunch with deadline 1300 and duration 30 30: done with lunch 30: busy with homework with deadline 2359 and duration 300 330: done with homework 330: busy with work with deadline 7200 and duration 2300 2400: adding work with deadline 7200 and duration 230 

For another example, suppose this was your schedule:

schedule work 60 30 schedule fun 40 30 run 50 run 100 

Your program should schedule fun before work (because in this case fun has an earlier deadline), and print the following:

0: adding work with deadline 60 and duration 30 0: adding fun with deadline 40 and duration 30 0: busy with fun with deadline 40 and duration 30 30: done with fun 30: busy with work with deadline 60 and duration 30 50: adding work with deadline 60 and duration 10 50: busy with work with deadline 60 and duration 10 60: done with work 

A slightly more complicated test program for your code is here.

Some suggestions

If you are having trouble debugging your code, you can test your driver class using the standard Java class PriorityQueue. Once your driver class is working, you can change it to use your own PriorityQueue class.

If only your driver class is working with the standard Priority Queue, you will get 50% of the credit for the assignment. Likewise if only your priority queue class is working well, you will get 50% of the credit for the assignment.

There are two kinds of time in this program. The heap methods must keep track of how long a method executes. This is actual time or elapsed time, requested from the operating system by the nanoTime method.

Your program keeps track of the time in the schedule, which is simulated time. Do not confuse the two! The elapsed time is in nanoseconds. The simulated time is in arbitrary units: the example file uses 1/10 of an hour as the unit, but for your own examples, you can decide what units to use (minutes, seconds, hours, days, or anything else).

If in doubt, ignore the calls to System.nanoTime and do everything else.