Nonpreemptive priority queue

Consider an M/M/$k$ queue with two priority classes (high and low), where high priority jobs have nonpreemptive priority over low priority jobs. That is, a high priority job can move ahead of all the low priority jobs waiting in the queue, but low priority jobs in service are not interrupted by high priority jobs.

The number of jobs in this system can be modeled as a GFB process. Here, we define the background process so that it tracks the number of high priority jobs waiting in the queue or in service, $N_H$, as well as the number of low priority jobs in service. Specifically, level $\ell$ in the background process consists of states with $N_H=\ell$. Also, we define the foreground process so that it tracks the number of low priority jobs waiting in the queue, $N_S$. Specifically, level $\ell$ in the foreground process is the state with $N_S=\ell$. Note that the number of low priority jobs in service is captured in the background process and not in the foreground process.

Figure 3.20: An example of a GFB process: Nonpreemptive priority queue. (a) Markov chain for the number of high priority jobs, $N_H$, (background process) when $N_H\geq 2$. (b) Markov chain for the number of low priority jobs in the queue (foreground process) when $N_H\geq 2$.

(a) number of high priority jobs, $N_H$, when $N_H\geq 2$

(b) number of low priority jobs when $N_H\geq 2$

As long as $N_H \geq k$ (there are enough high priority jobs to occupy all the servers), the foreground and background processes can be modeled as QBD processes, respectively. Figure 3.19 shows a part of the foreground and background processes when the number of servers $k=2$. Figure 3.19(a) shows the background process when $N_H \geq 1$. It tracks $N_H$ as well as the number of low priority jobs in service. When there are $n$ low priority jobs in service, $2-n$ servers are serving high priority jobs, and high priority jobs are completed with rate $(2-n)\mu_H$ for $n=0,1,2$. Figure 3.19(b) shows the foreground process given $N_H \geq 1$. Since all the servers are occupied, no low priority jobs waiting in the queue start receiving service, and the number of low priority jobs in the queue increases with rate $\lambda_L$. Observe that both Markov chains in Figures 3.18(a)-(b) are QBD processes. Also, any transition from level $<k$ to level $\geq k$ is (from level $k-1$) to level $k$ in the background process, since $N_H$ is never incremented more than one at a time. Further, any transition changes the level of the foreground process by at most one, since any event (job arrival, or job completion) changes the number of low priority jobs in the queue by at most one. Thus, these foreground and background processes constitute a GFB process.