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

Optimalité
de l'organisation séquentielle
de l'information
sur un tambour de pagination

G. Baudet, J. Boulenger
J. Ferrié

Rapport de Recherche n° 79

Septembre 1974
OPTIMALITÉ DE L'ORGANISATION SÉQUENTIELLE
DE L'INFORMATION SUR UN TAMBOUR DE PAGINATION

Gérard Baudet

Jacques Boulenger

Jean Ferrié

Résumé :

Un modèle de tambour de pagination a été développé dans [Bau 73] ;
le tambour est soumis à des demandes de transfert groupées et l'organi-
sation sur le tambour (répartition des demandes de transfert élémentai-
res composant une demande groupée) est un paramètre de ce modèle.

En utilisant comme critère la longueur moyenne des files d'attente associées aux secteurs, on démontre ici que l'organisation séquentielle est optimale.

Abstract :

A model of a paging drum was given in [Bau 73]. In this model,
transfer requests are assumed to be bulk requests, and the organization
of information on the drum (distribution of the elementary transfer
requests of a bulk request) is one of the parameters.

In the present paper, it is proved that sequential organization is
optimal according to the criterium of the mean length of the queues
associated with the sectors.
RAPPELS

L'étude du comportement d'un tambour de pagination soumis à des demandes de transfert groupées a été développée dans [Bau 73]. Ce modèle repose sur les hypothèses suivantes :

- la vitesse de rotation du tambour est constante et sa période est $T$.

- les intervalles de temps entre deux arrivées consécutives de demandes groupées au tambour constituent un processus de Poisson de paramètre $\lambda$.

- la taille des demandes groupées (nombre de requêtes simples qu'elles contiennent) suit une loi de probabilité indépendante du temps définie par $\{h_i\}_{i=0}^\infty$, où $h_i$ est la probabilité que la taille d'une demande soit $i$ ; la taille moyenne d'une demande est donc donnée par :

$$ \bar{h} = \sum_{i=0}^{\infty} i \cdot h_i \quad (1) $$

- les $N$ secteurs composant le tambour jouent des rôles symétriques.

- le tambour a atteint son état d'équilibre.

L'analyse mathématique de ce modèle a conduit, en particulier, à une expression générale de la longueur moyenne $\bar{n}$ de la file associée à un secteur :

$$ \bar{n} = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)} + \frac{\rho}{2(1-\rho)} \cdot \frac{N \cdot A_1''(1)}{\bar{h}} \quad (2) $$

où $\rho = \lambda \cdot \bar{h} \cdot T/N$ est le facteur d'utilisation du tambour, et $A_1(z)$ est la fonction génératrice de la contribution d'une demande groupée à un secteur donné.
Il a été démontré que $A_1(z)$ peut se mettre sous la forme :

$$A_1(z) = \sum_{i=0}^{\infty} h_i \cdot C_i(z) \quad (3)$$

où $C_i(z)$ est la fonction génératrice de la contribution d'une demande groupée de taille $i$ à un secteur donné. Si l'on note $c(n|i)$ la probabilité qu'une demande groupée de taille $i$ contienne $n$ requêtes simples s'adressant à un secteur donné, on a :

$$C_i(z) = \sum_{n=0}^{\infty} c(n|i) \cdot z^n, \quad i = 0, 1, 2, \dots \quad (4)$$

Ces fonctions génératrices caractérisent l'organisation de l'information sur le tambour.

Il a été démontré, en outre, en utilisant l'hypothèse de symétrie des secteurs, que :

$$C'_i(1) = \sum_{n=0}^{\infty} n \cdot c(n|i) = \frac{i}{N}, \quad i = 0, 1, 2, \dots \quad (5)$$

## THEOREME

Deux hypothèses concernant l'organisation de l'information sur le tambour ont été étudiées dans [Bau 73].

### Hypothèse Ha :

Toutes les requêtes simples d'une demande groupée sont indépendantes et ont la même probabilité d'adresser tous les secteurs du tambour. C'est par exemple le cas d'un système qui adresse le tambour au moyen d'une fonction de "hash-code".
Sous cette hypothèse, on a :

$$ \bar{n}_a = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)} + \frac{\rho}{2N\bar{h}(1-\rho)} \sum_{i=0}^{\infty} h_i (i^2 - i) \quad (6) $$

Hypothèse Hb :

Les requêtes simples d'une demande groupée adressent des secteurs consécutifs du tambour. C'est le cas dans les systèmes qui utilisent le segment comme unité de transfert.

Sous cette hypothèse les distributions de probabilité $\{c(n|i)\}_{n=0}^{\infty}$ pour $i = 0, 1, 2, ...$ sont donnés par :

$$ c(n|i) = \begin{cases} 1 - \frac{r}{N} & \text{si } n = q \\ \frac{r}{N} & \text{si } n = q + 1 \\ 0 & \text{ailleurs} \end{cases} $$ 

$i = 0, 1, 2, ... \qquad (7)$

où $r = i$ (modulo $N$) et $q = (i-r)/N$. Il en résulte :

$$ \bar{n}_b = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)} + \frac{\rho}{2N\bar{h}(1-\rho)} \cdot \sum_{i=0}^{\infty} h_i \cdot (i-r) \cdot (i+r-N) \quad (8) $$

On déduit de l'expression de $\bar{n}$ dans chacune de ces hypothèses que :

$$ \bar{n}_a - \bar{n}_b = \frac{\rho}{2N\bar{h}(1-\rho)} \cdot \sum_{i=0}^{\infty} h_i \cdot [(N-1) \cdot N \cdot q + r \cdot (r-1)] \geq 0 \quad (9) $$
L'organisation correspondant à l'hypothèse Hb est donc meilleure que celle correspondant à l'hypothèses Ha, suivant le critère de la longueur moyenne des files associées aux secteurs.

Ce résultat se généralise au cas d'une organisation quelconque de l'information sur le tambour. Pour le démontrer on utilise les lemmes suivants.

LEMME 1 : Sur l'ensemble V des valeurs de la variable

$X = \{x_n\}_{n=0}^{\infty}$ défini par les relations :

$$x_n \ge 0 \qquad n = 0, 1, 2, \dots \tag{10}$$

$$\sum_{n=0}^{\infty} x_n = 1 \tag{11}$$

et :

$$\sum_{n=0}^{\infty} n \cdot x_n = \alpha \tag{12}$$

où $\alpha$ est une constante positive, l'expression :

$$f(X) = \sum_{n=0}^{\infty} n \cdot (n-1) \cdot x_n \tag{13}$$

atteint son minimum pour la valeur de la variable X donnée par :

$$x_n = \begin{cases} 1 + q - \alpha & \text{si } n = q \\ \alpha - q & \text{si } n = q + 1 \\ 0 & \text{ailleurs} \end{cases} \tag{14}$$

où $q$ est l'entier positif défini par $\alpha - 1 < q \le \alpha$.
DEMONSTRATION : Etant donné un entier $q$ positif quelconque, soit $V_q$
l'ensemble des valeurs de la variable $X = \{x_n\}_{n=0}^\infty$ défini par les relations (11)
et (12) et la relation supplémentaire suivante :

$$x_n \ge 0 \quad n \neq q, \quad n \neq q+1 \qquad (15)$$

On peut déjà remarquer que $V \subseteq V_q$ pour tout entier $q$.

Maintenant pour chaque entier positif $k$ différent de $q$ et de $q + 1$,
définissons la fonction $\varphi_k$ par

$$X = \{x_n\}_{n=0}^\infty \underset{\sim}{\to} \varphi_k \quad Y = \{y_n\}_{n=0}^\infty, \text{où :}$$

$$y_n = \begin{cases} 0 & \text{si } n = k \\ x_q + (1+q-k)x_k & \text{si } n = q \\ x_{q+1} + (k-q)x_k & \text{si } n = q+1 \\ x_n & \text{ailleurs} \end{cases} \qquad (16)$$

On complète cette définition en posant la fonction $\varphi_k$ égale à la fonction identité pour $k = q$ et $k = q + 1$.

On vérifie facilement que cette fonction préserve les relations (11), (12), et (15). De plus, la différence :

$$\begin{aligned} & f(X) - f(\varphi_k(X)) \\ &= k \cdot (k-1) \cdot x_k + q/(q-1) \cdot x_q + (q+1) \cdot q \cdot x_{q+1} \\ &\quad - q \cdot (q-1) \cdot [x_q + (1+q-k)x_k] - (q+1) \cdot q \cdot [x_{q+1} + (k-q)x_k] \\ &= (q-k) \cdot (1+q-k) \cdot x_k \end{aligned} \qquad (17)$$

est toujours positive ou nulle pour toute valeur de $X$ dans $V_q$ (pour $k=q$ ou $k=q+1$, cette différence est évidemment identiquement nulle dans $V_q$).

<footnote>(*) Une autre démonstration, reposant sur la minimisation du lagrangien associé au problème, nous a été communiquée par M. Yvon.</footnote>
A partir d'une valeur quelconque de la variable $X$ dans $V_q$, construisons
par récurrence la suite des valeurs $Y_{-1}$, $Y_0$, $Y_1$, $Y_2$... par

$$
Y_k = \begin{cases} X & k = -1 \\ \varphi_k(Y_{k-1}) & k = 0, 1, 2, \dots \end{cases} \tag{18}
$$

Si l'on pose $Y_k = \{y_n^k\}_{n=0}^\infty$ pour $k = -1, 0, 1, 2, \dots$, on obtient
directement :

$$
y_n^k = \left\{
\begin{array}{ll}
0 & n \le k \\
\\
x_q + \sum_{p=0}^{k} (1+q-p) \cdot x_p & n = q \\
\\
x_{q+1} + \sum_{p=0}^{k} (p-q) \cdot x_p & n = q + 1 \\
\\
x_n & \text{ailleurs} \\
\\
\text{pour } k < q
\end{array}
\right.
$$
$$
\left\{
\begin{array}{ll}
y_n^{q-1} & n = 0, 1, 2, \dots \\
\text{pour } k = q \text{ ou } k = q + 1 &
\end{array}
\right.
\tag{19}
$$
$$
\left\{
\begin{array}{ll}
0 & n < q, q + 1 < n \le k \\
\\
k \sum_{p=0}^{k} (1+q-p) \cdot x_p & n = q \\
\\
k \sum_{p=0}^{k} (p-q) \cdot x_p & n = q + 1 \\
\\
x_n & \text{ailleurs} \\
\\
\text{pour } k > q + 1
\end{array}
\right.
$$
La limite de cette suite est donc donnée par :

$$
\lim_{k \to \infty} Y_k = Y = \{y_n\}_{n=0}^{\infty}, \text{ où :}
$$

$$
y_n = \begin{cases}
\sum_{p=0}^{\infty} (1+q-p) \cdot x_p & n=q \\
\sum_{p=0}^{\infty} (p-q) \cdot x_p & n=q+1 \\
0 & \text{ailleurs}
\end{cases}
\qquad (20)
$$

ce qui peut se réécrire en utilisant les relations (11) et (12) :

$$
y_n = \begin{cases}
1 + q - \alpha & n = q \\
\alpha - q & n = q + 1 \\
0 & \text{ailleurs}
\end{cases}
\qquad (21)
$$

Puisque d'une part cette limite est dans $V_q$ et est indépendante de $X$,
et que d'autre part la suite $f(X), f(Y_0), f(Y_1), \dots$ est monotone
décroissante (d'après la formule (17)) et la fonction $f$ continue, cette
fonction $f$ est minimale sur $V_q$ pour la valeur $Y$ de la variable.

La valeur Y est également dans V si l'on choisit pour q l'entier
défini par α - 1 < q ≤ α (*). Du fait que V ⊆ V_q, on déduit que f est
minimale sur V pour la valeur Y de la variable.
C.Q.F.D.

LEMME 2 : La longueur moyenne des files associées aux secteurs est minimale pour les distributions de probabilités :

$$
c(n \mid i) = \begin{cases}
1 - r/N & n = q \\
r/N & n = q + 1 \\
0 & \text{ailleurs}
\end{cases}
\qquad (22)
\\
i = 0, 1, 2, \dots
$$

où $r = i$ (modulo $N$) et $q = (i-r)/N$.

<footnote>(*) Si $\alpha$ est entier, on peut aussi choisir l'entier $q$ défini par $\alpha - 1 \le q < \alpha$, mais cela conduit à la même valeur pour $Y$.</footnote>
DEMONSTRATION : La démonstration de ce lemme découle directement du
lemme 1 puisque, d'après l'équation (2), le minimum de la longueur
moyenne des files est obtenu lorsque l'expression

$$
A_1''(1) = \sum_{i=0}^{\infty} h_i \cdot \left[ \sum_{n=0}^{\infty} n \cdot (n-1) \cdot c(n \mid i) \right] \quad (23)
$$

atteint son minimum.

Pour minimiser cette expression, il suffit de minimiser séparément
le coefficient de chaque $h_i$ ($i = 0, 1, 2, ...$) c'est-à-dire
$f(c(0 | i), c(1 | i), c(2 | i), ...)$.

Les contraintes mentionnées dans le lemme 1 sont respectées puisque :

$$
c(n \mid i) \ge 0 \qquad n = 0, 1, 2, \dots
$$

$$
\sum_{n=0}^{\infty} c(n \mid i) = 1
$$

et :

$$
\sum_{n=0}^{\infty} n \cdot c(n \mid i) = i/N
$$

Le résultat du lemme 1 est donc applicable et le coefficient de $h_i$ est minimal pour la distribution de probabilité :

$$
c(n \mid i) = \begin{cases} 1 + q - i/N & n = q \\ i/N - q & n = q + 1 \\ 0 & \text{ailleurs} \end{cases} \quad (24)
$$

où q est l'entier défini par $i/N - 1 < q \le i/N$,
ou encore $q = (i - r)/N$ avec $r = i \pmod N$. C.Q.F.D.

THEOREME : L'organisation de l'information correspondant à l'hypothèse Hb est optimale du point de vue du tambour, en ce sens qu'elle minimise la longueur moyenne des files associées aux secteurs.
DEMONSTRATION : la démonstration de ce théorème est immédiate. En effet,
on a vu (formules (7)) que les distributions de probabilité
{c(n | i)}∞∑n=0 pour i = 0, 1, 2, ... sont données par les formules (22)
pour l'organisation de l'information qui correspond à l'hypothèse Hb.

C.Q.F.D.

CONCLUSION

L'analyse mathématique du modèle nous a donné une expression générale
de la longueur moyenne des files d'attente associées aux secteurs, fournis-
sant ainsi un critère d'évaluation de comportement du tambour. En utilisant
ce critère, nous avons démontré que l'organisation qui consiste à ranger
sur des secteurs consécutifs l'information transférée pour une demande
groupée, est optimale. Ce résultat a été établi indépendamment de la poli-
tique de gestion des files associées aux secteurs.

Ce résultat confirme ceux qui ont été établis dans une simulation du
modèle ([Bau 73]) et qui concernent le temps moyen d'attente requis pour
transférer une demande groupée.
REFERENCES

[Bau 73a] G. Baudet, J. Boulenger, J. Ferrié
Analyse du comportement d'un tambour soumis à des demandes de transfert groupées,
Note de travail Laboria, Sys/A/03, mai 1973.

[Bau 73b] G. Baudet
Etude du comportement d'un tambour soumis à des demandes de transfert groupées,
Thèse de 3ème cycle, Université de Paris VI, Juin 1973 ;
disponible comme Rapport Laboria, n°30, Septembre 1973.

[Cof 69] E.G. Coffman, Jr
Analysis of a drum input/output under scheduled operation in a
paged computer system,
JACM, vol 16, n° 1, January 1969 (pp 73-90).