GATE CSE 2003 | Question: 77

Question

A uni-processor computer system only has two processes, both of which alternate $10$ $\text{ms}$ CPU bursts with $90$ $\text{ms}$ I/O bursts. Both the processes were created at nearly the same time. The I/O of both processes can proceed in parallel. Which of the following scheduling strategies will result in the least CPU utilization (over a long period of time) for this system?

• A. First come first served scheduling
• B. Shortest remaining time first scheduling
• C. Static priority scheduling with different priorities for the two processes
• D. Round robin scheduling with a time quantum of $5$ $\text{ms}$

Comments

P1 goes for I/O burst from 10-100.

P2 I/O starts at 20 and goes from 20 to 110 .

cpu utilization = cpu burst time/ total time

here total time is 100  ( 10 + 90) 

within 100 , cpu is used 10 for p1 and 10 for process p2 so in total 10+10 = 20
in next from 100 to 110 =(P1 runs + p2 i/o runs) ..?

@Bikram sir pls check..

---

after the completion of 1st process, we can execute IO of both processes in parallel?

---

What does exactly "both of which alternate 10ms burst time and 90ms i/o burs time "

Answer 1

CPU utilization $=$ CPU burst time/Total time. 

FCFS: 
from $0-10:$ process $1$
from $10-20:$ process $2$
from $100-110:$ process $1$
from $110-120:$ process $2$
....
So, in every $100$ ms, CPU is utilized for $20$ ms, CPU utilization $= 20\%$

SRTF:
Same as FCFS as CPU burst time is same for all the processes

Static priority scheduling:
Suppose process $1$ is having higher priority. Now, the scheduling will be same as FCFS. If process $2$ is having higher priority, then the scheduling will be as FCFS with process $1$ and process $2$ interchanged. So, CPU utilization remains at $20\%$

Round Robin:
Time quantum given as $5$ ms. 
from $0-5:$ process $1$
from $5-10:$ process $2$
from $10-15:$ process $1$
from $15-20:$ process $2$
from $105-110$: process $1$
from $110-115:$ process $2$
...
So, in $105$ ms, $20$ ms of CPU burst is there. So, utilization $= 20/105 = 19.05\%$

$19.05$ is less than $20$, so answer is (D). 

(Round robin with time quantum 10ms would have made the CPU utilization same for all the schedules)

Comments

preemptive.

nonpremptive version is SJF

---

SRTF will be preemptive ..... https://www.geeksforgeeks.org/preemptive-and-non-preemptive-scheduling/

---

After arriving all process, it's become non-preemptive

Answer 2

We need to find the least cpu utilization i.e. the max cpu wastage. 

Consider the processes as P and Q 

1. Firstly let us consider the FCFS schedule. 

0 - 10 P will use the CPU usage and after that starts the I/O 

11-20 Q will use CPU and ​after 20 ms will start the I/O

P will complete the I/O at time = 10 + 90 = 100; 

Q will complete the I/O at time = 20 + 90 = 110; 

Note that after 100 ms CPU is again starting to be utilized by P. Thus the first cycle ends at 100 ms. 

Thus in the time of 100 sec the CPU was vacant for time = 20 to 100 as after 100 P will again use CPU for the 2nd time. This means CPU wastage of 80 ms. This gives us a  CPU utilization of 20/100 = 20 percent. 

 

2. Now let us consider the case of RR scheduling with time quantum of 5 ms. 

0-5 P will use for CPU 

5- 10 Q will use for CPU 

10-15 P will again use for CPU and complete its required 10 ms time, 

15-20 Q will use CPU and complete its required 10ms time. 

From 15 onwards P will start use for I/O (please note it is 15 onwards). P will continue to use till 15+ 90 = 105. 

from 20 onwards Q will start use for I/O . Q will continue to use till 20 + 90 = 110. 

CPU is not used in the time 20 to 105.  (NOTE that the 2nd cycle will start at the time 105ms and again the CPU becomes available to P )

ie CPU wastage = 20 to 105 = 85 ms . This gives us a CPU utilization of 20 / 105 = 19 percent 

Thus the least CPU utilization in the RR case. Correct ans should be (D). 

Hope this helps to clear your doubt. 

Answer 3

So, given options have FCFS, SRTF, PRIORITY BASED SCHEDULING and RR with TQ=5.

Now, since the burst time are equal, SRTF will work same as FCFS, as well as Priority based scheduling will be same as FCFS. 

(You can check it by preparing a Gantt chart)

So the gantt chart for options A, B and C is as follows

10	20	80	100	110
P1	P2	CPU IDLE TIME	P1	P2

Here, CPU idle time is 80 ms.

Now gantt chart for RR is as follows:

5	10	15	20	85	105	110
P1	P2	P1	P2	CPU IDLE TIME	P1	P2

So, it can be clearly seen, idle time for CPU in RR scheduling is more compared to other options which reduces CPU utilization.

Hence, Answer would option D.

Comments

Please recheck, I think you have considered incorrect timings in RR, time at which I/O of P1 ends should be 105 and then CPU burst of P1 resumes again. Same with P2, you have written that at 105 I/O of P2 begins rather it should be from 110. Let me know if I am wrong.