Andrew S. Tanenbaum (OS) Edition 4 Exercise 2 Question 43 (Page No. 177)

1 vote
190 views

Measurements of a certain system have shown that the average process runs for a time $T$ before blocking on $I/O$. A process switch requires a time $S$, which is effectively wasted (overhead). For round-robin scheduling with quantum $Q$, give a formula for the CPU efficiency for each of the following:

1. $Q = \infty$
2. $Q > T$
3. $S < Q < T$
4. $Q = S$
5. $Q\: \text{nearly}\: 0$

CPU efficiency =$\frac{\text{useful CPU time}}{ \text{total CPU time}}$

(a) and (b):

The process is executed for time $\textbf T$ and a switch happens when it is blocked.

$\therefore \text {Efficiency} = \dfrac{\textbf T }{\textbf T + \textbf S}$

So, when $\textbf {S = 0}, \text{CPU Efficiency} = \dfrac{\textbf T}{\textbf T} = 100\%$

(c):

$\because \textbf Q<\textbf T$, for each run of $\textbf T$ needs $\dfrac{\textbf T}{\textbf Q}$  process switches, which results in overhead of $\dfrac{\textbf {ST}}{\text Q}$

$\therefore \text {Efficiency }=\dfrac{\textbf T}{\textbf T+\dfrac{\textbf {ST}}{\textbf Q}} = \dfrac{\textbf Q}{\textbf Q + \textbf S}$

So, CPU Efficiency varies from $100\%$ to $50\%$ depending on $\textbf {TQ}$

(d):

Substitute $\textbf Q$ for $\textbf S$ in $\text {(c)}$, and we get $\frac{\textbf Q}{\textbf Q+\textbf Q }= 50%$

So, Efficiency $=50\%$

(e):

$\text{The Efficiency} \to 0\; \text {as} \;\textbf Q \to 0$

So, Efficiency$\approx \textbf0\%$

edited by
0

@
Why did u take S=0 in (a) and (b)?
And in option (c), How did u deduce from the formula that Efficiency will be varying between 50 and 100
Not able to understand it, please explain

Related questions

1
225 views
Explain how time quantum value and context switching time affect each other, in a round-robin scheduling algorithm.
Five batch jobs. $A$ through $E$, arrive at a computer center at almost the same time. They have estimated running times of $10, 6, 2, 4,$ and $8$ minutes. Their (externally determined) priorities are $3, 5, 2, 1,$ and $4,$ respectively, with $5$ being the highest ... the CPU. For $(b)$ through $(d),$ assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
Five jobs are waiting to be run. Their expected run times are $9, 6, 3, 5,$ and $X$. In what order should they be run to minimize average response time? $($Your answer will depend on $X.)$