Threshold based policy for reducing switching costs in cycle stealing

Specifically, we assume there are two queues, the beneficiary queue and the donor queue, with independent arrival processes and service time distributions operating as M/PH/1/FCFS queues (see Figure 6.1). Jobs arrive at rate $\lambda_B$ (respectively, $\lambda_D$) at the beneficiary (respectively, donor) queue and have service demand $X_B$ with a phase type (PH) distribution $G_B$ (respectively, $X_D$ with a PH distribution $G_D$). The load made up by beneficiary (respectively, donor) jobs is denoted by $\rho _B$ (respectively, $\rho_D$) where $\rho_B = \lambda_B \mbox{{\bf\sf E}}\left[ X_B \right]$ and $\rho_D = \lambda_D \mbox{{\bf\sf E}}\left[ X_D \right]$.

To reduce the switching costs associated with cycle stealing, we consider the following threshold-based policy. If there are no donor jobs ($N_D = 0$), and if the number of the beneficiary jobs, $N_B$, is at least $N_B^{th}$, the donor transitions into the switching state, for a random amount of time, $K_{sw}$, having a PH distribution. After $K_{sw}$ time, the donor server is available to work on the beneficiary queue and the beneficiary queue becomes an M/$G_B$/2/FCFS queue. When the number of donor jobs, $N_D$, reaches $N_D^{th}$ (either during $K_{sw}$, or during the time the donor is helping the beneficiary), the donor transitions into a switching back state, for a random amount of time, $K_{ba}$, having a PH distribution. After the completion of the switch back, the donor server resumes working on its own jobs until the donor queue is empty. The donor server cannot work on any job while the donor is in the switching or switching back state.

Figure 6.1: A threshold-based policy for reducing switching costs in cycle stealing.

A few details are in order. First, in the above model, the donor server continues to cooperate with the beneficiary even if there is no beneficiary work left for it to do -- the donor server can switch back only when a donor job arrives. Second, we assume that if the donor server is working on a beneficiary job and a donor job arrives, that beneficiary job is returned to the beneficiary queue and will be resumed by the beneficiary server as soon as that server is available. The work done on the job is not lost (i.e. preemptive resume). Our performance metric throughout is mean response time (overall and for each class of jobs), where the response time of a job is the time from when the job arrives until it completes service. We assume the first three moments of the service times are finite, and queues are stable.

Our model deals with switching times in a general way, making the results both applicable to a shared-memory multiprocessor architecture and to a network of workstations (NOW). Our switching times, $K_{sw}$ and $K_{ba}$, can be viewed as the time for switching between job types in a shared-memory multiprocessor architecture. In a NOW, there is an additional overhead incurred from migrating jobs from one server to another, where jobs which have not started running require negligible overhead, whereas migrating a ``running'' job (in progress) requires high overhead, since all of its state must be migrated with it. Our model captures this notion in that the switching back time, $K_{ba}$, can be viewed as the time incurred for preempting an already running job and returning it to the beneficiary.