Threshold-based policy for reducing switching costs in cycle stealing

We consider two processors, each serving its own M/M/1 queue, where one of the processors (the donor) can help the other processor (the beneficiary) while the donor's queue is empty (see Figure 3.18(a)). There is a switching time, $K_{sw}$, required for the donor to start working on the beneficiary's jobs, as well as a switching back time, $K_{ba}$. We assume that $K_{sw}$ and $K_{ba}$ have exponential distributions (but this can be generalized to PH distributions). Due to non-zero switching times, the donor's switching may pay only when the beneficiary's queue length, $N_B$, is sufficiently long, and the donor's switching back may pay only when the donor's queue length, $N_D$, is sufficiently long. Thus, we consider the following threshold-based policy. If $N_B \geq N_B^{th}$ and $N_D = 0$, the donor starts switching to the beneficiary's queue. After $K_{sw}$ time, the donor is available to work on the beneficiary's jobs. When $N_D$ reaches $N_D^{th}$, the donor starts switching back to its own queue. After $K_{ba}$ time, the donor resumes working on its own jobs. We will study the performance of the threshold-based policy for reducing switching costs in cycle stealing in Chapter 6. Below, we will model the system with this threshold-based policy as a GFB process.

Figure 3.18: An example of an GFB process: Threshold-based policy for reducing switching costs in cycle stealing. (a) Threshold-based policy for reducing switching costs in cycle stealing. (b) Markov chain for the number of donor jobs, $N_D$, (background process) when $N_D\geq N_D^{th}$. (c) Markov chain for the number of beneficiary jobs (foreground process) when $N_D\geq N_D^{th}$.

(a) Threshold-based policy for reducing switching costs in cycle stealing

(b) number of donor jobs when $N_D\geq N_D^{th}$

(c) number of beneficiary jobs when $N_D\geq N_D^{th}$

The number of jobs in the above system can be modeled as a GFB process^3.5. Here, the background process captures the number of the donor's jobs and the mode of the donor (whether it is at its own queue, is switching to the beneficiary's queue, is at the beneficiary's queue, or is switching back to its own queue), and the foreground process captures the number of the beneficiary's jobs. Specifically, level $\ell$ in the background process (respectively, foreground process) corresponds to the number of donor jobs (respectively, beneficiary jobs) in the system.

As long as $N_D\geq N_D^{th}$, the foreground and background processes can be modeled as QBD processes, respectively. Figure 3.18(b) shows the background process when $N_D\geq N_D^{th}$. Since $N_D\geq N_D^{th}$, the donor server is either switching back to its own queue (top row) or serving donor jobs (bottom row). If the donor server is switching back, the donor jobs do not complete. After $K_{ba}$ time, switching back is completed. While the donor server is serving donor jobs, the donor jobs are completed with rate $\mu_D$. Figure 3.18(c) shows the foreground process given $N_D\geq N_D^{th}$. Since the donor server is not helping, the beneficiary jobs complete with rate $\mu_B$. Observe that both Markov chains in Figures 3.18(b)-(c) are QBD processes. Also, any transition from level $<N_D^{th}$ to level $\geq N_D^{th}$ is (from level $N_D^{th}-1$) to level $N_D^{th}$ in the background process, since $N_D$ 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 donor server mode) changes the number of beneficiary jobs by at most one. Thus, these foreground and background processes constitute a GFB process.