# Analyse d'un algorithme de gestion simultanée. mémoire centrale, disque de pagination.

Erol Gelenbe, Dominique Potier, Alexandre Brandwajn, Jacques Lenfant

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

## To cite this version:

Erol Gelenbe, Dominique Potier, Alexandre Brandwajn, Jacques Lenfant. Analyse d'un algorithme de gestion simultanée. mémoire centrale, disque de pagination.. [Rapport de recherche] IRIA-RR-019, IRIA. 1973, pp.51. hal-04715914

HAL Id: hal-04715914

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

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>
<figure><img src="image_3.png" /></figure>

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

Analyse d'un algorithme
de gestion simultanée.
Mémoire centrale,
disque de pagination.

E. Gelenbe, J. Lenfant,
A. Brandwajn, D. Potier.

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

Rapport de Recherche n°19

mai 1973
ANALYSE D'UN ALGORITHM DE GESTION SIMULTANÉE
MÉMOIRE CENTRALE - DISQUE DE PAGINATION

E. Gelenbe - J. Lenfant*

A. Brandwajn - D. Potier

RÉSUMÉ

L'optimisation de la gestion d'un disque sur lequel les pages ont
des images fixes et l'optimisation du remplacement à la demande de pages
de la mémoire centrale mettent en évidence des exigences contradictoires.

Dans cette étude une nouvelle politique-globale-de gestion d'un tel système
de pagination est analysée sur un modèle mathématique.

Pour cela, une classe à un paramètre d'algorithmes de remplacement qui
choisissent la page à remplacer non seulement en fonction de l'état de la
mémoire centrale et du comportement du programme, mais aussi en fonction
de la position instantanée du disque est introduite. Ses performances sont
evaluées en monoprogrammation. Les résultats théoriques sont illustrés
d'exemples numériques.
TABLE DES MATIERES

I - INTRODUCTION

I.1. La gestion des mémoires paginées 1

I.2. La gestion simultanée des disques et de la mémoire centrale 3

I.3. Plan de l'étude 4

II - LES ALGORITHMES DE REMPLACEMENT DE PAGE ALEATOIRES A PRECHARGEMENT PARTIEL

II.1. Le modèle de programme à références indépendantes 5

II.2. Définition formelle des ARPAPP 6

II.3. Taux de défauts de page des ARPAPP 9

II.4. Les ARPAPP optimaux 11

III - GESTION DU DISQUE DE PAGINATION

III.1. Introduction 12

III.2. Calcul du temps moyen de service sans tampon 14

III.3. Calcul du temps moyen de service avec tampon 19

IV - RESULTATS NUMERIQUES

IV.1. Introduction 25

IV.2. Détermination de la valeur optimale de 2 25

IV.3. Utilité du tampon 27

APPENDICE 29

REFERENCES 32

FIGURES
# I - INTRODUCTION

## I.I. - LA GESTION DES MEMOIRES PAGINEES

Dès les débuts de l'informatique, les programmeurs ont essayé de disposer d'un espace adressable considérablement plus vaste que ne l'est la mémoire centrale. L'information ne doit se trouver en mémoire centrale qu'au moment d'être traitée par les processeurs ; sinon elle peut résider dans des mémoires auxiliaires à accès plus lent mais moins coûteuses. Dans de nombreux systèmes d'exploitation récents - ceux qui utilisent le concept de mémoire virtuelle - c'est le système lui-même qui contrôle la répartition de l'information entre les différents supports disponibles et qui décide de l'opportunité des transferts. Le choix de cette stratégie d'allocation est crucial pour l'efficacité du calculateur.

Le procédé le plus fréquemment utilisé pour réaliser une mémoire virtuelle est la pagination. L'espace adressable de chaque programme est divisé en blocs de même taille, les "pages". La mémoire centrale est elle-même divisée en "pages physiques" pouvant chacune être le support d'une page du programme. Un dispositif câblé permet de traduire toute adresse logique en une adresse physique.

La partie de l'information d'un programme qui ne se trouve pas en mémoire centrale est souvent rangée sur un disque à secteurs ayant une tête de lecture/écriture par piste (ou sur un tambour, ce qui est équivalent du point de vue de l'adressage). La portion d'une piste située à l'intérieur d'un secteur constitue l'unité de mémoire adressable et transférable sur ce type de dispositifs. Pour de plus amples détails on pourra se reporter, à titre d'exemple, à [1].

C'est dans cet environnement "hardware" que sont définies les stratégies que cette étude se propose d'analyser. Nous considérerons l'espace adressable N d'un programme comme un ensemble de n pages : $N = \{p_1, ..., p_n\}$
A ce programme sont attribuées m (m < n) pages physiques en mémoire centrale
Pendant l'exécution, un "défaut de page" se produit lorsqu'une page non
présente en mémoire centrale est référencée par le programme. Si les m pages
physiques ne sont pas toutes occupées, la page demandée est alors transférée
vers l'une d'entre elles, choisie de manière quelconque ; sinon un "algo-
rithme de remplacement de page "(ARP) détermine celle des m pages physiques
qui recevra la page demandée. Ce transfert doit être précédé d'un transfert
- en sens inverse - de la page qui occupait l'emplacement physique sélectionné,
au moins si cette page a été modifiée. Lorsque les seuls instants où une
décision de remplacement de page peut être prise sont ceux des défauts de
page, l'ARP est dit "à la demande".

Il est clair que l'influence des défauts de page sur l'efficacité
du système est particulièrement néfaste. Pendant les transferts évoqués
ci-dessus, l'exécution du programme ayant subi un défaut de page doit être
suspendue. Du point de vue de l'usager la durée totale de ces suspensions
est un élément primordial du temps de réponse. Le nombre de programmes
traités par le calculateur dans un temps donné est lui aussi très sensible
à une augmentation du taux de défauts de page, même si le système d'exploi-
tation est multiprogrammé. Dans ce cas, en effet, si le taux de défauts de
page de chacun des programmes qui se partagent l'unité centrale est élevé,
il en est de même de la probabilité que tous ces programmes soient suspendus
et donc que l'unité centrale soit inactive. En outre, le trafic sur les
canaux a pour conséquence des vols de cycles-mémoire qui affaiblissent
la vitesse d'exécution du calculateur. Enfin, le temps de calcul nécessaire
au traitement de ces défauts de page par le moniteur peut devenir important.
Pour limiter ces inconvénients, des travaux ont été menés dans deux direc-
tions :

- minimisation du taux de défauts de page. Les ARP conçus dans
ce but s'efforcent de remplacer la page dont la présence en mémoire centrale
sera inutile jusqu'à la date la plus éloignée [2].

- minimisation du temps de réponse du disque. Ce délai peut être réduit par l'utilisation de disques à têtes fixes, à secteurs [3] [4].

Le but de la présente étude est d'analyser des stratégies globales d'allocation de la mémoire hiérarchisée qui concilient les exigences parfois contradictoires de la gestion de mémoire centrale et de celle des mémoires secondaires rotatives.

## I.2. - LA GESTION SIMULTANÉE DES DISQUES ET DE LA MEMOIRE CENTRALE

Dans un système à mémoire virtuelle, il est important d'améliorer le temps de réponse, à temps de calcul donné. Il est donc naturel de choisir pour critère d'optimisation :

$$ \eta = \frac{e}{e + T} $$

où e est le temps moyen entre deux défauts de page consécutifs et T le temps moyen de suspension d'un programme à la suite d'un défaut de page. Cette grandeur peut encore s'écrire :

$$ \eta = \frac{1}{1 + FT} $$

où $F = \frac{1}{e}$ désigne le taux de défauts de page. La maximisation de $\eta$ équivaut à la minimisation de $FT$. Les études de gestion de disques que nous avons citées ont pour but la minimisation de $T$, les études sur les ARP celle de $F$. Or ces optimisations peuvent reposer sur des exigences contradictoires.

Il suffit pour s'en convaincre de considérer le cas suivant : supposons que l'image de la page sélectionnée par un ARP optimisé vienne juste de passer sous la tête de lecture-écriture du disque ; l'attente alors nécessaire contrebalance, et au delà, le bénéfice de l'optimisation du remplacement.

Nous analyserons donc une classe d'ARP qui prennent leurs décisions non seulement en fonction de l'état de la mémoire et du comportement du programme mais aussi, ce qui est nouveau, en fonction d'une prévision du temps de
réponse du disque. L'effet de ces ARP sera évalué selon le critère η précé-
demment défini et comparé avec les méthodes classiques.

I.3. - PLAN DE L'ETUDE

Considérons un système paginé dans lequel chaque page de l'espace
d'adressage N d'un programme a une image fixe sur disque. Cette image corres-
pond à un secteur d'une piste du disque à têtes fixes (voir fig. 1). Consi-
dérons aussi un ARP qui détermine à chaque instant de défaut de page un
ensemble Π<sub>l</sub> de l pages susceptibles d'être remplacées. Supposons qu'à
chaque défaut de page deux transferts entre mémoire centrale et mémoire
secondaire doivent être effectués : le chargement de la page référencée
et le rangement de la page remplacée. Les ARP de la classe que nous considérons
choisissent un élément p<sub>i</sub> de Π<sub>l</sub> qui minimise le temps de réponse du disque,
ce temps étant quasiment identique au temps de suspension du programme.
S'il n'existe aucune corrélation entre la position de l'image de la page
à charger et celle de la page à ranger, il est alors raisonnable de supposer
que toutes les pages de Π<sub>l</sub> ont la même chance d'être sélectionnées par
l'ARP;c'est pourquoi nous considérons dans la deuxième partie le modèle
des ARP avec sélection aléatoire d'un élément de Π<sub>l</sub>.

Dans la troisième partie nous calculons la valeur moyenne du
temps de réponse du disque sous deux politiques. Dans l'une d'elles aucune
page physique n'est réservée comme tempon ce qui contraint à effectuer le
rangement d'une page avant le chargement de la page référencée. Dans l'autre
politique une telle réservation est effectuée, ce qui lève cette contrainte
mais à l'inconvénient de diminuer l'espace physique dans lequel le programme
peut s'exécuter.

Le modèle considéré ignore les files d'attente au niveau du disque.
Il sera donc apte à décrire les systèmes monoprogrammés à mémoire virtuelle
ainsi que les systèmes dans lesquels la charge des disques est légère.
## II - LES ALGORITHMES DE REMPLACEMENT DE PAGE ALEATOIRES

### A PRECHARGEMENT PARTIEL (A R P A P P')

De manière informelle un ARPAPP est un ARP à la demande ayant les deux propriétés suivantes :

- une partie $\mathcal{I}_k^\infty$ à k éléments ($k < m$) de l'espace adressable N du programme est toujours résidente en mémoire (préchargement partiel).

- lors d'un défaut de page chacune des $A (= m-k)$ pages chargées en mémoire mais n'appartenant pas à $\mathcal{I}_k^\infty$ a la probabilité $1/\ell$ d'être désignée comme page à remplacer (ARP aléatoire).

Reprenant l'étude faite par l'un des auteurs [5], nous allons définir précisément les ARPAPP en utilisant la notion d'automate stochastique. Nous donnerons ensuite un aperçu des propriétés de cette classe d'algorithmes. Une telle analyse suppose que l'on ait fait choix d'un modèle de comportement de programme : en l'occurrence ce sera le modèle à références indépendantes qui a déjà été utilisé dans [2] et [6].

### II.1 - LE MODELE DE PROGRAMME A REFERENCES INDEPENDANTES

#### Définition 1

Une chaîne de références à des pages est une suite d'éléments de l'ensemble N des pages du programme.

La chaîne de références à des pages

$$x = P_{r_1} P_{r_2} \dots P_{r_t} \dots$$

pourra être considérée comme une réalisation d'un processus stochastique discret $\{R_t\}_{t=1,2,\dots}$, $R_t$ étant une variable aléatoire à valeurs dans N.
## Définition 2

Le comportement de programme est dit à références indépendantes si le processus stochastique {$R_t$} a les trois propriétés suivantes :

(I) Pour toute paire d'entiers positifs distincts s et t, les variables aléatoires $R_s$ et $R_t$ sont indépendantes.

(II) Toutes les variables aléatoires $R_t$ ont la même distribution. Pour tout $t \ge 1$ et tout $1 \le i \le n$ nous noterons :

$$ \text{Prob} [R_t = p_i] = \beta_i $$

(III) Pour tout $1 \le i \le n$, $\beta_i \ne 0$

Statistiquement, la probabilité $\beta_i$ peut être interprétée comme le pourcentage des références qui, au cours d'une longue période, concernent la page $p_i$. Un tel modèle ne tient pas compte de la localité d'un programme mais seulement de l'importance relative -en durée totale d'exécution- de chacune de ses parties.

## II.2. DEFINITION FORMELLE DES ARPAPP

Considérons une mémoire centrale de m pages ($m \le n$)

### Définition 3

Un état de mémoire est une partie à m éléments de N. L'ensemble des états de mémoire sera noté $S_m$.

### Définition 4

Un ARP est le système

$$ B = (S, Q, N, s_0, q_0, \{M(n)\}) $$

où

$S$ est une partie non vide de $S_m$

$Q$ est un ensemble fini d'états de contrôle

$N$ est l'ensemble à n éléments des pages du programme

$s_0$, élément de S, est l'état initial de la mémoire
$q_0$, élément de Q, est l'état de contrôle initial.

{M(r)} est une famille à n éléments, indexée par {1,2,...,n},
de matrices stochastiques d'ordre $|S| \cdot |Q|$ (1)

Chaque paire (s,q) de SxQ est appelée une configuration. A
chaque configuration (s,q), nous attacherons un entier distinct i = g(s,q)
de sorte que 1 ≤ i ≤ |S| . |Q| et que g(s₀, q₀) = 1. La famille {M(r)} peut
être interprétée de la manière suivante. Pour toute page pᵣ de N, désignons
par mᵢⱼ(r) le terme général de la matrice M(r). Si le programme référence
la page pᵣ et que B se trouve dans la configuration (s,q) telle que g(s,q)=i,
la probabilité que la nouvelle configuration soit (s',q') telle que g(s',q')=j
est égale à mᵢⱼ(r).

Soit $x = p_{r_1} p_{r_2} \cdots p_{r_t} \cdots$ une chaîne de références. L'ARP B répond à x en passant par une suite de configurations

$y_1, y_2, \dots, y_t, \dots$

telle que

$$
\text{Prob} \left[ g(y_1) = j \mid (s_0, q_0), p_{r_1} \right] = m_{1j}(r_1) \quad (1)
$$

et

$$
\mathrm{Prob} \left[ g(y_{t+1}) = j \mid g(y_t) = i, p_{r_{t+1}} \right] = m_{ij}(r_{t+1}) \quad (2)
$$

$(1 \le i,j \le |S| \cdot |Q|, t \ge 1)$

Dans le cas particulier que nous considérons où le programme se
comporte selon le modèle à références indépendantes, la suite $y_1, y_2, \dots, y_t$
est une chaîne de Markov dont les états sont les configurations de B. En
effet compte tenu de l'indépendance des variables aléatoires $R_t$, il résulte
de (1) et (2) :

$$
\begin{align*}
& \text{Prob} [g(y_{t+1}) = j | g(y_t) = i, y_{t-1}, \dots, y_2, y_1, (s_0, q_0)] \\
& = \text{Prob} [g(y_{t+1}) = j | g(y_t) = i]
\end{align*}
$$

<footnote>(1) $|X|$ désigne le cardinal de l'ensemble X.</footnote>
La matrice de transition de cette chaîne de Markov est une matrice
carréeC d'ordre $|S| \cdot |Q|$. Son terme général $c_{ij}$, défini comme étant
$\text{Prob } [g(y_{t+1}) = j | g(y_t) = i]$, est égal à $\sum_{r=1}^{n} \beta_r \cdot m_{ij}(r)$

Définition 5

Un ARP est dit "à la demande" si pour tous i = g(s,q) et j = g(s',q')
tels que $m_{ij}(r) \neq 0$ et $p_r \notin S$, $p_r$ est le seul élément de s' qui n'appartient
pas à s.

Définition 6

Soient k un entier tel que $0 \le k \le m-1$ et $\mathcal{Y}_k$ une partie à k éléments de N. L'ARP aléatoire à préchargement partiel de $\mathcal{Y}_k$ (ARPAPP) est un ARP ayant les trois propriétés suivantes :

$$
a) S = \{s \mid s \in S_m \text{ et } \mathcal{Y}_k \subset s\}
$$

$$
b) \mathcal{Q} = \{q_0\}
$$

c) Pour tous s et s' appartenant à S et toute page p<sub>r</sub> de N, les entiers i et j étant respectivement égaux à g(s,q<sub>0</sub>) et g(s',q<sub>0</sub>) :

$$
m_{ij}(r) = \begin{cases}
1 & \text{si } i=j \text{ et } p_r \in s \\
\frac{1}{m-k} & \text{si } p_r \notin s \text{, } p_r \notin s \text{ et } p_r \text{ est la seule page de } s \text{ qui n'appartient pas à } s \\
0 & \text{sinon}
\end{cases}
$$

Un ARPAPP a donc un seul état de contrôle et par suite les matrices
$M_{(r)}$ sont d'ordre $|S|$. Nous appelerons k l'ordre de l'ARPAPP. La classe des
ARPAPP d'ordre k a $C_n^k$ éléments.

Remarquons que ces algorithmes sont des algorithmes de remplacement
à la demande.
II.3. TAUX DE DEFAUTS DE PAGE DES ARPAPP

Dans un ARP à la demande une transition de la configuration (s,q)
à la configuration (s',q') est appelée transition avec défaut de page si
s ≠ s'.

Considérons à nouveau la suite de configurations

y₁, y₂, ..., y_t, y_{t+1}, ..., y_w, ...

qu'un ARP produit en réponse à une chaîne de références. Soit y₀ = (s₀, q₀) ;
pour tout entier $t>1$ définissons $f_t(s,q)$ par

$$
f_t(s,q) = \begin{cases} 1 & \text{si la transition de } y_{t-1} \text{ à } y_t \text{ est une transition avec défaut de page et } y_t = (s,q) \\ y_t & \text{sinon} \end{cases} \\
\text{Soit } N_W(s,q) = \sum_{t=1}^{W} f_t(s,q)
$$

Démonstration 7

Le taux de défaut de page moyen pour l'ARP B est

$$
F(B) = \sum_{(s,q) \in S \times Q} \left[ \lim_{W \to \infty} E \left\{ \frac{N_W(s,q)}{W} \right\} \right]
$$

sous réserve que les limites existent.

Si le programme a un comportement à références indépendantes, ce
taux de défauts de page peut être exprimé plus simplement. Si la matrice de
transition C de la chaîne de Markov {R_t} est irréductible et apériodique,
il existe un vecteur ligne unique ξ dont la somme des composantes est égale
à 1 et tel que

$\xi . C = \xi$

La ième composante, ξ(i), est la probabilité qu'en "régime station-
naire" l'ARP B soit dans la configuration (s,q) telle que g(s,q) = i.
## Proposition

Soit $T(i)$ l'ensemble d'entiers

$T(i) = \{j \mid i = g(s,q), j = g(s'q') \text{ et la transition de } (s,q) \text{ à } (s',q') \text{ est une transition avec défaut de page}\}$

Si la matrice C est régulière et apériodique, alors

$$F(B) = \sum_{i=1}^{|S|} \xi(i) \sum_{j \in T(i)} C_{ij}$$

pour tout ARP à la demande B, le programme ayant un comportement à références indépendantes.

Si nous particularisons encore le problème pour limiter notre attention aux ARPAPP nous parvenons au théorème suivant.

## Théorème

Considérons un programme dont l'ensemble des pages est $N = \{p_1, \dots, p_n\}$ et dont le comportement est représenté par le modèle à références indépendantes, la probabilité de référencer la ième page étant notée $\beta_i (i= 1,2,\dots,n)$. Soit B un ARPAPP maintenant en mémoire les pages de la partie $\varphi_k = \{p_1, \dots, p_k\}$ de N. Alors :

$$F(B) = \frac{\sum_{s \in S} \beta_{i_k+1} \beta_{i_k+2} \dots \beta_{i_m} p_1 \in S \beta_1}{\sum_{s \in S} \beta_{i_k+1} \beta_{i_k+2} \dots \beta_{i_m}}$$

où

$$s = \{p_1, p_2, \dots, p_k, p_{k+1}, p_{k+2}, \dots, p_m\} \text{ si } 1 \le k \le m-1$$

et

$$s = \{p_{i_1}, p_{i_2}, \dots, p_{i_m}\} \quad \text{si } k = 0$$

Nous ne démontrerons ni ce théorème ni la proposition qui le précède. Cette étude est exposée en détail dans [5].
## II.4. LES ARPAPP OPTIMAUX

Considérons un programme s'exécutant dans une zone de mémoire centrale de taille m. Parmi les ARPAPP d'ordre k, il en est un -que nous noterons $B_0(k,m)$- pour lequel le taux de défauts de page est minimum : c'est celui qui maintient en mémoire l'ensemble $\{\omega_k\}$ formé des k pages de N ayant les plus fortes probabilités d'être référencées. Ce résultat (qui ne choque pas l'intuition) est démontré dans [7].

La classe des ARPAPP est d'autant plus intéressante à considérer qu'elle contient deux algorithmes "extrêmes" :

- l'algorithme $B_0(0,m)$ est l'algorithme RAND : la page à remplacer est choisie "au hasard". Cet algorithme semble bien être le plus mauvais de ceux qu'on puisse songer à implanter. Son taux moyen de défauts de page est égal à celui de FIFO [5].

- l'algorithme $B_0(m-1, m)$ est l'algorithme $A_0$ de Denning-Chen-Schelder. De tous les ARP à la demande c'est celui qui cause le plus faible taux moyen de défauts de page [2].

Gardons toutefois à l'esprit que les résultats rapportés dans ce paragraphe sur les performances relatives de divers ARP sont fortement liés à la manière dont nous avons choisi de représenter le comportement des programmes.
# III - GESTION DU DISQUE DE PAGINATION

## III.1. INTRODUCTION

Nous nous proposons de calculer le temps de service moyen du disque à têtes fixes en réponse à une requête de page. La requête de page provoquée par un défaut de page du programme en cours d'exécution en unité centrale donne lieu à deux opérations :

- chargement en mémoire centrale, à partir du disque, de la page demandée.

- déchargement d'une page de la mémoire centrale pour libérer l'espace nécessaire à la page requise.

(ces deux opérations sont exécutées dans un certain ordre, précisé ultérieurement en fonction des hypothèses d'étude).

Le calcul est conduit en fonction du paramètre $\ell$, nombre des pages candidates au remplacement à l'instant de la requête, notées $p_1, p_2, \dots, p_\ell$.

Les hypothèses générales suivantes sont retenues :

### Hypothèse 1 :

L'image physique d'une page sur le disque est fixe. Lorsqu'une page est déchargée de la mémoire centrale elle reprend sur le disque la place qu'elle y occupait avant son chargement en mémoire centrale.

### Hypothèse 2 :

Le disque de pagination est à têtes fixes et caractérisé par :

$S$ = nombre de secteurs

$T$ = période de révolution

$a = \frac{T}{S}$ = durée de défilement d'un secteur

$\alpha = S^{-1}$

Le secteur de piste a une taille suffisante pour recevoir une page. La commutation lecture-écriture peut être effectuée dans l'intervalle de temps séparant le passage de la fin d'un secteur du passage du début du
secteur suivant.

**Hypothèse 3 :**

Les positions sur le disque des pages $p_i$, $1 \le i \le l$, candidates au remplacement, sont indépendantes de la position sur le disque de la page requise.

**Hypothèse 4 :**

La répartition des pages du programme sur les différentes secteurs du disque est uniforme. Posons

$n_i$ = nombre de pages ayant leur image sur le secteur i. La distribution de la variable $(n_1, n_2, ..., n_S)$ est multinominale, avec

$$ \text{Prob} \{n_1 = x_1, \dots, n_S = x_S\} = \frac{n!}{x_1! \dots x_S!} \frac{1}{S^n} \\ (n = \sum_{i=1}^{S} n_i \text{ nombre de pages du programme}). $$

**Hypothèse 5 :**

Le secteur sur lequel se trouve la tête de lecteur-écriture à l'instant de la requête n'est accessible qu'après une révolution complète du disque. Au même instant, la position de la tête sur le secteur y est uniformément répartie.

## Notations

Les notations du chapitre précédent sont utilisées chaque fois qu'elles n'entraînent aucune ambiguïté. On pose de plus :

$Q$ = page requise

$L_j$ = nombre de secteurs séparant le secteur où se trouve la tête de lecture de celui où se trouve l'image de $p_j$, à l'instant de la requête ($j = 1...l$)

$D$ = même définition que ci-dessus en remplacant $p_j$ par $Q$
Pour faciliter les calculs ultérieurs les indices de secteurs sont à valeur dans les S classes d'entiers modulo S : i et i+S désignent alors le même secteur.

Les résultats sur les temps de service moyen du disque de pagination sont obtenus pour les deux configurations suivantes :

1 - mémoire centrale sans page tampon. On doit recopier une des pages $p_j$ avant de charger Q

2 - mémoire centrale avec une page tampon : les deux opérations de chargement de Q et de déchargement de $p_j$ peuvent être exécutées dans un ordre quelconque.

### III.2. CALCUL DU TEMPS MOYEN DE SERVICE SANS TAMPON R<sub>ST</sub>

Pour toute valeur d de D deux évènements exclusifs et exhaustifs sont à considérer :

i) $E_1(d) : \exists j \in \{1,...,l\} \text{ tel que } L_j \le d-1$

i-1

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

L'évènement $E_1(d)$, représenté sur la figure est l'évènement favorable. Le temps réponse du disque compte-tenu du déplacement angulaire moyen des têtes sur le secteur où elles se trouvent à l'instant de la requête (voir l'hypothèse 5) est :

$$t_1(d) = \frac{2d + 3}{2} a$$
ii) $E_2(d) : \forall j \in \{1, \dots, \ell\} \quad L_j \ge d$

i-1

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

Le temps de service moyen est alors :

$$t_2(d) = \frac{2S + 2d + 3}{2} a$$

Calcul des probabilités des évènements $E_1(d)$ et $E_2(d)$

On a :

$$\mathrm{Pr} [E_1(d)] + \mathrm{Pr} [E_2(d)] = \mathrm{Pr} [E_1(d) \cup E_2(d)] = \mathrm{Pr} [D=d]$$

et l'on obtient :

$$ \begin{align*} \mathrm{Pr} [D=d] &= \sum_{i=1}^{S} \mathrm{Pr} [I] \mathrm{Pr}[d|I] \\ &= \sum_{i=1}^{S} \alpha \frac{m_{i+d}}{n} = \alpha \end{align*} $$

Il suffit donc de calculer $\mathrm{Pr}[E_2(d)]$.

$$\mathrm{Pr} [E_2(d)] = \sum_{i=1}^{S} \mathrm{Pr} [A] \times \mathrm{Pr} [B]$$

A = {la tête de lecture se trouve sur le secteur i-1 lors de la requête}

B ={l'image de Q est sur i+d ; les pages p_j sur i + d, ou
i+ d + 1,......, ou i + S - 1}
Explicitons $\Pr[B]$.

$\Pr[B] = \Pr[\text{image de Q sur } i + d]$

$\times \Pr[P_1 \text{ sur } i + d \text{ ou } i + d + 1 \text{ ou } \dots \text{ou } i + 5 - 1 \mid \text{Q sur } i + d]$

$\times \Pr[P_j \text{ sur } i + d \text{ ou } i + d + 1 \text{ ou } \dots \text{ou } i + S - 1 \mid \text{Q sur } i + d$;
$P_1, P_2, \dots, P_{j-1} \text{ sur } i + d \text{ ou } i + d + 1 \dots \text{ou } i + S-1]$

$\times \Pr[P_\ell \text{ sur } i + d \text{ ou } i + d + 1 \text{ ou } \dots \text{ou } i + S - 1 \mid \text{Q sur } i + d$;
$P_1, P_2, \dots, P_{\ell-1} \text{ sur } i + d \text{ ou } i + d + 1 \dots \text{ou } i + S - 1]$

$$ \Pr[B] = \frac{n_{i+d}}{n} \times \frac{n_{i+d} + n_{i+d-1} + \dots + n_{i+S-1}}{n-1}^{-1} $$

$$ \times \frac{n_{i+d} + n_{i+d-1} + \dots + n_{i+S-1} - j}{n-j} $$

$$ \times \frac{n_{i+d} + n_{i+d-1} + \dots + n_{i+S-1} - \ell}{n-\ell} $$

On en déduit, en remarquant que $\Pr[A] = \alpha$,

$$ \Pr[E_2(d) | n_1, \dots, n_S] = \sum_{i=1}^{S} \alpha \frac{n_{i+d}}{n} e_i $$

$$ \text{où } e_i = \begin{cases} 0 & \text{si } \sum_{r=d}^{S-1} n_{i+r} < \ell+1 \\ \frac{S-1}{\sum_{r=d}^{S-1} n_{i+r} - 1} & \text{! } (n-\ell-1) \text{ !} \\ \frac{S-1}{\sum_{r=d}^{S-1} n_{i+r} - \ell - 1} & \text{! } (n-1) \text{ !} \end{cases} \quad \text{sinon} $$
En utilisant l'hypothèse 4, $\Pr[E_2(d)]$ s'écrit :

$$ \Pr[E_2(d)] = \sum_{i=1}^{S} \frac{n_{i+d}}{n} \sum_{*} \frac{\left( \sum_{r=d}^{S-1} n_{i+r}^{-1} \right) ! \left( n-\ell-1 \right) !}{S-1} \times \frac{n!}{n_1! n_2! \dots n_S!} \times \frac{1}{S^n} $$

la sommation $\sum_{*} \ell$ étant étendue à tous les S-uples $(n_1, n_2, \dots, n_S)$ d'entiers non-négatifs tels que

$$ \sum_{i=1}^{S} n_i = n, $$

les entiers $n_{i+d}$, $n_{i+d+1}$, ..., $n_{i+S-1}$ vérifiant en outre

$$ \sum_{r=d}^{S-1} n_{i+r} \ge \ell+1 $$

En modifiant l'arrangement des termes $\Pr[E_2(d)]$ devient :

$$ \Pr[E_2(d)] = \alpha \sum_{i=1}^{S} \frac{(n-\ell-1)!}{S^n n!} \sum_{*} n_{i+d} \frac{\sum_{r=d}^{S-1} n_{i+r}^{\ell-1}!}{S-1} \frac{n!}{n_1! n_2! \dots n_S!} $$

Le lemme suivant, démontré en appendice., permet d'évaluer l'expression précédente.

**Lemme :**

Soit $(y_1, y_2, \dots, y_p, y_{p+1}, \dots, y_S)$ une permutation de $(1, 2, \dots, S)$.

Soit $E$, fonction de $n$, $\ell$, $S$, $p$ et $(y_1, y_2, \dots, y_p)$, la quantité :

$$ \sum_{i=1}^{S} \frac{(n-\ell-1)!}{S^n n!} \sum_{*} n_{i+y_1} \times \frac{\left( n_{i+y_1} + n_{i+y_2} + \dots + n_{i+y_{p-1}} \right)!}{\left( n_{i+y_1} + \dots + n_{i+y_p} - \ell - 1 \right)!} \times \frac{n!}{n_1! n_2! \dots n_S!} $$

la sommation $\sum_{*} \ell$ étant étendue aux S-uples d'entiers non-négatifs $(n_1, n_2, \dots, n_S)$ tels que

$$ \sum_{i=1}^{S} n_i = n, $$
les entiers non-négatifs $n_{i+y_1}, \dots, n_{i+y_p}$ vérifiant en outre

$$ \sum_{j=1}^{p} n_{i+y_j} \ge l+1 $$

Alors

$$ E = (\mathbb{P}_S)^l $$

L'application du lemme au calcul de $\mathrm{Pr}[E_2(d)]$ est immédiate, en faisant $p = S-d$; d'où :

$$ \mathrm{Pr} [\bar{E}_2(d)] = \alpha \left(\frac{S-d}{S}\right)^l = \alpha (1 - \alpha d)^l $$

par suite,

$$ \mathrm{Pr} [\bar{E}_1(d)] = \alpha - \mathrm{Pr} [\bar{E}_2(d)] = \alpha [1 - (1 - \alpha d)^l] $$

Temps de service moyen du disque

$$ R_{ST} = \sum_{d=0}^{S-1} \{t_1(d) \times \mathrm{Pr} . [\bar{E}_1(d)] + t_2(d) \times \mathrm{Pr} . [\bar{E}_2(d)]\} $$

$$ R_{ST} = a \sum_{d=0}^{S-1} \left\{ \frac{2d+3}{2} \alpha [1-(1-\alpha d)^l] + \frac{2S+2d+3}{2} \alpha (1-\alpha d)^l \right\} $$

et finalement

$$ R_{ST} = T \left[ \frac{S+4}{2S} + \frac{1}{S} \sum_{i=1}^{S-1} \left( \frac{i}{S} \right)^l \right] $$

Remarques

Le résultat obtenu est indépendant de n, taille du programme considéré. Les conclusions sont donc indépendantes des caractéristiques des programmes des utilisateurs du système, et ne dépendent que de ses données techniques.

Lorsque $l$ tend vers l'infini, $R_{ST}$ tend vers la limite $T$. $\frac{S+4}{2S}$. Pour $S=3$, cette limite est atteinte à 1% près dès que $l$ est supérieur à 8, à 10 % près dès que $l$ est supérieur à 2.
### III.3 CALCUL DU TEMPS MOYEN DE SERVICE AVEC TAMPON

Dans ce cas, à chaque défaut de page, on choisit celle des deux stratégies suivantes qui minimise le temps de service.

#### i) Stratégie sortie-entrée

Parmi les $ℓ$ pages candidates au remplacement, on recopie sur le disque celle dont l'image passe la première sous la tête. On charge ensuite la page requise dans l'emplacement libéré.

#### ii) Stratégie entrée-sortie

La page requise est chargée dans le tampon. On recopie ensuite sur le disque une des pages candidates. L'emplacement libéré devient le nouveau tampon.

On est amené à considérer le système exhaustif d'évènements deux à deux exclusifs, représenté dans le tableau ci-dessous :

<table><thead><tr><th></th><th>DEFINITION</th><th>STRATEGIE CHOISIE</th><th>TEMPS DE SERVICE</th></tr></thead><tbody><tr><td>E<sub>β</sub>(d)</td><td>∃j ∈ {1,...,ℓ} : L<sub>j</sub> ≤ d-1</td><td>S-E</td><td>2d+3/2 a</td></tr><tr><td>E<sub>β</sub>(d)</td><td>∃j ∈ {1,...,ℓ} : L<sub>j</sub> = d+β<br>ET<br>L<sub>j</sub> ≥ d+β</td><td>E-S</td><td>3+2(d+β)/2 a</td></tr><tr><td>β ∈ {1,...,S-d-1}</td><td>∀j ∈ {1,...,ℓ} : OU<br>L<sub>j</sub> = d</td><td></td><td></td></tr><tr><td>E<sup>*</sup>(d)</td><td>∀j ∈ {1,...,ℓ} : L<sub>j</sub> = d</td><td>Indifférente</td><td>2d+3+2S/2 a</td></tr></tbody></table>
Calcul des probabilités des évènements $E_0(d)$, $E_β(d)$, $E^*(d)$

Evènement $E_0(d)$

L'évènement $E_0(d)$ est semblable à l'évènement $E_1(d)$ étudié précédemment.

$$ \mathrm{Pr} [E_0(d)] = \alpha [1 - (1-d\alpha)^\beta] $$

Evènements $E_β(d)$ ($β = 1, ..., S-d-1$)

Pour tous triplets d'entiers $(β, i, d)$ satisfaisant aux conditions :

$$ 0 \le d \le S-1 $$

$$ 1 \le i \le S $$

$$ 1 \le \beta \le S-d $$

définissons l'évènement $A_i^β(d)$ :

$$ A_i^β(d) = \left[ \bigcup_{j \in \{1, \dots, l\}} V_j \right] $$

l'image de $p_j$ est sur le secteur $i+d$, ou sur un secteur de numéro $i+γ$, avec $d+β \le γ \le S-1$, la tête de lecture étant sur le secteur $i-1$.

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

Y

Sur la figure sont hachurés les secteurs du disque ne pouvant contenir d'image des $p_j$, suivant la définition de l'évènement $A_i^β(d)$.
Pour calculer la probabilité de l'évènement $E_β(d)$, remarquons que,
d étant donné, l'évènement complémentaire de $A_i^{β+1}(d)$, $1 \le β \le S-d-1$, s'énonce
ainsi :

" il existe au moins une page $p_j$ dont l'image n'est ni sur le secteur $i+d$, ni sur aucun des secteurs numérotés $i+γ$, avec $d+β+1 \le γ \le S-1$".

Notons $\neg X$ l'évènement complémentaire de l'évènement X; on en déduit, d étant donné,

$$
A_i^\beta(d) \wedge \neg A_i^{\beta+1}(d) = \left\{ \begin{array}{ll} \exists j \in \{1, \dots, \ell\} & L_j = d + \beta \\ \text{ET} \\ \forall j \in \{1, \dots, \ell\} : & \begin{array}{ll} L_j \ge d + \beta & \\ \text{OU} & \\ L_j = d & \end{array} \end{array} \right\}
$$

et donc :

$$
\mathrm{Pr} \, [E_{\beta}(d)] = \sum_{i=1}^{S} \mathrm{Pr}_{\beta} [A] \times \mathrm{Pr} \, [C]
$$

avec A défini comme précédemment

$$
\text{et } C = \{A_i^\beta (d) \wedge A_i^{\beta+1}(d) \text{ et } D = d\}
$$

Explicitors $\Pr[C]$

$$
\mathrm{Pr} \, [C] = \mathrm{Pr} \, [\text{page Q sur } i+d] \times \mathrm{Pr} \, [A_i^\beta(d) \wedge \neg A_i^{\beta+1}(d) \mid D=d]
$$

Nous pouvons écrire par ailleurs :

$$
\mathrm{Pr} \, [A_i^\beta(d) \wedge \neg A_i^{\beta+1}(d) \mid D=d] + \mathrm{Pr} \, [A_i^\beta(d) \wedge A_i^{\beta+1}(d) \mid D=d] = \mathrm{Pr} \, [A_i^\beta(d) \mid D=d]
$$

et remarquant que $A_i^\beta(d) \wedge A_i^{\beta+1}(d) = A_i^{\beta+1}(d)$, nous obtenons :

$$
\mathrm{Pr} \, [A_i^\beta(d) \wedge \neg A_i^{\beta+1}(d) \mid D=d] = \mathrm{Pr} \, [A_i^\beta(d) \mid D=d] - \mathrm{Pr} \, [A_i^{\beta+1}(d) \mid D=d]
$$

d'où

$$
\mathrm{Pr} [\neg E_{\beta}(d)] = \sum_{i=1}^{S} \alpha \frac{n_i+d}{n} \left( \mathrm{Pr}[A_i^{\beta}(d) | =d] - \mathrm{Pr}[A_i^{\beta+1}(d) | D=d] \right)
$$
Soit :

$$
\mathrm{Pr} [E_{\beta}^{\beta}(d)] = T_{(\beta)} - T_{(\beta+1)} , T_{(\beta)} \text{ défini par}
$$

$$
T_{(\beta)} = \sum_{i=1}^{S} \alpha \frac{n_{i+d}}{n} \quad \text{Pr} [A_i^{\beta}(d) | D=d]
$$

$$
\text{Posons } \sigma = n_{i+d} + n_{i+d+\beta} + n_{i+d+\beta+1} + \dots + n_{i+S-1}
$$

Il vient alors, par un calcul semblable à celui du paragraphe précédent,

$$
\mathrm{Pr} \left[ A_i^\beta (d) \mid D=d ; n_1, n_2, \dots, n_S \right] = \begin{cases} 0 & \text{si } \sigma < \ell + 1 \\ \\ \frac{(\sigma-1) ! (n-\ell-1) !}{(\sigma-\ell-1) ! (n-1) !} & \text{si } \sigma \ge \ell+1 \end{cases}
$$

En utilisant le nouveau l'hypothèse 4, nous pouvons écrire :

$$
\mathrm{Pr} \left[ A_i^\beta (d) \mid D=d \right] = \sum_* \frac{(\sigma-1) ! (n-\ell-1) !}{(\sigma-\ell-1) ! (n-1) !} \times \frac{n !}{n_1 ! n_1 ! n_2 ! \dots n_S !} \times \frac{1}{S^n}
$$

∑ étant étendue aux S-uples d'entiers non-négatifs (n₁, n₂, ..., n_S) vérifiant :

$$
n_{i+d} + n_{i+d+\beta} + n_{i+d+\beta+1} + \dots + n_{i+S-1} \ge \ell+1
$$

et

$$
n_1 + n_2 + \dots + n_S = n
$$

$T_{(\beta)}$ s'écrit alors :

$$
T_{(\beta)} = \alpha \sum_{i=1}^{S} \frac{n_i}{n} \sum_{*} \frac{(\sigma-1) ! (n-\ell-1) !}{(\sigma-\ell-1) ! (n-1) !} \times \frac{n !}{n_1 ! n_2 ! \dots n_S !} \times \frac{1}{S^n}
$$

$$
T_{(\beta)} = \alpha \sum_{i=1}^{S} \frac{(n-\ell-1)!}{S^n n!} \times \sum_{i} \frac{(\sigma-1)!}{(\sigma-\ell-1)!} \times \frac{n!}{n_1! n_2! \dots n_S!}
$$

Nous utilisons le lemme avec dans ce cas $y_1 = d$, $y_2 = d+\beta$,

$y_3 = d+\beta+1, \dots, y_p = S-1$, soit $p = S-d-\beta+1$. D'où

$$
T_{(\beta)} = \alpha \left[ \frac{S-d-1}{S} \right]^{\ell} = \alpha^{\ell+1} \left[ S - (d+\beta)+1 \right]^{\ell}
$$
et par suite :

$$
\mathrm{Pr} [\hat{E}_{\beta}(d)] = \alpha^{\ell+1} \{ [S-(d+\beta)+1]^{\ell} - [S-(d+\beta)]^{\ell} \}
$$

Evènement E*(d)

Considérons l'évènement $A_i^{S-d}(d)$. D'après la définition de $A_i^{\beta}(d)$,
les images des pages $p_j$, $1<j<l$, sont toutes sur le secteur i+d. On en
déduit, comme précédemment :

$$
\mathrm{Pr} [\hat{E}^*(d)] = \sum_{i=1}^{S} \mathrm{Pr} [A] \times \mathrm{Pr} [A_i^{S-d}(d) | D=d]
$$

et par définition de $T_{(\beta)}$

$$
\mathrm{Pr} [\hat{E}^*(d)] = T(S-d)
$$

soit

$$
\mathrm{Pr} [\hat{E}^*(d)] = \alpha^{\ell+1}
$$

Temps de service moyen R<sub>AT</sub> (avec tampon)

Le temps de service moyen $R_{AT}$ est obtenu par les trois sommations correspondant aux trois familles d'évènements, suivant les valeurs de d.

Evènements $E_0(d)$

$$
R_1 = a \alpha \sum_{d=0}^{S-1} \frac{2d+3}{2} \left[ 1 - (1+\alpha d)^\ell \right]
$$

Evènements E<sub>β</sub>(d)

Remarquons en premier lieu que les résultats, pour cette famille
d'évènements, ne dépendent que de β+d. On en déduit, β+d variant entre 1
et S-1,

$$
R_2 = a \alpha^{\ell+1} \sum_{t=1}^{S-1} t \frac{3+2t}{2} \left[ (S-t+1)^{\ell} - (S-t)^{\ell} \right]
$$
## Evènements E*(d)

$$R_3 = a \alpha^{\ell+1} \frac{3S^2 + 2S}{2}$$

$$R_{AT} = R_1 + R_2 + R_3$$

$$R_{AT} = a \alpha \sum_{d=0}^{S-1} \frac{2d+3}{2} \left[1-(1-d\alpha)^{\ell}\right] + \alpha^{\ell+1} \sum_{t=1}^{S-1} t \frac{3+2t}{2} \left[(S-t+1)^{\ell} - (S-t)^{\ell}\right] \\ + \alpha^{\ell+1} \frac{3S^2+2S}{2}$$

## Remarques

Lorsque $\ell$ tend vers l'infini, $R_{AT}$ tend vers la limite

$$T \frac{S^2+2S+2}{2S^2}$$

Cette limite est atteinte à 1% près pour $\ell \ge 8$, à 10% près pour $\ell \ge 2$ lorsque $S=3$.
# IV - RESULTATS NUMERIQUES

## IV.1. INTRODUCTION

Soient m le nombre total de pages physiques allouées au programme et m' le nombre de pages physiques destinées à l'exécution proprement dite : m et m' sont égaux s'il n'est pas réservé de page tampon ; sinon m' = m-1. Les algorithmes de remplacement de page que nous étudions maintiennent constamment en mémoire les k pages ($1 \le k \le m'-1$) ayant les plus fortes probabilités d'être référencées. Lors d'un défaut de page, ils choisissent la page à remplacer parmi les $\ell$ ($\ell = m'-k$) autres pages présentes en mémoire de telle façon que le temps de service du disque soit minimum. Comme nous l'avons expliqué au paragraphe I.3., il est raisonnable d'admettre que chacune de ces pages à la probabilité $1/\ell$ d'être désignée. Le taux de défauts de page des algorithmes que nous considérons est donc celui des ARPAPP optimaux.

L'efficacité du système de pagination sera donc :

$$ \eta_{ST}^{(\ell)} = \frac{1}{1 + F(B_0(m-\ell, m)) \times R_{ST}^{(\ell)}} \quad 1 \le \ell \le m $$

si aucune page n'est réservée comme tampon et :

$$ \eta_{AT}^{(\ell)} = \frac{1}{1 + F(B_0(m-1-\ell, m-1)) \times R_{AT}^{(\ell)}} \quad 1 \le \ell \le m-1 $$

dans le cas contraire.

## IV.2. DETERMINATION DE LA VALEUR OPTIMALE DE $\ell$

Sur la figure 2 est représentée la variation en fonction de $\ell$ du temps moyen de service d'un disque à trois secteurs. L'amélioration apportée par la possibilité de choisir la page à ranger croît rapidement pour les premières valeurs de $\ell$ puis devient presque constante.
La figure 3 montre la variation du taux de défauts de page en fonction de $\ell$, la taille m' de la zone de mémoire réservée à l'exécution du programme étant constante (m' = 13). Trois types de programmes sont considérés qui diffèrent entre eux par la distribution $(\beta_i)_{i=1,...n}$ des probabilités de référence :

- pour le programme à distribution uniforme des références, toutes les probabilités $\beta_i$ sont égales à 1/n.

- pour le programme GEOM (0,95), la distribution $(\beta_i)$ est géométrique tronquée :

$$ \beta_i = C_1 \times (0,95)^i \quad \text{pour } i = 1, \dots, n $$

où

$$ C_1 = \frac{0,05}{0,95(1-(0,95)^{n+1})} = 0,08204 \quad (\text{constante de normalisation}) $$

- pour le programme 999922221111111111, la distribution des probabilités de référence est telle que :

$$ \beta_i = C_2 \times 9 \quad \text{pour } 1 \le i \le 4 $$

$$ \beta_i = C_2 \times 2 \quad \text{pour } 5 \le i \le 8 $$

$$ \beta_i = C_2 \times 1 \quad \text{pour } 9 \le i \le 20 $$

où $C_2$ désigne la constante de normalisation.

On constate, ce qui n'est pas étonnant, que ces courbes sont croissantes. Vantilborgh [7] a d'ailleurs montré que pour $0 \le k \le m'-2$.

$$ 0 \le F(B_0(k,m')) - F(B_0(k+1, m')) < \frac{1}{m'-k} \left(1 - \sum_{i=1}^{n} \beta_i^2\right) $$

La courbe représentant le taux de défauts de page du troisième programme a deux zones de croissance rapide : pour $\ell=6$ (resp. 10) une page dont la probabilité d'être référencée est proportionnelle à 2 (resp. 9) disparaît de l'ensemble $\mathcal{F}_k$ des pages préchargées.
Considérant ces courbes représentant les variations du temps de réponse du disque et du taux de défauts de page, on peut prévoir que les algorithmes que nous étudions seront efficaces pour des petites valeurs de $\ell$. C'est ce que confirment les courbes des figures 4, 5 et 6 qui représentent en fonction de $\ell$ l'amélioration relative d'efficacité:

$$ \frac{n(\ell) - n(1)}{n(1)} $$

L'amélioration relative peut être importante : plus de 23 % pour le programme 99992222111111111111 lorsque $\ell=4$ (figure 4) ; 36 % pour ce même programme lorsque $\ell=6$, une page étant réservée comme tampon (figure 6). L'amélioration relative est généralement plus importante lorsqu'on utilise un tampon ; ceci ne nous livre néanmoins aucun renseignement sur l'utilité de ce tampon puisque les efficacités $\eta_{AT}$ (resp. $\eta_{ST}$) sont comparées entre elles.

Faisant varier la distribution $(\beta_i)_{i=1,...,n}$ la taille du programme et celle de la mémoire ainsi que le nombre des secteurs et la période de rotation des disques, nous avons obtenu quelques centaines de courbes de ce type. Toutes ont un seul maximum. Celui-ci est très souvent atteint pour une valeur de $\ell$ inférieure ou égale à 5. L'efficacité est proche de sa valeur maximum pour $\ell=2$ ou $3$. En outre pour ces deux valeurs, il est rare que les performances soient moins bonnes que pour $\ell=1$. Cela arrive pourtant (cf. figures 7 et 8).

La variation de l'amélioration relative en fonction de la taille de la mémoire est représentée pour $\ell=2$ et $\ell=3$ sur les figures 7 (sans tampon) et 8 (avec tampon).

### IV.3. - UTILITÉ DU TAMPON

De la considération d'un grand nombre de situations correspondant à divers types de programme et différents tailles de mémoire, il n'estort
que le maximum atteint par $n_{AT}(\ell)$ est presque toujours supérieur à celui de $n_{ST}(\ell)$, les valeurs optimales de $\ell$ n'étant pas nécessairement les mêmes dans les deux cas. Cela apparaît par exemple sur les figures 9 et 10.

Il apparaît toutefois difficile de tirer de ces résultats numériques des remarques suffisamment générales. Adoptons par exemple un point de vue "pratique" et choisissons pour $\ell$ une valeur convenable (1, 2 ou 3). On peut alors tracer de courbes analogues à celles des figures 11 à 16 : Elles ne permettent pas de trancher le problème de l'utilité d'un tampon. Tout au plus peut-on remarquer que si la taille de la mémoire est proche de la taille du programme, la réservation d'un tampon est néfaste (à la limite, lorsque $m=n$, il n'y a plus de défauts de page que dans le cas où l'on garde une page physique pour loger le tampon).
# APPENDICE

## Démonstration du Lemme

Réécrivons E en ordonnant la sommation $\sum \ast$ suivant la valeur des sommes $\sigma$,

$$ \sigma = \sum_{i=1}^{n} (i+1)^2 + \dots + n \cdot y_p $$

$$ E = \sum_{i=1}^{S} \frac{(n-l-1)!}{S^n n!} \sum_{*} n_i + y_1 \frac{(n_i + y_1 + \dots + n_i + y_p - l - 1)!}{(n_i + y_1 + \dots + n_i + y_p - l - 1)!} \times \frac{n!}{n_1! n_2! \dots n_S!} $$

$$ E = \sum_{i=1}^{S} \frac{(n-l-1)!}{S^n n!} \sum_{\sigma=l+1}^{n} \frac{(\sigma-1)!}{(\sigma-l-1)!} \sum_{**} \frac{n!}{n_1! n_2! \dots n_S!} $$

la sommation $\sum \ast$ étant étendue à tous les S-uples d'entiers non-négatifs $(n_1, n_2, \dots, n_S)$ tels que :

$$ \sum_{i=1}^{S} n_i = n, $$

les entiers non-négatifs $n_i+y_1, \dots, n_i+y_p$ vérifiant en outre :

$$ \sum_{j=1}^{p} n_i + y_j = \sigma $$

En utilisant la partition de l'ensemble $\{1, \dots, S\}$ en ses deux sous-ensembles :

$$ \{y_1, y_2, \dots, y_p\} $$

et

$$ \{y_{p+1}, \dots, y_S\} $$

les deux conditions précédentes sont équivalentes à

$$ n_i + y_1 + \dots + n_i + y_p = \sigma $$

$$ n_i + y_{p+1} + n_i + y_{p+2} + \dots + n_i + y_S = n - \sigma $$
Soit $E_1(\sigma)$, $E_2(\sigma)$, l'ensemble des solutions entières non-négatives des deux dernières équations. En remarquant qu'on peut toujours écrire :

$$n_1! n_2! \dots n_S! = (n_{i+1}! \dots n_{i+y_1}!) (n_{i+y_1+1}! \dots n_{i+y_S}!)$$

la sommation $\sum_{**}$ se transforme en

$$ \begin{align*} \sum_{**} n! \frac{n_i+y_1}{n_1! n_2! \dots n_S!} &= \sum_{**} n! \frac{n_i+y_1}{n_{i+y_1}! \dots n_{i+y_p}!} \times \frac{1}{n_{i+y_{p+1}}! \dots n_{i+y_S}!} \\ &= n! \sum_{E_1(\sigma)} \frac{n_i+y_1}{n_{i+y_1}! \dots n_{i+y_p}!} \sum_{E_2(\sigma)} \frac{1}{n_{i+y_{p+1}}! \dots n_{i+y_S}!} \end{align*} $$

Rappelons le théorème suivant :

**Théorème:** La somme $\sum_{k_1, k_2, \dots, k_q} \frac{1}{k_1! k_2! \dots k_q!}$, étendue à tous les q-uples (k_1, k_2, \dots, k_q) d'entiers non-négatifs vérifiant :

$$k_1 + k_2 + \dots + k_q = c$$

est égale à : $\frac{c}{c!}$

De ce résultat, connu sous le nom de formule du multinôme, nous déduisons la valeur de chacune des sommes : $\sum_{E_1(\sigma)}$ et $\sum_{E_2(\sigma)}$ :

$$\sum_{E_2(\sigma)} \frac{1}{n_{i+y_p}! \dots n_{i+y_S}!} = \frac{(3-p)^{n-\sigma}}{(n-\sigma)!}$$

$$\sum_{E_1(\sigma)} \frac{n_{i+y_1}}{n_{i+y_1}! \dots n_{i+y_p}!} = \sum_{E_1(\sigma)} \frac{1}{(n_{i+y_1}-1)! \dots n_{i+y_p}!} = \frac{p^{\sigma-1}}{(\sigma-1)!}$$
Revenant à E, nous obtenons :

$$
E = \sum_{i=1}^{S} \frac{(n-l-1)!}{S^n n!} \sum_{\sigma=l+1}^{n} \frac{(\sigma-1)!}{(\sigma-l-1)!} \frac{n! (S-p)^{n-\sigma}}{(n-\sigma)! (\sigma-1)!} \quad \text{p.s.}
$$

$$
E = \sum_{i=1}^{S} \frac{(n-l-1)!}{S^n} \sum_{\sigma=l+1}^{n} \frac{1}{(\sigma-l-1)!(n-\sigma)!} (S-p)^{n-\sigma} p^{\sigma-1}
$$

Regroupons les termes de façon à faire apparaître le terme général
du développement selon la formule du binôme de :

$$
[(S-p)+p]^{n-l-1} = \sum_{q=0}^{n-l-1} C_{n-l-1}^{q} (S-p)^{n-l-1-q} p^{q} = \sum_{q=l+1}^{n} C_{n-l-1}^{q} (S-p)^{n-q} p^{l-q-1}
$$

$$
E = \sum_{i=1}^{S} \frac{p^i}{S^n} \sum_{\sigma=l+1}^{n} \frac{(n-l-1)!}{(\sigma-l-1)!(n-\sigma)!} = (S-p)^{n-\sigma} \sigma^{l-1} = \sum_{i=1}^{S} \frac{2^i}{S^n} [(S-p)+p]^{n-l-1}
$$

finalement :

$$
E = \sum_{i=1}^{S} \frac{p^i}{S^{l-1}} = \frac{p^l}{S^l}
$$
REFERENCES

[1] Mémoires auxiliaires à disques magnétiques DIAD - CII manuel C 90097 9B

[2] A.V. AHO, P. DENNING, J.D. ULLMAN : Principles of optimal page replacement JACM vol 18 n° 1 - janvier 1971.

[3] A. WEINGARTEN : The Eschenbach drum scheme - CACM vol 9 n° 7 - juillet 1966

[4] E.G. COFFMAN, Jr. : Analysis of a drum input/output queue under scheduled operation in a paged computer system - JACM vol 16 n° 1 - janvier 1969

[5] E. GELENBE : A unified approach to the evaluation of a class of replacement algorithms - Rapport de Recherche No. 5, IRIA-LABORIA, 1972.

[6] W.F. KING III : Analysis of demand paging algorithms - proc. of the I.F.I.P. congress 1971 - North Holland Publishing Company.

[7] H. VANTILBORGH : On random partially pre-loaded page replacement algorithms - Report R 202, MBLE Bruxelles.
<figure><img src="image_8.png" /><figcaption>FIGURE N° 1</figcaption></figure>
<figure><img src="image_9.png" /><figcaption>FIGURE N° 2</figcaption></figure>
<figure><img src="image_10.png" /></figure>

FIGURE N° 3
<figure><img src="image_11.png" /><figcaption>FIGURE N° 4</figcaption></figure>
<figure><img src="image_12.png" /></figure>

FIGURE N° 4
<figure><img src="image_13.png" /></figure>

Modèle de programme
9999 2222 1111111111

(20 pages)
échantillon échantillon

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

+0.5

0

-0.5

l-3

l-2

Sans tampon

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

5

10

15

20

25

taille

de la

côneure
Amélioration relative

Programme : 25 pages

<figure><img src="image_16.png" /><figcaption>FIGURE n° 8</figcaption></figure>
<figure><img src="image_17.png" /></figure>

Programme : 20 pages
GEOM (0.95)

disque : S=3
T=40 000

Taille de la mémoire :
15 pages

A.T.

S.T.

Taille de la
mémoire : 10 pages

S.T.

FIGURE N° 9
<figure><img src="image_18.png" /></figure>

FIGURE N° 10
<figure><img src="image_19.png" /></figure>
<figure><img src="image_20.png" /></figure>

FIGURE N° 12
<figure><img src="image_21.png" /></figure>

FIGURE N° 19
<figure><img src="image_22.png" /></figure>

FIGURE N° 14
<figure><img src="image_23.png" /></figure>
<figure><img src="image_24.png" /></figure>