M/G/1 Queue with Priority 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 = service time random variable for priority i jobs R i = residual service time random variable for priority i jobs λ i = arrival rate for priority i jobs (Poisson arrivals) ρ i λ i X i = utilization of the server by jobs of priority i σ i j 1 i ρ j = utilization of the server by jobs of priority 1 to i W i = random variable for the time a job of priority i spends waiting from arrival until service begins N i = random variable for the number of jobs in queue i (not counting jobs for which service has already begun) T i = random variable for the time a job of priority i spends in the system from arrival until the completion of service W i W i q W i a W i r where W i q = random variable for the delay seen by an arriving class i job due to other jobs in the system which have not yet begun service W i a = random variable for the delay seen by an arriving class i job due to jobs which arrive after it but before it begins service W i r = random variable for the delay seen by an arriving class i 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 . 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 1 i N j X j j 1 i λ j W j X j j 1 i ρ j W j 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 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 1 i ρ j W j W i r W i 1 σ i j 1 i 1 ρ j W j W i r (we define σ 0 to be 0). From , we get (for i 2 ) W i - 1 1 σ i - 2 j 1 i 1 ρ j W j W i - 1 r ⇒ j 1 i 1 ρ j W j W i - 1 1 σ i - 2 W i - 1 r Substituting the in gives 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 Now we need to consider the effects of what happens when a job first arrives.

No Preemption If an arrival never preempts a job in service, the time that a class i job expects to wait on the job in service must be the same as the time that a class i 1 job expects to wait: W i r W i - 1 r . Hence, W i W i - 1 1 σ i - 2 1 σ i for all i 2 . For 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 With this as a starting point, we can solve the recurrence (). 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 and in general W i W 1 r 1 σ i 1 σ i - 1 The expected time an arrival waits on a class i job in service at the time of arrival is the probability of a job seeing a class i job in service at its arrival times the expected residual service time for a class i job. Therefore, 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 M is the number of classes. Then W i j 1 M λ j X j 2 2 1 σ i 1 σ i - 1 T i j 1 M λ j X j 2 2 1 σ i 1 σ i - 1 X i

Preemption Let C i be the random variable for the time it takes a class i 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 i job, λ j C i class j jobs arrive, and hence 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 The probability that a class j job service is in progress (either a class j job is in service or is preempted) is just the fraction of time such a job is in the system, or λ j C j , since only one class j job can be in service or preempted at a time. Therefore, class j service in progress at an arrival λ j X j 1 σ j - 1 ρ j 1 σ j - 1 and 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 Substituting this into the previous expression for 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 Solving the recurrence: 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 and in general, 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 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 Finally, the response time for a class i job in a preemptive resume system is the waiting time plus the completion (not execution!) time: 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 1 i λ j X j 2 2 1 σ i 1 σ i - 1 T i j 1 i λ j X j 2 2 1 σ i 1 σ i - 1 X i 1 σ i - 1