D'abord, nous considérons des cas où les résultats possibles des observations font partie d'un ensemble fini de valeurs. Par exemple, nous considérons que le temps qu'un professeur prend pour corriger un examen prend ou 1, 2, 3 ou 5 heures (on ne compte pas les minutes). Si la probabilité pour chaque valeur est la même (soit 0.25 = 1/4) nous disons que le temps de correction a une distribution uniforme entre les valeurs 1 à 4, inclusivement.
Quelle serait la distribution pour le temps requis par le professeur pour corriger deux examens ? - Réponse: les valeurs 2 et 8 ont une probabilité (1/16), les valeurs 3 et 7 ont une probabilité 2 * (1/16), les valeurs 4 et 6 ont une probabilité 3 * (1/16), et la valeur 5 a une probabilité 4 * (1/16). Ceci s'approche une distribution normale.
La moyenne d'une distribution sur un ensemble de valeurs Vi (i = 1 ... N) est égale à (Sum over all i of Vi * Pi ) / N où Pi est la probabilité que Vi arrive. Notez que les valeurs de probabilité sont toujours normalisées pour que leur somme soit égale à 1 (un).
Dans le cas où 'il y a un ensemble infini de valeurs, par exemple tous les nombres réels entre zéro et infini, la moyenne est définie par l'intégrale sur x * Px * dx où Px * dx est la probabilité qu'une valeur entre x et (x + dx) arrive (dx est un différentiel - très petit).
Il y a deux valeurs importantes pour une distribution: la moyenne Av et l'écart type (déviation standard) SD. L'écart type est égal à la racine carrée de ((Sum over all i of (Av - Vi )**2) / N )
Modèles de performance: On introduit des modèles de performance quand on est intéressé par la performance du système. Souvent on est intéressé par le temps de réponse d'un système. Si l'on fait l'hypothèse que le temps de réponse ne dépend pas de la requête particulière envoyée par l'usager, et si la prochaine requête est seulement envoyée quand le système a fourni la réponse à la requête précédente, alors on peut caractériser la performance du système par une distribution sur les valeurs réelles entre zéro et infini représentant la probabilité d'obtenir un temps de réponse avec une valeur entre x et (x + dx).
Erreur estimé de mesures: La moyenne du temps de réponse (moyenne à la limite d'un très grand nombre de mesures) sera égale à la moyenne de la distribution. Par contre, on veut souvent déterminer le temps de réponse en faisant seulement un petit nombre de mesures, disons N mesures. Puisque les N valeurs de temps de réponse observées par nos expérimentations seront sélectionnées aléatoirement d'après la distribution du temps de réponse, on peut s'attendre que la moyenne calculée de ces N valeurs ne sera pas exactement égale à la moyenne "réelle" de la distribution. Cette différence est l'erreur estimée de la moyenne calculée des N observations. Il est évident aussi que chaque fois que nous faisons N mesures, nous allons obtenir une valeur différente pour la moyenne. Donc, la moyenne de N mesures a une certaine distribution. On peut montrer que la moyenne (pour un très grand nombre de fois que N mesures sont faites) des moyennes calculées est égale à la moyenne de la "vraie" distribution, et que l'écart type des moyennes calculées est égal à l'écart type de la "vraie" distribution divisée par la racine carrée de N (voir Wikipedia - "Standard error of mean" - voir aussi Écart type ou Standard Deviation).Cela veut dire que l'erreur estimée de la moyenne est plus petit que l'écart type (l'erreur estimée pour une expérimentation simple) par un facteur un sur la racine carrée de N.
L'erreur statistique attendu dans des histogrammes: Un histogramme est un tableau qui accumule pour chaque boîte du tableau le nombre d'occurences d'événements qui ont une valeur qui "tombe" dans la boîte. Si les valeurs des événements dépendent d'un processus aléatoire, alors le nombre d'événements qui tombent dans une boîte particulière du tableau aura aussi des variations statistiques. La variation attendue du nombre d'événements est égale à la racine carrée du nombre moyenne attendu. Ceci est confirmé par l'expérimentation suivante.
De l'expérience avec des erreurs statistiques peut être obtenue par des simulations. Voici un programme de simulation qui construit un histogramme des temps inter-arrivée d'un processus d'arrivée de Poisson. Le nombre mesuré d'événements par boîte (comme déterminé par la simulation) est comparé avec le nombre attendu d'après la formule exponentielle de la distribution de Poisson. Et ceci est montré dans ces diagrammes pour différentes valeurs du nombre moyenne attendu. Les variations statistiques des valeurs mesurées correspondent à peu près à la règle ci-haute. Les variations statistiques dépendent de la valeur graine utilisée par le générateur de nombres aléatoires, mais l'allure générale suit la règle ci-haut.
Le problème: Nous voulons modéliser un système qui consiste d'un grand nombre d'usagers et un serveur. Nous sommes intéressés à connaître le temps de réponse du serveur, ce qui est l'intervalle de temps entre le moment qu'une requête d'un usager arrive au serveur jusqu'au moment où le serveur a complété sa réponse (nous ignorons les délais de communication).
Supposons que le temps de service soit constant (1 seconde), c'est-à-dire, le serveur prend toujours exactement 1 seconde pour fournir une réponse à une requête. On suppose que le serveur traite une requête à la fois (pas de traitement en parallèle). Donc la distribution du temps de service est une fonction delta avec un pic à x = 1 seconde.
Si les usagers s'organisent entre eux d'une telle manière que la prochaine requête soit envoyée au serveur seulement après que la réponse ait été reçu de la dernière requête, alors le temps de réponse sera toujours égal au temps de service. Par contre, si les usagers ne s'organisent pas ainsi, il peut arriver qu'un usager envoie une requête quand la dernière requête n'est pas encore complètement traitée. Cela veut dire que le serveur sera occupé quand cette nouvelle requête arrive et la requête doit attendre (dans une quelconque file d'attente) avant d'être traitée par le serveur. C'est pourquoi le temps de réponse, dans ce cas-ci, sera plus long que le temps de service (temps de service plus temps d'attente). On voit que les relations entre les arrivées de requêtes ont un impact sur le temps de réponse du système.
Arrivées à la Poisson: Nous considérons une situation où il y a un très grand nombre d'usager indépendant (sans coordination entre eux) où chaque usager envoie de temps en temps une requête au serveur. On peut montrer que dans ce cas l'intervalle de temps entre une arrivée de requête jusqu'à l'arrivée de la requête suivante (appelé temps inter-arrivé) a une distribution exponentielle de la forme Pt = alpha * exp(- alpha * t) où alpha est le taux d'arrivée. En effet, la moyenne de cette distribution du temps inter-arrivé est 1/ alpha ce qui est le temps moyen entre deux requêtes consécutives. On voit que dans ce cas, il y a une bonne probabilité que le temps inter-arrivé soit bien plus petit que la moyenne; donc il serait intéressant de déterminer quel sera en moyenne le temps d'attente des requêtes dans la file d'attente du serveur. Une réponse est donnée par les modèles de files d'attente.
Conclusion importante: On ne peut pas déterminer le temps de réponse d'un serveur sans connaître le patron des arrivée de requêtes. La garantie de performance d'un serveur dépend de l'hypothèse sur son environnement (qui détermine la distribution des arrivées de requêtes).
Dans le cas le plus simple, un modèle de file d'attente représente un système où les requêtes arrivent d'une façon aléatoire (distribution de Poisson - avec une distribution du temps inter-arrivée exponentiel) et une ressource partagée qui est requise pour l'exécution d'une requête. La ressource travaille sur une requête à la fois; les autres requêtes doivent attendre dans une file d'attente. On suppose que le temps de service de la ressource est connu (ou fixe, ou une distribution de temps). Des formules analytiques simples existent pour calculer le temps moyen d'attente, le temps total de service (incluant le temps d'attente - c'est le temps de réponse), la longueur moyenne de la file, etc. (voir pour une introduction "Queuing Analysis" (en anglais) ou (plus court en français)).
Pour le cas d'un ressource simple avec un temps de service exponentiel et l'arrivée des requêtes à distribution de Poisson, nous avons les formules suivantes:
Le facteur 1 / (1- ρ) est typique pour les formules de files d'attente. Il montre que le temps de réponse explose quand le taux d'arrivée approche le temps moyen de service. Pour des valeurs de ρ égale ou supérieure à 1, le système est complètement sur-chargé et la file d'attente croit sans limite. La distribution du temps de service pourrait ne pas être exponentielle - différentes autres distributions peuvent être considérées (formules similaires).
Hypothèse: L'hypothèse principale est la suivante (pas toujours satisfaite - mais les formules donnent quand même souvent des bonnes approximations):
Exemple: Supposant un temps inter-arrivée moyen égale à 90% du temps de service, et un temps de service fixe. Si les requêtes arrivent en des intervalles de temps réguliers, alors chaque requête sera traitée avant que la prochaine arrive - donc, pas de delais d'attentes. Si les requêtes arrivent indépendamment (avec une distribution de Poisson), alors la formule ci-haute montre que le temps de réponse est 10 fois plus grand que le temps de service - le délai dans la file d'attente est en moyenne 9 fois plus grand que le temps de service.
Modèles de simulation : Quand les modèles de files d'attente ne sont pas facilement applicables (hypothèses de base non satisfaites ou systèmes plus complexes), on construit souvent des modèles de simulation. Ils pourraient être assez détaillés, dépendant des aspects que l'on veut modéler. Mais, ils exigent normalement beaucoup de temps de calcul pour obtenir des résultats avec assez de précision statistique. Voir laboratoire 11.
Il y a principalement deux approches pour écrire des programmes de simulation:
Les deux approches utilisent des structures de programmes très différentes. Voici quelques commentaires::
Notes de cours (en anglais)