Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 38 Ā· Finite Capacity and Priorities

Priority Queues: Preemptive and Non-Preemptive

Compute waiting times for each class in an M/G/1 priority queue, compare non-preemptive and preemptive-resume rules, and see the conservation law in action.

An emergency room does not treat patients in arrival order. A network router sends voice packets before file downloads. When customers differ in urgency, we give them priority classes. The key questions are: how much does the high class gain, how much does the low class lose, and is the total pain reduced or only moved around?

We study a single server with K classes, numbered 1 (highest priority) to K (lowest). Class i arrives as a Poisson stream with rate λ_i and has service time S_i with mean E[S_i] and second moment E[S_i²] (any distribution). Define ρ_i = λ_i E[S_i] and the cumulative load σ_k = ρ_1 + ... + ρ_k. We need σ_K < 1 for stability.

Two rules

  • Non-preemptive: a customer in service is never interrupted. A newly arrived high-priority customer waits for the current one to finish, then jumps ahead of lower classes.
  • Preemptive-resume: a high-priority arrival interrupts a lower-priority customer in service, who later resumes where they left off.

Non-preemptive waiting times (Cobham's formula)

Let W0 = Σ_i λ_i E[S_i²] / 2, the mean residual work that an arriving customer finds in service. The mean waiting time in the queue for class k is:

Text
Wq_k = W0 / ((1 - σ_{k-1}) (1 - σ_k)),     σ_0 = 0

The class-k customer waits for the residual service (W0), but is also delayed by higher-priority customers already waiting or arriving during the wait; this is what the two factors in the denominator capture.

Python Non-preemptive priority waiting times

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The high class waits much less than the FCFS baseline; the low class waits more.

The conservation law

Priorities cannot make everyone better off. For the non-preemptive M/G/1 case the load-weighted waits satisfy:

Text
Σ ρ_k Wq_k = ρ · W0 / (1 - ρ),     ρ = σ_K

The right side equals what the same weighted sum would be under FCFS. So priorities redistribute waiting; they do not create it or remove it.

Python Verify the conservation law

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The two numbers match to rounding.

Preemptive-resume

Under preemptive-resume, lower classes are invisible to class k: it behaves as if it were alone with classes 1..k. The mean time in system (response time) for class k is:

Text
T_k = E[S_k] / (1 - σ_{k-1})  +  ( Ī£_{i≤k} Ī»_i E[S_i²] / 2 ) / ( (1 - σ_{k-1})(1 - σ_k) )

The first term is the service time stretched by interruptions from higher classes; the second is the delay caused by the work present from classes 1..k. Class 1 sees a plain M/G/1 queue by itself. Class K, the lowest, can suffer badly when σ_{K-1} is close to 1.

Python Preemptive-resume response times versus non-preemptive

Press Run (or Ctrl + Enter) to see the result here.

Program input Ā· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Preemption helps the top class most, because it never waits for a lower-class customer to finish.

Preemption only makes sense when interrupting is cheap. If restarting work wastes effort (preemptive-repeat), or switching costs time, the formulas above no longer apply.

Check your understanding

Quick check Ā· 4 questions

of 4 answered You scored / 4 Ā· perfect!

  1. 1. In a non-preemptive priority queue, the highest class (k = 1) waits Wq_1 equal to

    With σ_0 = 0 and σ_1 = ρ_1 the formula gives W0 / (1 - ρ_1). Class 1 still waits for the customer currently in service.
  2. 2. What does the conservation law say?

    For work-conserving rules, the weighted sum of mean waits is fixed; priorities move waiting between classes.
  3. 3. Under preemptive-resume, how does class 1 see the system?

    Lower classes can always be interrupted, so class 1 is unaffected by them.
  4. 4. Which condition is needed for all classes to have finite waits?

    The lowest class sees all the work, so total utilization must stay below 1.

Summary

  • Classes are ordered; σ_k is the cumulative load of classes 1..k.
  • Non-preemptive: Wq_k = W0 / ((1 - σ_{k-1})(1 - σ_k)) with W0 = Ī£ Ī»_i E[S_i²]/2.
  • Preemptive-resume: class k ignores lower classes; use the T_k formula.
  • The conservation law shows priorities redistribute waiting rather than remove it.

Next: The M/G/1 Queue and the Pollaczek-Khinchine Formula