Benefit and penalty of cycle stealing

In this thesis, various resource allocation policies with cycle stealing (resource sharing in general) are introduced, and their performance is analyzed via DR. These policies include the threshold-based policy for reducing switching costs in cycle staling (Chapter 6), the task assignment with cycle stealing under immediate dispatching (SBCS-ID; Chapter 5), the task assignment with cycle stealing under central queue (SBCS-CQ; Chapter 5), and the threshold-based policies for the Beneficiary-Donor model (Chapter 7).

Although cycle stealing provides obvious benefits to the beneficiary jobs (``short'' jobs in SBCS-ID and SBCS-CQ), these benefits come at some cost to the donor jobs (``long'' jobs in SBCS-ID and SBCS-CQ). For example, the donor jobs may suffer from switching costs or may suffer from the nonpreemptive beneficiary jobs stealing cycles of the donor server. DR allows us to quantify the benefit and penalty of cycle stealing under a wide range of parameter settings, and this leads to insights into good resource allocation policies.

Our analysis shows that cycle stealing can provide unbounded benefit overall (to the beneficiary jobs in particular) over the dedicated policy (without cycle stealing). The unbounded benefit stems from the increased stability region under cycle staling, and we have provided the necessary and sufficient conditions for stability under all the resource allocation policies with cycle stealing studied in this thesis. These stability conditions are often nontrivial. For example, under the threshold-based policy for reducing switching costs in cycle staling, we find that the beneficiary side threshold, $N_B^{th}$, does not affect the stability region, but increasing the donor side threshold, $N_D^{th}$, increases the stability region.

The mean response time of donor jobs is sensitive to the switching times, and large switching times can result in a significant penalty to the donor jobs. Switching times also diminish the benefit of cycle stealing to the beneficiary jobs. We find that switching times have a significant impact on the mean response time when the beneficiary is overloaded without cycle stealing ($\rho_B \geq 1$), but the mean response time of the beneficiary jobs is far less sensitive when $\rho_B < 1$.

Our analysis shows that long jobs experience only a small penalty under both SBCS-ID and SBCS-CQ. We also consider the case where the ``short'' jobs are indistinguishable from the ``long'' jobs, and the pathological case where the ``short'' jobs are longer than the ``long'' jobs. Our analysis shows that SBCS-ID and SBCS-CQ can still provide an unbounded benefit over Dedicated when the load of short jobs is high, but the benefit diminishes as the load becomes lower. In fact, when the load of short jobs is low, cycle stealing (especially, SBCS-ID) can worsen the overall mean response time.