Time slices with Heap / Java

In the chapter it was mentioned that you can use Heaps to create Priority Queues. Priority Queues are helpful for Operating System process scheduling where you want to give each process a chance to run, but processes with a higher priority get more CPU time. (granted, in an actual OS implementation, you would also pause a process when it was waiting for I/O and let another process execute, but we arent worrying about I/O for this assignment). In this assignment you will implement a basic Process Scheduler, where each process will get a little bit of time to execute before allowing the next process to run. The amount of time each process gets will be based on its priority (0-9, 0 being the highest, and 9 being the lowest). A task with a priority of 0 will get 10 milliseconds to execute, and a task with a priority of 9 will get 1 millisecond to execute. Each process will need to run to completion, keeping track of when it started and when it finished, so that the total runtime for a process can be determined and displayed at the end.

The program will need to perform the following tasks:

Create the ProcessInfo class listed below

o Create necessary getters/setters for the class variables

Implement the Heap class (see pic for info)

Read the process information from a file (sample provided)

o Create a processInfo object for each process in the file

Add these processInfo objects to a Heap, sorted so that the lowest priority process is the root

Print a sample of the Heap by level

Run through the processes, allocating time for each process based on its priority (i.e. 0 priority gets 10 seconds, 9 priority gets 1 second)

o Thus during the first time through the Heap, the process with Priority 0 gets 10 milliseconds to execution time, then the two process with Priority of 2 get 8 miliseconds each, and so on (use Thread.sleep(milliseconds) to sleep the process as you need to know the total time it took for a process to complete.) Each process gets a chance to execute, just for less and less time, so that the top priority processes get more time to execute.

o If a process is not complete, then it needs to stay in a Heap (HINT: you may need more than 1 Heap)

o Keep running though the Heap until all processes have completed executing

o Keep track of completed processes so that you can print them at the end Display each completed process, and the runtime that it took for each to complete

Processes will need to know when they started and when they stopped executing. (see pic for info)

processList.txt

javac|20|3|70 javac|45|9|50 gcc|4|0|25 llvm|44|2|22 clang|8|2|100 cc|20|4|55 ada|33|6|44 python|16|5|77 perl|77|8|33

ProcessInfo

String processName

int processId

int ProcessPriority

int processRemainingRuntime

long processStartTime

long processEndTime

long processElapsedTime

+ ProcessInfo()

+ executeProcess(int): boolean

+ comapreTo(ProcessInfo): int

+ toString(): String

+ displayCompletedInfo(): String

- endProcess(): void

Make Sure:

Implement the heap class

Implement ProcessInfo class

Display Heap

Execute processes in Heap in priority order

Display total run time of all processes when completed

Sample Run:

898 Chapter 23 Sorting 23.6.4 The Heap Class Now you are ready to design and implement the Figure 23.16. Its implementation is given in Listing 23.9. eady to design and implement the Heap class. The class diagram is shown in Heap> -list: java.util.ArrayList +Heap) +Heap(objects: E[]) +add(newObject: E): void +remove(): E +getSize(): int +isEmpty(): boolean Creates a default empty Heap. Creates a Heap with the specified objects. Adds a new object to the heap. Removes the root from the heap and returns it. Returns the size of the heap. Returns true if the heap is empty. FIGURE 23.16 The Heap class provides operations for manipulating a heap. LISTING 23.9 Heap.java 1 public class Heap> { 2 private java.util.ArrayList list = new java.util.ArrayList(); internal heap representation /** Create a default heap */ public Heap() { no-arg constructor OOO constructor /** Create a heap from an array of objects */ public Heap (E[] objects) { for (int i = 0; i 0) { int parentIndex = (current Index - 1) / 2; 1 / Swap if the current object is greater than its parent if (list.get(current Index).compareTo( list.get (parent Index)) > 0) { E temp = list.get(current Index): list.set(current Index, list.get (parent Index)): list.set(parent Index, temp): 20 swap with parent else break; // The tree is a heap now heap now current Index = parent Index: ** Remove the root from the heap public E remove() { remove the root 23.6 Heap Sort 899 if (list.size() == 0) return null; empty heap E removedObject = list.get(0); list.set(0, list.get(list.size() - list.remove(list.size() - 1): 41 1)): root new root remove the last int current Index = 0; while (current Index = list.size()) break; // The tree is a heap int maxIndex = leftChildIndex; if (rightChildIndex = 0; ) System.out.print(a[i]): 223.4 Design an On) time algorithm for computing the sum of numbers from alto n2 for nl 2). Can you design an O(l) for performing the same task? 225 Example 7 in Section 22.3 assumes n = 2. Revise the algorithm for an arbitrary and prove that the complexity is still O(logn). Process Remaining Runtime: 25 Current Level: 0 Process Name: gcc Process Id: 4 Process Priority: 0 Current Level: 1 Process Name: Ilvm Process Id: 44 Process Priority: 2 Process Name: clang Process Id: 8 Process Priority: 2 100 Current Level: 2 Process Name: javac Process Id: 20 Process Priority: 3 Process Name: python Process Id: 16 Process Priority:5 Process Remaining Runtime: 22 Process Remaining Runtime: Process Remaining Runtime: 70 Process Remaining Runtime: 77 Process Id: 33 Process Id: 45 Process Priority: 6 Process Priority: 9 Process Remaining Runtime: 44 Process Remaining Runtime: 50 Process Name: ada Process Name: javac Current Level: 3 Process Name: perl Process Name: CC Process Id: 77 P rocess Id: 20 Process Priority: 8 Process Priority: 4 Process Remaining Runtime: 33 Process Remaining Runtime: 55 Process Name: gcc Process Priority: 0 Process Name: llvm Process Priority: 2 Process Name: javac Process Priority: 3 Process Name: CC P rocess Priority: 4 Process Name: ada Process Priority: 6 Process Name: clang Process Priority: 2 Process Name: python Process Priority: 5 Process Name: perl Process Priority: 8 Process Name: javac Process Priority: 9 Completion Time: 122 Completion Time: 129 Completion Time: 409 Completion Time: 410 Completion Time: 446 Completion Time: 474 Completion Time: 506 Completion Time: 511 Completion Time: 554 898 Chapter 23 Sorting 23.6.4 The Heap Class Now you are ready to design and implement the Figure 23.16. Its implementation is given in Listing 23.9. eady to design and implement the Heap class. The class diagram is shown in Heap> -list: java.util.ArrayList +Heap) +Heap(objects: E[]) +add(newObject: E): void +remove(): E +getSize(): int +isEmpty(): boolean Creates a default empty Heap. Creates a Heap with the specified objects. Adds a new object to the heap. Removes the root from the heap and returns it. Returns the size of the heap. Returns true if the heap is empty. FIGURE 23.16 The Heap class provides operations for manipulating a heap. LISTING 23.9 Heap.java 1 public class Heap> { 2 private java.util.ArrayList list = new java.util.ArrayList(); internal heap representation /** Create a default heap */ public Heap() { no-arg constructor OOO constructor /** Create a heap from an array of objects */ public Heap (E[] objects) { for (int i = 0; i 0) { int parentIndex = (current Index - 1) / 2; 1 / Swap if the current object is greater than its parent if (list.get(current Index).compareTo( list.get (parent Index)) > 0) { E temp = list.get(current Index): list.set(current Index, list.get (parent Index)): list.set(parent Index, temp): 20 swap with parent else break; // The tree is a heap now heap now current Index = parent Index: ** Remove the root from the heap public E remove() { remove the root 23.6 Heap Sort 899 if (list.size() == 0) return null; empty heap E removedObject = list.get(0); list.set(0, list.get(list.size() - list.remove(list.size() - 1): 41 1)): root new root remove the last int current Index = 0; while (current Index = list.size()) break; // The tree is a heap int maxIndex = leftChildIndex; if (rightChildIndex = 0; ) System.out.print(a[i]): 223.4 Design an On) time algorithm for computing the sum of numbers from alto n2 for nl 2). Can you design an O(l) for performing the same task? 225 Example 7 in Section 22.3 assumes n = 2. Revise the algorithm for an arbitrary and prove that the complexity is still O(logn). Process Remaining Runtime: 25 Current Level: 0 Process Name: gcc Process Id: 4 Process Priority: 0 Current Level: 1 Process Name: Ilvm Process Id: 44 Process Priority: 2 Process Name: clang Process Id: 8 Process Priority: 2 100 Current Level: 2 Process Name: javac Process Id: 20 Process Priority: 3 Process Name: python Process Id: 16 Process Priority:5 Process Remaining Runtime: 22 Process Remaining Runtime: Process Remaining Runtime: 70 Process Remaining Runtime: 77 Process Id: 33 Process Id: 45 Process Priority: 6 Process Priority: 9 Process Remaining Runtime: 44 Process Remaining Runtime: 50 Process Name: ada Process Name: javac Current Level: 3 Process Name: perl Process Name: CC Process Id: 77 P rocess Id: 20 Process Priority: 8 Process Priority: 4 Process Remaining Runtime: 33 Process Remaining Runtime: 55 Process Name: gcc Process Priority: 0 Process Name: llvm Process Priority: 2 Process Name: javac Process Priority: 3 Process Name: CC P rocess Priority: 4 Process Name: ada Process Priority: 6 Process Name: clang Process Priority: 2 Process Name: python Process Priority: 5 Process Name: perl Process Priority: 8 Process Name: javac Process Priority: 9 Completion Time: 122 Completion Time: 129 Completion Time: 409 Completion Time: 410 Completion Time: 446 Completion Time: 474 Completion Time: 506 Completion Time: 511 Completion Time: 554