<figure><img src="image_1.png" /></figure>

HAL
open science

# On the sharing of a processor among many job classes

Guy Fayolle, Roudolf Iasnogorodski, Israel Mitrani

► To cite this version:

Guy Fayolle, Roudolf Iasnogorodski, Israel Mitrani. On the sharing of a processor among many job classes. [Research Report] IRIA-RR-275, IRIA. 1978, pp.24. hal-04716532

HAL Id: hal-04716532

https://inria.hal.science/hal-04716532v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

ARCHIVES

ON THE SHARING
OF A PROCESSOR
AMONG MANY JOB CLASSES

G. FAYOLLE
R. IASNOGORODSKY
I. MITRANI

Rapport de Recherche N° 275

Janvier 1978
ON THE SHARING OF A PROCESSOR AMONG
MANY JOB CLASSES

G. Fayolle, R. Iasnogorodski*, I. Mitrani**

Résumé :

Nous considérons un système à un serveur dont la puissance est partagée entre M classes de clients. La politique d'ordonnancement est du type «discriminatory processor-sharing». Plus précisément, si il y a $N_j$ clients de classe j ($j = 1, 2, ..., M$) à l'état stationnaire, un client de classe k reçoit une fraction $g_k / (\sum_{j=1}^M g_j N_j)$ de la puissance totale du serveur.

On démontre que les analyses de ce système faites par certains auteurs sont incorrectes. On donne pour chaque classe k l'expression $W_k(t)$ du temps moyen d'attente sachant que la durée du service demandé est t. Les distributions des temps de service sont générales.

Abstract :

A single server Processor-Sharing system with M job classes is analysed in the steady state. The scheduling strategy considered divides the total processor capacity in unequal fractions among the different job classes. More precisely, if there are $N_j$ jobs of class j in the system ($j = 1, 2, ..., M$), each class k job receives a fraction $g_k / (\sum_{j=1}^M g_j N_j)$ of the processor capacity.

Earlier analyses of this system are shown to be incorrect and new expressions for the conditional
expected response times $W_k(t)$ of class k jobs with required service time t are obtained (for general
required service time distributions). These yield the asymptotic behaviour of $W_k(t)$ as $t \to \infty$ and
rather simple formulae in the exponential case. The unconditional average response times are also
obtained.

<footnote>* University of Orlans, France.</footnote>

<footnote>** On leave of absence from the University of Newcastle-upon-Tyne (England).</footnote>
# 1. Introduction.

Processor-Sharing is the name usually given to job scheduling strategies whose chief characteristic is that several (perhaps all) of the jobs present at a service center may receive service simultaneously, with individual service rates depending on the system state. Strategies of this type have been the object of considerable interest ever since the advent, more than a decade ago, of time-shared computer systems.

The simplest and best known [1,4,8,11] processor-sharing discipline is the one which divides the total processing capacity equally among the jobs in the system. Thus, if the processor is capable of executing C instructions per unit time and there are N jobs present, they all proceed in parallel at the rate of C/N instructions per unit time. A recently introduced generalisation [2] allows the rate at which all jobs are served to be an arbitrary positive function of N. In both cases the jobs may belong to different classes, with different (Poisson) arrival streams and (general) required service times distributions. We use the term "egalitarian" when referring to this type of processor-sharing.

Egalitarian processor-sharing disciplines have some interesting and very useful properties. For example, the expected response time $W_k(t)$ of a class k job with required service time t, does not depend on the second and higher moments of the required service times distributions; the departure process for each class is Poisson; queuing networks with egalitarian processor-sharing at their nodes have product form solutions; etc. However, it is impossible, using such strategies, to give preferential treatment to one or more job classes at the expense of others. For that, the rate of service for each class k job needs to depend, not on the total number N of jobs present, but on the numbers $N_j$ of class j jobs present. Processor-sharing strategies which use rules of this type can be called "discriminatory".

A discriminatory processor-sharing strategy for a single-processor system with M job classes was introduced by Kleinrock [4]. The division of the processor capacity is controlled by a vector of "weights" $\{w_k>0; k=1,2,...,M\}$:
if the processor is capable of executing C instructions per unit time and there are $N_j$ jobs of class j present ($j=1,2,...,M$) then all jobs proceed in parallel, each class k job being served at rate

$$ (1.1) \qquad r_k(N_1, N_2, \dots, N_M) = \frac{Cg_k}{\left(\sum_{j=1}^{M} s_j \bar{W}_j\right)}, \quad k=1,2,\dots,M $$

instructions per unit time.

The importance of this scheduling strategy lies in the fact that by varying the parameters $g_k$ one can control the average response times for the M job classes over a very wide domain. Indeed, for the case of exponentially distributed required service times it was shown (Mitrani and Hine, [6]) that any vector of average response times ($\bar{W}_1, \bar{W}_2, \dots, \bar{W}_M$) that can be achieved by any scheduling strategy, can also be achieved by Kleinrock's discriminatory processor-sharing strategy with suitably chosen $s_j$'s. Nor is the study of that strategy (which will be referred to as KDPS in future) a purely academic exercise. One can implement a Round - Robin discipline which gives $g_k$ quanta of service to class k jobs every time they came to the processor; it will behave approximately like KDPS when the quantum size is small.

There exist two analyses of KDPS : one by Kleinrock [4] and one by O'Donovan [10]. Both obtain, under different assumptions and by different methods, the following expression for the steady-state expected response time of a class k job whose required service time is t :

$$ (1.2) \qquad W_k(t) = t \left[ 1 + \frac{1}{g_k(1-\rho)} \sum_{j=1}^{M} s_j \rho_j \right] \quad k=1,2,\dots,M $$
where $\rho_j$ is the traffic intensity for class j and $\rho = \sum_{j=1}^{M} \rho_j$.

This expression is incorrect. The easiest way to see that is to let $g_k \to \infty$, keeping $s_j$ ($j \neq k$) finite. This should, according to (1.1), result in class k jobs sharing the processor among themselves only, whenever they are present. Thus the egalitarian processor-sharing formula should apply to class k :
$$W_k(t) = t/(1-\rho_k)$$

On the other hand, (1.2) gives, when $g_k \to \infty$,

$$W_k(t) = t(1-\rho+\rho_k)/(1-\rho)$$

and the two do not coincide in general.

We present another solution. First, following O'Donovan's approach, a system of integro-differential equations for $W_k(t)$, $i=1,2,...,M$ is derived in section 2. The correct form of the equations was, in fact, found by O'Donovan after the error in the original version was communicated to him [7]. The system is then solved, for general distributions of the required service times, by the method of Wiener - Hopf (in the appendix). The general solution is discussed in section 3 and is used to obtain the asymptotic behaviour of $W_k(t)$ as $t \to \infty$. The latter turns out to have a very simple form : $W_k(t) \sim t/(1-\rho)$.

In the case of exponentially distributed required service times we can write closed-form expressions for $W_k(t)$; this is done in section 4. Also for that case, the unconditional steady-state average response times $W_k(k=1,2,...,M)$ can be obtained directly by solving a system of linear equations.

## 2. Derivation of the integro-differential equations.

Jobs of class k arrive in a Poisson stream with rate $\lambda_k$ and have required service times distribution $F_k(x)$ with mean $1/\mu_k$, $k=1,2,...,M$. When the state of the system is $\underline{M} = (N_1,N_2,...,N_M)$ the processor is shared according to the weights $g_1,g_2,...,g_M$ and each class k job receives service at rate $r_k(\underline{N})$ given by (1.1). We can assume without loss of generality that the speed C of the processor is 1.

Steady-state exists when the system is non-saturated, i.e. when $\rho_1 + \rho_2 + ... + \rho_M = \rho < 1$, where $\rho_k = \lambda_k/\mu_k$, $k=1,2,...,M$. Under that condition, we are interested in the average response time (time in the system) $W_k(t)$ of a class k job whose required service time is t.
We begin by remarking that $W_k(t)$ can also be interpreted as the average time necessary for a class k job whose required service time is greater than t to attain service t. Hence $\Delta W_k(t) = W_k(t+\Delta t) - W_k(t)$ is the expected time for a class k job whose required service time is greater than $t+\Delta t$ to increase its attained service from t to $t+\Delta t$.

Let us tag a class k job with required service time greater than t. If, when the tagged job attains service t, there are $N_j$ class j jobs in the system, $j=1,2,...,M$ (excluding the tagged job), then its instantaneous service rate will be $r_k(N_1,...,N_k+1,...,N_M)$ and therefore it will increase its attained service time by a small amount $\Delta t$ in time

$$ \Delta t/r_k(N_1, \dots, N_k+1, \dots, N_M) $$

Substituting (1.1), taking expectations, dividing by $\Delta t$ and letting $\Delta t \to 0$ yields

$$ (2.1) \qquad W_k'(t) = 1 + \sum_{j=1}^{M} \frac{g_j}{g_k} \mathbb{E}[N_j] ; \quad k = 1, 2, \dots, M $$

It remains to determine $\mathbb{E}[N_j]$, which we shall denote by $n_j$, $j=1,2,...,M$. The expectations $n_j$ can be written as

$$ (2.2) \qquad n_j = n_{j,1} + n_{j,2} $$

where $n_{j,1}$ is the expected number of class j jobs which were in the system when the tagged job arrived and are still there when the tagged job attains service t; $n_{j,2}$ is the expected number of class j jobs which arrived after the tagged job and are still in the system when it attains service t; $j=1,2,...,M$.

Now, while the tagged job receives $g_k$ units of service, a class j job who is together with it in the system receives $g_j$ units of service. Therefore, while the tagged job attains service t a class j job attains service $(g_j t)/g_k$. Thus a class j job who was in the system at the arrival of the tagged job and had attained then service u, is still in the system when the tagged job attains service t with probability

$$ (2.3) \qquad \left[1 - F_j(u + (g_j t/\bar{z}_k))\right] / \left[1 - F_j(u)\right] $$
On the other hand, the expected number of class j jobs which have attained service u at a random point in the steady-state (and the arrival epoch of the tagged job is a random point) is given (see [5,9]) by

$$ (2.4) \qquad \lambda_j[1 - F_j(u)]W_j'(u)du $$

Multiplying (2.3) and (2.4) and integrating over all u yields the first term in the right-hand side of (2.2) :

$$ (2.5) \qquad n_{j,1} = \lambda_j \int_0^\infty W_j'(u)[1 - F_j(u + (g_j t/g_k))] du $$

To find $n_{j,2}$ we remember that the expected time taken by the tagged job to increase its attained service from u to u + du is $dW_k(u)$; an average of $\lambda_j$ d $W_k(u)$ class j jobs arrive during that time. The probability that one of those arrivals is still in the system when the tagged job attains service t, is equal to $[1 - F_j(g_j(t-u)/g_k)]$, by an argument similar to the one preceding (2.3). Multiplying number by probability and integrating over u $\in (0,t)$ gives

$$ (2.6) \qquad n_{j,2} = \lambda_j \int_0^t W_k'(u)[1 - F_j(g_j(t-u)/g_k)] du $$

Finally, (2.1), (2.2), (2.5) and (2.6) yield the following system of equations for the unknown functions :

$$ (2.7) \qquad W_k'(t) = 1 + \sum_{j=1}^{M} \int_{0}^{\infty} \left[ \lambda_j g_j \frac{W_j'(u)}{g_k} \right] \left[ 1 - F_j \left( u + \left( g_j t / g_k \right) \right) \right] du \\ \qquad \qquad + \int_{0}^{t} \left\{ W_k'(u) \sum_{j=1}^{M} \lambda_j g_j \frac{[1 - F_j(g_j(t-u)/g_k)]}{g_k} \right\} du; \\ \qquad k = 1, 2, \dots, M. $$

To these, we must add the initial conditions $W_k(0) = 0, k = 1,2,\dots,M$.

### 3. General solution.

The system (2.7) is solved in the appendix. To state the result, we need some additional notations :
Define

$$ \Psi_j(x) = \lambda_j \mathcal{E}_j[1 - F_j(g_j x)] $$

$$ \Psi(x) = \sum_{j=1}^{M} \Psi_j(x) $$

$$ \xi(x) = \sum_{j=1}^{M} \mathcal{E}_j \Psi_j(x) $$

The Laplace transform of any function $f(x)$ will be denoted by $\mathcal{L}^*(s)$.

Define further

$$ \mathcal{L}(s) = \frac{\xi^*(is) - \xi^*(-is)}{[1 - \mathcal{L}^*(is)][1 - \mathcal{L}^*(-is)]} $$

where $i$ is the imaginary unit.

Now our result can be summarised as follows :

### Theorem.

The system (2.7) has a unique solution when $\rho < 1$. That solution is given by

$$ (3.1) \qquad W_k^*(t) = a(\frac{t}{\xi_k}) + \frac{1}{\xi_k} b(\frac{t}{\xi_k}); \quad k=1,2,\dots,M $$

where the Laplace transform of $a(x)$ is

$$ (3.2) \qquad a^*(s) = \frac{1}{s[1 - \mathcal{L}^*(s)]} $$

and the derivative of $b(x)$ is equal to

$$ (3.3) \qquad b'(x) = -\frac{i}{\pi} \int_{0}^{\infty} \theta(s) \sin(sx) ds $$

Furthermore, $\int_{0}^{\infty} b(x) dx$ exists when the second moments of the required service times exist.

From (3.1), and remembering that $W_k(0) = 0$, we immediately obtain

$$ (3.4) \qquad W_k(t) = \xi_k \int_0^t a(x) dx + \int_0^t b(x) dx; \quad k=1,2,\dots,M. $$
This form of the general solution is not very illuminating but there are, nevertheless, some conclusions that can be drawn from it :

**Remark 1.**

In general, on the entire distributions $F_j(x)$, $j=1,2,...,M$ and not only on their first moments. This is one major difference between the egalitarian and the discriminatory processor-sharing disciplines. The two coincide, of course, when $g_k = g$, $k=1,2,...,M$. Then our solution becomes $W_k(t) = t/(1-\rho)$.

**Remark 2.**

Whatever the distributions $F_j(x)$, $j=1,2,...,M$, provided that the second moments exist, the asymptotic behaviour of $W_k(t)$ as $t \to \infty$ is always

$$W_k(t) \sim t/(1-\rho)$$

To prove this, we note that

$$\lim_{s \to 0} s a^*(s) = \frac{1}{1 - \Psi^*(0)} = \frac{1}{1 - \rho}$$

as can be verified directly. This implies, according to a Tauberian theorem, that $\lim_{x \to \infty} a(x) = 1/(1-\rho)$. Dividing both sides of (3.4) by t and letting $t \to \infty$ we get, since $\int_0^\infty b(x)dx$ is finite,

$$\lim_{t \to \infty} \frac{1}{t} W_k(t) = \frac{1}{1-\rho} \quad , \text{q.e.d.}$$

**4. Exponentially distributed required service times.**

The inversion of the Laplace and Fourier transforms involved in the general solution can be done explicitly when the required service times are distributed exponentially :

$F_j(x) = 1 - e^{-\mu_j x}$; $j=1,2,...,M$. The definitions of section 3 now yield
$$
(4.1) \qquad \Psi^*(s) = \sum_{j=1}^{M} \frac{\lambda_j g_j}{\mu_j g_j^+ s}
$$

$$
(4.2) \qquad \xi^*(s) = \sum_{j=1}^{M} \frac{\lambda_j g_j^2}{\mu_j g_j^+ s}
$$

$$
(4.3) \qquad \theta(s) = \frac{\sum_{j=1}^{M} \frac{\lambda_j g_j^2}{\mu_j g_j^+ is} - \sum_{j=1}^{M} \frac{\lambda_j g_j^2}{\mu_j g_j^- is}}{\left[ 1 - \sum_{j=1}^{M} \frac{\lambda_j g_j}{\mu_j g_j^+ is} \right] \left[ 1 - \sum_{j=1}^{M} \frac{\lambda_j g_j}{\mu_j g_j^- is} \right]}
$$

In order to determine the first component of $W'_k(t)$, given by (3.2),
we need to investigate the roots of the equation

$$
(4.4) \qquad 1 - \Psi^*(s) = 1 - \sum_{j=1}^{M} \frac{\lambda_j g_j}{\mu_j g_j^+ s} = 0.
$$

Lemma 1.

All roots of (4.4) are real, distinct and negative. Their number, m,
is equal to the number of distinct elements in the vector (g<sub>1</sub>μ<sub>1</sub>, g<sub>2</sub>μ<sub>2</sub>, ..., g<sub>M</sub>μ<sub>M</sub>).

Proof.

Suppose that there are m distinct elements in the above vector and
that the indexing is such that

$$
g_1 \mu_1 < g_2 \mu_2 < \dots < g_m \mu_m, \quad m \le M.
$$

Since the left-hand side of (4.4) is a rational function of s and the degree
of the numerator is m, there are exactly m roots. On the other hand, we note
that

$$
\Psi^*(0) = p < 1; \quad \Psi^*(-\xi_j \mu_j + 0) = \infty;
$$

$$
\Psi^*(-g_j \mu_j - 0) = - \infty; \quad j=1, 2, \dots, m.
$$

Hence, there is at least one real root of the equation in each of the inter-
vals (0,-g₁μ₁), (-g₁μ₁,-g₂μ₂),...,(-g_m-1μ_m-1,-g_mμ_m). Therefore, there is.
exactly one root in each of those intervals and there are no other rocts,
q.e.d.
Denote the roots of (4.4) by $-\alpha_j$ ($\alpha_j > 0$), $j=1,2,...,m$. (3.2) can be rewritten as

$$a^*(s) = \frac{\prod_{j=1}^{m} (g_j \mu_j + s)}{s \prod_{j=1}^{m} (s + \alpha_j)}$$

and can further be decomposed into elementary fractions thus

$$(4.5) \qquad a^*(s) = \frac{c_0}{s} + \sum_{j=1}^{m} \frac{c_j}{s + \alpha_j}$$

where

$$c_o = sa^*(s) \bigg|_{s=0} = \frac{1}{1-\psi^*(0)} = \frac{1}{1-\rho}$$

and

$$(4.6) \qquad c_j = (s+\alpha_j)a^*(s) \bigg|_{s=-\alpha_j} = \frac{\left[ \prod_{k=1}^{m} (g_k \mu_k - \alpha_j) \right]}{-\alpha_j \prod_{k \neq j}^{m} (\alpha_k - \alpha_j)}; \\ j=1,2,...,m$$

Inverting the Laplace transform (4.5) is immediate :

$$(4.7) \qquad a(x) = \frac{1}{1-\rho} + \sum_{j=1}^{m} c_j e^{-\alpha_j x}$$

We now turn our attention to the expression (3.3), with $\theta(s)$ being given by (4.3). After some arithmetic, and using again lemma 1 and the roots $-\alpha_j$ ($j=1,2,...,m$), we can rewrite (4.3) as

$$\theta(s) = \frac{-2is \left[ \sum_{j=1}^{M} \frac{\lambda_j g_j^2}{(\mu_j^2 g_j^2 + s^2)} \right] \left[ \prod_{j=1}^{m} (\mu_j^2 g_j^2 + s^2) \right]}{\prod_{j=1}^{m} (\alpha_j^2 + s^2)}$$

and further decompose it into elementary fractions thus :

$$(4.8) \qquad \theta(s) = -2is \sum_{j=1}^{m} \frac{d_j}{\alpha_j^2 + s}$$

where
$$ (4.9) \quad d_j = (s^2 + \alpha_j^2) \theta(s) \Big|_{s^2 = -\alpha_j^2} = \frac{\left[ \sum_{k=1}^{M} \frac{\lambda_k g_k^2}{(\mu_k g_k^2 - \alpha_j^2)} \right] \left[ \prod_{k=1}^{m} (\mu_k^2 g_k^2 - \alpha_j^2) \right]}{\prod_{k \neq j}^{m} (\alpha_k^2 - \alpha_j^2)} $$

Substituting (4.8) into (3.3) and using the identity (see [3], p. 406, formula 3.723)

$$ \int_0^\infty \frac{x \sin \gamma x}{\beta^2 + x^2} dx = \frac{\pi}{2} e^{-\beta \gamma} $$

we obtain

$$ b'(x) = - \sum_{j=1}^{m} d_j e^{-\alpha_j x} $$

and, since $b(\infty) = 0$,

$$ (4.10) \qquad b(x) = \sum_{j=1}^{m} \frac{d_j}{\alpha_j} e^{-\alpha_j x} $$

Now, (3.4), (4.7) and (4.10) yield the following result :

### Lemma 2.

In the case of exponentially distributed required service times, the conditional average response time of a class k job with required service time t is equal to

$$ (4.11) \qquad W_k(t) = \frac{t}{1-\rho} + \sum_{j=1}^{m} \frac{g_k c_j \alpha_j + d_j}{\alpha_j^2} [1 - e^{-\frac{\alpha_j t}{g_k c_j}}]; \quad k=1,2,\dots,M $$

where $-\alpha_j$ ($j=1,2,\dots,m$) are the m distinct roots of equation (4.4) and $c_j$ and $d_j$, $j=1,2,\dots,m$ are given by (4.6) and (4.9) respectively.

Thus $W_k(t)$ has the usual linear component $t/(1-\rho)$ plus a correction which depends on k and on the system parameters (it may be positive, negative or null) and tends negative exponentially to a constant when $t \to \infty$.

We should point out that the methods of this section can be employed with other distributions of the required service times, e.g. hyper-exponential, Erlang or distributions with rational Laplace transforms. In those
cases, multiple roots of equation (4.4) and the corresponding decomposition of $a^*(s)$ and $\theta(s)$ into elementary fractions may give rise to terms of the type $t e^{\frac{n_j}{\alpha_j}g_k} t$ in $W_k(t)$. The formulae thus obtained become rapidly very complex.

Finally, let us turn our attention to the unconditional average response times given in the exponential case by

$$W_k = \int_0^\infty W_k(t) \mu_k e^{-\mu_k t} dt; \quad k=1,2,\dots,M.$$

Clearly, these can be obtained from (4.11) without too much difficulty. However, if one is interested only in the unconditional averages and does not wish to compute the roots $-\alpha_j$ and the constants $c_j$ and $d_j$ ($j=1,2,\dots,n$) one can determine $W_k$ ($k=1,2,\dots,M$) directly by solving a system of linear equations:

### Lemma 3.

In the case of exponentially distributed required service times, the unconditional average response times satisfy the following system of equations:

$$ (4.12) \qquad W_k \left[ 1 - \sum_{j=1}^{M} \frac{\lambda_j g_j}{\mu_j g_j^+ + \mu_k g_k^-} \right] - \sum_{j=1}^{M} \frac{\lambda_j g_j^+ W_j}{\mu_j g_j^+ + \mu_k g_k^-} = \frac{1}{\mu_k}; \\ k = 1,2,\dots,M. $$

### Proof.

(4.12) is derived in a straightforward fashion from the original system (2.7) after substituting $F_j(x) = 1 - e^{-\mu_j x}$, multiplying both sides by $e^{-\mu_k t}$, integrating over $t \in (0,\infty)$ and using the fact that

$$ \int_0^\infty e^{-\mu_k t} W_k'(t) dt = \int_0^\infty \mu_k e^{-\mu_k t} W_k(t) dt = W_k; \\ k = 1,2,\dots,M. $$
The details of these manipulations will be omitted.

We have not been able to find a closed form solution to (4.12) for arbitrary parameter values. When M=2 we have

$$ (4.13) \qquad W_1 = \frac{1}{\mu_1(1-\rho)} \left[ 1 + \frac{\mu_1 \rho_2 (g_2 - g_1)}{D} \right] \\ W_2 = \frac{1}{\mu_2(1-\rho)} \left[ 1 + \frac{\mu_2 \rho_1 (g_1 - g_2)}{D} \right] $$ 
where $D = \mu_1 g_1 (1-\rho_1) + \mu_2 g_2 (1-\rho_2)$.

### Remark.

The system (4.12) can be used to solve the synthesis problem : "Given the arrival and service parameters $\lambda_j$ and $\mu_j$ ($j=1,2,...,M$) and a desired vector of average response times ($W_1, W_2,...,W_M$), what values of $g_1, g_2, ..., g_M$ should be used in the KOPS strategy in order to achieve that vector ?". The dimension of that problem is M-1 because (4.12) is homogeneous with respect to the $g_j$'s and one of them can be fixed arbitrarily, say $g_1 = 1$. Even so, the non-linearity of the equations make it a much more difficult problem and one would probably have to employ a numerical iteration procedure.

### Conclusion.

We have presented an analysis of a very versatile (in the sense of being able to achieve a wide range of different performance vectors) processor-sharing strategy. Expressions for the conditional average response times for the various job classes were obtained under quite general assumptions.

It is now apparent that the versatility which discriminatory processor sharing brings is paid for by giving up the "nice" properties of egalitarian processor sharing. We mentioned already the dependence of the average response times on the entire service times distributions. There is also indirect
evidence that the departure process for each job class is no longer Poisson, in general. Indeed, if that was true for the KDPS strategy for all $g_j$'s, then it would also be true for the preemptive priority disciplines (since they are limiting cases). But the departure process of a lower priority class under a preemptive priority discipline is not, to our knowledge, Poisson.

Nothing is yet known about the joint or marginal distributions of queue sizes, or about the second and higher moments of the response times, or about the behaviour of the KDPS strategy when used in queueing networks. These are interesting open problems which, we may hope, will receive the attention they deserve and will be resolved in the near future.
APPENDIX

Here we prove the theorem of section 3. First, we bring the system (2.7) into a slightly more manageable form by replacing the unknown functions $\Pi_k'(t)$ with the functions

$$V_k(t) = g_k \Pi_k'(g_k t), \quad k=1,2,\dots,M$$

Setting $t \leftarrow g_k t$ in (2.7), multiplying both sides by $g_k$, making the changes of variables $u \leftarrow g_j u$ in the integrals in the first term and $u \leftarrow \xi_k u$ in the integral in the second term, we can rewrite (2.7) as

$$(A.1) \qquad V_k(t) = g_k + \sum_{j=1}^{M} \int_{0}^{\infty} V_j(u) \Psi_j(t+u)du + \int_{0}^{t} V_k(u)\Psi(t-u)du, \\ k=1,2,\dots,M$$

where $\Psi_j(x)$, $j=1,2,\dots,M$ and $\Psi(x)$ are defined in section 3. We note that

$$\int_{0}^{\infty} \Psi(x)dx = \sum_{j=1}^{M} (\lambda_j / \mu_j) = \rho$$

Consider now the integral equation

$$(A.2) \qquad a(t) = 1 + \int_{0}^{t} a(u) \Psi(t-u)du$$

This is a renewal equation which has a unique solution when $\rho < 1$. Multiplying (A.2) by $g_k$ and subtracting it from (A.1) we find that the functions

$$b_k(x) = V_k(x) - g_k a(x), \quad k=1,2,\dots,M$$

satisfy the integral equations

$$(A.3) \qquad b_k(t) = \sum_{j=1}^{M} \int_{0}^{\infty} [b_j(u) + \xi_j a(u)] \Psi_j(t+u)du + \int_{0}^{t} b_k(u)\Psi(t-u)du, \\ k=1,2,\dots,M$$

But these equations do not depend in any way on $k$; hence

$$b_k(x) = b(x), \quad k=1,2,\dots,M$$
and $b(x)$ satisfies the equation (A.3) which can be rewritten as

$$ (A.4) \qquad b(t) = c(t) + \int_{0}^{\infty} b(u) \Psi(t+u) du + \int_{0}^{t} b(u) \Psi(t-u) du, \\ t \ge 0 $$

where

$$ (A.5) \qquad c(t) = \sum_{j=1}^{M} g_j \int_{0}^{\infty} a(u) \Psi_j(t+u) du = \int_{0}^{\infty} a(u) \xi(t+u) du $$

$(\xi(x)$ was defined in section 3).

We have thus proved that if the system (A.1), which is equivalent
to (2.7), has a solution, then the solution is of the form

$$ (A.6) \qquad V_k(x) = g_k a(x) + b(x) $$

or, equivalently (and this establishes (3.1)),

$$ (A.7) \qquad W'_{k}(x) = a\left(\frac{x}{g_k}\right) + \frac{1}{g_k} b\left(\frac{x}{g_k}\right) $$

where $a(x)$ is the unique solution of (A.2) and $b(x)$ satisfies (A.4).
Conversely, any solution $b(x)$ of (A.4) can be combined with $a(x)$ as indicated by (A.6) to form a solution of (A.1). Hence, the question of existence and uniqueness of the solution of (2.7) reduces to that of existence and uniqueness of the solution of (A.4).

In the remainder of this appendix we shall be using Laplace and Fourier - Stieltjes transforms. For any function $f(x)$, its Laplace transform $f^*(s)$ is defined as

$$ f^*(s) = \int_{0}^{\infty} e^{-sx} f(x) dx $$

for all complex $s$ such that $\text{Re}(s) \ge 0$. The Fourier - Stieltjes transform $\hat{f}(s)$ is defined as

$$ \hat{f}(s) = \int_{-\infty}^{\infty} e^{isx} df(x) $$

for all real $s$.
Taking Laplace transforms in (A.2) yields, since the integral in the right-hand side is a convolution,

$$a^*(s) = \frac{1}{s} + a^*(s) \Psi^*(s)$$

or

$$(A.8) \qquad a^*(s) = \frac{1}{s[1 - \Psi^*(s)]}$$

thus establishing (3.2). To complete the proof, we have to show that (A.4) has a unique solution when $\rho < 1$, that the solution is given by (3.3) and that it is integrable when the second moments of the required service times exist. It should be mentioned that we are looking for solutions in the class $\mathcal{G}$ of functions which are integrable in absolute value with respect to $\Psi(x)$ (so that the first integral in (A.4) exists) and whose Laplace transforms exist for some $s > 0$ (i.e. they do not rise faster than exponentials).

The existence, uniqueness and integrability of the solution of (A.4) follow from the following assertions, whose proofs will be given at the end of the appendix.

**Assertion 1.**

If (A.4) has a solution in $\mathcal{G}$ then that solution is bounded.

**Assertion 2.**

There is one, and only one bounded solution of (A.4) in $\mathcal{G}$. Moreover, the solution is positive.

**Assertion 3.**

Any bounded solution of (A.4) is integrable iff the second moments of the required service times exist.

Now we proceed to determine the solution. A change of variables, $u \leftarrow t+u$ in the first integral in the right-hand side of (A.4) and $u \leftarrow t-u$ in the second integral allows us to combine them in a single integral thus

$$(A.9) \qquad b(t) = c(t) + \int_{0}^{\infty} b(|t-u|) \Psi(u) \, du, \quad t \ge 0$$
So far, all our functions have been defined for non-negative values of the arguments. By extending the definitions

$$ 
\left. 
\begin{array}{l}
\Psi_i(x) = 0, \quad i=1,2,...,M \\
a(x) = 0
\end{array}
\right\} \text{for } x < 0
$$

and by introducing a new function

$$ h(t) = \begin{cases} b(t), & t \ge 0 \\ c(t) + \int_{0}^{t} b(|t-u|) \Psi(u) \, du, & t < 0 \end{cases} $$

we can write

$$ (A.10) \qquad h(t) = c(t) + \int_{0}^{\infty} b(|t-u|) \Psi(u) \, du $$

which holds for the whole real axis.

Now we wish to take Fourier - Stieltjes transforms in (A.10). For that we need

**Assertion 4.**

The solution of (A.4), when integrable, is of bounded variation :

$$ \int_{0}^{\infty} |db(x)| < \infty $$

whose proof will also be given at the end.

We write

$$ (A.11) \qquad \hat{h}(s) = \int_{-\infty}^{\infty} e^{ist} dc(t) + \int_{-\infty}^{\infty} e^{ist} d\left[ \int_{0}^{\infty} b(|t-u|) \Psi(u) du \right] $$

The first term in the r.h.s. of (A.11) can be shown, after integrating (A.5) by parts, taking into account the step of $a(x)$ at the origin, then changing the order of integration, separating $e^{ist}$ into $e^{-isu} e^{is(t+u)}$ and changing variables $t \to t+u$, to be equal to

$$ - \int_{0^{-}}^{\infty} e^{-isu} da(u) \int_{-\infty}^{\infty} e^{ist} \zeta(t) dt = - i s a^{*}(is) \zeta^{*}(-is) = \frac{-\zeta^{*}(-is)}{1 - \Psi^{*}(is)} $$

where we have used (A.8) and the fact that $\zeta(t)=0$ for $t < 0$. The notation $0^-$ means that integration starts just to the left of the origin.
Changing the order of integration in the second term in the r.h.s. of (A.11) and separating the variables reduces it to

$$ \int_{0}^{\infty} e^{isu} \psi(u) du \int_{-\infty}^{\infty} e^{ist} db(|t|) = \psi^{*}(-is) \left[ \int_{0}^{\infty} e^{ist} db(t) - \int_{0}^{\infty} e^{-ist} db(t) \right] $$

We shall denote

$$ (A.12) \qquad \theta(s) = \int_{0}^{\infty} e^{ist} db(t) - \int_{0}^{\infty} e^{-ist} db(t) = 2i \int_{0}^{\infty} \sin(st) b'(t) dt $$

(at the points where $\Psi'(t)$ and hence $b'(t)$ exists) and

$$ (A.13) \qquad \eta(s) = \hat{h}(s) - \theta(s) = \int_{0}^{\infty} e^{-ist} db(t) + \int_{-\infty}^{0} e^{ist} dh(t) $$

With this notation, and the expressions above, (A.11) becomes

$$ \theta(s) + \eta(s) = \frac{-\xi^{*}(-is)}{1-\Psi^{*}(is)} + \Psi^{*}(-is) \theta(s) $$

or

$$ (A.14) \qquad \theta(s)[1-\Psi^{*}(is)][1-\Psi^{*}(-is)] + \eta(s)[1-\Psi^{*}(is)] = -\xi^{*}(-is) $$

Setting $s = -s$ in (A.14) and noting, from (A.12), that $\theta(-s) = -\theta(s)$, we get

$$ (A.15) \qquad -\theta(s)[1-\Psi^{*}(is)][1-\Psi^{*}(-is)] + \eta(-s)[1-\Psi^{*}(-is)] = -\xi^{*}(is) $$

(A.14) and (A.15) yield the following equation for $\eta(s)$:

$$ (A.16) \qquad \eta(s)[1-\Psi^{*}(is)] + \xi^{*}(is) = -\{\eta(-s)[1-\Psi^{*}(-is)] + \xi^{*}(-is)\} $$

Now, taking a closer look at the definitions of $\eta(s)$, $\Psi^{*}(is)$ and $\xi^{*}(is)$ we observe that the left-hand side of (A.16) is defined, analytic and bounded on the lower half-plane : $\operatorname{Im}(s) \le 0$.

Similarly, the right-hand side of (A.16) is defined, analytic and bounded on the upper half plane : $\operatorname{Im}(s) \ge 0$. The equation itself, which is valid on the real line $\operatorname{Im}(s) = 0$ shows that the two sides are analytic continuations of each other. Therefore, together they define a function which
is analytic and bounded on the whole complex plane. According to Liouville's theorem that function must be a constant. Thus

$$\eta(s)[1-\Psi^*(is)]+\xi^*(is) = -\{\eta(-s)[1-\Psi^*(-is)]+\xi^*(-is)\} = \text{const}$$

in the respective domains. Since Laplace transforms are zero at infinity, the constant must be zero. Hence

$$(A.17) \qquad \eta(s)[1-\Psi^*(is)] = -\xi^*(is), \quad \text{Im}(s) \le 0.$$

Substitution of (A.17) into (A.14) yields

$$(A.18) \qquad \theta(s) = \frac{\xi^*(is) - \xi^*(-is)}{[1-\Psi^*(is)][1-\Psi^*(-is)]}, \quad \text{real } s.$$

Finally, noting from (A.12) that $\theta(s)$ is equal to twice the imaginary part of the Fourier transform of $b'(t)$, and using a well-known inversion formula we obtain (3.3). This completes the proof of the theorem.

### Proof of Assertion 1.

Denoting the first two terms in the r.h.s. of (A.4) by $\alpha(t)$ and taking Laplace transforms we obtain

$$b^*(s) = \alpha^*(s) + b^*(s) \Psi^*(s)$$

or

$$b^*(s) = \alpha^*(s) \cdot \frac{1}{1-\Psi^*(s)} = \alpha^*(s) \beta^*(s)$$

$$\text{where } \beta^*(s) = [1-\Psi^*(s)]^{-1}.$$

This implies that $b(t)$ is a convolution

$$b(t) = \int_{0}^{t} \alpha(t-u) \beta(u) \, du$$

It is easy to see that $|\alpha(t)|$ is bounded :

$$|\alpha(t)| \le c(0) + \int_{0}^{\infty} \Psi(u) |b(u)| du = \text{const} = \alpha_{0}$$

since $c(t)$ is positive and decreasing, and $b(t) \in \mathbb{C}$.
Hence

$$|b(t)| \le \alpha_0 \int_0^t \beta(u) du < \alpha_0 \beta^*(0) = \frac{\alpha_0}{1-\rho}, \quad \text{q.e.d.}$$

### Proof of Assertion 2.

We write (A.2) in operator form :

$$b(t) = c(t) + K.b(t)$$

where

$$K.f(t) = \int_{0}^{\infty} k(t,u) f(u) du, \quad t \ge 0$$

with

$$k(t,u) = \begin{cases} \Psi(t+u) + \Psi(t-u) & \text{for } u \le t \\ \Psi(t+u) & \text{for } u > t \end{cases}$$

Any solution of the equation must satisfy

$$b(t) = \sum_{i=0}^{n} K^{i} \cdot c(t) + K^{n+1} \cdot b(t) \quad \text{for all } n \ge 0.$$

but

$$0 \le \sum_{i=0}^{n} K^{i} \cdot c(t) \le c(0) \sum_{i=0}^{n} K^{i} \cdot I(t) = c(0) \sum_{i=0}^{n} \rho^{i} \le \frac{c(0)}{1-\rho}$$

where $I(t) \equiv 1$, and

$$|K^{n+1} \cdot b(t)| \le \frac{\alpha_0}{1-\rho} \rho^{n+1}$$

from the proof of assertion 1.

It follows immediately that

$$\lim_{n \to \infty} b(t) - K^{n+1} \cdot b(t) = b(t) = \sum_{i=0}^{\infty} K^{i} \cdot c(t)$$

uniformly in t, i.e. the solution, if it exists, is unique and given by
$$\sum_{i=0}^{\infty} K^{i} \cdot c(t). \quad \text{It is, therefore, positive.}$$

On the other hand, it is readily seen that this last series is a
solution, q.e.d.
### Proof of Assertion 3.

The "if" part of the assertion is obtained by remarking that, in the notation of the proof of assertion 1 we have

$$b^*(0) = \alpha^*(0) \beta^*(0) = \frac{\alpha^*(0)}{1-\rho}$$

but

$$\alpha^*(0) \le c^*(0) + \frac{\alpha_o}{1-\rho} \int_o^\infty \int_t^\infty \Psi(u) du \, dt$$

which is finite when

$$\int_o^\infty t \Psi(t) dt < \infty$$

i.e. when the second moments of the required service times exist.

The "only if" part follows directly, (although not immediately !) by integrating (3.3) twice, obtaining

$$\int_o^t b(x) \, dx = \frac{i}{\pi} \int_o^\infty \frac{\theta(s) \sin(st) ds}{s^2}$$

and letting $t \to \infty$.

### Proof of Assertion 4.

Whenever $\Psi'(t)$ exists, we can write, by taking derivatives in (A.4)

$$b'(t) = c'(t) + \int_{0}^{\infty} \Psi'(t+u)b(u)du + \int_{0}^{t} \Psi'(t-u)b(u)du + \Psi(0)b(t).$$

Then they exist, $\Psi'(t)$ and $c'(t)$ are negative. Hence

$$\begin{aligned} |b'(t)| & \le -c'(t) - \int_0^\infty \Psi'(t+u)b(u)du - \int_0^t \Psi'(t-u)b'(u)du \\ & \quad + \Psi(0)b(t) \\ & = -b'(t) + 2\Psi(0)b(t). \end{aligned}$$

Therefore

$$\int_0^\infty |db(t)| \le b(0) + 2\Psi(0) \int_0^\infty b(t)dt < \infty, \text{ q.e.d.}$$
REFERENCES

[1] Baskett, F., Chandy, K.M., Muntz, R.R. and Palacios, F., "Open, closed and Mixed Networks of Queues with Different Classes of Customers", JACM, 22, 2, pp. 248-260, 1975.

[2] Cohen, J.W., "The Multiple Phase Service Network with Generalized Processor Sharing", Report n° 69, Dept. of Mathematics, Utrecht University, 1977.

[3] Gradshtein, I.S. and Ryzhik, I.M., "Tables of Integrals, Series and Products", Academic Press, 1965.

[4] Kleinrock, L., "Time-Shared Systems : A Theoretical Treatment", JACM, 14, pp. 242-261, 1967.

[5] Kleinrock, L. and Coffman, E.G., "Distribution of Attained Service in Time Shared Systems", J. Comp. Sci., 1, pp. 287-298, 1967.

[6] Mitrani, I and Hine, J.H., "Complete Parameterised Families of Job Scheduling Strategies", Acta Informatica, 8, pp. 61-73, 1977.

[7] Mitrani, I and O'Donovan, T.M., Private Communications.

[8] Muntz, R.R., "Poisson Departure Processes and Queueing Networks", Proc., 7th Ann. Princeton Conf. on Inf. Sci., Princeton University, pp. 435-440, 1973.

[9] O'Donovan, T.M., "Distribution of Attained and Residual Service in General Queueing Systems", Opns. Res., 22, pp. 570-575, 1974.

[10] O'Donovan, T.M., "Direct Solutions of M/G/1 Processor-Sharing Models", Opns. Res., 22, pp. 1232-1235, 1974.

[11] Sakata, M., Noguchi, S. and Oizumi, J., "Analysis of a Processor Shared Queueing Model for Time Sharing Systems", Proc. 2nd Hawaii Conf. on Sys. Sci., Honolulu, 1969.