GATE CSE 2006 | Question: 65

Question

Consider three processes, all arriving at time zero, with total execution time of $10$, $20$ and $30$ units, respectively. Each process spends the first $20\%$ of execution time doing I/O, the next $70\%$ of time doing computation, and the last $10\%$ of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of time does the CPU remain idle?

• A. $0\%$
• B. $10.6\%$
• C. $30.0\%$
• D. $89.4\%$

Comments

The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst

Here it is mentioned SRTF but told that it will schedule a new process only when blocked by I/O or finishes its burst. If arrival time and burst time are given such that preemption is possible, should we apply preemption as in SRTF, or only in those two cases?

---

@Kush_Bhatt I also have the same doubt. 

But in the video solution, @Sachin Mittal 1 sir considered standard SRTF Scheduling for variation of this problem:

But if their is explicitly mentionioned:

"schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst."

we should stick with it? 

---

The percentages are appearing as \text{20%}. Pls look into this!!!

Answer 1

$$\text{CPU Idle time}=\frac{2+3}{47} \times 100 = 10.6383\%$$

Answer is option (B).

Comments

And what if the I/O operations doesn't overlaps.

---

@amarVashishth, at t=44, the CPU burst of process p3 is done, so why should CPU wait for p3 to complete its IO? Kindly clarify.

---

forgot the last i/o

Answer 2

Process	TOTAL BURST  TIME	I/O TIME	CPU TIME	I/O TIME
P1	10	(10*20/100)=2	(10*70/100)=7	(10*10/100)=1
P2	20	(20*20/100)=4	(20*70/100)=14	(20*10/100)=2
P3	30	(30*20/100)=6	(30*70/100)=21	(30*10/100)=3

GANTT CHART

Idle

P1

P2

P3

Idle

0                          2                     9                     23                  44                    47

total time=47

idle time= 2+3=5

% of idle time= (5/47)*100=10.6%

Answer 3

Let three processes be p0, p1 and p2. Their execution time is 10, 20 and 30 respectively. p0 spends first 2 time units in I/O, 7 units of CPU time and finally 1 unit in I/O. p1 spends first 4 units in I/O, 14 units of CPU time and finally 2 units in I/O. p2 spends first 6 units in I/O, 21 units of CPU time and finally 3 units in I/O.

 idle   p0    p1     p2    idle
0    2     9     23     44     47

Total time spent = 47
Idle time = 2 + 3 = 5
Percentage of idle time = (5/47)*100 = 10.6 %

Answer 4

Option "B" 

Answer 5

Answer will be 10.6382

Comments

Good explanation

Answer 6

	$i/o$	$cpu$	$i/o$
1	2	7	1
2	4	14	2
3	6	21	3

 

Assume that all I/O operations can be overlapped as much as possible.

 

$\underbrace{0-2}$	$\underbrace{2-9}$	$\underbrace{9-23}$	$\underbrace{23-44}$	$\underbrace{44-47}$
$idle$	$p1$	$p2$	$p3$	$idle$

$\dfrac{5}{47}\times 100=10.6\%$