edited by
2,529 views
15 votes
15 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.

edited by

3 Answers

Best answer
18 votes
18 votes
  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$$.
edited by
4 votes
4 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)$
1 votes
1 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)$
edited by

Related questions

4 votes
4 votes
3 answers
2
12 votes
12 votes
1 answer
3
go_editor asked May 30, 2016
1,169 views
Construct a context free grammar (CFG) to generate the following language:$L = \{a^nb^mc^{n+m}: \text{n, m are integers, and } n \geq 1, m \geq 1 \}$
5 votes
5 votes
4 answers
4
go_editor asked May 30, 2016
1,732 views
Construct two nonregular languages $L_1$ and $L_2$ such that $L_1 \cup L_2$ is regular.Prove that the languages $L_1$ and $L_2$ constructed above are nonregular and $L_1 ...