edited by
19,394 views
92 votes
92 votes

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?

  1. First come first served scheduling
  2. Shortest remaining time first scheduling
  3. Static priority scheduling with different priorities for the two processes
  4. Round robin scheduling with a time quantum of $5$ $\text{ms}$
edited by

3 Answers

Best answer
167 votes
167 votes

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)

edited by
16 votes
16 votes

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. 

5 votes
5 votes

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.

Answer:

Related questions

55 votes
55 votes
7 answers
2
go_editor asked Apr 24, 2016
14,665 views
Suppose we want to synchronize two concurrent processes $P$ and $Q$ using binary semaphores $S$ and $T$. The code for the processes $P$ and $Q$ is shown below.$$\begin{ar...