For FCFS

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

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

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:

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

+15 votes

Best answer

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

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

0

@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}$

+1

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

0

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

0

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

+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

$p_{i}=n*(k-1)*(d+\delta)+(i-1)(d+\Delta)+d$

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

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

$p_{i}=n*(k-1)*(d+\delta)+(i-1)(d+\Delta)+d$

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

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.4k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,654 questions

56,169 answers

193,876 comments

94,298 users