Time slices with AVL Tree Java

Introduction

Last week we implemented Time Slices with a Heap. This week we will implement the same thing with an AVL Tree instead. 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.

Assignment Description

The program will need to perform the following tasks:

Display your name and email address as the first output

Display the following text after your name I certify that this is my own work

Create the ProcessInfo class listed below

o Create necessary getters/setters for the class variables

Implement the AVL Tree class from 996 (will require implementing BST and Tree)

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 an AVL Tree

Print a sample of the Tree 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 Tree, 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 the Tree

o Keep running though the Tree 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.

(page 842 is one example for how to do this)

Recall that an BST/AVL Tree will not allow for duplicate items, but some of your processes have the same priority.

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

+ compareTo(ProcessInfo) : int

+ toString() : String

+ displayCompletedInfo() : String

- endProcess() : void

Rubric

Task Unit Points

Code Compiles

Code Structure

Comments

Implement AVL Tree class

Implement ProcessInfo class

Display Tree

Execute processes in Tree in priority order

Display total run time of all processes when completed

Use appropriate Data Structures

Sample Run

ProcessInfo.java

// Represents a process public class ProcessInfo implements Comparable {

// process details private String processName; private int processId; private int processPriority; private int processRemainingRuntime; private long processStartTime; private long processEndTime; private long processElapsedTime;

// constructor public ProcessInfo(String processName, int processId, int processPriority, int processRemainingRuntime) { this.processName = processName; this.processId = processId; this.processPriority = processPriority; this.processRemainingRuntime = processRemainingRuntime; } // set start time public void setProcessStartTime(long processStartTime) { this.processStartTime = processStartTime; } // get remianing time public int getProcessRemainingRuntime() { return processRemainingRuntime; }

// execute process //returns actual time taken public int executeProcess(int currentTime) { int timeTaken = Math.min(processRemainingRuntime, 10 - processPriority); processRemainingRuntime -= timeTaken; // finished if(processRemainingRuntime == 0) { processEndTime = currentTime + timeTaken; endProcess(); } return timeTaken; }

@Override public String toString() { return String.format( "\tProcess Name: %s \tProcess id: %s \tProcess Priority: %s \tProcess Remaining time: %d", processName, processId, processPriority, processRemainingRuntime); }

@Override public int compareTo(ProcessInfo o) { return o.processPriority - this.processPriority; } public String dislayCompletedInfo() { return String.format("Process Name: %s \t Process Priority: %d \t Completion Time: %d", processName, processPriority, processElapsedTime); } private void endProcess() { processElapsedTime = processEndTime - processStartTime; }

}

Process Id: 20 Process Priority: 3 Process Remaining Runtime: 70 Process Id: 8 Process Id: 77 Process Priority: 2 Process Priority: 8 Process Remaining Runtime: 100 Process Remaining Runtime: 33 Level 0 > Process Name: javac Level 1 > Process Name: clang Process Name: perl Level 2 > Process Name: gcc Process Name: Ilvm Process Name: pythn Process Name: javac Level 3 > Process Name: cc Process Name: ada Process Id: 4 Process Id: 44 Process Id: 16 Process Id: 45 Process Priority: 0 Process Priority: 2 Process Priority: 5 Process Priority: 9 Process Remaining Runtime: 25 Process Remaining Runtime: 22 Process Remaining Runtime: 77 Process Remaining Runtime: 50 Process Id: 20 Process Priority: 4 Process Id: 33 Process Priority: 6 Process Remaining Runtime: 55 Process Remaining Runtime: 44 Results > Process Name: gcc Process Name: Ilvm Process Name: javac Process Name: cc Process Name: ada Process Name: clang Process Name: pythn Process Name: perl Process Name: javac Process Priority: 0 Process Priority: 2 Process Priority: 3 Process Priority: 4 Process Priority: 6 Process Priority: 2 Process Priority: 5 Process Priority: 8 Process Priority: 9 Completion Time: 122 Completion Time: 139 Completion Time: 403 Completion Time: 404 Completion Time: 436 Completion Time: 464 Completion Time: 494 Completion Time: 499 Completion Time: 542 Process Id: 20 Process Priority: 3 Process Remaining Runtime: 70 Process Id: 8 Process Id: 77 Process Priority: 2 Process Priority: 8 Process Remaining Runtime: 100 Process Remaining Runtime: 33 Level 0 > Process Name: javac Level 1 > Process Name: clang Process Name: perl Level 2 > Process Name: gcc Process Name: Ilvm Process Name: pythn Process Name: javac Level 3 > Process Name: cc Process Name: ada Process Id: 4 Process Id: 44 Process Id: 16 Process Id: 45 Process Priority: 0 Process Priority: 2 Process Priority: 5 Process Priority: 9 Process Remaining Runtime: 25 Process Remaining Runtime: 22 Process Remaining Runtime: 77 Process Remaining Runtime: 50 Process Id: 20 Process Priority: 4 Process Id: 33 Process Priority: 6 Process Remaining Runtime: 55 Process Remaining Runtime: 44 Results > Process Name: gcc Process Name: Ilvm Process Name: javac Process Name: cc Process Name: ada Process Name: clang Process Name: pythn Process Name: perl Process Name: javac Process Priority: 0 Process Priority: 2 Process Priority: 3 Process Priority: 4 Process Priority: 6 Process Priority: 2 Process Priority: 5 Process Priority: 8 Process Priority: 9 Completion Time: 122 Completion Time: 139 Completion Time: 403 Completion Time: 404 Completion Time: 436 Completion Time: 464 Completion Time: 494 Completion Time: 499 Completion Time: 542