Scheduling

Question

Consider N processes are sharing the cpu in round robin fashion. If the context switching time is S. What must be the time quantum 'Q' such that the number of context switches are reduced but at the same time each process is guranteed to get its term jobs at the cpu for every 'T' second time ??

Comments

check this

https://gateoverflow.in/1690/gate1998-2-17-ugcnet-dec2012-iii-43

Answer 1

Let us take a simple example of 4 processes P1 , P2 , P3 and P4 . Here n=4

Consider  P1 || P2 || P3 || P4 || P1 || P2 || ..... will be the round robin scheduling order.

Now acc to the question the context swtich time is S , here context is shown by " || "

and time quantum is " Q "

and T is the time taken by a process to again get the CPU after scheduling once .

if we see our scheduling pattern P1 || P2 || P3 || P4 || P1 || P2 ||

P1 gets the CPU again after 4 ( = n) context switch and 3 ( =n-1) time quantum.

So 4S + 3Q <= T

In general, where n is the process count , this becomes

nS + (n-1) Q <= T

(n-1)Q <= T - nS

=> Q <= (T- nS ) / ( n-1)

Answer 2

$\begin{align*} &\Rightarrow \left \{ \left ( S+Q \right )*\left [ {\color{red}{N-1}} \right ] + S \right \} \;\; \leq \;\; T \\ &\Rightarrow Q.\left [ {\color{red}{N-1}} \right ] + S.\left [ {\color{red}{N-1}} \right ] + S\;\; \leq \;\; T \\ &\Rightarrow Q \leq \frac{T-SN}{\left [ {\color{red}{N-1}} \right ]} \end{align*}$

Comments

I am in doubt about the sign whether it should be

{ ( S+Q)∗[N−1]+S} ≤ T  or {( S+Q)∗[N−1]+S}  >= T