The Gateway to Computer Science Excellence
+12 votes

Consider scheduling $n$ processes $P_1, P_2, \dots, P_n$ which are created in this order at almost the same instant. Assume that all processes have exactly one CPU burst of duration $D$ units (and no I/O bursts). Compute the average waiting time and average turn-around time if the scheduling policy is:

  1. FCFS
  2. RR with time slice $d$ units $(d < D)$.

Assume that it takes $\delta$ units of time to switch from one running process to another and $\Delta$ units of time to switch from a terminated process to a running process.

in Operating System by Veteran (104k points)
edited by | 909 views


Avg Turn Around Time= [(n+1)D+(n-1)⧍] / 2

Avg Waiting time = (⧍+D)*(n-1)/2

Its seems correct to me. I got it now. Do one thing write the answer in details. Its seems good.

But I am stuck with RR.

Can you tell me what is the completion time of P1 in terms of d, n and ∂ in RR sceduling?











TAT=D+2D+3D+...nD   +     $\bigtriangleup$+2$\bigtriangleup$+3$\bigtriangleup$+...(n-1)$\bigtriangleup$




2 Answers

+15 votes
Best answer
  1. FCFS

    Waiting time is the time from being ready to being processed.
    $P_1$ does not wait. $P_2$ wait for $D + \Delta$ and for $ 2 \leq i \leq n, W(P_i)) = (i-1) (D + \Delta)$. So, average waiting time $$= \frac{\sum_{i=1}^n (i-1) (D + \Delta)}{n} = \frac{n-1}{2} (D + \Delta).$$

    Turn around time is the time from being ready to being completed.

    $T(P_1) = D$ and $T(P_i) = i. D+ (i-1)\Delta$. So, average turn around time $$= \frac{(n+1)}{2} D + \frac{n-1}{2} \Delta.$$
  2. Round Robin.

    Here since all processes came at once, once $P_1$ is preempted, it can come back only after all other processes. Since all processes are identical, we can get the number of times each will be run by $\left \lceil \frac {D}{d} \right \rceil = x.$ For example, if $D = 100, d=9$ each process will run for $\lceil \frac{100}{9}\rceil = 11$ times. So, if $n = 20$, process $P_5$ will have to wait for $19 \times10 \times(9 + \delta) $ (time other processes execute) $+ 10 \times (\delta)$ (time $P_5$ context switched) $+4 \times (100\%9 + \delta)$ (in the final iteration process $P_5$ waits only for the first $4$ processes.  i.e., for process $i$, waiting time would be

    $W(P_i) = (x-1) (n-1) (\delta + d) + (x-1) \delta+ (i-1) (D \%d + \Delta) $
    $\qquad = (x-1) (n-1)  d + (x-1) n \delta+ (i-1) (D \%d + \Delta) $.

    So, average waiting time would be

    $$=  (x-1) (n-1)  d + (x-1) n \delta + \frac{(n-1)}{2} (D \%d + \Delta).$$

    Turn around time for process $P_i$ will be:

    $T(P_i) = (x-1) (n) (\delta + d) + i . (D \%d) + (i-1) \Delta$. So, average turn around time would be

    $$=  (x-1) (n) (\delta + d) + \frac{(n+1)}{2} (D \%d )+ \frac{n-1}{2}\Delta$$.
by Veteran (422k points)
edited by
@Arjun Sir, Is the waiting time till a process begins execution for the first time accounted for in the case of RR scheduling? I get an additional term $(i-1)*(d+\delta)$ in the waiting time of $P_{i}$
Sir can you please explain the RR part in detail

@Arjun sir, you mistakenly subtract scheduling over ( δ ) also from waiting time of the process

i hope the term (x−1)(n−1)(δ+d) should be replaced by (x−1)(n−1)(d) + (x−1)(n)(δ)

in Round Robbin... Check it once.


@shaik masthan i think you are right because D=((x-1)d+D%d) will be subtracted for each process.δ will not be subtracted


@Shaik Masthan i am not getting how Δ is added in tat of FCFS , and why it is (i-1) times for Pi..pls explain

thanks :)

@Shaik Masthan Thanks. Fine now?

+2 votes
For FCFS only D and $\Delta$ are required.

The first process will complete at D, Second at 2D+$\Delta$, Third at 3D+2$\Delta$..., the nth process at nD+n-1$\Delta$

The arrival time of all process is 0

So Turn around will be Completion - Arrival= D+2D+$\Delta$+3D+2$\Delta$...

$\rightarrow$ D + 2D + 3D ... + nD + $\Delta$ + 2$\Delta$ + ...+ (n-1)$\Delta$

$\rightarrow$ D$\frac{n(n+1)}{2}$+ $\Delta \frac{n(n-1)}{2}$

so average TT will be D$\frac{n+1}{2}$+$\Delta \frac{n-1}{2}$

Waiting time = TT- burst time = D$\frac{n(n+1)}{2}$+ $\Delta \frac{n(n-1)}{2}$ - nD

Average waiting time = $\frac{D\frac{n(n+1)}{2}+ \Delta \frac{n(n-1)}{2}-nD}{n}$

$\rightarrow$ D$\frac{n-1}{2}+ \Delta \frac{n-1}{2}$

Average Waiting time will be = $\frac{(n-1)(D+\Delta)}{2}$

For RR

let D=kd

Completion time for i$^{th}$ process can be  given by following equation


so Turn around can be given by = $D(\delta+n)+\frac{n-1}{2}*(d+\Delta)$

Avg waiting time will be = $D(\delta+n-1)+\frac{n-1}{2}*(d+\Delta)$
by Boss (18.2k points)

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
50,654 questions
56,169 answers
94,298 users