Concluding remarks

In this chapter, size-based task assignment policies with cycle stealing, SBCS-ID and SBCS-CQ, are proposed, and their mean response time is analyzed via dimensionality reduction (DR), as the analysis of SBCS-ID and SBCS-CQ involves multidimensional Markov chains. Under SBCS-ID and SBCS-CQ, short jobs are processed by one server (short server) and long jobs are processed by another server (long server), but when there are no long jobs, the long server also processes short jobs, i.e. short jobs can steal idle cycles of the long server. DR allows us to quantify the benefit and penalty of cycle stealing, and provides insights into good task assignment policies.

Our analysis shows that the short jobs can benefit immensely from cycle stealing, while long jobs experience only a small penalty. Also, we find that holding jobs at a central queue (SBCS-CQ) provides more benefit of cycle stealing to the short jobs with a smaller penalty to the long jobs than immediately dispatching jobs upon their arrivals (SBCS-ID). Thus, overall, SBCS-CQ is a superior policy to SBCS-ID. In fact, SBCS-ID often provides an unbounded benefit over the Dedicated policy (without cycle stealing), and SBCS-CQ often provides an unbounded benefit over SBCS-ID. The unbounded benefit stems from the increased stability region under SBCS-ID and SBCS-CQ. We provided the necessary and sufficient conditions for the stability under these policies.

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 are low, cycle stealing (especially, SBCS-ID) can worsen the overall mean response time. However, since the performance improvement is most needed at high load, SBCS-ID and SBCS-CQ may still have a practical use even in the pathological case.

An advantage of the analysis via DR is that the job sizes can be modeled as a PH distribution. This allows us to study the impact of job size variability on performance. In particular, we study the impact of the variability of the long job sizes on the mean response time of the short jobs. We find that the impact is surprisingly small under SBCS-ID, but larger under SBCS-CQ. Another advantage of the analysis via DR is that it allows us to evaluate the mean response time accurately for a wide range of loads. This is in contrast to heavy traffic approximations, which becomes more accurate at higher loads. We have seen that the benefit and penalty of cycle stealing are quite different at low load and high load. Specifically, when the load of the short jobs is low, cycle stealing can worsen the mean response time. It would be interesting to see whether heavy traffic approximations can capture this.

In this chapter, we limit our discussion to a system with two homogeneous servers, but the analysis via DR can be extended to heterogeneous servers and multiple servers in various ways. For example, in [68], we study SBCS-ID with multiple short servers that independently receives short jobs and steal idle cycles of the long server. We find that the benefit of cycle stealing reduces as the number of short servers increases, but the most reduction comes from the first additional short server. In [68], we also extend Theorem 9 and Theorem 10 to the case of multiple short servers. Also, in Chapter 3, we show that SBCS-ID with $m$ classes of jobs and $m$ servers can be modeled as an RFB process, and validated the analysis via DR against simulation. These analysis will be useful in practice to decide, for example, how many servers are needed and how much capacity is needed for each server to guarantee certain mean response time, when SBCS-ID is used in real systems.