Previous Table of Contents Next


31.3 M/M/m QUEUE

The M/M/m queue can be used to model multiprocessor systems or devices that have several identical servers and all jobs waiting for these servers are kept in one queue. It is assumed that there are m servers each with a service rate of µ jobs per unit time. The arrival rate is λ jobs per unit time. If any of the m servers are idle, the arriving job is serviced immediately. If all m servers are busy, the arriving jobs wait in a queue. The state of the system is represented by the number of jobs n in the system. The state transition diagram is shown in Figure 31.4. It is easy to see that the number of jobs in the system is a birth-death process with the following correspondence:

Theorem 31.1 gives us the following expression for the probability of n jobs in the system:

In terms of the traffic intensity ρ = ρ/, we have

Using this expression for pn, other performance parameters for M/M/m queues can be easily derived. A summary of the results is presented in Box 31.2. Derivations of some of the results are given here. Readers who are not interested in the derivation may sldp to the example following it.

Derivation 31.1 The probability of zero jobs in the system is computed by the relationship


FIGURE 31.4  State transition diagram for an M/M/m queue.

Box 31.2 M/M/m Queue

1.  Parameters:
λ = arrival rate in jobs per unit time
µ = service rate in jobs per unit time
m = number of servers
2.  Traffic intensity: ρ = λ/()
3.  The system is stable if the traffic intensity ρ is less than 1.
4.  Probability of zero jobs in the system:

5.  Probability of n jobs in the system:

6.  Probability of queueing:


In the remaining formulas below we will use as defined here.
7.  Mean number of jobs in the system: E[n] = mρ + ρ/(1 – ρ
8.  Variance of number of jobs in the system:

9.  Mean number of jobs in the queue: E[nq] = ρ(1 – ρ)
10.  Variance of number of jobs in the queue:
Var[nq] = ρ(1 + ρ – ρ)/(1 – ρ)2
11.  Average utilization of each server: U = λ/() = ρ
12.  Cumulative distribution function of response time:

13.  Mean response time:

14.  Variance of the response time:

15.  Cumulative distribution function of waiting time:
F(w) = 1 – e–mµ(1 – ρ)w
16.  Mean waiting time: E[w] = E[nq]/λ = /[(1 – ρ)]
17.  Variance of the waiting time: Var[w] = (2 – )/[m2µ2(1 – ρ)2]
18.  q-Percentile of the waiting time: max
19.  90-Percentile of the waiting time:
Once again, in these formulas is the probability of m or more jobs in the system: = [(mρ)m/{m!(1 – ρ}]ρ0. For m = 1, is equal to ρ and all of the formulas become identical to those for M/M/1 queues.
This gives

or


The probability that an arriving job has to wait in the queue is denoted by and given by


This is known as Erlang’s C formula. This probability is an important performance parameter for M/M/m queues. It is convenient to compute before proceeding to compute other parameters since appears frequently in other expressions. Notice that for the single-server case (m = 1), the probability of queueing , or equivalently, the probability of all servers being busy, is equal to ρ.
Using the expression for pn, the mean number of jobs in the queue E[nq] can be computed easily:


The expected number of jobs in service is


The expected number of jobs in the system is


The variance of n and nq can similarly be shown as


If we observe the system for a long time, for instance, T seconds, the total number of jobs arriving and getting service will be λT. The total busy time of m servers to service these jobs will be λT/µ, and the utilization of each server will be


The mean response time using Little’s law is


Similarly, the mean waiting time is


The probability distribution function of the response time can be shown as


Notice that the response time r is not exponentially distributed unless m = 1. In general, the coefficient of variation, that is, the ratio of the standard deviation to the mean, of r is less than 1.
Similarly, the probability distribution function of the waiting time is

F(w) = 1 – e–mµ(1–ρ)w


Since w has a truncated exponential distribution function, the q-percentile can be computed as follows:


If the probability of queueing is less than 1 – q/100, the second term in the equation can be negative. The correct answer in those cases is zero.
Example 31.2 Students arrive at the university computer center in a Poisson manner at an average rate of 10 per hour. Each student spends an average of 20 minutes at the terminal, and the time can be assumed to be exponentially distributed. Tbe center currently has five terminals. Some students have been complaining that waiting times are too long. Let us analyze the center usage using a queueing model.

The center can be modeled as an M/M/5 queueing system with an arrival rate of per minute and a service rate of per minute.

Substituting these into the expressions previously used in this section, we get

The probability of all terminals being idle is

The probability of all terminals being busy is

Average terminal utilization is

ρ = 0.67

Average number of students in the center is

The average number of students waiting in the queue is

The average number of students using the terminals is

The mean and variance of the time spent in the center are

Thus, each student spends an average of 24 minutes in the center. Of these, 20 minutes are spent working on the terminal and 4 minutes are spent waiting in the queue. We can further verify this using the formula for the mean waiting time:

The 90-percentile of the waiting time is

Thus, 10% of the students have to wait more than 14 minutes.

Queueing models can be used not only to study the current behavior but also to predict what would happen if we made changes to the system. The following examples illustrate this.


Previous Table of Contents Next

Copyright © John Wiley & Sons, Inc.