Basic Queueing Theory Concepts

What is covered in this page

This page covers the basic queueing theory concepts: arrival process, service process, Poisson stream properties, M/M/1 queue and performance measures.

* The following content is derived or directly copied from class notes and these books *

Introduction to Queueing Theory

The performance of a computer system can be evaluated in a variety of ways. Queueing Theory supplies a simplest and cheapest way to measure system performance.

Basic Parameters

Arrival process : Jobs arrive intermittently from elsewhere at times that are not known in advance. This process continues indefinitely. The external population might be finite and infinite in size.

Service process : There may be just one or more than one processor serving jobs in the queue. If there are several, they are assumed to be identical. A service time distribution is a probability distribution function that describes the time required to serve a job. They are usually exponential .

Kendall notation: A/B/c/k/m/Z

A -- Arrival process. The "M" is the most common case that the arrivals follow a Poisson Distribution.
B -- Service processes. The "M" here means an exponential service distribution.
c -- Number of servers. There can be one or more servers in the system.
k -- Maximum queue size. By default, maximum queue size is infinite.
m -- Customer Population. By default, customer population is infinite.
Z -- Queue discipline. By default, queue discipline is First Come First Serve.

The Poisson Distribution

Bottom Line: In Poisson Distribution, each job arrives independently without knowing anything before and after it. We can not make any assumptions about next job base on the current job.

Poisson Postulates

The probability of more than one arrival at same time is negligible. Each arrival is independent to other arrivals and also independent of the time since the last arrival.

Poisson Streams Properties

A Poisson input stream(M) splits into n paths, each selected with probability Pi where Sum of Pi(1<=i<=N) equals 1, the result streams are each Poisson output stream(M x Pi).

N Poisson input streams(Mi) composite into a single output Poisson stream(M), where M = Sum Mi(1<=i<=n).

M/M/1 Queue

The M/M/1 Queue has following properties:

Jobs arrive according to a Poisson distribution with arrival rate A.
Service time is in a exponential distribution with mean service rate U.
There is only one server.

Steady-State Queue Length Probabilities

Let Sn= Probability of n things in the system at time t. Then Sn= limSn(t)[t->infinity] describes the probability of n jobs in the queue.

In Si state, there are two things can happen: A job(A)arrives, and the state is changed from Si to Si+1. Another case no more jobs arrive, the state is changed from Si to Si-1. Based on the assumption--there does not exist two or more jobs arriving at the same time, so the state can't jump from Si to Si+2.

In a Steady-State, the flow into a state equals the flow out of the state.

Flow out of S0 equal Flow into S0:
A x S0 = U x S1 -----> S1 = (A/U) x S0
Flow out of Sn equal Flow into Sn:
(A + U) x Sn = A x Sn-1 + U x Sn+1 -----> Sn+1= (1+A/U) x Sn - (A/U) x Sn-1

Combining the results in 1 and 2 above, we conclude this general formula:

Sn = (A/U)^n x S0

Sn = P^n x S0 where P = A/U

To figure out S0, we need to use the fact Sum Sn(0<=n)=1. By assuming that arrival rate is less than service rate(p<1), we get the queue length probability formulas:

S0 = 1- P and Sn = P^n x (1-P) , where P is also called "processor utilization".

Basic Measures

Mean queue length n = p / (1-P).
Mean waiting-line length (jobs not getting service) w = p^2 / (1-p).
Mean time in system t = n / A.
Mean waiting time before service tw = w / A.

The last two performance measures are also called Little's Laws .

Reference

Maekawa,M., Oldehoeft,A., and Oldehoeft,R. Operating Systems Advanced Concepts, The Benjamin/Cummings Publishing Company,Inc, pp. 375-382.

Send comment to chrisye@csgrad.cs.vt.edu

Go to Operating Systems Home page