Size-based task assignment with cycle stealing under central queue

Figure 3.19: An example of a GFB process: Size-based task assignment with cycle stealing under central queue. (a) The SBCS-CQ policy. (b) Markov chain for the number of long jobs in the queue or in service, $N_L$, (background process) when $N_L\geq 1$. (c) Markov chain for the number of short jobs in the queue or in service at the short server (foreground process) when $N_L\geq 1$.

(a) SBCS-CQ

(b) number of long jobs when $N_L\geq 1$

(c) number of short jobs when $N_L\geq 1$

We consider size-based task assignment with cycle stealing under central queue (SBCS-CQ; see Figure 3.19(a)), where short jobs and long jobs arrive at the central queue according to Poisson processes with rate $\lambda_S$ and $\lambda_L$, respectively. The service demand of the short jobs (respectively, long jobs) has an exponential distribution with rate $\mu_S$ (respectively, $\mu_L$). We assume that jobs are nonpreemptive (i.e., once a job receives service, it runs to completion). To prevent short jobs from waiting behind long jobs, we designate one server as the short server, and the other as the long server. Whenever the short server becomes idle, it picks the first short job in the queue to run. Whenever the long server becomes idle, it picks the first long job in the queue. However, if there is no long job, the long server picks the first short job in the queue.

The number of jobs in the above system can be modeled as a GFB process^3.6. Here, we define the background process so that it tracks the number of long jobs waiting in the queue or in service at the long server, $N_L$, as well as whether the long server is serving a long job, short job, or none. Specifically, level $\ell$ in the background process corresponds to $N_L$. Also, we define the foreground process so that level $\ell$ in the foreground process corresponds to the the number of short jobs waiting in the queue or in service at the short server, $N_S$. Note that whether there is a short job in service at the long server is captured in the background process and not in the foreground process.

As long as $N_L\geq 1$, the foreground and background processes can be modeled as QBD processes, respectively. Figure 3.19(b) shows the background process when $N_L\geq 1$. It tracks $N_L$ as well as whether the long server is working on a long job (top row) or a short job (bottom row). If the long server is serving a short job, the short job is completed with rate $\mu_S$, but no long jobs are completed. If the long server is serving long jobs, long jobs are completed with rate $\mu_L$. Figure 3.19(c) shows the foreground process given $N_L\geq 1$. Since the long server is busy, it does not pick short jobs in the queue, but short jobs are completed with rate $\mu_S$ by the short server. Observe that both Markov chains in Figures 3.18(b)-(c) are QBD processes. Also, any transition from level 0 to level $\geq 1$ is to level 1 in the background process, since $N_L$ 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, job completion, and changes in the long server mode) changes the number of short jobs by at most one. Thus, these foreground and background processes constitute a GFB process.