辅导CSCI 2110、讲解Java编程、辅导Java、讲解Algorithms留学生

CSCI 2110 Computer Science III

Data Structuresand 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) howa

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 givennext tothe Assignment 4 link.

Each process isan object that is defined by its id, the numberof timeunitsrequired to complete,

its priority and its time of arrival.

Create a Process class that defines a Process object:

public class Process{

privateint id;

privateint timeReqd;

privateint priority;

privateint timeArrival;

//get, set and other methods asrequired

}

In yourclient program,start by reading a textfile 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 thatProcesswith id1 requires 2 time unitsfor processing has a priority of 10, and

arrivesat timeunit 1,processwith id2 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 forprocessing, 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 timeunit for processing,

has a priority of 10 and arrives at time unit 5.

For thesake ofthis assignment, assumethat the CPU “holds andprocesses”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 modifythe Heap class so that it stores Process objects;the key for

insertion or retrieval is the priority of the Process object. The CPU takes theprocesswith 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 thesame priority (see example fromlecturenotes).

The output of your program should be a time unit by time unit listing of the heapcontents and

the CPU contents. It is slightly different from the waywe displayed the output in the example discussed in thelectures,in thesense that in your program you would display the contents of the

heap and the CPU at thebeginning,during and at the endof each time unit. But the idea is the

same. For example, for the above sampletext file,the output would looksomethinglike this. Do

not display thecomments 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 unit1. The two processes 1 and

2 have arrived into the heap and the CPU is empty.The second column indicates the scenario

during the timeunit 1.Process2 whichis the higher priority process is moved from the heap to

the CPUbeing processedby the CPU and it is no longer in the heap. Thethird column indicates

the scenario atthe endof the time interval.Process 2 is done,so onlyprocess1is 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) sinceit nowrequires one time

unit tobe 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).

…. andso on.

Your client program should workfor a text filecontaining 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 foreach time unit

until all the processesin the given text file have been processed by the CPU.

The complete output forthe sample textfile given above would look as follows.You canformat it

differently if you wish, but itshould convey all the pertinentinformation.

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