IRIA
laboria

laboratoire de recherche
en informatique
et automatique

# Etude du comportement d'un tambour soumis à des demandes de transfert groupées

Gérard Baudet

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

Institut de Recherche
d'Informatique
et d'Automatique

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

Rapport de Recherche n° 30

Septembre 1973
ETUDE DU COMPORTEMENT D'UN TAMBOUR
SOUMIS A DES DEMANDES DE TRANSFERT GOUPÉES*

Gérard Baudet

(Présenté par C. Kaiser)

RÉSUMÉ

La gestion efficace d'un tambour magnétique, ou d'un disque à têtes fixes, comme mémoire secon-
daire, constitue un problème important dans les systèmes de multiprogrammation. L'unité de trans-
fert entre un tel périphérique et la mémoire principale est le secteur. Une demande de transfert peut
s'adresser à un secteur (demande de transfert élémentaire ou requête simple) ou à plusieurs secteurs,
non nécessairement consécutifs (demande de transfert groupée).

Un modèle mathématique a été défini par E.C. Coffman, Jr. dans le cas où les demandes de transfert parviennent sous forme de requête simple (cas d'un système géré suivant une politique de page à la demande) ; cet article présente une généralisation au cas où les demandes de transfert parviennent par groupe (cas d'un système utilisant le préchargement ou basé sur la segmentation).

La description du modèle et son analyse mathématique complétée par une simulation permettent de
dégager certains résultats concernant l'utilisation d'un tambour (en tant que mémoire auxiliaire) géré
suivant cette politique.

ABSTRACT

An important element in multiprogramming systems is the magnetic drum, or fixed-head disk. And the
task of managing this secondary memory in an efficient way presents serious problems in the building
of these systems.

The sector is the transfer unit between this peripheral and main memory. A request for transfer may
address one sector (single request) or several sectors, not necessarily consecutive (bulk request). A ma-
thematical model has been defined by E.G. Coffman, Jr. for demand-paging-oriented operating systems
when the transfer requests are single requests. This article presents a generalization of the model when
the transfer requests are bulk requests. Such a generalization is applicable to operating systems using
preloadin methods or segmentation.

The description of the model and its mathematical analysis, along with a simulation, lead to certain
results useful in the evaluation of drum utilization in the context of these systems.

<footnote>* Ce travail a été présenté à l'Université Paris 6, le 22 juin 1973, pour soutenir une thèse de doctorat de 3ème cycle mathématiques appliquées, informatique pratique devant une commission d'examen composée de :
MM. J. ARSAC Président, A. BATSON et E. GELENBÉ Examinateurs.</footnote>
<table><thead><tr><th>TABLE DES MATIERES</th><th>Pages</th></tr></thead><tbody><tr><td>INTRODUCTION</td><td>1</td></tr><tr><td>Chapitre 1 : DESCRIPTION INFORMELLE DU PROBLEME</td><td>3</td></tr><tr><td>1.1 DESCRIPTION PHYSIQUE DU TAMBOUR</td><td>3</td></tr><tr><td>1.2 TYPES DE TRANSFERTS</td><td>5</td></tr><tr><td>1.3 ORGANISATION DE L'INFORMATION SUR LE TAMBOUR</td><td>6</td></tr><tr><td>1.4 PRESENTATION DU MODELE</td><td>7</td></tr><tr><td>1.4.1 Arrivée des demandes groupées au tambour, répartition des requêtes simples</td><td></td></tr><tr><td>1.4.2 Gestion des files, acquittement des requêtes</td><td></td></tr><tr><td>1.4.3 Temps d'attente d'une demande groupée</td><td></td></tr><tr><td>1.5 HYPOTHESES SIMPLIFICATRICES</td><td>10</td></tr><tr><td>Chapitre 2 : MODELE MATHEMATIQUE</td><td>11</td></tr><tr><td>2.1 HYPOTHESES</td><td>12</td></tr><tr><td>2.2 DISTRIBUTION DES ARRIVEES DES REQUETES SIMPLES A UN SECTEUR</td><td>13</td></tr><tr><td>2.2.1 Distribution de la contribution d'une demande groupée à un secteur</td><td></td></tr><tr><td>2.2.1.1 Première hypothèse, Ha</td><td></td></tr><tr><td>2.2.1.2 Deuxième hypothèse, Hb</td><td></td></tr><tr><td>2.2.1.3 Troisième hypothèse, Hc</td><td></td></tr><tr><td>2.2.1.4 Cas particulier</td><td></td></tr><tr><td>2.2.2 Distribution dans le temps du nombre de requêtes simples s'adressant à un secteur</td><td></td></tr><tr><td>2.3 DISTRIBUTION DE LA LONGUEUR DE LA FILE ASSOCIEE A UN SECTEUR POUR UNE SUITE DISCRETE D'INSTANTS</td><td>23</td></tr><tr><td>2.3.1 Calcul de la fonction génératrice</td><td></td></tr><tr><td>2.3.2 Facteur d'utilisation d'un secteur</td><td></td></tr></tbody></table>
## 2.4 DISTRIBUTION DE LA LONGUEUR DE LA FILE ASSOCIEE

A UN SECTEUR EN TEMPS CONTINU 29

2.4.1 Calcul de la fonction génératrice

2.4.2 Longueur moyenne de la file associée
à un secteur

## 2.5 TEMPS MOYEN D'ATTENTE 34

2.5.1 Temps moyen d'attente pour une demande
composée d'une seule requête simple

2.5.2 Temps moyen d'attente pour une demande de
taille i(i≥2)

2.5.2.1 Expression de $W_i(o)$ sous l'hypothèse Hb

2.5.2.2 Expression de $W_i(o)$ sous l'hypothèse Hc

## Chapitre 3 : SIMULATION DU MODELE 43

## 3.1 DESCRIPTION DE L'EXPERIENCE DE SIMULATION 44

3.1.1 Processus ARRIVEE

3.1.2 Processus TAMBOUR

3.1.3 Processus MESURES

3.1.4 Programme principal

3.1.5 Ramassage des résultats, édition

## 3.2 VALIDITE DU MODELE 48

3.2.1 Facteurs entachant les résultats

3.2.1.1 Générateurs de nombres aléatoires

3.2.1.2 Obtention du régime stationnaire

3.2.2 Solutions apportées

3.2.2.1 Tests des générateurs de nombres aléatoires

3.2.2.2 Charge initiale du système

3.2.3 Validité des résultats de la simulation

3.2.3.1 Comparaison aux résultats théoriques
pour $I = 1$

3.2.3.2 Demandes de taille $I \ge 2$
## 3.3 RESULTATS DE LA SIMULATION

56

3.3.1 Variation du temps d'attente d'une demande groupée en fonction de la charge du système

3.3.2 Variation du temps d'attente d'une demande groupée en fonction de sa taille

3.3.3 Histogramme de la longueur des files associées aux secteurs

## CONCLUSION

71

## BIBLIOGRAPHIE

74

## ANNEXES

76
# INTRODUCTION

Lors de la réalisation d'un système d'exploitation on doit résoudre le problème d'accès à la mémoire secondaire (que ce soit disques à bras mobiles, disques à têtes fixes, tambours magnétiques - éventuellement bandes magnétiques).

Comme cet accès est souvent un point de congestion, la méthode choisie a une grande importance pour l'efficacité du système d'exploitation et a fait l'objet de quelques articles.

Certains articles présentent une solution qui permet, en choisissant un ordre approprié des demandes parvenant à la mémoire secondaire, de minimiser le temps de positionnement des bras pour un disque à bras mobiles, de minimiser le temps de latence (latency-time) sur un tambour, etc... [Teo 72, Fra 69, Den 67, Ful 72a, Aba 69].

D'autres articles présentent l'analyse d'une stratégie de gestion des mémoires secondaires [Cof 69, Wei 66] et permettent ainsi de donner certains résultats, relatifs à une mesure d'efficacité donnée.

En particulier, l'analyse d'un modèle de tambour magnétique a été présenté [Cof 69] dans le contexte d'un système d'exploitation fonctionnant sur le principe de la page à la demande. Si une solution est ainsi apportée pour ce genre de système elle n'est pas applicable aux systèmes basés sur la segmentation [Cor 65].

Dans ce qui suit nous allons développer un modèle permettant de représenter, dans un système utilisant la segmentation ou faisant du préchargement, les transferts d'information entre la mémoire principale et un tambour magnétique utilisé comme mémoire auxiliaire.

Ce périphérique est découpé en un nombre défini de secteurs. On appelle requête simple la demande d'un transfert élémentaire exécuté par le tambour. Il lui correspond le transfert de l'information contenue sur un secteur (on parlera aussi de "page" même pour un système qui n'est pas un système de pagination).
E.G. Coffman, Jr. a présenté le cas où les demandes de transfert parviennent au tambour sous forme de requête simple. Nous donnons, ici, une généralisation de son modèle au cas où les demandes de transfert parviennent au tambour sous forme de *demandes groupées* : ensemble de plusieurs requêtes simples. Cette généralisation permet de représenter des systèmes dans lesquels les transferts ne se font plus sur la base d'une page mais au contraire d'un ensemble de pages; cet ensemble peut par exemple être celui des pages composant un segment dans le cas d'un système basé sur la segmentation, ou bien aussi l'ensemble des pages constituant la partition d'un utilisateur d'un système de multiprogrammation.

Notre démarche est la suivante : après avoir développé dans le chapitre 1 la description informelle du problème et de notre modèle, dans le chapitre 2 nous analyserons celui-ci d'un point de vue mathématique en posant les hypothèses nécessaires. Le chapitre 3 est consacré à la simulation de ce modèle et à l'obtention de résultats qui viennent compléter certaines formules du chapitre 2. L'analyse des résultats et les conclusions de cette étude sont présentées dans la dernière partie.

Les annexes contiennent la démonstration de certains lemmes utilisés dans le chapitre 2 et les listings du programme de simulation décrit dans le chapitre 3.
# 1 DESCRIPTION INFORMELLE DU PROBLEME

## 1.1 DESCRIPTION PHYSIQUE DU TAMBOUR

Nous allons discuter dans la suite d'un tambour magnétique (ou d'un disque à têtes fixes) dont la description physique est représentée schématiquement sur la figure ci-dessous.

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

** Schéma d'un tambour magnétique **

Le tambour peut être considéré comme un cylindre sur la surface duquel un certain nombre de pistes sont réparties le long de l'axe de rotation, chacune d'elles étant divisée en N secteurs identiques.

A chaque piste correspond une tête de lecture-écriture, celles-ci sont situées sur la circonférence et parallèlement à l'axe de rotation ; si bien qu'à un instant donné toutes les pistes d'un même secteur se trouvent en même temps sous les têtes de lecture-écriture. Toutefois, nous supposons qu'un seul canal d'entrée-sortie relie le tambour au système extérieur, il ne peut effectuer qu'un seul transfert à la fois, une seule piste peut donc être lue ou écrite à la fois.
Lorsque la fin du secteur k passe sous les têtes de lecture-écriture le début du secteur $k+1$ (modulo $N$) arrive sous celles-ci et le transfert de l'information contenue sur une piste quelconque de ce secteur $k+1$ peut commencer instantanément - en fait le transfert ne peut être effectué instantanément que si le transfert précédemment effectué était de même sens (deux opérations de lecture ou deux opérations d'écriture successives).

Avec un tel schéma du tambour, une requête simple parvenant au tambour est une demande de transfert de l'information qui se trouve à l'intersection d'une piste j et d'un secteur k donnés, le couple $(k,j)$ et le sens du transfert définissant la requête simple.

En fait d'après la disposition des têtes de lecture-écriture et puisqu'un seul transfert est possible à la fois, les requêtes simples sont regroupées d'après le secteur qu'elles adressent. Lorsque l'ensemble des têtes de lecture-écriture se trouvent au début d'un secteur l'une des requêtes simples contenues dans le groupe correspondant à ce secteur est prise en compte (si ce groupe n'est pas vide) et elle sera acquittée lorsque la fin du secteur passera sous les têtes de lecture-écriture ; c'est-à-dire, si la vitesse de rotation du tambour est constante et si la durée d'une révolution est $T$, la requête simple sera acquittée un temps $T/N$ après avoir été prise en compte - les $N$ secteurs étant identiques.
## 1.2 TYPE DE TRANSFERTS

Les transferts entre la mémoire principale et le tambour intervient dans presque toutes les actions des utilisateurs dans un système à temps partagé ou un système de multiprogrammation.

Ces transferts sont variés :

1) chargement des parties non résidentes du système,

2) transfert en mémoire principale des programmes à exécuter (le chargement peut être effectué en totalité ou concerner une partie seulement du programme),

3) transfert des données propres à l'exécution d'un programme,

4) transfert des fichiers des utilisateurs du système.

Cette liste n'est pas exhaustive mais ce sont autant de points qui entraînement la congestion pendant l'accès au tambour.

On voit également sur cette liste que les transferts qui peuvent être exécutés portent en général sur plus d'un secteur, même dans le cas où les programmes ou les fichiers ne sont pas transférés en totalité (pour les points 2 ou 4). Ceci justifie, si nécessaire, l'étude faite ici dans le cas où le système envoie au tambour des demandes de transferts portant sur plus d'un secteur.

D'autre part, la diversité des transferts justifie le caractère aléatoire de l'arrivée des demandes au tambour, hypothèse qui sera faite dans le chapitre 2.
## 1.3 ORGANISATION DE L'INFORMATION SUR LE TAMBOUR

L'organisation des "pages" sur le tambour est un facteur qui dépend bien évidemment du système d'exploitation lui-même et nous ne cherche-rons pas à entrer dans les détails. Toutefois nous notons ci-après les types d'organisation les plus fréquemment utilisés dans les systèmes d'exploitation existants, ce qui nous permettra, dans la suite, de faire les hypothèses nécessaires.

L'organisation de l'information sur le tambour dépend essentiellement de la conception même du système.

Par exemple pour un système basé sur la segmentation [Cor 65] ou utilisant le "segment" comme unité de transfert avec le tambour, l'organisation sera plutôt de type séquentiel : les segments de longueur en général très supérieure à la taille d'une "page" sont divisés en un nombre *i* d'enregistrements qui se trouvent placés sur des secteurs contigus du tambour (remarquons, d'ailleurs, que si les supports des enregistrements d'un segment se trouvent sur des secteurs en séquence sur le tambour, ils ne se trouvent pas nécessairement sur une même piste).

Cette technique basée sur une gestion particulière de la mémoire secondaire nécessite l'utilisation d'un algorithme de récupération de place sur le tambour - la remarque précédente permet, d'ailleurs, de simplifier cet algorithme.

Une autre technique, fréquemment utilisée, répartit les "pages" (ou enregistrements) composant un ensemble (fichier, programmes) d'après une fonction d'adressage dispersé (hash-coding). Cette méthode, si elle permet une meilleure utilisation de la place sur tambour, ne permet pas, comme on le verra d'après l'analyse, un temps d'accès meilleur que pour la technique précédente.
## 1.4 PRESENTATION DU MODELE

Avant d'aborder l'aspect mathématique du problème nous allons donner une description informelle du modèle qui sera reprise dans les chapitres 2 et 3 et complétée par les hypothèses nécessaires.

Pour clarifier l'exposé on supposera, dans la suite, sans nuire à la généralité, que le tambour reste fixe et que ce sont les têtes de lecture-écriture qui se déplacent.

### 1.4.1 Arrivée des demandes groupées au tambour, répartition des requêtes simples

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

A divers instants... $t_{j-1}$, $t_j$, $t_{j+1}$... répartis aléatoirement dans le temps des demandes de transferts parviennent au tambour (la loi suivie par les arrivées des demandes sera définie dans le chapitre 2 à partir des intervalles de temps séparant deux arrivées consécutives au tambour : $t_j - t_{j-1}$, $t_{j+1} - t_j$...).

Lorsqu'une demande groupée parvient au tambour elle est définie par sa *taille*, $i_j$, (nombre de requêtes simples qu'elle contient), chacune des $i_j$ requêtes simples étant elle-même définie par le secteur auquel elle s'adresse - d'après la description du tambour, § 1.1, on ne distingue pas deux requêtes simples s'adressant pour le même secteur à deux pistes distinctes, seule intervient l'appartenance au groupe correspondant à ce secteur.

Le sens du transfert d'une requête simple (lecture, écriture) est également ignoré : pour cela on est obligé de faire, par exemple, l'hypothèse que le temps de commutation des têtes de lecture-écriture de la lecture à l'écriture et vice-versa est nul.
A l'arrivée d'une demande groupée de taille i, les i requêtes simples qui la composent sont réparties et mises en attente dans les files associées à chaque secteur. Cet éclatement de la demande groupée est supposé instantané et n'est pas pris en compte dans le modèle.

### 1.4.2 Gestion des files, acquittement des requêtes

La file associée à un secteur contient l'ensemble des requêtes simple non encore satisfaites s'adressant à ce secteur.

Lorsque les têtes de lecture-écriture passent au début du secteur k, une requête simple de la file k, associée à ce secteur, (si cette file n'est pas vide) est prise en compte pour être servie : le transfert commence alors et sera terminé lorsque les têtes de lecture-écriture passeront en fin du secteur k, la requête simple est alors acquittée.

La gestion des requêtes simples est FCFS (first come first served), gestion sans priorité, pour cela :

* lors de l'éclatement d'une demande groupée, les requêtes simples sont mises en queue des files correspondantes (il n'y a pas de distinction faite pour deux requêtes simples d'une même demande groupée s'adressant au même secteur),

* lors du passage des têtes de lecture-écriture sur le début du secteur k c'est la requête simple en tête de la file k qui sera prise en compte pour être acquittée.

### 1.4.3 Temps d'attente d'une demande groupée

Nous utiliserons, ici, le terme de temps d'attente pour désigner l'intervalle de temps pendant lequel une demande reste dans le système (ce temps comprend le temps de service lui-même).

Certains auteurs parlent aussi de temps de réponse ; pour éviter toute ambiguïté nous donnerons la définition du temps d'attente d'une demande groupée :

**Définition** : Le temps d'attente d'une demande groupée est l'intervalle de temps séparant

* l'instant d'arrivée de cette demande dans le système

* de l'instant où la requête simple la plus tardivement servie de cette demande est acquittée.
Ce temps d'attente constitue une mesure d'efficacité dans l'utilisation du tambour et nous allons essayer de l'évaluer. Cette mesure nous permettra d'effectuer des comparaisons avec d'autres modèles de gestion d'un tambour [Cof 69, Aba 69].
## 1.5 HYPOTHESES SIMPLIFICATRICES

Nous avons mentionné, § 1.4.1, que l'éclatement des demandes groupées était instantané et qu'il n'en était pas tenu compte dans l'étude du modèle. Si l'on voulait en tenir compte on pourrait supposer que le temps mis pour répartir les requêtes simples ne dépend pas de la taille de la demande groupée et qu'il a une valeur fixe : ôt ; cette hypothèse permettrait d'appliquer strictement les mêmes résultats que ceux qui vont être développés puisque cela revient seulement à faire une translation du temps de la valeur ôt.

Cette hypothèse n'est pas correcte en toute rigueur. Il serait plus raisonnable de supposer que le temps d'éclatement de la demande groupée est fonction linéaire croissante de sa taille. De toutes façons ce temps de gestion est négligeable (de l'ordre de quelques microsecondes par requête simple) devant le temps de révolution du tambour (de l'ordre de quelques millisecondes).

Nous avons également mentionné, § 1.4.1, que le sens de transfert d'une requête simple était ignoré, nous entendons par là que le transfert d'une requête simple ne tient pas compte du sens de transfert de la requête précédemment acquittée sur la même piste. Cela suppose que le temps de basculement des têtes de lecture-écriture est nul, ou seulement que ce basculement peut être effectué avant le transfert proprement dit ; pour cela, pour les tambours magnétiques de construction récente [Dia ], deux secteurs consécutifs sont séparés par un espace sans information (gap) qui permet ce basculement ; le temps de service, T/N, comprend alors le temps pour les têtes de lecture-écriture de passer sur cet espace (avec le basculement éventuel de la tête concernée) et le temps de transfert proprement dit.
## 2. MODELE MATHEMATIQUE

Après avoir posé les hypothèses qui permettront de développer l'analyse mathématique du modèle, nous déterminerons la distribution des arrivées des requêtes simples à un secteur donné qui permettra de trouver la distribution du nombre de requêtes simples dans la file d'attente associée à ce secteur. A partir de là nous pourrons déterminer le temps moyen d'attente d'une demande groupée.

La démarche adoptée consiste à mettre en évidence un ensemble discret d'instants pour lesquels le système étudié se comporte comme un processus de Markov ; les distributions cherchées seront définies à ces instants précis (par leurs fonctions génératrices). Ensuite nous étendrons ces résultats, en nous ramenant à une échelle de temps continue.

Le modèle du tambour analysé ici est présenté schématiquement sur la figure suivante.

<figure><img src="image_4.png" /></figure>
## 2.1 HYPOTHESES

H1 La vitesse de rotation du tambour est constante, sa période est T.

H2 Les intervalles de temps entre deux arrivées consécutives de demandes groupées au tambour constituent un processus de Poisson ; le temps moyen entre deux arrivées consécutives étant $1/\lambda$, la fonction de distribution correspondante est :

$$ \Phi(t) = \begin{cases} 1 - e^{-\lambda t} & \text{si } t \ge 0 \\ 0 & \text{si } t < 0 \end{cases} \qquad (1.1) $$

Soit encore en posant :

$$ \phi_j(t) = \begin{cases} \text{Pr} \{ j \text{ demandes consécutives arrivent dans le temps } t \} & \text{pour } j = 0, 1, 2, \dots \\ 0 & \text{pour } j = \infty \end{cases} \qquad (1.2) $$

$$ \phi_j(t) = e^{-\lambda t} \frac{(\lambda t)^j}{j!} \quad \text{pour } j = 0, 1, 2, \dots \qquad (1.3) $$

H3 La taille d'une demande groupée (nombre de requêtes simples qu'elle contient) ne dépend pas du temps et suit une loi de probabilité définie par $\{h_i\}_{i=0}^\infty$ où :

$$ h_i = \begin{cases} \text{Pr} \{ \text{une demande groupée contient } i \text{ requêtes simples} \} & \text{pour } i = 0, 1, 2, \dots \\ 0 & \text{pour } i = \infty \end{cases} \qquad (1.4) $$

La taille moyenne d'une demande groupée est donc donnée par :

$$ \bar{h} = \sum_{i=0}^{\infty} ih_i \qquad (1.5) $$

H4 Les N secteurs composant le tambour jouent un rôle symétrique, i.e. la probabilité qu'une requête simple appartenant à une demande groupée s'adresse à un secteur k donné est la même pour tous les secteurs et vaut $1/N$ pour $k = 1, 2, \dots, N$.

H5 L'étude faite ici suppose que le système a atteint son état d'équilibre.
## 2 DISTRIBUTION DES ARRIVEES DES REQUETES SIMPLES A UN SECTEUR.

Si les intervalles de temps entre deux arrivées consécutives de demandes groupées au système suivent une loi exponentielle, il n'en est pas de même pour les arrivées des requêtes simples à un secteur k donné ($1 \le k \le N$). Cependant le nombre de requêtes simples s'adressant au secteur k pendant l'intervalle de temps ($t,t+\Delta t$), s'il est fonction de $\Delta t$, ne dépend pas de t.

### 1.1 Distribution de la contribution d'une demande groupée à un secteur :

Dans une première étape nous allons déterminer les probabilités conditionnelles d'avoir n requêtes simples s'adressant au secteur k dans j demandes groupées consécutives parvenant au système.

On définit :

$$a_k(n \mid j) = \Pr \{ \begin{array}{l} n \text{ requêtes simples parviennent au secteur } k, \text{ sachant que} \\ \text{j demandes groupées sont parvenues au système} \end{array} \} \\ \text{pour } j = 1, 2, \dots \text{ et } n = 0, 1, 2, \dots \qquad (2.1)$$

on étend cette définition pour $j = 0$ par :

$$a_k(n \mid 0) = \begin{cases} 1 & \text{si } n = 0 \\ 0 & \text{si } n > 0 \end{cases}$$

Ces probabilités conditionnelles sont calculées à partir de leurs fonctions génératrices :

$$A_j(z) = \sum_{n=0}^{\infty} a(n \mid j) z^n \quad \text{pour } j = 0, 1, 2, \dots \qquad (2.2)$$

(1'indice k a été omis puisque, d'après l'hypothèse H4, les N secteurs jouant un rôle symétrique, k n'intervient pas dans ces fonctions génératrices).

Introduisons les probabilités :

$$c_k(n \mid i) = \Pr \{ \begin{array}{l} n \text{ requêtes simples d'une demande groupée s'adressent} \\ \text{au secteur } k, \text{ sachant que cette demande groupée a une} \\ \text{taille } i \end{array} \} \\ \text{pour } i = 0, 1, 2, \dots \text{ et } n = 0, 1, 2, \dots \qquad (2.3)$$

et leurs fonctions génératrices :

$$C_i(z) = \sum_{n=0}^{\infty} c(n \mid i) z^n \quad \text{pour } i = 0, 1, 2, \dots \qquad (2.4)$$

(pour les mêmes raisons que précédemment l'indice k a encore été omis).
**Théorème 1 :**

Les fonctions génératrices $A_j(z)$ sont données par :

$$A_j(z) = [A_j(z)]^j \quad \text{pour } j = 0, 1, 2, \dots \quad (2.5)$$

avec :

$$A_j(z) = \sum_{i=0}^{\infty} h_i C_i(z) \quad (2.6)$$

**Démonstration :**

La probabilité conditionnelle $a(n|j)$ peut être calculée en supposant que $r (0 \le r \le n)$ requêtes simples de la première demande groupée s'adressent au secteur k et que les n-r autres proviennent des j-1 (j ≥ 2) demandes groupées suivantes, donc :

$$a(n \mid j) = \sum_{r=0}^{n} a(r \mid 1) a(n-r \mid j-1)$$

d'où :

$$A_j(z) = \sum_{n=0}^{\infty} a(n \mid j) z^n = \sum_{n=0}^{\infty} \sum_{r=0}^{n} a(r \mid 1) a(n-r \mid j-1) z^n \\ = \sum_{n=0}^{\infty} \sum_{r=0}^{n} a(r \mid 1) z^r a(n-r \mid j-1) z^{n-r}$$

où l'on reconnaît le produit de convolution de $A_j(z)$ avec $A_{j-1}(z)$, en conséquence :

$$A_j(z) = A_j(z) A_{j-1}(z) \quad \text{pour } j = 2, 3, \dots$$

d'où le résultat (2.5), en remarquant que :

$$A_j(z) = [A_j(z)]^j$$

et que

$$A_0(z) = 1 = [A_1(z)]^0$$

Pour la formule (2.6) la démonstration est immédiate puisque d'après les définitions (2.1), (1.4) et (2.3) :

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

d'où :

$$A_j(z) = \sum_{n=0}^{\infty} a(n \mid 1) z^n = \sum_{n=0}^{\infty} \sum_{i=0}^{\infty} h_i c(n \mid i) z^n \\ = \sum_{i=0}^{\infty} h_i \sum_{n=0}^{\infty} c(n \mid i) z^n$$
et en utilisant (2.4) il vient (2.6).

C.Q.F.D.

Remarques :

. Une demande groupée de taille i ne pouvant fournir plus de i
requêtes simples au secteur k :

$$
c_k(n \mid i) = 0 \quad \text{pour } i = 0,1,2,\dots \quad \text{et } n > i
$$

. Si $\bar{c}_k(i)$ est la contribution moyenne au secteur k d'une demande groupée de taille i, on a :

$$
\bar{c}_k(i) = \sum_{n=0}^{\infty} n \cdot c_k(n \mid i) = \sum_{n=0}^{\infty} n \cdot c_k(n \mid i)
$$

avec bien sûr :

$$
\sum_{k=1}^{N} \bar{c}_k(i) = i
$$

or, d'après l'hypothèse H4, tous les secteurs ont un rôle symétrique ;
la contribution moyenne à un secteur ne dépend donc pas de ce secteur
et vaut :

$$
\bar{c}_k(i) = \frac{i}{N} \left( \lim_{z \to 1} C'_i(z) \right) \quad \text{pour } k = 1, 2, \dots, N
$$

d'où l'on déduit le nombre moyen de requêtes simples issues d'une demande
groupée quelconque et s'adressant à un secteur donné :

$$
\sum_{n=0}^{\infty} n \cdot a(n \mid 1) = \lim_{z \to 1} A'_1(z)
$$

$$
= \lim_{i \to 0} h_i \cdot \lim_{z \to 1} C'_i(z) = \lim_{i \to 0} \frac{h_i}{N} \frac{i}{N}
$$

C'est-à-dire en utilisant la formule (1.5) :

$$
\lim_{z \to 1} A'_1(z) = \frac{\bar{h}}{N} \tag{2.7}
$$

$z \to 1$
Ce résultat confirme l'intuition puisque $\bar{h}$ est le nombre moyen de requêtes simples dans une demande groupée et que les N secteurs sont également requis.

Sans hypothèse supplémentaire sur la composition des demandes groupées, les fonctions génératrices $C_i(z)$ et en conséquence la fonction génératrice $A_1(z)$ ne peuvent pas être explicitées.

Nous allons étudier différentes hypothèses, compatibles avec H4, à partir desquelles les calculs pourront être effectués.

### 2.2.1.1 Première hypothèse, Ha :

Une demande groupée est considérée, ici, du seul point de vue du tambour. Pour celui-ci la seule information qui intervient dans une demande groupée est la taille des contributions de la demande groupée aux différents secteurs composant le tambour, en d'autres termes :
la demande est simplement vue comme le vecteur $(r_1, r_2, \dots, r_N)$ où $r_k(1 \le k \le N)$ est le nombre de requêtes simples de la demande groupée s'adressant au secteur k.

On supposera que toutes les configurations possibles de ces vecteurs sont équiprobables.

Remarquons que les configurations possibles d'une demande de taille i, sont, ici, toutes les combinaisons i à i des N secteurs avec répétitions ; on suppose donc que ces combinaisons sont équiprobables.

**Théorème 1 :** Si l'on considère que les configurations possibles d'une demande groupée de taille i sont toutes les combinaisons i à i des N secteurs avec répétitions et que ces combinaisons sont équiprobables, alors :

$$A_1(z) = \sum_{i=0}^{\infty} h_i \binom{i}{n=0} \frac{\binom{N-1+i}{N-1+n}}{\binom{N-1+i}{N-1}} (z-1)^n \quad (2.8)$$

**Démonstration :**

**Lemme 1 :** Le nombre des combinaisons r à r de n objets avec répétitions est donné par :

$$r_n = \binom{n+r-1}{r} \quad (2.9)$$
Ce résultat est démontré en annexe.

Etant donnée une demande groupée composée de i requêtes simples, chacune d'elles s'adresse à l'un des N secteurs : il y a donc $\Gamma_N^i$ demandes groupées possibles de taille i.

Une demande groupée de taille i contient exactement n requêtes simples s'adressant au secteur k si et seulement si elle contient i - n requêtes simples s'adressant aux N - 1 autres secteurs : le nombre de ces demandes groupées est donc $\Gamma_{N-1}^{i-n}$.

On a donc, sous les hypothèses faites ici, et d'après la définition (2.3) :

$$ c(n \mid i) = \begin{cases} \frac{\Gamma_{N-1}^{i-n}}{\Gamma_N^i} = \frac{\binom{i-n+N-2}{i-n}}{\binom{i+N-1}{i}} & \text{pour } 0 \le n \le i \\ 0 & \text{pour } n > i \end{cases} \quad (2.10) $$

et en remplaçant dans (2.4) :

$$ C_i(z) = \sum_{n=0}^{\infty} c(n \mid i) z^n = \sum_{n=0}^{i} \frac{\binom{i-n+N-2}{i-n}}{\binom{i+N-1}{i}} z^n \quad (2.11) $$

la transformation de cette formule pour aboutir au résultat (2.8) repose sur le lemme suivant dont la démonstration est également rejetée en annexe :

**Lemme 2** : On a pour $i = 0, 1, 2, \dots$ et $p \ge i$ :

$$ \sum_{n=0}^{i} \binom{p-n}{i-n} z^n = \sum_{n=0}^{i} \binom{p+1}{i-n} (z-1)^n \quad (2.12) $$

D'après ce résultat en posant $p = i+N-2$ on obtient à partir de (2.11) :

$$ C_i(z) = \sum_{n=0}^{i} \frac{\binom{N-1+i}{N-1+n}}{\binom{N-1+i}{N-1}} (z-1)^n \quad \text{pour } i = 0, 1, 2, \dots \quad (2.13) $$

d'où le résultat (2.8) en utilisant la formule (2.6).
Remarquons que la formule (2.13) permet de retrouver le résultat (2.7) puisque :

$$C'_{i}(1) = \frac{\binom{N-1+i}{N-1+1}}{\binom{N-1+i}{N-1}} = \frac{i}{N}$$

### 2.2.1.2 Deuxième hypothèse, $H_b$ :

Nous supposons maintenant que les requêtes simples composant une demande groupée sont indépendantes et ont des probabilités égales de s'adresser à chacun des secteurs.

La demande groupée n'est plus considérée du seul point de vue du tambour et c'est par exemple le cas que l'on rencontre dans un système d'exploitation qui fait du préchargement dans un environnement paginé : lorsqu'un programme effectue un défaut de page la suite des références ultérieures aux pages détermine l'ensemble des pages à précharger :
($p_1, p_2, \dots, p_i$), d'où l'on déduit la suite des secteurs concernés :
($r_1, r_2, \dots, r_i$) — $r_j$ étant le secteur où est implantée la page $p_j$. S'il n'est pas naturel de supposer que les $\{p_j\}_{j=1}^i$ sont indépendants, la fonction $\phi : p_j \to r_j$, assurant la correspondance entre le numéro de page et le secteur d'implantation de la page sur le tambour, étant en général une fonction d'adressage dispersé (hash-coding), il est admissible de supposer que les $\{r_j\}_{j=1}^i$ sont indépendants et uniformément répartis sur tous les secteurs.

Cette hypothèse diffère essentiellement de la précédente : parce qu'ici, l'ordre des requêtes simples à l'intérieur d'une demande groupée intervient alors que ce n'était pas le cas précédemment ; par exemple pour un tambour à deux secteurs ($N = 2$) et pour une demande de taille $i = 2$ on doit considérer les 4 demandes groupées possibles (a,a), (a,b), (b,a) et (b,b) alors que pour l'hypothèse Ha les deux demandes (a,b) et (b,a) ne se distinguent pas l'une de l'autre.

**Théorème 1b :** Si les requêtes simples composant une demande groupée sont indépendantes et s'adressent uniformément à tous les secteurs, alors :

$$A_1(z) = H\left(1 + \frac{z-1}{N}\right) \qquad (2.14)$$

où $H(z)$ est la fonction génératrice de la distribution de la taille des demandes groupées :

$$H(z) = \sum_{i=0}^{\infty} h_i z^i \qquad (2.15)$$
Démonstration :

Sous les hypothèses énoncées ici la probabilité que n requêtes simples données d'une demande groupée de taille i s'adressent au même secteur k est :

$$ \left(\frac{1}{N}\right)^n \cdot \left(1 - \frac{1}{N}\right)^{i-n} $$

et puisque les ensembles de n requêtes simples d'une demande groupée de taille i sont au nombre de :

$$ \binom{i}{n} $$

on a, à partir de la définition (2.3) :

$$ c(n \mid i) = \begin{cases} \binom{i}{n} \cdot \left(\frac{1}{N}\right)^n \cdot \left(1 - \frac{1}{N}\right)^{i-n} & \text{pour } 0 \le n \le i \\ 0 & \text{pour } n > i \end{cases} \quad (2.16) $$

d'où à partir de (2.4) :

$$ C_i(z) = \sum_{n=0}^{\infty} c(n \mid i) z^n = \sum_{n=0}^{i} \binom{i}{n} (1 - \frac{1}{N})^{i-n} \left(\frac{1}{N}\right)^n z^n $$

soit :

$$ C_i(z) = \left(1 + \frac{z-1}{N}\right)^i \quad \text{pour } i = 0, 1, 2, \dots \quad (2.17) $$

donc en reportant dans (2.6) :

$$ A_i(z) = \sum_{n=0}^{\infty} h_i \cdot C_i(z) = \sum_{n=0}^{\infty} h_i \left(1 + \frac{z-1}{N}\right)^n $$

d'où le résultat (2.14) en introduisant la fonction générale $H(z)$.

C.Q.F.D.

Ici aussi le résultat (2.7) peut être retrouvé à partir de la formule (2.14) :

$$ A'_1(1) = \frac{1}{N} H'(1) = \frac{\bar{h}}{N} $$
### 2.2.1.3 Troisième hypothèse, Hc :

Maintenant les requêtes simples composant une demande groupée sont supposées s'adresser à des secteurs consécutifs du tambour ; une demande est donc, ici, déterminée par sa taille et l'adresse du premier secteur concerné.

C'est le cas par exemple dans un système d'exploitation où l'unité de transfert entre tambour et mémoire principale est le segment. Les segments, de longueur variable, sont découpés en enregistrements de longueur fixe implantés séquentiellement sur le tambour.

**Théorème 1c :** Si les requêtes simples d'une demande groupée s'adressent à des secteurs consécutifs du tambour et si la probabilité qu'un secteur donné soit le premier adressé par la demande est la même pour tous les secteurs, alors :

$$A_1(z) = \sum_{i=0}^{\infty} h_i \left[ \left(1 - \frac{r}{N}\right) z^q + \frac{r}{N} z^{q+1} \right] \quad (2.18)$$

où :

$$r = i \text{ modulo}(N) \text{ et } q = \frac{i - r}{N}$$

**Démonstration :**

Sous les hypothèses valables ici, si une demande de taille i ($i = q, N+r$ avec $0 \le r < N$) parvient au tambour, r secteurs auront une contribution de $q+1$ requêtes simples et $N-r$ une contribution de $q$ requêtes simples, d'où :

$$c(n \mid i) = \begin{cases} \frac{r}{N} & \sin n = q + 1 \\ 1 - \frac{r}{N} & \sin n = q \\ 0 & \sin n \end{cases} \quad (2.19)$$

d'où pour l'expression de $C_i(z)$ :

$$C_i(z) = \left(1 - \frac{r}{N}\right) z^q + \frac{r}{N} z^{q+1} \quad (2.20)$$

et de là le résultat (2.18) à partir de (2.6).

C.Q.F.D.
Ici encore on peut retrouver l'égalité (2.7) puisque :

$$C'_{i}(1) = q \left(1 - \frac{r}{N}\right) + (q + 1) \frac{r}{N} = q + \frac{r}{N} = \frac{i}{N}$$

### §1.4 Cas particulier :

Si l'on suppose que toutes les demandes groupées sont composées d'une seule requête simple s'adressant uniformément à tous les secteurs, alors $A_j(z)$ peut être trouvé comme cas particulier de chacune des hypothèses précédentes où :

$$h_i = \begin{cases} 1 & \text{si } i = 1 \\ 0 & \text{sinon} \end{cases}$$

d'où :

$$A_j(z) = 1 + \frac{z-1}{N} \qquad (2.21)$$

Ce cas particulier permettra de retrouver les résultats établis par E.G. Coffman, Jr. [Cof 69].

### §2.2 Distribution dans le temps du nombre de requêtes simples s'adressant à un secteur :

Etant donné que

- les intervalles de temps entre deux arrivées consécutives de demande groupée suivent une loi de Poisson,

- la loi de distribution de la taille des demandes est indépendante du temps : la distribution du nombre de requêtes simples s'adressant au secteur k pendant un intervalle de temps ne dépend que de la longueur t de cet intervalle.
Posons donc :

$f_n(t) = \text{Pr} \{ n \text{ requêtes simples parviennent au secteur k pendant un intervalle de temps de longueur } t \}$

$$ \text{pour } n = 0, 1, 2, \dots \tag{2.22} $$

et pour la fonction génératrice de cette distribution :

$$ A(z,t) = \sum_{n=0}^{\infty} f_n(t) z^n \tag{2.23} $$

**Théorème 2 :** La fonction génératrice de la distribution de probabilité du nombre de requêtes simples s'adressant au secteur k pendant un intervalle de temps de longueur t est donnée par :

$$ A(z,t) = e^{-\lambda t [1-A_1(z)]} \tag{2.24} $$

**Démonstration :**

A partir des définitions (2.22), (1.2) et (2.1) on obtient directement :

$$ f_n(t) = \sum_{j=0}^{\infty} \phi_j(t) a(n \mid j) \tag{2.25} $$

d'où, en reportant (2.25) dans (2.23) :

$$ \begin{align*} A(z,t) &= \sum_{n=0}^{\infty} z^n \sum_{j=0}^{\infty} \phi_j(t) a(n \mid j) = \sum_{j=0}^{\infty} \phi_j(t) \sum_{n=0}^{\infty} a(n \mid j) z^n \\ &= \sum_{j=0}^{\infty} \phi_j(t) A_j(z) \end{align*} $$

ce qui devient d'après les résultats (1.3) et (2.5) :

$$ A(z,t) = \sum_{j=0}^{\infty} e^{-\lambda t} \frac{(\lambda t)^j}{j!} [A_1(z)]^j $$

d'où le résultat (2.24).

C.Q.F.D.
## 2.3 DISTRIBUTION DE LA LONGUEUR DE LA FILE ASSOCIEE A UN SECTEUR POUR UNE SUITE DISCRETE D'INSTANTS.

### 3.1 Calcul de la fonction génératrice :

Nous allons maintenant déterminer la distribution de probabilité de la longueur de la file associée au secteur k.

On rappelle que lorsqu'une demande groupée parvient au tambour, celle-ci est éclatée instantanément, chaque requête simple composant la demande groupée étant placée à la queue de la file associée au secteur auquel elle s'adresse.

On rappelle, en outre, que le tambour sert la requête simple en tête de file associée au secteur k, la file k, (si celle-ci n'est pas vide) lorsque la tête de lecture-écriture passe devant le secteur k.

Définissons les instants $t_0, t_1, ..., t_ℓ, ...$ où la tête de lecture-écriture passe en fin du secteur k, et, pour cette suite discrète d'instants, soit

$X_ℓ = X(t_ℓ)$ $ℓ = 0, 1, 2, ...$ la longueur de la file k.

$\{X_ℓ\}_{ℓ=0}^∞$ est une chaîne de Markov : en effet la longueur de la file k à l'instant $t_{ℓ+1}$ ne dépend que de la longueur de la file k à l'instant $t_ℓ$ et du nombre de requêtes simples s'adressant au secteur k parvenues entre les instants $t_ℓ$ et $t_{ℓ+1}$, et, comme on l'a vu en 2.2.2, ce nombre ne dépend que de $t_{ℓ+1} - t_ℓ = T$ qui ne dépend pas de $ℓ$.

Plus précisément on peut écrire :

$$X_{ℓ+1} = X_{ℓ} - \delta + Y(t_{ℓ+1} - t_{ℓ})$$

où :

$$ \delta = \begin{cases} 0 & \text{si la file k est vide lorsque la tête de lecture-écriture passe au début du secteur k} \\ 1 & \text{sinon} \end{cases} $$

et :

$$Y(t_{\ell+1} - t_{\ell}) = \text{le nombre de requêtes simples s'adressant au secteur k entre les instants } t_{\ell} \text{ et } t_{\ell+1}.$$
Définissons, pour la suite discrète des instants $\{t_\ell\}_{\ell=0}^\infty$ les probabilités de transitions de la longueur de la file k par :

$$ \pi_{ij} = \Pr \{ X_{\ell+1} = j | X_\ell = i \} \\ \text{pour } i = 0, 1, 2, \dots \text{ et } j = 0, 1, 2, \dots $$

Alors, par définition de l'état d'équilibre, la distribution de la probabilité de la longueur de la file k : $\{\pi_j\}_{j=0}^\infty$ à l'état stationnaire vérifie, si elle existe :

$$ (\pi_0, \pi_1, \pi_2, \dots) = (\pi_0, \pi_1, \pi_2, \dots) ((\pi_{ij})) \quad (3.1) $$

ou encore :

$$ \pi_j = \sum_{i=0}^{\infty} \pi_i \pi_{ij} \quad \text{pour } j = 0, 1, 2, \dots \quad (3.2) $$

Posons pour la fonction génératrice de cette distribution :

$$ \Pi(z) = \sum_{j=0}^{\infty} \pi_j z^j \quad (3.3) $$

**Théorème 3** : La fonction génératrice de la distribution de probabilité de la longueur de la file associée au secteur k est donnée, à l'état d'équilibre et pour la suite discrète des instants $\{t_\ell\}_{\ell=0}^\infty$, par :

$$ \Pi(z) = \left(1 - \frac{\lambda \bar{h} T}{N}\right) \frac{(z-1) e^{-\lambda T / N} [1 - A_1(z)]}{z - e^{-\lambda T [1 - A_1(z)]}} \quad (3.4) $$

**Démonstration :**

Nous utilisons ici les notations suivantes (qui seront reprises par la suite) : $\theta$ représente $T \frac{N-1}{N}$ et $\tau$ représente $T \frac{1}{N}$.

Revenons aux probabilités de transitions. Pour l'évaluation de $\pi_{ij}$ plusieurs cas sont à considérer :

- $i=0$ : la file est vide à l'instant $t_0$ et

• si aucune requête ne s'est adressée au secteur k avant l'instant $t_0+\theta$, où la tête de lecture-écriture passe par le début du secteur k, j requêtes devront s'adresser au secteur k entre les instants $t_0+\theta$ et $t_0+1$,
• sinon, si r (r ≥ 1) requêtes se sont adressées au secteur k avant l'instant $t_ℓ+θ$, l'une d'elles sera acquittée à l'instant $t_{ℓ+1}$ et j - (r - 1) devront donc être parvenues au secteur k entre les instants $t_ℓ+θ$ et $t_{ℓ+1}$,

on a donc :

$$ \pi_{oj} = \Pr \left\{ \begin{array}{l} (o \text{ requête parvient au secteur } k \text{ pendant l'intervalle de temps} \\ (t_ℓ+θ) - t_ℓ = θ) \text{ & } (j \text{ pendant } t_{ℓ+1} - (t_ℓ+θ) = τ) \end{array} \right\} $$

$$ \begin{array}{l} j+1 \\ + \sum_{r=1}^{n} \Pr \left\{ \begin{array}{l} (r \text{ requêtes parviennent au secteur } k \text{ pendant } (t_ℓ+θ) - t_ℓ = θ) \text{ & } \\ (j - r + 1 \text{ pendant } t_{ℓ+1} - (t_ℓ+θ) = τ) \end{array} \right\} \end{array} $$ pour $j \ge 0$.

- $i > 0$ :

• une requête au plus étant acquittée entre deux instants consécutifs de la suite {$t_ℓ$}$_{ℓ=0}^∞$, on a :

$$ \begin{array}{l} \pi_{ij} = 0 \\ \quad \text{pour } j < i - 1 \end{array} $$

• sinon, une des i requêtes étant acquittée à l'instant $t_{ℓ+1}$, $j-(i-1)$ doivent s'adresser au secteur k entre les instants $t_ℓ$ et $t_{ℓ+1}$ et l'on a :

$$ \begin{array}{l} \pi_{ij} = \Pr \left\{ \begin{array}{l} j - i + 1 \text{ requêtes s'adressent au secteur } k \text{ pendant} \\ \qquad t_{ℓ+1} - t_ℓ = T \end{array} \right\} \\ \quad \text{pour } j \ge i - 1. \end{array} $$

En reprenant la définition (2.22), les expressions précédentes deviennent :

$$ \pi_{oj} = f_o(\theta) f_j(\tau) + \sum_{r=1}^{j+1} f_r(\theta) f_{j-r+1}(\tau) \quad \text{pour } j \ge 0 $$

$$ \pi_{ij} = 0 \quad \text{pour } 0 \le j < i - 1 $$

$$ \pi_{ij} = f_{j-i+1}(T) \quad \text{pour } 1 \le i \le j + 1 \quad (3.5) $$
On a donc à partir de (3.3) en utilisant (3.2) et les formules précédentes :

$$
\begin{align*}
\Pi(z) &= \sum_{j=0}^{\infty} \sum_{i=0}^{\infty} \pi_i \pi_{ij} z^j = \pi_0 \sum_{j=0}^{\infty} \pi_{0j} z^j + \sum_{i=1}^{\infty} \pi_i \sum_{j=0}^{\infty} \pi_{ij} z^j \\
&= \pi_0 \sum_{j=0}^{\infty} [f_0(\theta) f_j(\tau) + \sum_{r=1}^{j+1} f_r(\theta) f_{j-r+1}(\tau)] z^j \\
&\quad + \sum_{i=1}^{\infty} \pi_i \sum_{j=i-1}^{\infty} f_{j-i+1}(T) z^j \\
&= \pi_0 f_0(\theta) \sum_{j=0}^{\infty} f_j(\tau) z^j \\
&\quad + \pi_0 \sum_{j=0}^{\infty} \sum_{r=1}^{j+1} f_r(\theta) f_{j-r+1}(\tau) z^j \\
&\quad + \frac{1}{z} \sum_{i=1}^{\infty} \sum_{j=i-1}^{\infty} \pi_i z^i f_{j-i+1}(T) z^{j-i+1} \\
&= \pi_0 f_0(\theta) A(z, \tau) \\
&\quad + \pi_0 \frac{1}{z} [A(z, \theta) - f_0(\theta)] A(z, \tau) \\
&\quad + \frac{1}{z} [\Pi(z) - \pi_0] A(z, T)
\end{align*}
$$

Après quelques simplifications faites en remarquant que :

$$
A(z,\theta) A(z,\tau) = A(z,\theta+\tau) = A(z,T)
$$

on obtient finalement l'équation fonctionnelle satisfaite par Π(z) :

$$
\Pi(z) = \frac{\pi_0}{z} (z - 1) f_0(\theta) A(z, \tau) + \frac{1}{z} \Pi(z) A(z, T) \quad (3.6)
$$

qui se résout en :

$$
\Pi(z) = \pi_0 f_0(\theta) \frac{(z-1) A(z, \tau)}{z - A(z, T)} \quad (3.7)
$$

Puisque Π(z) est la fonction génératrice d'une distribution de probabilité, π₀ peut être déterminé en écrivant que :

$$
\lim_{z \to 1} \Pi(z) = 1
$$
Π(1) se présente sous la forme indéterminée o/o. En appliquant la règle
de l'Hospital (A'(z,t) représentant la dérivée de A(z,t) par rapport à z)
on obtient donc :

$$
1 = \pi_o f_o(\theta) \frac{A(1,T)}{1-A'(1,T)} = \pi_o f_o(\theta) \frac{1}{1 - \frac{\lambda \bar{h} T}{N}}
$$

c'est-à-dire :

$$
\pi_o f_o(\theta) = 1 - \frac{\lambda \bar{h} T}{N} \tag{3.8}
$$

et en reportant (3.8) dans (3.7) on obtient (3.4).

C.Q.F.D.

Remarquons que pour que l'égalité (3.8) ait un sens il faut que :

$$
\frac{\lambda \bar{h} T}{N} < 1 \tag{3.9}
$$

lorsque cette relation est vérifiée les calculs précédents sont valides :
elle représente donc la condition d'existence de l'état d'équilibre.

2.3.2 Facteur d'utilisation d'un secteur :

**Définition** : Le facteur d'utilisation du secteur k, $\rho_k$, est le nombre moyen de requêtes simples acquittées par le secteur k au cours d'une révolution du tambour lorsque le système a atteint son régime d'équilibre.

Théorème 4 : Le facteur d'utilisation du secteur k est donné par :
$$ \rho_k = \frac{\lambda \bar{h} T}{N} \quad \text{pour } k = 1, 2, \dots, N. \tag{3.10} $$

Démonstration :

Définissons la variable aléatoire $b_k(l)$ comme le nombre de
requêtes simples acquittées par le secteur k au cours de la $l$<sup>ième</sup> révolution
du tambour (entre les instants $t_\ell$ et $t_{\ell+1}$). On a d'après cette définition :

$$
b_k(l) = \begin{cases} 0 & \text{si la file k ne contient aucune requête à l'instant } t_\ell+\theta \text{ où la tête de lecture-écriture passe au début du secteur k,} \\ 1 & \text{sinon.} \end{cases}
$$
Par définition de $\rho_k$ on a :

$$ \rho_k = o \cdot \Pr \{ b_k(l) = o \} + o \cdot \Pr \{ b_k(l) = 1 \} \\ = \Pr \{ b_k(l) = 1 \} = 1 - \Pr \{ b_k(l) = o \} $$

La file k est vide à l'instant $t_k+\theta$ si et seulement si elle était vide à l'instant $t_k$ et si aucune requête simple ne s'est adressée au secteur k entre les instants $t_k$ et $t_k+\theta$. Ces deux événements étant indépendants on a directement :

$$ \Pr \{ b_k(l) = o \} = \pi_o f_o(\theta) $$

et d'après l'égalité (3.8) on obtient le résultat (3.10) qui est indépendant de k.

C.Q.F.D.

Ce dernier résultat permet de retrouver, a posteriori, la condition d'équilibre pour le système en écrivant que $\rho_k$ reste majoré par l'unité :

$$ \frac{\lambda \bar{h} T}{N} < 1 $$

puisque le nombre moyen de requêtes simples acquittées par le secteur k pendant une révolution du tambour doit, si le système est à l'état d'équilibre, être plus petit que le nombre maximum de requêtes simples acquittées par le secteur k pendant cette même révolution, c'est-à-dire 1.

Dans la suite nous utiliserons la notation :

$$ \rho = \frac{\lambda \bar{h} T}{N} \qquad (3.11) $$
## 2.4 DISTRIBUTION DE LA LONGUEUR DE LA FILE ASSOCIEE A UN SECTEUR EN TEMPS CONTINU

### 2.4.1 Calcul de la fonction génératrice

La fonction génératrice $\Pi(z)$ permet de déterminer la distribution de la longueur de la file k, à l'équilibre et pour la suite discrète des instants $\{t_\ell\}_{\ell=0}^\infty$ où la tête de lecture-écriture quitte le secteur k.

Nous allons maintenant déterminer cette même distribution de probabilité en temps continu.

**Théorème 5** : La fonction génératrice de la distribution de probabilité de la longueur de la file k en temps continu, en régime stationnaire, est donnée par :

$$ P(z) = \left(1 - \frac{\lambda \bar{h} T}{N}\right) \frac{e^{-\frac{\lambda T}{N} [1-A_1(z)]}}{z^e - e^{-\lambda T [1-A_1(z)]}} \frac{1-e^{-\lambda T [1-A_1(z)]}}{\lambda T [1-A_1(z)]} \quad (4.1) $$

**Démonstration :**

Soit $(t_\ell, t_\ell+t)$ un intervalle de temps avec $0 \le t < T$, définisons :

$$ \begin{gathered} p_j(t) = \text{Pr} \left\{ \text{la file k contient j requêtes simples à l'instant } t_\ell + t \right\} \\ \text{pour } j = 0, 1, 2, \dots \end{gathered} \quad (4.2) $$

Dans l'intervalle de temps $(t_\ell, t_\ell+t)$ la longueur de la file k ne peut qu'augmenter et le système étant supposé en régime stationnaire on a directement à partir des définitions :

$$ p_j(t) = \sum_{i=0}^{j} \pi_i f_{j-i}(t) \quad \text{pour } j = 0, 1, 2, \dots \quad (4.3) $$

Soit $P(z,t)$ la fonction génératrice de la distribution des probabilités $p_j(t)$, on a :

$$ \begin{aligned} P(z,t) &= \sum_{j=0}^{\infty} p_j(t) z^j = \sum_{j=0}^{\infty} z^j \sum_{i=0}^{j} \pi_i f_{j-i}(t) \\ &= \sum_{j=0}^{\infty} \sum_{i=0}^{j} \pi_i z^i f_{j-i}(t) z^{j-i} \end{aligned} $$
où l'on reconnaît le produit de convolution de $\Pi(z)$ avec $A(z,t)$ ; donc :

$$P(z,t) = \Pi(z) A(z,t) \tag{4.4}$$

Soit maintenant $\{p_j\}_{j=0}^{\infty}$ la distribution "en temps continu" de la longueur de la file associée au secteur k, c'est-à-dire :

$$ \begin{gathered} p_j = \operatorname{Pr} \{ \text{un observateur qui examine le système à des instants quelconques voit } j \text{ requêtes simples dans la file k} \} \\ \text{pour } j = 0, 1, 2, \dots \tag{4.5} \end{gathered} $$

Si l'on suppose que $dF(t)$ est la densité de répartition de $t$, où $t_\ell+t$ est l'instant de l'observation, on a :

$$p_j = \int_0^T p_j(t) \, dF(t) \tag{4.6}$$

Soit $P(z)$ la fonction générateur de la distribution des probabilités $p_j$, on a :

$$ \begin{align*} P(z) &= \int_0^\infty \sum_{j=0} p_j z^j \, dz = \int_0^\infty z^j \int_0^T p_j(t) \, dF(t) \\ &= \int_0^T \left[ \sum_{j=0} p_j(t) z^j \right] \, dF(t) = \int_0^T P(z,t) \, dF(t) \end{align*} $$

et d'après (4.4) :

$$P(z) = \Pi(z) \int_{0}^{T} A(z,t) \, dF(t) \tag{4.7}$$

Si les observations sont réparties uniformément dans le temps la densité de répartition est donnée par :

$$dF(t) = \frac{dt}{T} \tag{4.8}$$

et en reportant cette densité dans (4.7) l'intégration de la formule est immédiate d'après la formule (2.24) d'où la formule (4.1).
2.4.2 Longueur moyenne de la file associée à un secteur :

Théorème 6 : En régime stationnaire, la longueur moyenne de la file associée à un secteur est donnée par :

$$
\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 (4.9)
$$

Démonstration :

Par définition on a :

$$
\bar{n} = \sum_{j=0}^{\infty} j p_j \quad (4.10)
$$

en utilisant la fonction générale P(z) on a aussi :

$$
\bar{n} = \lim_{z \to 1} P'(z) \quad (4.11)
$$

Le calcul de cette limite nous obligerait à appliquer plusieurs
fois la règle de l'Hospital pour lever les indéterminations successives
de la forme o/o. Une méthode plus simple consiste à trouver le développe-
ment limité de P(z) au voisinage de z = 1, puisque d'après la formule (4.11) :

$$
P(z) = 1 + \bar{n} (z - 1) + o(z - 1) \quad (4.12)
$$

C'est cette méthode qui est utilisée en partant de la
formule (4.7)

En utilisant le résultat (2.7), on obtient pour le développement
limité de A₁(z) :

$$
A_1(z) = 1 + \frac{\bar{h}}{N} (z-1) + \frac{A_1''(1)}{2} (z-1)^2 + o(z-1)^2
$$

En partant de l'équation (2.24) et en développant on obtient,
en utilisant la notation (3.11) :

$$
A(z,t) = 1 + \rho \frac{t}{T} (z-1) + \left( \rho \frac{N \cdot A_1''(1)}{2 \bar{h}} \frac{t}{T} + \frac{1}{2} \rho^2 \frac{t^2}{T^2} \right) (z-1)^2 + o((z-1)^2)
$$
d'où, d'une part :

$$ (z - 1) A(z, \frac{T}{N}) = (z - 1) \left[ 1 + \frac{\rho}{N} (z - 1) + o(z - 1) \right] $$

et d'autre part :

$$ z - A(z, T) = (1-\rho)(z-1) \left[ 1 - \left( \frac{\rho^2}{2(1-\rho)} + \frac{\rho}{2(1-\rho)} \cdot \frac{N \cdot A''_1(1)}{\bar{h}} \right) (z-1) + o(z-1) \right] $$

D'où, à partir de l'équation (4.4) et en utilisant les résultats précédents :

$$ P(z,t) = 1 + \left[ \frac{\rho}{N} + \frac{\rho^2}{2(1-\rho)} + \rho \frac{t}{T} + \frac{\rho}{2(1-\rho)} \cdot \frac{N \cdot A''_1(1)}{\bar{h}} \right] (z-1) + o(z-1) \quad (4.13) $$

d'où par intégration par rapport à t :

$$ P(z) = 1 + \left[ \frac{\rho}{N} + \frac{\rho^2}{2(1-\rho)} + \frac{\rho}{2} + \frac{\rho}{2(1-\rho)} \cdot \frac{N \cdot A''_1(1)}{\bar{h}} \right] (z-1) + o(z-1) \quad (4.14) $$

et de là, en rapprochant les formules (4.12) et (4.14), on obtient le résultat (4.9) après simplification.

C.Q.F.D.

Ce résultat permet de trouver l'expression de $\bar{n}$ sous les différentes hypothèses envisagées dans le § 2.2.1

Hypothèse Ha :

$$ \bar{n} = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)} + \frac{\rho}{(N+1)(1-\rho)} \left( \frac{E\{i^2\}}{\bar{h}} - 1 \right) $$

Hypothèse Hb :

$$ \bar{n} = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)} + \frac{\rho}{2N(1-\rho)} \left( \frac{E\{i^2\}}{\bar{h}} - 1 \right) $$

Hypothèse Hc :

$$ \bar{n} = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)} + \frac{\rho}{2(1-\rho)} \left( \frac{E\{i^2\} - E\{r^2\}}{N\bar{h}} + \frac{E\{r\}}{\bar{h}} - 1 \right) $$
Dans ces expressions $E\{f(i)\}$ représente l'espérance de $f(i)$ par rapport à la distribution ${h_i}_i^{\infty}_{i=0}$, c'est-à-dire :

$$E\{f(i)\} = \sum_{i=0}^{\infty} h_i \cdot f(i)$$

En particulier on remarquera pour la troisième hypothèse que si la taille des demandes groupées reste toujours inférieure à $N(h_i = 0 \ si \ i > N)$ alors $A''_1(1)$ est nul et l'expression de $\bar{n}$ est la même que dans le cas étudié par E.G. Coffman, Jr. :

$$\bar{n} = \frac{\rho}{N} + \frac{\rho}{2(1-\rho)}$$
## 2.5 TEMPS MOYEN D'ATTENTE

Les requêtes simples composant une demande groupée sont supposées former un tout ; elles représentent par exemple l'ensemble des pages à pré-charger pour l'exécution d'un programme ou encore l'ensemble des enregistrements composant un même segment. Aussi, est-il plus naturel de s'intéresser au temps d'attente d'une demande groupée plutôt qu'au temps d'attente d'une requête simple de cette demande.

**Rappel :** Le temps d'attente d'une demande groupée est l'intervalle de temps séparant

* l'instant d'arrivée de cette demande dans le système

* de l'instant où la requête simple la plus tardivement servie de cette demande est acquittée.

Pour évaluer ce temps d'attente il faut déterminer, parmi les secteurs qui reçoivent une contribution non nulle, celui qui, après éclatement de la demande groupée, a sa file associée la plus longue. C'est ce secteur qui acquittera la "dernière" requête simple de la demande et la longueur de la file associée déterminera le temps d'attente cherché.

### 2.5.1 Temps moyen d'attente pour une demande composée d'une seule requête simple :

Si l'on ne s'intéresse, parmi les demandes groupées, qu'à celles qui sont constituées d'une seule requête simple alors le temps d'attente est déterminé par la longueur de la file associée au secteur requis.

**Théorème 7 :** Le temps moyen d'attente pour une demande composée d'une seule requête simple est :

$$W_1 = T \left[ \frac{1}{2} + \frac{1}{N} + \bar{n} - \frac{\rho}{N} \right] \quad (5.1)$$

**Démonstration :**

Soit k le seul secteur concerné par la demande.

On suppose que cette demande parvient dans le système un intervalle de temps $t$ ($0 \le t < T$) après un instant $t_0$ de la suite discrète des instants $\{t_\ell\}_{\ell=0}^\infty$ où la tête de lecture-écriture quitte le secteur k.
On suppose, en outre, que, lorsque la requête simple est mise
dans la file k, cette file contient n requêtes simples (1'une d'entre elles
pouvant éventuellement être en service).

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

Deux cas sont à considérer : à l'instant de l'arrivée, $t_\ell+t$,
la tête de lecture-écriture se trouve

- ou bien ailleurs que sur le secteur k, c'est-à-dire $0 \le t \le \theta$
(en reprenant les notations de 2.3.1),

- ou bien sur le secteur k, c'est-à dire $\theta < t < T$ et dans ce cas une
requête simple peut ou non être en service selon qu'à l'instant
$t_\ell+\theta$ la file associée au secteur contenait ou non une requête simple.

Si : $0 \le t \le \theta$,

alors à l'instant $t_\ell+\theta$ la première des (n+1) requêtes simples composant la file à l'instant $t_\ell+t$ sera prise en compte et acquittée dans le même tour à l'instant $t_\ell+1 = t_\ell + T$ (si n=0 la requête considérée est acquittée dans le même tour) ; le temps d'attente est donc :

$$ (T - t) + nT \qquad (w1) $$

La probabilité pour que ces conditions se présentent est donnée, en
reprenant la définition 4.2 et en notant $dF(t)$ la densité de répartition
de l'instant d'arrivée de la demande, par :

$$ [p_n(t)] dF(t) , \quad 0 \le t \le \theta, \ n \ge 0 \qquad (p1) $$

Si : $\theta < t < T$, deux cas peuvent se présenter :

- la file k est vide à l'instant $t_\ell+\theta$, alors aucune requête n'est en
service à l'instant d'arrivée et le temps d'attente pour la requête
considérée est :

$$ (T - t) + (n + 1) T \qquad (w2) $$

La file étant vide à l'instant $t_\ell+\theta$, n requêtes simples doivent
arriver dans la file k entre les instants $t_\ell+\theta$ et $t_\ell+t$, la probabilité
d'être dans ces conditions est donc :
$$ [p_o(\theta) \ f_n(t-\theta)] dF(t) , \ \theta < t < T, \ n \ge 0 \quad (p2) $$

- La file k contient au moins une requête simple à l'instant $t_\ell+\theta$, alors une de ces requêtes simples sera acquittée dans le même tour et le temps d'attente de la requête considérée est :

$$ (T-t) + nT \quad (w3) $$

Si $j$ ($1 \le j \le n$) requêtes simples sont présentes dans la file k à l'instant $t_\ell+\theta$, $n-j$ requêtes doivent arriver entre les instants $t_\ell+\theta$ et $t_\ell+t$ ; la probabilité d'être dans ces conditions est :

$$ [ \Sigma_{j=1}^{n} p_j(\theta) \ f_{n-j}(t-\theta) ] dF(t) , \quad \theta < t < T, n \ge 1 \quad (p3) $$

En remarquant, directement ou d'après les formules (4.4) et (2.24),

que :

$$ \Sigma_{j=0}^{n} p_j(\theta) f_{n-j}(t-\theta) = p_n(t) \quad \text{pour } 0 \le t < T \text{ et } n \ge 0 \quad (5.2) $$

la probabilité (p3) peut donc s'écrire aussi :

$$ [p_n(t) - p_o(\theta) \cdot f_n(t-\theta)] , \quad \theta < t < T , \ n \ge 1 $$

On a donc, en tenant compte des différents cas possibles, comme temps moyen d'attente pour la requête simple considérée :

$$ \begin{align*} W_1 &= \int_0^\theta \sum_{n=0}^\infty [(T-t) + nT] [p_n(t)] dF(t) \\ &\quad + \int_\theta^T \sum_{n=0}^\infty [(T-t) + (n+1)T] [p_o(\theta) \cdot f_n(t-\theta)] dF(t) \\ &\quad + \int_\theta^T \sum_{n=1}^\infty [(T-t) + nT] [p_n(t) - p_o(\theta) \cdot f_n(t-\theta)] dF(t) \end{align*} $$

C'est-à-dire, en tenant compte des regroupements et des simplifications possibles en utilisant l'égalité (5.2) pour $n = 0$, on obtient :
$$
W_1 = \int_0^T \sum_{n=0}^{\infty} [(T-t) + nT] [p_n(t)] dF(t) \\
+ \int_0^T \sum_{n=0}^{\infty} [T] [p_0(\theta) f_n(t-\theta)] dF(t)
$$

ou encore, puisque $\sum_{n=0}^{\infty} p_n(t) = 1$ et $\sum_{n=0}^{\infty} f_n(t-\theta) = 1$ :

$$
W_1 = \int_{0}^{T} (T-t) \, dF(t) \\
+ T \int_{0}^{T} \left[ \sum_{n=0}^{\infty} n p_n(t) \right] dF(t) \\
+ p_0(\theta) T \int_{\theta}^{T} dF(t)
$$

On a, en différentiant P(z,t) et en utilisant les résultats
(4.13) et (4.9) :

$$
\sum_{n=0}^{\infty} n p_n(t) = \lim_{z \to 1} \frac{\partial P(z,t)}{\partial z} = \bar{n} - \frac{\rho}{2} + \rho \frac{t}{T}
$$

on a également, en utilisant la formule (4.3) et le résultat (3.8) :

$$
p_o(\theta) = \pi_o f_o(\theta) = 1 - \rho
$$

On a donc pour $W_1$ :

$$
W_1 = \int_0^T (T-t) dF(t) + T \int_0^T \left( \bar{n} - \frac{\rho}{2} + \rho \frac{t}{T} \right) dF(t) + (1-\rho) \int_0^T dF(t)
$$

Pour déterminer dF(t) on utilise le lemme suivant, dont la
démonstration est donnée en annexe :

**Lemme 3 :**
Considérons une suite d'événements répartis aléatoirement dans le temps.

Si ces événements constituent un processus de Poisson alors
la variable aléatoire :
X = date d'occurrence d'un événement (modulo T)
est distribuée uniformément sur (o,T).

L'événement considéré ici est l'arrivée des demandes de taille 1 au secteur k, il est exponentiel (de paramètre $\frac{\lambda h_1}{N}$) ; le résultat du lemme est donc applicable et l'on a :

$$
dF(t) = \frac{dt}{T}
$$

D'où, par intégration et après quelques simplifications, le
résultat (5.1).
C.Q.F.D.
2.5.2 Temps moyen d'attente pour une demande de taille i (i ≥ 2)

Pour une demande groupée de taille i (i ≥ 2) on se sait pas
dire grand'chose dans le cas général : il faut pouvoir évaluer la distri-
bution de la plus grande des longueurs des files, associées aux secteurs
adressés par la demande groupée, après l'éclatement de celle-ci, c'est-à-
dire une expression de la forme :

$$
s_n = \Pr \{ X = n \}
\quad \text{pour } n = 0, 1, 2, \dots \tag{5.3}
$$

avec :

$$
X = \sup_{k=1}^{N} \left[ \delta_k (n_k + r_k) \right] \tag{5.4}
$$

où :

n_k (1 ≤ k ≤ N) est la variable aléatoire représentant la longueur de
la file k, <u>avant</u> éclatement,

r_k (1 ≤ k ≤ N) est la variable aléatoire représentant la contribution
de la demande groupée à la file k,

et :

$$
\delta_k = \begin{cases} 0 & \text{si } r_k = 0 \\ 1 & \text{si } r_k > 0 \end{cases}
$$

Remarquons que l'expression (5.3) peut prendre une forme, peut
être plus simple, si l'on écrit :

$$
\sigma_n = \Pr \{ X \le n \}
\quad \text{pour } n = 0, 1, 2, \dots \tag{5.5}
$$

$$
\text{et : } s_n = \begin{cases} \sigma_o & \text{si } n = 0 \\ \sigma_n - \sigma_{n-1} & \text{si } n > 0 \end{cases}
$$

(5.6)

L'expression (5.5) pouvant aussi s'écrire :

$$
\sigma_n = \Pr \left\{ \& \left[ \delta_k (n_k + r_k) \le n \right] \right\} \\
\text{pour } n = 0, 1, 2, \dots
$$

pour n = 0, 1, 2,...
L'évaluation de $\{\sigma_n\}_{n=0}^\infty$ est compliquée par le fait que les $\{r_k\}_{k=1}^N$ sont liés par l'équation $r_1 + r_2 + \dots + r_N = i$, pour une demande de taille i, et que les $\{n_k\}_{k=1}^N$ ne sont pas indépendants.

Toutefois si l'on ne sait pas faire cette évaluation dans le cas général, on peut tout de même obtenir certains résultats lorsque le tambour est presque toujours oisif (pour $\rho$ tendant vers zéro).

Ces résultats, très particuliers, présentent peu d'intérêt en soi mais ils permettront, dans le chapitre 3 (lors de la simulation) de faire certaines vérifications et c'est pourquoi nous les mentionnons (les formules, sous l'hypothèse Hb, seront d'ailleurs données sans démonstration).

### 2.5.2.1 Expression de $W_i(o)$ sous l'hypothèse Hb

On n'a pas su trouver de résultat global pour l'expression de $W_i(o)$ si ce n'est une conjecture à la vue des formules donnant $W_i(o)$ pour $i = 1, 2$ et $3$ :

$$W_1(o) = T \left[ \frac{1}{2} + \frac{1}{N} \right]$$

$$W_2(o) = T \left[ \frac{2}{3} + \frac{2}{N} - \frac{1}{6N^2} \right]$$

$$W_3(o) = T \left[ \frac{3}{4} + \frac{3}{N} + \frac{1}{4N^2} - \frac{1}{2N^3} \right]$$

**Conjecture :** Sous l'hypothèse Hb, le temps d'attente d'une demande groupée de taille i est donné, lorsque $\rho = 0$, par :

$$W_i(o) = T \left[ \frac{i}{i+1} + \frac{i}{N} + \frac{1}{N^2} Q_i \left( \frac{1}{N} \right) \right] \quad (5.7)$$

où $Q_i(z)$ est un polynôme de degré $i - 2$ (pour $i \ge 2$).
2.5.2.2 Expression de $W_i(o)$ sous l'hypothèse Hc

On peut ici aboutir à une formule générale énoncée dans le théorème suivant.

**Théorème 8c :** Sous l'hypothèse Hc, lorsque $\rho = 0$, le temps d'attente pour une demande groupée de taille i est donné par :

$$W_i(o) = T \left[ \frac{1}{2} + \frac{i}{N} - \frac{r(r-1)}{2N^2} \right] \quad (5.8)$$

où :

$$i = qN + r \text{ avec } 1 \le r \le N$$

**Démonstration :**

Soit $k$ le secteur adressé par la première requête simple de la demande groupée de taille $i$ (où : $i = qN + r$ avec $1 \le r \le N$, remarquons, d'ailleurs, que, lorsque $r = N$, $q$ n'est pas le quotient de $i$ par $N$).

Supposons que la demande groupée arrive un instant $t$ ($0 < t \le T$) après le passage de la tête de lecture-écriture sur le début du secteur $k$.

Si à l'instant $t$ la tête de lecture se trouve sur le secteur $k+p \pmod N$ ($0 \le p < N$) on a :

$$p \frac{T}{N} < t \le (p+1) \frac{T}{N}$$

et le transfert d'une requête simple de la demande ne pourra, éventuellement commencer que lorsque la tête de lecture-écriture se trouvera au début du secteur $k+p+1 \pmod N$, c'est-à-dire il faudra attendre

$$(p+1) \frac{T}{N} - t$$

<figure><img src="image_6.png" /></figure>
Plusieurs cas sont à considérer :

### $0 \le p < r$

Après l'instant $(p+1) \frac{T}{N}$ q tours devront être effectués complètement pour acquitter les qN premières requêtes simples et un $(q+1)$ème tour complet devra être effectué pour transférer les r requêtes simples restantes. Le temps d'attente est donc :

$$ (p+1) \frac{T}{N} - t + qT + T $$

En reprenant, pour $dF(t)$, la notation du § 2.5.1, la probabilité d'être dans ces conditions est :

$$ dF(t), \quad p \frac{T}{N} < t \le (p+1) \frac{T}{N} \quad \text{pour } 0 \le p < r $$

### $r \le p < N$

C'est la même chose que précédemment sauf pour le $(q+1)$ème tour qui ne sera pas complet mais qui comprend le temps pour la tête de lecture-écriture de se positionner devant le secteur k c'est-à-dire :

$T - (p+1) \frac{T}{N}$, et le temps de transférer les r requêtes simples restantes c'est-à-dire $r \frac{T}{N}$. Le temps d'attente est donc ici donné par :

$$ (p+1) \frac{T}{N} - t + qT + T - (p+1) \frac{T}{N} + r \frac{T}{N} $$

La probabilité d'être dans ces conditions étant :

$$ dF(t), \quad p \frac{T}{N} < t \le (p+1) \frac{T}{N} \quad \text{pour } r \le p < N $$

En regroupant ces différents cas, le temps moyen d'attente pour une demande de taille i, lorsque $\rho=0$, est, compte tenu des simplifications :

$$ W_i(o) = \sum_{p=0}^{r-1} \int_{p}^{(p+1)\frac{T}{N}} \left[ (p+1)\frac{T}{N} + (q+1)(T-t) \right] dF(t) $$

$$ + \sum_{p=r}^{N-1} \int_{p}^{(p+1)\frac{T}{N}} \left[ r\frac{T}{N} + (q+1)(T-t) \right] dF(t) $$
Or, d'après le lemme 3, puisque l'arrivée des demandes de taille i dont la première requête simple s'adresse au secteur k est exponentielle (de paramètre $\frac{\lambda h_i}{N}$) on a :

$$dF(t) = \frac{dt}{T}$$

d'où, après transformation :

$$ 
\begin{align*}
W_i(0) &= r \cdot \int_0^{\frac{T}{N}} \left[ \frac{T}{N} \cdot (q+1) \cdot T - \tau \right] \frac{d\tau}{T} \\
&\quad + \int_{\frac{T}{N}}^T \left[ (q+1) \cdot T + r \cdot \frac{T}{N} - t \right] \frac{dt}{T} \\
&= r \cdot \frac{T}{N} \cdot \left[ q+1 + \frac{1}{2N} \right] \\
&\quad + T \cdot \left( 1 - \frac{r}{N} \right) \cdot \left[ q + \frac{1}{2} \cdot \left( 1 + \frac{r}{N} \right) \right] \\
&= T \cdot \left[ \frac{1}{2} + q + \frac{r}{N} - \frac{r(r-1)}{2N^2} \right]
\end{align*}
$$

D'où la formule (5.8) en remarquant que :

$$q + \frac{r}{N} = \frac{i}{N}$$

C.Q.F.D.
### 3. SIMULATION DU MODELE

La simulation est un outil de mesure qui permet de retrouver et de vérifier certaines formules et de les compléter.

Les résultats établis par l'analyse mathématique du modèle sont, ici, complétés par une simulation du tambour fonctionnant sous les mêmes hypothèses que celles qui ont été posées pour établir les résultats du chapitre 2.

Les hypothèses H1, H2, H3, H4 et H5 ont été reprises dans ce chapitre, l'hypothèse H4 étant complétée dans le § 3.3, d'une part, avec la deuxième hypothèse du § 2.2.1, Hb, d'autre part, avec Hc. Ha, la première hypothèse du § 2.2.1, n'a pas été simulée.

Après la description du programme de simulation et une discussion sur sa validité, on trouvera, sous forme de tableaux et de courbes, l'ensemble des résultats obtenus.
## 3.1 DESCRIPTION DE L'EXPERIENCE DE SIMULATION

La simulation a été réalisée sur une CII 10070, dans un premier temps en utilisant le langage SIMULA 67 ; par la suite le programme de simulation a été réécrit en FORTRAN ce qui a permis d'économiser plus de 98 % du temps machine ! (l'exécution du programme est plus de 50 fois plus rapide en FORTRAN qu'en SIMULA qui est un interpréteur !).

Toutefois on continuera de parler de *processus* pour une partie du programme servant à décrire une action et *d'activation* pour l'exécution de la partie de programme correspondante.

Le principe de synchronisation des processus est le suivant :
au cours d'une activation, le $p_{ième}$ processus trouve comme $p_{ième}$ élément du tableau DATE l'heure courante simulée et il vient modifier cet élément du tableau avant de rendre la main à l'échéancier en y mettant sa prochaine date d'activation. L'échéancier est une partie du programme qui scrute le tableau DATE pour y trouver l'échéance la plus proche et activer le processus correspondant.

La description détaillée des différentes parties du programme se trouve en annexe B avec les listings correspondants, des explications supplémentaires sont données dans les paragraphes suivants.

### 3.1.1 Processus ARRIVEE

C'est le processus qui simule l'arrivée des demandes groupées au tambour.

L'intervalle de temps séparant deux activations successives suit une loi exponentielle négative de paramètre LAMBDA.

A chaque activation le processus génère une demande groupée (jusqu'à concurrence de ND, nombre de demandes sur lequel porte l'expérience de simulation), pour cela, ID étant le numéro courant de la demande générée à cette activation :

* il note l'heure d'arrivée de la demande : HA(ID) = DATE(1)

* il tire au sort la taille I de la demande groupée suivant la loi $\{H(I)\}_{I=0}^{\infty}$ et la note : TAILLE(ID) = I.
Les lois $\{H(I)\}_{I=0}^{\infty}$ utilisées dans les expériences de simulation rapportées ici ont été :

Loi uniforme sur (1,P)

$$H(I) = \begin{cases} \frac{1}{P} & 1 \le I \le P \\ 0 & \text{sinon} \end{cases}$$
de moyenne : $\text{HBARRE} = \frac{P+1}{2}$

Loi "inverse" sur (1,P)

$$H(I) = \begin{cases} \frac{P+1-I}{P(P+1)/2} & 1 \le I \le P \\ 0 & \text{sinon} \end{cases}$$
$\text{HBARRE} : \frac{P+2}{3}$

• il répartit les I requêtes simples sur les différents secteurs : lorsque le secteur K reçoit une requête simple, on place en queue de la file K le numéro de la demande à laquelle appartient la requête : $FILE(K,QUEUE(K)) = ID$.

Suivant les hypothèses envisagées dans la simulation :

- Hb : le numéro de secteur est tiré uniformément sur (1,N) pour les I requêtes simples,

- Hc : le numéro de secteur est tiré uniformément sur (1,N) pour la première requête simple et les I - 1 autres sont réparties sur les I - 1 secteurs consécutifs suivants.

### 3.1.2 Processus TAMBOUR

Ce processus est activé toutes les T/N unités de temps simulé : à chaque fois que le début d'un secteur (de numéro IS) passe sous la tête de lecture-écriture.

Lors d'une activation le processus regarde si la file IS contient une requête simple.

Lorsque la file est vide, NR(IS) = 0, le processus attendra simplement la prochaine activation.

Si la file est non vide la requête de tête est "acquittée" : son heure de départ est notée : HD(FILE(IS,TETE(IS))) = DATE(2) + T/N (DATE(2) + T/N représente l'heure de passage de la tête de lecture-écriture sur la fin du secteur IS) ; lorsque toutes les requêtes simples auront été acquittées c'est bien l'instant de départ de la requête simple la plus tardivement servie de la demande groupée ID qui figurera dans HD(ID).
### 3.1.3 Processus MESURES

A chaque activation, ce processus effectue des mesures en notant les longueurs des files associées à chaque secteur ce qui permettra de connaître en fin de simulation l'histogramme de la longueur des files en "temps continu".

Les intervalles de temps séparant deux activations successives de ce processus sont répartis uniformément sur (0,2T) ce qui correspond en moyenne à une activation pour chaque révolution du tambour.

### 3.1.4 Programme principal

Après une phase d'initialisation le contrôle est donné à l'échecancier pour la gestion des processus.

Dans une première phase les trois processus évoluent jusqu'à ce que toutes les demandes voulues pour l'expérience (ND) aient été générées, alors le "booléen" FIN est positionné et seul le processus TAMBOUR continue à s'exécuter jusqu'à ce que toutes les requêtes contenues dans les files soient acquittées. A ce moment le contrôle est donné à la partie du programme servant au ramassage des résultats et à leur édition.

### 3.1.5 Ramassage des résultats, édition

A la fin de l'expérience les résultats relatifs à une taille donnée I de demande groupée sont rassemblés et la moyenne des temps d'attente est effectuée pour ces demandes :

```
DO 1302 I=1,P
W(I)=0
NI(I)=0
DO 1301 ID=1,ND
IF(TAILLE(ID).EQ.I) W(I)=W(I)+HD(ID)-HA(ID) ; NI(I)=N(I)+1
1301 CONTINUE
IF(NI(I).NE.O) W(I)=W(I)/NI(I)
1302 CONTINUE
```

déterminant ainsi le nombre NI(I) des demandes groupées de taille I et la moyenne W(I) des temps d'attente de ces NI(I) demandes.
L'histogramme de la longueur des files est également constitué et
la longueur moyenne des files, LBARRE, est déterminée pour cette expérience
de simulation :

```fortran
LBARRE = 0
DO 1311 I = 1, LFILE
LBARRE = LBARRE + I * HISTN(I)
1311 CONTINUE
LBARRE = LBARRE/NHIST
```
## 3.2 VALIDITE DU MODELE

Les mêmes hypothèses ont été faites pour la simulation du modèle et pour l'établissement des résultats par l'analyse mathématique.

Toutefois si l'hypothèse H1 est facile à réaliser en simulation il n'en est pas de même en toute rigueur pour les autres hypothèses.

### 3.2.1 Facteurs entachant les résultats

Il est essentiel pour pouvoir comparer les résultats de la simulation aux résultats obtenus par l'approche mathématique :

d'avoir les arrivées des demandes groupées suivant une loi exponentielle (H2),

d'avoir une symétrie entre les N secteurs (H4),

d'effectuer les mesures lorsque le système a atteint son régime stationnaire (H5).

#### 3.2.1.1 Générateurs de nombres aléatoires

Les nombres "aléatoires" sont déterminés par la méthode des générateurs congruents [Knu 69]. La valeur initiale du générateur, $g_0$, fixe la suite $\{g_n\}_{n=1}^{\infty}$ par $g_{n+1} = \alpha \cdot g_n \pmod{2^{32}}$, où $\alpha$ a été choisi à $\alpha = 10003$ en hexadécimal. Cette suite permet de déterminer une suite de nombres $\{\rho(g_n)\}$ répartis "uniformément" sur $(0,1)$ et qui est à la base des tirages des nombres aléatoires pour une loi donnée de densité $F(x)$ par $X_n = F^{-1}[\rho(g_n)]$.

Si les nombres aléatoires vérifient la loi de distribution donnée lorsque le nombre des échantillons tirés au sort est assez élevé il n'en est pas nécessairement de même lorsque le nombre de ces échantillons reste faible et ceci peut introduire une erreur dans les mesures effectuées.

#### 3.2.1.2 Obtention du régime stationnaire

L'hypothèse H5 impose que dans une expérience de simulation les mesures soient effectuées lorsque le système a atteint son régime stationnaire.
On a vu que, lorsque $\rho = \frac{\lambda\bar{h}T}{N} < 1$ cet état stationnaire existe.

Le problème est de savoir à partir de quand et comment il est atteint, étant donné l'ensemble des paramètres définissant l'état du système.

## 3.2.2 Solutions apportées à ces problèmes

### 3.2.2.1 Tests des générateurs de nombres aléatoires

Si l'on veut être sûr que les nombres aléatoires tirés suivant une loi de distribution donnée approchent cette distribution avec une erreur suffisamment faible il faut pouvoir effectuer un nombre de tirages suffisant, ce qui impose, pour la simulation décrite ici, d'avoir un nombre ND suffisant de demandes parvenant au système ; en contrepartie le temps d'exécution du programme en est bien sûr augmenté.

En fait les "nombres aléatoires" sont entièrement déterminés par la loi suivie et par la valeur initiale du générateur. Ici on a cherché à choisir une valeur initiale de ce générateur telle que les tirages effectués permettent un échantillonnage assez large et suffisamment près de la loi de distribution donnée.

Des tests systématiques ont été faits pour la distribution uniforme sur (0,1) : test des 20000 premiers éléments de la suite {$\rho(g_p)}_{p=1}^{\infty}$, pour diverses valeurs initiales des générateurs. Les moments d'ordre n ont été calculés et comparés aux valeurs théoriques :

$$E\{X^n\} = \int_{0}^{1} x^n dx = \frac{1}{n+1}$$

et l'histogramme des échantillons tirés au sort a été établi en notant le pourcentage des échantillons dans les tranches $[m\delta, (m+1)\delta]$ et comparé à l'histogramme théorique :

$$Pr\{m\delta \le X < (m+1)\delta\} = \int_{m\delta}^{(m+1)\delta} dx = \delta$$

Des tests identiques ont été faits pour la valeur initiale du générateur choisi pour la loi de distribution exponentielle négative utilisée par le processus ARRIVEE.
Les résultats en sont portés sur la figure ci-dessous.

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

Sur l'histogramme le signe '+' indique le pourcentage des échantillons dans l'intervalle $[m\delta, (m+1)\delta]$ (où $\delta = 0.1$) et la courbe continue montre où sont situées les valeurs théoriques correspondantes :

$$ \text{Pr} \{m\delta \le X < (m+1)\delta\} = \int_{m\delta}^{(m+1)\delta} \lambda e^{-\lambda x} dx = e^{-n\lambda\delta} (1-e^{-\lambda\delta}) $$

On remarquera que les moments des 5 premiers ordres trouvés pour les 20000 échantillons tirés au sort sont un peu faibles par rapport à leurs valeurs théoriques :
$$
E \{X^n\} = \int_0^\infty x^n \lambda e^{-\lambda x} dx = \frac{n}{\lambda} E \{X^{n-1}\} = \frac{n!}{\lambda^n} E\{1\} = \frac{n!}{\lambda^n}
$$

mais cette erreur sera atténuée par le fait que l'on prendra pour faire les
calculs qui permettront la comparaison entre les résultats du chapitre 2 et
la simulation non pas la valeur théorique de LAMBDA mais la valeur
effective : $L1 = \frac{1}{E\{X\}}$

3.2.2.2. Obtention du régime stationnaire, charge initiale du système :

Si l'on reprend le calcul de W(I), décrit dans 3.1.5, la valeur
obtenue pour W(I) dépend bien évidemment du nombre ND de demandes groupées
parvenues au système, plus précisément du nombre NI(I) de demandes de
taille I sur lequel la moyenne est faite. C'est la variation de W(I) en
fonction NI(I) qui est portée sur les courbes ci-dessous et qui montre
l'évolution vers le régime stationnaire.

A la $\ell$<sup>ième</sup> révolution du tambour l'état probabiliste du système est donné par le vecteur des probabilités $E_\ell$ où :

$$
E_{\ell} = E_{\ell-1}((\pi_{ij})) = E_{0}((\pi_{ij}))^{\ell}
$$

(en reprenant les notations du § 2.3.1). L'état stationnaire (les probabi-
lités à l'équilibre) est donné par :

$$
\lim_{\ell \to \infty} E_{\ell} = \lim_{\ell \to \infty} E_{0}((\pi_{ij})^{\ell})
$$

et ne dépend pas de $E_0$ ; en fait si la limite ne dépend pas de $E_0$, la conver-
gence de $E_\ell$ vers cette limite en dépend.

Sur le diagramme ci-contre (page 52) on a indiqué l'évolution vers
le régime stationnaire dans trois conditions initiales différentes :

1) courbes en pointillé : les files associées à chaque secteur sont vides au début de la simulation (ceci représente le fonctionnement réel du tambour depuis son démarrage),

2) courbes en trait continu : les files sont chargées avec un nombre de requêtes simples égal à NBARRE (calculé d'après la valeur théorique $\bar{n}$ établie dans le § 2.4.1),

3) courbes en tireté : les files sont chargées avec 2*NBARRE.
<figure><img src="image_8.png" /></figure>

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

<footnote>\*\* Evolution vers le régime stationnaire pour l = 1 \*\*</footnote>

<footnote>\*\* Evolution vers le régime stationnaire pour l = 7 \*\*</footnote>
Les expériences ont été réalisées pour ces trois conditions initiales et reproduites pour des valeurs de RHO = 30 %, 70 % et 90 % ; elles ont été effectuées sur 5000 arrivées de demandes groupées au système, la taille de ces demandes groupées étant choisie uniformément sur (1,7). Les courbes portées sont relatives aux demandes groupées de taille 1 et de taille 7.

Ces courbes montrent que les conditions initiales ont très peu d'influence sur l'évolution vers le régime stationnaire lorsque RHO n'a pas de valeurs trop proches de 1 : pour 30 % et 70 % les trois courbes, relatives aux trois conditions initiales différentes, sont pratiquement confondues au-delà des 100 premières arrivées des demandes groupées, qu'elles soient de taille 1 ou de taille 7.

Pour 90 % les conditions initiales ont nettement plus d'influence : l'écart relatif après 750 arrivées de demandes groupées de taille 1 ou 7 reste encore à près de 5 % entre les conditions initiales 1 et 3.

Toutefois la valeur théorique que l'on peut obtenir pour $W_1$ (§ 2.5.1) est à moins de 1 % de la valeur obtenue par simulation pour la condition initiale 2 (celle qui donne le résultat le plus proche). C'est pourquoi tous les résultats de simulation rapportés ici ont été établis pour cette condition initiale.

### 3.2.3 Validité des résultats de la simulation

#### 3.2.3.1 Comparaison avec les résultats théoriques pour une demande de taille 1

Sur la courbe suivante (page 54) sont portés :

* la courbe théorique $W_1$ en fonction de $\rho$ :

$$W_1 = \frac{1}{2} + \frac{1}{N} + \bar{n} - \frac{\rho}{N}$$

en prenant pour $\bar{n}$ l'expression de §2.4.2 sous l'hypothèse Hb (1'unité de temps, ici comme dans les autres résultats rapportés par la suite, est la durée d'une révolution du tambour),
** Comparison :

Theorie/Simulation **

<table><thead><tr><th>Rho</th><th>Theorie</th><th>Simul.</th></tr></thead><tbody><tr><td>.050</td><td>.595</td><td>.646</td></tr><tr><td>.100</td><td>.631</td><td>.647</td></tr><tr><td>.149</td><td>.672</td><td>.653</td></tr><tr><td>.199</td><td>.718</td><td>.705</td></tr><tr><td>.249</td><td>.769</td><td>.760</td></tr><tr><td>.299</td><td>.828</td><td>.848</td></tr><tr><td>.348</td><td>.896</td><td>.910</td></tr><tr><td>.398</td><td>.975</td><td>.990</td></tr><tr><td>.448</td><td>1.069</td><td>1.065</td></tr><tr><td>.498</td><td>1.181</td><td>1.196</td></tr><tr><td>.547</td><td>1.317</td><td>1.335</td></tr><tr><td>.597</td><td>1.487</td><td>1.493</td></tr><tr><td>.647</td><td>1.706</td><td>1.685</td></tr><tr><td>.697</td><td>1.995</td><td>1.940</td></tr><tr><td>.746</td><td>2.399</td><td>2.347</td></tr><tr><td>.796</td><td>2.999</td><td>2.984</td></tr><tr><td>.846</td><td>3.986</td><td>3.883</td></tr><tr><td>.896</td><td>5.915</td><td>5.515</td></tr><tr><td>.945</td><td>11.351</td><td>10.196</td></tr></tbody></table>

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

Coefficient d'utilisation: Rho **

** Resultats de la simulation pour une demande de taille I **
les résultats de la simulation effectuée sous les mêmes hypothèses, en prenant pour valeur RHO non pas la valeur théorique donnée comme paramètre en entrée mais la valeur effective prise en fonction des paramètres calculés en fin de simulation :

$$ RHO = \frac{E\{i\} \cdot T}{E\{X\} \cdot N} $$ (en reprenant les notations des §§ 2.4.2 et 3.2.2.1) - l'expérience est réalisée en choisissant la taille des demandes groupées uniformément sur (1,7).

Comme on peut le constater sur cette courbe les résultats de la simulation concordent très bien avec la théorie (sauf peut être pour les grandes valeurs de RHO - le régime stationnaire étant plus long à s'instaurer comme on peut le constater sur les courbes du § 3.2.2.2).

### 3.2.3.2 Pour une demande de taille $I \ge 2$

On n'a plus alors d'expression théorique du temps d'attente $W_i$ (sauf pour $\rho \to 0$) et l'on ne peut plus effectuer de comparaison. On admettra les résultats de la simulation.
## 3.3 RESULTATS DE LA SIMULATION

Nous avons réuni ici sous forme de courbes certains des résultats obtenus dans diverses expériences réalisées en simulation.

Faute de mesures effectuées sur des systèmes réels les paramètres choisis dans ces expériences ne correspondent certainement pas à la réalité aussi les résultats mentionnés ici ne doivent être pris qu'à titre d'exemples. Toutefois d'autres expériences (non rapportées dans cette étude) avec d'autres valeurs des paramètres ont donné des résultats similaires.

Ces résultats sont relatifs à la variation du temps d'attente d'une demande groupée, mesure d'efficacité choisie dans l'évaluation de ce modèle, en fonction de la charge du système (représentée par $p$) et en fonction de la taille de la demande groupée.

D'autres résultats donnent une indication sur la longueur des files associées aux secteurs.

### 3.3.1 Variation du temps d'attente d'une demande groupée en fonction de la charge du système :

Deux expériences ont été reproduites l'une dans l'hypothèse $Hb$ l'autre dans l'hypothèse $Hc$.

Ces deux expériences ont été réalisées en faisant varier $\rho$, le coefficient d'utilisation d'un secteur défini en 2.3.2, pour un tambour composé de $N = 16$ secteurs,

- dans la première expérience le tambour est soumis à des demandes de transfert dont la taille $I$ varie uniformément sur (1,7)

- dans la deuxième, la taille $I$ de ces demandes varie suivant la loi "inverse" sur (1,10) mentionnée dans le §3.1.1

Dans ces deux cas la taille moyenne des demandes groupées est $HBARRE = 4$.

Pour chacune de ces expériences on a porté (figures 1 à 8) les deux réseaux de courbes $W_i(\rho)$ et $W_i(\rho)/i$ ($W_i(\rho)/i$ correspondant au temps moyen d'attente d'une requête simple appartenant à une demande groupée de taille $i$) et pour chacune des courbes de ces réseaux on a :
<figure><img src="image_11.png" /><figcaption>Fig. 1 : Wᵢ(ρ)
Hypothèse Hb
Loi uniforme sur (1,7)</figcaption></figure>
<caption>Fig. 2 : $W_i(\rho)/i$</caption>

Hypothèse Hb

Loi uniforme sur (1,7)

<figure><img src="image_12.png" /></figure>
<caption>Fig. 3 : W₁(ρ)</caption>

Hypothèse Hb
Loi "inverse" sur (1,10)

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

** Resultats de la simulation pour une demande de taille ! **
<figure><img src="image_14.png" /><figcaption>Fig. 4 : W₁(ρ)/i
Hypothèse Hb
Loi "inverse" sur (1,10)</figcaption></figure>
<figure><img src="image_15.png" /><figcaption>Fig. 5 : $W_1(\rho)$
Hypothèse Hc
Loi uniforme sur (1,7)</figcaption></figure>

** Resultats de la simulation pour une demande de taille 1 **
Fig. 6 : $W_i(\rho)/i$

Hypothèse Hc

Loi uniforme sur (1,7)

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

** Résultats de la simulation pour une demande de taille I **
<figure><img src="image_17.png" /><figcaption>Fig. 7 : W_i(p)
Hypothèse Hc
Loi "inverse" sur (1,10)</figcaption></figure>
<figure><img src="image_18.png" /><figcaption>Fig. 8 : W₁(ρ)/i
Hypothèse Hc
Loi "inverse" sur (1,10)</figcaption></figure>
- les résultats de la simulation par les points marqués '+'
  (ρ variant de 5 % en 5 % depuis 5 % jusqu'à 95 %)

- et une courbe réalisant une approximation continue de ces
  points : d'après l'expression théorique donnant $W_1(\rho)$ on a choisi
  une famille de courbes de la forme $\alpha + \beta \frac{\rho}{1-\rho}$ où $\alpha$ et $\beta$
  sont déterminés par la méthode des moindres carrés (ces
  approximations ne semblent d'ailleurs pas mauvaises sauf
  peut-être lorsque $i$ est grand : $W_{10}(\rho)$ sur les figures 3 et 7).

Pour tous ces différents réseaux on retrouve une même "cassure"
correspondant à la saturation du tambour et à l'effondrement du système
au-delà d'une charge de 75 %.

On peut voir aussi sur ces courbes que si le temps d'attente
d'une demande groupée augmente avec sa taille au contraire le temps
moyen d'attente d'une requête simple appartenant à une demande groupée
décroit lorsque la taille de cette demande augmente. L'étude de ce point
particulier est reprise dans le paragraphe suivant.

### 3.3.2 Variation du temps d'attente d'une demande groupée en fonction de sa taille

Pour cette étude nous ne rapportons qu'une seule expérience,
reproduite pour $\rho = 30\%$, $70\%$ et $90\%$, pour un tambour composé de $N = 8$
secteurs, soumis à des demandes groupées dont la taille $l$ est répartie
uniformément sur $(1,31)$ et sous l'hypothèse $H_0$.

Ici aussi deux réseaux sont tracés : $W_\rho(i)$ et $W_\rho(i)/i$
(figures 9 et 10).

Dans ces réseaux, les courbes réalisant l'approximation des
résultats de simulation sont de la forme $\alpha + \beta i + \gamma \frac{1}{i+1}$ pour $W_\rho(i)$ et
$\alpha + \beta \frac{1}{i} + \gamma \frac{1}{i(i+1)}$ pour $W_\rho(i)/i$, $\alpha$, $\beta$ et $\gamma$ étant encore déterminés par la
méthode des moindres carrés. Ces expressions ont été choisies d'après la
conjecture du § 2.5.2.1 et les approximations ne semblent pas mauvaises.

Ce que l'on voit sur ces courbes c'est que l'asymptote est
très rapidement atteinte : pour $i > 8$, $W_\rho(i)$ est pratiquement linéaire pour
$\rho = 30\%$, et $\rho = 70\%$ (pour $\rho = 90\%$ la dispersion des résultats est trop
grande pour pouvoir conclure) et ce qui ressort, surtout du réseau $W_\rho(i)/i$
(figure 10), c'est la "pénalisation" apportée aux demandes groupées de
petites tailles : le temps d'attente d'une demande de taille $l$ est très
<figure><img src="image_19.png" /><figcaption>Fig. 9 : W$_{p}$(i)</figcaption></figure>

Hypothèse Hb

Loi uniforme sur (1,31)
<figure><img src="image_20.png" /><figcaption>Fig. 10 : $W_p(i)/i$</figcaption></figure>

Hypothèse Hb

Loi uniforme sur (1,31)

** Resultats de la simulation pour un coefficient d'utilisation Rho **
nettement supérieur à la moitié du temps d'attente d'une demande de
taille 2, etc... Toutefois le gain s'affaiblit lorsque la taille des
demandes augmente et il est même négligeable pour des tailles de demandes
supérieures à 8 (remarquons qu'une demande groupée de taille 8 correspond
à la demande du transfert de l'information contenue sur l'ensemble du tambour).

3.3.3 Histogramme de la longueur des files associées aux secteurs

Nous rapportons ici les résultats rassemblés par le processus
MESURES.

Ces résultats ont été obtenus au cours d'une expérience déjà
mentionnée dans le § 3.3.1 : un tambour composé de N = 16 secteurs est
soumis à des demandes de transfert groupées dont la taille I varie uniformément sur (1,7) et sous l'hypothèse Hb.

Les mesures rapportées ici ont été effectuées pendant les
expériences correspondant à p = 30 %, 70 % et 90 %.

Les résultats donnés sur la figure 11 représentent
l'histogramme de la longueur des files associées aux secteurs, en fait
cet histogramme a été normalisé il représente donc le pourcentage de
fois où le processus MESURES a observé une file de longueur n en fonction
de cette longueur.

Ces résultats pourraient être complétés par une analyse
numérique fournissant les coefficients de la fonction génératrice
P(z) = Σ p_n z^n (définie dans le § 2.4) puisque p_n est la probabilité
que la longueur de la file associée à un secteur soit égale à n.

Les histogrammes de la figure 11 ont été approximés par une
fonction de la forme e^[α + β.n + γ (1/n + 1)] où α, β et γ ont été déterminés
par la méthode des moindres carrés à partir des logarithmes des pourcentages
constituant les résultats.

Cette approximation par une exponentielle paraît assez bonne
et ceci pourrait constituer une hypothèse simplificatrice qui permettrait
de pousser certains calculs par des méthodes d'analyse numérique en
remplaçant la fonction P(z) par une expression plus simple.
<caption>Fig. 11 : Pn</caption>

Hypothèse Hb
Loi uniforme sur (1,7)

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

\*\* Histogrammes de La Longueur des Filés associées aux secteurs \*\*
Remarquons aussi sur ces histogrammes que la longueur de la file associée à un secteur reste toujours inférieure à une faible valeur ce qui permet de remplacer $P(z)$ par un polynôme dont le degré n'est pas élevé, les coefficients étant d'ailleurs déterminés par la valeur de l'exponentielle.
## CONCLUSION

Dans l'étude qui vient d'être faite deux méthodes ont été utilisées pour permettre l'évaluation de notre modèle.

La première méthode, l'analyse mathématique, repose sur une théorie classique des files d'attente [Tak 62] et a conduit à l'établissement de formules permettant d'exprimer l'efficacité du modèle.

La deuxième méthode, la simulation, est venue compléter les résultats de l'analyse mathématique.

Ces deux méthodes se complètent et en particulier, si la simulation a permis de déterminer la mesure d'efficacité choisie pour évaluer le modèle là où la première méthode ne le permettait plus, en revanche celle-ci permet de rendre compte de résultats qui peuvent être difficilement obtenus en simulation : l'hypothèse Ha, par exemple, n'est pas simplement réalisable en simulation.

L'étude de notre modèle repose sur plusieurs hypothèses. Si aucune hypothèse spéciale n'a été faite sur la distribution $\{h_i\}_{i=0}^\infty$, les résultats obtenus par cette étude dépendent cependant assez étroitement du caractère poissonnien des arrivées des demandes au tambour (hypothèse H2). Pour juger de la validité des hypothèses, il aurait été intéressant d'avoir des résultats de mesures, prélevées sur des systèmes réels, permettant de confirmer les hypothèses faites ici et d'avoir une idée sur les lois de distribution $\{h_i\}_{i=0}^\infty$.

Plusieurs hypothèses supplémentaires ont été faites dans l'étude du modèle pour permettre de représenter les différentes configurations possibles d'une demande groupée. Les fonctions génératrices $\{C_i(z)\}_{i=0}^\infty$ (établies dans le § 2.2.1) doivent, d'ailleurs, être considérées comme un paramètre du modèle dont l'évaluation permet la représentation d'un type donné d'organisation de l'information sur le tambour.
En particulier si l'on cherche à comparer les résultats obtenus
pour les différentes hypothèses étudiées par l'analyse mathématique et
reprises en simulation on peut se rendre compte que l'on a intérêt à
disposer sur des secteurs contigus du tambour l'ensemble des requêtes
simples faisant partie d'une même demande groupée : le temps d'accès à
l'information sous l'hypothèse Hc est plus court que sous l'hypothèse Hb et
le gain est souvent de l'ordre de 25 % (Voir le tableau de l'annexe C) ce
qui est considérable quand on sait le temps perdu par un système d'exploi-
tation en attente des transferts avec la mémoire secondaire.

Il en résulte que pour un système d'exploitation basé sur la
segmentation une méthode tout indiquée de stockage des segments consiste
à placer les divers enregistrements composant un segment sur des secteurs
contigus du tambour.

De même, dans un système faisant du préchargement, ce but peut être
atteint en implantant l'ensemble des pages composant les "working-sets" des
programmes séquentiellement sur le tambour. Ceci nécessite la connaissance
préalable des programmes mais c'est en général le cas pour les traducteurs
d'un système (compilateurs, relieurs, éditeurs de textes) et pour les
parties non-résidentes du système. Une étude préliminaire et des mesures
sur leurs "working-sets" peuvent ainsi faire gagner une partie non
négligeable du temps d'inactivité d'un système en attente d'entrée-sortie
avec la mémoire secondaire.

Si l'on veut maintenant comparer la stratégie de gestion du tambour
soumis à des demandes de transfert groupées à d'autres stratégies de gestion
d'un tambour, on peut se reporter par exemple à [Cof 69] où l'on trouve
des résultats relatifs à un modèle de tambour dans le contexte d'un système
de pagination fonctionnant sur le principe de page à la demande. Ces
résultats constituent, d'ailleurs, un cas particulier des résultats obtenus
ici pour une valeur particulière du paramètre $\{h_i\}_{i=0}^\infty$.
Les résultats obtenus avec ces deux méthodes :

- d'un côté une stratégie de "préchargement" (pour reprendre, par exemple, l'hypothèse Hb)

- et de l'autre une stratégie de chargement de "page à la demande", ne sont pas directement comparables ; en effet, alors que dans le premier modèle le chargement de i pages est représenté par une demande groupée de taille i, au contraire dans le second il est représenté par i demandes de transfert élémentaire (chaque page étant alors chargée une à une). D'un côté le temps de transfert de ces i pages est égal à $W_i$ (en reprenant les notations du § 2.5) et de l'autre il est égal à $i.W$ (où W est le temps moyen de transfert d'une page dans la deuxième stratégie). En d'autres termes le temps de transfert moyen d'une page est d'un côté de $\frac{W_i}{i}$ et de l'autre de W. Ce sont ces mesures qui sont portées dans le tableau de l'annexe C, ou, plus précisément, en pondérant par $h_i$, probabilité d'avoir une demande de taille i, les mesures d'efficacité portées sont :

$\sum_{i=1}^{\infty} h_i \frac{W_i}{i}$, pour les différentes techniques examinées : hypothèse Hb,

hypothèse Hc et stratégie de page à la demande.

Le gain apporté par la stratégie correspondant à l'hypothèse Hc par rapport à la stratégie de page à la demande est considérable : 55 %. Et bien que les résultats de ces deux stratégies ne soient pas directement comparables, en toute rigueur, l'ordre de grandeur de ce rapport justifierait une étude plus poussée de cette comparaison et montre l'intérêt que présente l'utilisation d'un tambour magnétique soumis à des demandes de transfert groupées.
BIBLIOGRAPHIE

[Aba 69] Joseph ABATE and Harvey DUBNER,
"Optimizing the Performance of a Drum-Like Storage",
I.E.E.E. Trans. on Computers, Vol. C-18, N° 11, November 1969,
pp. 992-997.

[Cof 69] Edward G. COFFMAN, Jr.,
"Analysis of a Drum Input/Output Queue Under Scheduled Operation
in a Paged Computer System",
J.A.C.M., Vol. 16, N° 1, January 1969, pp. 73-90.

[Cof 72] - and Peter J. DENNING,
"Operating Systems Theory",
Preprints de l'Ecole d'Eté du Bréau, Septembre 1972.

[Cor 65] F.J. CORBATO and V.A. VYSSOTSKY
"Introduction and Overview of the Multics System",
Proc. AFIPS Fall Joint Computer Conf., 1965, Vol. 27, pp. 185-196.

[Den 67] Peter J. DENNING,
"Effects of Scheduling on File Memory Operations",
Proc. AFIPS Spring Joint Computer Conf., 1967, Vol. 30, pp. 9-21.

[Dia ] C.I.I.
"DIAD Storage System 7201/7202/7204 User's Manual"
C. 900979 B/En.

[Fel 57] William FELLER,
"An Introduction to Probability Theory and Its Applications",
Wiley, New York, 1957.

[Fra 69] H. FRANK,
"Analysis and Optimization of Disk Storage Devices for Time-Sharing
Systems",
J.A.C.M., Vol. 16, N° 4, October 1969, pp. 602-620.
[Ful 72a] Samuel H. FULLER,
"An Optimal Drum Scheduling Algorithm",
I.E.E.E. Trans. on Computers, Vol. C-21, N° 11, November 1972,
pp. 1153-1165.

[Ful 72b] - and F. BASKETT,
"An Analysis of Drum Storage Units",
Digital System Lab. Stanford Univ., Stanford Calif.,
Technical Report 26, August 1972.

[Jew 67] William S. JEWELL,
"A Simple Proof of : L=λW *",
Operation Research, Vol. 15, Nov.-Dec. 1967, pp. 1109-1116.

[Knu 69] Donald E. KNUTH,
"The Art of Computer Programming",
Vol. 2, Chapter 3 "Random Numbers", Adison Wesley 1969.

[Lit 61] J.D.C. LITTLE,
"A Proof for the Queueing Formula : L=λW",
Operating Research, Vol. 9, 1961, pp. 383-387.

[Mon 42] Paul MONTEL,
"Sur les combinaisons avec répétitions limitées",
Bulletin des sciences mathématiques, 66, 1942, pp. 86-103.

[Tak 62] Lajos TAKACS,
"Introduction to the Theory of Queues",
Oxford University Press, New York, 1962.

[Teo 72] Toby J. TEOREY and Tad B. PINKERTON,
"A Comparative Analysis of Disk Scheduling Policies",
C.A.C.M., Vol. 15, N° 3, March 1972, pp. 177-184.

[Wei 66] Allen WEINGARTEN,
"The Eschenbach Drum Scheme",
C.A.C.M., Vol. 9, N° 7, July 1966, pp. 509-512.
# ANNEXE A

## Lemme 1 :
Le nombre de combinaisons $r$ à $r$ de n objets avec répétitions est donné par :

$$ \Gamma_n^r = \binom{n+r-1}{r} $$

## Démonstration :

L'ensemble des combinaisons $r$ à $r$ avec répétitions des n premiers entiers est l'ensemble des suites ordonnées au sens large :

$$ \{c_i\}_{i=r}^{r}, 1 \le c_1 \le c_2 \le \dots \le c_n \le n $$

D'une suite $\{c_i\}_{i=1}^r$ construisons la nouvelle suite $\{d_i\}_{i=1}^r$ par $d_i = c_i + i - 1$.

La suite $\{d_i\}_{i=1}^r$ est une suite ordonnée au sens strict de $r$ nombres parmi les $n + r - 1$ premiers entiers, c'est une des combinaisons $r$ à $r$ sans répétition des $n + r - 1$ premiers entiers. Ces suites sont donc au nombre de $\binom{n+r-1}{r}$.

Or il y a bijection entre l'ensemble des suites $\{c_i\}_{i=1}^r$ et l'ensemble des suites $\{d_i\}_{i=1}^r$ (d'après la construction même) ; le nombre $\Gamma_n^r$ des suites $\{c_i\}_{i=1}^r$ est donc aussi $\binom{n+r-1}{r}$.

C.Q.F.D.
**Lemme 2 :** On a pour $i = 0, 1, 2, \dots$ et $p \ge i$ :
$$ \sum_{n=0}^{i} (p-n) z^n = \sum_{n=0}^{i} (p+1) (z-1)^n $$

**Démonstration :**

Définissons le polynôme :

$$ F(z) = \sum_{n=0}^{i} (p-n) z^n $$

c'est le coefficient du terme en $t^p$ dans le polynôme :

$$
\begin{align*}
F(z,t) &= \sum_{n=0}^{i} z^n (1+t)^{p-n} t^{p+n-i} \\
&= t^{p-i} (1+t)^p \sum_{n=0}^{i} \left(\frac{zt}{1+t}\right)^n \\
&= t^{p-i} (1+t)^p \frac{1 - \left(\frac{zt}{1+t}\right)^{i+1}}{1 - \frac{zt}{1+t}} \\
&= t^{p-i} (1+t)^{p-i} \frac{(1+t)^{i+1} - (zt)^{i+1}}{(1+t) - (zt)} \\
&= [t^{p-i} (1+t)^{p+1} - z^{i+1} t^{p+1} (1+t)^{p-i}] [1-(z-1)t]^{-1}
\end{align*}
$$

Sous cette dernière forme si l'on recherche le coefficient de $t^p$ dans le développement en série entière de la fraction rationnelle $F(z,t)$, on obtient :

$$ F(z) = \sum_{n=0}^{i} (p+1) (z-1)^n $$

d'où le résultat annoncé.

C.Q.F.D.
**Lemme 3 :** Considérons une suite d'événements répartis aléatoirement dans le temps.

Si ces événements constituent un processus de Poisson alors la variable aléatoire :

X = date d'occurrence d'un événement (modulo T)
est distribuée uniformément sur (0,T).

En d'autres termes, si l'on pose :

$dF(t) = \text{Pr}\{\text{un événement se produit dans l'intervalle de temps}$
$$[\ell T + t, \ell T + t + dt[}$$
$$\text{pour } 0 \le t < T$$

alors :

$$dF(t) = \frac{dt}{T}$$

**Démonstration :**

La suite des événements constituant un processus de Poisson, les intervalles de temps séparant deux occurrences successives de ces événements suivent une loi exponentielle de paramètre $\lambda$ et en particulier si l'on pose :

$$\phi_j(t) = \text{Pr}\{j \text{ événements consécutifs se produisent dans un intervalle de temps de longueur } t\} \\ \text{pour } j = 0, 1, 2, \dots$$

on a :

$$\phi_j(t) = e^{-\lambda t} \frac{(\lambda t)^j}{j!} \quad \text{pour } j = 0, 1, 2, \dots$$

Pour simplifier les notations, posons $t_\ell = \ell T$ et pour un intervalle de la forme $(t_\ell+t, t_\ell+t+dt)$ on écrira dans la suite $(t,t+dt)$.

Considérons un événement, notons le $E^+$, se produisant dans l'intervalle $[t, t+dt[$. Soit $I^+$ l'intervalle $[t_\ell, t_\ell+1[$ contenant $[t, t+dt[$ (Remarquons que $I^+$ n'est pas un intervalle quelconque, de cette forme, puisqu'un événement au moins se produit dans $I^+$).

Pour calculer :

$$dF(\cdot) = \text{Pr}\{E^+ \text{ se produit dans l'intervalle } [t, t+dt[\}$$

supposons :
* que $n(n \ge 1)$ événements se produisent dans $I^+$,

* que $E^+$ est le ième (1 ≤ i ≤ n) de ces n événements,

* que le ième de ces n événements se produit dans $[t, t+dt[$.
Pour cela posons pour $n = 1,2,...$ et $i = 1, 2, ...$ $n:$

$$a(n) = \text{Pr} \{ n \text{ événements se produisent dans } I^+ \}$$

$$b(i|n) = \text{Pr} \{ E^+ \text{ est le i}^{\text{ème}} \text{ événement sachant que} \\ \text{n événements se produisent dans } I^+ \}$$

$$c(i|n) = \text{Pr} \{ \text{le i}^{\text{ème}} \text{ événement se produit dans } [t,t+dt[ \\ \text{sachant que n événements se produisent dans } I^+ \}$$

On a bien sûr :

$$dF(t) = \sum_{n=1}^{\infty} a(n) \sum_{i=1}^{n} b(i|n) \cdot c(i|n)$$

Chacun des n événements étant indépendants des autres, on a :

$$b(i|n) = \frac{1}{n}$$

D'autre part, si le ième événement se produit dans $[t,t+dt[$ sachant que n événements se produisent dans $I^+$, c'est que, sur ces n événements : i - 1 se produisent dans $[o,t[$,

1 dans $[t,t+dt[$,

n - 1 dans $[t + dt, T[$,

(on suppose pour cela que deux événements, ou plus, ne peuvent pas se produire dans $[t,t + dt[ - ce qui est vrai au second ordre près).

On a alors en utilisant l'expression de $\phi_j(t)$ et en négligeant les termes du second ordre :

$$c(i|n) = e^{-\lambda t} \frac{(\lambda t)^{i-1}}{(i-1)!} \cdot \lambda dt \cdot e^{\frac{-\lambda(T-t)}{(n-i)!}} \cdot \frac{n!}{e^{-\lambda T} (\lambda T)^n} \\ = \frac{dt}{T} \cdot n \cdot \frac{1}{T^{n-1}} \binom{n-1}{i-1} t^{i-1} (T-t)^{n-1}$$

d'où :

$$\sum_{i=1}^{n} b(i|n) \cdot c(i|n) = \frac{dt}{T} \frac{1}{T^{n-1}} \sum_{i=1}^{n} \binom{n-1}{i-1} t^{i-1} (T-t)^{n-i} \\ = \frac{dt}{T} \frac{1}{T^{n-1}} (t+T-t)^{n-1} = \frac{dt}{T}$$

d'où :

$$dF(t) = \sum_{n=1}^{\infty} a(n) \sum_{i=1}^{n} b(i|n) \cdot c(i|n) = \frac{dt}{T} \sum_{n=1}^{\infty} a(n) = \frac{dt}{T}$$
ANNEXE B

Programme principal

31: REAL LAMBDANBARREL1
2: INTEGER P,FIN,HISTN(0:500),FILE(16,500),TETE(16),QUEUE(16),
3: * TAILLE(0:20000),H,S,CPT,PAS
4: INTEGER CHAINE(20)
3: DIMENSION DATE(3),HA(0:20000),HD(0:20000),NR(16)
6: C
7: C
8: C
9: C
10: C
11: C
12: C
13: C
14: C
15: C ***** INITILISATION DES PARAMETRES DU PROGRAMME *****
16: C
17: LFILE=500
18: ND=20000
19: N=16
20: LAMBDA=1.0
21: C
22: C
23: C
24: C
25: C ***** ENTREE DES PARAMETRES DE CETTE EXPERIENCE
26: C
27: 1000 READ(105,900,END=9999,ERR=9999) RHOP
28: C
29: C ***** CALCUL DES PARAMETRES THEORIQUES
30: C ***** (AVEC L'HYPOTHÈSE HB)
31: C
32: HBARRE=(P+1)/2.0
33: T=(RH0*N)/(LAMBDA*HBARRE)
34: A2=(P+1)*(P-1)/3.0
35: NBARRE=RH0*(1.0/N+0.5*(1.0+A2*N/HBARRE)/(1.0-RH0))
36: N1=0.5+1/N+NBARRE-RH0/N
37: C
38: C
39: C ***** MISE A JOUR DE LA LÖNGUEUR DES FILES
40: C
41: CB 1001 K=1,N
42: TETE(K)=QUEUE(K)=1;NR(K)=0
43: 1001 CONTINUE
44: C
45: C
46: I=NBARRE*N+C.5
47: IF(I.EC>0) GOTO 1010
48: K=1
49: CB 1002 C=1,I
50: FILE(K,QUEUE(K))=0
51: QUEUE(K)=QUEUE(K)+1
52: NR(K)=NR(K)+1
53: K=K+1
54: IF(K.GT.N) K=1
55: 1002 CONTINUE
56: C
57: C
58: C
59: C
60: C ****** INITILISATION DES PARAMETRES DES PROCESSUS ******

61: C

62: C

63: C ****** POUR ARRIVEE

64: C

65: 1010 DATE(1)=0

66: H=1789;S=1871;L=-782098491

67: FIN=0

68: ID=1

69: C

70: C

71: C ****** POUR SERVICE

72: C

73: 1020 DATE(2)=DATE(1)

74: DELAI=T/N

75: IS=0

76: CPT=0

77: C

78: C

79: C ****** POUR MESURES

80: C

81: 1030 DATE(3)=DATE(1)

82: DEUXT=T*2

83: OS 1031 I=0,LFILE

84: MISTN(I)=0

85: 1031 CONTINUE

86: NHIST=0

87: M=0367961

88: C

89: C

90: C

91: C

92: C ****** SYNCHRONISATION DES PROCESSUS ******

93: C

94: 1200 I=1

95: IF(DATE(2).LT.LATE(1)) I=2

96: IF(DATE(3).LT.LATE(1)) I=3

97: GSTO (2100,2200,2300),I

98: C

99: C

100: C ****** TOUTES LES DEMANDES SONT PARVENUES AU SYSTEME

101: C ****** SELL LE PROCESSUS TAMBOUR RESTE ACTIF

102: C

103: 1201 FIN=1

104: GOTO 2200

105: C

106: C

107: C

108: C

109: C

110: C

111: C ****** EDITION DES RESULTATS DE L'EXPERIENCE ******

112: C

113: 1300 CONTINUE

114: CALL EDITION

115: C

116: C

117: C ****** ON EN A TERMINE POUR CETTE EXPERIENCE

118: C

119: GOTO 1000
Processus ARRIVEE

120: C ** ******** ********** ** ** ** ********** **********
121: C **** ********** ********** ** ** ** ********** **********
122: C ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
123: C ********** ********** ********** ** ** ** ********** **********
124: C ********** ********** ********** ** ** ** ********** **********
125: C ** ** ** ** ** ** ** ** ** ** ** ** ** ** ** **
126: C ** ** ** ** ** ** ** ** ** ** ** ********** **********
127: C ** ** ** ** ** ** ** ** ** ** ********** **********
128: C
129: C
130: C
131: C **** TIRAGE DE LA TAILLE DE LA DEMANDE
132: C
133: 2100 CONTINUE
134: CALL INVERSE(P,H,I)
135: TAILLE(ID)=I,HA(ID)=DATE(1)
136: C
137: C
138: C **** ECLATEMENT DES REQUETES SIMPLES
139: C **** (AVEC L'HYFOTHESE HB)
140: C
141: D8 2101 J=1,I
142: CALL IUNFRM(N,S,K)
143: FILE(K,QUEUE(K))=ID
144: QUEUE(K)=QUEUE(K)+1
145: IF(QUEUE(K).GT.LFILE) QUEUE(K)=1
146: NR(K)=NR(K)+1
147: 2101 CONTINUE
148: C
149: C
150: C **** PASSAGE A LA DEMANDE SUIVANTE
151: C
152: ID=ID+1
153: IF(ID.GT.ND) GETB 1201
154: CALL NESEXP(LAMBDA,L,X)
155: DATE(1)=DATE(1)+X
156: GETB 1200
157: C
158: C
159: C
160: C
161: C
162: C
163: C
164: C
165: C
166: C
167: C
168: C
169: C
170: C
171: C
172: C
173: C
174: C
175: C
176: C
177: C
178: C
179: C
Processus TAMBOUR

180: C ********** ** ** ** ********** ********** ** ** **********
181: C ********** **** ** ** ********** ********** ** ** **********
182: C ** ** ** ********** ** ** ********** ** ** **********
183: C ** ********** ** ** ** ********** ** ** **********
184: C ** ********** ** ** ********** ** ** **********
185: C ** ********** ** ** ********** ** ** **********
186: C ** ** ** ********** ********** ********** **********
187: C ** ** ** ********** ********** ********** **********
188: C
189: C
190: C
191: 2200 IS=IS+1
192: C IF(IS.GT.N) IS=1
193: C
194: C IF(NR(IS).EQ.0) GBT0 2201
195: C HD(FILE(IS,TETE(IS)):=DATE(2)+DELAI
196: C TETE(IS)=TETE(IS)+1
197: C IF(TETE(IS).GT.LFILE) TETE(IS)=1
198: C NR(IS)=NR(IS)-1
199: 2201 CONTINUE
200: C
201: C DATE(2)=DATE(2)+DELAI
202: C IF(FIN.EQ.0) GBT0 1200
203: C IF(NR(IS).NE.0) CPT:=G5T0 2200
204: C CPT=CPT+1
205: C IF(CPT-N) 2200,1300,1300
206: C
207: C
208: C
209: C
210: C
211: C
212: C
213: C
214: C
215: C
216: C
217: C
218: C
219: C
220: C
221: C
222: C
223: C
224: C
225: C
226: C
227: C
228: C
229: C
230: C
231: C
232: C
233: C
234: C
235: C
236: C
237: C
238: C
239: C
Processus MESURES

240: C
241: C
242: C
243: C
244: C
245: C
246: C
247: C
248: C
249: C
250: C
251: 2300 08 2301 K=1,N
252: HISTN(NR(K))=HISTN(NR(K))+1
253: 2301 CONTINUE
254: NHIST=NHIST+N
255: C
256: CALL UNFRM(DEDAT,MAX)
257: DATE(3)=DATE(3)+X
258: GSTB 1200
259: C
260: C
261: C
262: C
263: C
264: C
265: C
266: C
267: C
268: C
269: C
270: C
271: C
272: C
273: C
274: C
275: C
276: C
277: C
278: C
279: C
280: C
281: C
282: C
283: C
284: C
285: C
286: C
287: C
288: C
289: C
290: C
291: C
292: C
293: C
294: C
295: C
296: C
297: C
298: C
299: C
ANNEXE C

<table><thead><tr><th>RHO</th><th>HB</th><th>HC</th><th>HD</th></tr></thead><tbody><tr><td>.05</td><td>.368</td><td>.268</td><td>.589</td></tr><tr><td>.10</td><td>.368</td><td>.273</td><td>.618</td></tr><tr><td>.15</td><td>.380</td><td>.282</td><td>.650</td></tr><tr><td>.20</td><td>.402</td><td>.298</td><td>.687</td></tr><tr><td>.25</td><td>.438</td><td>.324</td><td>.728</td></tr><tr><td>.30</td><td>.480</td><td>.353</td><td>.775</td></tr><tr><td>.35</td><td>.512</td><td>.379</td><td>.830</td></tr><tr><td>.40</td><td>.553</td><td>.407</td><td>.893</td></tr><tr><td>.45</td><td>.598</td><td>.441</td><td>.968</td></tr><tr><td>.50</td><td>.665</td><td>.493</td><td>1.058</td></tr><tr><td>.55</td><td>.743</td><td>.555</td><td>1.167</td></tr><tr><td>.60</td><td>.830</td><td>.616</td><td>1.303</td></tr><tr><td>.65</td><td>.940</td><td>.695</td><td>1.478</td></tr><tr><td>.70</td><td>1.084</td><td>.797</td><td>1.710</td></tr><tr><td>.75</td><td>1.312</td><td>.968</td><td>2.033</td></tr><tr><td>.80</td><td>1.666</td><td>1.238</td><td>2.514</td></tr><tr><td>.85</td><td>2.180</td><td>1.628</td><td>3.305</td></tr><tr><td>.90</td><td>3.096</td><td>2.369</td><td>4.849</td></tr><tr><td>.95</td><td>5.670</td><td>4.347</td><td>9.204</td></tr></tbody></table>

Explication :

La mesure portée dans ce tableau est : $\sum_{i=1}^{\infty} h_i \frac{W_i(\rho)}{i}$ pour différentes valeurs de $\rho$ et sous les différentes hypothèses Hb, Hc et Hd (Hd étant la stratégie de page à la demande : cas particulier du § 2.2.1.4).

Les résultats ont été tirés d'une expérience réalisée avec un tambour à N = 16 secteurs soumis à des demandes de transfert groupées dont la taille varie uniformément sur (1,7).