PriorityQueue class, which is to have methods to support simulations as described below. You needn't implement all the binary heap methods of the text, although you may need to add methods. You needn't add documentation to the text's methods. Heap insertion should signal overflow by throwing a OutOfMemoryError, but the priority queue insertion method should catch this error, and print a message that the element is not being inserted.
Elements of the priority queue are to be of a class Task. Note that this class will have to implement the Comparable interface.
All simulations are to be of a k-processor system where tasks arrive at random times, with random priorities and random time requirements. Tasks may not be interrupted once they begin executing, even if a higher-priority task enters the queue. The priorities and time requirements are to be integers taken uniformly from the range 0 through maxPriority and 1 through maxTimeRequired, respectively. Higher priorities are to correspond to larger integers. The probability of a task being added in a given time step is to be 1/m for some integer m. The PriorityQueue should have a constructor with four integer parameters corresponding to k, maxPriority, maxTimeRequired, and m.
You need only be able to support the second type of simulation described in the Weiss text. In the this sort of simulation, the only time steps that are simulated explicitly are those in which a task is added or deleted from the queue. The time intervals are to be chosen randomly and uniformly from the range 1 through 2m-1, where m is the integer of the previous paragraph.
If a task is added during a given time step, then it should be considered for processing during that time step, if a processor is or becomes available at that time step. In any case, if a task completes during a time step and the queue is not empty, a task from the queue should be started at that same time step (rather than waiting one time step to start it).
Discrete time steps are to be used in the simulation, beginning with time 0. Assume that the first task arrives at time 0. If a processor is free by the beginning of a given time step, then the task in the priority queue, if any, with the highest (that is, the highest-numbered) priority is deleted from the queue and its execution is simulated for whatever time it requires. If more than one processor is available, assign the task to the processor that has been waiting the longest. Initially, assume that lower-numbered processors have been waiting longer than higher-numbered processors.
Please use separate Random objects, seeded with the values 1, 2, and 3 respectively, to generate the arrival time of events, the priorities, and the execution times. You need only seed these objects once for each priority queue, when it is constructed.
The PriorityQueue class is to have a constructor as described above, and a method simulate to run a simulation for a given integer number of time steps. It should also have five public methods for statistical summaries. The getSize() method should return an integer giving the number of tasks currently in the priority queue. The printProcessorStatus() method should print the task currently being executed by each processor. The printNumberOfTasksCompleted() method should print a list of the number of tasks completed by each processor, and also the total number of tasks completed by all processors. The traverse() method should return a List of the tasks currently in the queue. This method should construct the list from highest-priority items to lowest, without destroying the queue. Finally, there should be a resetCounters() method, to reset the counters used by a simulation, in case a second simulation is performed on the same priority queue.
The third and fourth of these methods may use the default print method for Lists, rather than more elaborate formatting. The second and third method should print to System.out. The second method may print null for any processor that is not currently executing a task. As always, you may provide any additional methods and classes that you find useful.
Use test file A3.java (available on the class web site) to test your implementation. To sensibly print the statistics, you will need to give each task an identifier and each processor a number. Please make sure that no two tasks have the same identifier. Note that in the test class A3, the first pair of simulations uses an average task length that is equal to the mean interval between task arrivals. For the second group it is smaller, while it is larger for the third pair.
Update the PriorityQueue class to allow each processor to maintain its own heap of pending tasks. More precisely, add methods simulate2 and printSizes() to the class. The simulate2 method is to behave like simulate, except that each processor is to maintain its own heap of pending tasks. Whenever a task is created, it should be assigned randomly and uniformly to one of the k processors. Please use a Random object with seed 0 to control this assignment. You may assign this seed in the simulate2 method. The printSizes method is to print the sizes of each of the k task heaps separately, as well as the total of these heap sizes, using the format of the simulate2 method.
Note that the testing done by the A3 class will still try to print the size and contents of the single heap of tasks. You can simply ignore this, except that you should make sure that the heap of tasks used by the non-extra-credit portion of the assignment has a value -- presumably a default initial value of an empty heap.
Finally, note that a maximum of 30 points of extra credit will be given in this course. If you have taken the pilot placement exam for CS 146, then you will get no points for doing this extra credit.