11.4 The MG1 Queue


11.4 The M/G/1 Queue

A well-studied special case of the G/G/1 queue occurs when the interarrival times are exponentially distributed but the service time distribution is any arbitrary (i.e., general) distribution. This queue is called an M/G/1 queue. The basic result for an M/G/1 queue, known as the Pollaczek-Khintchine (P-K) formula [2] for the average waiting time W, is

Equation 11.4.14

graphics/11equ414.gif


where graphics/296fig01.gif is the square of the coefficient of variation of the service time distribution. [Note: if Cs = 1, the system is an M/M/1 queue.]

The other equations for M/G/1 follow directly from Eqs. (11.2.1)-(11.2.3):

Equation 11.4.15

graphics/11equ415.gif


Equation 11.4.16

graphics/11equ416.gif


Equation 11.4.17

graphics/11equ417.gif


Example 11.3.

Suppose that e-mail messages arrive at an e-mail server from a Poisson process at a rate of 1.2 messages per second. Also suppose that 30% of the messages are processed in 0.1 sec, 50% in 0.3 sec, and 20% in 2 sec. What is the average time E[S] it takes to process a message? What is the average time W a message waits in the queue to be processed? What is the average response time T of an e-mail message? What is the average number of messages Nw waiting in the queue? What is the average number of messages N in the e-mail server?

The average time to process a message is

graphics/297equ01.gif


The utilization of the e-mail server is r = l x E[S] = 1.2 messages/sec x 0.58 seconds/message = 0.696. The coefficient of variation of the processing time, Cs, is the ratio between the standard deviation, ss, and the average processing time E[S]. The standard deviation is the square root of the variance graphics/297fig03.gif, which is obtained as graphics/297fig01.gif, where E[S2] is the second moment of the processing time. In this case,

graphics/297equ02.gif


Thus, the standard deviation ss is

graphics/297equ03.gif


The coefficient of variation Cs is then Cs = ss/E[S] = 0.715/0.58 = 1.233. From Eqs. (11.4.14)-(11.4.17):

graphics/297equ04.gif


Example 11.4.

What is the ratio between the average waiting time of an M/G/1 queue with exponentially distributed service times and the waiting time of an M/G/1 queue with constant service times?

The coefficient of variation Cs of a server with an exponentially distributed service time is 1. When the service times are constant, the variance, and therefore the coefficient of variation, is zero. Thus,

graphics/298equ01.gif


Thus, the time spent in the waiting line at an exponential server is on average twice the time spent in the waiting line of a constant speed server.

Figure 11.2 shows various curves of the average response time versus utilization for an M/G/1 queue with E[S] = 1 and for four values of Cs: 0, 0.5, 1, and 2. When Cs = 0, the M/G/1 queue is also referred to as an M/D/1 queue because service times are deterministic. When Cs = 1 service times are exponentially distributed and the resulting queue is an M/M/1 queue. As illustrated in Fig. 11.2 and from Eq. (11.4.15), the average response time increases as a function of the square of the coefficient of variation of the service time. This result indicates that performance degrades as the variability in the server increases. Thus, reducing the uncertainty (i.e., the standard deviation) of the service times placed on devices improves performance.

Figure 11.2. Response time of an M/G/1 queue for various values of Cs.

graphics/11fig02.gif



Performance by Design. Computer Capacity Planning by Example
Performance by Design: Computer Capacity Planning By Example
ISBN: 0130906735
EAN: 2147483647
Year: 2003
Pages: 166

Similar book on Amazon

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net