The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+38 votes
3.6k views

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}$

asked in Operating System by Veteran (59.6k points)
edited by | 3.6k views
0
@arjun sir , need an answer to this question
0
hey by mistake i hide sol :) You chek the sol.
0

@Bikram sir pls see this bold text part  Am I thinking right ?


both of which alternate 10 ms CPU bursts with 90 ms I/O bursts.

it means  cpu burst followed with i/o burst

p1=(0-10)cpu burst  since  both the processes were created at nearly the same time p2 inintial waiting will be 10

p2=(10-20)cpu burst

p1=(20-80)(process p1 i/o burst)

p2=(80-100)p2 remaining i/o burst

cpu utilization = cpu burst/total time

(20/100)*100=20%

+3

set2018

Need some slide changes in P1 and P2  I/O burst in your calculation .. rest cpu burst you calculated correctly.

Given 10 ms CPU bursts with 90 ms I/O bursts ..

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

so cpu utilization = (20/100) * 100 = 20%

0
@bikram sir

that was very silly mistake in my method that without getting CPU to p2 I was calculating 0-10 i/o time for cpu

this is not possible,without getting cpu how can process going into block state

thnks a lot for correcting me
+2

Notice --> importance of word "over a long period of time"

Little bit similar question - https://gateoverflow.in/1843/gate2006-65

1 Answer

+73 votes
Best answer

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 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)

answered by Veteran (359k points)
edited by
+1
@arjun sir , Thank you so much :)
Actually the question had clearly defined cycle time as 10ms + 90 ms
But I misinterpreted "both of which alternate 10 ms CPU bursts with 90 ms I/O bursts" as cycle time is 10ms +90 ms +10ms .
+2
that's the power of gateoverflow every question has been explained so nicely by the expert that it seems so easy :)
–1
i did understand that RR explanation what i did  not understand is in FCFS one cycle is completed in the 110 s   a follows     po  p1  p0  p1

                 0   10   20   100 110    

 

so cpu utilization should be 20/110 which is 18% approx so FCFS should be answer by this way
0

Time needed for process is 100 Na so why u take 110 as completion time.

When p2 executed first time then 10 unit of input output for p1 already completed. So, remaining is 80 which is overlapped with p2 input output.

+1
@eddy

given , burst time is 10 ms and I/O time is 90 ms .

In FCFS
 it starts from 0 goes to 10 for p1 cpu burst.
then P1 goes for I/O burst from 10-100.

At same time when p1 complete burst at 10 , p2 burst start and goes to 10-20. after that p2 I/O starts and goes from 20 to 110 .

cpu utilization = cpu burst time/ total time

here total time is 100

within 100 , cpu is used 10 for p1 and 10 for process p2 so in total 10+10 = 20

so cpu utilization = (20/100) * 100 = 20%
+1
What if srtf is preemtive then i think this will give worst because in 19 p1 will finish its Burst time then 90 I/O so 19+90=119 so CPU utilization would become 20/119 so 16.80%

please correct me if i am wrong
0

Hi @Arjun Sir , Everyone 

Even after going through your answer and all comments I could not understand explanation for answer D.

I have drawn Gantt chart in excel . I am getting answer as 20% even for D.

Can you please correct my Gantt chart. I am attaching excel sheet so that you don't have to redraw everything

https://gateoverflow.in/?qa=blob&qa_blobid=1927053546862752235

Sheet 2 in excel workbook contains meaning of symbol

0
@mehul, in question it is mentioned that I/O for both process can be executed in parallel but you are executing in RR manner which is wrong according to your gantt chart you will get cpu utilization as 20/195 = 10.2 %.
0

 Both the processes were created at nearly the same time

 @Arjun Sir, if we consider that p2 comes after p1 in some fraction of time then in case of static priority cpu utilization will come down from 20 to 19.something.

Suppose if p1 has priority 1(low) & p2 has priority 2(high) & AT of p1 & p2 is 0 & 1 then after execution of 1ms of p1 there will be a preemption for p2.

0ms -1ms = p1, 1ms-11ms = p2, 11ms-20ms=p1 then after 101ms p2's chance will come i.e Cpu util = 20/101 = 19.8%.( Now if it will 0.001 rather than 1 then also utilzn != 20)

please reply me that my doubt is valid or not.

0

I am also having similar doubt
19+90=109
20/109=18.34
still srtf is least cpu utilization among all
and srtf is always primitive

Now i got the answer i was relating srtf with longest running time first but here once process1 start then obviously p1 will become lesser burrt time after 1 ms and so first p1 finish then p2 which conclude it is same as fcfs

Answer:

Related questions



Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

41,053 questions
47,651 answers
147,210 comments
62,380 users