Modeling and analysis

We assume that the service demand of the short jobs, $X_S$, has a phase type (PH) distribution (see Section 2.2), and the service demand of the long jobs, $X_L$, has another PH distribution. Thus, we do not require that the exact service demand of jobs be known in advance. Rather, we assume that, based on some information such as the owner of a job and the CPU requirement specified by a user, we can classify jobs into ``short'' jobs that are likely to be short and ``long'' jobs that are likely to be long. We will consider three scenarios: the expected size of ``short'' jobs is shorter than that of ``long'' jobs, ``short'' jobs and ``long'' jobs have an identical job size distribution, and a pathological case where the expected size of ``short'' jobs is longer than that of ``long'' jobs.

Throughout, we assume that the short jobs (respectively, long jobs) arrive according to a Poisson process with rate $\lambda_S$ (respectively, $\lambda_L$), although the analysis via dimensionality reduction (DR) allows an extension to Markovian arrival processes (see Section 2.2), as we have discussed in Chapter 3. We define the load of the short jobs as $\rho_S=\lambda_S\mbox{{\bf\sf E}}\left[ X_S \right]$ and the load of the long jobs as $\rho_L=\lambda_L\mbox{{\bf\sf E}}\left[ X_L \right]$.

With the above assumptions, the system with SBCS-ID can be modeled as an FB process, and the system with SBCS-CQ (without renaming) can be modeled as a GFB process, as discussed in Section 3.4, and the analysis of these processes via DR provides mean response time of the short jobs and the long jobs, respectively, under SBCS-ID and SBCS-CQ. The system with SBCS-CQ with renaming does not appear to be modeled as a GFB process, and in [67], we analyze its performance via DR with a certain independence assumption (some random variables with dependency are assumed to be independent); however, this approximation is validated against simulation, which shows that the error is within 2% in almost all cases, and within 8% in all cases (large error occurs at high load) [67]. All the details of the analysis of the SBCS-ID and SBCS-CQ, used to generate the results in Section 5.4, are provided in [67,68]. In particular, we derive a closed form expression for the mean response time of the long jobs under SBCS-ID via a virtual waiting time analysis in [68], as shown in the following theorem.

Theorem 9   Let $T_L$ represent the response time of the long jobs under SBCS-ID, and let $\widetilde T_L(s)$ denote it's Laplace transform. Then,

$$\begin{eqnarray*} \widetilde T_L(s) & = & \frac{s+\lambda_S-\widetilde X_S(s)\la... ...}}\left[ X_L^2 \right] - 2\mbox{{\bf\sf E}}\left[ X_L \right]^2, \end{eqnarray*}$$

where

$$\pi_0 = \frac{1-\rho_L}{1+\rho_S}.$$

Here, $\pi_0$ represents the fraction of time that the long server is idle.

We postpone the proof of this theorem to Appendix A.