CSCI 2110 Computer Science III Data Structures and Algorithms ASSIGNMENT NO. 4 Date Given: Sunday, November 11, 2018 Date Due: Sunday, November 25, 2018, 11.55 PM

In this assignment, you are to build a simple application that demonstrates (simulates) how a CPU uses the heap data structure (priority queue) for process scheduling. First study the example on CPU scheduling from the lectures (Pages 133-134 in the handbook). Download Heap.java given next to the Assignment 4 link.

Each process is an object that is defined by its id, the number of time units required to complete, its priority and its time of arrival.

Create a Process class that defines a Process object: public class Process{ private int id; private int timeReqd; private int priority; private int timeArrival;

//get, set and other methods as required }

In your client program, start by reading a text file that contains a list of processes. For example, the input text file would look something like this:

1 2 10 1 2 1 20 1 3 2 30 2 4 1 15 3 5 1 10 5

This means that Process with id 1 requires 2 time units for processing has a priority of 10, and arrives at time unit 1, process with id 2 requires 1 time unit for processing, has a priority of 20, and arrives at time unit 1, process with id 3 requires 2 time units for processing, has a priority of 30 and arrives at time unit 2, process with id 4 requires 1 time unit for processing, has a priority of 15 and arrives at time unit 3, and finally, process with id 5 requires 1 time unit for processing, has a priority of 10 and arrives at time unit 5.

For the sake of this assignment, assume that the CPU holds and processes each process for only one time unit.

Then, using the heap class, create a heap that stores the processes on a priority basis upon arrival. You may need to modify the Heap class so that it stores Process objects; the key for insertion or retrieval is the priority of the Process object. The CPU takes the process with the highest priority, processes it for one time unit and releases it back into the heap (if it still remains to be processed). If two processes have the same priority, they take turns in being processed that is, when the first process is released back into the heap, it goes behind the second process with the same priority (see example from lecture notes).

The output of your program should be a time unit by time unit listing of the heap contents and the CPU contents. It is slightly different from the way we displayed the output in the example discussed in the lectures, in the sense that in your program you would display the contents of the heap and the CPU at the beginning, during and at the end of each time unit. But the idea is the same. For example, for the above sample text file, the output would look something like this. Do not display the comments given within brackets. They are just for your understanding of how to display the output.

[(1,2,10)]

(The first column indicates that scenario at the beginning of time unit 1. The two processes 1 and 2 have arrived into the heap and the CPU is empty. The second column indicates the scenario during the time unit 1. Process 2 which is the higher priority process is moved from the heap to the CPU being processed by the CPU and it is no longer in the heap. The third column indicates the scenario at the end of the time interval. Process 2 is done, so only process 1 is in the heap.)

Time Unit: 2

Heap: [(3,2,30), (1,2,10)] [(1,2,10)] [(3,1,30),(1,2,10)]

CPU: [(3,2,30)]

(Process 3 enters the heap at the beginning of Time Unit 2, is processed by the CPU and is released back into the heap. Process (3,2,30) changes to (3,1,30) since it now requires one time unit to be processed.)

Time Unit: 3

Heap:[(3,1,30),(4,1,15)(1,2,10)] [(4,1,15),(1,2,10)] [(4,1,15),(1,2,10)]

CPU: [(3,1,30)]

(Process 3 is done at the end of time unit 3).

. and so on.

Your client program should work for a text file containing any arbitrary set of processes, not just the example given above. However, you may assume that once the text file is read, no new processes are added to the list. That is, your program should show the output for each time unit until all the processes in the given text file have been processed by the CPU.

The complete output for the sample text file given above would look as follows. You can format it differently if you wish, but it should convey all the pertinent information.

Time Unit: 1

Heap: [(2,1,20), (1,2,10)] [(1,2,10)] [(1,2,10)] CPU: [(2,1,20)]

Time Unit: 2 Heap: [(3,2,30), (1,2,10)] [(1,2,10)] [(3,1,30),(1,2,10)] CPU: [(3,2,30)]

Time Unit: 3 Heap:[(3,1,30),(4,1,15)(1,2,10)] [(4,1,15),(1,2,10)] [(4,1,15),(1,2,10)] CPU: [(3,1,30)]

Time Unit: 4 Heap:[(4,1,15)(1,2,10)] [(1,2,10)] [(1,2,10)] CPU: [(4,1,15)] Time Unit: 5 Heap:[(1,2,10),(5,1,10)] [(5,1,10)] [(5,1,10),(1,1,10)] CPU: [(1,2,10)]

Time Unit: 6 Heap:[(5,1,10),(1,1,10)] [(1,1,10)] [(1,1,10)] CPU: [(5,1,10)]

Time Unit: 7 Heap: [(1,1,10)] CPU: [(1,1,10)]