Data Structures and Algorithms ASSIGNMENT NO. 4

Data Structures and Algorithms
ASSIGNMENT NO. 4

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.
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 30, 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” 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.
Time Unit: 1
Heap: [(2,1,20), (1,2,10)] [(1,2,10)] [(1,2,10)]
CPU: [(2,1,20)]
(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 is 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. (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)]