3.6k views

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$
edited | 3.6k views

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),
$$0-1\underset{\text{job }3}{-}2\underset{\text{job }2}{-}7\underset{\text{job }1}{-}16$$

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

For option (D),
$$0\underset{\text{job }1}{-}9\underset{\text{job }2}{-}14\underset{\text{job }3}{-}15$$

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

edited ago
+7

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.

http://www.geeksforgeeks.org/convoy-effect-operating-systems/

+6

"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

+6
How is the idle time for option d is 5 ?
It has to be 0 unit
+5
For option (d) idle time is $0$
+2
How can the CPU be idle if the process p1 is arriving at 0sec of time
+8
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.
+4

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.

+4

Okay, sir, This statement makes thing clear.

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

+1
Thanks for the clarification sir
0
what do they mean by " optimal " here? Is it w.r.t CPU idleness or some other factors ( like waiting time )?
0
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 .
+3

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.

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

In question it's given optimal..so 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

(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.

Answar is A, CPU will be idle for first 1 unit
0
can u explain ur answer !

1
2