George Mason University
DEPARTMENT OF COMPUTER SCIENCE
CS471 - Operating Systems - Spring 2000
Summary of Queueing Network Formulas
basic parameters:
Si = mean service time per visit server i
Vi = mean number of visits to server i
Di = demand for server i = Vi*Si
Z = think time (for time sharing system)
N = load (closed system)
basic metrics:
Ui = utilization server i
Xi = throughput server i
Qi = mean queue length server i
Ri = mean response time per visit server i (includes service)
Ti = mean total residence time server i (Ti = Vi*Ri)
R = system response time
X = system throughput
load-dependent:
Add parameter N after any of the above
Xi(N), Qi(N), R(N), X(N), etc.
utilization law
Ui = Xi*Si = X*Di
Little's law
Qi = Xi*Ri = X*Ti
Forced flow law:
Xi = X*Vi
Response time law:
R = sum(Vi*Ri) = sum(Ti)
Response time formula for time sharing system
R = N/X - Z
Response time estimator for open system
Ri = Si/(1-Si*Xi), and then R = sum{ Vi*Ri }
system bottleneck
server b for which {Di} is largest; Db = max{Di}
X(N) < 1/Db
R(N) > NDb - Z
---------------------
Recursive Mean Value Algorithm (MVA)
with parameters Vi, Si, N, and Z:
Initialize Qi[0]=0 all i
For k=1,2,...,N do {
for all i {Ri[k] = Si*(1+Qi[k-1]) }
R[k] = SUM {Vi*Ri[k]}
X[k] = k/(R[k]+Z)
for all i {Qi[k] = X[k]*Vi*Ri[k] }
}
Recursive Mean Value Algorithm (MVA)
with parameters Di, N, and Z and Ti=Vi*Ri
is total residence time at server i:
Initialize Qi[0]=0 all i
For k=1,2,...,N do {
for all i {Ti[k] = Di*(1+Qi[k-1]) }
R[k] = SUM {Ti[k]}
X[k] = k/(R[k]+Z)
for all i {Qi[k] = X[k]*Ti[k] }
}
NOTE: if you use this algorithm with Di that depend on N,
choose a particular n of interest, set Di=Di(n), and run
the algorithm until k=n. The final values R[n] and X[n] are
valid, but the values for k<n are not valid.
Iterative Mean Value Algorithm:
(A shortcut for calculating for just one N)
Initialize {Qi=0, Ri=0, Xi=0, all i}
repeat {
for all i {Ti = Di*(1+Qi*(N-1)/N) }
R = SUM{Ti}
oldX = X
X = N/(R+Z)
for all i {Qi = X*Ti }
} until {|oldX-X| < e}
(For example e = 0.001 is good to two significant digits)