Modélisation des réseaux

Devan SOHIER
Files M/M : rappels de cours et TD

1 Rappels de cours
Une file d’attente est un objet composé de deux parties, une file à proprement parler dans laquelle sont stockées
les requêtes en attente de traitement, et un serveur qui les traite. On note λ le nombre moyen de requêtes qui
parviennent au système chaque unité de temps, et µ le nombre de requêtes que le serveur traite chaque seconde
en moyenne. La notation de Kendall X /Y /n/α/ β permet de décrire le mode de fonctionnement de cette file. X
décrit la manière dont les requêtes parviennent au système : M indique des temps d’inter-arrivée exponentiel de
moyenne λ, D déterministes (une requête arrive exactement toutes les λ1 secondes), G I des temps d’inter-arrivée
suivant une loi quelconque, les temps d’inter-arrivée successifs étant indépendants les uns des autres, G des temps
d’inter-arrivée totalement quelconques. Y décrit le temps de traitement des requêtes, avec les mêmes symboles (en
remplaçant, bien sûr, λ par µ). n est le nombre de serveurs travaillant en parallèle. α désigne la capacité de la file,
nombre maximal de requêtes présentes dans la file : toute nouvelle requête arrivant alors qu’α requêtes sont déjà
présentes est rejetée ; quand elle n’est pas mentionnée, on la suppose infinie. β représente la discipline de la file,
c’est-à-dire la manière dont le serveur choisit la prochaine requête à traiter : quand elle n’est pas précisée, la file est
FIFO.

λ µ

File Serveur

Figure 1 – Composition d’une file d’attente avec un serveur

Une file M /M est une file dans laquelle les temps d’inter-arrivée et les temps de traitement suivent une loi
exponentielle. Cela a une conséquence fondamentale : le système est sans mémoire (markovien, dans les termes
des probabilités, d’où le « M ») : la manière dont on est parvenu à un certain état n’a pas d’influence sur la manière
dont il évoluera. Si, par exemple, on prend une file D/D/1 de paramètre λ = 31 et µ = 12 , l’unité de temps étant la
seconde, et que l’on sait que deux requêtes sont en attente, et une en traitement, on ne peut prédire correctement
l’évolution du système avec ces seuls renseignements : si la dernière requête est arrivée il y a une seconde, la
prochaine arrivera dans deux secondes ; si elle est arrivée il y a deux secondes, la suivante parviendra dans une
seconde ; de même si on vient juste de débuter le traitement de la requête en cours de traitement il faudra attendre
deux secondes, alors que si elle est en traitement depuis une seconde, il n’en reste qu’une à attendre avant de traiter
la suivante. En passant à des files probabilistes, qui représentent beaucoup mieux les phénomènes que l’on souhaite
mettre en évidence (notamment la fluctuation du nombre de requêtes dans la file), on complique nécessairement le
modèle : pour parvenir quand même à le traiter, on est obligé de faire des hypothèses simplificatrices, en particulier
celle-ci (c’est une hypothèse reflétant fidèlement ce qui se passe pour les temps d’inter-arrivée pour la plupart des
phénomènes qui nous intéressent ; elle est moins conforme à la réalité pour ce qui concerne les temps de calcul,
mais l’expérience prouve que ses prédictions sont assez fidèles à la réalité).
L’évolution d’une file M /M est intégralement prévisible à partir de son état actuel, c’est-à-dire, pour une file
d’attente, par les requêtes présentes dans la file et en cours de traitement. Le cas le plus simple est celui d’une
file M /M /1, dans lequel les requêtes arrivent indépendamment les unes des autres, et sont stockées dans une file
d’attente de capacité supposée infinie.
Si à partir d’un certain nombre de requêtes, le système est en mesure d’en traiter plus par unité de temps qu’il
n’en reçoit, alors le système est stable (le nombre de requêtes fluctue, et n’explose pas) et il admet une distribution
stationnaire : si l’on le laisse évoluer suffisamment longtemps, le nombre de requêtes qu’il contiendra ne dépend
plus du nombre actuel de requêtes.

1
 La première étape consiste en une modélisation de ce système et de sa dynamique sous forme d’un graphe
orienté : on représente chaque état du système par un sommet de ce graphe, un arc d’un état A à un état B indiquant
la possibilité de passer directement de l’état A à l’état B. Sur chaque arc, on va porter l’intensité avec laquelle on
passe de l’état de départ à l’état d’arrivée : cette intensité le nombre moyen de fois chaque seconde que se produit
le phénomène faisant passer d’un état à l’autre. Pour une file M /M /1, les deux seuls événements faisant évoluer
l’état du système sont l’arrivée d’une nouvelle requête, événement qui fait augmenter d’un le nombre de requêtes
présentes, et qui se produit λ fois par seconde en moyenne, et la fin du traitement de la requête en cours, qui
diminue d’un le nombre de requêtes présentes et se produit µ fois par seconde en moyenne.

λ λ λ λ λ λ λ λ
0 1 2 3 ... n−1 n n+1 ...
µ µ µ µ µ µ µ µ

Figure 2 – Graphe d’état d’une file M /M /1 de paramètres λ et µ

De ce graphe, on peut tirer un système d’équation permettant de déterminer les probabilités stationnaires que
la file soit dans chacun de ces états. Un arc sortant d’un nœud exprime l’intensité avec laquelle on sort de cet état
quand on y est : elle tend donc à diminuer la probabilité d’être dans cet état ; un arc entrant tend à augmenter cette
probabilité. Comme la probabilité est stationnaire, ces tendances à diminuer et augmenter la probabilité doivent se
compenser. On s’échappe d’un nœud selon un certain arc avec une fréquence qui est le produit d’être dans cet état
(sinon, on ne peut bien sûr pas en sortir) et de l’intensité avec laquelle on sort de cet état selon cet arc : pour chaque
nœud, la somme des produits des intensités des arcs sortants par la probabilité d’être dans cet état est égale à la
somme des produits des arcs entrants par la probabilité d’être dans les états dont ils proviennent.
Notons πk la probabilité d’être dans un état k. Si l’on note i 1, i 2, . . . , i m les destinations des arcs sortant de k, α1 ,
α2 , . . . , α m les poids des arcs correspondants, et j1, j2, . . . , jn les origines des arcs entrants, β 1 , β 2 , . . . , β n les poids
des arcs correspondants, on a :
m n
πk × α l = πi l × β l
X X
l =1 l =1

Par exemple, dans une file M /M /1 de paramètres λ = 12 et µ = 16 à l’état stationnaire, nous montrerons un peu
plus bas que la probabilité d’être dans l’état 1 (c’est-à-dire qu’une seule requête soit présente dans le système) est
π1 = 16 , la probabilité d’être dans l’état 3 est π3 = 256 . Si l’unité est la seconde, sur une heure (c’est-à-dire 3 600 s),
3 27

le système passe 11 minutes et 15 secondes (675 s) dans l’état 2, et un peu moins de 6 minutes et 20 secondes
(379,875 s) dans l’état 4. λ = 12 signifie qu’en moyenne, douze fois par seconde, une nouvelle requête arrive. Donc,
en un heure, pendant les 675 s que le système passera en moyenne avec une requête, ce sont 12 × 675 = 8 100 fois
que le système passera de l’état 1 à l’état 2. De même, il passera en moyenne 16 × 379, 875 = 6 075 fois de l’état 3 à
l’état 2. Il faut bien évidemment sortir de l’état 2 autant de fois qu’on y entre (on ne peut en sortir qu’à condition
d’y être préalablement entré, et réciproquement i ), c’est-à-dire λ × π1 × 3 600 + µ × π3 × 3 600 = 8 100 + 6 075 = 14 175
fois. Et puisque le système, quand il est dans l’état 2, en sort en moyenne λ + µ = 28 fois par seconde, il devra 28
14 175

seconde, (soit 506,25 secondes, soit un peu moins de 8 minutes et demie) : il devra y passer une proportion π2 du
temps telle que le nombre moyen de fois qu’il sort de l’état 2, (λ + µ) × π2 , soit égal au nombre de fois qu’il y entre
λ × π1 + µ × π2 . Dans cet exemple, on obtient π2 = 3600 = 64
506,25 27

i. A une entrée ou une sortir prêt, suivant l’état dans lequel on commence ou on finit l’heure, mais puisqu’on commence et finit dans un
état avec une probabilité qui est justement la probabilité stationnaire, cela n’influence pas les résultats du calcul.

2
 C

D
ν
ξ λ B
σ
E µ
A
ρ
τ

Figure 3 – (λ + ν + ξ + ρ)π A = µπB + σπ E + τπ F

On a de plus que, s’agissant de probabilités d’événements incompatibles et qui couvrent tous les états possibles
du système étudié, πi = 1. L’ensemble de toutes ces équations fournit un système, que l’on peut résoudre, et qui
P
donne les valeurs de la distribution stationnaire.
Pour une file M/M/1, les équations sont les suivantes.

λπ0 = µπ1 (0)

(λ + µ)π1 = λπ0 + µπ2 (1)
(λ + µ)π2 = λπ1 + µπ3 (2)
..
.
(λ + µ)πn = λπn−1 + µπn−2 (n)
..
.

De l’équation 0, on tire π1 en fonction de π0 .

λ
π1 = π0
µ
L’équation 1, à partir de là, permet de calculer π2 en fonction de π0 .

(λ + µ)π1 = λπ0 + µπ2

⇔ µπ2 = (λ + µ)π1 − λπ0
λ
⇔ µπ2 = (λ + µ) π0 − λπ0 D’après la formule trouvée plus haut.
µ
λ
 2 
⇔ µπ2 = + λ − λ π0
µ
λ
 2
⇔ µπ2 = π0
µ
λ λ
 2  2
⇔ π2 = π0 = π0
µ 2 µ

3
 L’équation 2 donne alors π3 .

(λ + µ)π2 = λπ1 + µπ3

⇔ µπ3 = (λ + µ)π2 − λπ1
λ λ
 2  
⇔ µπ3 = (λ + µ) π0 − λ π0 D’après les formules trouvées plus haut.
µ µ
λ λ2 λ2
 3 
⇔ µπ3 = + − π0
µ2 µ µ
λ
 3
⇔ µπ3 = π0
µ2
λ λ
 3  3
⇔ π3 = π = π0
µ3 µ
0

 n
On peut conjecturer que ∀n, πn = λµ π0 . Procédons par récurrence. Notons, pour tout entier n, (Hn ) l’hypothèse
 k
de récurrence « ∀k ≤ n, πk = λµ π0 ».
 0  0
Nous avons déjà démontré (H1 ) (pour k = 0, λµ = 1, donc π0 = λµ π0 ). Soit n ≥ 1. Supposons (Hn−1 ), et
démontrons (Hn ).
D’après l’équation (n − 1), on a

(λ + µ)πn−1 = λπn−2 + µπn

⇔ µπn = (λ + µ)πn−1 − λπn−2
  n−1   n−2
λ λ
⇔ µπn = (λ + µ) π0 − λ π0 D’après l’hypothèse de récurrence.
µ µ
λ λ n−1 λ n−1
 n 
⇔ µπn = + − π0
µ n−1 µ n−2 µ n−2
λ
 n 
⇔ µπn = π0
µ n−1
 n
λ λ
 n
⇔ πn = π = π0
µ µ
n 0

 n
Ainsi, (Hn ) est vraie. Par le principe de récurrence, pour tout n de N, (Hn ) est vraie : ∀n, πn = λµ .
Reste à calculer π0 . Pour ce faire, on utilise le fait que (πn )n ∈N est une distribution de probabilité : le système est
nécessairement être dans un état, et ne peut pas être dans deux états différents à la fois. Donc, n ∈N πn = 1.
P

πn = 1
X
n ∈N
n
X λ

⇔ π0 = 1
n ∈N µ
  !
X λ n
⇔ π0 = 1
n ∈N µ
1
⇔ π0 = 1
1 − λµ
λ
⇔ π0 = 1 −
µ
Ainsi, pour tout entier n   n
λ λ

πn = 1 − π0
µ µ
Connaissant cette probabilité, on peut maintenant calculer le nombre moyen de requêtes présentes dans la file.
Par définition, une moyenne est a somme des valeurs que peut prendre la variable aléatoire multipliées par la
probabilité qu’elle les prenne (ou de façon équivalente, des probabilité d’être dans chaque état multipliées par la

4
valeur de la variable dans cet état). La probabilité qu’il y ait n requêtes dans le système est πn , donc le nombre
moyen de requêtes dans le système est
+∞
N =
X
nπn
n=0

On obtient le nombre moyen de requêtes en attente, en considérant que, à partir du moment où l’on a au moins
une requête, une requête est en traitement et les autres en attente. Donc dans tout état n ≥ 1 (mais pas dans l’état
0), on a n − 1 requêtes en attente. Donc
+∞ +∞
N f = 0π0 + (n − 1)πn =
X X
(n − 1)πn
n=1 n=1

Pour le temps moyen de traitement, si une requête arrive alors que n requêtes sont déjà présentes, elle devra
attendre, pour finir d’être traitée, le temps moyens pour que n + 1 requêtes soient traitées (les n qui la précède, et
elle même), soit nµ . Ainsi
+∞ +∞ +∞
(n + 1) 1X 1X N +1
T = πn = nπn + πn =
X
n=0 µ µ n=0 µ n=0 µ
Le temps d’attente, lui, vérifie :
+∞
n N
= πn =
X
T f
n=0 µ µ
Pour une file M /M /1, on a donc :
+∞
N =
X
nπn
n=0
 +∞   n
λ X λ

= 1− n
µ n=0 µ
λ λ/µ
 
= 1−
µ (1 − λ/µ)2
λ/µ
=
1 − λ/µ
λ
=
µ−λ

+∞
N f = 0π0 +
X
(n − 1)πn
n=1
+∞
=
X
(n − 1)πn
n=1
+∞ +∞
= πn
X X
nπn −
n=1 n=1
 +∞   +∞ 
= π n − π0
X X
nπn − 0π0 −
n=0 n=0

= N − (1 − π0 )
λ λ
  
= − 1− 1−
µ−λ µ
λ λ
= −
µ−λ µ
λ2
=
µ(µ − λ)

5
 N +1
T =
µ
λ
µ−λ + 1
=
µ
µ
µ−λ
=
µ
1
=
µ−λ

N
T f =
µ
λ
=
µ(µ − λ)
On retrouve plus simplement ces deux derniers résultats en utilisant la loi de Little : dans tout système d’attente,
T = Nλ . Ce résultat est valable pour toute file d’attente, M /M ou pas, pour des réseaux de files d’attente, pour la
file à proprement parler. . .

2 Quelques exemples
2.1 File M /M /2
Considérons une file M /M /2. Il s’agit d’une file M /M : les temps d’inter-arrivée suivent comme les temps de
traitement une loi exponentielle. Deux serveurs travaillent en parallèle.
Puisqu’il s’agit d’une file M /M , l’état du système est intégralement décrit par le nombre de requêtes qui y sont
présentes. Le système a un nombre fini d’états, et converge donc. Les requêtes parviennent au système au rythme
de λ = 3 requêtes par seconde, et chacun des deux serveurs à la capacité de traiter µ = 2 requêtes par seconde.
Lorsqu’aucune requête n’est présente, aucun des deux serveurs ne travaille. Lorsqu’une requête est présente, un
seul serveur travaille. Lorsque deux requêtes ou plus sont présentes, les deux serveurs travaillent. Ainsi, lorsqu’une
requête est présente, le système la traite au rythme de 3 requête par seconde. Par contre, lorsque deux requêtes ou
plus sont dans le système, ce dernier exploite les deux serveurs en parallèle, et la cadence de traitement est doublée
à 4 requêtes par seconde. Cela amène donc à la modélisation ci-dessous.

3 3 3 3 3 3 3 3
0 1 2 3 ... n−1 n n+1 ...
2 4 4 4 4 4 4 4

Figure 4 – Graphe d’états d’une file M /M /2 de paramètres 3 et 2

Comme λ = 3 < µ = 4, le système a un ensemble fini d’états incluant 0 (0 et 1 en l’occurence) tel que le nombre
de requêtes augmente plus vite qu’il ne diminue.
De ce graphe, on peut tirer les équations suivantes :
3π0 = 2π1 (0)
5π1 = 3π0 + 4π2 (1)
7π2 = 3π1 + 4π3 (2)
7π3 = 3π2 + 4π4 (3)
..
.
7πn = 3πn−1 + 4πn+1 (n)
..
.

6
 De l’équation 0, on tire
3
π1 = π0
2
L’équation 1 donne :

5π1 = 3π0 + 4π2

⇔ 4π2 = 5π1 − 3π0
3
⇔ 4π2 = 5 × π0 − 3π0 D’après la formule trouvée plus haut.
2
9
⇔ 4π2 = π0
2
 2
9 3
⇔ π2 = π0 = 2 π0
8 4

L’équation 2 donne alors π3 .

7π2 = 3π1 + 4π3

⇔ 4π3 = 7π2 − 3π1
9 3
⇔ 4π3 = 7 × π0 − 3 × π0 D’après les formules trouvées plus haut.
8 2
27
⇔ 4π3 = π0
8
 3
27 3
⇔ π3 = π0 = 2 π0
32 4

De l’équation 3, on tire de même que

 4
3
π4 = 2 π0
4
 k
On pose donc pout tout n > 0 l’hypothèse de récurrence (Hn ) : « ∀1 ≤ k ≤ n, πk = 2 π0 » ii . On a déjà
3
4
démontré (H2 ). Soit n de N, supposons (Hn ). Démontrons maintenant (Hn+1 ).
D’après l’équation n :

7πn = 3πn−1 + 4πn+1

⇔ 4πn+1 = 7πn − 3πn−1
 n   n−1
3 3
⇔ 4πn+1 = 7 × 2 π0 − 2 × 3 π0 D’après l’hypothèse de récurrence.
4 4
    n−1
42 3
⇔ 4πn+1 = −6 π0
4 4
 9   3  n−1
⇔ 4πn+1 = π0
2 4
 n+1   n+1 
3 3
⇔ 4πn+1 = 2n−1 π0 = 2 π0
2 4n
  n+1
3
⇔ πn+1 = 2 π0
4
 n
(Hn+1 ) est donc vraie, et par le principe de récurrence, pour tout n > 0, πn = 2 π0 .
3
4
De plus, π étant une distribution de probabilité, +∞ n=0 πn = 1 :
P

ii. Pour k = 0, cette propriété est fausse

7
 +∞
πn = 1
X
n=0
+∞
π0 + πn = 1
X
⇔
n=1
 +∞   n
X 3
⇔ π0 + 2 π0 =1
n=1 4
 +∞   n 
X 3
⇔ π0 + 2π0 =1
n=1 4
  +∞   n   0
X 3 3
⇔ π0 1 + 2 −1 =1 Car = 1.
n=0 4 4
!
2
⇔ 3 − 1 π0 =1
1− 4
⇔ 7π0 = 1
1
⇔ π0 =
7
 n
Ainsi, π0 = et pour tout n > 0, πn =
1 2 3
7 7 4 .
On peut maintenant calculer N et N f .

+∞ +∞
N = nπn = 0π0 +
X X
nπn
n=0 n=1
+∞ +∞  n
2X 3
= nπn =
X
n
n=1 7 n=1 4
2 3/4 24
= =
7 (1 − 3/4)2 7

+∞ +∞ +∞
Nf = (n − 2)πn = πn
X X X
nπn − 2
n=2 n=2 n=2
+∞  +∞ 
= nπn − π1 − 2 π n − π1 − π0
X X
n=0 n=0

= N − π1 − 2 (1 − π1 − π0 ) = N + π1 + 2π0 − 2
24 3 2 27
= + + −2=
7 14 7 14

La loi de Little permet de calculer T et T f .

N N 8
T = = =
λ 3 7

Nf Nf 9
T f = = =
λ 3 14
Le temps T de séjour d’une requête dans le système se décompose en un temps d’attente T f et un temps de
traitement, dont la durée moyenne est 1µ . On doit donc avoir T = T f + 1µ . C’est bien le cas ici.
Les serveurs sont tous les deux occupés lorsque l’état est ≥ 2. Lorsque l’état est 1, un seul des deux serveurs est

8
occupé, et donc la charge du système est 21 . Donc la charge moyenne du système est :
+∞ +∞
1 1
0π0 + π1 + 1πn = π n − π1 − π0
X X
2 n=2 n=0 2
1
= 1 − π1 − π0
2
1 3 1
=1− . −
2 14 7
21
=
28

2.2 File M /M /1/3

Considérons une file M /M /1/3 de paramètres λ = 3 et µ = 2. Il s’agit d’une file M /M : les temps d’inter-
arrivée suivent comme les temps de traitement une loi exponentielle. Deux serveurs travaillent en parallèle. Quatre
requêtes au maximum peuvent être présentes dans le système : toute requête supplémentaire est rejetée.
Puisqu’il s’agit d’une file M /M , l’état du système est intégralement décrit par le nombre de requêtes qui y sont
présentes. Le système a un nombre fini d’états, et converge donc quelles que soient les valeurs de µ et λ.
Puisque le système contient au maximum trois requêtes, son graphe d’états a quatre nœuds.

3 3 3
0 1 2 3
2 2 2

Figure 5 – Graphe d’états d’une file M /M /2/4 de paramètres 3 et 2

De ce graphe, on peut tirer les équations suivantes :

3π0 = 2π1 (0)

5π1 = 3π0 + 2π2 (1)
5π2 = 3π1 + 2π3 (2)
2π3 = 3π2 (3)

Ce système d’équations, contrairement à celui d’une file M /M /1, est fini, grâce au fait que la capacité de la file
est finie. De l’équation 0, on tire
3
π1 = π0
2
L’équation 1 donne :

5π1 = 3π0 + 2π2

⇔ 2π2 = 5π1 − 3π0
15
⇔ 2π2 = π0 − 3π0 D’après la formule trouvée plus haut.
2
9
⇔ 2π2 = π0
2
9
⇔ π2 = π0
4
L’équation 2 donne alors π3 .

5π2 = 3π1 + 2π3

⇔ 2π3 = 5π2 − 3π1
9 3
⇔ 2π3 = 5 × π0 − 3 × π0 D’après les formules trouvées plus haut.
4 2
27
⇔ 2π3 = π0
4
27
⇔ π3 = π0
8

9
 Enfin, l’équation 3 donne π3 = 2 π0 , ce qui confirme les deux résultats précédents.
3

On sait de plus que πn = 1, et donc π0 + π1 + π2 + π3 = 1. En utilisant les formules trouvées ci-dessus, il vient :
P

1 = π0 + 2 π0 + 4 π0 + 8 π0 = 8 π0 , et donc
3 9 27 65

8 12
π0 = π1 =
65 65
18 27
π2 = π3 =
65 65
Le nombre moyen de requêtes présentes dans le système est : N = 0π0 + 1π1 + 2π2 + 3π3 = 1265 + 2 × 65 + 3 × 65 = 65 ,
18 27 129

soit un peu moins de 2. Le serveur est occupé une proportion 1 − π0 = 65 du temps. Une requête est rejetée si elle
57

arrive alors que les trois créneaux disponibles sont occupées, donc avec un probabilité π3 : en moyenne, 27 requêtes
sur 65 sont rejetées.

2.3 Files à priorité

On considère ici un système à priorité. Des requêtes non-prioritaires arrivent selon un processus de Poisson
d’intensité λ 1 ; d’autres requêtes, prioritaires, arrivent avec une intensité λ 2 . Le temps de traitement des requêtes
est géométrique de paramètre µ, indépendamment de leur statut. Lorsque le serveur termine une tâche, il choisit
une nouvelle tâche prioritaire dans la file. S’il n’y en a aucune, il sélectionne une tâche non-prioritaire. Si, alors
qu’il est en train de traiter une tâche non-prioritaire, une tâche prioritaire arrive, le serveur suspend son traitement,
passe à la tâche prioritaire, et reprendra le traitement interrompu une fois qu’il n’aura plus de tâche prioritaire à
traiter.
L’état d’un tel système ne peut pas être décrit seulement par le nombre de requêtes qui y sont présentes (du
moins si l’on souhaite étudier les différences entre le traitement des deux types de requêtes). Il est nécessaire de
connaître le nombre de requêtes de chaque type. On décrira donc l’état du système par un couple (n 1, n 2 ), avec
n 1 le nombre des requêtes non-prioritaires, et λ 2 celui des requêtes prioritaires. Si des requêtes prioritaires sont
présentes, c’est l’une d’entre elles qui est en cours de traitement, et le nombre de requêtes non-prioritaires ne peut
pas décroître.
Le graphe d’états de ce système est donc le suivant.

.. .. ..
. . .

λ2 µ λ2 µ λ2 µ
λ1 λ1 λ1
(0, 2) (1, 2) (2, 2) ...

λ2 µ λ2 µ λ2 µ
λ1 λ1 λ1
(0, 1) (1, 1) (2, 1) ...

λ2 µ λ2 µ λ2 µ
λ1 λ1 λ1
(0, 0) (1, 0) (2, 0) ...
µ µ µ

Figure 6 – Graphe d’états d’une file M /M /1 avec deux niveaux de priorité — l’arrivée d’une requête prioritaire
interrompt le traitement d’une requête moins prioritaire

De ce graphe, on tire les équations suivantes :

(λ 1 + λ 2 )π00 = µπ01 + µπ10
∀n > 0, (λ 1 + λ 2 + µ)π0n = µπ0n+1 + λ 2 π0n−1
∀m > 0, (λ 1 + λ 2 + µ)πm0 = µπm+10 + µπm1 + λ 1 πm−10
∀n > 0, m > 0, (λ 1 + λ 2 + µ)πmn = µπmn+1 + λ 1 πm−1n + λ 2 πmn−1

10
2.4 Le cours de tennis
On considère un système composé d’un cours de tennis, où se présentent des joueurs selon un processus de
Poisson d’intensité λ. Lorsque deux joueurs sont présents, ils font une partie, de durée exponentielle de paramètre
µ et quittent le cours en même temps une fois la partie terminée.
Le cours n’est occupé que si le nombre de joueurs n est plus grand que ou égal à deux. Donc, si 0 ou 1 joueur est
présent, ce nombre ne peut qu’augmenter avec l’arrivée d’un nouveau joueur, ce qui se produit avec une intensité
λ. Lorsque plus de deux joueurs sont présents, une partie est en cours, et deux événements peuvent se produire :
soit un nouveau joueur arrive (intensité λ) et le nombre de joueurs augmente d’un, soit la partie se termine, et le
nombre de joueurs diminue de deux. Le graphe d’états de ce système est donc celui représenté à la figure 7

λ λ λ λ λ
0 1 2 3 4 ...

µ µ µ µ µ

Figure 7 – Graphe d’états

3 Exercices
Etudier une file signifie déterminer son graphe d’états, sa distribution stationnaire, le nombre moyen de requêtes
présentes, le nombre moyen de requêtes en attente, le temps moyen total passé dans le système, le temps moyen
d’attente, le taux d’occupation du ou des serveurs, ainsi que, le cas échéant, le taux de rejet.

Exercice 1 : Standard téléphonique

Deux lignes téléphoniques sont mises à la disposition des clients qui passent des commandes. Lorsque les deux
lignes sont occupées les appels restent en file et dès qu’une ligne est libérée le premier entre en contact. On suppose
que des appels arrivent suivant le processus de Poisson de taux de 30 à l’heure et l’on retient l’hypothèse que la
durée de la commande est une variable aléatoire exponentielle de durée moyenne 3 mn.
Dessiner le diagramme de transition. Le système est-il ergodique (stable) ? Si oui trouver la distribution station-
naire.
Trouver le nombre moyen d’appels branchés, le nombre moyen d’appels en attente, la durée moyenne de temps
passé par usager et la durée d’attente pour avoir une conversation en régime stationnaire
Quelle est la portion de temps où les deux lignes sont occupées ?

Exercice 2 : File M /M /2/4

Etudiez une file M /M /2/4 de paramètres λ = 1 et µ = 1.

Exercice 3 : Blanchisserie
Une blanchisserie possède 3 machines identiques et indépendantes. Chaque machine a une durée de fonction-
nement indépendante du passé, suivant une loi exponentielle d’espérance de deux jours. Une machine qui tombe
en panne est réparée par un technicien ; la durée de réparation est une variable aléatoire d’espérance un jour. La
blanchisserie n’a qu’un technicien.
Dessiner le graphe d’états de ce système.
Quelle est la fraction de temps où toutes les machines fonctionnent et celle où toutes les machines sont hors
service ?
Quel est le nombre moyen de machines en état de marche ? Quel est le nombre moyen de machines immobilisées ?

Exercice 4 : Au choix
On cherche à mettre en place un système pour traiter λ = 10 requêtes par seconde. On nous propose, pour des
tarifs équivalents, trois systèmes différents :
— une file M/M/1 avec un serveur capable de traiter 2µ = 16 requêtes par seconde ;
— une file M/M/2 avec deux serveur capables de traiter chacun µ = 8 requêtes par seconde ;

11
 — deux file M/M/1 avec chacune un serveur capable de traiter µ = 8 requêtes par seconde, avec un mécanisme
routant une requête sur deux vers chacun des serveurs.
L’objectif est de minimiser le temps de réponse.

A File M/M/1 On considère une file M/M/1 avec des arrivées suivant un processus de Poisson d’intensité λ et
un temps de service exponentiel de paramètre µ.
1. A quelle condition le système est-il stable ? Représentez le graphe de transition entre les différents états
(nombres de requêtes présentes dans le système).
2. Calculez la probabilité que k requêtes soient présentes dans le système en régime stationnaire en fonction
de λ et µ. Vous commencerez par exprimer la probabilité πk que k requêtes soient présentes dans le système
en fonction de π0 , puis calculerez π0 , et obtiendrez ainsi une expression de πk , k ≥ 0.
3. Calculez le nombre moyen N de requêtes présentes dans le système, et le temps moyen T de traitement
d’une requête.

B File M/M/2 On considère une file M/M/2 avec des arrivées suivant un processus de Poisson d’intensité λ et
un temps de service exponentiel de paramètre µ pour chacun des deux serveurs.
1. A quelle condition le système est-il stable ? Représentez le graphe de transition entre les différents états
(nombres de requêtes présentes dans le système).
2. Calculez la probabilité que k requêtes soient présentes dans le système en régime stationnaire en fonction
de λ et µ. Vous commencerez par exprimer la probabilité πk que k requêtes soient présentes dans le système
en fonction de π0 , puis calculerez π0 , et obtiendrez ainsi une expression de πk , k ≥ 0.
3. Calculez le nombre moyen N de requêtes présentes dans le système, et le temps moyen T de traitement
d’une requête.

C Comparaison des trois systèmes

1. Calculez le temps moyen de traitement d’une requête avec les deux premiers systèmes.
2. Justifiez que le temps moyen de traitement d’une requête avec le deuxième système correspond au temps de
traitement d’une file M/M/1 de paramètres λ/2 et µ. Calculez le temps moyen de traitement d’une requête
avec le premier système.
3. Concluez.
On suppose λ < 2µ. Calculer le temps moyen passé dans le système. Lequel des 3 systèmes est le plus
performant ?

Exercice 5 : File à priorité M /M /1/3

On considère une file à priorité de capacité 3. Les requêtes non-prioritaires arrivent au rythme de λ 1 requête
par seconde, et les requêtes prioritaires au rythme de λ 2 requêtes par seconde. Les requêtes sont toutes traitées au
rythme de µ requêtes par seconde. Modélisez ce système dans le cas où toute requête est rejetée si trois requêtes
sont déjà présentes. Modélisez le dans le cas où l’arrivée d’une requête prioritaire alors que trois requêtes sont
présentes évince une requête non-prioritaire s’il y en a une. Dans les deux cas on supposera que le traitement
d’une requête non-prioritaire est interrompu en cas d’arrivée d’une requête prioritaire. Vous donnerez les nombres
moyens de requêtes de chaque type, et les temps moyens pour chaque type.

Exercice 6 : File M/M/2 avec deux serveurs différents

On considère une file d’attente avec deux serveurs. Les arrivées sont poissoniennes d’intensité λ. Le serveur
s présente un taux de service µ, et le serveur s 0 un taux de service µ 0, avec µ > µ 0. Quand une requête arrive,
elle est dirigée prioritairement sur le serveur le plus rapide, s, si ce dernier est inoccupé. Une fois qu’un serveur a
commencé à traiter une requête, il ne s’interrompt pas et la traite jusqu’au bout.
S’il y a plus de deux requêtes, les deux serveurs sont donc occupés. S’il n’y en a qu’une, deux états différents
existe : l’un (appelons l’état 1), qui correspond au cas où le serveur s est en train de traiter cette requête ; et l’autre
(appelons 1’), correspondant au cas où c’est le serveur s 0 qui est en train de travailler. On ne peut donc atteindre
la situation 10 que si les deux serveurs sont en train de travailler, que la file est vide, et que le serveur s finit son
traitement avant s 0.

12
 1. Donner le graphe d’états de ce système.
2. Donner les équations vérifiées par les probabilités des nombres de requêtes présentes dans le système en
régime stationnaire, puis les résoudre. Finir l’étude du système.
3. Que se passerait-il si le traitement par le serveur s 0 était interrompu quand le serveur s devient inactif, pour
être instantanément transféré au serveur s ? Donner le graphe et les équations.

Exercice 7 : Au restaurant. . .
On considère un restaurant iii , dans lequel les clients sont servis d’autant plus vite qu’ils sont nombreux. On
considèrera une table, à laquelle un client est servi en un temps inversement proportionnel au nombre de clients
qui attendent une place : si dix clients attendent, son repas sera expédié en cinq fois moins de temps que s’il n’y en
a que deux. Par contre, si aucun client n’attend une place, le rythme du service devient nul.
Les clients arrivent avec un temps exponentiel de paramètre un client par heure, et sont donc servis avec un
temps exponentiel de paramètre n clients par heure, avec n le nombre de clients en attente. Modélisez et étudiez
ce système.
xn
On rappelle que +∞ n=0 n! = e .
x
P

Exercice 8 : Deux cours de tennis

Etudiez un système composé de deux cours de tennis (cf. ci-dessus) où les joueurs arrivent au rythme d’un
toutes les demi-heures, et ou un match dure en moyenne 90 minutes. On suppose que les temps d’inter-arrivée
comme la durée des matchs suivent des lois exponentielles.
Les exercices 1 et 3 sont tirés de https ://[Link]/ENSEIGNEMENT/formation-a-distance/cibermiage-
processus/c1.7/ch03/seq10/[Link].

iii. Un de ces restaurants qui se soucie plus du client à venir que de celui qui est déjà attablé. . .

13