# Application de la méthode de décomposition au traitement de modèles de systèmes informatiques

Geneviève Jomier, Alain Kurinckx

► To cite this version:

Geneviève Jomier, Alain Kurinckx. Application de la méthode de décomposition au traitement de modèles de systèmes informatiques. [Rapport de recherche] IRIA-RR-319, IRIA. 1978, pp.16. hal-04716548

HAL Id: hal-04716548

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

Submitted on 1 Oct 2024

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
Dw-04264. RR319

RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

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

laboratoire de recherche
en informatique
et automatique

APPLICATION DE LA MÉTHODE
DE DÉCOMPOSITION
AU TRAITEMENT DE MODÈLES
DE SYSTÈMES INFORMATIQUES

Geneviève JOMIER
Alain KURINCKX

Rapport de Recherche N° 319

Juillet 1978

16p.
APPLICATION DE LA METHODE DE DECOMPOSITION AU
TRAITEMENT DE MODELES DE SYSTEMES INFORMATIQUES

G. Jomier*, A. Kurinckx**

RESUMÉ

Nous rappelons les principes de la méthode de décomposition pour le traitement de certains réseaux de files d'attente. Nous l'appliquons alors à la solution de deux problèmes posés par les systèmes multiprogrammés à mémoire virtuelle : la comparaison de deux politiques d'allocation de la mémoire centrale et l'étude d'une méthode de contrôle de la multiprogrammation.

ABSTRACT

We recall the principles of the decomposition method for the study of markovian queuing net-
works. We use it to solve two problems occuring in multiprogrammed systems with virtual memo-
ry : the comparison of two central memory allocation policies and the study of a control of multi-
programming method.

<footnote>Université de Nancy 1, UER Sciences Mathématiques, CO140, 54037 NANCY CEDEX</footnote>

<footnote>** IRIA-LABORIA, B.P. 105, 78150 LE CHESNAY</footnote>
# 1. - INTRODUCTION

La modélisation des systèmes informatiques conduit fréquemment à des réseaux de files d'attente dont les équations ne peuvent être résolues expliquement. Les méthodes numériques ne sont pas généralement applicables à cause de la dimension de l'espace d'états. Le but de cet article est de montrer comment une technique approximative (la méthode de décomposition [Courtois 77]) permet de traiter de tels modèles.

Dans une première partie, nous rappelons les principes de la méthode sans entrer dans les détails mathématiques, mais en soulignant physiquement où se situe l'approximation.
Dans une seconde partie, nous décrivons le modèle mathématique uti-
lisé pour évaluer les performances des systèmes multiprogrammés à mémoire
virtuelle. Ce modèle central est ensuite étendu pour l'étude de deux applica-
tions dont la solution est obtenue par décomposition.

Le but de la première est la comparaison de deux politiques d'allo-
cation de la mémoire centrale [Jomier 78]. La seconde fournit les performances
d'un système à mémoire virtuelle contrôlé par injection aléatoire des program-
mes [Gelenbe 78].

2. - PRINCIPE DE LA METHODE DE DECOMPOSITION

La décomposition des réseaux de files d'attente est une application
des résultats de Simon et Ando [Simon 61] sur l'agrégation des variables
d'état d'un système dynamique. Elle a été développée par Courtois [Courtois 77]
dont nous reprendrons les points essentiels.

L'idée de la décomposition est de former, avec les variables d'état
d'un système complexe, un petit nombre de groupes (agrégats) tels que :

- les interactions des variables à l'intérieur d'un groupe peuvent être étudiées comme si les interactions avec l'extérieur n'existaient pas,

- les interactions des groupes s'étudient sans qu'il soit nécessaire
dé considérer les interactions entre variables à l'intérieur de
chaque groupe.

Les systèmes satisfaisant aux conditions nécessaires pour que la
technique d'agrégation fournisse des résultats exacts sont dits complètement
décomposables. Ils sont formés d'un certain nombre de sous-systèmes qui évo-
luent indépendamment les uns des autres.

Lorsque les interactions entre groupes de variables ne sont pas
nulles mais faibles par rapport aux interactions à l'intérieur des groupes,
Simon, Ando puis Courtois ont étudié les conditions pour que l'agrégation des
variables donne encore des résultats satisfaisants ; on parle alors de
systèmes quasi décomposables.

Considérons un système stochastique décrit par les équations :

$$
(2.1) \quad p(t+1) = p(t)Q
$$

où p(t) est le vecteur ligne de probabilité des états à l'instant t et Q
la matrice stochastique de transition d'ordre k x k. Considérons également le
système de même dimension :
$$ (2.2) \qquad p^*(t+1) = p^*(t)Q^* $$

dans lequel la matrice $Q^*$ est composée de K matrices carrées sur la diagonale principale, les autres éléments étant nuls. Le système (2.2) est, dans ces conditions, complètement décomposable.

Supposons qu'il existe une permutation des lignes et colonnes de Q telle qu'on peut écrire :

$$ Q = Q^* + \varepsilon C $$

dans laquelle C est une matrice carrée dont les sommes des éléments de chaque ligne est nulle ; $\varepsilon$ est un nombre réel positif, petit comparé aux éléments de $Q^*$. Le système (2.1) est alors quasi décomposable et peut être étudié en considérant le système complètement décomposable (2.2). Les relations entre les évolutions temporelles des deux systèmes sont données par les théorèmes de Simon et Ando [SiA. 61] dont nous n'exposerons ici qu'une interprétation physique.

Lorsqu'on étudie la dynamique des systèmes (2.1) et (2.2), on distingue, si $\varepsilon$ est suffisamment petit, quatre périodes séparées par les instants $T_1, T_2, T_3$ :

- transitoire à court terme ($t < T_1$) les vecteur $\beta(t)$ et $\beta^*(t)$ évoluent de façon identique,

- équilibre à court terme ($T_1 < t < T_2$) : un état stationnaire est atteint dans chaque sous-système de (2.1) et (2.2),

- transitoire à long terme ($T_2 < t < T_3$) le système quasi décomposable évolue vers son état d'équilibre global mais les valeurs relatives des variables obtenues dans chaque sous-système à l'équilibre à court terme ne varient pratiquement pas,

- équilibre à long terme ($t > T_3$) : le système (2.1) atteint son équilibre global sans que les équilibres locaux soient affectés.

La méthode de décomposition ramène donc l'étude des systèmes quasi-décomposables à celle de systèmes plus petits en travaillant en deux étapes :

- calcul de l'état d'équilibre de K sous-systèmes indépendants,

- puis étude d'un nouveau système à K dimensions dont les variables d'état sont les agrégats obtenus dans la première étape.

La précision des résultats d'équilibre global est liée à la qualité de l'approximation (ordre de grandeur de la constante $\varepsilon$) et a été analysée en détail par Courtois [Cou. 77].
La décomposition peut être considérée comme une hiérarchie à deux niveaux dont l'un est occupé par les variables du système original (micro-variables) et l'autre par les agrégats (macrovariables). Cette hiérarchie peut être étendue à plus de deux niveaux, chaque variable d'un certain niveau étant un agrégat de variables du niveau immédiatement inférieur. Nous verrons un exemple de hiérarchie à trois niveaux dans le modèle de contrôle par injection aléatoire.

La méthode de décomposition s'applique donc aux réseaux de files d'attente markoviens. Une agrégation de variables se traduit dans un réseau de files d'attente par la notion de *serveur équivalent étudiée* en détail dans [Brandwajn 74] lorsque les échanges entre l'agrégat et le monde extérieur se font par l'intermédiaire d'un seul serveur. Cette technique consiste à remplacer la partie du réseau correspondant aux variables d'état de l'agrégat par une file d'attente unique. Les deux réseaux, avant et après remplacement, sont équivalents si et seulement si :

- les distributions de probabilité du nombre total de clients dans chacun des deux systèmes sont identiques,

- les distributions de probabilité des variables d'état qui n'appartient pas à l'agrégat sont identiques.

La distribution des temps de service du serveur équivalent doit être évaluée en tenant compte de ces contraintes. Les paramètres nécessaires sont obtenus en étudiant le sous-réseau à l'état d'équilibre, en appliquant les principes de la méthode de décomposition.

### 3. - MODELISATION DES SYSTEMES A MEMOIRE VIRTUELLE

Les réseaux de files d'attente conduisent à des résultats intéressants dans l'étude des problèmes posés par les systèmes multiprogrammés à mémoire virtuelle [Den. 68] allocation de ressources, optimisation, contrôle pour éviter l'écroulement des performances.

Pour faciliter l'exposé des deux problèmes traités dans la suite, il est nécessaire de décrire d'abord le réseau classique à serveur central utilisé pour modéliser les ressources du système et les comportements de programme.

Le réseau fermé dans lequel circulent N processus (au sens informationique) statistiquement identiques comprend n+1 files d'attente à un serveur (figure 1) : l'unité centrale (numérotée 0), le tambour de pagination (numéroté 1), support de la mémoire secondaire et n-1 périphériques d'entrée-sortie.
<figure><img src="image_2.png" /></figure>

Boucle de ressources

<caption>Figure 1</caption>

Toutes les variables aléatoires qui interviennent dans le modèle sont indépendantes. La politique de service est, pour chaque file, premier-arrivé-premier-servi ; les lois de service sont exponentielles de paramètre $\mu_i$ aux unités $i = 0, ..., n$ et on notera $\nu_i$ la longueur de la file i.

Le comportement des programmes est décrit par les lois inter-événements (en temps virtuel) exponentielles de moyenne :

- c pour le temps total de calcul à l'unité centrale,

- $s_i$ pour le temps entre deux demandes consécutives d'entrée-sortie au périphérique $i, 1 \le i \le n$.

Dans le cas où on utilise un modèle de comportement à durée de vie, intervient dans $s_1$, la fonction de Belady-Kuehner [Belady 69] $e(N) = a(\frac{R}{N})^k$ qui exprime le temps moyen (virtuel) entre deux interruptions successives d'un processus pour défauts de page (référence à une adresse située dans la mémoire secondaire). Dans cette expression, R est la dimension de la mémoire principale, N le degré de multiprogrammation, a et k des cons-tantes dépendant du système et des caractéristiques des programmes. En parti-culier k est le coefficient de localité des programmes dont la valeur obtenue expérimentalement est généralement comprise entre 1.2 et 2.5.

Avec ces hypothèses, le modèle à serveur central est un réseau de Gordon et Newell dont on peut obtenir la solution analytique. Dans le cas où $s_1 = e(N)$, le taux d'activité de l'unité centrale ($A_o(N)$) est représenté à la figure 2. Le phénomène d'écroulement apparaît clairement ; on observe en outre, l'existence d'un degré optimal $N_k$ qui maximise les performances. Par contre, si $s_1$ ne dépend pas de N, la courbe $A_o(N)$ est toujours croissante.
<figure><img src="image_3.png" /></figure>

## 4. - COMPARaison DE DEUX aLgoRITHMES D'allocatION DE LA MEMOIRE CENTRALE

Nous nous intéresserons à la comparaison de deux systèmes qui diffèrent par l'allocation de la mémoire centrale :

- dans le cas de l'allocation statique, notée A.S., l'admission d'un processus au partage de la mémoire n'a lieu que lorsque le système peut lui allouer tout l'espace mémoire nécessaire à son déroulement. L'allocation dure jusqu'à la fin du processus.

- dans le cas de l'allocation dynamique, notée A.D., la mémoire est gérée en "page à la demande" et, pour éviter l'écroulement (cf. 3.), le degré de multiprogrammation N est borné supérieurement à N<sub>k</sub> (k paramètre de Belady et Kuehner) valeur pour laquelle le taux d'utilisation de l'unité centrale, U.C., est maximal.

### 4.1. - Le modèle physique

Le système sera modélisé par un réseau de files d'attente $\mathbb{R}$ (fig. 3a) composé de la file des processus candidats à l'entrée en mémoire centrale, dite "file d'ordonnancement" et notée f.o., gérée en FIFO suivie du réseau "boucle de ressources", noté b.r. L'entrée et la sortie de la b.r. se font au serveur central (correspondant à l'UC); les caractéristiques de la b.r. étudiée isolément comme un réseau fermé à N clients ont été données en 3.

<figure><img src="image_4.png" /></figure>
Le nombre de processus présents dans $\mathcal{R}$ est $M = \nu_{-1}+N$ ; les arrivées sont supposées poissonniennes de paramètre $\lambda$.

Les modèles des deux types d'allocation différeront donc :

1) au niveau des passages de la f.o. à la b.r. ; pour l'A.S. il faut connaître la probabilité $\Pi(x)$ qu'un processus demande un espace mémoire de taille $x$.

$x \in ]0,R]$ où R est la taille de la M.C.

2) au niveau des échanges mémoire centrale (M.C) - mémoire secondaire (M.S.). Pour l'A.D. qui travaille en page à la demande, chaque transfert M.C.-M.S. portera sur une page. Mais dans l'A.S. les transferts M.C.-M.S. concerneront des modules complets et la taille moyenne des informations transférées à chaque échange sera supposée proportionnelle en nombre de pages à la taille moyenne des programmes traités.

Donc si on note $e'$ le temps (virtuel) moyen entre deux demandes d'échange M.C.-M.S. pour un programme, on aura :

$s_1 = e'$ pour l'A.S.,

$s_1 = [e'^{-1} + e(N)^{-1}]^{-1}$ pour l'A.D.,

les défauts de pages ($e(N)$) et les demandes de première page de modules ($e'$) se superposant.

## 4.2. - Les équations du modèle

D'après 3. et 4.1, le réseau $\mathcal{R}$ est markovien, mais nous ne pourrons obtenir une solution stricte à cause des dépendances entre files dans le cas de solution analytique et à cause du trop grand nombre d'états possibles pour une solution numérique. Nous allons donc chercher des solutions approchées en utilisant la méthode de décomposition de Courtois.

Celle-ci est développée, cf. 2., dans le cas où le nombre d'états possibles du système est fini, ce qui n'est pas notre cas puisque $\mathcal{R}$ est ouvert.

Nous nous ramènerons à un nombre fini d'états en considérant non plus $\mathcal{R}$, mais $\mathcal{R}'$, réseau fermé à L clients, composé de $\mathcal{R}$ "fermé" sur une file F, de service exponentiel de paramètre $\lambda$ (fig. 3b). Quand $\mathcal{R}$

est ergodique (seul cas qui nous intéresse) la solution de $\mathcal{R}'$ est une approximation de celle de $\mathcal{R}$ d'autant meilleure que L est grand (puisqu'on élimine ainsi les états de $\mathcal{R}$ qui ont une très faible probabilité d'apparaître).

<figure><img src="image_5.png" /><figcaption>Figure 3b</figcaption></figure>
L'étant fixé, la répartition des clients dans $\mathbb{R}'$ est totalement décrite par $v = (v_{-1}, v_0, v_1, \dots, v_n)$ ; $v_i \ge 0, i = -1, 0, \dots, n$ ; $\sum_{i=-1}^{n} v_i \le L$ qui sera le vecteur d'états, noté $v'$, pour l'A.D.

Pour l'A.S., il faut de plus connaître X, l'espace mémoire occupé par les $N = \sum_{i=0}^{n} v_i$ processus présents dans la b.r. : les vecteurs d'états seront les $v' = (X,v)$ où $X \in [0,R]$.

Le réseau $\mathcal{R}'$ pourra donc, dans les deux cas, être décrit par un système d'équations du type (2.1) : $p(t+1) = p(t) \cdot Q$, si l'unité de temps est suffisamment petite pour que la probabilité de plus d'une fin de service en une unité de temps puisse être négligée.

### Description de la matrice des transitions Q

Ces transitions non nulles $Q(v',v'_i)$ seront :

* égales à $\frac{1}{s_i}$ et à $\mu_i$ à l'intérieur de la b.r.

* égales à $\frac{1}{c}$ et à $\lambda$ pour les entrées de la f.o., les passages f.o.-b.r. et les sorties de la b.r. dans le cas de l'A.D.

* pour l'A.S. les transitions non intérieures à la b.r. seront aussi en $\lambda$ et en $\frac{1}{c}$ mais ici ces coefficients seront multipliés par des probabilités pour que les processus candidats à l'entrée en b.r. disposent ou non de l'espace qui leur est nécessaire.

$$ \cdot Q(v',v') = 1 - \sum_{v'_i \neq v'} Q(v'; v'_i) $$

Les expressions exactes ont été développées dans [Jomier 78].

## 4.3. Résolution

L'échelle des temps est de l'ordre de 10 msec à l'intérieur de la b.r. et de la seconde à son extérieur. Par suite, l'écriture de $\lambda$ pour l'A.D. et l'A.S. montre que $Q$ est quasi décomposable et l'étude du comportement du système pourra se faire en deux temps :

1) agrégation des états de la b.r. et calcul du serveur équivalent à la boucle : son taux de service sera $\mu_o(N) = \frac{1}{c} \cdot A_o(N)$ où $A_o(N)$ est le taux d'activité du serveur central dans le réseau b.r. fermé à N clients (cf. 3.).

2) Calcul du comportement du système agrégé, composé, dans $\mathcal{R}'$, de la f.o. suivie de la file équivalente à la b.r. (fig. 3c) : pour cela
ces deux dernières sont remplacées par une file $\varphi$ (fig. 3d), FIF$\varphi$
de longueur $M = \nu_{-1} + N$ et de taux de service $\mu(M) = \frac{a_0(M)}{c}$.
Définissons $a_0(M)$ :

<figure><img src="image_6.png" /><figcaption>Figure 3d</figcaption></figure>

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

a) si N est l'unité à $N_{max}$ $a_0(M) = A'_0(N_{max}, M) = \begin{cases} A_0(M) & \text{si } M \le N_{max} \\ A_0(N_{max}) & \text{si } N > N_{max} \end{cases}$ c'est le cas de l'A.D. où $N_{max} = N_k$.

b) pour l'A.S. $N_{max}$ est une variable aléatoire :

$$a_0(M) = \sum_n P[N_{max} = n] A'_0(n,M)$$

Le calcul de $P[N_{max} = n] = \gamma(n)$, loi de probabilité du degré maximal de multiprogrammation dans l'A.S. est fait en étabtant en fonction de $\pi$, loi de la taille des processus, les $Q_1(N,X; N',X')$, probabilités de transition des états(N,X) où N processus en b.r occupent un espace X, dans le cas où la f.o. n'est jamais vide (pour avoir le degré maximal). On en déduit les probabilités marginales de transitions $Q_2(N; N')$ puis les $\gamma(n)$, solution au système linéaire $\gamma = \gamma Q_2$.

### 4.4. - Comparaison des deux algorithmes d'allocation

La comparaison à l'état stationnaire des temps de réponses des deux types d'allocation se ramène à la comparaison des temps moyens de présence T d'un client dans une file $\varphi$, d'un réseau fermé à deux files F et $\varphi$ et L clients, les seules différences entre les deux réseaux étant les valeurs de $\mu(N)$, taux de service à $\varphi$.

$$T = \frac{1}{\lambda} \sum_{M=0}^{k} M P_{M} \text{ (formule de Little) où } P_{M} \text{ est la probabilité que la file soit de longueur } M, \text{ i.e. } P_{M} = P_{0} \prod_{n=0}^{M-1} \frac{\mu(n)}{\lambda} \text{ et } P_{0} = \left[ \sum_{M \le L} \prod_{n=0}^{M-1} \frac{\mu(n)}{\lambda} \right]^{-1}$$

Ces valeurs données aux différents paramètres (figure 4) sont issues des résultats de mesures [SFER 76] et [Leroudier 77].

Les courbes de temps de réponse (figure 4) ont été établies en fonction du paramètre k de Belady donc de la localité des processus traités, pour l'A.D. et en fonction de l'espace moyen nécessaire par processus
(≈ 10(α+1) Kmots) pour l'A.S. Elles ont été étudiées en détail dans [Jomier 78] et permettent de déterminer quel type d'allocation est préférable en fonction des caractéristiques des processus.

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

## 5. - ETUDE DU CONTROLE PAR INJECTION ALEATOIRE DES PROGRAMMES

Nous avons vu dans le paragraphe 3. l'importance du contrôle des systèmes multiprogrammés à mémoire virtuelle. La méthode que nous avons proposée et étudiée en détail [Gelenbe 78, Kurinckx 78] peut être décrite à partir du réseau de files d'attente représenté à la figure 5 sur laquelle

<figure><img src="image_9.png" /><figcaption>Figure 5</figcaption></figure>

on reconnait le modèle à serveur central décrit-ci-dessus. Cependant, dans ce problème, le degré de multiprogrammation n'est pas fixé ; les processus sont issus de L consoles et admis directement dans la file de l'unité centrale ; lorsque l'exécution est terminée, le processus rejoint sa console.

La méthode de contrôle proprement dite est la suivante : quand un processus a obtenu X unité de temps d'exécution, il est placé dans l'ensemble des processus empêchés et perd le droit à posséder un espace en mémoire principale. A l'issue d'un temps de résidence dans cet ensemble le processus est réinjecté dans l'ensemble multiprogrammé.

Les hypothèses et les définitions posées dans la description du modèle à serveur central restent valables. Nous supposerons en outre que :
- le temps passé par un processus a sa console est distribué suivant une loi exponentielle de paramètre λ,

- les intervalles X entre deux départs consécutifs d'un processus vers l'ensemble des empêchés sont des variables aléatoires exponen-
tielles de moyenne q,

- le temps de résidence dans l'ensemble des empêchés est distribué suivant une loi exponentielle de paramètre $\tilde{\alpha}(N,t)$, défini par la relation :

$$ \tilde{\alpha}(N,t) = \begin{cases} B & \text{si } N = 0 \\ h \tilde{\beta}(N,t) & \text{si } N \ge 1 \end{cases} $$

dans laquelle h et B sont des constantes et $\tilde{\beta}(N,t)\Delta t$ la probabi-
lité que dans l'intervalle $[t,t+\Delta t]$ un processus quitte l'unité
centrale pour entrer dans l'ensemble des empêchés ou pour regagner
sa console.

Avec ces hypothèses et en adaptant $s_i = e(N)$, on obtient aisément
le taux de service de l'unité centrale $\mu_o(N) = (c^{-1} + q^{-1} + e^{-1}(N) + \sum_{i=2}^{N} s_i^{-1})$

Il faut maintenant entreprendre la résolution des équations du réseau
de files d'attente obtenu [Kurinckx 78] afin de démontrer que le contrôle
proposé est capable, par un choix judicieux de ses paramètres, d'éviter
l'écroulement du système et de calculer les performances (débit, temps moyen
de réponse) auxquelles il conduit.

En raison de la dépendance des taux de service à l'état du réseau,
la théorie disponible ne peut fournir de solution analytique même si on ne
s'intéresse qu'à l'état d'équilibre statistique du modèle. Le système auquel
nous sommes confrontés paraît cependant à première vue, assez bien répondre
aux critères de décomposition. On peut en effet y distinguer trois parties :

- la boucle de ressources dans laquelle les événements sont séparés par des intervalles de l'ordre de 10 ms (temps de service moyen de la mémoire secondaire),

- l'ensemble des empêchés pour lequel l'expérience suggère des temps de résidence proches de la seconde,

- les consoles qui travaillent à l'échelle du temps des réactions humaines (environ 10 secondes).
Nous allons donc travailler en trois étapes, d'abord remplacer la boucle de ressources par un serveur équivalent (macrovariable de deuxième niveau) (figure 3), ensuite substituer à ce serveur et à l'ensemble des empêchés un second serveur équivalent (macrovariable de premier niveau) et enfin, résoudre ce réseau pour obtenir des valeurs approchées des performances du système.

Le taux de service moyen $\hat{\beta}(N,t)$ du serveur équivalent à la boucle de ressources s'obtient en exprimant que $\hat{\beta}(N,t)\Delta t$ est la probabilité qu'un processus quitte la boucle de ressources pour entrer dans l'ensemble des empêchés ou pour regagner sa console dans l'intervalle $(t, t+\Delta t)$ :

$$ \hat{\beta}(N,t) = (x_{n+1} + x_{n+2}) \mu_o(N) A(N,t) $$

dans laquelle $A(N,t)$ est la probabilité que l'unité centrale soit active à l'instant $t$ lorsqu'il y a $N$ processus dans la boucle de ressources.

L'approximation de décomposition consiste à remplacer dans cette expression $A(N,t)$ par $A_o(N)$, probabilité à l'état stationnaire que l'unité centrale soit active dans le réseau fermé à $N$ clients de la figure 1. En tenant compte des valeurs de $x_{n+1}$ et $x_{n+2}$, on obtient le taux de service moyen :

$$ \beta(N) = (c^{-1} + q^{-1}) A_o(N) $$

Par une technique analogue, nous calculons $\hat{\gamma}(M,t)$, le taux de service moyen du serveur équivalent à la boucle de ressources et à l'ensemble des empêchés :

$$ \hat{\gamma}(M,t) = \sum_{N=1}^{M} \frac{x_{n+2}}{x_{n+1} + x_{n+2}} \beta(N) \hat{p}(N/M,t) $$

dans laquelle $\hat{p}(N/M,t)$ est la probabilité qu'il y ait à l'instant $t$ $N$ processus dans la boucle de ressources sachant qu'il y en a $M$ dans la boucle de ressources et dans l'état empêché. Par un argument de décomposition, nous remplaçons $\hat{p}(N/M,t)$ par $p(N/M)$, probabilité dont la signification est identique mais évaluée à l'état stationnaire dans le réseau fermé à $M$ processus et 2 files (boucle de ressources et état empêché). La forme définitive de l'expression de $\gamma(M)$ est alors obtenue en remplaçant les quantités par leur valeur et en prenant la limite pour $B \to \infty$ (afin d'éviter que le contrôle dégrade le taux d'activité de l'unité centrale).

La figure 6 présente des valeurs numériques de $\gamma(M)$ pour différentes valeurs de la constante $h$ et de la localité ($k$). Nous constatons que pour des valeurs bien choisies de $h$, $\gamma(M)$ ne décroît pas sensiblement lorsque $M$ croît,
ce qui montre bien que le contrôle par injection aléatoire est capable d'em-
pêcher que l'écroulement des performances se manifseste.

La figure 7 compare les temps de réponse obtenus avec le contrôle
proposé avec d'une part les temps moyens de réponse du système non contrôlé
et d'autre part les temps de réponse fournis par le contrôle "optimal" : cas
idéal où on limite le degré de multiprogrammation à sa valeur optimale.

Bien que les conditions suffisantes de décomposabilité [Courtois 77]
ne soient pas toujours satisfaites, nous avons montré en comparant à des
résultats de simulation [Kurinckx 78] que l'erreur commise était toujours
faible (maximum 10 % pour les valeurs numériques utilisées).

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

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

6. - CONCLUSION

Les deux exemples que nous venons de décrire montrent l'intérêt de
la méthode de décomposition lorsque la solution analytique d'un réseau est
inconnue et que la taille de l'espace d'état interdit l'emploi des méthodes
numériques. Devant un problème nouveau, la difficulté est de connaître a priori
la qualité de l'approximation. Bien qu'il existe des conditions suffisantes de
décomposition, c'est souvent l'expérience ou la physique du problème qui met-
tent en évidence l'intérêt de la méthode.
BIBLIOGRAPHIE

Belady L., Kuehner C.J., Dynamic space sharing in computer systems, CACM 12, 5, 282-288 (1969).

Brandwajn A., A model of a time-sharing virtual memory system solved using equivalence and decomposition method, Acta Informatica 4, 11-47 (1974).

Courtois P.J, Décomposability - Queueing and computer system applications, ACM Monograph series, Academic Press, New York (1977).

Dennig P.J., Trashing: its causis and prevention, Proc.AFIPS 68, Fall Joint Computer Conference, 33, 915-922 (1968).

Gelenbe E., Kurinckx A., Random injection control of multiprogramming in virtual memory, IEEE Trans. on Soft. Engin. 4, 1, 2-17 (1978).

Jomier G., Comparison of static and dynamic memory allocation in paged system, Rapport CRIN.78 P017, Laboratoire d'informatique, Université de Nancy I (1978).

Kurinckx A. Contrôle de la multiprogrammation des systèmes à mémoire virtuelle, thèse de 3ème cycle, 2406, Université de Paris Sud - Orsay (1978).

Leroudier J., Systèmes adaptatifs à mémoire virtuelle, thèse d'Etat, Université de Grenoble (1977).

Simon H.A., Ando A., Aggregation of variables in dynamic systems, Econometrica 20, 2 (1961).