More Queueing Theory
Carey Williamson
Department of Computer Science
University of Calgary
Motivating Quote for Queueing Models
“Good things come to those who wait”
- poet/writer Violet Fane, 1892
- song lyrics by Nayobe, 1984
- motto for Heinz Ketchup, USA, 1980’s
- slogan for Guinness stout, UK, 1990’s
2
M/M/1 Queue
M/M/1 queue is the most commonly used type of
queueing model
Used to model single processor systems or to model
individual devices in a computer system
Need to know only the mean arrival rate λ and the
mean service rate μ
State = number of jobs in the system
l l l l l l
0 1 2 … j-1 j j+1
m m m m
3
Results for M/M/1 Queue (cont’d)
Mean number of jobs in the system:
Mean number of jobs in the queue:
4
Results for M/M/1 Queue (cont’d)
Probability of n or more jobs in the system:
P (n k ) pn (1 ) n k
nk nk
Mean response time (using Little’s Law):
— Mean number in the system
= Arrival rate × Mean response time
— That is:
5
M/M/1/K – Single Server, Finite Queuing Space
K
K
6
Analytic Results
State-transition diagram:
l l l l
0 1 … K-1 K
m m m m
Solution p n p0 ,
n
where
1
1
p0 n 0 n 1
K 1 K 1
1 1
K 1
7
M/M/m - Multiple Servers
8
Analytic Results
State-transition diagram:
l l l l l l
0 1 … m-1 m m+1
m 2m (m-1)m mm m m
Solution n 1
n 1 p0 nm
pn p0 j
n!
j 0 j 1 1
p0 n
nm
m!m n m
9
M/M/ - Infinite Servers
Infinite number of servers - no queueing
10
Analytic Results
State-transition
diagram:
l l l l l l
0 1 … j-1 j j+1
m 2m (j-1)m jm (j+1) (j+2)
1
Solution pn p0 n
n!
1
n 1
p0 n 0 e
n!
Thus the number of customers in the system follows a Poisson
distribution with rate
11
M/G/1 Queue
Single-server
queue with Poisson arrivals, general
service time distribution, and unlimited capacity
Suppose service times have mean and variance
For , the steady-state results for are:
/ , p0 1
2 (1 2 2 ) 2 (1 2 2 )
E[n] , E[nq ]
2(1 ) 2(1 )
1 (1 / 2 2 ) (1 / 2 2 )
E[r ] , E[ w]
2(1 ) 2(1 )
12
M/G/1 Queue
— No simple expression for the steady-state probabilities
— Mean number of customers in queue, , can be rewritten
as:
If and are held constant, depends on the variability,, of the
service times.
13
Effect of Utilization and Service Variability
For
almost all queues, if lines are too long, they can be reduced by
decreasing server utilization () or by decreasing the service time
variability ()
Coefficient of Variation: a measure of the variability of a distribution
— The larger is, the more variable is the distribution relative to its
expected value.
Pollaczek-Khinchin (PK) mean value formula:
2 (1 (CV ) 2 )
E[n]
2(1 ) 14
Effect of Utilization and Service Variability
Consider for M/G/1 queue:
2 (1 2 2 )
E [ nq ]
2(1 )
Mean no. of customers in queue
2 1 (CV ) 2
1 2
Same as for Adjusts the M/M/1
M/M/1 formula to account for
queue a non-exponential
service time
distribution Traffic Intensity ()
15