Théorie des files d'attentes

1 Introduction

La théorie des files d'attente est une théorie mathématique relevant du domaine des probabilités, qui étudie les solutions optimales de gestion des files d’attente, ou queues. Une queue est nécessaire et se créera d'elle même si ce n'est pas anticipé, dans tous les cas où l'offre est inférieure à la demande, même temporairement. Elle peut s’appliquer à différentes situations : gestion des avions au décollage ou à l’atterrissage, attente des clients et des administrés aux guichets, ou bien encore stockage des programmes informatiques avant leur traitement. Ce domaine de recherches, né en 1917, des travaux de l’ingénieur danois Erlang sur la gestion des réseaux téléphoniques de Copenhague entre 1909 et 1920, étudie notamment les systèmes d’arrivée dans une queue, les différentes priorités de chaque nouvel arrivant, ainsi que la modélisation statistique des temps d’exécution. C'est grâce aux apports des mathématiciens Khintchine, Palm, Kendall, Pollaczek et Kolmogorov que la théorie s'est vraiment développée.

2 La loi de Little

Little a démontré mathématiquement ce que Erlang avait dit des années auparavant. Voici la loi :

L = A x W

• L : La longueur de la file d'attente qui correspond à une moyenne de requêtes en attente du système
• A : C'est le taux d'entrée de requêtes dans le système (x/seconde)
• W : Moyenne de temps pour satisfaire une requête

3 Taille de la file d'attente

Les requêtes sont stockées en mémoire. Donc L peut être un cache de lecture/écriture tunable ou de lecture seulement pour des mesures. Il existe des algorithmes pour gérer les priorités de file d'attente :

• Deux files d'attentes (1 pour les requêtes urgentes, 1 pour les requêtes normale). Les requêtes sont traitées selon l'urgence de celles ci.
• Une seule file d'attente qui va traiter les requêtes urgentes en priorité. Les requêtes normales ne seront traitées que si il n'y a plus d'urgentes.

4 Taille de la file d'attente et temps d'attente

L a tendance à varier directement avec W. Exemple bête :

100 requêtes = 100 requêtes/seconde * 1s

200 requêtes = 100 requêtes/seconde * 2s

800 requêtes = 100 requêtes/seconde * 8s

On peut donc prédire le rendement du temps d'attente en restreignant la taille de la file d'attente.
De même, on peut restreindre le temps d'attente pour optimiser la taille de la file d'attente (en mémoire).

5 Temps d'attente

Le temps d'attente comprends

(W = Q + S)

• Temps de file d'attente : temps d'attente pour qu'une ressource devienne disponible
• Temps de service : temps pour une ressource à exécuter une requête

Le but est de réduire le temps de la file d'attente et le temps de service. Pour exemple, un temps d'attente correspond à une page web qui se charge. Son temps d'exécution peut mettre un certain temps qui peut être multiplié en fonction du nombre de requêtes parallèles.

Si nous regardons d'un côté plus accès système :

W = Q + (T(système) + T(user))

• Temps système : temps pour une tâche kernel
• Temps utilisateur : temps pour une tâche utilisateur

Vous pouvez obtenir plus d'informations dans le man de la commande time ou bien top. Le but est donc :

• De réduire le temps système (mais va bloquer les opérations pour les utilisateurs)
• Passer autant de temps que nécessaire à des tâches utilisateur (mais pas plus)

Le temps de service correspond au temps qu'un processus prends pour exécuter une tache insérée dans la queue jusqu'à la fin de son exécution. Ce type de service peut être calculé sous la forme utilisation / débit.
Le temps moyen d'un service est définit par la quantité d'occupation d'une ressource par requête : S = Temps d'occupation / achèvement par seconde

6 Algorithmes de temps utilisateurs

Il existe des complexité asymptotic qui permettent de se rendre compte quel est le temps utilisateur nécessaire pour exécuter x requêtes :

• Intractable : O(2^n)
• Polynominal : O(n^2)
• Linear : O(50n)
• Constant : O(1)
• Logarithmic : O(500 log n)

Note : O décrit l'ordre du taux de croissance dans un moment de l'exécution ou l'utilisation de la mémoire d'un algorithme quand ses entrées croîent.

Lorsque l'on change d'algorithme, on peut améliorer les performances en réduisant le temps d'attente et augmentant le débit (nombre d'actions).

7 Profiling avec la commande time

La commande time permet de connaitre le temps d'exécution d'une commande :

time

> export TIME="\n%e %S %U" > time tar -czf deimos.tgz /home/deimos real 0m0.017s user 0m0.001s sys 0m0.001s

• real : c'est le temps réel que l'application met pour s'exécuter
• user : c'est le temps CPU nécessaire pour exécuter ses instructions
• sys : c'est le temps que le CPU met pour les appels kernel ou en attente d'I/O

Pour obtenir le temps de la file d'attente : Q = W - (Tsys + Tuser)

8 Taux d'achèvement

La bande passante (théorique) correspond à une taille de données qui peuvent être transférées en un certain nombre de temps.
La bande passante (réelle) correspond à une taille de données qui sont transférées en un certain nombre de temps.
Le débit quant à lui, correspond à une taille de données utilisable qui sont transférées en un certain nombre de temps.
L'overhead est la différence entre la bande passante réelle et le débit. C'est le surplus des données réelles transférées.
Pour des données transférées à une certaine bande passante, le débit sera toujours inférieure à la bande passante.

Le taux d'achèvement est le taux auquel le travail est effectué à un certain débit ou une certaine bande passante :

x = travaux effectués / temps d'observation

La bande passante est généralement prédictible, mais on peut réduire l'overhead pour accélérer le temps de traitement. Par exemple sur un réseau à 100Mb/s, on peut mesurer 80Mb/s de données au niveau de la couche application (OSI). Car dans les faits, nous avons 20Mb/s d'overhead (20 + 80 = 100).
Si nous réduisons l'overhead à 10, on pourra augmenter le débit à 90Mb/s.

B (bandwith) = X (transferts) + O (overhead)

Il faut cependant savoir que réduire l'overhead peut infliger des comportement indésirable. Par exemple si nous décidons de réduire l'overhead en choisissant l'UDP au lieu de TCP sur une application (du fait que l'UDP a moins d'overhead que le TCP). Si sur le réseaux, nous avons de la perte de paquets, l'application risque de redemander la retransmission de la requête. Du coup, l'application risque de faire plus d'overhead qu'avec des sessions UDP.
Suivant les application, les données n'ont pas forcément besoin d'être retransmise (tel que les sites de musique en ligne). Au bout d'un certains nombre de paquets non transmit, le client peut donner un message d'erreur pour mauvaise transmission des données.

9 Taux d'arrivée et taux d'achèvement

Le taux d'achèvement est le taux auquel le travail est effectué et est lié au débit, ainsi qu'à la bande passante (en fonction du contexte).

A (nombre d'arrivées) = C (nombre d'achèvement) / T (temps d'observation)

• T : le temps d’observation correspond au temps de imparti pour l'exécution d'évènements dans un temps donné (ex: en secondes)
• A : Le nombre d'arrivées observées durant la période d'observation (ex: paquets/s)

Le nombre d'arrivées (A) qui ont été faites pendant un temps d'observation (T) sont référencées comme achevées (C).
Le temps d'occupation est le temps d'observation * le temps d'utilisation.

10 Trouver le meilleur temps d'observation

Il est important d'utiliser ce genre d'outils pendant des temps de charge non nulle. Faire une observation pendant un temps trop court ne permettra pas d'avoir des résultats satisfaisant. Il est conseiller donc de mesurer le temps d'observation de la manière suivante :

• Collecter les données le plus fréquemment possible (idéalement 1 seconde)
• Comparer les valeurs de mesure selon la loi de Little
• Est-ce que la comparaison est bonne ?
  • oui : le temps d'observation es valide et L = C x W
  • non : refaire la capture avec un intervalle de temps plus long

Nous allons maintenant calculer la longueur de la queue et la comparer aux données collectées.
Voici un exemple de capture :

dd

> dd if=/dev/zero of=/tmp/bigfile bs=1M count=1024 oflag=direct & sar -d -p 1 5 > sar_result ; pkill dd && rm -f /tmp/bigfile ; cat sar_result 23:45:05 DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm  %util 23:45:06 sda 227,00 9872,00 16288,00 115,24 6,85 28,58 4,39 99,6023:45:06 dev254-0 1,00 0,00 8,00 8,00 2,23 2836,00 284,00 28,40 23:45:06 dev254-1 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 23:45:06 dev254-2 206,00 10056,00 424,00 50,87 7,17 34,00 4,82 99,20 23:45:06 dev254-3 2541,00 40,00 20288,00 8,00 100,64 33,19 0,12 30,00   23:45:06 DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm  %util 23:45:07 sda 114,85 2811,88 12110,89 129,93 9,98 89,90 8,62 99,0123:45:07 dev254-0 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 23:45:07 dev254-1 0,99 0,00 7,92 8,00 0,07 68,00 68,00 6,73 23:45:07 dev254-2 84,16 2471,29 0,00 29,36 3,86 47,25 11,76 99,01 23:45:07 dev254-3 21,78 253,47 166,34 19,27 16,84 1514,73 37,09 80,79   23:45:07 DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm  %util 23:45:08 sda 207,00 4672,00 1304,00 28,87 6,09 29,72 4,83 100,0023:45:08 dev254-0 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 23:45:08 dev254-1 162,00 0,00 1296,00 8,00 59,80 369,14 4,02 65,20 23:45:08 dev254-2 185,00 4216,00 0,00 22,79 5,07 27,70 5,38 99,60 23:45:08 dev254-3 5,00 288,00 0,00 57,60 0,18 36,00 36,00 18,00   23:45:08 DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm  %util 23:45:09 sda 173,00 3208,00 0,00 18,54 3,54 19,93 5,78 100,0023:45:09 dev254-0 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 23:45:09 dev254-1 0,00 0,00 0,00 0,00 0,00 0,00 0,00 0,00 23:45:09 dev254-2 171,00 2744,00 0,00 16,05 3,30 18,76 5,85 100,00 23:45:09 dev254-3 3,00 520,00 0,00 173,33 0,16 54,67 54,67 16,40   23:45:09 DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm  %util 23:45:10 sda 155,56 3797,98 1470,71 33,87 3,29 21,71 6,36 98,9923:45:10 dev254-0 1,01 8,08 0,00 8,00 0,06 60,00 60,00 6,06 23:45:10 dev254-1 84,85 0,00 678,79 8,00 5,16 60,86 2,81 23,84 23:45:10 dev254-2 242,42 3498,99 791,92 17,70 6,40 26,77 4,02 97,37 23:45:10 dev254-3 1,01 242,42 0,00 240,00 0,08 76,00 76,00 7,68   23:45:10 DEV tps rd_sec/s wr_sec/s avgrq-sz avgqu-sz await svctm  %util 23:45:11 sda 74,75 1252,53 13292,93 194,59 0,95 12,81 5,35 40,0023:45:11 dev254-0 43,43 8,08 339,39 8,00 0,40 9,12 3,44 14,95 23:45:11 dev254-1 90,91 0,00 727,27 8,00 3,03 33,29 0,93 8,48 23:45:11 dev254-2 27,27 1204,04 0,00 44,15 0,28 10,81 8,30 22,63 23:45:11 dev254-3 1530,30 8,08 12234,34 8,00 25,25 16,36 0,16 25,05 ...

Par rapport aux colonnes que nous donne sar, voici la formule :

(rd_sec/s + wr_sec/s) * await / 1000 = requêtes/s

Donc si on reprends les informations ci dessus, on peut aisément calculer comme ceci (sur sda ici) :

awk

> grep sda sar_result | awk '{ printf("%s%s%s%s", "("$4" + ", $5") * ", $8" / 1000) = ", (($4+$5)*$8)/1000"\n") }'(9872,00 + 16288,00) * 28,58 / 1000) = 732.48 (2811,88 + 12110,89) * 89,90 / 1000) = 1327.97 (4672,00 + 1304,00) * 29,72 / 1000) = 173.304 (3208,00 + 0,00) * 19,93 / 1000) = 60.952 (3797,98 + 1470,71) * 21,71 / 1000) = 110.607 (1252,53 + 13292,93) * 12,81 / 1000) = 174.528 (1837,62 + 1900,99) * 13,89 / 1000) = 48.581 (2407,92 + 22922,77) * 42,17 / 1000) = 1063.82 (290,91 + 371,72) * 4,00 / 1000) = 2.644 (1096,00 + 96,00) * 7,64 / 1000) = 8.344 (118,10 + 3126,40) * 3,74 / 1000) = 9.732

Il est intéressant de laisser tourner ce genre d'outils un moment pour profiler une application sur un serveur par exemple et se rendre compte pendant une forte période de charge le nombre de requêtes disponibles.

11 Prédire les limites d'un système

Il faut déjà savoir qu'une ressource saturée est le goulet d'étranglement pour tout le système assuré ! Il faut donc veiller à ce qu'il n'y ai pas d'effet entonnoir sur vos ressources.

Réduire le nombre d'accès ou améliorer la bande passante permet de résoudre le problème, que ce soit pour n'importe quoi, CPU, RAM, Réseaux...

Il est donc important de bien connaitre le taux d'arrivé ainsi que la bande passante nécessaire pour paramétrer correctement votre matériel.