Here we discuss some solved questions based on CPU Scheduling Algorithms. These problems have been asked in previous GATE examinations.
Solution:
Process | Execution time | I/O time | CPU time |
P1 | 10 | 2 | 8 |
P2 | 20 | 4 | 16 |
P3 | 30 | 6 | 24 |
Since all the processes will first do I/O and then CPU processing, process P1 spends first 20% i.e. 2ms in doing I/O. So CPU is not utilized for the first 2ms. Then P1 spends next 80% i.e. 8ms on processing. By the time P1 finishes with CPU processing P2 has finished its I/O (4ms) and then it gets turn for CPU processing which it does for 16ms and similarly P3 does processing for next 24ms.
Total time = 50ms
CPU utilized for 48ms (starting from 2 and ending at 50)
Therefore utilization = (48/50)*100 = 96%
Solution:
Process | Execution time | I/O burst | CPU burst | I/O Burst |
P1 | 10 | 2 | 6 | 2 |
P2 | 15 | 3 | 9 | 3 |
P3 | 20 | 4 | 12 | 4 |
Total time = 33ms
Free time = 2 + 4 [(0-2) + 29-33)]
Unutilized %age = (6/33)*100 = 18.18%
Solution:
P1 utilizes CPU for 20ms, P2 for next 20ms and P3 for next 20ms. P1 after 20ms goes for I/O for 80ms.
This means it completes I/O at 100ms. After 100ms P1 will again utilize CPU and then P2 after 120ms and so on. This means the CPU remains idle from 60th to 100thms i.e. it is utilized for first 60ms only.
Hence CPU utilization = 60/100 = .60 i.e. 60%
Time slice = 5ms.
P1 utilizes 10ms of CPU and then P2 utilizes 10ms of CPU and the P3 for next 10ms. Hence after 40ms P1 starts with I/O and after 50ms P2 also starts with I/O and P3 after 60ms. Since I/O can be done in parallel, P1 finishes I\O at 120th ms (40 + 80),P2 finishes its I\O at 130th ms (50 +80) and P3 at 140ms(60+80). Therefore we can see that CPU remains idle from 60th to 120th ms.
That is when Round Robin scheduling is used,
Idle time of CPU = 60ms
CPU Utilization = 60/120 = .50 = 50%
Q4.
Process | Burst Time | Arrival time |
P1 | 4 | 0 |
P2 | 2 | 1 |
P3 | 5 | 2 |
Consider the longest remaining time first (LRTF) scheduling algorithm. In LRTF ties are broken by giving priority to the process with the lowest process id. Calculate the average waiting time.
Solution:
Waiting time for
P1 = 0+3+2 = 5
P2 = 2+2+2 = 6
P3 = (6-1) +2 = 7
Hence, Average waiting time = (5+6+7)/3 =6