$24
Lab 09 Solution
Purpose:
For this lab, you will implement a fair scheduler in C++ using a Minmax heap.
General Requirements:
In this assignment, you will develop an array-based implementation of a Minmax heap. You will design the scheduler in such a way that every process gets CPU time without waiting for a long time, even if the process has low priority. Each process will be given a pair containing the priority of the element and its expected runtime. In particular, the first element is the priority of that process, i.e., priority(x), where 1 is the highest priority, and 10 is the lowest priority. The second element is the estimated time (y) in milliseconds required for that process to run.
The scheduler divides the CPU time into chunks. The first chunk will run processes for 20 milliseconds, where it will start scheduling processes starting from the highest priority process at the root (min) level. The next chunk will run for 10 milliseconds, where it will start scheduling processes starting with the lowest priority process at the max level. This cycle is repeated until all the processes are finished processing. The time series for the cycle starts with T1 and ends at Tn, which is the last chunk when all of the processes have finished executing. All odd time slots (i.e., T1, T3, T5, etc.) will have a duration of 20ms, and the even time slots (i.e., T2, T4, T6, etc.) will have a duration of 10ms. Each time a process is run, the time in the pair representing the process must be updated with the remaining time for the process to complete. The processes which are completed should be removed from the heap. The initial build of the Minmax heap should use the bottom-up approach. Each time you remove a process, you should heapify the heap.
In the Minmax heap:
The root of T is at A[1].
Here is where the min and max nodes are located:
Min node: floor(lg(i)) = even
Max node: floor(lg(i)) = odd
The grandparent of A[i] is at A[floor(i/4)], if it exists.
The Minmax heap methods should be implemented as follows:
buildheap() - should build the Minmax heap using the bottom up approach.
insert(x) - should insert x into the Minmax heap. This means you should add a new process to all the existing processes in the heap and see how your scheduling order changes with the new process added.
deletemin() - should delete the process with highest priority from the Minmax heap.
deletemax() - should delete the lowest priority process from the Minmax heap.
findmin() - should print the highest priority process from the Minmax heap.
findmax() - should print the lowest priority process from the Minmax heap.
runSchedule() - should print out the scheduling sequence in which each of the processes is executed starting from time chunk T1 and ending with the time chunk Tn. Finally, it should give the scheduling order in which the processes are executed.
The file you will read the processes from will be data.txt. You may hard code the file name in your program if you wish.
In this lab, you should build the heap using the samples which are in the data.txt. After that, your program should have a simple menu like this:
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
Expected output:
data.txt:
(1,10), (3,12), (1,15), (2,8), (5,20), (7,23), (4,5), (10,10)
Below we demonstrate the process of building the heap on the above dataset:
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5-
FindMax
6-
RunSchedule
7-
Exit
6
Initial Minmax heap:
P1
P8 P6
P4P5-P3P7
P2
Scheduling output:
T1: 20 ms
P1(1,0), P3(1,5)
P1 and P3 are executed. P1 is completed and removed from heap.
Updated Minmax heap:
P3
P8 P6
P4P5-P2P7
T2: 10 ms
P8(10,0)
P8 is completed and removed from heap.
Updated Minmax heap:
P3
P5 P6
P4P7–P2
T3: 20 ms
P3(1,0), P4(2,0), P2(3,5)
P3, P4 and P2 are executed. P3 and P4 are completed and removed from heap.
Updated Minmax heap:
P2
P5 P6
P7
T4: 10 ms
P6(7,13)
P6 is executed
Updated Minmax heap:
P2
P5 P6
P7
T5: 20ms
P2(3,0), P7(4,0), P5(5,10)
P2, P7 and P5 are executed. P2 and P7 are completed and removed from heap.
Updated Minmax heap:
P5
P6
T6:10ms
P6(7,3)
P6 is executed
Updated Minmax heap:
P5
P6
T7:20ms
P5(5,0), P6(7,0)
P5 and P6 executed. P5 and P6 are completed and removed from heap.
Updated Minmax heap:
Heap is empty
Scheduling order:
P1 P8 P3 P4 P2 P7 P5 P6
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
1
Add a process:
(4,10)
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
6
Initial Minmax heap:
P1
P8 P6
P4P5-P3P7
P2 P9
Scheduling output:
T1: 20 ms
P1(1,0), P3(1,5)
P1 and P3 are executed. P1 is completed and removed from heap.
Updated Minmax heap:
P3
P8 P6
P4P5–P9P7
P2
T2: 10 ms
P8(10,0)
P8 is completed and removed from heap.
Updated Minmax heap:
P3
P5 P6
P4P2–P9P7
T3: 20 ms
P3(1,0), P4(2,0), P2(3,5)
P3, P4 and P2 are executed. P3 and P4 are completed and removed from heap.
Updated Minmax heap:
P2
P5 P6
P7 P9
T4: 10 ms
P6(7,13)
P6 is executed
Updated Minmax heap:
P2
P5 P6
P7 P9
T5: 20ms
P2(3,0), P9(4,0), P7(4,0)
P2, P9 and P7 are executed. P2, P9 and P7 are completed and removed from heap.
Updated Minmax heap:
P5
P6
T6:10ms
P6(7,3)
P6 is executed
Updated Minmax heap:
P5
P6
T7:20ms
P5(5,0), P6(7,0)
P5 and P6 executed. P5 and P6 are completed and removed from heap.
Updated Minmax heap:
Heap is empty
Scheduling order:
P1 P8 P3 P4 P2 P7 P5 P6
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
4
P1(1,10)
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
5
P8(10,10)
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
2
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
3
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
6
Initial Minmax heap:
P3
P5 P6
P4P2–P9P7
Scheduling output:
T1: 20 ms
P3(1,0), P4(2,3)
P3 and P4 are executed. P3 is completed and removed from heap.
Updated Minmax heap:
P4
P5 P6
P7P2–P9
T2: 10 ms
P6(7,13)
P6 is executed.
Updated Minmax heap:
P4
P5 P6
P7P2–P9
T3: 20 ms
P4(2,0), P2(3,0), P7(4,0)
P4, P2 and P7 are executed. P4, P2 and P7 are completed and removed from heap.
Updated Minmax heap:
P9
P5 P6
T4: 10 ms
P6(7,3)
P6 is executed
Updated Minmax heap:
P9
P5 P6
T5: 20ms
P9(4,0), P5(5,10)
P9 and P5 are executed. P9 is completed and removed from heap.
Updated Minmax heap:
P5
P6
T6:10ms
P6(7,0), P5(5,3)
P6 and P5 are executed. P6 is completed and removed from heap.
Updated Minmax heap:
P5
T7:20ms
P5(5,0)
P5 is executed. P5 is completed and removed from heap.
Updated Minmax heap:
Heap is empty
Scheduling order:
P1 P8 P3 P4 P2 P7 P5 P6
------------------------------------------------------------
Please choose one of the following commands:
1- Insert
2- DeleteMin
3- DeleteMax
4- FindMin
5- FindMax
6- RunSchedule
7- Exit
7
Byebye!
Questions:
Please answer the following questions in not more than 5 lines each and submit it with your implemented code in PDF format.
What is the worst time complexity of each of the operations that you have implemented.
Add process into the scheduler.
Delete minimum priority process from the scheduler.
Delete maximum priority process from the scheduler.
Is the average case complexity equal to the worst case complexity in each of the 3 cases above? If not, mention the average case complexity for each of the above operations in a., b., and c., and also explain the reason in short for the difference.
Submission:
Follow the conventions below to facilitate grading:
Report
Please include your answers (answers.pdf) in your folder before compressing it.
Source Code
Place all your source files (*.cpp, *.hpp) and input files in a single folder with no subfolders.
Name your folder using the convention Lastname_LabX (e.g., Smith_Lab09).
Include a functioning Makefile inside the folder. (The makefile should also include the clean command.)
Verify that your code runs on the lab Linux machines before submission.
Compressed File
Compress using .zip, .rar, or .tar.gz.
Name your file using the convention Lastname_LabX (e.g., Smith_Lab09.zip).
Email
Use the following subject for your email: Lastname_LabX (e.g., Smith_Lab09).
Send your code to l290w868@ku.edu if you are in one of Lei’s sections or to dhwanipandya1401@ku.edu if you are in one of Dhwani’s sections.
Anytime you have a question about the lab, put the word question in the subject of the email.
