Skip to content Skip to navigation

OpenStax-CNX

You are here: Home » Content » The M/G/1 Queue

Navigation

Recently Viewed

This feature requires Javascript to be enabled.
 

The M/G/1 Queue

Module by: Bart Sinclair. E-mail the author

Summary: (Blank Abstract)

The M/G/1 Queue

The M/G/1 queue has exponentially distributed interarrival times and an arbitrary distribution for service times. The increase in generality compared to the M/M/1 queue comes with a price: the M/G/1 queue does not have a general, closed form distribution for the number of jobs in the queue in steady state. It does, however, admit a general solution for the average number of jobs in the queue, and application of Little's Theorem provides the corresponding result for the average time spent in the queue. Collectively, these results are known as the Pollaczek-Khinchin mean value formulae.

The following derivation of the Pollaczek-Khinchin mean value formulae for the M/G/1 queue assumes FCFS scheduling, to simplify the analysis. However, the formulae are valid for any scheduling discipline in which

  1. the server is busy if the queue is non-empty,
  2. no job departs the queue before completing service, and
  3. the order of service is not dependent on knowledge about job service times.

We begin by recalling or defining the following notation. Job ii refers to the iith job to arrive at the queue. As usual, we assume that a steady state solution exists; i.e., the arrival rate is less than the service rate.

  • X i X i - r.v. for service time of job ii
  • X-=E X i X X i
  • X2-=E X i 2 X 2 X i 2
  • W i W i - r.v. for time job ii spends waiting in queue before beginning service
  • W i -=E W i W i W i
  • W=limit  i W i - W i W i
  • N i N i - r.v. for number of jobs in the queue when job ii arrives
  • N i -=E N i N i N i
  • N Q =limit  i N i - N Q i N i
  • R i R i - r.v. for residual service time seen by job ii (the amount of time job ii must wait until a job in service when ii arrives is completed)
  • R i -=E R i R i R i
  • R=limit  i R i - R i R i
  • λλ - job arrival rate
  • ρ=λX- ρ λ X - server utilization
When a job arrives at the queue, it must wait for the job in service (if there is one) to complete. Since we are assuming FCFS scheduling, it must also wait for all of the jobs which arrived before it but which have not begun service to complete. W i = R i +j=i N i i1 X j W i R i j i N i i 1 X j R i R i will be 0 if the job arrives when the queue is empty. Taking expectations, W i -= R i -+Ej=i N i i1E X j | N i = R i -+X- N i - W i R i j i N i i 1 N i X j R i X N i This last step is valid because the number of jobs that are in the queue at an arrival instant must be independent of the service times of jobs that have not been serviced yet. We can take lim i lim i of both sides of this equation to obtain W=R+X- N Q W R X N Q From Little's Theorem, N Q =λW N Q λ W Substituting this into the expression for WW gives W=R+X-λW=R+ρW=R1ρ W R X λ W R ρ W R 1 ρ To determine RR, we could make use of a well-known result which relates the principal moments R i n-=E R i n R i n R i n of the residual time r.v. to the moments X i n-=E X i n X i n X i n of the service time r.v.: R i n-= X i n+1-(n+1) X i - R i n X i n 1 n 1 X i

However, we can also find RR directly by looking at a plot of the residual service time r.v. as a function of tt. Define the following functions:

  • rτ r τ - the residual service time of the customer in service at time ττ (this will be 0 if no customer is in service)
  • Mt M t - the number of service completions in the interval 0 t 0 t ; we are interested only in tt such that rt=0 r t 0 .
The figure below illustrates how the residual service time changes over time. When a job ii begins service, its residual service time starts at X i X i and falls linearly (with slope -1) to 0.

Figure 1
Figure 1 (MG1_queue1.png)

The time average of rτ r τ in the interval 0 t 0 t is given by

1t0trτdτ=1ti=1Mt X i 22=12Mtti=1Mt X i 2Mt 1 t τ 0 t r τ 1 t i 1 M t X i 2 2 1 2 M t t i 1 M t X i 2 M t
(1)
limit  t 1t0trτdτ=12limit  t Mttlimit  t i=1Mt X i 2Mt t 1 t τ 0 t r τ 1 2 t M t t t i 1 M t X i 2 M t
(2)
These are time averages; however, the ensemble averages (means of the steady state distributions) and time averages are equal, giving us R=λX2-2 R λ X 2 2 Consequently, W=λX2-2×(1ρ) W λ X 2 2 1 ρ

The M/G/1 Queue with Vacations

One important variation on the M/G/1 queue is to allow the server to take vacations - i.e., to be idle when there is work to be done. The server goes idle at the end of each busy period (when the queue becomes empty), and remains idle for some random amount of time. If the queue is still empty at the end of a vacation time, the server immediately starts another vacation; otherwise, the server begins a job service time.

The analysis proceeds as for the M/G/1 queue, up to the point at which we find an expression for the average waiting time: W=R1ρ W R 1 ρ except that we must define RR to be the mean residual service or vacation time, since a job might arrive during another job's service time or during a server vacation, and it will be delayed until the completion of either. Define

  • V i V i - r.v. for the length of vacation ii
  • V i -=E V i V i V i
  • V=limit  i V i - V i V i
  • Lt L t - the number of vacations completed in the interval 0 t 0 t
Assume that vacation times are independent and identically distributed, and are independent of job interarrival and service times.

We will be interested in looking at the system only at some time tt corresponding to the completion of a service or a vacation. In the figure below, darker triangles are service times and lighter ones are vacations.

Figure 2
Figure 2 (MG1_queue2.png)

Proceeding as before:

1t0trτdτ=1ti=1Mt X i 22+1ti=1Lt V i 22=12Mtti=1Mt X i 2Mt+12Ltti=1Lt V i 2Lt 1 t τ 0 t r τ 1 t i 1 M t X i 2 2 1 t i 1 L t V i 2 2 1 2 M t t i 1 M t X i 2 M t 1 2 L t t i 1 L t V i 2 L t
(3)
Since t(1ρ)Lt=V- t 1 ρ L t V we can take the limit as tt approaches of the average residual service time and use the equality of time and ensemble averages to obtain R=λX2-2+(1ρ)V2-2V- R λ X 2 2 1 ρ V 2 2 V Substituting this into the expression for the average waiting time gives us W=λX2-2×(1ρ)+V2-2V- W λ X 2 2 1 ρ V 2 2 V

Content actions

Download module as:

Add module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks