RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Adaptive allocation
of CPU quanta.

D.Potier
E.Gelenbe, J.Lenfant

Rapport de Recherche n° 58
avril 1974
ADAPTIVE ALLOCATION OF CPU QUANTA

D. Potier*, E. Gelenbe*, J. Lenfant**

ABSTRACT

The allocation of the central processing unit (CPU) of a computer
system in quanta of fixed length in round robin fashion favors jobs with
shorter total CPU processing time by reducing the time they spend waiting
in queue than if all the jobs were served in first-come-first-served
order. This effect can be accentuated by the use of short quanta. The
main disadvantage of this allocation policy is the resulting time the
CPU spends in overhead activities when switching from one task to the
other and this too will increase with smaller quanta. Thus it appears
useful to consider adaptive CPU allocation policies to reduce the overhead
during high traffic conditions when saturation of this resource is more
likely while keeping a small quantum during periods of low arrival traffic.

In this paper we analyze such a policy : it is assumed that each time
at least r (a threshold) arrivals occur during a quantum, the job
currently using the CPU is allocated an additional quantum (if it is
needed). Thus the number of job arrivals during a quantum is used as
a sensor of the intensity of arrival traffic. This policy, which can
be easily implemented in hardware, is analyzed using a mathematical
model yielding the average response time for jobs as a function of mean
total CPU time, the quantum size, r and a fixed overhead for switching
tasks, with a Poisson arrival process. Numerical results to illustrate
the effect of this policy are presented.

<footnote>*IRIA</footnote>

<footnote>**Département de Mathématiques et Informatique, Université de Rennes.</footnote>
RESUME

L'allocation de l'unité centrale (UC) dans un système à temps partagé est réalisée à partir de stratégies qui tentent de favoriser les usagers dont le temps de service est court en allouant l'UC aux usagers pendant au plus q unités de temps consécutives, où q est appelé le quantum.

Cette méthode d'ordonnancement a un inconvénient évident : chaque fois qu'un usager achève son quantum, le système doit passer en mode superviseur afin de déactiver l'usager en cours de service et d'activer l'usager suivant. Ces opérations augmentent le temps passé par l'UC en activité de superviseur, temps qui représente l'overhead de la méthode d'ordonnancement.

L'objet de cette note est d'analyser l'effet sur les performances du système de l'allocation d'un quantum supplémentaire à l'usager en cours de service si un nombre d'usagers supérieur à r-1, où r est appelé le seuil, ont pénétré dans le système pendant le quantum en cours.
ADAPTIVE ALLOCATION OF CPU QUANTA

I - INTRODUCTION.

The allocation of the central processing unit (CPU) in a time-shared
computing system is based on strategies which attempt to favor users having
a short processing requirement by assigning the CPU to the users for at most
q consecutive units of time. q is usually called the *quantum*, and users re-
quiring a total CPU time of several quanta are placed in the CPU queue at
the end of each quantum to wait once again for their turn for service.

Such scheduling techniques have an obvious disadvantage. Each time a
user quantum terminates (this can be signalled by a hardware clock) the
system has to enter the supervisor mode so as to deactivate the current
user (stack his program status word, etc...) and to activate the next user.
This will increase the amount of time spent by the CPU in supervisory acti-
vities and will constitute the *overhead* of the scheduling method.

Several authors (1), have analyzed models of such time-sharing sche-
duling algorithms and Coffman (2) has suggested a technique which renders the
allocation of several consecutive quanta to a user dependent on input activity.
Coffman's approach is adaptive in the sense that during intervals of time
at which the number of new arrivals to the CPU queue is high, less time is
expended in overhead.

Heacox and Purdom (3) have analyzed a system similar to the one suggested
by Coffman by using a continuous time queueing model with exponentially dis-
tributed interarrival and service times. They assume that an additional quan-
tum will be allocated to the current program in execution, if a new arrival
to the system has occurred during the current quantum.

The purpose of this note is to analyze the effect, on the operation of
the system, of allocating an additional quantum to the current user if more
than r-1 users have arrived to the system during the current quantum. r is
called the threshold. Such a scheme is not difficult to implement in hardware ;
if each new arrival manifests itself by an interrupt (which is stacked), a
counter set to r would produce a signal masking the interrupt of the hard-
ware clock (used to indicate the end of the quantum) if the number of new
arrivals during a quantum is at least r. The hardware clock would be used
in any case to reset the counter at the end of each quantum.

## II - THE MODEL.

Consider the model described in Figure 1. Users arrive to the system
from the "outside world" to node x following a Poisson process with rate $\lambda$.

<figure><img src="image_1.png" /><figcaption>Figure 1</figcaption></figure>

They are placed in FIFO (First-In-First-Out) order in the queue. Users
also arrive to x from w and are also placed in the queue. The users
in the queue do not include the user receiving service at the CPU ; the
number in the system will include the users in the queue and the one occu-
pying the CPU. Let $\gamma_r$ given by
$$ (1) \qquad \gamma_r = \sum_{i=r}^{\infty} e^{-\lambda q} \frac{(\lambda q)^i}{i!} $$

be the probability of more than r-1 arrivals during a quantum. Let also the service requirement of each user at the CPU be an exponentially distributed random variable t with expected value 1/μ; t is exclusive of overhead (swap time) which is a constant s. The probability that a user will not complete its processing requirements during a quantum is then

$$ (2) \qquad \delta = \int_{q}^{\infty} e^{-\mu t} dt = e^{-\mu q} $$

Thus, during a quantum, a user will leave the CPU and the system (via τ) with probability 1-δ. The actual time τ used by a user during a quantum (excluding overhead) is therefore a random variable with probability distribution F(τ):

$$ (3) \qquad F(\tau) = \begin{cases} 0 & \text{if } \tau < 0 \\ 1 - e^{-\mu\tau} & \text{if } 0 \le \tau < q \\ 1 & \text{otherwise} \end{cases} $$

The probability that the user will remain at the CPU (going from z, via w, back to y) when it reaches the end of the quantum, and that the end of the quantum is reached, is $\delta \gamma_r$. This yields no overhead . On the other hand, with probability $(1-\gamma_r)\delta$ the user will head back to x and into the queue, utilizing the CPU for an additional time s (the overhead). It is assumed that the overhead is incurred also when a user leaves the system.

In the sequel, we obtain expressions for the expected total time in the system (response time) $W(k)$ for users requiring k quanta, as a function of s, r and q. The effect on system performance of varying r is investigated and illustrated by several numerical examples.
### III - THE MAIN RESULT.

The main result obtained from the analysis of the model is an expression for the expected response time (expectation of total time in queue, plus total overhead, plus service time) for a program requiring k quanta; let it be $W_r(k)$ for a system with threshold value r. We obtain:

$$W_r(k) = z_o + \frac{\rho}{\lambda(1-\rho)} (m'_1 + m_1 + \lambda \frac{q \frac{\gamma_{r-1}}{\gamma_r} - Q}{1-\alpha} - (m'_1 + \alpha(m_1 + \lambda \frac{q \frac{\gamma_{r-1}}{\gamma_r} - Q}{1-\alpha}))) \times (\gamma_r + \alpha(1-\gamma_r))^{k-1} - \frac{1 - (\gamma_r + \alpha(1-\gamma_r))^k}{(1-\alpha)(1-\gamma_r)} \lambda q \frac{\gamma_{r-1}}{\gamma_r} + (k-1)\lambda q \gamma_{r-1} + \lambda Q (\gamma_r + k(1-\gamma_r))$$

where $z_o$ is the expected completion time (for the current pass) of the program in execution when the tagged program arrives:

$$z_o = \frac{\lambda s}{1-\xi} \left( \frac{s}{2} + \frac{1}{\mu}(1-\xi) \right) + \frac{\lambda}{\mu^2} \frac{1-\delta(\mu g + 1)}{1-\delta} + \frac{\lambda \delta}{1-\delta} Q \gamma_{r-1} \left( \frac{q}{2} + \frac{1}{\mu}(1-\xi) \right)$$

$\xi$ being defined as the probability that a program, having just finished a pass will require more service:

$$\xi = \delta \frac{1-\gamma_r}{1-\delta\gamma_r}, \quad \alpha = \xi + \rho(1-\xi)$$

In the expression for $W_r(k)$, $\rho$ is given by:

$$\rho = \frac{\lambda}{\mu} \left( 1 + \frac{\mu s}{1-\xi} \right)$$

and represents the C.P.U. load factor. The parameter $m'_1$ is given by

$$m'_1 = \eta + \lambda z_o$$

where $\eta$ is the probability that the program P in execution at the arrival of the tagged program does not terminate its computation during the current pass

$$\eta = \frac{\lambda s \xi}{1-\xi} + \frac{\lambda \delta (1-\gamma_{r-1})}{1-\delta} q = \lambda \frac{\xi}{1-\xi} Q$$

Notice that $m'_1$ is the expected number of programs which are found behind the tagged unit just after the P terminates its pass (during which the tagged unit arrived). We have used $Q$ to denote
$$Q = s + q \frac{1 - \gamma_{r-1}}{1 - \gamma_r}$$

Finally, $m_l$ being the expected number of programs in front of the tagged job at its arrival, we have

$$m_l = \lambda W_r$$

where $W_r$ is the average (over all k) of $W_r(k)$ :

$$W_r = \sum_{k=1}^{\infty} W_r(k) \int_{(k-1)q}^{k q} \mu e^{-\mu t} dt$$

$$= (1-\delta) \sum_{k=1}^{\infty} W_r(k) \delta^{k-1}$$

We are now able to compute the expression for $W_r(k)$ given at the head of this section.

The proof is given in Section V.
IV - NUMERICAL EXAMPLES.

The result obtained is best illustrated by a number of numerical examples plotted on the accompanying figures. All the numerical results have been computed for values of $r=1, 2, 3, 4$ of the threshold. Note that for $r=1$ we have the "Multiple quantum" model (M.Q.) of HEACOX and PURDOM (3) and for $r=\infty$ their "single quantum" model (S.Q.). As a whole the numerical examples show that the S.Q. model is practically reached for $r=3$ or $r=4$, depending on the parameters, and that the results for $r=2$ lie closer to those of the (S.Q.) model than to those for the (M.Q.) model. This simply means that for $r=2$ the condition for an additional quantum allocation becomes severe, and is actually never met for $r \ge 4$.

Waiting time, mean waiting time and C.P.U. utilization are plotted on figures 2, 3 and 4, as a function of arrival rate. Adaptive allocation is shown, for small values of $r$, to cause C.P.U. utilization to increase with the load of the system, the more rapidly the swap time is larger (Fig. 4). As for waiting time, adaptive allocation does always do better than fixed allocation when mean waiting time is concerned (Fig. 3), though it tends to increase waiting time for short programs (Fig. 2). This is no longer true when the arrival rate becomes high : as a rule, the more heavy the load of the system, both from arrival rate and overhead, the more efficient the adaptive allocation.

The effect of quantum length on mean waiting time is investigated on Fig. 5. Acceptable quantum lengths increase with swap time, and preference for adaptive allocation turns out to cease when the quantum length is large. This would cause, for small swap times, some of the conclusions drawn from fig. 3 to be negative : for $q=0.8$ sec., adaptive allocation would be no more better if $s=0.05$ sec. (Fig. 5).
<figure><img src="image_2.png" /><figcaption>**Figure 2** : Waiting time as a function of arrival and service requirements
k=1,2,4, r=1,2,3,4, q=0.15 sec., s=0.02 sec., µ =1.0 sec.<sup>-1</sup></figcaption></figure>
<figure><img src="image_3.png" /><figcaption>**Figure 3** : Mean waiting time as a function of arrival rate and swap time.
r=1,2,3,4, q=0.15 sec., µ =1.0 sec.⁻¹</figcaption></figure>
<figure><img src="image_4.png" /><figcaption>Figure 4 : C.P.U. utilization as a function of arrival rate and swap time
r=1,2,3,4, q=0.15 sec., μ =1.0 sec⁻¹</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>**Figure 5** Waiting time as a function of quantum length and service requirement.
k=1,2,4, r=1,2,3,4, s=0.04 sec., λ=0.5 sec.⁻¹, μ=1.0 sec.⁻¹</figcaption></figure>
V - Proof of the main result

The proof follows closely an argument similar to the one developped
in (3) . Using the method of Coffman and Kleinrock(1) we consider a "tagged
unit" requiring k quanta of service which arrives when the system is in
equilibrium, and let n be the number of passes made by the tagged unit,
where 1 ≤ n ≤ k. We define p_n(k) as the probability that a program requi-
ring k quanta will make n passes. We have

$$
(1) \qquad p_n(k) = \binom{k-1}{n-1} \gamma_r^{k-n} (1-\gamma_r)^{n-1},
$$
where $\gamma_r$ is given by (1).

We define $\omega_n(k)$ to be the mean waiting time in queue for a k-quanta program which makes exactly n passes, then

$$
(2) \qquad W_r(k) = \sum_{n=1}^{k} p_n(k) \omega_n(k).
$$

In order to find an expression for $\omega_n(k)$ we break up the waiting time of
the tagged unit into two parts, T1 and T2 :

a program contributes to T1 if it was being swapped or processed
when the tagged unit arrived, or if it arrives during swapping or processing
of a program contributing to T1 ;

a program contributes to T2 if it was waiting in queue at arrival of
the tagged unit, or if it arrives during swapping or processing of a program
contributing to T2. Then

$$
(3) \qquad \omega_n(k) = E_{k,n}^{(T1)} + E_{k,n}^{(T2)}.
$$
## Evaluation of T2

Let $y_i$ be the tagged unit's waiting time in queue on its i-th pass (excluding waiting time due to the program possibly operating at arrival). Then we have

$$E_{k,n}(T2) = \sum_{i=1}^{n} E(y_i).$$

If $m_i$ is the expected number of programs in the queue on the i-th pass (ahead of the tagged unit), and if $\tau_l$ is the mean processing time per program per pass, then

$$E(y_i) = m_i(\tau_l+s),$$

and

$$E_{k,n}(T2) = \sum_{i=1}^{n} m_i(\tau_i+s). \quad (4)$$

We now define $\bar{\zeta}$ as the probability that a program, having just finished a pass will require more service. Assume that the tagged unit received $k_{n,i-1}$ quanta on the (i-1)th pass, which implies that each of the $k_{n,i-1}^{-1}$ quanta had at least r arrivals in it, and let $N_r$ be the expected number of arrivals during each of these $k_{n,i-1}^{-1}$ quanta. We have

$N_r = E (\text{number of arrivals in a quantum} | \text{there are at least r arrivals}),$

$$N_r = \frac{\sum_{p=r}^{\infty} pe^{-\lambda q (\lambda q)^p} p!}{\sum_{p=r}^{\infty} e^{-\lambda q (\lambda q)^p} p!},$$

$$N_r = \lambda q \frac{\gamma_{r-1}}{\gamma_r}. \quad (5)$$

During the last quantum of the $k_{n,i-1}$ quanta the number of arrivals is less
than r. The expected number of arrivals is, in this case :

$$
\frac{\sum_{p=0}^{r-1} pe^{-\lambda q} \frac{(\lambda q)^p}{p!}}{\sum_{p=0}^{r-1} e^{-\lambda q} \frac{(\lambda q)^p}{p!}} = \lambda q \frac{1-\gamma_{r-1}}{1-\gamma_r}.
$$

Furthermore, $\lambda$s programs will have arrived during the tagged unit's
swap on the preceding pass, and $\lambda$ $m_{i-1}(\tau_1+s)$ programs will have arrived du-
ring processing of the queue. Then :

$$
m_i = \zeta m_{i-1} + \lambda m_{i-1}(\tau_1 + s) + N_r E(k_{n,i-1}-1) + \lambda s + \lambda q \frac{1-\gamma_{r-1}}{1-\gamma_r}.
$$

Following Coffman (2) , we take k$_{n,i}$ = k/n , for all i . Then letting

$$
(6) \qquad \alpha = \zeta + \lambda(\tau_1 + s),
$$

$$
(7) \qquad Q = s + q \frac{1-\gamma_{r-1}}{1-\gamma_r},
$$

we obtain

$$
m_i = \alpha m_{i-1} + \left(\frac{k}{n} - 1\right) N_r + \lambda Q .
$$

Proceeding by induction, we have

$$
(8) \quad m_i = \alpha^{i-1} m_1 + \left( \left( \frac{k}{n} - 1 \right) N_r + \lambda Q \right) \frac{1-\alpha^{i-1}}{1-\alpha}
$$

we defer the evaluation of $m_1$ to the end of the proof. For $\zeta$ we consider
the model described in figure 1. Letting $\lambda_s$ and $\lambda_q$ be the arrival rate
of swaps and quanta, we have, by definition of $\xi$,

$$
\begin{align*}
\zeta \lambda_s &= \lambda_q \delta (1 - \gamma_{\dot{r}}), \\
\zeta &= \frac{\lambda}{\lambda_s} \delta (1 - \gamma_r),
\end{align*}
$$
we have also

$$ (9) \qquad \begin{aligned} \lambda_q &= \lambda_s + \delta\gamma_r \lambda_q, \\ \frac{\lambda_q}{\lambda_s} &= \frac{1}{1-\delta\gamma_r}, \end{aligned} $$

it follows

$$ (10) \qquad \xi = \delta \frac{1 - \gamma_r}{1 - \delta \gamma_r}. $$

For $\tau_l$, we observe that the probability that a program will take $j$ quanta on a single pass, without completing its service requirement, is given by $\gamma_r^{j-1}(1-\gamma_r)\delta^j$. The probability of taking $j$ quanta, completing on the $j$-th, is given by $\gamma_r^{j-1}(1-\delta)\delta^{j-1}$. Thus

$$ \tau_l = \sum_{j=1}^{\infty} \left( \gamma_r^{j-1} (1-\gamma_r) \delta^j jq + \gamma_r^{j-1} (1-\delta) \delta^{j-1} \left( (j-1)q + E_1(t) \right) \right), $$

where $E_1(t)$ is the mean time taken by a program to which $q$ seconds have been allocated, assuming the program completes during the $q$ seconds ($t < q$).

$$ \tau_l = \delta q(1-\gamma_r) \sum_{j=1}^{\infty} j(\gamma_r \delta)^{j-1} + q(1-\delta) \sum_{j=1}^{\infty} (j-1)(\gamma_r \delta)^{j-1} + (1-\delta)E_1(t) \sum_{j=1}^{\infty} (\gamma_r \delta)^{j-1}, $$

$$ \tau_l = \frac{\delta q + (1-\delta)E_1(t)}{1 - \gamma_r \delta}, $$

$$ E_1(t) = \int_0^{q-} \mathrm{tdF}(t) / \int_0^{q-} \mathrm{dF}(t) = \frac{(1-\delta)/\mu - \delta q}{1-\delta}. $$

Therefore,

$$ \tau_l = \frac{1}{\mu} \frac{1-\delta}{1-\delta\gamma_r}, $$

$$ (11) \qquad \tau_l = \frac{1}{\mu} (1-\xi). $$
We have also :

$$ \rho = \lambda E(\tau), $$

where $\tau$ includes both execution and swap times. Then

$$ \rho = \lambda \sum_{k=1}^{\infty} \int_{(k-1)q}^{kq} \sum_{i=1}^{k} (t+is)p_i(k)\mu e^{-\mu t} dt, $$

$$ (12) \qquad \rho = \frac{\lambda}{\mu} \left( 1 + \frac{\mu s}{1-\xi} \right). $$

then, using (A6) and (A12), we get

$$ \alpha = \xi + \rho (1-\xi). $$

Substituting (A8) into (A6) we have

$$ E_{k,n}(T2) = (\tau_1+s) \sum_{i=1}^{m} \left( \alpha^{i-1} m_i + \left( \left( \frac{k}{n} - 1 \right) N_r + \lambda Q \right) \frac{1-\alpha^{i-1}}{1-\alpha} \right) $$

$$ (13) \qquad = \frac{\tau_1 + s}{1 - \alpha} \left( (k-n)N_r + n \lambda Q + \left( m_1 - \frac{\left(\frac{k}{r}-1\right)N_r + \lambda Q}{1-\alpha} \right) (1-\alpha^n) \right). $$

## Evaluation of $\tau_1$

We now turn to $\tau_1$, the waiting time due to a program in service at the arrival of the tagged unit. Consider first the expected time $z_o$, to completion of the service in progress. We have three possibilities :

* With probability $\pi_s$, the tagged unit may arrive during a swap.

* With probability $\pi_q$, the tagged unit may arrive during a quantum.

* With probability $\pi_{cq}$, the tagged unit may arrive during a quantum, which satisfies the following conditions : the program in service does not complete its service requirement during this quantum, and at least $r-1$ arrivals occur during this quantum.
In the latter case the program in service will get an additional
quantum, and, using the memoryless property, will operate for $\tau_1$ seconds
after the completion of the current quantum. Since the expected time to
complete the current quantum is $\frac{q}{2}$, we have then :

$$z_o = \pi_s ( \bar{s} + \tau_1 ) + \pi_q \bar{q} + \pi_{cq} ( \tau_1 + \frac{q}{2} )$$

where $\bar{s}$ and $\bar{q}$ are the expected time remaining in the swap and quantum,
respectively for the first and the second possibility.

Evaluation of $\pi_s$ and $\bar{s}$

We have

$$\pi_s = \lambda_s s,$$

where $\lambda_s$ is defined as before. By definition of $\zeta$ we obtain

$$\lambda_s = \lambda + \zeta \lambda_s,$$

$$\lambda_s = \frac{\lambda}{1-\zeta},$$

and

$$\pi_s = \frac{\lambda_s}{1-\zeta}.$$

Since the swap time is constant, and arrivals of programs and swaps
are independent events, we have $\bar{s} = \frac{s}{2}$.

Evaluation of $\pi_s$ and $\bar{q}$

We have

$$\pi_q = \lambda_q E(t),$$

where $E(t)$, the mean amount of time actually used during a quantum $q$, is
the first moment of $F(\tau)$ given by Equation (3). Then

$$E(t) = \frac{1}{\mu} (1-\delta).$$
The arrival rate of quanta, $\lambda_q$, is obtained from (A9)

$$ \lambda_q = \frac{\lambda_s}{1-\frac{\lambda}{\epsilon}} = \frac{\lambda}{1-\frac{\lambda}{\epsilon}}, $$

and

$$ \pi_q = \frac{\lambda}{\mu} $$

The mean amount of service time $\bar{\tau}$ processed in a quantum after the arrival of the tagged unit is obtained as an application of the following remark.

**Remark.** Consider a queueing system with Poisson arrival process independent of the service time which is arbitrarily distributed with first two moments $E(\tau)$ and $E(\tau^2)$ and independent of queue length. Successive service times are not necessarily independent. The expected remaining time $\bar{\tau}$ to complete the service of the unit being processed at the arrival of a new unit is given by:

$$ \bar{\tau} = \frac{1}{2} \frac{E(\tau^2)}{E(\tau)} . $$

**Proof.**

Let $\tau$ be the service requirement of the unit in service at the arrival of a new unit. Since the arrival process and the service process are independent, the excepted remaining time to complete the service of the unit being processed after the arrival of the new unit is $\frac{\tau}{2}$. The probability of the event: "the arrival of the new unit occurs during a service of length $\tau$" depends both on the service requirement probability density function $dF(\tau)$ and on the fraction

$$ \text{service requirement/mean service requirement} = \frac{\tau}{E(\tau)}, $$

then

$$ \bar{\tau} = \int_{0}^{\infty} \frac{1}{2} \tau \frac{\tau}{E(\tau)} dF(\tau) = \frac{1}{2E(\tau)} \int_{0}^{\infty} \tau^2 dF(\tau), $$

$$ \bar{\tau} = \frac{1}{2} \frac{E(\tau^2)}{E(\tau)} . $$
From the lemma we get

$$
\bar{q} = \frac{E(t^2)}{2E(t)},
$$

where E(t²) is the second moment of F(τ) given by equation (3). Then, since

$$
E(t^2) = \frac{2}{\mu^2} (1 - \delta(\mu q + 1)),
$$

we have

$$
\bar{q} = \frac{1}{\mu} \frac{1 - \delta (1 + \mu q)}{1 - \delta}
$$

Evaluation of π<sub>cq</sub>.

We have

$$
\begin{align*}
\pi_{cq} &= \text{Pr} \left( \text{the tagged unit arrives during a complete quantum} \right) . \\
&= \text{Pr} \left( \text{at least } r-1 \text{ new units arrive during this quantum} \right) .
\end{align*}
$$

We define $\sigma$ to be the probability that the tagged unit arrives
during a complete quantum, i.e. such that the program being processed
does not complete its service at the end of the quantum. Then

$$
\sigma = \lambda_{cq} \cdot q,
$$

where $\lambda_{cq}$ is the arrival rate of complete quanta. By definition of $\lambda_{cq}$,
we have

$$
\lambda_{cq} = \lambda_q \delta = \lambda \frac{\delta}{1-\delta}
$$

and

$$
\pi_{cq} = \lambda \frac{\delta}{1-\delta} q \gamma_{r-1} .
$$

Therefore

$$
(14) \quad z_o = \frac{\lambda s}{1-\xi} \left( \frac{s}{2} + \frac{1}{\mu} (1-\xi) \right) + \frac{\lambda}{\mu^2} \frac{1-\delta(\mu q + 1)}{1-\delta} + \frac{\lambda \delta}{1-\delta} q \gamma_{r-1} \left( \frac{g}{2} + \frac{1}{\mu} (1-\xi) \right).
$$
Now if $\eta$ is the probability that the program in service at arrival
will return for more service after its current pass, then the number of
programs behind the tagged unit on its first pass (and therefore ahead of
it on its second pass) due to this program is :

$$
m_i' = \eta + \lambda z_o .
$$

In considering η, note that the tagged unit arrives during a swap, or
during a complete quantum with no additional quantum. Using the memoryless
property, we have :

$$
\eta = \pi_s \xi + \lambda_q \delta(1 - \gamma_{r-1})q
$$

$$
\eta = \lambda \left( s \frac{\xi}{1-\xi} + \frac{\delta}{1-\delta} (1-\gamma_{r-1})q \right) = \lambda \frac{\xi}{1-\xi} q
$$

Since these programs are behind the tagged unit, they will receive at
most n-1 passes, before the tagged unit completes its service requirement,
so

$$
E_{k,n}(T1) = z_o + \sum_{i=1}^{n-1} m_i'(\tau_1+s),
$$

but

$$
m_i' = \alpha m_{i-1}' = \alpha^{i-1} m_i' ,
$$

thus

$$
E_{k,n}(T1) = z_o + m_i'(\tau_1 + s) \frac{1-\alpha^{n-1}}{1-\alpha},
$$

and, noting that $\tau_1+s = \rho(1-\xi)/\lambda$ ,

$$
\omega_n(k) = E_{k,n}(T1) + E_{k,n}(T2)
$$

$$
\begin{equation}
\begin{aligned}
&= z_o + m_1' \frac{\rho}{\lambda} (1-\xi) \frac{1-\alpha^{n-1}}{1-\alpha} \\
&\quad + \frac{\rho(1-\xi)}{\lambda(1-\alpha)} \left[ (k-n)N_r + n\lambda Q + (m_1 - \frac{\frac{k}{n}-1}{1-\alpha} N_r + \lambda Q) (1-\alpha^n) \right].
\end{aligned}
\tag{15}
\end{equation}
$$
Multiplying (A14) by $p_n(k)$ given by (A1), substituting into (A2), and
carrying out the summation yields:

$$ (..16) \qquad W_r(k) = z_o + \frac{\rho}{\lambda(1-\rho)} (m_1' + m_1 + \frac{N_r - \lambda Q}{1-\alpha} - m_1' + \alpha(m_1 + \frac{N_r - \lambda Q}{1-\alpha})) (\gamma_r + \alpha(1-\gamma_r))^{k-1} \\ \qquad - \frac{1-\gamma_r + \alpha(1-\gamma_r)^k}{(1-\alpha)(1-\gamma_r)} N_r + N_r \gamma_r (k-1) + \lambda Q (\gamma_r + \alpha(1-\gamma_r)). $$

It remains to derive an expression for $m_1$. From Little's well-known formula
we get

$$ m_1 = \lambda E(W_r(k)), $$

where

$$ E(W_r(k)) = \sum_{k=1}^{\infty} W_r(k) \pi(k), $$

if we define $\pi(k)$ as the probability that a program will be processed in $k$ quanta. Then

$$ \pi(k) = \int_{(k-1)q}^{kq} \mu e^{-\mu t} dt = \delta^{k-1}(1-\delta). $$

We obtain

$$ E(W_r(k)) = z_o + \frac{\rho}{\lambda(1-\rho)} \left\{ \frac{m_1' \delta(1-\gamma_r)(1-\alpha) + m_1(1-\alpha)(1-\delta\gamma_r)}{1-\delta(\gamma_r+\alpha(1-\gamma_r))} + \frac{(1-\alpha)(1-\gamma_r)}{1-\delta} \frac{\delta^2 N_r \gamma_r + \lambda \delta Q (1-\delta\gamma_r)}{1-\delta(\gamma_r+\alpha(1-\gamma_r))} \right\}. $$

Setting $E(W_r(k)) = m_1/\lambda$, and solving for $m_1$, we have:

$$ m_1 = \frac{\lambda}{1-\rho} z_o + \frac{\rho}{1-\rho} \frac{\xi}{1+\xi} \left( \eta + \frac{\lambda \delta (1-\gamma_r)^q + \lambda Q (1-\gamma_r) \delta}{1-\delta} \right), $$

which completes the proof.
For $r=1$, we obtain the MQ model of Heacox and Purdom and when $r$ approaches infinity we have their single-quantum (SQ) model since in this case

$$ \lim_{r \to \infty} \gamma_r = 0 $$

and the probability that a program obtains an additional quantum becomes zero. These results may simply be proved after straightforward, but rather lengthy computation, which is left to the reader.

## Acknowledgement

We wish to thank Mademoiselle GRANGEARD for her excellent typing.
REFERENCES

(1) COFFMAN, E.G., Jr, and KLEINROCK,L. Feedback queuing models for time-sharing computer systems.
J. ACM 17, 1 (Jan 1970), 131-145.

(2) COFFMAN, E.G. Jr. Analysis of two time-sharing algorithms designed for limited swapping.
J. ACM 15, 3 (July 1968), 341-353.

(3) HEACOX, H.C., Jr. and PURDOM, P.W., Jr. Analysis of two time-sharing queuing models.
J. ACM 19, 1 (January 1972), 70-91.