The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+23 votes

The sequence __________ is an optimal non-preemptive scheduling sequence for the following jobs which leaves the CPU idle for ________ unit(s) of time.

$$\begin{array}{|c|c|c|} \hline  \textbf{Job} & \textbf{Arrival Time} & \textbf{Burst Time} \\\hline 1 & 0.0 & 9 \\\hline  2 & 0.6 & 5 \\\hline 3 & 1.0 & 1 \\\hline \end{array}$$

  1. $\{3, 2, 1\}, 1$
  2. $\{2, 1, 3\}, 0$
  3. $\{3, 2, 1\}, 0$
  4. $\{1, 2, 3\}, 5$
asked in Operating System by Veteran (59.8k points)
edited by | 3.6k views

3 Answers

+31 votes
Best answer

Answer is (A).
Here, in option B and C they have given CPU idle time is $0$ which is not possible as per schedule (B) and (C).
So, (B) and (C) are eliminated.

Now, lets see (A) and (D):

For (A),

So, idle time is between $0$ and $1$ which is $1$ in case of option (A).

For option (D),

We can see that there is no idle time at all, but in option given idle time is $5$, which is not matching with our chart so option (D) is eliminated.

Therefore, the correct sequence is option (A).

answered by Loyal (8.1k points)
edited by

Why should we wait for 1 sec. initially, although first process has arrived at 0. And this is also a disadvantage of SJF when first process could have a longer burst time and we can call it something like CONVOY Effect in SJF( not exactly, but it happens).......

Edit :- Convoy Effect is phenomenon associated with the First Come First Serve (FCFS) algorithm, in which the whole Operating System slows down due to few slow processes.


"idle time" means the time when cpu is not working. if we see all pairs, then the answer is (A).

example : for pair {2,1,3} --- waiting time = 0.6

How is the idle time for option d is 5 ?
It has to be 0 unit
For option (d) idle time is $0$
How can the CPU be idle if the process p1 is arriving at 0sec of time
To get  the  correct sequence  subsequent CPU idle time should match with given one in options, but in case of D it's not matching so D is not possible also.

CPU ideal time given is incorrect for the corresponding sequence of D hence D is also eliminated.

So correct answer is option A .

Like for A ,

0---1----job 3---2----job 2------7----job 1----16   so idle time is between 0 to 1 which is 1 in case of option A .

for option D,

0---job 1-----9---job 2-----14----job 3----15

 we can see there is no idle time at all ..but in option given idle time is 5 , which is wrong so option D is eliminated.

Vikrant Nagta 6  

The order of jobs for option A is {3,2,1} with given idle time is 1 . In above gantt chart you can see idle time came as 1 which is between 0 to 1 .

Yes  job p1 is arriving at 0.00 but as per given order in options those jobs will be executed. Here order is job 3 first then job 2 and last is job 1 will get executed.


Okay, sir, This statement makes thing clear. 

Subsequent CPU idle time should match with given one in options.

Thanks for the clarification sir
what do they mean by " optimal " here? Is it w.r.t CPU idleness or some other factors ( like waiting time )?
I think, it's in the given sequence we are not unnecessary letting CPU idle..
like in A) option if we go by that sequence the maximum idle time is 1 .

Here, Optimal non-preemptive scheduling sequence implies SJF scheduling.
Indeed Option A is correct but is it a valid scheduling sequence?
At t=0.0, only job-1 is there. It will get CPU as soon as it arrives if we use SJF scheduling algorithm. 

So you're saying that whenever optimal non-preemptive scheduling is given it's nothing but it true always?

In question it's given is it  minimum waiting time ??
if D) option would be {1,2,3},0 then which one will be right? i think in that case we should have to go for A) as there's minimum waiting time
+13 votes

(D) CPU idle time will be 0.
(C) CPU idle time will be 1.
(B) CPU Idle Time will be 0.6
(A) CPU idle time will be 1.

Hence, (A) is correct answer!

answered by Boss (42.7k points)
+5 votes
Answar is A, CPU will be idle for first 1 unit
answered by Junior (883 points)
can u explain ur 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
49,403 questions
53,576 answers
70,852 users