GATE CSE 2012 | Question: 31

Question

Consider the $3$ processes, $P1, P2$ and $P3$ shown in the table. $$\small \begin{array}{|c|c|c|} \hline \textbf{Process} & \textbf{Arrival Time} & \textbf{Time Units Required} \\\hline \text{P1} & 0 & 5\\\hline \text{P2} & 1 & 7 \\\hline \text{P3} & 3 & 4 \\\hline  \end{array}$$The completion order of the $3$ processes under the policies FCFS and RR$2$ (round robin scheduling with CPU quantum of $2$ time units) are

• A. FCFS: $P1, P2, P3$  RR2: $P1, P2, P3 $
• B. FCFS: $P1, P3, P2$  RR2: $P1, P3, P2$
• C. FCFS: $P1, P2, P3$  RR2: $P1, P3, P2$
• D. FCFS: $P1, P3, P2$  RR2: $P1, P2, P3$

Comments

They started with FCFS to trick us into thinking the question is simple, but then switched to Round Robin, clearly playing with our minds.

---

ready queue working

At time $0$, only $P_1$ has arrived, so it gets the CPU first. It runs for the full time quantum of $2$ units (from time $0$ to $2$), leaving it with $3$ units of remaining work.

While $P_1$ was running, $P_2$ arrived at time $1$. It sits at the front of the ready queue. When $P_1$ is preempted at time $2$, $P_1$ moves to the back of the queue behind $P_2$.

From time $2$ to $4$, $P_2$ takes its turn and runs for $2$ units, leaving it with $5$ units of remaining work.

While $P_2$ was running, $P_3$ arrived at time $3$. It enters the ready queue behind $P_1$. When $P_2$ finishes its turn at time $4$, the ready queue sequence looks exactly like this: $P_1, P_3, P_2$.

From time $4$ to $6$, $P_1$ gets its second turn and runs for $2$ units, leaving it with $1$ unit of remaining work. It moves back to the end of the queue.

and so on till 16

---

Detail Explanation 

Answer 1

FCFS First Come First Server

RR2

In Round Robin We are using the concept called Ready Queue. 
 

Note
 at $t=2$ ,

• $P1$ finishes and sent to Ready Queue
• $P2$ arrives and schedules $P2$

This is the Ready Queue

At $t=3$

• $P3$ arrives at ready queue

At $t =4$

• $P1$ is scheduled as it is the first process to arrive at Ready Queue

Option (C) is correct

Comments

This was a really nice question which indirectly says "Solve it if you understand the Ready Que concept or not." ;)

---

this is the beautiful question clearing the doubt that if any process in came first in ready queue and another process came after that process and previous process already got chance to execute but the new arrived process is not even in ready queue at that time so that the process which came first will get chance to execute

 

---

I would have lost marks if there was an option like P3P1P2 for RR algo.

Answer 2

FCFS :- First come first serve.

Here arrival times of all processes are different, So for completion time just order them according of their arrival time. We get P1,P2,P3. So this eliminates option B & D.

Round Robin - Here when you run round robin algorithm on this 3 processes. completion sequence is P1, P3, P2.As Burst Time for P2 is big, P3 completes before P2.

 

So answer is (C)

Referemce :-

https://en.wikipedia.org/wiki/Round-robin_scheduling

https://en.wikibooks.org/wiki/Operating_System_Design/Scheduling_Processes/FCFS

Comments

I'm not understanding how P3 finishes after P1.

   P1    P2    P3    P1    P2    P3    P1    P2

0       2      4      6      8      10    12     14      16

is the sequence I'm getting.

---

i am getting the sequance p3 p1 p2 for RR

---

round robin takes the first process in ready queue,after time quantum 2 p1 is sent to ready queue and is joined by p3 at time quantum 3. When p2 is preempted in time quantum 4,p1 is executed as it is in ready queue before p3

---

Someone explain how $RR2: P1,P3,P2$ ?

iam getting $RR2: P3,P1,P2$

---

@mcjoshi It is P1 P3 P2 itself..!

---

See the order of completion in round robin

---

Order of computation is

p1

p2

p1

p3

p2

p1

p3

p2

See my answer below for more explanation

---

@mcjoshi ,  After 2 time units, P1 would be added at the end of P2 in the Ready Queue.

while P3 only arrives after 3 units

Therefore, it will be queued after P1 in the Ready Queue.

. So, in your Gantt chart, after P1,P2,   P1 will be executed ,not P3.

I too initially did the same mistake  😅

---

MohanK

same mistake!

Answer 3

option C  is correct  here FCFS is completion order               P1   P2   P3

                                                                                       0    5      12     16

 and RR scheduling    P1   P2   P1   P3   P2   P1   P3    P2

                             0     2      4     6      8     10   11     13     16

  ready queue -  P1,P2,P1,P3 ,P2,P1,P3,P2

           completion order P1, P3 ,P2  hence optionC is correct

Comments

Best answer, I finally understood, other ready queue answers were very confusing.

Answer 4

You can  appy this method to solve every question related to round robin process 

Comments

In the gantt chart, Completion time of P1 = 11, P2 = 16 and P3 = 13.

---

Exactly You are right,Please do correction

Answer 5

Option C is right choice.

https://s30.postimg.org/b4ux9mjbl/IMG_20161222_213043.jpg

https://s30.postimg.org/4sfrzsg9d/IMG_20161222_213059.jpg

Comments

Nice explaination

Answer 6

You can go with the manual approach using the gantt chart.

But this actually a good question, and it utilizes the concept that has already been asked in one of the gate previous year questions.

We'll take a smarter approach.

So we have two schedulings, FCFS and RR with TQ=2.

Now, FCFS is very simple, arrange the processes in increasing order of arrival time and you get the answer.

FCFS: P1 P2 P3

So possible options are A and C

​​​Now, regarding RR, there is a concept that when the time slice of the RR is as large as the largest execution time of the set of processes, then it will behave same as FCFS.

So, if my time quantum was equal to 7(largest execution time in our set), then execution sequence of RR would have been same as FCFS.

So answer would have been A.

But, here our TQ=2, so definitely RR will not work same as FCFS so answer would be C, and cannot be A.

 

 

Comments

So in every premption algorithm we have to use this ready queue concept?