##### 9. A uni-processor computer system only has two process

9. A uni-processor computer system only has two processes, both of which alternate 10 ms CPU bursts with 90 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 ms

Tushar
2 Oct 2014 09:31 am

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

Consider the processes as P and Q

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.

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.

Raman
13 Sep 2017 03:21 pm

Thank u!!

Aparajita Mehta
2 Oct 2014 09:50 am

This sounds correct but please refer question no. 9 from

http://www.btechonline.org/2013/01/gate-questions-os-cpu-scheduling.html

it says correct answer is (a) . I don't understand how :|

Pritam Prasun
2 Oct 2014 09:58 am

The answer given on the referred site is INCORRECT. The above explanation is CORRECT.

joepra
10 Mar 2015 05:20 pm

'