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

Evaluation sur des modèles
de comportement
de programme
de la taille d'un ensemble
de travail

J. Lenfant

Rapport de Recherche n° 55

Février 1974
EVALUATION SUR DES MODELES DE COMPORTEMENT
DE PROGRAMME DE LA TAILLE D'UN ENSEMBLE DE TRAVAIL

J. Lenfant*

(Présenté par E. Gelenbe)

RESUME

L'efficacité de la gestion des ressources dans un calculateur
dépend pour une bonne part de l'éparpillement des références à la mémoire
qui sont exécutées par les programmes. Afin de quantifier ce comportement,
P.J. DENNING a introduit la notion d'ensemble de travail. Dans cet article
la distribution de la taille des ensembles de travail est calculée sur deux
modèles stochastiques de comportement qui sont fréquemment utilisés dans
les études analytiques ou par simulation : le modèle à références indépen-
dantes et le modèle à liste LRU.

ABSTRACT

We compute the probability distribution function of the size of
P.J. DENNING's working set for two models of page reference string behaviour :
the independent reference model and the LRU stack model. The analytical
results are illustrated by some numerical examples which are also compared
with a normal distribution function approximation for working set size.

<footnote>* C.N.R.S. Université de Rennes, stagiaire IRIA-LABORIA.</footnote>
EVALUATION SUR DES MODELES DE COMPORTEMENT DE PROGRAMME
DE LA TAILLE D'UN ENSEMBLE DE TRAVAIL

par J. LENFANT. (1)

Résumé.

L'efficacité de la gestion des ressources dans un calculateur
dépend pour une bonne part de l'éparpillement des références à la mémoire
qui sont exécutées par les programmes. Afin de quantifier ce comportement,
P.J. Denning a introduit la notion d'ensemble de travail. Dans cet article
la distribution de la taille des ensembles de travail est calculée sur
deux modèles stochastiques de comportement qui sont fréquemment utilisés
dans les études analytiques ou par simulation : le modèle à références
indépendantes et le modèle à liste LRU.

# 1. INTRODUCTION

Dans un calculateur à mémoire paginée, la plupart des programmes
s'exécutent dans une zone de mémoire physique qui ne peut contenir qu'une
fraction de leur espace virtuel. Cette situation se traduit par des échanges
de pages entre la mémoire principale et la mémoire secondaire : souvent il
n'en résulte pas pour autant une dégradation notable du temps de réponse
ou du taux horaire de traitement du système. Ceci est dû à une propriété
intrinsèque du comportement de beaucoup de programmes. Même si un programme
référence un grand nombre de pages différentes au cours de son exécution,
dans tout intervalle de temps "raisonnable" les adresses auxquelles il
accède ne sont pas éparpillées sur tout l'espace virtuel : elles cons-
tituent au contraire un sous-ensemble strict qui est la "localité" dans
laquelle s'exécute le programme à l'instant donné.

L'existence de ces localités a plusieurs causes, D'une part
l'attention du programmeur se porte successivement sur des fractions de
l'algorithme qu'il met en oeuvre, certaines structures de données favori-
sant aussi cette concentration.

(1) C.N.R.S. - Université de Rennes - BP 25 A - 35031 Rennes-Cedex.
D'autre part, un programme comporte de nombreuses boucles qui, étant exécutées un grand nombre de fois, ont pour effet de circonscrire momentanément la partie utilisée de l'espace virtuel.

La connaissance et l'utilisation de cette propriété des programmes peuvent être utiles pour assurer une gestion efficace de l'ensemble des ressources physiques et logiques d'un système, et pas seulement de la mémoire centrale. De nombreuses expériences ont mis en évidence l'influence de ce phénomène sur l'intensité du trafic entre mémoire principale et mémoire secondaire et sur les performances des systèmes ; elles ont montré sa sensibilité au style de programmation et aux choix des structures de données [1] [2].

Pour formaliser cette notion floue de "localité", P. Denning [3] a introduit le concept d'ensemble de travail (en anglais: Working set). Pour une exécution donnée d'un programme, l'ensemble de travail (E.T.) de fenêtre T est, à l'instant t, l'ensemble noté W(t,T) des adresses qui ont été référencées dans l'intervalle de temps ]t-T, t]. Sur un modèle de programme assez général, Denning et Schwartz [4] ont calculé l'espérance mathématique de la taille de cet ensemble de travail en fonction de la distribution de l'intervalle entre deux références successives à une même adresse. Toutefois la seule connaissance de cette espérance mathématique est insuffisante pour qui veut analyser des politiques d'allocation de ressources: dans ce cas l'efficacité du système dépend autant de la dispersion autour de la valeur moyenne que de cette valeur moyenne elle-même. Il est donc nécessaire de connaître la distribution de la taille w (t,T) de l'E.T. ou, au moins, ses deux premiers moments. C'est ainsi que pour comparer l'efficacité d'une partition dynamique et d'une partition statique de la mémoire principale, Coffman et Ryan [5] ont admis que la distribution de la variable aléatoire w (t,T) est presque normale. Cette approximation, bien que suggéréepar plusieurs auteurs, n'a jamais été justifiée de manière convaincante.

L'objet de cette note est le calcul de la distribution de la taille de l'E.T. sur deux modèles de comportement de programme : le modèle à références indépendantes et le modèle à liste LRU. Ces deux modèles, dont nous rappellerons la définition au paragraphe 2, ont déjà été utilisés pour évaluer analytiquement les performances d'algorithmes de remplacement de pages [6] [7] [8] . Ils permettent également de représenter le comportement des programmes pour des études en simulation [9]
## 2. MODELISATION DES PROGRAMMES.

Pour que des mesures soient possibles et exploitables, il est souhaitable de regrouper les adresses par pages. Nous appellerons donc espace virtuel du programme étudié l'ensemble N de ses n pages :

$$N = \{1,2, \dots, n\}$$

La suite des adresses auxquelles le programme accède au cours d'une exécution est considérée comme une réalisation d'un processus sto-chastique à temps discret $(R_t)_{t \in N}$ ; la valeur de la variable aléatoire $R_t$ est le numéro de la page virtuelle référencée à l'instant $t$ : c'est un élément de $N$. Remarquons qu'une réalisation de ce processus stochas-tique est une suite infinie alors qu'un programme ne peut évidemment exé-cuter qu'un nombre fini de références : cette différence n'a pas de conséquence fâcheuse pour les études de comportement. Avec ce formalisme, définir un modèle de comportement de programme c'est énoncer un ensemble d'hypothèses sur le processus $(R_t)$.

Avant de particulariser le modèle nous allons définir de manière plus précise l'ensemble de travail.

### Définition 1

Soient $t$ et $T$ deux entiers positifs tels que $T < t$. Pour une réalisation

$$r_0, r_1, r_2, \dots, r_t, \dots$$

du processus $(R_t)$ l'ensemble de travail de fenêtre $T$ est, à l'instant $t$

$$W(t,T) = \{i \in N \mid (\exists u \in N) \ (t-T+1 \le u \le T) \ : r_u = i\}$$

La taille de $W(t,T)$ (notée $w(t,T)$) est son nombre d'éléments.

### Définition 2

Le taux d'absence de page $m(t,T)$ est la probabilité que la page référencée à l'instant $t+1$ n'appartienne pas à l'E.T. $W(t,T)$

$$m(t,T) = \Pr[r_{t+1} \notin W(t,T)] \\ = \Pr[w(t+1, T+1) - w(t,T) = 1]$$
## 2.1. LE MODELE DE COMPORTEMENT DE PROGRAMME DE DENNING ET SCHWARTZ

Pour toutes pages i et j et tous entiers strictement positifs t et x, nous désignerons par $g_{ij}(t,x)$ la probabilité que la première référence à la page j après l'instant t ait lieu à l'instant $t+x$, sachant que la page i est référencée à l'instant $t$ :

$$g_{ij}(t,x) = \text{Pr} \left[ r_{t+1} \neq j ; \dots ; r_{t+x-1} \neq j, r_{t+x} = j | r_t = i \right]$$

Le modèle de Denning et Schwartz est caractérisé par les hypothèses suivantes :

**DS 1** Pour tout i appartenant à N, $g_{ii}(t,x)$ ne dépend pas de t.
Nous noterons : $g_{ii}(t,x) = f_i(x)$

**DS 2** Pour tout i, $\sum_{x \ge 1} f_i(x) = 1$

**DS 3** Pour tout i, la durée moyenne de l'intervalle $X_i$, entre deux références successives à la page i est finie :
$$\bar{X}_i = \sum_{x \ge 1} f_i(x) < + \infty$$

**DS 4** Il existe un instant $t_{asym}$ tel que toute page de N est référencée avant $t_{asym}$

Rappelons le théorème démontré par Denning et Schwartz.

La probabilité absolue qu'une référence concerne la page i est égale à $\frac{1}{\bar{X}_i}$. Posons

$$f = \sum_{i} \frac{1}{\bar{X}_i} f_i$$

et désignons par F la fonction cumulative associée à f :

$$F(y) = \sum_{x=1}^{y} f(x)$$

**Théorème 1** Soit un programme dont le comportement obéit aux hypothèses DS1 à DS4. Pour tout entier $t \ge t_{asym}$ et tout entier positif $T \le t$ :
$$ \bar{w}(t,T) = \sum_{y=0}^{T-1} (1-F(y)) $$

$$ m(t,T) = 1 - F(T) $$

On remarque que la taille moyenne de l'E.T. et le taux d'absence de page ne dépendent pas de t. En outre

$$ m(T) = \bar{w}(T+1) - \bar{w}(T) $$

## 2.2. LE MODELE DE COMPORTEMENT DE PROGRAMME A REFERENCES INDEPENDANTES

### Définition

Le modèle de comportement de programme est dit "à références indépendantes" si le processus stochastique ($R_t$) satisfait aux trois conditions suivantes :

**RI1** Pour toute famille finie $t_1, t_2, \dots, t_p$ d'entiers positifs deux à deux distincts, les variables aléatoires $R_{t_1}, R_{t_2}, \dots, R_{t_p}$ sont indépendantes.

**RI2** Toutes les variables aléatoires $R_t$ ont la même distribution. Pour toute page i et tout entier positif $t$, nous noterons

$$ \Pr[R_t = i] = \alpha_i $$

**RI3** Pour tout $i$, $\bar{\alpha}_i$ est différent de 0.

Remarquons que ce modèle ne prend pas en compte les propriétés de localité des programmes. En revanche il traduit l'importance relative en durée d'exécution - des différents parties du programme. Statistiquement la probabilité $\bar{\alpha}_i$ peut être interprétée comme le pourcentage des références qui, au cours d'une longue période, concernent la page i.

Ce modèle de comportement est un cas particulier de celui qui est défini au paragraphe 2.1. En effet l'intervalle entre deux références successives à la page i a une densité de distribution indépendante de t :

$$ f_i(x) = (1 - \alpha_i)^{x-1} \alpha_i \quad (x \ge 1) $$
qui vérifie en outre

$$ \sum_{x \ge 1} f_i(x) = \alpha_i \sum_{x \ge 1} (1 - \alpha_i)^{x-1} = \frac{\alpha_i}{\alpha_i - 1} = 1 $$

et

$$ \sum_{x \ge 1} x f_i(x) = \alpha_i \sum_{x \ge 1} (1 - \alpha_i)^{x-1} = \alpha_i < +\infty $$

Comme, pour tout $i$, la probabilité que la page $i$ ne soit pas référencée entre 0 et $t$ tend vers 0 lorsque $t$ tend vers l'infini, l'hypothèse OS4 est également vérifiée.

### 2.3. LE MODELE DE COMPORTEMENT DE PROGRAMME A LISTE LRU

Pour ce modèle, la probabilité qu'une page soit référencée dépend de sa position instantanée dans la liste LRU, c'est-à-dire dans la liste des pages classée par ordre d'ancienneté croissante de la dernière référence.

Soit $\mathcal{Y}$ l'ensemble des permutations de $N$. Nous désignerons par $\sigma = (a_1, a_2, \dots, a_k, \dots, a_n)$ un élément de $\mathcal{Y}$. Nous dirons que la page $a_k$ est à la distance $k$ dans $\sigma$. $\mathcal{Y}$ est l'ensemble des états du programme, l'état initial étant désigné par $\sigma_0$. Au cours de l'exécution le programme passe par une suite d'états.

$$ \sigma_0, \sigma_1, \sigma_2, \dots, \sigma_t, \dots $$

telle que pour $t \ge 0$, si l'on note

$$ \sigma_t = (a_1, a_2, \dots, a_n) $$

il existe un entier $1 \le d_t \le n$ tel que

$$ \sigma_{t+1} = (a_{d_t}, a_1, a_2, \dots, a_{d_{t-1}}, a_{d_t+1}, \dots, a_n) $$

Le nombre $d_t$ sera considéré comme la réalisation d'une variable aléatoire $D_t$. Il est essentiel de remarquer que pour un état initial $\sigma_0$ donné, la connaissance du processus stochastique $(R_t)_{t \in \mathbb{N}}$ équivaut à celle de $(D_t)_{t \in \mathbb{N}}$ puisque pour tout $t; a_{d_t} = r_t$
## Définition

Le modèle de comportement de programme est à liste LRU si le processus stochastique ($D_t$) satisfait aux trois conditions suivantes : $t \in N$

**LRU1** Pour toute famille $t_1, t_2, ..., t_p$ d'entiers positifs deux à deux distincts, les variables aléatoires $D_{t_1}, D_{t_2}, ..., D_{t_p}$ sont indépendantes.

**LRU2** Toutes les variables aléatoires $D_t$ ont la même distribution

Pour tout $1 \le i \le n$ nous noterons

$$ \Pr[D_t = i] = \beta_i $$

**LRU3** Pour tout $i$, $\beta_i$ est différent de 0.

Ce modèle, inspiré par les bonnes performances de l'algorithme de remplacement de pages LRU, tient compte de la propriété de localité des programmes. Mais sur une longue période, toutes les pages sont référencées avec la même fréquence relative. Nous ne considérerons que le comportement stationnaire d'un programme à modèle LRU : le choix de l'état initial $D_0$ n'a aucune influence sur ce comportement. Remarquons enfin que ce modèle est également un cas particulier du modèle de Denning et Schwartz.

## 3. TAILLE DE L'E.T. D'UN PROGRAMME CONFORME AU MODELE A LISTE LRU.

Pour un tel modèle de comportement, l'E.T. $W(t,T)$ a exactement $k$ éléments si et seulement si la chaîne

$$ D_{t-T+1} \ D_{t-T+2} \ \dots \ D_t $$

des distances associées aux références exécutées entre $t-T+1$ et $t$ est de la forme

$$ (1) \quad \delta_1 (1)^{r_1} \ \delta_2 (1,2)^{r_2} \ \delta_3 (1,2,3)^{r_3} \ \dots \ \delta_k (1,2,...,k)^{r_k} $$
où $\delta_i$ est une distance supérieure ou égale à i
les $r_i$ sont des entiers positifs ou nuls dont la somme est $T-k$
$(1,2,...,1)^r$ désigne une suite de r distances toutes non supérieures à 1.

Par suite de l'indépendance des variables aléatoires ($D_t$),
la probabilité d'un E.T. de taille k ($1 \le k \le \min(n,T)$) est donc

$$
\begin{align*}
(2) \quad \operatorname{Pr} [w(t,T) = k] &= \operatorname{Pr} [D \ge 1] \times \operatorname{Pr} (D \ge 2) \times \dots \times \operatorname{Pr} (D \ge k) \times \\
& \quad \sum_{r_i \ge 0} r_1^{\beta_1} (\beta_1 + \beta_2)^{r_2} \dots (\beta_1 + \beta_2 + \dots + \beta_k)^{r_k} \\
& \quad r_1^{\beta_1+\dots+r_k} = T-k
\end{align*}
$$

Désignons par $P(\beta_1, \beta_2, ..., \beta_k)$ la sommation figurant dans le
membre de droite et posons $S_i = \sum_{j=1}^{i} \beta_j$. Puisque $\Pr[D \ge i] = 1 - S_{i-1}$
$(1 \le i \le n)$, l'égalité (2) équivaut à

$$
(3) \quad \mathrm{Pr} \left[ w(t,T) = k \right] = (1-S_1) (1-S_2) \dots (1-S_{k-1}) \mathrm{Pr} \left[ \beta_1, \beta_2, \dots, \beta_k \right]
$$

Pour simplifier l'expression de P ($\beta_1, \beta_2, \dots, \beta_k$) remarquons
que ce nombre est le $(T-k)^e$ coefficient du développement en série entière
de la fonction rationnelle :

$$
Q(z) = \frac{1}{(1-S_1 z)(1-S_2 z) \dots (1-S_k z)}
$$

Puisque tous les pôles de Q sont simples (hypothèse LRU 3)
sa décomposition en éléments simples est

$$
Q(z) = \sum_{i=1}^{k} \frac{S_i^{k-1}}{\prod_{\substack{1 \le j \le k \\ j \ne i}} (S_i - S_j)} \times \frac{1}{(1 - S_i z)}
$$

En utilisant cette expression de Q pour calculer les coefficients
de son développement en série entière, nous obtenons :

$$
(4) \quad P ( \beta_1, \beta_2, \dots, \beta_k ) = \sum_{i=1}^{k} \frac{S_i^{T-1}}{\prod_{\substack{1 \le j \le k \\ j \ne i}} (S_i - S_j)}
$$
Enonçons ce résultat :

## Théorème 2

La distribution de la taille de l'E.T. d'un programme se comportant suivant le modèle LRU est déterminée pour tout entier $k$ positif et au plus égal à $\min(n,T)$ par

$$ \mathrm{Pr} \left[ w(t,T) = k \right] = (1-S_1) (1-S_2) \cdots (1-S_{k-1}) \sum_{i=1}^{k} \frac{s_i^{T-1}}{\prod_{1 \le t \le k} (s_i - s_j)} \quad j \ne i $$

Cette formule permet de faire rapidement le calcul effectif de la distribution de $w(t,T)$ ainsi que de la valeur moyenne $\bar{w}(t,T)$ et du taux d'absence de page $m(t,T)$. Remarquons en particulier que

$$ m(t,T) = \sum_{k=1}^{\min(n,T)} (1-S_k) \mathrm{Pr} \left[ w(t,T) = k \right] $$

## 4. TAILLE DE L'E.T. D'UN PROGRAMME CONFORME AU MODELE A REFERENCES INDEPENDANTES.

Pour un programme ayant un comportement à références indépendantes, la probabilité que la chaîne des pages référencées entre $t - T + 1$ et $t$ soit

$$ Y = i_1 \ i_2 \ \dots \ i_T \quad \text{est égale à} $$

$$ \begin{align*} \pi(Y) &= \mathrm{Pr} [R_{t-T+1} = i_1] \times \mathrm{Pr} [R_{t-T+2} = i_2] \times \dots \times \mathrm{Pr} [R_{t} = i_T] \\ &= \alpha^{i_1} \times \alpha^{i_2} \times \dots \times \alpha^{i_T} \end{align*} $$

Par suite la probabilité que l'E.T. $W(t,T)$ ait pour taille $k$ ($1 \le k \le \min(n,T)$) est

$$ (5) \quad \mathrm{Pr} \left[ w(t,T) = k \right] = \sum_{*} \pi(Y) $$

la sommation $\sum_{*}$ étant étendue à toutes les chaînes de $T$ éléments de $N$ comportant exactement $k$ éléments distincts. Pour évaluer (5) nous allons utiliser une méthode analogue à celle qui est utilisée pour démontrer le théorème d'inversion de Möbius [10]
Nous dirons qu'une chaîne $\gamma$ de $N^T$ à la propriété $P(i)$ si elle ne contient pas l'élément $i$ ; $i_1, i_2, \dots, i_q$ étant $q$ éléments de $N$, nous désignerons par $N_{i_1 i_2 \dots i_q}$ l'ensemble des chaînes de $N^T$ ayant à la fois les propriétés $P(i_1), P(i_2), \dots$ et $P(i_q)$ (et éventuellement d'autres propriétés) et par $\pi_{i_1 i_2 \dots i_q}$ la probabilité de cet ensemble. Il est clair que

$$ (6) \qquad \begin{aligned} \pi_{i_1 i_2 \dots i_q} &= \operatorname{Pr} \left[ N_{i_1 i_2 \dots i_q} \right] = \sum_{\gamma \in N_{i_1 i_2 \dots i_q}} \pi(\gamma) \\ &= (1 - \alpha_{i_1} - \alpha_{i_2} - \dots - \alpha_{i_q})^T \end{aligned} $$

Nous allons démontrer que, pour tout $1 \le k \le \min(n, T)$ :

$$ (7) \quad \operatorname{Pr} [W(t,T) = k] = \sum_{r=n-k}^{n} \binom{r+n+k}{n-k} C_r^{n-k} \prod_{i_1<i_2<\dots<i_r} \pi^{i_1} i_1! i_2! \dots i_r! $$

(La sommation $\sum$ est une sommation sur toutes les combinaisons $i_1 < i_2 < \dots < i_r$ choisis dans $N$)

En effet soit $\gamma$ une chaîne de T références. Trois éventualités sont à considérer.

a) si $\gamma$ contient strictement plus de $k$ termes différents, elle a strictement moins de $(n-k)$ propriétés du type $P(i)$ : elle ne figure donc dans aucun des ensembles $N_{i_1 i_2 \dots i_q}$ dont les probabilités sont prises en compte dans le membre de droite $q$ de l'égalité (7).

b) si $\gamma$ contient exactement $k$ termes différents, c'est-à-dire si elle possède les propriétés $P(j_1), P(j_2), \dots, P(j_{n-k})$ à l'exclusion de toute autre, sa probabilité $\pi(\gamma)$ contribue à $\pi^{j_1} j_1! j_2! \dots j_{n-k}!$ (qui est affecté du coefficient $C_{n-k}^{n-k} = 1$) et seulement à ce terme

c) si $\gamma$ a exactement $s$ propriétés du type $P(i)$ ($s > n-k$) sa contribution à $(-1)^{r+n+k} C_r^{n-k} \sum_{i_1<i_2<\dots<i_r} \pi^{i_1} i_1! i_2! \dots i_r!$ est égale à $(-1)^{r+n+k} C_r^{n-k} C_s^r \pi(\gamma)$
La contribution totale d'une telle chaîne au membre de droite de l'égalité (7) est donc :

$$ (8) \quad (-1)^{k-n} \pi(\gamma) \sum_{r=n-k}^{s} (-1)^r C_s^r C_r^{n-k} $$

En dérivant (n-k) fois l'identité binomiale :

$$ (1+x)^s = \sum_{r=0}^{s} C_s^r x^r $$

en divisant par (n-k) et l'identité ainsi obtenue et en posant $x = -1$, il vient :

$$ \sum_{r=n-k}^{s} (-1)^r C_s^r C_r^{n-k} = \frac{1}{(n-k)!} \frac{d^{(n-k)}}{dx^{(n-k)}} (1+x)^s \Big|_{x=-1} $$

quantité qui est nulle puisque $s > n-k$. La contribution de la chaîne Y au membre de droite de (7) est donc nulle également dans ce cas.

Il résulte de cette étude que le membre de droite de (7) est la somme des probabilités des chaînes de $N^T$ qui contiennent exactement k éléments distincts : cette somme est égale à $\text{Pr}[W(t,T) = k]$ d'après l'égalité (5). D'où le théorème :

### Théorème 3

La distribution de la taille de l'E.T. d'un programme se comportant suivant le modèle à références indépendantes est déterminée pour tout entier k positif et au plus égal à min(n,T) par :

$$ \begin{array}{l} (9) \quad \text{Pr}[W(t,T) = k] = \sum_{r=n-k}^{n} (-1)^{r-n-k} C_r^{n-k} U_r \\ \qquad \text{où l'on a posé } U_r = \sum_{i_1<i_2<\dots<i_r} (1-\alpha_{i_1}-\alpha_{i_2}-\alpha_{i_r})^T \\ \qquad \text{et } U_0 = 1 \end{array} $$
**Corollaire** Pour un programme ayant un comportement à références indépendantes et la variance de la taille d'un E.T. sont respectivement égales à

$$ (10) \quad \bar{w}(T) = n - U_1 $$

$$ \text{et} \quad (11) \quad \sigma^2(T) = -U_1^2 + (2n-1) U_1 + 2 U_2 $$

Pour démontrer ces deux formules, utilisons l'égalité (11)

$$ \text{Pr} [w(T)=n] = C_0^n U_0 + C_1^n U_1 + C_2^n U_2 + \dots + C_{n-1}^n U_{n-1} + C_n^n U_n $$

$$ \text{Pr} [w(T)=n-1] = C_1^{n-1} U_1 + C_2^{n-1} U_2 + \dots + C_{n-1}^{n-1} U_{n-1} + C_n^{n-1} U_n $$

$$ \text{Pr} [w(T)=n-2] = C_2^{n-2} U_2 + C_3^{n-2} U_3 + \dots + C_{n-1}^{n-2} U_{n-1} + C_n^{n-2} U_n $$

$$ \text{Pr} [w(T)=n-1] = C_1^{n-1} U_1 + C_2^{n-1} U_2 + \dots + C_{n-1}^{n-1} U_{n-1} + C_n^{n-1} U_n $$

$$ \text{Pr} [w(T)=1] = C_{n-1}^{n-1} U_{n-1} - C_n^{n-1} U_n $$

$$ \text{Pr} [w(T)=0] = C_n^n U_n $$

En évaluant "par colonnes" la somme $\sum_{r=0}^{n} r \cdot \text{Pr}[w(T)=r]$

on obtient

$$ \bar{w}(T) = \sum_{k=0}^{n} \sum_{l=0}^{k} (-1)^{k+1} C_k^l U_k $$

$$ (12) \quad = \sum_{k=0}^{n} (-1)^k U_k \sum_{l=0}^{k} (-1)^{n-l} C_l^k $$

La sommation la plus à droite peut se scinder en deux :

$$ \sum_{k=0}^{n} (-1)^k C_k^1 \text{ est égal à } n \text{ si } k=0, \text{ sinon à } n(1-1)^k = 0 $$
$$ \sum_{k=0}^{k} (-1)^k C_k^1 \quad \text{est la valeur pour } x = -1 \text{ de la dérivée de } (1+x)^k : $$

cette somme est donc nulle sauf si $k=1$, auquel cas elle vaut 1.

Finalement l'égalité (12) implique :

$$ \bar{w}(T) = n U_0 - U_1 = n - U_1 $$

ce qui est le résultat cherché.

Un calcul analogue nous permet de trouver le second moment de la distribution de $w(T)$. En effet :

$$ (13) \quad E(w^2(T)) = \sum_{k=0}^{n} (-1)^k U_k \sum_{l=0}^{k} (n^2-2l-1)^2 (-1)^l C_k^l $$

Compte tenu de ce que $\sum_{l=0}^{k} (1+x)^l = (1+x)^k + 1$, l'égalité (13) point x=-1 de $-\frac{d}{dx}\left[x\frac{d}{dx}(1+x)^k\right]$

conduit à :

$$ E(w(T)^2) = n^2 U_0 - U_1 + 2U_2, $$

La variance de la taille de 1'E.T. est donc :

$$ \sigma^2(T) = E(w(T)^2) - E(w(T))^2 = -U_1^2 + (2n-1)U_1 + 2U_2 $$

Notons enfin que l'égalité (10) a déjà été établie par Coffmann et Schwartz comme conséquence du théorème 1.

## Remarque sur une autre approche possible

Il est possible de calculer cette distribution de $w(t,T)$ par une méthode analogue à celle qui a été employée pour les programmes suivants : un modèle de comportement à liste LRU. Calculons la probabilité que $w(t,T)$ soit égal à $k$ ($1 < k < \min(n,T)$). L'ensemble de travail $W(t,T)$ est égal à $\{1,2,...,k\}$ si et seulement si la chafine des $T$ références exécutées entre l'instant $t-T+1$ et l'instant $t$ est :
- soit une chaîne de la forme

(14) $1(1)^{r_1} 2(1,2)^{r_2} 3(1,2,3)^{r_3} \dots k(1,2,3,\dots,k)^{r_k}$ où les $r_i$ sont des entiers positifs ou nuls de somme T-k et où $(1,2,\dots,1)^r$ désigne une suite de r références à des pages du sous-ensemble $\{1,2,\dots,1\}$

- soit une chaîne déduite d'une chaîne du type précédent par une permutation sur $\{1,2,\dots,k\}$

La probabilité qu'une suite de T références générées par le programme soit de la forme décrite en (14) est égale à

$$ \alpha_1 \alpha_2 \cdots \alpha_k \sum_{r_1 \ge 0} \alpha_1^{r_1} (\alpha_1 + \alpha_2)^{r_2} \cdots (\alpha_1 + \alpha_2 + \cdots + \alpha_k)^{r_k} \\ \qquad r_1 + r_2 + \cdots + r_k = T-k $$

c'est-à-dire à

$$ \alpha_1 \alpha_2 \cdots \alpha_k P(\alpha_1, \alpha_2, \cdots, \alpha_k) $$

où P désigne la même fonction qu'au paragraphe 3.

Par additivité, il en résulte

$$ \mathrm{Pr} [W(t,T) = \{1,2,\dots,k\}] = \alpha_1 \alpha_2 \cdots \alpha_k \sum_{\sigma} P(\alpha_{\sigma(1)} \alpha_{\sigma(2)} \cdots \alpha_{\sigma(k)}) $$

la sommation $\sum_{\sigma}$ étant étendue à toutes les permutations $\sigma$ de $\{1,2,\dots,k\}$ ; de même

$$ \mathrm{Pr} [W(t,T) = k] = \sum_{\sigma} \alpha_{i(1)} \alpha_{i(2)} \cdots \alpha_{i(k)} P(\alpha_{i(1)} \alpha_{i(2)} \cdots \alpha_{i(k)}) $$

la sommation $\sum_{\sigma}$ étant étendue à l'ensemble $I_k$ des arrangements i des n premiers entiers positifs choisis k à k, c'est-à-dire à l'ensemble des injections i de $\{1,2,\dots,k\}$ dans $\{1,2,\dots,n\}$. Du calcul de P qui a été fait au paragraphe 3 on tire donc l'expression suivante pour la distribution de $w(t,T)$ :

$$ (15) \quad \mathrm{Pr} [w(t,T) = k] = \sum_{i \in I_k} \alpha_{i(1)} \alpha_{i(2)} \cdots \alpha_{i(k)} \sum_{r=1}^{k} \frac{s_{r,i}^{T-1}}{1 \le s \le k} \frac{(s_{r,i} - s_{s,i})}{s/r} $$

$$ \text{où } s_{i,j} = \alpha_{i(1)} + \alpha_{i(2)} + \cdots + \alpha_{i(k)} $$
En raison du nombre élevé d'arrangements ($|I_k| = \frac{n!}{(n-k)!}$) la formule (9) est préférable pour le calcul effectif de la distribution de $w(t,T)$.

## 5. RESULTATS NUMERIQUES

Sur les figures 1 et 2 est rapportée la taille de l'E.T. de deux comportements de programme : le premier de ces comportements est à références indépendantes, le second à liste LRU. La valeur de $Pr[w(T) = k] (1 \le k \le n)$ y est comparée à son approximation gaussienne

$$ \Pi_k = \Phi\left(\frac{k+1/2 - w(T)}{\sigma}\right) - \Phi\left(\frac{k - \frac{1}{2} - w(T)}{\sigma}\right) $$

où l'on désigne par $\sigma$ l'écart-type de $w(T)$ et par $\Phi$ la fonction de répartition de la distribution normale réduite :

$$ \Phi(x) = \frac{1}{\sqrt{2\pi}} \int_{-\infty}^{x} e^{-\frac{t^2}{2}} dt $$

Sur ces figures, ainsi que sur les quelques centaines d'autres résultats de ce type que nous avons obtenus, l'accord entre $Pr[w(T) = k]$ et $\Pi_k$ est très bon ; il est d'autant meilleur que n est plus grand. Toute-fois lorsque T est très supérieur à n (par exemple : T=480 sur la figure 2) la différence entre $Pr[w(T) = k]$ et $\Pi_k$ peut être sensible : ceci n'est pas surprenant car on approxime alors par une distribution continue une distribution discrète dont seules quelques valeurs ont une probabilité non négligeable.

Les figures 3 et 4 représentent la variation en fonction de T de la moyenne et de l'écart-type de l'E.T. du programme déjà considéré sur la figure 2.
BIBLIOGRAPHIE

[1] B.S. BRAWN et F.G. GUSTAVSON : Program behavior in a paging envi-
ronment- Proc. of A.F.I.P.S. F,J.C.C,
1968.-

[2] D.SAYRE : Is automatic folding of programs efficient enough to displace manual? - C.A.C.M., décembre 1969.-

[3] P.J. DENNING : The working set model for program behavior - C.A.C.M., mai 1968.-

[4] P.J. DENNING et S.C. SCHWARTZ : Properties of the working set model
C.A.C.M., Mars 1972.-

[5] E.G. COFFMAN Jr et T.A. RYAN Jr : A study of storage partitioning using a mathematical model of locality - C.A.C.M. Mars 72.

[6] A.V. AHO et P.J. DENNING et J.D. ULLMAN : Principles of optimal page replacement - J.A.C.M., janvier 1971.-

[7] W.F. KING III : Analysis of demand paging algorithms - Proc of the I.F.I.P. Congress 1971, North-Holland Publishing Company.-

[8] E. GELENBE : A unified approach to the evaluation of a class of re-
placement algorithms - I.E.E.E. Trans. on computers,
Juin 1973.-

[9] C. BETOURNE et S. KRAKOWIAK : Simulation de l'allocation de ressources
dans un système à mémoire virtuelle paginée
- Congrès A.F.C.E.T., Novembre 1972.-

[10] M. HALL Jr : Combinatorial theory - Blaisdell Publishing Company, 1967.-
CARACTERISTIQUES DU PROGRAMME

Nombres de pages : n=15

Modèles à références indépendantes

$$ \alpha_i = C (16-i) $$

(C est la constante de normalisation)

T = 15

<table><thead><tr><th>k</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>Pr [w(T)=k]</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,002</td><td>0,024</td><td>0,112</td><td>0,260</td></tr><tr><td>Approximation<br>gaussienne</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,003</td><td>0,027</td><td>0,114</td><td>0,257</td></tr><tr><td>k</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td></td></tr><tr><td>Pr [w(T)=k]</td><td>0,316</td><td>0,204</td><td>0,068</td><td>0,011</td><td>0,001</td><td>0,000</td><td>0,000</td><td></td></tr><tr><td>Approximation<br>gaussienne</td><td>0,311</td><td>0,202</td><td>0,071</td><td>0,013</td><td>0,001</td><td>0,000</td><td>0,000</td><td></td></tr></tbody></table>

T=125

<table><thead><tr><th>k</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th><th>7</th><th>8</th></tr></thead><tbody><tr><td>Pr [w(T)=k]</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td></tr><tr><td>Approximation<br>gaussienne</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,000</td></tr><tr><td>k</td><td>9</td><td>10</td><td>11</td><td>12</td><td>13</td><td>14</td><td>15</td><td>16</td></tr><tr><td>Pr [w(T)=k]</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,003</td><td>0,064</td><td>0,402</td><td>0,532</td><td></td></tr><tr><td>Approximation<br>gaussienne</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,001</td><td>0,062</td><td>0,462</td><td>0,427</td><td>0,048</td></tr></tbody></table>

FIGURE 1
Caractéristiques du programme

Nombre de pages n=40

Modèle à liste LRU

$\beta_i = C \times 20 \quad \text{si } 1 < i < 8$

$\beta_i = C \times 10 \quad \text{si } 9 < i < 20$

$\beta_i = C \times 7 \quad \text{si } 21 < i < 23$

$\beta_i = C \times 6 \quad \text{si } 24 < i < 26$

$\beta_i = C \times 5 \quad \text{si } 27 < i < 29$

$\beta_i = C \times 4 \quad \text{si } 30 < i < 32$

$\beta_i = C \times 3 \quad \text{si } 33 < i < 35$

$\beta_i = C \times 2 \quad \text{si } 36 < i < 38$

$\beta_i = C \times 1 \quad \text{si } 39 < i < 40$

(C est la constante de normalisation)

$T=20$

<table><caption>FIGURE 2</caption><thead><tr><th>k</th><th>6</th><th>7</th><th>8</th><th>9</th><th>10</th><th>11</th><th>12</th><th>13</th><th>14</th></tr></thead><tbody><tr><td>Pr [w(T)=k]</td><td>0,000</td><td>0,000</td><td>0,002</td><td>0,013</td><td>0,051</td><td>0,128</td><td>0,216</td><td>0,248</td><td>0,194</td></tr><tr><td>Approximation gaussienne</td><td>0,000</td><td>0,000</td><td>0,003</td><td>0,014</td><td>0,051</td><td>0,127</td><td>0,215</td><td>0,246</td><td>0,192</td></tr><tr><td>k</td><td>15</td><td>16</td><td>17</td><td>18</td><td>19</td><td>20</td><td></td><td></td><td></td></tr><tr><td>Pr [w(T)=k]</td><td>0,102</td><td>0,036</td><td>0,008</td><td>0,001</td><td>0,000</td><td>0,000</td><td></td><td></td><td></td></tr><tr><td>Approximation gaussienne</td><td>0,102</td><td>0,037</td><td>0,009</td><td>0,002</td><td>0,000</td><td>0,000</td><td></td><td></td><td></td></tr></tbody></table>
T=80

<table><thead><tr><th>k</th><th>19</th><th>20</th><th>21</th><th>22</th><th>23</th><th>24</th><th>25</th><th>26</th><th>27</th></tr></thead><tbody><tr><td>Pr [w(T)=k]</td><td>0,000</td><td>0,001</td><td>0,004</td><td>0,016</td><td>0,047</td><td>0,100</td><td>0,162</td><td>0,203</td><td>0,193</td></tr><tr><td>Approximation gaussienne</td><td>0,000</td><td>0,001</td><td>0,005</td><td>0,017</td><td>0,047</td><td>0,100</td><td>0,161</td><td>0,201</td><td>0,193</td></tr></tbody></table>

<table><thead><tr><th>k</th><th>28</th><th>29</th><th>30</th><th>31</th><th>32</th><th>33</th></tr></thead><tbody><tr><td>Pr [w(T)=k]</td><td>0,142</td><td>0,081</td><td>0,034</td><td>0,011</td><td>0,003</td><td>0,000</td></tr><tr><td>Approximation gaussienne</td><td>0,142</td><td>0,081</td><td>0,035</td><td>0,012</td><td>0,003</td><td>0,001</td></tr></tbody></table>

T=480

<table><caption>FIGURE 2 Suite</caption><thead><tr><th>k</th><th>32</th><th>33</th><th>34</th><th>35</th><th>36</th><th>37</th><th>38</th><th>39</th><th>40</th><th>41</th><th>42</th></tr></thead><tbody><tr><td>Pr [w(T)=k]</td><td>0,000</td><td>0,000</td><td>0,001</td><td>0,011</td><td>0,062</td><td>0,211</td><td>0,396</td><td>0,255</td><td>0,065</td><td></td><td></td></tr><tr><td>Approximation gaussienne</td><td>0,000</td><td>0,000</td><td>0,000</td><td>0,002</td><td>0,065</td><td>0,238</td><td>0,369</td><td>0,244</td><td>0,068</td><td>0,008</td><td>0,000</td></tr></tbody></table>
<figure><img src="image_1.png" /><figcaption>FIGURE 3</figcaption></figure>
<figure><img src="image_2.png" /><figcaption>FIGURE 4</figcaption></figure>