Since the invention of networks of workstations, systems designers have touted the benefits of allowing a user to take advantage of machines other than her own, at times when those machines are idle. This notion is often referred to as cycle stealing. Cycle stealing allows such a user, Betty, with multiple jobs, to offload one of her jobs to the machine of a different user, Dan, if Dan's machine is idle, giving Betty two machines to process her jobs. When Dan's workload resumes, Betty must return to using only her own machine. We refer to Betty as the beneficiary, to her machine as the beneficiary machine/server, and to her jobs as beneficiary jobs. Likewise, we refer to Dan as the donor, to his machine as the donor machine/server, and to his jobs as donor jobs.
Although cycle stealing provides obvious benefits to the beneficiary, these benefits come at some cost to the donor. For example, the beneficiary job may have to be checkpointed and the donor's working set memory reloaded before the donor server can resume, delaying the resumption of processing of donor jobs. Furthermore, there is also some wasted time for the beneficiary who may experience various remote execution costs, and must wait for her working set memory to be loaded into the donor machine before she can use the donor machine. In our model we refer to these additional costs associated with cycle stealing as switching costs (or switching times).
A primary goal of this chapter is to understand the benefit of cycle stealing for the beneficiary and the penalty to the donor, as a function of switching times. A secondary goal is to derive parameter settings for cycle stealing. In particular, given non-zero switching times, cycle stealing may pay only if the beneficiary's queue is ``sufficiently'' long. We seek to understand the optimal threshold on the beneficiary queue when switching to help, and the optimal threshold on the donor queue when switching back. More broadly, we seek general insights into which system parameters have the most significant impact on the effectiveness of cycle stealing.