Here we discuss some solved questions based on CPU Scheduling Algorithms. These problems have been asked in previous GATE examinations.
Q1. Three process P1, P2 and P3 arrive at time zero. The total time spent by the process in the system is 10ms, 20ms, and 30ms respectively. They spent first 20% of their execution time in doing I/O and the rest 80% in CPU processing. What is the percentage utilization of CPU using FCFS scheduling algorithm?
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%
Q2. Three process p1, P2 and P3 arrive at time zero. Their total execution time is 10ms, 15ms, and 20ms respectively. They spent first 20% of their execution time in doing I/O, next 60% in CPU processing and the last 20% again doing I/O. For what percentage of time was the CPU free? Use Round robin algorithm with time quantum 5ms.
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%
Q3. A uniprocessor computer system has three processes, which alternate 20ms CPU bursts with 80ms I/O bursts. All the processes were created at nearly the same time. The I/O of all the processes can proceed in parallel. What will be the CPU utilization (over a long period of time) using FCFS and Round Robin (time quantum 10ms) for this system?
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