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, , required for the donor to start working on the beneficiary's jobs, as well as a switching back time, . We assume that and 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, , is sufficiently long, and the donor's switching back may pay only when the donor's queue length, , is sufficiently long. Thus, we consider the following threshold-based policy. If and , the donor starts switching to the beneficiary's queue. After time, the donor is available to work on the beneficiary's jobs. When reaches , the donor starts switching back to its own queue. After 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.
(a) Threshold-based policy for reducing switching costs in cycle stealing
|
The number of jobs in the above system can be modeled as a GFB process3.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 in the background process (respectively, foreground process) corresponds to the number of donor jobs (respectively, beneficiary jobs) in the system.
As long as , the foreground and background processes can be modeled as QBD processes, respectively. Figure 3.18(b) shows the background process when . Since , 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 time, switching back is completed. While the donor server is serving donor jobs, the donor jobs are completed with rate . Figure 3.18(c) shows the foreground process given . Since the donor server is not helping, the beneficiary jobs complete with rate . Observe that both Markov chains in Figures 3.18(b)-(c) are QBD processes. Also, any transition from level to level is (from level ) to level in the background process, since 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.