Preemptive priority queue

Consider an M/M/$k$ queue with $m$ priority classes, where class $i$ jobs have preemptive priority over class $j$ jobs for $1\leq i<j\leq m$ (i.e. class 1 has the highest priority). The behavior of class 1 jobs is not affected by the jobs of other classes. However, the behavior of class 2 jobs depends on the number of class 1 jobs in the system. Specifically, when there are $n$ jobs of class 1, $\max\{k-n,0\}$ servers are available for class 2 jobs. Likewise, the behavior of class $i$ jobs depends on the total number of higher priority (classes $\leq i-1$) jobs for $2\leq i\leq m$ (when there are $n$ higher priority jobs, $\max\{k-n,0\}$ servers are available for class $i$ jobs). We will study the performance of the preemptive priority queue in Chapter 4. Below, we will model the preemptive priority queue as an RFB process.

Figure 3.15: Ideas in the RFB process. (a) Relationships among $m$ processes in the extended RFB process. (b)-(c) Two equivalent QBD processes.

(a) Extended RFB process.

Two equivalent QBD processes

(b)

(c)

As we have seen in Section 3.1, when $m=2$, the number of jobs in a priority M/M/$k$ queue can be modeled as an FB process where the background process, $B$, captures the number of class 1 jobs (high priority jobs), and the foreground process, $F$, captures the number of class 2 jobs (low priority jobs). Here, the level $\ell$ of $B$ corresponds to the state with $\ell$ high priority jobs. Note that the number of servers available for low priority jobs (and hence the behavior of $F$) is determined by the number of high priority jobs (equivalently, the level of $B$).

When $m>2$, the number of jobs in a priority M/M/$k$ queue can be modeled as an ``extended'' RFB process having $m$ (QBD) processes. In the ``extended'' RFB process, the transitions in the $i$-th process depend on the level of a process, $\widehat Q_{i-1}$, that is equivalent to the $(i-1)$-th process, $Q_{i-1}$ (see Figure 3.15(a)). Here, the only difference between $\widehat Q_{i-1}$ and $Q_{i-1}$ is how levels are defined in these two processes. Specifically, the level of $Q_{i-1}$ corresponds to the number of class $i-1$ jobs, while the level of $\widehat Q_{i-1}$ corresponds to the total number of higher priority (classes $\leq i-1$) jobs.

Figure 3.16: An example of an RFB process: Preemptive priority queue. Figures show Markov chains for the number of jobs of class $i$ (a) when there are $0$ higher priority jobs, (b) when there are $1$ higher priority jobs, (c) when there are $k-1$ higher priority jobs, and (d) when there are $\geq k$ higher priority jobs. Here, $N_i$ denotes the number of class $i$ jobs in the system.

Number of class $i$ jobs

(a) when there are $0$ higher priority jobs

(b) when there is $1$ higher priority job

$\vdots$

(c) when there are $k-1$ higher priority jobs

(d) when there are $\geq k$ higher priority jobs

Figures 3.15(b)-(c) show two equivalent QBD processes with different definitions of levels. Figure 3.15(b) is the 1D Markov chain that is reduced from a 2D Markov chain in the analysis of an M/M/2 queue with two priority classes (high priority and middle priority) via DR. (Recall the dimensionality reduction from Figure 3.3(c) to Figure 3.3(d); the low priority jobs are replaced by the middle priority jobs in Figure 3.15(b).) In the QBD process of Figure 3.15(b), level $\ell$ consists of the states with $\ell$ middle priority jobs. Observe that the QBD process in Figure 3.15(c) is exactly the same as the QBD process in Figure 3.15(b) except that they have different layout of states. In the QBD process of Figure 3.15(b), level 0 and level 1 consist of the states with 0 and 1 total jobs in the system, respectively. For $\ell>1$, level $\ell$ consists of states with $\geq \ell$ total jobs in the system. Since the bottom two rows have states with $\geq 2$ high priority jobs, the exact number of high priority jobs is not known (and hence the total number of jobs is not known, either). However, note that the QBD process in Figure 3.15(c) is exactly what we need in the analysis of low priority jobs in an M/M/2 queue with three priority classes (high, middle, and low). The behavior of the low priority jobs is determined by whether there are 0, 1, or $\geq 2$ higher priority (high or middle priority) jobs in the system, and hence by the level of the QBD process in Figure 3.15(c).

In the general case of an M/M/$k$ queue with $m$ priority classes, it is intuitively easy to see that there is a QBD process $\widehat Q_{i-1}$ that is equivalent to $Q_{i-1}$ such that the level of $\widehat Q_{i-1}$ corresponds to the total number of higher priority jobs in the system, since any event (job arrival or completion) changes the total number of jobs (and hence the level of $\widehat Q_{i-1}$) by 1. Since all the transitions are between neighboring levels, the process is a QBD process. For completeness, Figure 3.16 shows the Markov chains for the number of class $i$ jobs conditioned on the number of higher priority (classes $\leq i-1$) jobs in the system.