13
C H A P T E R 2
Single Queues
A typical computer system has queues everywhere. A queue imposes order on a set of tasks, mak-
ing some wait for others. Such waiting is usually wasted time, so modeling system performance
requires an understanding of queue behavior. is chapter introduces some elementary queueing
theory.
2.1 APPLYING LITTLE’S LAW TO A 1-SERVER QUEUE
Consider a queue with one server and buffer space for holding jobs that are in service or waiting,
as illustrated in Fig. 2.1. (Unless otherwise stated, a server” refers to the server of a queue, rather
than the server web server, IO server, etc. in some client-server architecture.)
server (rate µ)
λ
buffer capacity
waiting space
Figure 2.1: A simple queue with a single server. Queue length refers to all jobs at the queue, i.e.,
jobs waiting and in service. System time refers to total time spent at the queue, i.e., waiting time plus
service time.
Let and be the arrival and service rates, i.e., the average inter-arrival time is 1= and
the average service time is 1=. Without specifying other details like the probability distributions
for inter-arrival and service times and the queueing discipline, we can already apply Little’s Law
to derive some relationships (see Fig. 2.2).
system=waiting space + server
system=waiting space
system=server
(a) (b) (c)
Figure 2.2: Little’s Law is applicable to all three interpretations of system.”
(a) If we view the waiting space and server as the system, then Little’s Law gives

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.