Another useful extension to the classical M/G/1 queue is the
priority M/G/1 queue. The workload for the queue consists of two
or more classes of jobs. Each job belongs to a single class.
Jobs receive service in an order that is based on a predetermined
priority ranking among the classes of jobs. Each class of job may
have its own, distinct arrival rate (with exponentially
distributed interarrival times) and service time distribution.
The objective is to determine the average waiting time for jobs
of each class and the average number of jobs of each class in
the queue. These will depend on whether the queueing discipline
is preemptive or non-preemptive. A
non-preemptive queueing discipline requires a job that begins
service to complete its service without interruption. In a
preemptive priority queue, if a job arriving at the queue finds
a job of lower priority in service, the arriving job preempts
the job being served and begins service immediately. A
preempted job will resume service, at the point at which its
service was suspended, as soon as there are no higher priority
jobs remaining in the queue. We call a preemptive scheduling
policy with this latter property preemptive resume.
Notation:
-
X
i
X
i
= service time random variable for priority
ii jobs
-
R
i
R
i
= residual service time random variable for
priority ii jobs
-
λ
i
λ
i
= arrival rate for priority ii
jobs (Poisson arrivals)
-
ρ
i
=
λ
i
X
i
¯
ρ
i
λ
i
X
i
= utilization of the server by jobs of priority
ii
-
σ
i
=∑j=1i
ρ
j
σ
i
j
1
i
ρ
j
= utilization of the server by jobs of priority 1 to
ii
-
W
i
W
i
= random variable for the time a job of priority
ii spends waiting from arrival
until service begins
-
N
i
N
i
= random variable for the number of jobs in queue
ii (not counting jobs for which
service has already begun)
-
T
i
T
i
= random variable for the time a job of priority
ii spends in the system from
arrival until the completion of service
W
i
=
W
i
q
+
W
i
a
+
W
i
r
W
i
W
i
q
W
i
a
W
i
r
where
-
W
i
q
W
i
q
= random variable for the delay seen by an arriving class
ii job due to other jobs in
the system which have not yet begun service
-
W
i
a
W
i
a
= random variable for the delay seen by an arriving class
ii job due to jobs which
arrive after it but before it begins service
-
W
i
r
W
i
r
= random variable for the delay seen by an arriving class
ii job due to jobs whose
service is in progress (either actually in service or
preempted) at the time of the arrival
We want to know
W
i
¯=
W
i
q
¯+
W
i
a
¯+
W
i
r
¯
W
i
W
i
q
W
i
a
W
i
r
.
The first two terms depend only on the priority of the arriving
job and not on whether queueing is preemptive or
non-preemptive.
W
i
q
¯=∑j=1i
N
j
¯
X
j
¯=∑j=1i
λ
j
W
j
¯
X
j
¯=∑j=1i
ρ
j
W
j
¯
W
i
q
j
1
i
N
j
X
j
j
1
i
λ
j
W
j
X
j
j
1
i
ρ
j
W
j
W
i
a
¯=∑j=1i−1
λ
j
W
i
¯
X
j
¯=∑j=1i−1
ρ
j
W
i
¯
W
i
a
j
1
i
1
λ
j
W
i
X
j
j
1
i
1
ρ
j
W
i
Substituting these two expressions gives
W
i
¯=∑j=1i
ρ
j
W
j
¯+∑j=1i−1
ρ
j
W
i
¯+
W
i
r
¯
W
i
j
1
i
ρ
j
W
j
j
1
i
1
ρ
j
W
i
W
i
r
which we can manipulate into two slightly different forms:
W
i
¯1−
σ
i
-
1
=∑j=1i
ρ
j
W
j
¯+
W
i
r
¯
W
i
1
σ
i
-
1
j
1
i
ρ
j
W
j
W
i
r
(1)
W
i
¯1−
σ
i
=∑j=1i−1
ρ
j
W
j
¯+
W
i
r
¯
W
i
1
σ
i
j
1
i
1
ρ
j
W
j
W
i
r
(2)
(we define
σ
0
σ
0
to be 0).
From Equation 1, we get (for
i≥2
i
2
)
W
i
-
1
¯1−
σ
i
-
2
=∑j=1i−1
ρ
j
W
j
¯+
W
i
-
1
r
¯
W
i
-
1
1
σ
i
-
2
j
1
i
1
ρ
j
W
j
W
i
-
1
r
⇒
∑j=1i−1
ρ
j
W
j
¯=
W
i
-
1
¯1−
σ
i
-
2
−
W
i
-
1
r
¯
⇒
j
1
i
1
ρ
j
W
j
W
i
-
1
1
σ
i
-
2
W
i
-
1
r
Substituting the in Equation 2 gives
W
i
¯1−
σ
i
=
W
i
-
1
¯1−
σ
i
-
2
−
W
i
-
1
r
¯+
W
i
r
¯
W
i
1
σ
i
W
i
-
1
1
σ
i
-
2
W
i
-
1
r
W
i
r
W
i
¯=
W
i
-
1
¯1−
σ
i
-
2
+
W
i
r
¯−
W
i
-
1
r
¯1−
σ
i
W
i
W
i
-
1
1
σ
i
-
2
W
i
r
W
i
-
1
r
1
σ
i
Now we need to consider the effects of what happens when a job
first arrives.
If an arrival never preempts a job in service, the time that
a class ii job expects to wait
on the job in service must be the same as the time that a
class
i−1
i
1
job expects to wait:
W
i
r
¯=
W
i
-
1
r
¯
W
i
r
W
i
-
1
r
. Hence,
W
i
¯=
W
i
-
1
¯1−
σ
i
-
2
1−
σ
i
W
i
W
i
-
1
1
σ
i
-
2
1
σ
i
(3)
for all
i≥2
i
2
. For
i=1
i
1
,
W
1
¯=
W
1
r
¯+
N
1
¯
X
1
¯=
W
1
r
¯+
λ
1
W
1
¯
X
1
¯=
W
1
r
¯+
ρ
1
X
1
¯=
W
1
r
¯1−
ρ
1
W
1
W
1
r
N
1
X
1
W
1
r
λ
1
W
1
X
1
W
1
r
ρ
1
X
1
W
1
r
1
ρ
1
With this as a starting point, we can solve the recurrence
(
Equation 3).
W
2
¯=
W
1
¯1−
σ
0
1−
σ
2
=
W
1
r
¯1−
σ
2
1−
σ
1
W
2
W
1
1
σ
0
1
σ
2
W
1
r
1
σ
2
1
σ
1
W
3
¯=
W
1
¯1−
σ
1
1−
σ
3
1−
σ
2
1−
σ
1
=
W
1
r
¯1−
σ
3
1−
σ
2
W
3
W
1
1
σ
1
1
σ
3
1
σ
2
1
σ
1
W
1
r
1
σ
3
1
σ
2
and in general
W
i
¯=
W
1
r
¯1−
σ
i
1−
σ
i
-
1
W
i
W
1
r
1
σ
i
1
σ
i
-
1
The expected time an arrival waits on a class
ii job in service at the time
of arrival is the probability of a job seeing a class
ii job in service at its
arrival times the expected residual service time for a class
ii job. Therefore,
W
1
r
¯=∑i=1M
ρ
i
R
i
¯=∑i=1M
λ
i
X
i
¯
X
i
2¯2
X
i
¯=∑i=1M
λ
i
X
i
2¯2
W
1
r
i
1
M
ρ
i
R
i
i
1
M
λ
i
X
i
X
i
2
2
X
i
i
1
M
λ
i
X
i
2
2
where
MM is the number of
classes. Then
W
i
¯=∑j=1M
λ
j
X
j
2¯21−
σ
i
1−
σ
i
-
1
W
i
j
1
M
λ
j
X
j
2
2
1
σ
i
1
σ
i
-
1
(4)
T
i
¯=∑j=1M
λ
j
X
j
2¯21−
σ
i
1−
σ
i
-
1
+
X
i
¯
T
i
j
1
M
λ
j
X
j
2
2
1
σ
i
1
σ
i
-
1
X
i
(5)
Let
C
i
C
i
be the random variable for the time it takes a class
ii job to complete service
(that is, the time between starting service and finishing,
including the time that the job is preempted). Then during
an average service completion interval for a class
ii job,
λ
j
C
i
¯
λ
j
C
i
class jj jobs arrive,
and hence
C
i
¯=
X
i
¯+∑j=1i−1
λ
j
C
i
¯
X
j
¯=
X
i
¯+
σ
j
-
1
C
i
¯
C
i
X
i
j
1
i
1
λ
j
C
i
X
j
X
i
σ
j
-
1
C
i
⇒
C
i
¯=
X
i
¯1−
σ
i
-
1
⇒
C
i
X
i
1
σ
i
-
1
The probability that a class jj
job service is in progress (either a class
jj job is in service or is
preempted) is just the fraction of time such a job is in the
system, or
λ
j
C
j
¯
λ
j
C
j
, since only one class
jj job can be in service or
preempted at a time. Therefore,
Prclass j service in progress at an arrival=
λ
j
X
j
¯1−
σ
j
-
1
=
ρ
j
1−
σ
j
-
1
class j service in progress at an arrival
λ
j
X
j
1
σ
j
-
1
ρ
j
1
σ
j
-
1
and
W
i
r
¯=∑j=1i
ρ
j
R
j
¯1−
σ
j
-
1
W
i
r
j
1
i
ρ
j
R
j
1
σ
j
-
1
From this we see that
W
i
r
¯−
W
i
-
1
r
¯=
ρ
i
R
i
¯1−
σ
i
-
1
W
i
r
W
i
-
1
r
ρ
i
R
i
1
σ
i
-
1
Substituting this into the previous expression for
W
i
¯
W
i
leads to the following simple recurrence equation:
W
i
¯=1−
σ
i
-
2
W
i
-
1
¯+
ρ
i
R
i
¯1−
σ
i
-
1
1−
σ
i
=1−
σ
i
-
1
1−
σ
i
-
2
W
i
-
1
¯+
ρ
i
R
i
¯1−
σ
i
1−
σ
i
-
1
W
i
1
σ
i
-
2
W
i
-
1
ρ
i
R
i
1
σ
i
-
1
1
σ
i
1
σ
i
-
1
1
σ
i
-
2
W
i
-
1
ρ
i
R
i
1
σ
i
1
σ
i
-
1
Solving the recurrence:
W
1
¯=
ρ
1
R
1
¯+
λ
1
W
1
¯
X
1
¯=
ρ
1
R
1
¯1−
σ
1
W
1
ρ
1
R
1
λ
1
W
1
X
1
ρ
1
R
1
1
σ
1
W
2
¯=1−
σ
1
1−
σ
0
W
1
¯+
ρ
2
R
2
¯1−
σ
2
1−
σ
1
=1−
σ
1
1
ρ
1
R
1
¯1−
σ
1
+
ρ
2
R
2
¯1−
σ
2
1−
σ
1
=
ρ
1
R
1
¯+
ρ
2
R
2
¯1−
σ
2
1−
σ
1
W
2
1
σ
1
1
σ
0
W
1
ρ
2
R
2
1
σ
2
1
σ
1
1
σ
1
1
ρ
1
R
1
1
σ
1
ρ
2
R
2
1
σ
2
1
σ
1
ρ
1
R
1
ρ
2
R
2
1
σ
2
1
σ
1
and in general,
W
i
¯=∑j=1i
ρ
j
R
j
¯1−
σ
i
1−
σ
i
-
1
W
i
j
1
i
ρ
j
R
j
1
σ
i
1
σ
i
-
1
which can be verified by substitution into the recurrence
equation.
W
i
¯=1−
σ
i
-
1
1−
σ
i
-
2
W
i
-
1
¯+
ρ
i
R
i
¯1−
σ
i
1−
σ
i
-
1
=1−
σ
i
-
1
1−
σ
i
-
2
∑j=1i
ρ
j
R
j
¯1−
σ
i
-
1
1−
σ
i
-
2
+
ρ
i
R
i
¯1−
σ
i
1−
σ
i
-
1
=∑j=1i
ρ
j
R
j
¯+
ρ
i
R
i
¯1−
σ
i
1−
σ
i
-
1
W
i
1
σ
i
-
1
1
σ
i
-
2
W
i
-
1
ρ
i
R
i
1
σ
i
1
σ
i
-
1
1
σ
i
-
1
1
σ
i
-
2
j
1
i
ρ
j
R
j
1
σ
i
-
1
1
σ
i
-
2
ρ
i
R
i
1
σ
i
1
σ
i
-
1
j
1
i
ρ
j
R
j
ρ
i
R
i
1
σ
i
1
σ
i
-
1
(6)
Finally, the response time for a class
ii job in a preemptive resume
system is the waiting time plus the completion (not
execution!) time:
T
i
¯=∑j=1i
ρ
j
R
j
¯1−
σ
i
1−
σ
i
-
1
+
X
i
¯1−
σ
i
-
1
T
i
j
1
i
ρ
j
R
j
1
σ
i
1
σ
i
-
1
X
i
1
σ
i
-
1
We can rewrite the equations for waiting time and response
time in terms of the first and second principal moments of
the service time distribution:
W
i
¯=∑j=1i
λ
j
X
j
2¯21−
σ
i
1−
σ
i
-
1
W
i
j
1
i
λ
j
X
j
2
2
1
σ
i
1
σ
i
-
1
(7)
T
i
¯=∑j=1i
λ
j
X
j
2¯21−
σ
i
1−
σ
i
-
1
+
X
i
¯1−
σ
i
-
1
T
i
j
1
i
λ
j
X
j
2
2
1
σ
i
1
σ
i
-
1
X
i
1
σ
i
-
1
(8)
