14 2. SINGLE QUEUES

n D T; (2.1)

where n is the average number of jobs at the queue (waiting and in service), and T is the

average time at the queue.

(b) If we view the waiting space alone as the system, then

L D W ; (2.2)

where L is the average number of jobs waiting for service, and W is the average waiting

time.

(c) If we view the single server alone as the system, then the average number of jobs at the

server is 1 Prob.1 job at the server/ C 0 Prob.no job at the server/ D

1

, so

D

where D Prob.1 job at the server/: (2.3)

A server is busy if and only if it is serving a job, so is a measure of server utilization.

Since T D W C

1

(waiting time plus service time), we have

n D T D

W C

1

D L C : (2.4)

As is a probability, D

requires that < , i.e., arrival rate is slower than service rate.

is is intuitive; if > , then jobs arrive faster than they can be served, the queue will grow

indeﬁnitely, there is no steady state, and averages have no meaning.

What if D ? e answer depends on whether the inter-arrival and service times are

deterministic. Such details are speciﬁed by the notation we introduce next.

2.2 QUEUE SPECIFICATION

In the Kendall Notation A=S=K=B=N=d ,

A is the arrival process (e.g., M for memoryless, i.e., Poisson arrivals);

S is the service time distribution (e.g., D for deterministic, G for general);

K is the number of servers (possibly inﬁnite);

B is the buﬀer capacity (including jobs in service; by default, B is inﬁnity);

N is the job population size (by default, N is inﬁnity);

Get *Analytical Performance Modeling for Computer Systems, 2nd Edition* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.