Modélisez une file d'attente

Le module de paiement de la billetterie traite une commande en 20 ms en moyenne. En régime normal, il en reçoit 10 par seconde ; au pic, 45. À 45 commandes par seconde, il n’est occupé qu’à 90 % : il lui reste de la marge, non ? Pourtant, les clients se plaignent d’attendre.

Les lois opérationnelles ne suffisent plus ici : elles disent combien de travail passe, pas combien de temps on attend. Pour cela, il faut modéliser l’attente elle-même, avec la théorie des files d’attente. Vous allez découvrir le modèle le plus simple et le plus utile, la file M/M/1, et une conclusion qui surprend toujours la première fois.

Décrire une file : la notation de Kendall

Une file d’attente se compose d’un ou plusieurs serveurs et d’une zone d’attente. Des clients (requêtes, paquets, tâches) arrivent, attendent si tous les serveurs sont occupés, sont servis, puis repartent. Pour décrire une file sans ambiguïté, on utilise la notation de Kendall :

$$A \,/\, B \,/\, c \,/\, K \,/\, N \,/\, D$$

Lettre	Signification	Valeurs courantes
$A$	loi des temps entre deux arrivées	M, D, E, H, G
$B$	loi des temps de service	M, D, E, H, G
$c$	nombre de serveurs	1, 2, …
$K$	capacité du système (attente comprise)	$\infty$ par défaut
$N$	taille de la population de clients	$\infty$ par défaut
$D$	discipline de service	FCFS par défaut

Les lettres pour les lois sont : M pour Markov (loi exponentielle, sans mémoire : les arrivées forment un processus de Poisson), D pour déterministe (durée constante), E pour Erlang, H pour hyper-exponentielle et G pour une loi générale quelconque. Les disciplines les plus courantes sont FCFS (premier arrivé, premier servi), LCFS (dernier arrivé, premier servi) et RR (tourniquet, round-robin, où chaque client reçoit à tour de rôle une petite tranche de service).

Quand $K$, $N$ et $D$ prennent leur valeur par défaut, on les omet : M/M/1 désigne une file à arrivées de Poisson, services exponentiels, un seul serveur, capacité et population infinies, discipline FCFS.

Attention

Certains formulaires écrivent « FCLS » pour la deuxième discipline. Le sigle standard est LCFS (last come, first served) : le dernier arrivé est servi en premier, comme une pile.

Les variables d’une file

• $\tau$ : temps entre deux arrivées ; $\lambda = 1/E[\tau]$ est le taux d’arrivée ;
• $S$ : temps de service d’un client ; $\mu = 1/E[S]$ est le taux de service d’un serveur (et $c\mu$ pour $c$ serveurs) ;
• $N_w$ et $N_s$ : nombre de clients en attente et en service, $N = N_w + N_s$ ;
• $W$ : temps d’attente, $R = W + S$ : temps de réponse.

Un client passe W dans la zone d'attente puis S au serveur : son temps de réponse est R = W + S. Seul S dépend du serveur ; W dépend de ceux qui sont arrivés avant lui.

L’utilisation d’une file à un serveur est $U = \lambda S = \lambda / \mu$ (loi d’utilisation). La file n’est stable que si $U < 1$ : sinon, il arrive plus de travail que le serveur ne peut en traiter, et la file grandit sans limite.

La file M/M/1

Pourquoi l’exponentielle ?

La loi exponentielle a une propriété unique : elle est sans mémoire. Si un service dure en moyenne 20 ms et qu’il a déjà duré 50 ms, la durée restante vaut encore 20 ms en moyenne. Cela semble artificiel, mais c’est une bonne approximation quand beaucoup d’utilisateurs indépendants envoient des requêtes (les arrivées forment alors presque un processus de Poisson), et surtout cela rend les calculs possibles. Le nombre de clients dans une file M/M/1 est une chaîne de Markov à temps continu, de type naissance et mort, dont on sait calculer la loi stationnaire. Vous trouverez cette démarche dans le cours de Modèles stochastiques.

Ici, retenons le résultat : en régime stationnaire, la probabilité d’avoir $n$ clients dans le système vaut $p_n = (1 - U)\,U^n$, une loi géométrique.

Les formules, par le raisonnement

On peut retrouver les formules principales sans chaîne de Markov, avec un raisonnement que l’on réutilisera au chapitre 5. Un client qui arrive trouve en moyenne $Q$ clients devant lui (avec des arrivées de Poisson, un arrivant voit l’état moyen de la file). Il doit attendre leur service à tous, puis recevoir le sien. Grâce à l’absence de mémoire, le client en cours de service a encore $S$ à faire en moyenne. Donc :

$$R = S\,(1 + Q)$$

Par la loi de Little appliquée à la file, $Q = X R = \lambda R$. En remplaçant : $Q = \lambda S (1 + Q) = U(1 + Q)$, d’où :

$$Q = \frac{U}{1 - U} \qquad \text{et} \qquad R = \frac{S}{1 - U}$$

• $Q$ est le nombre moyen de clients dans la file (en attente et en service) ;
• $R$ est le temps de réponse moyen ;
• $S$ est le temps de service moyen, et $U = \lambda S$ l’utilisation.

On en déduit le temps d’attente $W = R - S = U S/(1 - U)$.

Exemple

Le module de paiement a $S = 20$ ms.

• À $\lambda = 10$ commandes/s : $U = 0{,}2$, $R = 20/0{,}8 = 25$ ms, $Q = 0{,}25$.
• À $\lambda = 40$ commandes/s : $U = 0{,}8$, $R = 20/0{,}2 = 100$ ms, $Q = 4$.
• À $\lambda = 45$ commandes/s : $U = 0{,}9$, $R = 20/0{,}1 = 200$ ms, $Q = 9$.

Passer de 40 à 45 commandes/s (+12,5 % de charge) double le temps de réponse.

Pourquoi la latence explose près de la saturation

La formule $R = S/(1 - U)$ est sans doute la plus importante du cours pour un ingénieur. Le facteur $1/(1 - U)$ vaut 2 à 50 % d’utilisation, 5 à 80 %, 10 à 90 %, 100 à 99 %. La courbe a la forme d’une crosse de hockey :

Mais pourquoi ? Bonne question ! Parce que les arrivées sont aléatoires. Même quand le serveur a en moyenne 10 % de temps libre, les requêtes arrivent parfois en rafale ; la file se remplit, et il faut du temps libre pour la vider. Plus ce temps libre est rare, plus les rafales s’accumulent. Avec des arrivées parfaitement régulières et des services constants (une file D/D/1), il n’y aurait aucune attente jusqu’à 100 %. C’est la variabilité qui crée l’attente.

Même charge, même utilisation de 90 % : seule la variabilité change. Les rafales aléatoires remplissent la file, que le serveur presque plein met longtemps à vider.

À retenir

Dans une file M/M/1, $R = S/(1 - U)$ : le temps de réponse double à 50 % d’utilisation, est multiplié par 5 à 80 % et par 10 à 90 %. Viser 100 % d’utilisation est une erreur : la latence explose bien avant. En pratique, on dimensionne les ressources critiques pour rester autour de 60 à 70 % au pic.

Et les percentiles ?

Dans une file M/M/1 FCFS, le temps de réponse suit lui-même une loi exponentielle de moyenne $R$. Son percentile $q$ vaut donc $R \ln\big(1/(1 - q)\big)$ : le p95 vaut environ $3R$ et le p99 environ $4{,}6R$. À 40 commandes/s, le paiement a un temps moyen de 100 ms, mais un p95 de 300 ms et un p99 de 460 ms. Si votre objectif porte sur le p99, la saturation arrive encore plus vite.

La moyenne est à 100 ms, mais 5 % des paiements dépassent 300 ms et 1 % dépassent 460 ms : la queue de l'exponentielle est longue.

En entretien

« La latence explose près de la saturation parce que la variabilité des arrivées crée des files qu’un serveur presque plein n’a pas le temps de vider. Dans le modèle M/M/1, le temps de réponse vaut le temps de service divisé par un moins l’utilisation : à 90 % de charge, on attend dix fois le temps de service. »

Au-delà de M/M/1

Le centre de délai

Certains « serveurs » n’ont pas de file : chaque client est servi immédiatement, comme s’il y avait une infinité de serveurs. C’est le cas du temps de réflexion des utilisateurs (chacun réfléchit de son côté) ou d’un réseau à très grande capacité. Pour un tel centre de délai, $R = S$ et il n’y a jamais d’attente.

Plusieurs serveurs : M/M/c

Avec $c$ serveurs identiques, la file est stable si $\lambda < c\mu$. Les formules générales sont plus lourdes (formule d’Erlang C), mais le cas $c = 2$ reste simple : en notant $\rho = \lambda S/2$ l’utilisation de chaque serveur, $R = S/(1 - \rho^2)$.

Voici une question classique : vaut-il mieux un serveur deux fois plus rapide ou deux serveurs ? À 40 commandes/s, un serveur à 10 ms ($U = 0{,}4$) donne $R = 10/0{,}6 \approx 16{,}7$ ms. Deux serveurs à 20 ms ($\rho = 0{,}4$) donnent $R = 20/0{,}84 \approx 23{,}8$ ms. Le serveur rapide gagne : quand la charge est faible, chaque requête profite de toute sa vitesse, alors qu’avec deux serveurs lents, une requête isolée prend toujours 20 ms. En contrepartie, deux serveurs offrent la tolérance aux pannes.

Le serveur rapide l'emporte partout, surtout à faible charge où chaque requête profite de toute sa vitesse ; près de la saturation commune, l'attente domine et les deux se valent.

Un réseau ouvert de files

Revenons à la billetterie entière, vue comme un réseau ouvert (les commandes arrivent de l’extérieur à un taux $\lambda$). Si l’on approche chaque ressource par une file M/M/1, son utilisation vaut $U_i = \lambda D_i$ et le temps passé sur la ressource par requête, toutes visites comprises, vaut :

$$R_i = \frac{D_i}{1 - U_i}, \qquad R = \sum_i R_i$$

def reseau_ouvert(D, lam):
    """Temps de réponse d'un réseau ouvert de files M/M/1 (approximation)."""
    R = 0.0
    for nom, d in D.items():
        U = lam * d                                   # loi d'utilisation
        if U >= 1:
            raise ValueError(f"{nom} saturé (U = {U:.2f})")
        R += d / (1 - U)                              # temps de résidence sur la ressource
        print(f"  {nom:<7} U = {U:.2f}  R_i = {d / (1 - U) * 1000:6.1f} ms")
    return R

D = {"web": 0.020, "cpu": 0.030, "disque": 0.060}     # demandes du chapitre 2 (s)
for lam in (10, 14):
    print(f"lambda = {lam} req/s")
    print(f"  R total = {reseau_ouvert(D, lam) * 1000:.0f} ms")

À 10 commandes/s, on obtient environ 218 ms, dont 150 ms sur le disque. À 14 commandes/s (+40 %), le disque passe à 84 % d’utilisation et le temps de réponse total à environ 455 ms : il fait plus que doubler, presque entièrement à cause du goulot.

Le web et le processeur ajoutent une tranche presque constante ; c'est la tranche du disque, le goulot, qui explose quand son utilisation approche 1.

Piège

Confondre le temps de service $S$ (sans attente) et le temps de réponse $R$ (avec attente), ou, dans un réseau, $S_i$ (par visite) et $D_i$ (par requête). Dans la formule du réseau ouvert, c’est bien $D_i$ qui figure, car on veut le temps total passé sur la ressource par requête.

En résumé

• La notation de Kendall A/B/c/K/N/D décrit une file : lois d’arrivée et de service (M, D, E, H, G), nombre de serveurs, capacité, population, discipline (FCFS, LCFS, RR).
• Une file à un serveur est stable si $U = \lambda S < 1$.
• M/M/1 : $Q = U/(1 - U)$ et $R = S/(1 - U)$, obtenus par $R = S(1 + Q)$ et la loi de Little.
• La latence explose près de la saturation : ×2 à 50 %, ×5 à 80 %, ×10 à 90 %. La cause est la variabilité des arrivées et des services.
• Dans une M/M/1, le temps de réponse est exponentiel : p95 ≈ $3R$, p99 ≈ $4{,}6R$.
• Un centre de délai n’a pas d’attente ($R = S$) ; un réseau ouvert s’approche par $R = \sum_i D_i/(1 - U_i)$.

Exercices

Exercice · Une file M/M/1

facile

Un service de redimensionnement d’images reçoit 30 images par seconde selon un processus de Poisson. Chaque image demande en moyenne 25 ms de traitement (loi exponentielle), sur un seul serveur.

Calculez l’utilisation, le nombre moyen d’images dans le système, le temps de réponse moyen et le temps d’attente moyen.

Voir la solution

• $U = \lambda S = 30 \times 0{,}025 = 0{,}75$.
• $Q = U/(1 - U) = 0{,}75/0{,}25 = 3$ images.
• $R = S/(1 - U) = 25/0{,}25 = 100$ ms. On vérifie Little : $Q = \lambda R = 30 \times 0{,}1 = 3$.
• $W = R - S = 100 - 25 = 75$ ms : les trois quarts du temps de réponse sont de l’attente.

En code

Python

lam, S = 30, 0.025              # arrivées (images/s), temps de service moyen (s)

U = lam * S                     # utilisation
Q = U / (1 - U)                 # nombre moyen d'images dans le système
R = S / (1 - U)                 # temps de réponse moyen
W = R - S                       # temps d'attente moyen
print(U, Q, round(R * 1000, 1), round(W * 1000, 1))   # 0.75 3.0 100.0 75.0 (ms)
print(lam * R)                  # 3.0 : Little redonne bien Q

R

lam <- 30; S <- 0.025           # arrivées (images/s), temps de service moyen (s)

U <- lam * S                    # utilisation
Q <- U / (1 - U)                # nombre moyen d'images dans le système
R <- S / (1 - U)                # temps de réponse moyen
W <- R - S                      # temps d'attente moyen
c(U = U, Q = Q, R_ms = R * 1000, W_ms = W * 1000)   # 0.75  3  100  75
lam * R                         # 3 : Little redonne bien Q

Exercice · Respecter un objectif de latence

moyen

Un service d’inférence a un temps de service moyen de 8 ms. On l’approche par une file M/M/1.

1. Quel taux d’arrivée maximal permet de garder un temps de réponse moyen sous 40 ms ?
2. Même question pour un p99 sous 40 ms.

Voir la solution

1. $R = S/(1 - U) \leq 40$ ms donne $1 - U \geq 8/40 = 0{,}2$, soit $U \leq 0{,}8$, donc $\lambda \leq 0{,}8/0{,}008 = 100$ req/s.
2. Le p99 vaut $R \ln 100 \approx 4{,}605 R$. Il faut $R \leq 40/4{,}605 \approx 8{,}69$ ms, soit $1 - U \geq 8/8{,}69 \approx 0{,}921$, donc $U \leq 0{,}079$ et $\lambda \leq 0{,}079/0{,}008 \approx 9{,}9$ req/s. Un objectif sur le p99 aussi serré que le temps de service impose de laisser le serveur presque vide : il faudrait plutôt accélérer le service ou ajouter des serveurs.

En code

Python

import numpy as np

S, cible = 0.008, 0.040                 # temps de service et objectif (s)

# 1. Moyenne : S / (1 - U) <= cible  =>  U <= 1 - S / cible
U_moy = 1 - S / cible
print(U_moy, U_moy / S)                 # 0.8  100 req/s

# 2. p99 : le temps de réponse est exponentiel, p99 = R * ln(100)
R_max = cible / np.log(100)             # R à ne pas dépasser
U_p99 = 1 - S / R_max
print(R_max * 1000, U_p99, U_p99 / S)   # 8.69 ms  0.079  9.87 req/s

R

S <- 0.008; cible <- 0.040              # temps de service et objectif (s)

# 1. Moyenne : S / (1 - U) <= cible  =>  U <= 1 - S / cible
U_moy <- 1 - S / cible
c(U_moy, U_moy / S)                     # 0.8  100 req/s

# 2. p99 : le temps de réponse est exponentiel, p99 = R * ln(100)
R_max <- cible / log(100)               # R à ne pas dépasser
U_p99 <- 1 - S / R_max
c(R_max * 1000, U_p99, U_p99 / S)       # 8.69 ms  0.079  9.87 req/s

Exercice · Un goulot dans un réseau ouvert

difficile

Un pipeline de traitement de journaux reçoit des lots au taux $\lambda$. Chaque lot a une demande de 50 ms sur le processeur, 80 ms sur le disque et 20 ms sur le réseau.

1. Quel est le taux maximal supportable ?
2. Calculez le temps de réponse à $\lambda = 5$ lots/s puis à $\lambda = 10$ lots/s, en approchant chaque ressource par une file M/M/1.
3. On remplace le disque par un modèle deux fois plus rapide. Que devient le temps de réponse à 10 lots/s ?

Voir la solution

1. Le goulot est le disque ($D_{\max} = 80$ ms), donc $\lambda < 1/0{,}08 = 12{,}5$ lots/s.
2. À $\lambda = 5$ : utilisations 0,25, 0,4 et 0,1. $R = 50/0{,}75 + 80/0{,}6 + 20/0{,}9 \approx 66{,}7 + 133{,}3 + 22{,}2 = 222$ ms. À $\lambda = 10$ : utilisations 0,5, 0,8 et 0,2. $R = 50/0{,}5 + 80/0{,}2 + 20/0{,}8 = 100 + 400 + 25 = 525$ ms.
3. Avec $D_{\text{disque}} = 40$ ms, à $\lambda = 10$ : le disque est à 0,4 et $R = 100 + 40/0{,}6 + 25 \approx 100 + 66{,}7 + 25 = 191{,}7$ ms. Le temps de réponse est presque divisé par 3, et le processeur (50 %) est désormais le goulot.

En code

Python

def reseau_ouvert(D, lam):
    """Temps de réponse (s) d'un réseau ouvert de files M/M/1 : somme des D_i / (1 - U_i)."""
    return sum(d / (1 - lam * d) for d in D)

D = [0.050, 0.080, 0.020]                         # processeur, disque, réseau (s)
print(1 / max(D))                                 # 12.5 lots/s au maximum
for lam in (5, 10):
    print(lam, round(reseau_ouvert(D, lam) * 1000, 1))   # 5 -> 222.2 ms, 10 -> 525.0 ms

D_ssd = [0.050, 0.040, 0.020]                     # disque deux fois plus rapide
print(round(reseau_ouvert(D_ssd, 10) * 1000, 1))  # 191.7 ms

R

# Temps de réponse (s) d'un réseau ouvert de files M/M/1 : somme des D_i / (1 - U_i)
reseau_ouvert <- function(D, lam) sum(D / (1 - lam * D))

D <- c(0.050, 0.080, 0.020)                       # processeur, disque, réseau (s)
1 / max(D)                                        # 12.5 lots/s au maximum
sapply(c(5, 10), function(lam) reseau_ouvert(D, lam) * 1000)   # 222.2  525.0 ms

D_ssd <- c(0.050, 0.040, 0.020)                   # disque deux fois plus rapide
reseau_ouvert(D_ssd, 10) * 1000                   # 191.7 ms